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

Введем на огромном количестве 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подстановкой формулы В заместо неких (а именно, заместо 1-го Следование, эквивалентность и преобразование формул) вхождений подформулы А.

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

Примеры.

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.

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

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

Ud( ) = U( ).

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

10. k = 0. В данном случае U = Xi , как следует, Ud = Xi º º ØU( ).

2 0. Представим, что аксиома верна при k £ m.

3 0. Покажем, что она Следование, эквивалентность и преобразование формул верна при k = m + 1.

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

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

а) U=Ø U1;

б) U= U1ÙU2;

в) U= U1ÚU2.

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

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

Ud = U ÚU = (ØU1( )) Ú (ØU2( )) º

º Ø (U1( ) Ù U2( )) = Ø U( ).

В случае в) выкладки подобны. Аксиома подтверждена.

Следствие Следование, эквивалентность и преобразование формул. Если U – ТИ-формула, то Ud – ТЛ-формула.

Аксиома 2.7. Если U º V, то Ud º Vd.

Подтверждение.Если U º V, то (ØU) º (ØV). Означает, в силу аксиомы 2.6, Ud(Х1, …, Хn) = ØU( ) и Vd(Х1, …, Хn) = ØV( ).

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


slishkom-mnogo-sluchajnostej-8-glava.html
slisok-literaturi-697-glavnij-redaktor-zav-psihologicheskoj-redakciej-zam-zav-psihologicheskoj-redakciej-vedushij.html
slitnoe-i-defisnoe-napisanie-narechij.html