Карты Карно

При решении задач минимизации логических функций, зависящих от небольшого числа переменных, находят широкое применение графические методы. Наиболее применимы эти методы для минимизации логических функций четырех переменных, однако при соответствующем навыке их можно применять и для функций пяти-шести переменных. При большем числе переменных эти методы теряют свое основное достоинство – наглядность и становятся неэффективными.

Наибольшее распространение получил метод минимизации с помощью карт Карно. Карта Карно – это диаграмма, в которой каждому возможному набору переменных функции поставлена в соответствие одна клетка. Клеток должно быть, как и наборов, 2 ⁿ. В каждую клетку записывается значение функции (0 или 1) для данного набора. Входные переменные располагаются по внешним сторонам карты напротив ее строк и столбцов. При этом значение каждой из входных переменных относится ко всей строке (или столбцу) и равно 1, если напротив строки (или столбца) стоит под скобкой обозначение этой переменной; для остальных строк (столбцов) значение этой переменной равно 0. Эти значения входных переменных не пишутся на карте, а подразумеваются.

Каждая клетка карты соответствует определенному набору переменных. Этот набор образует код клетки.

Каждая из входных переменных делит карту Карно на две равные части, в одной из которых значение этой переменной равно 1, а в другой 0.

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

Карта Карно для двух переменных изображена на рисунке 3.1.

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

Рисунок 3.1

Число клеток карты Карно равно числу строк таблицы соответствия, т.е. 2 ⁿ, где n – число входных переменных. Прибавление каждой новой переменной удваивает число клеток карты (n увеличивается на 1), т.е. увеличивает карту вдвое.

Чтобы составить карту Карно для функции, заданной таблицей соответствия, необходимо построить карту с числом клеток, равным числу строк таблицы; по внешним сторонам карты определенным образом расположить входные переменные. Для каждого набора (строки) таблицы отыскать соответствующий набор (клетку) карты. В эту клетку проставить значение функции для данного набора.

Для функции трех переменных, заданной таблицей соответствия (таблица 3.4), карта Карно представлена на рисунке 3.2. Если логическая функция задана аналитическим выражением (формулой), то карта Карно для нее может быть составлена в следующем порядке.

Таблица 3.4
a	b	c	f


							c
						b

				а	a

					Рисунок 3.2

По числу переменных, входящих в выражение заданной функции, строится карта Карно и располагаются переменные. Заданное аналитическое выражение функции приводится к СДНФ. В карте Карно для каждой конституенты СДНФ находится соответствующая клетка (с таким же набором переменных), в которую записывается 1, в остальные клетки карты записываются 0.

Например, пусть задана функция Функция зависит от трех переменных, значит, карта Карно должна содержать 2³ = 8 клеток. Приводим функцию к СДНФ:

Карта Карно для заданной функции представлена на рис.3.2. Функция имеет значения, равные 1, в клетках карты, соответствующих членам СДНФ.

Если функция задана в виде карты Карно, то легко можно определить ее СДНФ и СКНФ.

СДНФ логической функции определяется следующим образом:

- для каждой клетки карты, в которой функция имеет значение 1, записывается конъюнкция всех входных переменных (прямых или инверсных), соответствующих этой клетке;

- составляется дизъюнкция этих конъюнкций, которая и представляет собой СДНФ данной функции.

СДНФ логической функции представляет собой дизъюнкцию кодов единичных клеток.

СКНФ логической функции по карте Карно определяется в следующем порядке:

- для каждой клетки карты, в которой функция имеет значение 0, записывается дизъюнкция инверсий входных переменных, определяющих данную клетку;

- составляется конъюнкция этих дизъюнкций, которая и представляет собой искомую СКНФ заданной функции.

СКНФ логической функции представляет собой конъюнкцию инверсий кодов нулевых клеток.

Например, для логической функции, представленной в виде карты Карно на рис.3.2, можно сразу записать ее совершенные нормальные формы:

СДНФ: СКНФ:

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

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

Клетки карты Карно, в которых проставлены значения 1, 0 и ~ называются соответственно единичными, нулевыми и условными клетками.

Заметим, что в картах Карно переменные проставляются не произвольно, а в некотором определенном порядке, так, чтобы каждая переменная покрывала половину карты и не повторяла других переменных. При этом возможны различные способы кодирования карт (варианты проставления переменных). В зависимости от способа кодирования различают карты Вейча и карты Карно. И те и другие иногда называют картами минтермов.

Мы будем называть их независимо от кодировки картами Карно.

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

Так, для карты четырех переменных (Рисунок 3.3) очевидно, что наборы переменных для соседних клеток отличаются друг от друга значением только одной переменной (Рисунок 3.4).





	Рисунок 3.4

Такие наборы, отличающиеся значением только одной переменной, называются соседними наборами. Таким образом, соседние клетки карты Карно имеют соседние коды (наборы).

Соседними между собой являются также крайние левые клети карты с крайними правыми и крайние верхние клетки карты с крайними нижними (как если бы карты были свернуты в цилиндры по вертикали и по горизонтали). В этом легко убедится, сравнивая первые и последние выражения, записанные ранее для второго столбца и третьей строки карты (см. рисунок 3.3): и

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

На рисунке 3.5 представлена карта Карно на пять переменных. Занумеруем клетки второй строки номерами от 1 до 8 и выпишем их коды (наборы переменных). Сравнивая коды клеток, видим, что клетка 1 является соседней с клеткой 2 (по переменной e), с клеткой 8 (по переменной c) и с клеткой 4 (по переменной d). Клетка 5 является соседней с клеткой 4 (по переменной c), с клеткой 6 (по переменной e) и с клеткой 8 (по переменной d). Аналогично устанавливается соседство и других клеток.

Для инженерных целей наиболее удобно кодирование карты Карно производить не в буквенной, а в цифровой форме, т.е. значение переменных обозначать не в виде скобок за полем карты, а виде переборов 0 и 1 у каждой строки и каждого столбца. При этом при выбранной базе (порядке расположения переменных) наличию переменной (прямому значению) соответствует 1, а отсутствию переменной (инверсному значению) соответствует 0.

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

					c	1.
				d		2.
			e		e		3.
									4.
		b							5.
	a							6.
								7.
									8.
Рисунок 3.5

Карта Карно с цифровой кодировкой на четыре переменных представлена на рисунке 3.6. Клетки карты Карно в этом случае имеют цифровой код. Так, например, клетки второй строки карты (см. рисунок 3.6) имеют (слева направо) следующие коды при базе x ₁ x ₂ x ₃ x ₄: 0100, 0101, 0111, 0110. От цифрового кода легко перейти к буквенному, для этого надо при данной базе заменить единицы на прямые, а нули на инверсные значения переменных:

		x ₁ x ₂	x ₃ x ₄





		Рисунок 3.6

От цифрового двоичного кода легко перейти к десятичному (восьмеричному) его выражению, т.е. к весовому состоянию при данной базе. Так, для второй строки карты (см. рисунок 3.6) весовые состояния клеток равны 4, 5, 7, 6.

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

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