Карты Карно

Карта Карно – это еще один способ задания логических функций в виде таблиц. Этими картами удобно пользовать при небольшом числе переменных (до 5 – 6). Строится она по таблице истинности.

Сначала создается заготовка карты в виде матрицы (см. табл. 19 – для двух переменных, табл. 20 – для трех переменных, табл. 21 – для четырех переменных, табл. 22 –для пяти переменных).

Разметка строк и столбцов матрицы производится так, что соседние строки (столбцы) отличаются значением одной переменной. Каждый элемент матрицы имеет номер (вес), соответствующий двоичному числу, получаемому из значений переменных, которыми обозначены столбцы и строки матрицы в порядке edcba (a – младший разряд). Этот вес совпадает с номером набора в таблице истинности функции.

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

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

Карта для пяти переменных (табл. 22) состоит как бы из двух карт для четырех переменных. В ней соседние элементы определяются сложнее. Например, для элемента 13 соседними являются элементы 5, 29, 12, 15 и элемент 9, расположенный в другой половине карты симметрично относительно средней, более толстой, линии. Для элемента 18 соседними будут элементы 2, 26, 19, 22 и 16. Элементы каждой пары различаются значением одной переменной.

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

.

Таблица 23
с\ba
	0		1

В приведенной карте Карно имеется еще два контура соседних единиц. В результате минимизации для мажоритарной функции получаем

.

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

В результате получается ДНФ минимизируемой функции.

Если в карте Карно объединяются нули, то получим КНФ.

Каждый 0 в карте Карно соответствует одной дизъюнкции в СКНФ.

В контуре, объединяющем два нуля, исключается переменная, которая меняет свое значение.

для контура с нулями, выделенного прямоугольником в табл. 22, получаем:

.

Для КНФ нашей функции получаем

.

В контуре из четырех 0 исключаем две переменные, в контуре из восьми 0 исключаем три переменные и т.д.

Если в таблице все единицы, то это означает, что функция равна «1», если все нули, то функция равна «0».

с помощью карты Карно проведем минимизацию функции, рассмотренной в примере 1 предыдущего пункта

Составим карту Карно (таблица 24).

Здесь есть две возможности оптимального формирования контуров, которые показаны в таблицах 24 и 24*.

Таблица 24
с\ba
	1		1
		1

Таблица 24*
с\ba
	1		1	1
	1

По табл. 24 получаем

.

По табл. 24* получаем

Как видим, применение карт Карно оказалось значительно проще расчетного метода.