Графические методы минимизации: Диаграммы Вейча
" Метод позволяет быстро получать минимальные ДНФ булевой функции f небольшого числа переменных. В основе метода лежит задание булевых функций диаграммами некоторого специального вида, получившими название диаграмм Вейча. Для булевой функции двух переменных диаграмма Вейча имеет вид (табл. 4.4.1). Каждая клетка диаграммы соответствует набору переменных булевой функции в ее таблице истинности. В (табл. 4.4.1) это соответствие показано, В клетке диаграммы Вейча ставится единица, если булева функция принимает единичное значение на соответствующем наборе. Нулевые значения булевой функции в диаграмме Вейча не ставятся. Для булевой функции трех переменных диаграмма Вейча имеет следующий вид (табл. 4.4.2). Добавление к ней еще такой же таблицы дает диаграмму для функции 4-х переменных (табл. 4.4.3). Таким же образом, т. е. приписыванием еще одной диаграммы 3-х переменных к только что рассмотренной, можно получить диаграмму для функции 5-ти переменных и т. д., однако диаграммы для функций с числом переменных больше 4-х используются редко. Для приведенных диаграмм характерно следующее:
Соседними наборами называются наборы, отличающиеся одной компонентой. Напомним, что конституенты, соответствующие таким наборам, склеиваются (см. метод Квайна- Мак-Класки). Например, для функции, заданной табл. 9.22, конституенты, соответствующие паре единиц в левой части таблицы, склеиваются и порождают элементарное произведение из 2-х букв:
х1х2/х3 v x1x2x 3 = x1x2
/х1х2/х3 v /x1/x2/x 3 = /x1/x3
m = n - log2M
Пример. Булева функция f имеет следующую СДНФ: f=х1х2х3 v х1/х2х3 v /х1/х2/х3 v /х1/х2/х3 v х1х2/х3.
Следовательно, минимальная ДНФ функции имеет вид: f = х1х2 v /х1/х2 v х1х3.
f1=х1х2х3 v /х1х4.
f2=х1х2х4 v х2х3/х4 v х1х3 v /х2х3х4 v х1х2х3x4.
f3=х3/х4 v /х3х4.
f4=/х3х4 v /х1х4 v х1х3/х4. f5=х3 v х4. f6=х3х4 v /х3/х4 v х1х2х3.
Популярное: Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы... Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы... Как построить свою речь (словесное оформление):
При подготовке публичного выступления перед оратором возникает вопрос, как лучше словесно оформить свою... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (2684)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |