Метод карт Карно

Метод карт (таблиц) Карно является более наглядным, менее трудоёмким и надёжным способом минимизации логических функций, но его использование практически ограничено функциями 3-4 переменных, максимум – 5-6 переменных.

Карта Карно – это двумерная табличная форма представления таблицы истинности булевой функции, позволяющая в графической наглядной форме легко отыскать минимальные ДНФ логических функций. Каждой клетке таблицы сопоставляется минтерм СДНФ минимизируемой функции, причём так, что любым осям симметрии таблицы соответствуют зоны, взаимно инверсные по какой-либо переменной. Такое расположение клеток в таблице позволяет легко определить склеивающиеся термы СДНФ (отличающиеся знаком инверсии только одной переменной): они располагаются в таблице симметрично.

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

x

y

f

y

x

y

f

y

x

x

а) И б) ИЛИ

Рис. 2.8. Пример карт Карно для функций двух переменных

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

f = x y.

В карте Карно для функции ИЛИ уже три 1 и можно составить две склеивающиеся пары, при этом 1, соответствующая терму xy, используется дважды. В выражении для минимальной функции нужно записать термы для склеиваемых пар, оставляя в них все переменные, которые для этой пары не меняются, и убирая переменные, которые меняют своё значение. Для горизонтальной склейки получим x, а для вертикальной – y, в итоге получим выражение

f = x + y.

На рис. 2.9 приведены таблицы истинности двух функций трёх переменных (а) и их карты Карно (б и в). Функция f ₂ отличается от первой тем, что на трёх наборах переменных она не определена (в таблице это обозначено прочерком).

При определении минимальной ДНФ функции используются следующие правила. Все клетки, содержащие 1, объединяются в замкнутые прямоугольные области, которые называются k-кубами, где k = log₂ K, K – количество 1 в прямоугольной области. При этом каждая область должна представлять собой прямоугольник с числом клеток 2 ^k, где k = 0, 1, 2, 3, …. Для k = 1 прямоугольник называется один-куб и содержит 2¹ = 2 единицы; для k = 2 прямоугольник содержит 2² = 4 единицы и называется два-куб; при k = 3 область из 2³ = 8 единиц называется три-куб; и т. д. Единицы, которые невозможно объединить в прямоугольники, можно назвать ноль-кубами, которые содержат только одну единицу (2⁰ = 1). Как видно, при чётном k области могут иметь форму квадрата (но не обязательно), а при нечётном k – только прямоугольников.

x 1	x 2	x 3	f 1	f 2		б в
				–
				–
				–

а

Рис. 2.9. Пример карт Карно для функций трёх переменных

Эти области могут пересекаться, т. е. одни и те же клетки могут входить в разные области. Затем записывается минимальная ДНФ функции как дизъюнкция всех конъюнктивных термов, соответствующих k- кубам.

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

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

Для функции по карте Карно на рис. 2.9, б находим

,

поскольку для верхней замкнутой области переменные x ₁ и x ₂ имеют значения без инверсий, для нижней x ₁ имеет значение с инверсией, а x ₃ – без инверсии.

Неопредёленные значения в карте на рис. 2.9, в можно доопределить, заменив нулём или единицей. Для данной функции видно, что оба неопределённых значения выгоднее заменить 1. При этом образуются две области, являющиеся различными видами 2-кубов. Тогда выражение для минимальной ДНФ функции будет следующим:

.

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

Карты Карно можно рисовать разными способами (рис. 2.10).

		x 2					x 2 x 3	x 2
x 1						x 1
		x 3

а б

в

Рис. 2.10. Разные способы изображения карт Карно
для функции 3 переменных

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

x 3

x 3

x 2

x 2

x 2

x 1

x 1

x 1

x 2

x 3

x 3

x 1

x 4

x 4

а б

Рис. 2.11. Наиболее удобное изображение карт Карно
для функций 3 (а) и 4 (б) переменных

Для функций 5 и 6 переменных больше подходит способ, показанный на рис. 2.10, в.

Рис. 2.12. Изображение карты Карно для функции 5 переменных

Рис. 2.13. Изображение карты Карно для функции 6 переменных