Минимизация функции с помощью карт карно.

Графический способ минимизации удобен для трех ,четырех переменных, а для функции пяти переменных и выше применение графического метода невозможно.

Поэтому для использования принципа этого метода для большеге количества переменных предложена модернизация.

Идея: развернуть куб на плоскости

000 001 011 010 000

       

100 101 111 100 100

минимизация функции с помощью карт карно. - student2.ru Исходя из развертки куба , строится таблица:

минимизация функции с помощью карт карно. - student2.ru М1 М2М3 00 01 М3 11 10

   
минимизация функции с помощью карт карно. - student2.ru 1    

минимизация функции с помощью карт карно. - student2.ru М1

М2

Построенная таблица – карта КАРНО.

В ней отмечены конституенты,присутствующие в функции, подобно тому, как отмеченные вершины куба объеденены в ребра и грани.

Объед. и еден. карты (интервалы).

Объединение единиц в интнрвалы в карте иначе называют склеиванием.

Этапы заполнения карты КАРНО.

1. Все конституенты , присутствующие в функции заносятся в карту с помощью единиц в соответствующие клетки.

2. Выделяют интервалы на карте по следующим принципам:

а) в один интервал объединяют только соседние единицы по вертикали или горизонтали;

б) в один интервал можно объеденить 2к единиц, где k=0,1,2,3,4,….

в) карта циклически замкнута по вертикали и горизонтали.

г) в выделенный интервал объединено максимально возможное количество единиц.

Всего на карте выделено 3 интервала, в каждый входят те минитермы в которых он полностью находится.

Запишем минимальную функцию:

f(M123) = М1М3 + М2М3 + М1 минимизация функции с помощью карт карно. - student2.ru 2 минимизация функции с помощью карт карно. - student2.ru 3

Пример:

Минимизировать функцию:

f(M123)= минимизация функции с помощью карт карно. - student2.ru 1 минимизация функции с помощью карт карно. - student2.ru 2 минимизация функции с помощью карт карно. - student2.ru 3 + М1 минимизация функции с помощью карт карно. - student2.ru 2 минимизация функции с помощью карт карно. - student2.ru 3 + минимизация функции с помощью карт карно. - student2.ru 1 минимизация функции с помощью карт карно. - student2.ru 2 М3 + М1 минимизация функции с помощью карт карно. - student2.ru 2 М3 + М1М2М3 +

+ минимизация функции с помощью карт карно. - student2.ru 1М2 минимизация функции с помощью карт карно. - student2.ru 3 + М1М2 минимизация функции с помощью карт карно. - student2.ru 3

минимизация функции с помощью карт карно. - student2.ru 00 01 М3 11 10

 
минимизация функции с помощью карт карно. - student2.ru 1

минимизация функции с помощью карт карно. - student2.ru М1

М2

f(M123) = минимизация функции с помощью карт карно. - student2.ru 2 + М1 + минимизация функции с помощью карт карно. - student2.ru 3

При правильном объединении функцию больше минимизировать невозможно.

минимизация функции с помощью карт карно. - student2.ru Карта Карно для 4-х переменных:

М1М2 М3М4 00 01 11 10

минимизация функции с помощью карт карно. - student2.ru 00      
    М2
минимизация функции с помощью карт карно. - student2.ru 11      
    М1

минимизация функции с помощью карт карно. - student2.ru минимизация функции с помощью карт карно. - student2.ru М3

М4

f(M123) = М1М4 + М2М4 + минимизация функции с помощью карт карно. - student2.ru 1 минимизация функции с помощью карт карно. - student2.ru 2 минимизация функции с помощью карт карно. - student2.ru 4

Пример:

минимизация функции с помощью карт карно. - student2.ru f(M1234 ) (3,4,5,7,9,11,12,13 конституенты)

М1М2 М3М4 00 01 11 10

       
   
     
     

3 - 0011 4 - 0100 5 - 0101 7 - 0111 9 - 1001

