Карты Карно

Карты Карно

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

Пусть дана булева функция f(x1, x2, …, xn), определенная на 2n наборах переменных. Наборы, отличающиеся значением только одной переменной xi, называются соседними.

Множество тех наборов, на которых f(x1, x2, …, xn) = 1, называется прообразом единицы, множество наборов, на которых f(x1, x2, …, xn) = 0 – соответственно прообразом нуля.

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

Булева функция может быть представлена на карте Карно выделением клеток, соответствующих прообразу 1. В этих клетках будем писать 1 и называть их p-клетками. Незаполненные ячейки соответствуют нулям функции. 2k соседних p-клеток, расположенных в виде прямоугольника или квадрата, образуют k-мерный p-подкуб. Он называется покрытием размерности k и соответствует произведению n–k переменных. Одна p-клетка образует 0-мерный p-подкуб (или 0-куб), две – одномерный (1-куб, покрытие размерности 1 – произведение n–1 переменной – все кроме той, которая отличается для этих наборов), четыре – двумерный, и т. п.

Для функции трех переменных карту Карно можно представить в следующем виде:

Все клетки, отмеченные скобкой xi (по строке и столбцу), представляют наборы с xi = 1, а в неотмеченных строках и столбцах клетки соответствуют наборам с  xi = 0.

В случае четырех переменных карта Карно имеет следующий  вид:

Заполним карту Карно для функции