Карты Карно для переменных.

В 1953 Морис Карно опубликовал статью о разработанной им системе графического представления и упрощения булевых выражений.

При относительно небольшом числе переменных весьма удобным и наглядным является графическое представление логических функций в виде так называемых карт Карно или карт минтермов (рис.31).

                                  Рис.31.Карты Карно для функций К=2,3 и 4 переменных

 

Карта Карно содержит q=2^K клеток, причём каждой клетке соответствует один из q минтермов. Если требуется представить на карте Карно логическую функцию, заданную в виде СДНФ, то в клетках карты соответствующих минтермам. входящих в СДНФ. ставится “1”. Остальные клетки остаются незаполненными или заполняются "О".

 

Например:

 

а) X=A̅B̅vA̅B

б) X=A̅B̅C̅vA̅BCvAB̅C̅vAB̅C

в) A̅B̅C̅D̅vA̅B̅C̅DvABCDvAB̅CD̅

Каждой клетке карты поставлен также в соответствие один из наборов логических переменных, который определяется номером столбца и строки на пересечении которых расположена клетка. Например, на рис. В, на пересечении строки с номером АВ=11 и CD=11 расположена клетка, соответствующая набору переменных ABCD=1111.

 

2.22. Минимизация переключательных функций с помощью карт Карно.

 

Для минимизации переключательных функций с небольшим числом переменных (К=2,3,4 и 5) наиболее простым и наглядным является графический метод, использующий карты Карно.

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

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

Правила минимизации путём объединения на картах Карно следующие:

1. Объединяются две соседние клетки в столбце или ряду, четыре соседние клетки:

2. Объединяются клетки или пары клеток, крайние в столбцах или рядах:

3. Объединяются полные столбцы или ряды, пары рядом расположенных столбцов или рядов, а также крайние столбцы или ряды на карте.

4. Одна и та же клетка карты Карно может входить в несколько групп.

                      Рис.32. Пример объединения соседних клеток на картах Карно

 

Рассмотрим примеры применения карт Карно.

Предположим, что надо упростить следующее булево выражение:

X = A̅BvAB̅vAB

Разместим единицы во всех квадратах, которым соответствуют произведения в исходном булевом выражении.

Теперь необходимо объединить соседние единицы в один контур. Построение контуров продолжается до тех пор, пока все единицы не окажутся внутри контуров.

Каждый контур представляет собой новый член упрощённого булева выражения.

Получили два контра, что означает, что новое, упрощённое выражение будет состоять только из двух переменных.

Если взять нижний контур, то А встречается в комбинации с В и В-инверсное. которые в соответствии с правилами булевой алгебры дополняют друг друга и их можно опустить. Тогда остаётся только А. Аналогично этому в вертикальном контуре содержится А и А- инверсное, которые можно опустить, оставив только В. Тогда упрощённое выражение будет иметь вид: X=AvB

Рассмотрим исходное булево выражение:

X=AB̅C̅vA̅B̅C̅vA̅B̅CvABC̅

Составим карту Карно и упростим булево выражение:

Упрощённое булево выражение имеет вид:     

X = A̅B̅vAC̅

Рассмотрим булево выражение:

X=AB̅C̅D̅vA̅BC̅DvA̅B̅CDvA̅BCDvAB̅C̅D

Составим карту Карно и упростим исходное булево выражение:

Упрощённое булево выражение имеет вид:

X=A̅B̅vAC̅