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

Метод Петрика — метод для фильтрации воды из таблицы простых импликант. Предложен в 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 года.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.