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

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

Алгоритм

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

Пример

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

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

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

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

[math]\displaystyle{ (K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q) }[/math]

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

[math]\displaystyle{ =(K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q) }[/math]

[math]\displaystyle{ =(K+LM)(N+LQ)(P+MQ) }[/math]

[math]\displaystyle{ =(KN+KLQ+LMN+LMQ)(P+MQ) }[/math]

[math]\displaystyle{ =KNP+KLPQ+LMNP+LMPQ+KMNQ+KLMQ+LMNQ+LMQ }[/math]

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

[math]\displaystyle{ = KNP + KLPQ + LMNP + LMQ + KMNQ }[/math]

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

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

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

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