Карты Карно

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

Для наглядности рассмотрим пример: пусть требуется найти логическое выражение для мажоритарной функции f_m трех переменных x, у, z, описываемой таблицей истинности, показанной в табл. 2.

Функция f_m строится по принципу голосования “два из трех”, т.е. принимает то значение, которое имеют большинство переменных.

Составим карту Карно функции f_m (табл. 3). В карте столбцам и строкам соответствуют наборы переменных (или одна из переменных), причем переменные располагаются в таком порядке, чтобы при переходе к соседнему столбцу или строке изменялось значение только одной переменной. Например, в строке xy табл. 3 значения переменных xy могут быть представлены следующими последовательностями 00, 01, 11, 10 или 00, 10, 11, 01. Внутри таблицу заполняют значениями функции, соответствующими комбинациям значений переменных.

На карте Карно отмечаем группы, состоящие из 2^k соседних клеток (2, 4, 8,…) и содержащие 1. В результате объединения (склеивания) таких ячеек в записи функции получаются более простые логические выражения. Три овала в таблице определяют логические выражения xy, xz, yz, полученные путем применения следующих операций склеивания:

Таблица 2

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

f_m = xy v xz v yz .

Таблица 3

yz x

xz yz xy

Самая короткая по числу букв ДНФ будет представлять собой минимальную дизъюнктивную нормальную форму (МДНФ).

Если объединять 0, то получим запись в конъюнктивной нормальной форме (КНФ)

f_m = (x v y)( x v z)(y v z).

Обратим внимание на то, что полученные записи функции f_m в ДНФ или КНФ являются более компактными, чем ее представления в СДНФ или СКНФ.