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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Метод Петрика — метод для получения всех минимальных ДНФ из таблицы простых импликант. Предложен в 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 года.