Метод Петрика
Поделись знанием:
Основываясь на пометках в таблице выше, выпишем КНФ (строки складываются, их суммы перемножаются):Используя свойство дистрибутивности, обратим выражение в ДНФ. Также будем использовать следующие эквивалентности для упрощения выражения: <math>X + XY = X</math>, <math>XX = X</math> и <math>X + X = X</math>.Теперь снова используем <math>X + XY = X</math> для дальнейшего упрощения:Выберем произведения с наименьшим количеством переменных:Выберем терм с наименьшим количеством литералов. В нашем случае оба произведения расширяются до шести литералов:Так что можно использовать и то, и другое.
– Еще, еще, – приговаривал майор.
Молодой офицер, с выражением недоумения и страдания в лице, отошел от наказываемого, оглядываясь вопросительно на проезжавшего адъютанта.
Князь Андрей, выехав в переднюю линию, поехал по фронту. Цепь наша и неприятельская стояли на левом и на правом фланге далеко друг от друга, но в средине, в том месте, где утром проезжали парламентеры, цепи сошлись так близко, что могли видеть лица друг друга и переговариваться между собой. Кроме солдат, занимавших цепь в этом месте, с той и с другой стороны стояло много любопытных, которые, посмеиваясь, разглядывали странных и чуждых для них неприятелей.
С раннего утра, несмотря на запрещение подходить к цепи, начальники не могли отбиться от любопытных. Солдаты, стоявшие в цепи, как люди, показывающие что нибудь редкое, уж не смотрели на французов, а делали свои наблюдения над приходящими и, скучая, дожидались смены. Князь Андрей остановился рассматривать французов.
– Глянь ка, глянь, – говорил один солдат товарищу, указывая на русского мушкатера солдата, который с офицером подошел к цепи и что то часто и горячо говорил с французским гренадером. – Вишь, лопочет как ловко! Аж хранцуз то за ним не поспевает. Ну ка ты, Сидоров!
– Погоди, послушай. Ишь, ловко! – отвечал Сидоров, считавшийся мастером говорить по французски.
Солдат, на которого указывали смеявшиеся, был Долохов. Князь Андрей узнал его и прислушался к его разговору. Долохов, вместе с своим ротным, пришел в цепь с левого фланга, на котором стоял их полк.
– Ну, еще, еще! – подстрекал ротный командир, нагибаясь вперед и стараясь не проронить ни одного непонятного для него слова. – Пожалуйста, почаще. Что он?
Долохов не отвечал ротному; он был вовлечен в горячий спор с французским гренадером. Они говорили, как и должно было быть, о кампании. Француз доказывал, смешивая австрийцев с русскими, что русские сдались и бежали от самого Ульма; Долохов доказывал, что русские не сдавались, а били французов.
– Здесь велят прогнать вас и прогоним, – говорил Долохов.
– Только старайтесь, чтобы вас не забрали со всеми вашими казаками, – сказал гренадер француз.
Зрители и слушатели французы засмеялись.
– Вас заставят плясать, как при Суворове вы плясали (on vous fera danser [вас заставят плясать]), – сказал Долохов.
– Qu'est ce qu'il chante? [Что он там поет?] – сказал один француз.
– De l'histoire ancienne, [Древняя история,] – сказал другой, догадавшись, что дело шло о прежних войнах. – L'Empereur va lui faire voir a votre Souvara, comme aux autres… [Император покажет вашему Сувара, как и другим…]
Метод Петрика — метод для получения всех минимальных ДНФ из таблицы простых импликант[неизвестный термин]. Метод Петрика очень утомительно применять для больших таблиц, но очень легко реализовать на компьютере.
Алгоритм
- Упростить таблицу простых импликант, исключив необходимые импликанты и соответствующие им термы.
- Обозначить строки упрощенной таблицы : <math>P_1,P_2,P_3,P_4</math>, и т. д.
- Сформировать логическую функцию <math>P</math>, которая истинна когда покрыты все столбцы. <math>P</math> состоит из КНФ, в которой каждый конъюнкт имеет форму <math>(P_{i0} + P_{i1} + \cdots + P_{iN})</math>, где каждая переменная <math>P_{ij}</math> представляет собой строку, покрывающую столбец <math>i</math>.
- Упростить <math>P</math> до минимальной ДНФ умножением и применением <math>X + XY = X</math>, <math>XX = X</math> и <math>X + X = X</math>.
- Каждый дизъюнкт в результате представляет решение, то есть набор строк, покрывающих все минтермы в таблице простых импликант.
- Далее для каждого решения, найденного в шаге 5 необходимо подсчитать количество литералов в каждой простой импликанте.
- Выбрать терм (или термы), содержащие минимальное количество литералов и записать результат.
Пример
Есть булева функция от трех переменных, заданная суммой минтермов:
<math>f(A,B,C) =\sum m(0,1,2,5,6,7)\,</math> Таблица простых импликант из метода Куайна-МакКласки: | 0 1 2 5 6 7
---------------|------------
K (0,1) a'b' | X X
L (0,2) a'c' | X X
M (1,5) b'c | X X
N (2,6) bc' | X X
P (5,7) ac | X X
Q (6,7) ab | X X (K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q) = (K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q)
= (K+LM)(N+LQ)(P+MQ)
= (KN+KLQ+LMN+LMQ)(P+MQ)
= KNP + KLPQ + LMNP + LMPQ + KMNQ + KLMQ + LMNQ + LMQ= KNP + KLPQ + LMNP + LMQ + KMNQ KNP
LMQKNP расширяется в a'b'+ bc'+ ac
LMQ расширяется в a'c'+ b'c + ab<imagemap>: неверное или отсутствующее изображение |
Для улучшения этой статьи желательно?:
|
 |
