6. Карты Карно

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

Имеется возможность обойти при синтезе этап получения ДСНФ (КСНФ) и часть этапа минимизации, если сразу записать сокращенные ДНФ (КНФ) по так называемым картам Карно.

Карты Карно — это другое графическое представление таблиц истинности. Структура таких карт для функции двух, трех и четырех переменных имеет вид:

Рисунок 6.1

Каждая клетка такой таблицы содержит значение логической функции x при фиксированном значении всех ее аргументов a₃, a₂, a₁, a₀ т.е. Изображает одну из строчек таблицы истинности. Соответствующий аргумент считается истинным для данной клетки, если эта клетка входит в строки или столбцы, помеченные сбоку или снизу символом этого аргумента, в противном случае аргумент для данной клетки считается ложным. Сокращенную ДНФ записывают по прямоугольным группам смежных клеток карты содержащих единицу. Допустимое число клеток в группе равно 2ⁿ, n=1,2,3,…

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

Запишем, для примера, ДНФ в последующей карте Карно:

Рисунок 6.2

Сокращенная ДНФ для данного случая имеет вид:

При выделении прямоугольных групп клеток следует иметь в виду, что:

1. выделение групп часто неоднозначно, а, следовательно, неоднозначно и решение задачи синтеза;

2. группы должны быть как можно больше, а число групп как можно меньше;

3. группы могут пересекаться, т.е. иметь общие клетки

4. с точки зрения формирования прямоугольных групп, карты трех и четырех переменных следует считать трехмерными. Карму функции с тремя переменными следует рассматривать как цилиндр со склеенными правым и левым краями. Поэтому на плоском рисунке карты прямоугольные группы смежных клеток могут оказаться разорванными. Например:

Рисунок 6.3

В прямоугольной группе смежных клеток на нашем рисунке сокращенной ДНФ соответствует слагаемое.

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

Рисунок 6.4

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

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