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

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

X	Y	Z	F
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Н арисуем карту Карно, соответ­ству­ющую приве­ден­ной в качестве примера таблице истинности.

Карта Карно представляет собой квадрат или поло­вин­­ку квадрата. Количество клеток в карте равно коли­чес­тву значений функции (в данном случае – 8).

Пронумеруем столбцы таблицы комбинациями зна­че­ний X и Y, а строки – зна­чениями Z. Начинать можно с любой комбинации, допустим с 00.

Обратите внимание, что при переходе из второго столбца в третий, из­ме­ня­ет­ся только значение X, поэтому номер изменяется от 01 к 11.

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

Правило записи функции по карте Карно по единицам

Для каждой прямоугольной группы единиц размером 2ⁿ записать про­из­ве­де­ние тех переменных, значение которых не изменяется при переходе из клеточки в клеточку в группе. Полученные произведения сложить.

Размер каждой группы должен быть максимально большим. Если объединя­ют­ся две единички, то одна переменная сокращается, если 4 единички, то 2 пе­ре­менные сокращаются и т.д., т.е. чем больше группы единиц, тем меньше функ­ция.

Любая единичка может входить в любое количество групп.

П ервой выделенной группе соответствует произведение YZ ( X имеет разные значения для разных клеточек в группе, поэтому X в это произведение не входит).

Второй группе (вертикальной) соответствует произведение XY (Z изменяется при переходе со строки на строку, поэтому Z в это произведение не входит).

Аналогично, третьей группе соответствует поизведение XZ.

Получаем функцию:

Д ля большей наглядности, столбцы и стро­ки, соответствующие единичным зна­че­ни­ям аргументов, подчеркивают. Соот­вет­ствен­но записывают для каждой груп­пы единиц произведение тех переменных, ко­торые подчеркивают всю группу, например на рисунке двум выделенным единицам со­от­вет­ствует произведение YZ.

Таблице истинности, которую мы использовали в качестве примера, соот­вет­ству­ет функция . Попробуем упростить эту функцию аналитически, для этого сгруппируем произведения так, чтобы при вынесении общей части за скобки в скобках оставалась только одна переменная и ее отрицание ( . При этом произведение XYZ необходимо использовать трижды. В алгебре логики это возможно, поскольку A&A = A.

Мы получаем тот же ответ, причем как аналитически мы трижды использо­ва­ли произведение XYZ, так и в карте Карно мы трижды использовали единич­ку, со­ответствующую набору 111. Таким образом карта Карно является графичес­ким отображением возможности минимизации функции, что делает этот процесс го­раз­до более наглядным.

С оседними являются не только клетки, расположенные рядом, но и клетки на грани­цах карты Карно.

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

	A	B	C	D	F
0	0	0	0	0	1
1	0	0	0	1	1
2	0	0	1	0	0
3	0	0	1	1	1
4	0	1	0	0	0
5	0	1	0	1	1
6	0	1	1	0	1
7	0	1	1	1	1
8	1	0	0	0	1
9	1	0	0	1	1
10	1	0	1	0	0
11	1	0	1	1	1
12	1	1	0	0	0
13	1	1	0	1	1
14	1	1	1	0	0
15	1	1	1	1	1

Карта Карно для функции от 4 переменных

Пусть имеется таблица истинности, приведенная на рисунке.

CD\AB	00	01	11	10
00	1	0	0	1
01	1	1	1	1
11	1	1	1	1
10	0	1	0	0

Карта Карно для функции от 4 переменных дол­ж­на состоять из 16 клеточек и представляет собой квадрат.

Единичные значения образуют 3 группы: из 2 единиц, из 4 единиц (на границах) и из 8 единиц.

Когда объединяют 2 единички, одна переменная сокращается ( в данном слу­чае D).

Когда объединяют 4 единички, две переменные сокращается ( в данном слу­чае A и D).

Когда объединяют 8 единичек, три переменные сокращаются ( в данном слу­чае A, B и C).

В результате мы получаем функцию:

				A
	C\AB	00	01	11	10
	0	0	0	1	0
C	1	0	0	1	0
			B

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

Например, составим карту Карно для функции:

Конъюнкции AB соответствует группа, пока­зан­ная на рисунке (клеточки, в которых A и B равны 1).

				A
	C\AB	00	01	11	10
	0	0	0	0	0
C	1	1	1	0	0
			B

Конъюнкции соответствует группа, пока­зан­­ная на рисунке (клеточки, в которых A равно 0 и С равно 1).

				A
	C\AB	00	01	11	10
	0	0	0	0	0
C	1	0	1	1	0
			B

Конъюнкции BC соответствует группа, пока­зан­ная на рисунке (клеточки, в которых B и C равны 1).

				A
	C\AB	00	01	11	10
	0	0	0	1	0
C	1	1	1	1	0
			B

В конечном итоге мы получим таблицу, пока­занную на рисунке.

Объединив единички в 2 группы (чем меньше количество групп, тем лучше), получим минималь­ный вид функции:

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

Пример:

Каждому произведению соответствуют следующие группы единиц:

			a
c			1	1
			1	1

			a
	1	1
	1	1
C

			a
d			1	1
			1	1

ac ad

	1			1
	1			1

	1	1
	1	1

	1			1
	1			1

Окончательный вид таблицы.

			a
	1	1		1
	1	1	1	1	d
c			1	1
	1	1	1	1
		b

Минимальный вид функции: