Метод Петрика

Метод Петрика — метод для получения всех минимальных ДНФ из таблицы простых импликант. Предложен в 1956 году американским учёным Стэнли Роем Петриком (1931—2006). Метод Петрика довольно сложно применять для больших таблиц, но очень легко реализовать программно.

Алгоритм

Упростить таблицу простых импликант, исключив необходимые импликанты и соответствующие им термы.

Обозначить строки упрощённой таблицы : P 1 , P 2 , P 3 , P 4 {displaystyle P_{1},P_{2},P_{3},P_{4}} , и т. д.

Сформировать логическую функцию P {displaystyle P} , которая истинна когда покрыты все столбцы. P {displaystyle P} состоит из КНФ, в которой каждый конъюнкт имеет форму ( P i 0 + P i 1 + ⋯ + P i N ) {displaystyle (P_{i0}+P_{i1}+cdots +P_{iN})} , где каждая переменная P i j {displaystyle P_{ij}} представляет собой строку, покрывающую столбец i {displaystyle i} .

Упростить P {displaystyle P} до минимальной ДНФ умножением и применением X + X Y = X {displaystyle X+XY=X} , X X = X {displaystyle XX=X} и X + X = X {displaystyle X+X=X} .

Каждый дизъюнкт в результате представляет решение, то есть набор строк, покрывающих все минтермы в таблице простых импликант.

Далее для каждого решения, найденного в шаге 5 необходимо подсчитать количество литералов в каждой простой импликанте.

Выбрать терм (или термы), содержащие минимальное количество литералов и записать результат.

Пример

Есть булева функция от трёх переменных, заданная суммой минтермов:

f ( A , B , C ) = ∑ m ( 0 , 1 , 2 , 5 , 6 , 7 ) {displaystyle f(A,B,C)=sum m(0,1,2,5,6,7),} Таблица простых импликант из метода Куайна-МакКласки:

Основываясь на пометках в таблице выше, выпишем КНФ (строки складываются, их суммы перемножаются):

( K + L ) ( K + M ) ( L + N ) ( M + P ) ( N + Q ) ( P + Q ) {displaystyle (K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q)}

Используя свойство дистрибутивности, обратим выражение в ДНФ. Также будем использовать следующие эквивалентности для упрощения выражения: X + X Y = X {displaystyle X+XY=X} , X X = X {displaystyle XX=X} и X + X = X {displaystyle X+X=X} .

= ( K + L ) ( K + M ) ( L + N ) ( M + P ) ( N + Q ) ( P + Q ) {displaystyle =(K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q)} = ( K + L M ) ( N + L Q ) ( P + M Q ) {displaystyle =(K+LM)(N+LQ)(P+MQ)} = ( K N + K L Q + L M N + L M Q ) ( P + M Q ) {displaystyle =(KN+KLQ+LMN+LMQ)(P+MQ)} = K N P + K L P Q + L M N P + L M P Q + K M N Q + K L M Q + L M N Q + L M Q {displaystyle =KNP+KLPQ+LMNP+LMPQ+KMNQ+KLMQ+LMNQ+LMQ}

Теперь снова используем X + X Y = X {displaystyle X+XY=X} для дальнейшего упрощения:

= K N P + K L P Q + L M N P + L M Q + K M N Q {displaystyle =KNP+KLPQ+LMNP+LMQ+KMNQ}

Выберем произведениями с наименьшим количеством переменных являются K N P {displaystyle KNP} и L M Q {displaystyle LMQ} .

Выберем терм с наименьшим количеством литералов. В нашем случае оба произведения расширяются до шести литералов:

• K N P {displaystyle KNP} расширяется в a ¯ b ¯ + b c ¯ + a c {displaystyle {ar {a}}{ar {b}}+b{ar {c}}+ac}
• L M Q {displaystyle LMQ} расширяется в a ¯ c ¯ + b ¯ c + a b {displaystyle {ar {a}}{ar {c}}+{ar {b}}c+ab}

Поэтому минимальными являются оба терма.