Примеры. 1. Докажем 1-й из законов поглощения XÚ(X Y) º X.

1. Докажем 1-й из законов поглощения XÚ (X Y) º X.

.

При доказательстве использовано правило замены.

2. Упростить формулу .

Так как º X в силу подстановки в закон поглощения, тогда, используя правило замены получим

º .

Приведем еще несколько эквивалентностей, имеющих широкое применение.

11. .

12. .

13. Законы склеивания

, .

Эквивалентность формул является отношением эквивалентности, поэтому множество M можно разбить на классы эквивалентности, включив в один класс эквивалентные между собой формулы. Каждой формуле U соответствует класс эквивалентности, который обозначается [ U ].

Определение. Формула называется приведенной, если она содержит операции конъюнкции, дизъюнкции и операцию отрицания, относящуюся к высказывательным переменным.

Теорема 2.5. Каждый класс эквивалентности [ U ] может быть представлен приведенной формулой, т.е. для любой формулы U M существует приведенная формула V.

Доказательство теоремы проведём конструктивно, то есть определим порядок построения приведенной формулы.

1. Удаляются операции импликация и эквиваленция по формулам 11, 12.

2. Операции отрицания спускаются до высказывательных переменных с помощью законов де Моргана и двойного отрицания.

3. Если это возможно, то полученная приведенная формула упрощается с помощью свойств 3, 4, 5, 6, 9, 10.

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

Приведенная формула для данного класса эквивалентности не является единственной.

Задание. Упростить формулу .

Решение. º

º º º A.

Определение. Формула U^d называется двойственной к приведенной формуле U, если она получена заменой операций конъюнкции на дизъюнкции и наоборот.

Теорема 2.6 (принцип двойственности). Пусть U () – приведенная формула, тогда

U^d () = U( ).

Доказательство. Число логических операций в формуле U называется рангом формулы и обозначается r (U).Проведем доказательство индукцией по k = r (U).

1⁰. k = 0. В этом случае U = X_i, следовательно, U^d = X_i º º Ø U ().

2 ⁰. Предположим, что теорема верна при k £ m.

3 ⁰. Покажем, что она верна при k = m + 1.

Пусть U₁ и U₂ – подформулы U. Каждая из них образована посредством не более, чем m операций, и следовательно, для них теорема верна.

Возможны следующие случаи

а) U = Ø U₁;

б) U = U₁ Ù U₂;

в) U = U₁ Ú U₂.

Случай а) эквивалентен условию 1⁰ и при нем теорема верна. В случаях б) и в) заменим в каждой из U_i конъюнкцию на дизъюнкцию и наоборот. По определению двойственности будем иметь, соответственно, б): U^d = U Ú U и в): U^d = U Ù U .

В силу законов де Моргана и предположения индукции будем иметь в случае б):

U^d = U Ú U = (Ø U₁ ()) Ú (Ø U₂ ()) º

º Ø (U₁ () Ù U₂ ()) = Ø U ().

В случае в) выкладки аналогичны. Теорема доказана.

Следствие. Если U – ТИ-формула, то U^d – ТЛ-формула.

Теорема 2.7. Если U º V, то U^d º V^d.

Доказательство. Если U º V, то (Ø U) º (Ø V). Значит, в силу теоремы 2.6, U^d (Х₁, …, Х_n) = Ø U () и V^d (Х₁, …, Х_n) = Ø V ().

Отсюда: U^d = (Ø U ()) º (Ø V ()) = Ø V^d. В силу транзитивности эквиваленции, получим U^d º V^d , что и требовалось доказать.