Метод Петрика нахождения тупиковых ДНФ

Рассмотрим табл.6.2, строки которой соответствуют простым импликантам функции f, а столбцы — конъюнкциям совершенной ДНФ (СДНФ). В каждую клетку записываем единицу, если соответствующая простая импликанта поглощает элементарную конъюнкцию и нуль — в противном случае. Такая таблица называется «импликантной таблицей».

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

Таблица 6.2

Пусть в общем случае в таблице имеется N столбцов и m строк. Поставим в соответствие простым импликантам сокращённой ДНФ переменные P₁ … P_m. Фиксируем некоторую дизъюнкцию простых импликант. Будем считать, что P_i = 1, если i-я простая импликанта входит в эту дизъюнкцию и P_i = 0, в противном случае. Запишем в виде формалы условие того, что рассматриваемая дизъюнкция является ДНФ функции. Для этого необходимо, чтобы в каждом столбце таблицы была хотя бы одна единица, т.е.

,

где — элемент матрицы (таблицы), стоящий в i-й строке и j-м столбце, .

Эту формулу можно трактовать как КНФ некоторой двоичной функции от переменных P₁ … P_m, которая принимает значение 1 только на тех наборах переменных, которые соответствуют некоторым ДНФ исходной функции, и значение 0 — на наборах, которые соответствуют наборам импликант, не являющихся ДНФ исходной функции.

Заметим, что функция монотонна, так как формула 6.2.3 не содержит переменных с отрицаниями. Поэтому согласно утверждению 6.3 для нахождения её сокращённой ДНФ достаточно раскрыть скобки в формуле 6.2.3, а затем произвести все поглощения. Наконец, остаётся заметить, что в силу указанного выше свойства этой функции, её простые импликанты и только они будут давать тупиковые ДНФ исходной функции f.

Для табл. 6.2 функция равна:

.

Отсюда P₁P₃P₅ даёт для f тупиковую форму:

,

а P₁P₂P₄P₅ даёт:

.

Л е к ц и я 7