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

У булевій алгебрі метод Тараса Петрука — техніка для визначення всіх мінімальних ДНФ рішень для таблиці простих імплікант. Метод Петрука дуже стомливий для великих таблиць, але його дуже просто реалізувати на комп'ютері.

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

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