Пусть имеется таблица истинности, приведенная на рисунке.
| CD\AB | ||||
Карта Карно для функции от 4 переменных должна состоять из 16 клеточек и представляет собой квадрат.
Единичные значения образуют 3 группы: из 2 единиц, из 4 единиц (на границах) и из 8 единиц.
Когда объединяют 2 единички, одна переменная сокращается ( в данном случае D).
Когда объединяют 4 единички, две переменные сокращается ( в данном случае A и D).
Когда объединяют 8 единичек, три переменные сокращаются ( в данном случае A, B и C).
В результате мы получаем функцию:
| A | |||||
| C\AB | |||||
| C | |||||
| B |
Каждой прямоугольной группе единичек размером 2n соответствует произведение тех переменных, которые не изменяются при переходе из клеточки в клеточку в группе. И наоборот, каждому произведению соответствует прямоугольная группа единиц.
Например, составим карту Карно для функции:
Конъюнкции AB соответствует группа, показанная на рисунке (клеточки, в которых A и B равны 1).
| A | |||||
| C\AB | |||||
| C | |||||
| B |
Конъюнкции соответствует группа, показанная на рисунке (клеточки, в которых A равно 0 и С равно 1).
| A | |||||
| C\AB | |||||
| C | |||||
| B |
Конъюнкции BC соответствует группа, показанная на рисунке (клеточки, в которых B и C равны 1).
| A | |||||
| C\AB | |||||
| C | |||||
| B |
В конечном итоге мы получим таблицу, показанную на рисунке.
Объединив единички в 2 группы (чем меньше количество групп, тем лучше), получим минимальный вид функции:
Минимизировать аналитический вид функции с помощью карты Карно можно, только если она представлена в виде дизъюнкции конъюнкций или в виде конъюнкции дизъюнкций. Если функция содержит отрицания над выражениями, их необходимо убрать, используя законы де Моргана.
Пример:
Каждому произведению соответствуют следующие группы единиц:
| a | ||||
| c | ||||
| a | ||||
| C | ||||
| a | ||||
| d | ||||
ac ad
Окончательный вид таблицы.
| a | |||||
| d | |||||
| c | |||||
| b |
Минимальный вид функции:
Запись функции по нулям
| X | Y | Z | F | |
Если записать по единицам функцию , получим: . Тогда:
На основе этого примера можно сформулировать правило записи функци по таблице истинности по нулям:
для каждой строки таблицы истинности, в которой функция равна 0, записать сумму всех переменных, причем если значение переменной в текущем наборе равно 1, то она записывается с отрицанием; полученные суммы перемножить.
Правило записи функции по карте Карно по нулям
Для каждой прямоугольной группы нулей размером 2n записать сумму тех переменных, значение которых не изменяется при переходе из клеточки в клеточку в группе, причем если значение переменной для данной группы равно 1, то она записывается с отрицанием. Полученные суммы перемножить. Для карты Карно, приведенной на рисунке результатом будет
