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

 

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

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

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

_{000 001 011 010 000}

^{100 101 111 100 100}

Исходя из развертки куба, строится таблица:

М₁ М₂М_{3 00 01} М_{3 11 10}

1

М₁

М₂

 

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

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

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

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

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

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

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

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

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

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

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

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

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

f(M₁,М₂,М₃) = М₁М₃ + М₂М₃ + М_{1 2 3}

Пример:

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

f(M₁,М₂,М₃)= _{1 2 3} + М_{1 2 3} + _{1 2} М₃ + М_{1 2} М₃ + М₁М₂М₃ +

+ ₁М_{2 3} + М₁М_{2 3}

 

_{00 01} М_{3 11 10}

1

М₁

М₂

f(M₁,М₂,М₃) = ₂ + М₁ + ₃

 

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

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

М₁М₂ М₃М_{4 00 01 11 10}

00
					М2
11
					М1

^М 3

М₄

f(M₁,М₂,М₃) = М₁М₄ + М₂М₄ + _{1 2 4}

Пример:

f(M₁,М₂,М₃,М₄) (3,4,5,7,9,11,12,13 конституенты)

М₁М₂ М₃М_{4 00 01 11 10}

 

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

11- 1011 12 - 1100 13 - 1101

f(M₁,М₂,М₃,М₄)= М_{2 3}+ ₁М₃М₄ +М_{1 2}М₄

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

М₄ М₅

М₁М₂ М₃М₄М_{5 001} М_{3 011 010 110 111 101 100}

01
М2 11
М1 10

 

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

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

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

f(М₁,М₂,М₃,М₄,М₅) = М_{2 3} М₅ + М_{1 3} М₄ М₅ + М_{1 2} М₃М_{4 5}

f(М₁,М₂,М₃,М₄,М₅) = ₁ М_{2 3 4}М₅ + ₁ М_{2 3} М₄ М₅ +

+ М₁М_{2 3 4} М₅ + М₁ М_{2 3} М₄ М₅ + М_{1 2 3 4} М₅ +

+ М_{1 2 3} М₄ М₅ + ₁ М_{2 3} М_{4 5} + М₁ М_{2 3} М_{4 5} +

+ ₁М₂М₃ М_{4 5} + М₁ М₂М₃ М_{4 5} + М_{1 2}М₃ М₄ М₅ +

+ М_{1 2}М_{3 4} М₅

М₁М₂ М₃М₄М_{5 001 011 010 110 111 101 100}

 

f(М₁,М₂,М₃,М₄,М₅) = М_{2 3} М₅ + М₂ М_{4 5} + М_{1 2} М₅

 

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

 

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

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

 

Недостатки:

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

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

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

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