Основные тождества логики высказываний

_

1. А à В = А +В

2. А à В = А &В

3. А à В = В à А правило контрапозиции

4. А + В = А & В правила де Моргана

5. А & В = А + В

6. А & B = B & A правила коммутативности

7. A +B = B +A

8. A +(A & B) = A правила поглощения

9. A &(A +B) = A

10.A & (B +C) = (A & B) +(A & C) правила дистрибутивности

11. A +(B & C) = (A +B) &(A +C)

12.(A +B) &(C +D) = A & C +A & D +B &C +B & D правило раскрытия скобок

=

13.А = А правило двойного отрицания

14.А +A = A правила равносильности (идемпотентности)

15.A & A = A

16.A +( B +C) = (A +B) +C правила ассоциативности

17.A & ( B & C) = (A & B ) &C

18. A + A = 1

19. A & A = 0

20.A +1 = 1

21.A + 0 = A

22.A & 1 = A

23. A & 0 = 0

24.A &A & B = 0

25. A + A +B = 1

26. (А &A) +B = B

27. (A + A) &B = B

28. (A +B) &( A +B) =B

29. (A B)= (A +B) &( B +A)

30. (A +C) &( B + C)= (A +C) &(B + C) &(A +B)

31. (A +C) & C=(A +C) & C & A

32.C &(B + C) = С & (B + C) & B

Всем формулы логики высказываний делятся на три класса:

1. тождественно истинные формулы

2. тождественно ложные

3. те. которые при одних значениях входящих в них переменных истинны, а при других - ложны.

В 1 и 3 случаях формулы являются выполнимыми, т.е. истинными хотя бы при одном наборе истинностных значений входящих в них переменных.

Используя возможность замены одних символических выражений высказываний на другие, но тождественные исходным, можно, например, для любой формулы определить является ли она тождественно истинной формулой, т.е. законом логики, или тождественно ложной, или выполнимой при определенном сочетании истинностных значений переменных. Для этой цели применяется процедура приведения формулы логики высказываний к конъюнктивной нормальной форме (сокращенно КНФ).

КНФ - конъюнкция дизъюнкций переменных или их отрицание, т.е. кратная конъюнкция, конъюнктивные члены которой - это кратные дизъюнкции, в которых каждый из дизъюнктов есть какая-нибудь переменная или отрицание переменной. Например, формулы

(А + B + C) &(B + C) & (A +C); A & (A +B) &(B +C) & C &(A +B +C)

находятся в КНФ. Во второй формуле конъюнктивные члены А и С - «вырожденные» дизъюнкции с одним дизъюнктом.

Приведение любой формулы к КНФ предполагает следующие требования:

_ _

1. Все подформулы вида А Ñ B заменить на (А V В) ^ ( А V В)

2. Все подформулы вида А B заменить, согласно правилу 29, на формулы

_ _

( А +B) & (B +A)

3. Все подформулы вида В à C заменить, согласно правилу 1, на В +C или, на В&С, cогласно правилу 2.

4. Все отрицания, стоящие над сложными подформулами, опускаются до подформул, образовавшихся после первого шага формулы (по правилам де Моргана).

5.Устаняются все двойные отрицания над формулами, согласно правилу 13.

6.Раскрываются все скобки по правилу дистрибутивности дизъюнкции относительно конъюнкции - при приведении к КНФ, или дистрибутивности конъюнкции относительно дизъюнкции - при приведении к дизъюнктивной нормальной форме (сокращенно ДНФ).

Если в элементарной дизъюнкции содержится хотя бы одна пара дизъюнктов, один из которых есть некоторая переменная, а другой ее отрицание, то это будет тождественно истинная дизъюнкция.

Формула логики высказываний в КНФ тождественно истинна, если каждый из ее конъюнктивных членов т.е. каждая элементарная дизъюнкция, содержит хотя бы одну переменную со знаком отрицания и без него. Поэтому о тождественной истинности формулы можно судить по ее виду в КНФ.

Пусть дана формула (А& ( А àВ)) àВ

По правилу 1 избавляемся от импликаций (А&(А +B)) +В

В большой скобке применяем правило 5 (правило де Моргана)

_ _

(А +(А +B)) +В

В маленькой скобке применяем снова правило 5

_ _

(А +(А & B)) +В

В большой скобке применяем правило 11 (правило дистрибутивности)

_ _ _

((A + A) & (A + B)) + B

По правилу 16 (правило ассоциативности дизъюнкции) к каждому из конъюнктов в большой скобке присоединяем через знак «+» остающуюся В

_ _ _

(A + A + B) & (A + B + B)

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

Если в результате приведения к КНФ выяснится, что имеющаяся формула оказалась не тождественно истинной, то нужно проверить на тождественную истинность ее отрицание. Если отрицание данной формулы окажется тождественно истинной формулой, то значит сама исходная формула является тождественно ложной. Если же отрицание данной формулы окажется не тождественно истинным, то, значит, исходная формула при одних значениях переменных истинна, а при других ложна.

ЗАДАНИЕ 23. Путем приведения данной формулы логики высказываний к КНФ выяснить, является ли она тождественно истинной или тождественно ложной.

Вариант: _

1. (A + C) à((B & C) àA)

_

2. (AàA) à(Bà(A + C))

3. (AàC) à(Bà(B + C))

4. ((A+ B) & (AàC) & ( BàC)) àC

5. Aà((AàB) àB)

6. ((AàB) & (CàD)) à((AàC) à(B & D))

7. (AàB) à((A& C) à(A&C))

8. ((AàB) + (AàC)) à(Aà(A + C))

9. Aà(Bà(A&B))

_ _

10. ((AàB) &(BàC) &(CàA)) + A