§1. Совершенная дизъюнктивная нормальная форма (сднф)

Пусть рассматривается булева функция от n переменных x₁, x₂,…, x_n. Выражение (отрицание на любых местах) называют элементарной конъюнкцией (ЭК).

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

ЭК называется правильной, если ни одна переменная в ней не повторяется, и полной, если в ней участвуют все n переменных.

Если в ДНФ все ЭК правильны и полны, то ДНФ называют совершенной (СДНФ).

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

Алгоритм преобразования формулы в СДНФ:

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

.

2. Раскроем скобки и получим ДНФ.

3. Сделаем все ЭК правильными (в последнем случае ЭК пропадает).

4. Сделаем все ЭК полными (если ЭК не содержит переменную х, то умножим ее на 1=х).

5. Вернемся к шагу 2.

Через конечное число шагов получим СДНФ. В ней могут оказаться несколько одинаковых ЭК. Из таких ЭК составляем одну, согласно тождеству

Для того, чтобы получить СДНФ с помощью таблицы истинности, необходимо:

1. Записать таблицу истинности.

2. В последнем столбце таблицы истинности выбрать 1.

3. В исходном наборе, соответствующем 1 последнего столбца таблицы, запишем 0 отрицанием переменной, а 1 самой переменной.

4. Записываем СДНФ булевой функции.

Примеры решения задач

Задача 1. Доказать, что булева функция (xy)((yz)((z)) является тождественно истиной.

Решение.

x	y	z	xy	yz			(yz)((xy)	(xy)((yz)((z))
0	0	0	1	1	1	1	1	1
0	0	1	1	0	1	0	1	1
0	1	0	0	1	1	1	1	1
0	1	1	0	1	1	0	0	1
1	0	0	1	1	1	1	1	1
1	0	1	1	0	1	0	1	1
1	1	0	1	1	0	1	1	1
1	1	1	1	1	0	1	1	1

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

Задача 2. Преобразовать в СДНФ булеву функцию, заданную формулой (ху)(z+x).

Решение. Действуем по стандартному алгоритму:

1. Добьемся, чтобы в формуле остались только дизъюнкции, конъюнкции и отрицания аргументов: (ху)(z+x)=.

2. Добьемся, чтобы конъюнкции выполнялись раньше дизъюнкций (раскроем скобки): =.

3. Делаем все элементарные конъюнкции правильными: .

4. Делаем все элементарные конъюнкции полными: =

5. Ликвидируем одинаковые элементарные конъюнкции:

Задача 3. Рассмотрим получение СДНФ с помощью таблицы истинности на предыдущем примере

х	у	z	xy	zx	(xy)( zx)
0	0	0	1	0	0
0	0	1	1	1	1
0	1	0	1	0	0
0	1	1	1	1	1
1	0	0	0	1	0
1	0	1	0	0	0
1	1	0	1	1	1
1	1	1	1	0	0

Решение. В последней колонки таблицы выбираем функции со значение 1.

По исходным наборам, с учетом алгоритма записываем СДНФ: