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

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

Алгоритм

1. Упростить таблицу простых импликант, исключив необходимые импликанты и соответствующие им термы.
2. Обозначить строки упрощённой таблицы : $P_{1},P_{2},P_{3},P_{4}$, и т. д.
3. Сформировать логическую функцию $P$, которая истинна когда покрыты все столбцы. $P$ состоит из КНФ, в которой каждый конъюнкт имеет форму $(P_{i0}+P_{i1}+\cdots +P_{iN})$, где каждая переменная $P_{ij}$ представляет собой строку, покрывающую столбец $i$.
4. Упростить $P$ до минимальной ДНФ умножением и применением $X+XY=X$, $XX=X$ и $X+X=X$.
5. Каждый дизъюнкт в результате представляет решение, то есть набор строк, покрывающих все минтермы в таблице простых импликант.
6. Далее для каждого решения, найденного в шаге 5 необходимо подсчитать количество литералов в каждой простой импликанте.
7. Выбрать терм (или термы), содержащие минимальное количество литералов и записать результат.

Пример

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

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

	0	1	2	5	6	7
K (${\bar {a}}{\bar {b}}$)	✓	✓
L (${\bar {a}}{\bar {c}}$)	✓		✓
M (${\bar {b}}c$)		✓		✓
N ($b{\bar {c}}$)			✓		✓
P ($ac$)				✓		✓
Q ($ab$)					✓	✓

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

$(K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q)$

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

$=(K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q)$

$=(K+LM)(N+LQ)(P+MQ)$

$=(KN+KLQ+LMN+LMQ)(P+MQ)$

$=KNP+KLPQ+LMNP+LMPQ+KMNQ+KLMQ+LMNQ+LMQ$

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

$=KNP+KLPQ+LMNP+LMQ+KMNQ$

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

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

• $KNP$ расширяется в ${\bar {a}}{\bar {b}}+b{\bar {c}}+ac$
• $LMQ$ расширяется в ${\bar {a}}{\bar {c}}+{\bar {b}}c+ab$

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