Карты Карно

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

Карта Карно на рис. 3.6, в соответствует логической функции F, заданной выше словесно и с помощью таблицы истинности. Булева функция четырех переменных Y (рис. 3.6, а) на четырех наборах принимает значение 1, на восьми наборах — 0, на четырех наборах — не определена (такие наборы иногда называют факультативными, они обозначены как Х).

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

Правила записи минимизированного выражения для логической функции по карте Карно:

1) выделяются блоки (замкнутые прямоугольные области, содержащие 1, 2, 4, 8 клеток), заполненные единицами;

2) блоки должны быть возможно большими, а их количество наименьшим;

3) левая и правая, а также верхняя и нижняя строки карты считаются соседними;

4) блоки могут пересекаться, т. е. одна и та же клетка может входить в несколько блоков;

5) на факультативных наборах функция может доопределяться произвольно (на тех наборах, где стоят Х), чтобы получить наиболее крупные блоки;

6) функция записывается в виде логических произведений (ЛП), описывающих выделенные блоки;

7) переменная не включается в ЛП, если блок областью ее прямых значений делится пополам;

8) переменная включается в ЛП с инверсией, если рассматриваемый блок лежит в области ее инверсных значений;

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

Логическая функция F (см. рис. 3.6)описывается совокупностью трех блоков (каждый блок включает группу из двух минтермов):

F = AB + BC + AC. (3.3)

С использованием формулы двойственности ее можно преобразовать в вид, удобный для реализации в базисе И-НЕ (рис. 3.7, а):

(3.4)

Логическая функция четырех переменных Y описывается совокупностью двух блоков (четыре угловые клетки считаются соседними):

.

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

.