Формулы логики высказываний. Равносильность формул

Определение 1.2. Формула логики высказываний определяется индуктивно следующим образом:

1. Любая высказывательная переменная, а также константы И, Л есть формула.

2. Если A и B – формулы, то Ø А, A Ú B, A & B, А É B, А ~ B есть формулы.

3. Ничто, кроме указанного в пунктах 1 – 2, не есть формула.

Две формулы называются равносильными, если на всех одинаковых наборах переменных значения этих формул совпадают.

Равносильность формул A и B будем обозначать следующтм образом: A º B.

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

При доказательстве равносильности формул можно использовать принцип двойственности.

Символы &, Ú называются двойственными.

Формула F ^* называется двойственной формуле F, если она получена из F одновременной заменой всех символов &, Ú на двойственные.

Например, F = A Ú (B &Ø C);

F ^* = A & (B Ú Ø C).

Принцип двойственности.

Если F º G, то F ^* º G ^*.

Все законы равносильности, имеющие место для формул булевых функций, справедливы и для формул логики высказываний, причем единице соответствует истинностное значение И, а нулю – Л. Приведем эти законы.

Для любых формул A, B, C справедливы следующие равносильности:

1. Коммутативность.

а) A & B º B & A (для конъюнкции);

б) A Ú B º B Ú A (для дизъюнкции).

2. Ассоциативность.

а) A &(B & C) º (A & C)& C (для конъюнкции);

б) A Ú (B Ú C) º (A Ú B)Ú C (для дизъюнкции).

3. Дистрибутивность.

а) A &(B Ú C) º A & B Ú A & C (для конъюнкции относительно дизъюнкции);

б) A Ú(B & C) º (A Ú B)&(A Ú C) (для дизъюнкции относительно конъюнкции).

4. Закон де Моргана.

а) Ø(A & B) º ØÚ Ø B (отрицание конъюнкции есть дизъюнкция отрицаний);

б) Ø(A Ú B) º Ø A & Ø B (отрицание дизъюнкции есть конъюнкция отрицаний).

5. Идемпотентность.

а) A & A º A (для конъюнкции);

б) A Ú A º A (для дизъюнкции).

6. Поглощение.

а) A &(A Ú B) º A (1– ый закон поглощения);

б) A Ú A & B º A (2– ой закон поглощения).

7. Расщепление (склеивание).

а) A & B Ú A &(Ø B) º A (1–ый закон расщепления);

б) (A Ú B) & (A ÚØ B) º A (2–ой закон расщепления).

8. Двойное отрицание.

Ø(Ø A) º A.

9. Свойства констант.

а) A &И º A; б) A &Л º Л; в) A ÚИ º И; г) A Ú Л º A; д) ØЛ º И; е) ØИ º Л.

10. Закон противоречия.

A & Ø A º Л.

11. Закон “исключенного третьего”.

A Ú Ø A º И.

12. A É B ºØ A Ú B º Ø(A &Ø B).

13. A ~ B º (A É B)&(B É A) º (A & B) Ú (Ø A & B) º (АÚ Ø B)&(Ø A Ú B).

Каждая из перечисленных равносильностей может быть доказана с помощью таблиц значений функций, составленных для выражений, стоящих слева и справа от символа “º”.

Справедливы также обобщенные законы дистрибутивности и обобщенные законы де Моргана:

14. (A ₁Ú A ₂Ú...Ú A_n)&(B ₁Ú B ₂Ú...Ú B_m) º

A ₁& B ₁Ú A ₁& B ₂Ú...Ú A ₁& B_m Ú...Ú A_n & B ₁Ú A_n & B ₂Ú...Ú A_n & B_m.

15. (A ₁& A ₂&...& A_n) Ú (B ₁& B ₂&...& B_m) º

(A ₁Ú B ₁)&(A ₁Ú B ₂)&...&(A ₁Ú B_m)&...&(A_n Ú B ₁)&(A_n Ú B ₂)&...&(A_n Ú B_m).

16. Ø(A ₁& A ₂&...& A_n) º Ø A ₁ÚØ A ₂Ú...ÚØ A_n.

17. Ø(A ₁Ú A ₂Ú...Ú A_n) ºØ A ₁&Ø A ₂&...&Ø A_n

В равносильностях 1 – 17 в качестве A, B, A_i, B_i могут быть подставлены любые формулы и, в частности, переменные.

Пример 1.9.

Доказать равносильность формул логики высказываний:

(А É B) & (A Ú B) º B.

Преобразуем левую часть, последовательно используя равносильности 12, 14, 10, 5а, 9г, 6б:

(А É B) & (A Ú B) º (Ø А Ú B) & (A Ú B) º Ø А & A Ú Ø А & B Ú B & А Ú B & B º Ø А & B Ú B & А Ú B º B.

Равносильность доказана.