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

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

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

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

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

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

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

Теорема 2.3. Если A есть некоторая подформула формулы U и A эквивалентна формуле B, то формула, полученная заменой A в формуле Uна B, эквивалентна U. Иными словами, если A º B, то U(A) º U(B).

Например, так как 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 и ее следствие позволяют преобразовывать формулы, упрощая их, и доказывать эквивалентность формул. Приведем список основных тавтологий, выражающих свойства логических операций.

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.

Тождественная истинность всех формул (кроме законов поглощения) уже доказана непосредственно построением таблиц истинности.

Задание. Доказать 1-й из законов поглощения.

Решение.

.

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

11. .

12. .

13. Склеивание:

, .

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

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

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

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

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

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

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

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

Решение. ( ) º

º ( ) º ( ) º A.

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

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

U^*( ) = U( ).

Доказательство.Обозначим k – число логических операций в формуле U.Проведем доказательство индукцией по k.

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.6. Если U º V, то U^d º V^d.

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

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: