Основные равносильности АВ

1 77X@X

2 XÙX@X, XÚX@X

3 XÙY@ YÙX, XÚY@ YÚX

4 (XÙY)ÙZ @XÙ(YÙZ), (XÚY)ÚZ @XÚ (YÚZ)

5 XÙ(YÚZ) @ (XÙY)Ú(XÙZ), XÚ(YÙZ) @ (XÚY)Ù(XÚZ)

6 XÙ(YÚX) @ X, XÚ(YÙX) @ X

7 7(XÙY) @7XÚ7Y, 7(XÚY) @ 7XÙ7Y

8 XÚ7X@1, XÙ7X@0

9 XÚ1@1, XÚ0@X, XÙ1@X, XÙ0@0

10 X®Y@ 7XÚY

11 X«Y@ (X®Y)Ù(Y®X)

 

Доказательство: 1) с помощью таблиц, 2) рассуждениями.

 

Л. (о замене)

Переход от формулы F к логически равносильной ей формуле называется

равносильным преобразованием формулы F

 

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

 

Отношение равносильности на множестве формул АВ является примером отношения эквивалентности. Класс эквивалентности, порожденный некоторой формулой F, состоит из равносильных ей формул. Внутри класса формулы неотличимы с точки зрения принимаемых ими логических значений.


ОК АВ 6

 

Дизъюнкт Конъюнктивная нормальная форма (КНФ)

Конъюнкт Дизъюнктивная нормальная форма (ДНФ)

 

Т. Для всякой формулы АВ существует ее представление в виде ДНФ (КНФ).

 

Совершенный дизъюнкт от n переменных Совершенная КНФ (СКНФ)

Совершенный конъюнкт от n переменных Совершенная ДНФ (СДНФ)

 

Пусть формула F(X1, X2, …, Xn) задана таблицей истинности. Рассмотрим

 

(1) (F(0, 0, …, 0)Ù7X1Ù7X2Ù...Ù7Xn) Ú (F(0, 0, …, 1)Ù7X1Ù7X2Ù...ÙXn) Ú...Ú

Ú (F(1, 1, …, 0)ÙX1ÙX2Ù...Ù7Xn) Ú (F(1, 1, …, 1)ÙX1ÙX2Ù...ÙXn)

 

(2) (F(0, 0, …, 0)ÚX1ÚX2Ú...ÚXn) Ù (F(0, 0, …, 1)ÚX1ÚX2Ú...Ú7Xn) Ù...Ù

Ù (F(1, 1, …, 0)Ú7X1Ú7X2Ú...ÚXn) Ù (F(1, 1, …, 1)Ú7X1Ú7X2Ú...Ú7Xn)

 

Выражения (1) и (2) равносильны F(X1, X2, …, Xn), т.к. на каждом наборе логических значений пропозициональных переменных X1, X2, …, Xn принимают те же значения, что и F.

 

Упрощение (1) для F, не являющейся тождественно ложной, дает ее СДНФ

Упрощение (2) для F, не являющейся тождественно истинной, дает ее СКНФ

 

Т.1 (о существовании и единственности СДНФ)

Т.2 (о существовании и единственности СКНФ)

 

Правило составления СДНФ (СКНФ) по таблице истинности

Правило составления СДНФ (СКНФ)путем равносильных преобразований

 

Т. F@H Û СДНФ (СКНФ) формул F и H совпадают с точностью до порядка следования конъюнктивных (дизъюнктивных) одночленов в их составе

 

Т. F H Û все дизъюнкты СКНФ формулы H содержатся среди дизъюнктов СКНФ формулы F

 

Правило построения всех неравносильных следствийформул F1, F2, …, Fm

1) построить F1Ù F2Ù ... ÙFm;

2) найти СКНФ полученной формулы;

3) выписать все содержащиеся в СКНФ дизъюнкты и их всевозможные конъюнкции.

 


ОК АВ 7

 

Ù, Ú – двойственные операции

 

Пусть F(X1, X2, …, Xn) содержит Ù, Ú и «тесные» 7

 

F*(X1, X2, …, Xn) называется двойственнойF(X1, X2, …, Xn),

если получается из F заменой содержащихся в ней Ù на Ú и Ú на Ù

 

Л. 7F(X1, X2, …, Xn) @ F*(7X1, 7X2, …, 7Xn)

Доказательство индукцией по количеству содержащихся в формуле логических связок

 

Т. (Принцип двойственности) F@H Û F*@H*

Доказательство:

F(X1, …, Xn) @ H(X1, …, Xn) Û 7F(X1, …, Xn) @ 7H(X1, …, Xn) Û

Û F*(7X1, …, 7Xn) @ H*(7X1, …, 7Xn) Û F(X1, …, Xn) @ H(X1, …, Xn)

 

Связь значений формулы F и F*: на противоположных наборах значений переменных они принимают противоположные значения

 

X1 X2 … Xn-1 Xn F(X1, X2, …, Xn) 7F(X1, X2, …, Xn) F*(X1, X2, …, Xn)
... F(0, 0, ..., 0, 0) 7F(0, 0, ..., 0, 0) 7F(1, 1, ..., 1, 1)
... F(0, 0, ..., 0, 1) 7F(0, 0, ..., 0, 1) 7F(1, 1, ..., 1, 0)
... ... ... F(0, 0, ..., 1, 0) 7F(0, 0, ..., 1, 0) ...
... ... ... ...
... ... ... ... ... ...
... ... ... ...
... ... ... ...
... ... ... ... ... ... ... 7F(0, 0, ..., 1, 0)
... F(1, 1, ..., 1, 0) 7F(1, 1, ..., 1, 0) 7F(0, 0, ..., 0, 1)
... F(1, 1, ..., 1, 1) 7F(1, 1, ..., 1, 1) 7F(0, 0, ..., 0, 0)

 

 

Правило построения СДНФ (СКНФ) по известной СКНФ (СДНФ):

1) выписать отсутствующие в СДНФ (СКНФ) совершенные конъюнкты (дизъюнкты);

2) преобразовать каждый из них, заменив Ù (Ú) на Ú (Ù), «сняв» имеющиеся 7 при переменных и поставив отсутствующие;

3) соединить полученные выражения знаками Ù (Ú).

 


ОК АВ 8