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

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(X₁, X₂, …, X_n) задана таблицей истинности. Рассмотрим

(1) (F(0, 0, …, 0)Ù7X₁Ù7X₂Ù...Ù7X_n) Ú (F(0, 0, …, 1)Ù7X₁Ù7X₂Ù...ÙX_n) Ú...Ú

Ú (F(1, 1, …, 0)ÙX₁ÙX₂Ù...Ù7X_n) Ú (F(1, 1, …, 1)ÙX₁ÙX₂Ù...ÙX_n)

(2) (F(0, 0, …, 0)ÚX₁ÚX₂Ú...ÚX_n) Ù (F(0, 0, …, 1)ÚX₁ÚX₂Ú...Ú7X_n) Ù...Ù

Ù (F(1, 1, …, 0)Ú7X₁Ú7X₂Ú...ÚX_n) Ù (F(1, 1, …, 1)Ú7X₁Ú7X₂Ú...Ú7X_n)

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

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

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

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

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

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

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

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

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

Правило построения всех неравносильных следствийформул F₁, F₂, …, F_m

1) построить F₁Ù F₂Ù ... ÙF_m;

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

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

ОК АВ 7

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

Пусть F(X₁, X₂, …, X_n) содержит Ù, Ú и «тесные» 7

F*(X₁, X₂, …, X_n) называется двойственнойF(X₁, X₂, …, X_n),

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

Л. 7F(X₁, X₂, …, X_n) @ F*(7X₁, 7X₂, …, 7X_n)

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

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

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

F(X₁, …, X_n) @ H(X₁, …, X_n) Û 7F(X₁, …, X_n) @ 7H(X₁, …, X_n) Û

Û F*(7X₁, …, 7X_n) @ H*(7X₁, …, 7X_n) Û F(X₁, …, X_n) @ H(X₁, …, X_n)

Связь значений формулы 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