Следование, эквивалентность и преобразование формул

Введем на множестве M отношения следования и эквивалентности.

Формула B следует из формулы A (обозначается A B), если она истинна на всех наборах высказывательных переменных, на которых истинна формула A.

Теорема 2.1. Формула B следует из формулы A тогда и только тогда, когда тождественно истинна формула A B.

Доказательство. Пусть формула B следует из формулы A. Импликация A B ложна только на тех интерпретациях, на которых формула А истинна, а В ложна, что невозможно в силу условия.

Покажем обратное. Пусть A B – тождественно истинна, тогда если на некоторой интерпретации формула А истинна, то и формула В истинна на ней, что и означает A B.

Формула A эквивалентна формуле B (обозначается A º B), если они следуют друг из друга, то есть A B и B A. Легко показать, что это определение эквивалентно определению, введенному в п.1.

Теорема 2.2. Формула A эквивалентна формуле B тогда и только тогда, когда тождественно истинна формула A ~ B.

Доказательство аналогично доказательству теоремы 2.1.

Приведем список основных тавтологий, выражающих свойства логических операций.

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

X Ù Y º Y Ù X, X Ú Y º YÚ X.

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

(X Ù Y)Ù Z º X Ù (YÙ Z), (XÚ Y)Ú Z º XÚ (YÚ Z).

3. Идемпотентность:

XÙ X º X, XÚ X º X.

4. Законы поглощения:

XÚ (X Y) º X, X (XÚ Y) º X.

5. Взаимная дистрибутивность конъюнкции и дизъюнкции:

X Ù (YÚ Z) º (X Ù Y)Ú (X Ù Z), XÚ (YÙ Z) º (XÚ Y)Ù (XÚ Z).

6. Свойства констант:

XÙ 0 º Л, XÙ 1 º X,

XÚ 0 º X, XÚ 1 º 1.

7. Законы де Моргана:

, .

8. Инволютивность:

.

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

º 0.

10. Закон исключенного третьего:

º 1.

Эквивалентность большинства из этих формул непосредственно следует из определения операций или проверяется построением таблиц истинности.

Пусть U – некоторая формула, в которую входит переменная X или подформула А, что обозначается U (¼, X, ¼) или U (¼, А, ¼). Пусть В – некоторая формула. Запись U (¼, X, ¼){ В // X } обозначает формулу, полученную из формулы U подстановкой формулы В вместо всех вхождений переменной X, а U (¼, А, ¼){ В / А } – формулу, полученную из формулы U подстановкой формулы В вместо некоторых (в частности, вместо одного) вхождений подформулы А.

Теорема 2.3 (правило подстановки). Если U (¼, X, ¼) – тавтология и В – любая формула, то U (¼, X, ¼){ В // X } – тавтология.

Теорема 2.4 (правило замены). Если A есть некоторая подформула формулы U и A эквивалентна формуле B, то формула, полученная заменой A в формуле U на B, эквивалентна U. Иными словами, если U (¼, А, ¼) и A º B, то U º V = U (¼, А, ¼){ В / А }.

Например, так как A®B º , то (A®B)Ù C º ()Ù C.

Следствие. Если U~A и V~B, то:

1) U V º A B;

2) U V º A B;

3) U V º A B;

4) (U ~ V) º (A ~ B);

5) U º A.

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