Тупиковые и минимальные ДНФ.

Если из дизъюнкции простых импликантов функции f нельзя отбросить ни одного слагаемого, то говорят, что получена тупиковая ДНФ (ТДНФ) функции f.

Тупиковая ДНФ функции f, содержащая минимальное число переменных или их отрицаний, называется минимальной ДНФ (МДНФ) функции f.

Алгоритм построения тупиковых

И минимальных ДНФ функции f.

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

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

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

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

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

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

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

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

Пример.

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

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

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

 

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

 

(1)
(2)

 

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