Эта статью следует сделать более понятной широкому кругу читателей. Пожалуйста, попытайтесь изложить эту статью, чтобы она была понятна неспециалисту. Вам могут помочь советы в этом эссе.
Пояснение: надо до описания алгоритма рассказать, что этот алгоритм должен делать |
Напишите отзыв о статье "Метод Петрика"
Отрывок, характеризующий Метод Петрика
И всё слышались гибкие удары и отчаянный, но притворный крик.– Еще, еще, – приговаривал майор.
Молодой офицер, с выражением недоумения и страдания в лице, отошел от наказываемого, оглядываясь вопросительно на проезжавшего адъютанта.
Князь Андрей, выехав в переднюю линию, поехал по фронту. Цепь наша и неприятельская стояли на левом и на правом фланге далеко друг от друга, но в средине, в том месте, где утром проезжали парламентеры, цепи сошлись так близко, что могли видеть лица друг друга и переговариваться между собой. Кроме солдат, занимавших цепь в этом месте, с той и с другой стороны стояло много любопытных, которые, посмеиваясь, разглядывали странных и чуждых для них неприятелей.
С раннего утра, несмотря на запрещение подходить к цепи, начальники не могли отбиться от любопытных. Солдаты, стоявшие в цепи, как люди, показывающие что нибудь редкое, уж не смотрели на французов, а делали свои наблюдения над приходящими и, скучая, дожидались смены. Князь Андрей остановился рассматривать французов.
– Глянь ка, глянь, – говорил один солдат товарищу, указывая на русского мушкатера солдата, который с офицером подошел к цепи и что то часто и горячо говорил с французским гренадером. – Вишь, лопочет как ловко! Аж хранцуз то за ним не поспевает. Ну ка ты, Сидоров!
– Погоди, послушай. Ишь, ловко! – отвечал Сидоров, считавшийся мастером говорить по французски.
Солдат, на которого указывали смеявшиеся, был Долохов. Князь Андрей узнал его и прислушался к его разговору. Долохов, вместе с своим ротным, пришел в цепь с левого фланга, на котором стоял их полк.
– Ну, еще, еще! – подстрекал ротный командир, нагибаясь вперед и стараясь не проронить ни одного непонятного для него слова. – Пожалуйста, почаще. Что он?
Долохов не отвечал ротному; он был вовлечен в горячий спор с французским гренадером. Они говорили, как и должно было быть, о кампании. Француз доказывал, смешивая австрийцев с русскими, что русские сдались и бежали от самого Ульма; Долохов доказывал, что русские не сдавались, а били французов.
– Здесь велят прогнать вас и прогоним, – говорил Долохов.
– Только старайтесь, чтобы вас не забрали со всеми вашими казаками, – сказал гренадер француз.
Зрители и слушатели французы засмеялись.
– Вас заставят плясать, как при Суворове вы плясали (on vous fera danser [вас заставят плясать]), – сказал Долохов.
– Qu'est ce qu'il chante? [Что он там поет?] – сказал один француз.
– De l'histoire ancienne, [Древняя история,] – сказал другой, догадавшись, что дело шло о прежних войнах. – L'Empereur va lui faire voir a votre Souvara, comme aux autres… [Император покажет вашему Сувара, как и другим…]
