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

Алгоритм

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

Пример

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

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

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

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

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

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

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

${\displaystyle =(K+LM)(N+LQ)(P+MQ)}$

${\displaystyle =(KN+KLQ+LMN+LMQ)(P+MQ)}$

${\displaystyle =KNP+KLPQ+LMNP+LMPQ+KMNQ+KLMQ+LMNQ+LMQ}$

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

${\displaystyle =KNP+KLPQ+LMNP+LMQ+KMNQ}$

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

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

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

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

Примечания

Для улучшения этой статьи желательно : Оформить статью по правилам . Найти и оформить в виде сносок ссылки на независимые авторитетные источники , подтверждающие написанное . После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.