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