WikiSort.ru - Не сортированное

Метод Петрика — метод для получения всех минимальных ДНФ из таблицы простых импликант. Метод Петрика довольно сложно применять для больших таблиц, но очень легко реализовать программно.

Алгоритм

1. Упростить таблицу простых импликант, исключив необходимые импликанты и соответствующие им термы.
2. Обозначить строки упрощенной таблицы : ${\displaystyle P_{1},P_{2},P_{3},P_{4}}$ , и т. д.
3. Сформировать логическую функцию ${\displaystyle P}$ , которая истинна когда покрыты все столбцы. ${\displaystyle P}$ состоит из КНФ, в которой каждый конъюнкт имеет форму ${\displaystyle (P_{i0}+P_{i1}+\cdots +P_{iN})}$ , где каждая переменная ${\displaystyle P_{ij}}$ представляет собой строку, покрывающую столбец ${\displaystyle i}$ .
4. Упростить ${\displaystyle P}$ до минимальной ДНФ умножением и применением ${\displaystyle X+XY=X}$ , ${\displaystyle XX=X}$ и ${\displaystyle X+X=X}$ .
5. Каждый дизъюнкт в результате представляет решение, то есть набор строк, покрывающих все минтермы в таблице простых импликант.
6. Далее для каждого решения, найденного в шаге 5 необходимо подсчитать количество литералов в каждой простой импликанте.
7. Выбрать терм (или термы), содержащие минимальное количество литералов и записать результат.

Пример

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

${\displaystyle f(A,B,C)=\sum m(0,1,2,5,6,7)\,}$ Таблица простых импликант из метода Куайна-МакКласки:

	0	1	2	5	6	7
K (${\displaystyle {\bar {a}}{\bar {b}}}$ )	✓	✓
L (${\displaystyle {\bar {a}}{\bar {c}}}$ )	✓		✓
M (${\displaystyle {\bar {b}}c}$ )		✓		✓
N (${\displaystyle b{\bar {c}}}$ )			✓		✓
P (${\displaystyle ac}$ )				✓		✓
Q (${\displaystyle ab}$ )					✓	✓

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

${\displaystyle (K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q)}$

Используя свойство дистрибутивности, обратим выражение в ДНФ. Также будем использовать следующие эквивалентности для упрощения выражения: ${\displaystyle X+XY=X}$ , ${\displaystyle XX=X}$ и ${\displaystyle X+X=X}$ .

${\displaystyle =(K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q)}$

${\displaystyle =(K+LM)(N+LQ)(P+MQ)}$

${\displaystyle =(KN+KLQ+LMN+LMQ)(P+MQ)}$

${\displaystyle =KNP+KLPQ+LMNP+LMPQ+KMNQ+KLMQ+LMNQ+LMQ}$

Теперь снова используем ${\displaystyle X+XY=X}$ для дальнейшего упрощения:

${\displaystyle =KNP+KLPQ+LMNP+LMQ+KMNQ}$

Выберем произведениями с наименьшим количеством переменных являются ${\displaystyle KNP}$ и ${\displaystyle LMQ}$ .

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

• ${\displaystyle KNP}$ расширяется в ${\displaystyle {\bar {a}}{\bar {b}}+b{\bar {c}}+ac}$
• ${\displaystyle LMQ}$ расширяется в ${\displaystyle {\bar {a}}{\bar {c}}+{\bar {b}}c+ab}$

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

Для улучшения этой статьи желательно: Викифицировать статью. Найти и оформить в виде сносок ссылки на независимые авторитетные источники, подтверждающие написанное.

Эту статью следует сделать более понятной широкому кругу читателей. Пожалуйста, попытайтесь изложить эту статью так, чтобы она была понятна неспециалисту. Вам могут помочь советы в этом эссе. Пояснение: надо до описания алгоритма рассказать, что этот алгоритм должен делать