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

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

Алгоритм

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}$

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

Примечания

Эта страница в последний раз была отредактирована 7 июля 2022 в 21:59.