Б) Проверка домашнего задания (файл д_з.doc загружен на компьютере).

Пример 1. Докажите тавтологию ((X Y) (Y Z)) (X Z)

Решение.

F1

F2

F3

 

X	Y	Z	X Y	Y Z	X Z	F1 F2	(F1 F2) F3

Вывод. Высказывание ((X Y) (Y Z)) (X Z) является тавтологий (тождественно-истинное высказывание).

Пример 2. Установить истинность высказывания.

Решение.

А	В	С		С	А ( С)

Вывод. Высказывание истинно, когда:

А) A 0; B 0; C 0; Б) A 0; B 1; C 0; В) A 0; B 1; C 1.

Пример 3. Эквивалентны ли высказывания:

и

Решение.

А	В	С						B

Вывод.

Высказывание и высказывание не эквивалентны.

II. Составление таблиц истинности.

Упражнение 1. Из простых высказываний: “Виктор хороший пловец” - А; “Виктор хорошо ныряет” - В; “Виктор хорошо поет” - С, составлено сложное высказывание, формула которого имеет вид: X=(A C) (A B). Установить, эквивалентно ли высказывание Х высказыванию: “Виктор - хороший пловец и Виктор хорошо поет”.

Решение. Y=A C

А	В	С	A C	A B	X	Y=A C

Вывод. Высказывание X не эквивалентно высказыванию Y.

Упражнение 2. Установить является ли данное высказывание тавтологией.

A	B	A B

Вывод. Высказывание является тавтологией.

Упражнение 3. Установить истинность высказываний:

а) ((X1 X2) X3) (X3 X1)

			F1	F2	F3
X1	X2	X3	X1 X2	F1 X3	X3 X1	F2 F3
1	0	1	0	1	1	1
1	1	1	1	1	1	1

Вывод. Высказывание ((X1 X2) X3) (X3 X1) истинно, когда:

1) X1 1; X2 0; X3 0; 2) X1 1; X2 1; X3 1

б) ((X Y) (Y Z)) (X Z)

			F1	F2	F3	F4
X	Y	Z	X Y	Y Z	F1 F2	X Z	F3 F4

Вывод. Высказывание ((X Y) (Y Z)) (X Z) истинно всегда.

Упражнение 4. Для формулы придумайте формализуемое предложение.

Решение. Пусть А – «Петр замечательно играет в шахматы»; В — «Семен играет на баяне»; С — «Галина смотрит телевизор»

Тогда и только тогда если Петр замечательно играет в шахматы, то Семен не играет на баяне, когда Галина смотрит телевизор и Петр замечательно играет в шахматы.

Самостоятельная работа.

Вариант №1.

Установить истинность высказывания

Решение.

X	Y			X Y

2. Для формулы придумайте формализуемое предложение.

3. Установите, является ли высказывание (X Y) тавтологией.

Решение.

X	Y	(X Y)				(X Y)

Вывод. Высказывание тавтологией не является.

4. Установите, эквивалентны ли высказывания?

Решение.

A	B					A B

Вывод. X1 X3

Вариант №2.

1. Установить истинность высказывания

Решение.

X	Y	X Y

2. Для формулы придумайте формализуемое предложение.

3. Установите, является ли высказывание тавтологией.

Решение.

X	Y	X Y

Вывод. Высказывание тавтологией не является.

4. Установите, эквивалентны ли высказывания?

Решение.

X	Y

Вывод. A B

IV. Подача нового материала. ( Использоватьпрограмму MATLOG).

Равносильности формул логики высказываний часто называют законами логики. Знание законов логики позволяет проверять правильность рассуждений и доказательств. Нарушения этих законов приводят к логическим ошибкам и вытекающим из них противоречиям.

Перечислим наиболее важные из них:

1. X X Закон тождества.
2. Закон противоречия
3. Закон исключенного третьего
4. Закон двойного отрицания
5. Законы идемпотентности: X X X, X X C
6. Законы коммутативности (переместительности): X Y Y X, X Y Y X
7. Законы ассоциативности (сочетательности): (X Y) Z X (Y Z), (X Y) Z X (Y Z)
8. Законы дистрибутивности (распределительности): X (Y Z) (X Y) (X Z), X (Y Z) (X Y) (X Z)
9. Законы де Моргана ,
10. X 1 X, X 0 X
11. X 0 0, X 1 1
12. Законы поглощения: X (X Y) X, X (X Y) X
13. Законы склеивания: (X Y) ( Y) Y, (X Y) ( Y) Y

1-й закон сформулирован древнегреческим философом Аристотелем. Закон тождества утверждает, что мысль, заключенная в некотором высказывании, остается неизменной на протяжении всего рассуждения, в котором это высказывание фигурирует.

Закон противоречия говорит о том, что никакое предложение не может быть истинно одновременно со своим отрицанием. “Это яблоко спелое” и “Это яблоко не спелое”.

Закон исключенного третьего говорит о том, что для каждого высказывания имеются лишь две возможности: это высказывание либо истинно либо ложно. Третьего не дано. “Сегодня я получу 5 либо не получу”. Истинно либо суждение, либо его отрицание.

Закон двойного отрицания. Отрицать отрицание какого-нибудь высказывания - то же, что утверждать это высказывание.

“ Неверно, что 2*2<>4”

Законы идемпотентности. В алгебре логики нет показателей степеней и коэффициентов. Конъюнкция одинаковых “сомножителей” равносильна одному из них.

Законы коммутативности и ассоциативности. Конъюнкция и дизъюнкция аналогичны одноименным знакам умножения и сложения чисел.

В отличие от сложения и умножения чисел логическое сложение и умножение равноправны по отношению к дистрибутивности: не только конъюнкция дистрибутивна относительно дизъюнкции, но и дизъюнкция дистрибутивна относительно конъюнкции.

Смысл законов де Моргана (Август де Морган (1806-1871) - шотландский математик и логик) можно выразить в кратких словесных формулировках:

- отрицание логического произведения эквивалентно логической сумме отрицаний множителей.

- отрицание логической суммы эквивалентно логическому произведению отрицаний слагаемых.

Доказать законы логики можно:

1. с помощью таблиц истинности;
2. с помощью равносильностей.

Докажем законы склеивания и поглощения с помощью равносильностей:

1. (X Y) ( Y) (X+Y) *( +Y) X* + Y* + Y*Y+ X*Y Y* + Y + X*Y Y* + Y(1+X) Y* +Y Y( +1) Y склеивания
2. X (X Y) X*X+X*Y X+X*Y X(1+Y) X поглощения

 

Домашнее задание.

1. Является ли высказывание (X Y) (Y X) тавтологией.

2. Установить эквивалентны ли высказывания.

3. С помощью таблиц истинности доказать законы поглощения и склеивания.