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

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

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

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

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

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

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

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

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

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

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

			A
	C\AB
C
			B

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

			A
	C\AB
C
			B

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

			A
	C\AB
C
			B

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

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

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

Пример:

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

		a
C

ac ad

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

		a
				d
c
		b

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

Запись функции по нулям

X	Y	Z	F

Если записать по единицам функцию , полу­чим: . Тогда:

На основе этого примера можно сформулировать правило записи функци по таблице истинности по ну­лям:
для каждой строки таблицы истинности, в которой функция равна 0, записать сумму всех переменных, причем если значение пере­менной в текущем наборе равно 1, то она записывается с отрицанием; полученные суммы перемножить.

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

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