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

Карта Карно или карта (диаграмма) Вейча – графический способ минимизации функций алгебры логики. Карты Карно представляют собой определенную таблицу истинности обычно для двух, трех и четырех переменных и отличаются друг от друга способом обозначения строк и столбцов таблиц истинности. На рисунке представлены карты Вейча для двух, трех и четырех переменных соответственно.

Согласно принятой форме построения карт соседними также считаются клетки первой и последней строк, клетки первого и последнего столбцов. Число клеток карты равно числу возможных комбинаций значений переменных (термов) и в каждую клетку записывается значение логической функции, соответствующее данному набору переменных. Если какая-то из возможных комбинаций присутствует в совершенной дизъюнктивной нормальной форме (СДНФ) записи функции, то в соответствующей клетке карты Карно ставится «1».

Например, функция , заданная таблицей истинности, может быть минимизирована и с помощью карт Карно. Карта Карно для нее будет иметь вид

1

Таким образом, упрощенное выражение логической функции будет иметь вид

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

Метод карт Карно (диаграмм Вейча), по существу, упрощает нахождение склеиваемых конъюнкций в СДНФ исходной логической функции.