Электронные промышленные устройства. Кузнецов Б.Ф. - 49 стр.

                                                                                               49

        Совершенной конъюнктивной нормальной формой (СКНФ) называется такая КНФ, у кото-
рой в каждую простую дизъюнкцию входят все переменные данного списка (либо сами, либо их
отрицания),          причем        в        одинаковом        порядке. Например, выражение
(x 1 _ x 2 _ x3 )(x1 _ x2 _ x№
                             3 )(№    №
                                 x1 _ x 2 _ x 3 ) является СКНФ.



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

      Для интерпретации любых логических функций широко используются карты Карно, кото-
рые можно рассматривать как упорядоченное представление подмножеств.
      Карта Карно - графический способ минимизации логическиз функций обеспечивающий
относительную простоту работы с большими выражениями.Они представляет собой операции по-
парного неполного склеивания и элементарного поглощения. Карты Карно рассматриваются как
перестроенная соответствующим образом таблица истинности функции.
         Карты Карно были изобретены в 1952 Эдвардом В. Вейч’ем и усовершенствованы в 1953 Морисом
         Карно, физиком из «Бэлл Лабс», и были призваны помочь упростить цифровые электронные схе-
         мы.

      Карта для двух аргументов содержит четыре клетки, для трех — восемь (рис. 2.4, а - в). С
увеличением числа аргументов число клеток быстро растет, для и аргументов получим 2n клеток.




                      Рис. 2.4. Карты Карно: а, б — двух; е — трех переменных

       На практике строят карты Карно не более чем для пяти-шести переменных. Множество кле-
ток позволяет отобразить все наборы аргументов. Так, в верхней строке рис. 2.2, в имеем пересе-
чение аргумента x с аргументами                в нижней - с                  . Если положить, что
                 ,a              , то все возможные наборы можно представить двоичными числа-
ми. Так, набору        соответствует число 000, набору         - 001. Часто для упрощения в клет-
ках пишут не двоичные числа, а их десятичные эквиваленты (рисунок 2.2, в).
       Задать логическую функцию нескольких аргументов — значит определить ее значение на
каждом наборе. Так, функция И принимает единичное значение на третьем наборе (рис. 2.4, а),
функция ИЛИ — на первом, втором, третьем наборах (рис. 2.4,6).
       Карты Карно - не только удобное средство для изображения наборов аргументов и задания
функций: они дают возможность минимизировать логические выражения. Наборы, располагающи-
еся в смежных клетках, описываются соседними кодовыми словами по Хеммингу: 0 и 4, 1 и 3, 7 и
5 (рис. 2.4, в). Соседними будут также числа в клетках, которые окажутся смежными после свер-
тывания карты в цилиндр (0 и 2, 4 и 6). Более просто понять принцип размещение наборов на карте
Карно, если принять, что комбинации по вертикале и горизонтали соответствуют коду Грея. Если
функция принимает значение 1 на двух соседних наборах, значит, она не зависит от одной из пере-
менных.
       Пример 2.1. Пусть функция принимает значение 1 на наборах 5 и 7 (см. рис. 2.4, в);
                . Эти наборы отличаются по переменной . Таким образом, две смежные клетки кар-
ты Карно, в которых функция принимает одно значение, можно объединить, исключив перемен-
ную, принимающую на этих наборах взаимно инверсные значения. С целью минимизации можно