11- 1011 12 - 1100 13 - 1101

f(M1234 )= М2 минимизация функции с помощью карт карно. - student2.ru 3+ минимизация функции с помощью карт карно. - student2.ru 1М3М4 1 минимизация функции с помощью карт карно. - student2.ru 2М4

Карты Карно для 5-ти переменных:

минимизация функции с помощью карт карно. - student2.ru минимизация функции с помощью карт карно. - student2.ru минимизация функции с помощью карт карно. - student2.ru М4 М5

минимизация функции с помощью карт карно. - student2.ru М1М2 М3М4М5 001 М3 011 010 110 111 101 100

               
минимизация функции с помощью карт карно. - student2.ru 01            
минимизация функции с помощью карт карно. - student2.ru М2 11            
М1 10            

При выделении интервалов необходимо соблюдать дополнительные правила:

1) Все интервалы должны быть симметричны относительно исходных размеров карт;

2) Если 2 единицы находятся симметрично границы раздела они считаются соседними.

f(М12345) = М2 минимизация функции с помощью карт карно. - student2.ru 3 М5 + М1 минимизация функции с помощью карт карно. - student2.ru 3 М4 М5 + М1 минимизация функции с помощью карт карно. - student2.ru 2 М3М4 минимизация функции с помощью карт карно. - student2.ru 5

f(М12345) = минимизация функции с помощью карт карно. - student2.ru 1 М2 минимизация функции с помощью карт карно. - student2.ru 3 минимизация функции с помощью карт карно. - student2.ru 4М5 + минимизация функции с помощью карт карно. - student2.ru 1 М2 минимизация функции с помощью карт карно. - student2.ru 3 М4 М5 +

+ М1М2 минимизация функции с помощью карт карно. - student2.ru 3 минимизация функции с помощью карт карно. - student2.ru 4 М5 + М1 М2 минимизация функции с помощью карт карно. - student2.ru 3 М4 М5 + М1 минимизация функции с помощью карт карно. - student2.ru 2 минимизация функции с помощью карт карно. - student2.ru 3 минимизация функции с помощью карт карно. - student2.ru 4 М5 +

+ М1 минимизация функции с помощью карт карно. - student2.ru 2 минимизация функции с помощью карт карно. - student2.ru 3 М4 М5 + минимизация функции с помощью карт карно. - student2.ru 1 М2 минимизация функции с помощью карт карно. - student2.ru 3 М4 минимизация функции с помощью карт карно. - student2.ru 5 + М1 М2 минимизация функции с помощью карт карно. - student2.ru 3 М4 минимизация функции с помощью карт карно. - student2.ru 5 +

+ минимизация функции с помощью карт карно. - student2.ru 1М2М3 М4 минимизация функции с помощью карт карно. - student2.ru 5 + М1 М2М3 М4 минимизация функции с помощью карт карно. - student2.ru 5 + М1 минимизация функции с помощью карт карно. - student2.ru 2М3 М4 М5 +

+ М1 минимизация функции с помощью карт карно. - student2.ru 2М3 минимизация функции с помощью карт карно. - student2.ru 4 М5

минимизация функции с помощью карт карно. - student2.ru

М1М2 М3М4М5 001 011 010 110 111 101 100

               
       
       
       

f(М12345) = М2 минимизация функции с помощью карт карно. - student2.ru 3 М5 + М2 М4 минимизация функции с помощью карт карно. - student2.ru 5 + М1 минимизация функции с помощью карт карно. - student2.ru 2 М5

Аппарат работы с картами и их преимущество.

1) Простота применения .

2) Наглядность расположения интервалов.

Недостатки:

1) Сложность работы возростает намного быстрее, чем увеличивается число элементов функции.

2) Трудоемкость алгоритмизации.

Исходя из недостатков следует, что для работы с функциями большего числа переменных нужны иные методы, причем они должны быть не графическими а аналитическими.

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

Наши рекомендации