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

Шаблон:Без джерелУ булевій алгебрі метод Патрика — техніка для визначення всіх мінімальних ДНФ рішень для таблиці простих імплікант, яку запропонував Шаблон:Нпні (1931–2006) у 1956 році. Метод Петрика дуже стомливий для великих таблиць, але його дуже просто реалізувати на комп'ютері.

1. Зменшити таблицю простих імплікант шляхом виключення рядків основних простих імплікантів (ядер) і відповідних стовпців.
2. Помітити рядки зменшеної таблиці простих імплікант $P_1$, $P_2$, $P_3$, $P_4$ і т.д..
3. Сформувати логічну функцію $P$ яка приймає значення 1 коли всі стовпці покриті. P є КНФ де кожна диз'юнкція має таку форму $(P_{i0}+P_{i1}+$$\cdots$$+P_{iN})$, де кожна $P_{ij}$ представляє рядок, що покриває стовпець $i$.
4. Зменшити $P$ до мінімальної ДНФ множенням і застосуванням $X+XY=X$.
5. Кожний терм в результаті представляє розв'язок, набір рядків, які покривають всі мінтерми в таблиці. Для визначення мінімального розв'язку спочатку знаходяться ті терми, які містять мінімальну кількість простих імплікант.
6. Далі, для кожного терма знайденого на попередньому кроці, підраховуються кількість літералів в кожній основній імліканті і знаходять загальну кількість літералів.
7. Обирають терм або терми, що утворені мінімальною кількістю літералів, і записують відповідні диз'юнкції основних імплікант.

Приклад методу Патрика (скопійовано з http://www.mrc.uidaho.edu/mrc/people/jff/349/lect.10)

Наступну функцію ми бажаємо зменшити:

$f(A,B,C)=\sum m(0,1,2,5,6,7)$

Таблиця основних імплікантів отримана методом Куайна — Мак Класкі наступна:

                0 1 2 5 6 7
 ---------------|------------
   K (0,1) a'b' | X X 
   L (0,2) a'c' | X   X
   M (1,5) b'c  |   X   X
   N (2,6) bc'  |     X   X
   P (5,7) ac   |       X   X
   Q (6,7) ab   |         X X

Ґрунтуючись на позначках Х в попередній таблиці, будуємо КНФ згідно з третім кроком:

 (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

Обираємо терми з найменшою кількістю літералів. В нашому випадку обидва добутки розкладаються в 6 літералів кожен:

KNP    розкладається в    a'b'+ bc'+ ac
LMQ    розкладається в    a'c'+ b'c + ab

Таким чином один з них може бути використаний. Взагалі застосування методу Петрика стомлююче для великих таблиць, але легко реалізується на комп'ютері.