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

Введем на множестве 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 UY º Y UX, X UY º YUX.

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

(X UY)UZ º X U(YUZ), (XUY)UZ º XU(YUZ).

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

XUX º X, XUX º X.

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

XU(X Y) º X, X (XUY) º X.

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

X U(YUZ) º (X UY)U(X UZ), XU (YUZ) º (XUY)U(XUZ).

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

XU0 º Л, XU1 º X,

XU0 º X, XU1 º 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)UC º ( )UC.

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

Примеры.

1. Докажем 1-й из законов поглощения XU(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.

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

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

Ud( ) = U( ).

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

10. k = 0. В этом случае U = Xi , следовательно, на данный момент = Xi º º OU( ).

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

3 0. Продемонстрируем, что она верна при k = m + 1.

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

Вероятны следующие случаи

а) U=O U1;

б) U= U1UU2;

в) U= U1UU2.

Случай а) эквивалентен условию 10 и при нем теорема верна. В случаях б) и в) заменим в каждой из Ui конъюнкцию на дизъюнкцию и напротив. По определению двойственности будем иметь, соответственно, б): Ud= U UU и в): Ud= U UU .

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

Ud = U UU = (OU1( )) U (OU2( )) º

º O (U1( ) U U2( )) = O U( ).

При в) выкладки подобны. Теорема доказана.

Следствие. В случае если U – ТИ-формула, то Ud – ТЛ-формула.

Теорема 2.7. В случае если U º V, то Ud º Vd.

Подтверждение.В случае если U º V, то (OU) º (OV). Значит, в силу теоремы 2.6, Ud(Х1, …, Хn) = OU( ) и Vd(Х1, …, Хn) = OV( ).

Из этого: Ud = (OU( )) º (OV( )) = OVd. В силу транзитивности эквиваленции, возьмём Ud º Vd , что и требовалось доказать.

Лекция 18: Эквивалентность формул


Также читать:

Понравилась статья? Поделиться с друзьями: