2.8 Равносильные формулы. Основные равносильности

Определение. Формула называется тождественно истинной, или тавтологией, если эта формула принимает значение 1 при всех наборах значений переменных.

Определение. Формула называется тождественно ложной, или противоречием, если эта формула принимает значение 0 при всех наборах значений переменных.

2.9 Основные тавтологии

1.	Закон исключенного третьего
2.
3.
4.	Цепное рассуждение
5.
6.

Определение. Формулы P и Q называются равносильными (обозначается  ), если при любых значениях переменных значение формулы P совпадает со значением Q.

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

1.  2.	Коммутативность   и
3. 4.	Ассоциативность   и
5. 6.	Дистрибутивность   и
7.  8.	Идемпотентность   и
9.  10.	Законы исключенного третьего и противоречия
11. 12.	Законы де Моргана
13. 14.	Законы поглощения
15.	Правило склеивания
16.  17. 18.  19.
20.	Закон двойного отрицания
21. 22. 23. 24.
25.	Коммутативность
26.	Ассоциативность
27.	Дистрибутивность   и
28. 29. 30.

Замечание. Здесь P, Q и R —пропозициональные формулы.

2.11 Понятие двойственной функции

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

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

Теорема. (Принцип двойственности.) Пусть  ,…,  и   — булевы функции и пусть  =   сложная булева функция. Тогда

=

Следствие. Пусть P и Q —формулы. Если  , тогда  .

Принцип двойственности позволяет получать из доказанных равносильностей целый ряд новых. Кроме того, СКНФ(f)= .

2.12 Некоторые двойственные функции

1.
2.
3.
4.
5.
Замечание.  .

2.13 Элементарные канонические формы

Определение. Элементарной конъюнкцией называется конъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более 1 раза.

Определение. Элементарной дизъюнкцией называется дизъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более 1 раза.

2.14 Нормальные формы формул

Определение. Дизъюнктивной нормальной формой (Д.Н.Ф.) называется произвольная дизъюнкция элементарных конъюнкций.

Определение. Конъюнктивной нормальной формой (К.Н.Ф.) называется произвольная конъюнкция элементарных дизъюнкций.

Определение. К.Н.Ф. называется совершенной и обозначается С.К.Н.Ф., если каждая переменная входит в каждую элементарную дизъюнкцию ровно один раз с отрицанием или без.

Определение. Д.Н.Ф. называется совершенной и обозначается С.Д.Н.Ф, если каждая переменная входит в каждую элементарную конъюнкцию ровно один раз с отрицанием или без.

Пример:  – Д.Н.Ф;   – С.Д.Н.Ф.

Теорема. Любая логическая функция кроме 0 имеет единственную С.Д.Н.Ф:  .

Теорема. Любая логическая функция кроме 1 имеет единственную С.К.Н.Ф:  .

Здесь  .

Пример. Пусть функция трех переменных задана таблицей истинности:

0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	1

Записать ее С.Д.Н.Ф. и С.К.Н.Ф.

С.Д.Н.Ф.(f)=

С.К.Н.Ф.(f)=