Алгоритм построения тупиковых и минимальных днф функции f.

1. По таблице истинности строим СДНФ функции f.

2. Строим сокращённую ДНФ функции f.

3. Занумеруем в любом порядке слагаемые сокращённой ДНФ функции f.

4. Составляем таблицу покрытий. Слагаемые СДНФ функции f пишем в первой строке, а слагаемые сокращённой ДНФ функции f вместе с номерами – в первом столбце. Если слагаемое сокращённой ДНФ функции f целиком входит в слагаемое СДНФ функции f, то на пересечении соответствующей строки и столбца пишем номер слагаемого сокращённой ДНФ функции f.

5. Составляем решеточное выражение. В каждом столбце числа соединяем знаком дизъюнкции и берём конъюнкцию этих дизъюнкций.

6. Раскрываем скобки в решеточном выражении и воспользуемся правилом поглощения.

7. Каждое слагаемое в полученном выражении соответствует тупиковой ДНФ функции f. Для восстановления тупиковой ДНФ функции f нужно взять дизъюнкции тех слагаемых, номера которых указаны в полученном выражении.

8. Тупиковые ДНФ функции f с минимальным числом переменных или их отрицаний являются минимальными ДНФ функции f.

Пример.

Построить тупиковую и минимальную ДНФ функции f из примера (*).

Решение: Совершенная дизъюнктивная нормальная форма СДНФ ,

сокр. ДНФ f = (занумеровали слагаемые).

Далее заполним таблицу покрытий:

(1)		1
(2)	2		2

Поясним, как заполняется таблица. В первой строке указаны слагаемые СДНФ функции f. В первом столбце указаны слагаемые сокращённой ДНФ функции f вместе с номерами. Если слагаемое сокращённой ДНФ функции f целиком входит в слагаемое СДНФ функции f, то на пересечении соответствующей строки и столбца пишем номер слагаемого сокращённой ДНФ функции f. Слагаемое (под номером 1) содержится в . Поэтому на соответствующем месте в таблице пишется 1. Слагаемое (под номером 2) содержится в и . Поэтому в соответствующих клетках таблицы пишем 2. Решеточное выражение равно 2&1&2. Упростим его: 1&2 = 12. Получилось одно слагаемое. Ему соответствует - тупиковая ДНФ функции f. Она содержит 5 переменных и их отрицаний. Так как получена одна тупиковая ДНФ, то она является и минимальной ДНФ функции f. В данном примере сокращённая ДНФ функции f оказалась и тупиковой, и минимальной ДНФ функции f. Но так бывает не всегда.

Минимизация конъюнктивных нормальных форм

Для построения минимальной конъюнктивной нормальной формы (МКНФ) функции f нужно построить минимальную ДНФ функции и в полученной минимальной ДНФ заменить знак & на знак , знак заменить на знак &, а над каждой переменной поставить знак отрицания. Это и будет минимальная КНФ функции f. Следует учесть, что ( - двойное отрицание).

Пример.

Построить минимальную КНФ функции f из примера (*).

Решение: Построим таблицу истинности для функции . Для этого значение 0 заменим на 1, а значение 1 заменим на 0.

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

Строим СДНФ функции :

СДНФ .

Строим СКНФ функции :

СКНФ .

Раскроем скобки в выражении для СКНФ функции . Получим сокращённую ДНФ функции :

сокр. ДНФ .

Составим таблицу покрытий.

(1)				1	1
(2)			2	2
(3)	3		3
(4)		4			4

Решеточное выражение равно

34(2 3)(1 2)(1 4) = (342 343)(1 21 14 24) = (342 34)(1 24) =

= 34(1 24) = 341 3424 = 134 234.

Выражению 134 соответствует тупиковая ДНФ функции , равная , которая содержит 6 переменных и отрицаний переменных.

Выражению 234 соответствует тупиковая ДНФ функции , равная , которая содержит 6 переменных и отрицаний переменных.

Так как обе тупиковые ДНФ функции содержат по 6 переменных или отрицаний переменных, то каждая из них является минимальной ДНФ функции . Построим по ним минимальные КНФ функции f. В формуле заменим знак & на знак , знак заменим на знак &, а над каждой переменной поставим знак отрицания. Получим форму . Это и будет минимальная КНФ функции f.

В формуле заменим знак & на знак , знак заменим на знак &, а над каждой переменной поставим знак отрицания. Получим форму . Это минимальная КНФ функции f.