6. Карты карно

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

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

Например, для двух переменных (n=2) имеем q= 2²=4 клетки. На рисунках последовательно представлена карта Карно для двух переменных, клетам которой поставлены в соответствие алгебраическое выражение минтерма (рис.12), наборы значений переменных, при которых минтерм равен 1 (рис.13),и числовое (десятичное) представление набора переменных (рис.14).

	Х1 0	1			Х1 0	1			Х1 0	1
Х2 0	Х1Х2	Х1Х2		Х2 0	00	01		Х2 0	0	2
1	Х1Х2	Х1Х2		1	10	11		1	1	3

Рис. 12. Рис.13. Рис.14

Значение переменной обычно задается в виде

черты по периметру карты:

черта есть – переменная в пределах строки или

столбца равна 1,

черты нет – переменная равна 0.

Рис.15.

Для трех переменных имеем карту Карно из 2³=8 клеток, которым соответствуют следующие наборы переменных в двоичном и десятичном представлении. Здесь расположение переменных по битам принято Х₁Х₂Х₃.

Рис.16. Рис.17.

__ __ __ __ X1 X2 X3 X4	__ __ __ X1 X2 X3 X4	__ __ X1 X2 X3 X4	__ __ __ X1 X2 X3 X4
__ __ __ X1 X2 X3 X4	__ __ X1 X2 X3 X4	__ X1 X2 X3 X4	__ __ X1 X2 X3 X4
__ __ X1 X2 X3 X4	__ X1 X2 X3 X4	X1 X2 X3 X4	__ X1 X2 X3 X4
__ __ __ X1 X2 X3 X4	__ __ X1 X2 X3 X4	__ X1 X2 X3 X4	__ __ X1 X2 X3 X4

Для четырех переменных имеем карту Карно из 2⁴=16 клеток.

Рис.19. Рис.20.

Здесь каждой клетке карты поставлены в соответствие выражение минтерма (рис.18), двоичное (рис.19) и десятичное (рис.20) представления набора переменных при расположении переменных по битам Х₁Х₂Х₃Х₄. При изменении порядка расположения битов изменится десятичное представление.

Аналогично, при n=5 имеем 32 клетки, при n=6 - 64 клетки.

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

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

Логическая функция “И”:

Y = X₁  X₂.

Рис.21.

Логическая функция “ИЛИ”:

Y = X₁  X₂ =

= X₁  X₂  X₁  X₂  X₁  X₂.

Рис.22.

Логическая функция “Исключающее ИЛИ”:

0	1
1	0

Рис.23.

Для произвольной логической функции карта Карно представляет собой совокупность клеток, заполненных “1”, каждой из которых соответствует минтерм в СДНФ логических функций.

Например: Х₁

1
	1
			1
			1

__ __ __ __

F (X1,X2 ,X3,X4) = X₁ X₂ X₃ X₄ +

__ __ __ __ __ X₃

+X₁X₂X₃X₄ + X₁X₂X₃X₄ + X₁X₂X₃X₄ .

Рис. 24. Функция и ее карта Карно. Х₂

Клетки, содержащие 1, называются “1-клетками”, а клетки, содержащие 0, - “0-клетками”. Логические функции, имеющие определенные значения (0 или 1) при всех возможных наборах переменных, называются полностью определенными. Имеются функции, значения которых определены только для части наборов переменных. Такие логические функции называютсячастично определенными. Те наборы значений аргументов, для которых значение функции не определено, будем называтьбезразличными, на карте Карно эти клетки будем указывать знаком “х”. Этим наборам соответствуют ситуации, которые на практике никогда не реализуются. Частично определенную функцию можно доопределить, приписав безразличным значениям произвольно 0 или 1. Обычно доопределение проводят таким образом, чтобы, используя законы алгебры логики, упростить выражение.