Здравствуйте, Deadmoonth!
Составим таблицу истинности для заданной функции.
При минимизации по методу Квайна предполагается, что минимизируемая функция задана в дизъюнктивной совершенной нормальной форме (ДСНФ). Сделаем это:
Будем называть конъюнкции ранга 4, входящие в ДСНФ минимизируемой функции, минитермами ранга 4.
Найдём первичные импликанты. Все минитермы данной функции сравним между собой попарно. Если минитермы
и
таковы, что они имеют вид
и
то выписываем конъюнкцию
являющуюся минитермом ранга 3. Минитермы ранга 4, для которых произошло склеивание, отмечаем знаком
После построения всех минитермов ранга 3 сравниваем их попрано, выписываем минитермы ранга 2 и т. д. Нахождение первичных импликант закончится, когда вновь полученные минитермы уже не склеиваются между собой. Все не отмеченные минитермы являются первичными импликантами.
Минитермы ранга 4:
Образуем минитермы ранга 3:
Полученные минитермы уже не склеиваются между собой. Простыми импликантами являются следующие минитермы:
Заданная функция может быть представлена как дизъюнкция указанных простых импликант (сокращённая ДНФ -- СДНФ). Для нахождения минимального покрытия интервалами максимального ранга необходимо теперь выполнить выбрасывание некоторого количества первичных импликант.
Расставим метки. Составим таблицу, в строках которой запишем первичные импликанты минимизируемой функции, а в столбцах -- минитермы ДСНФ. Если в некоторый минитерм ДСНФ входит какая-либо из первичных импликант, то на пересечении соответствующих строки и столбца ставим метку в виде знака
Найдём существенные импликанты. Если в каком-либо столбце составленной таблицы имеется только одна метка, то первичная импликанта, стоящая в соответствующей строке, является существенной. Без существенной импликанты не может быть получено минимальное покрытие. Поэтому из таблицы меток исключаются строки, соответствующие существенным импликантам, и столбцы минитермов, покрываемых этими существенными импликантами. В данном случае все четыре импликанты оказались существенными; поэтому искомая МДНФ суть
Литература
Поспелов Д. А. Логические методы анализа и синтеза схем. -- М.: Энергия, 1974. -- 368 с.
Об авторе:
Facta loquuntur.