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

Зменшити таблицю простих імплікант шляхом виключення рядків основних простих імплікантів (ядер) і відповідних стовпців. Помітити рядки зменшеної таблиці простих імплікант , , , і т.д.. Сформувати логічну функцію яка приймає значення 1 коли всі стовпці покриті. P є КНФ де кожна диз'юнкція має таку форму , де кожна представляє рядок, що покриває стовпець . Зменшити до мінімальної ДНФ множенням і застосуванням . Кожний терм в результаті представляє розв'язок, набір рядків, які покривають всі мінтерми в таблиці. Для визначення мінімального розв'язку спочатку знаходяться ті терми, які містять мінімальну кількість простих імплікант. Далі, для кожного терма знайденого на попередньому кроці, підраховуються кількість літералів в кожній основній імліканті і знаходять загальну кількість літералів. Обирають терм або терми, що утворені мінімальною кількістю літералів, і записують відповідні диз'юнкції основних імплікант.

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

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

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

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

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

Примітки