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

(перенаправлено с «Петрик, Стэнли»)

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

Алгоритм

править
  1. Упростить таблицу простых импликант, исключив необходимые импликанты и соответствующие им термы.
  2. Обозначить строки упрощённой таблицы :  , и т. д.
  3. Сформировать логическую функцию  , которая истинна когда покрыты все столбцы.   состоит из КНФ, в которой каждый конъюнкт имеет форму  , где каждая переменная   представляет собой строку, покрывающую столбец  .
  4. Упростить   до минимальной ДНФ умножением и применением  ,   и  .
  5. Каждый дизъюнкт в результате представляет решение, то есть набор строк, покрывающих все минтермы в таблице простых импликант.
  6. Далее для каждого решения, найденного в шаге 5 необходимо подсчитать количество литералов в каждой простой импликанте.
  7. Выбрать терм (или термы), содержащие минимальное количество литералов и записать результат.

Пример

править

Есть булева функция от трёх переменных, заданная суммой минтермов:

  Таблица простых импликант из метода Куайна-МакКласки:

0 1 2 5 6 7
K ( )
L ( )
M ( )
N ( )
P ( )
Q ( )

Основываясь на пометках в таблице выше, выпишем КНФ (строки складываются, их суммы перемножаются):

 

Используя свойство дистрибутивности, обратим выражение в ДНФ. Также будем использовать следующие эквивалентности для упрощения выражения:  ,   и  .

 
 
 
 

Теперь снова используем   для дальнейшего упрощения:

 

Выберем произведениями с наименьшим количеством переменных являются   и  .

Выберем терм с наименьшим количеством литералов. В нашем случае оба произведения расширяются до шести литералов:

  •   расширяется в  
  •   расширяется в  

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

Примечания

править
  1. Биографическая справка. Архивировано 13 апреля 2017 года.