Русская Википедия:Метод Петрика
Шаблон:Проще Метод Петрика — метод для получения всех минимальных ДНФ из таблицы простых импликант. Предложен в 1956 году американским учёным Стэнли Роем Петриком (1931—2006)[1]. Метод Петрика довольно сложно применять для больших таблиц, но очень легко реализовать программно.
Алгоритм
- Упростить таблицу простых импликант, исключив необходимые импликанты и соответствующие им термы.
- Обозначить строки упрощённой таблицы : <math>P_1,P_2,P_3,P_4</math>, и т. д.
- Сформировать логическую функцию <math>P</math>, которая истинна когда покрыты все столбцы. <math>P</math> состоит из КНФ, в которой каждый конъюнкт имеет форму <math>(P_{i0} + P_{i1} + \cdots + P_{iN})</math>, где каждая переменная <math>P_{ij}</math> представляет собой строку, покрывающую столбец <math>i</math>.
- Упростить <math>P</math> до минимальной ДНФ умножением и применением <math>X + XY = X</math>, <math>XX = X</math> и <math>X + X = X</math>.
- Каждый дизъюнкт в результате представляет решение, то есть набор строк, покрывающих все минтермы в таблице простых импликант.
- Далее для каждого решения, найденного в шаге 5 необходимо подсчитать количество литералов в каждой простой импликанте.
- Выбрать терм (или термы), содержащие минимальное количество литералов и записать результат.
Пример
Есть булева функция от трёх переменных, заданная суммой минтермов:
<math>f(A,B,C) =\sum m(0,1,2,5,6,7)\,</math> Таблица простых импликант из метода Куайна-МакКласки:
| 0 | 1 | 2 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|
| K (<math>\bar{a}\bar{b}</math>) | ✓ | ✓ | ||||
| L (<math>\bar{a}\bar{c}</math>) | ✓ | ✓ | ||||
| M (<math>\bar{b}c</math>) | ✓ | ✓ | ||||
| N (<math>b\bar{c}</math>) | ✓ | ✓ | ||||
| P (<math>ac</math>) | ✓ | ✓ | ||||
| Q (<math>ab</math>) | ✓ | ✓ |
Основываясь на пометках в таблице выше, выпишем КНФ (строки складываются, их суммы перемножаются):
<math>(K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q)</math>
Используя свойство дистрибутивности, обратим выражение в ДНФ. Также будем использовать следующие эквивалентности для упрощения выражения: <math>X + XY = X</math>, <math>XX = X</math> и <math>X + X = X</math>.
- <math>=(K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q)</math>
- <math>=(K+LM)(N+LQ)(P+MQ)</math>
- <math>=(KN+KLQ+LMN+LMQ)(P+MQ)</math>
- <math>=KNP+KLPQ+LMNP+LMPQ+KMNQ+KLMQ+LMNQ+LMQ</math>
Теперь снова используем <math>X + XY = X</math> для дальнейшего упрощения:
- <math>= KNP + KLPQ + LMNP + LMQ + KMNQ</math>
Выберем произведениями с наименьшим количеством переменных являются <math>KNP</math> и <math>LMQ</math>.
Выберем терм с наименьшим количеством литералов. В нашем случае оба произведения расширяются до шести литералов:
- <math>KNP</math> расширяется в <math>\bar{a}\bar{b}+b\bar{c}+ac</math>
- <math>LMQ</math> расширяется в <math>\bar{a}\bar{c}+\bar{b}c+ab</math>
Поэтому минимальными являются оба терма.
Примечания
