Минимизация методом карт Карно

Карты Карно – это графическое изображение таблиц истинности.

Пусть задана функция . Подмножество элементов , в которых , называется носителем функции f и обозначается через supp(f). Конечные пересечения подмножеств вида: называются кубиками. Кубики будут равны: , для некоторых и , таких, что . Если кубики являются максимальными, содержащимися в носителе, и попарно не пересекаются, то формула

будет давать разложение в дизъюнктивную нормальную форму, минимальное по количеству слагаемых. Карты Карно позволяют «увидеть» эти кубики. Для функций двух, трех и четырех переменных они имеют следующие структуры:

x1 x2
f(0,0) f(0,1)
f(1,0) f(1,1)

  x2 x3
x1  
f(0,0,0) f(0,0,1) f(0,1,1) f(0,1,0)
f(1,0,0) f(1,0,1) f(1,1,1) f(1,1,0)

  х3 x4
x1 x2  
f(0,0,0,0) f(0,0,0,1) f(0,0,1,1) f(0,0,1,0)
f(0,1,0,0) f(0,1,0,1) f(0,1,1,1) f(0,1,1,0)
f(1,1,0,0) f(1,1,0,1) f(1,1,1,1) f(1,1,1,0)
f(1,0,0,0) f(1,0,0,1) f(1,0,1,1) f(1,0,1,0)

Кубикам будут соответствовать отрезки и квадраты. Рассмотрим примеры кубиков и соответствующих им логических произведений:


 

 

Возможно превращение кубиков в квадраты и отрезки после отождествления противоположных сторон карты Карно, например:

 

 

Логические произведения состоят из сомножителей, значения которых не изменяются внутри кубика. Если это значение равно 1, то для переменной берется сомножитель , а если это значение равно 0 – то сомножитель .

Пример

Для булевой функции:

найти дизъюнктивную нормальную форму с наименьшим числом логических слагаемых.

Решение. Составим карту Карно:

х3 x4
x1 x2  

Получаем 2 кубика: и . Внутри первого кубика не изменяются переменные и , и равны 0. Значит, первое слагаемое равно: . Внутри второго кубика не изменяются и , откуда второе слагаемое равно: . Следовательно, искомая дизъюнктивная нормальная форма равна: .









Дата добавления: 2016-09-20; просмотров: 597;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.009 сек.