Карты Карно. 1 страница

Построим карты Карно и выделим все компактные группы наибольшей размерности, покрывающие р-клетки.

 

 

Получаем 12 компактных групп размерности 3 и 17 компактных групп размерности 2.

Соответствующие им импликанты образуют сокращенную дизъюнктивную нормальную форму.

СкДНФ: v v v v v v v v v v v v v v v v v v v v v v

v v v v v v .

Найдем р-клетки, покрытые только одной компактной группой; импликанты, соответствующие этой компактной группе, образуют ядро функции (в смысле Квайне). Отметим цветом все р-клетки, покрытые ядром функции (белые единицы – покрытые одной компактной группой, серые клетки – покрытые). На каждом следующем шаге будем рассматривать оставшиеся непокрытыми р-клетки. Делаем упорядочивание, т.е. удаляем из рассмотрения первую компактную группу, если она покрывает те же р-клетки, что и вторая компактная группа, но вторая компактная группа покрывает больше непокрытых клеток. Снова находим р-клетки, покрытые только одной компактной группой(если таких клеток нет, то производится ветвление: выбираем какую-либо импликанту и смотрим цена какой ТДНФ будет меньше с данной импликантой или без); импликанты, соответствующие этим компактным группам, входят в псевдоядро функции. Так повторяем, пока все р-клетки не окажутся покрытыми.

 

 

 

Ядро функции: { , , }

 

Упорядочивая перебор, удаляем из рассмотрения { , , ,

, , , , , }

 

Псевдоядро: { }

Пусть импликанта не входит в ТДНФ

 

Псевдоядро: { , , }

Упорядочивая перебор, удаляем из рассмотрения { , }

Пусть импликанта не входит в ТДНФ

Псевдоядро: { , }