Метод Петрика — метод для получения всех минимальных ДНФ из таблицы простых импликант. Предложен в 1956 году американским учёным Стэнли Роем Петриком (1931—2006). Метод Петрика довольно сложно применять для больших таблиц, но очень легко реализовать программно.
Алгоритм Упростить таблицу простых импликант, исключив необходимые импликанты и соответствующие им термы. Обозначить строки упрощённой таблицы : , и т. д. Сформировать логическую функцию , которая истинна когда покрыты все столбцы. состоит из КНФ, в которой каждый конъюнкт имеет форму , где каждая переменная представляет собой строку, покрывающую столбец . Упростить до минимальной ДНФ умножением и применением , и . Каждый дизъюнкт в результате представляет решение, то есть набор строк, покрывающих все минтермы в таблице простых импликант. Далее для каждого решения, найденного в шаге 5 необходимо подсчитать количество литералов в каждой простой импликанте. Выбрать терм (или термы), содержащие минимальное количество литералов и записать результат.
Пример Есть булева функция от трёх переменных, заданная суммой минтермов:
Таблица простых импликант из метода Куайна-МакКласки: 012567K ()✓✓L ()✓✓M ()✓✓N ()✓✓P ()✓✓Q ()✓✓ Основываясь на пометках в таблице выше, выпишем КНФ (строки складываются, их суммы перемножаются):
Используя свойство дистрибутивности, обратим выражение в ДНФ. Также будем использовать следующие эквивалентности для упрощения выражения: , и .
Теперь снова используем для дальнейшего упрощения:
Выберем произведениями с наименьшим количеством переменных являются и .
Выберем терм с наименьшим количеством литералов. В нашем случае оба произведения расширяются до шести литералов: расширяется в расширяется в Поэтому минимальными являются оба терма.
Примечания
Категория:Математическая логика