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

Шаблон:Проще Метод Петрика — метод для получения всех минимальных ДНФ из таблицы простых импликант. Предложен в 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 ($\overline{a}\overline{b}$)	✓	✓
L ($\overline{a}\overline{c}$)	✓		✓
M ($\overline{b}c$)		✓		✓
N ($b\overline{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$ расширяется в $\overline{a}\overline{b}+b\overline{c}+ac$
• $LMQ$ расширяется в $\overline{a}\overline{c}+\overline{b}c+ab$

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