2.2. Нормальные формы логических функций

2.2.1. Дизъюнктивные нормальные формы (днф)

Введем обозначение

Тогда Следовательно,

.

Определение. Формула вида , где , i = 1, 2,…, n, а среди переменных могут быть совпадающие, называется элементарной конъюнкцией (ЭК).

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

Определение. ПЭК называется полной (ППЭК) относительно переменных , если она содержит все эти и только эти переменные (быть может под знаком отрицания).

Пример. ; xxxxx  элементарные конъюнкции;  правильные элементарные конъюнкции;  правильные полные ЭК относительно переменных .

Утверждение. Всякая ППЭК равна 1 на единственном наборе значений аргументов: .

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

Пусть

.

Пусть

.

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

Пример.  ДНФ.

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

Пример.  СДНФ относительно переменных .

Утверждение. Всякую функцию алгебры логики, не равную тождественно нулю, можно представить СДНФ

(1)

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

Предварим доказательство формулы (1) примером построения СДНФ.

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

Таблица 1

x	y	z	f
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	0

Выпишем двоичные наборы, на которых функция равна 1 и составим соответствующие этим наборам ППЭК.

(0,0,1): ; (1,0,1): ; (1,1,0): ;

СДНФ: .

Построенная СДНФ равна 1 в точности на наборах (0,0,1); (1,0,1); (1,1,0): на каждом из этих наборов ровно одна ППЭК, составляющая СДНФ, равна 1. На каждом из остальных 5 наборах значений аргументов все три ППЭК равны 0, поэтому и СДНФ равна 0. Итак, построенная СДНФ и данная функция имеют одну и ту же таблицу истинности – эти функции равносильны.

Перейдем к доказательству формулы (1).

СДНФ равна 1 в точности на тех же двоичных наборах, на которых равна 1 функция , так строится эта СДНФ. Поэтому у функции и функции совпадают таблицы истинности, эти функции равносильны.

Утверждение. Представление функции СДНФ единственно.

Доказательство. Рассмотрим две различные СДНФ n переменных, обозначим их СДНФ₁ и СДНФ₂. Так как СДНФ₁ ≠ СДНФ₂, то имеется хотя бы одна ППЭК , которая входит в одну из СДНФ, например, в СДНФ₁, и не входит в другую. Тогда на наборе СДНФ₁ равна 1, а СДНФ₂ равна 0, эти СДНФ не равносильны, они представляют разные функции.