Консультация № 195930
02.07.2019, 19:42
0.00 руб.
0 1 1
Уважаемые эксперты! Пожалуйста, ответьте на вопрос:
Используя метод Квайна, необходимо найти МДНФ функции f(x1,x2,x3,x4), принимающей значение 1 на наборах: 7,8,9,11,12,14.

Обсуждение

давно
Мастер-Эксперт
17387
18345
05.07.2019, 11:56
общий
это ответ
Здравствуйте, Deadmoonth!

Составим таблицу истинности для заданной функции.



При минимизации по методу Квайна предполагается, что минимизируемая функция задана в дизъюнктивной совершенной нормальной форме (ДСНФ). Сделаем это:



Будем называть конъюнкции ранга 4, входящие в ДСНФ минимизируемой функции, минитермами ранга 4.

Найдём первичные импликанты. Все минитермы данной функции сравним между собой попарно. Если минитермы и таковы, что они имеют вид и то выписываем конъюнкцию являющуюся минитермом ранга 3. Минитермы ранга 4, для которых произошло склеивание, отмечаем знаком После построения всех минитермов ранга 3 сравниваем их попрано, выписываем минитермы ранга 2 и т. д. Нахождение первичных импликант закончится, когда вновь полученные минитермы уже не склеиваются между собой. Все не отмеченные минитермы являются первичными импликантами.

Минитермы ранга 4:

Образуем минитермы ранга 3:

Полученные минитермы уже не склеиваются между собой. Простыми импликантами являются следующие минитермы:


Заданная функция может быть представлена как дизъюнкция указанных простых импликант (сокращённая ДНФ -- СДНФ). Для нахождения минимального покрытия интервалами максимального ранга необходимо теперь выполнить выбрасывание некоторого количества первичных импликант.

Расставим метки. Составим таблицу, в строках которой запишем первичные импликанты минимизируемой функции, а в столбцах -- минитермы ДСНФ. Если в некоторый минитерм ДСНФ входит какая-либо из первичных импликант, то на пересечении соответствующих строки и столбца ставим метку в виде знака



Найдём существенные импликанты. Если в каком-либо столбце составленной таблицы имеется только одна метка, то первичная импликанта, стоящая в соответствующей строке, является существенной. Без существенной импликанты не может быть получено минимальное покрытие. Поэтому из таблицы меток исключаются строки, соответствующие существенным импликантам, и столбцы минитермов, покрываемых этими существенными импликантами. В данном случае все четыре импликанты оказались существенными; поэтому искомая МДНФ суть


Литература
Поспелов Д. А. Логические методы анализа и синтеза схем. -- М.: Энергия, 1974. -- 368 с.
Об авторе:
Facta loquuntur.
Форма ответа