Основы булевой алгебры. Логические функции. Способы минимизации и декомпозиции функций.

В алгебре переключений для представления значения логического сигнала используется символическая переменная, например X. В зависимости от технологии логический сигнал может иметь одно из двух значений: низкий или высокий уровень, «включено» или «выключено» и т. д.

Аксиомы или постулаты математической системы –это набор основных утверждений, про которые мы предполагаем, что они справедливы, и из которых можно вывести все другие свойства системы. Первые две аксиомы алгебры переключений устанавливают «цифровую абстракцию», формально утверждая, что переменная X может принимать только одно из двух значений

 

 

Вторая аксиом:

 

(А2) Если Х = 0, то Х'= 1;

(А2') Если Х = 1, то Х' = 0.

 

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

 

(АЗ) 0×0=0, (АЗ')1+1=1;

(А4) 1×1=1, (А4')0+0=0;

(A5) 0×1=1×0=0, (А5')1+0=0+1=1.

 

Теоремы (theorems) алгебры переключений представляют собой заведомо верные утверждения, которые позволяют преобразовывать алгебраические выражения, чтобы упростить анализ или более эффективно осуществить синтез соответствующей схемы. Например, теорема, утверждающая, что X + 0 = X, позволяет повсюду, где в выражении встретится X + 0, заменить эту сумму на X.

Ниже перечислены все теоремы алгебры переключений, касающиеся функций одной переменной X.

 

(T1) X+О=X (T1') X×1=X,
(T2) X+1=1 (Т2') X×0=О,
(ТЗ) X+X=X (Т3') X×X=X,
(Т4) =X,
(Т5) Х+Х'=1 (Т5') X×Х'=О.

 

Теоремы алгебры переключений, относящиеся к функциям двух и трех переменных, перечислены ниже. Каждая из теорем легко доказывается полной индукцией, то есть путем нахождения функции для четырех возможных комбинаций Х и У или для восьми возможных комбинаций X,Y и Z.

В первых двух парах теорем речь идет о коммутативности и ассоциативности логического сложения и логического умножения; эти утверждения идентичны коммутативному и ассоциативному правилам для сложения и умножения целых и действительных чисел. Эти теоремы утверждают, что наличие скобок и порядок членов в логической сумме и в логическом произведении несущественны. Например, со строго алгебраической точки зрения выражение типа W×X×У×Z допускает неоднозначное толкование; его следует записывать в виде (W-(X-(У-Z))) или (((W×X)У)×Z) или (W-X)×(У×Z). Но наши теоремы говорят, что неопределенность данного выражения по форме не страшна, поскольку в любом случае мы получаем один и тот же результат.

 

(Т6) X+Y=Y+X (Т7') XY=YX,

(Т7) (X+Y)+Z=X+(Y+Z) (Т7') (XY)Z=X(Y Z),

(Т8) XY+XZ =X(Y+Z) (T8') (X+Y)(X+Z)=X+YZ,

(T9) X+XY=X (T9') X(X+Y)=X,

(TIO) ХY+XY'=X (T10')(X+Y)(X+Y')=X,

(T11) XY+X'Z+YZ=XY+X'Z (T11')(X+Y)(X'+Z)(Y+Z)=(X+Y)(X'+Z).

 

Эти рассуждения кажутся тривиальными, и это действительно так, но они очень важны, так как образуют теоретическую базу для использования логических схем с числом входов больше двух. Мы ввели знаки × и + как двучленные операторы {binary operators),то есть операторы, связывающие две переменные. Однако на практике мы используем логические схемы И и ИЛИ с тремя, четырьмя и большим числом входов. Из теорем следует, что входы логических схем можно подключать к источникам сигналов в любом порядке; эта возможность используется во многих программах разводки соединений на печатных платах и внутри специализированных ИС. Можно воспользоваться, в принципе, одним n-входовым вентилем, либо двухвходовыми вентилями в количестве (n-1)штук, хотя задержка распространения и стоимость в последнем случае будут, вероятнее всего, больше.

Логическая функция - это функция, которая устанавливает соответствие между одним или несколькими высказываниями, которые называются аргументами функции, и высказыванием которое называется значением функции. Это определение почти не отличается от определения числовой функции. Разница лишь та, что аргументом и значением числовой функции являются числа, а аргументом логической функции - высказывания (переменные).

Инверсия (отрицание) — это логическое не. Говорят, что имея суждение А, можно образовать новое суждение, которое читается как «не А» или «неверно, что А». Для обозначения отрицания суждения употребляется символ или – над переменной. Запись А читается как «не А».

Коньюкция - это логическое умножение. Обозначение: А & В (АВ, А ∧ В). Читается так “ А и В “.

Дизьюкция - это логическое сложение. Обозначение: А ∨ В, (А + В). Читается так: “ А или В ”.

Эквиваленция - это функция тождества. Она обозначается символами =, ~, или <=>. Выбираем обозначение А = В. («тогда и только тогда»). Запись А = В читается как «А эквивалентно В».

Импликация - это логическое следование. Импликация двух высказываний А и В соответствует союзу «ЕСЛИ…ТО». Она обозначается символом →. Читается как «из А следует В». Обозначение: A→B.

Минимизация функций алгебры логики (ФАЛ) – это процедура нахождения наиболее простого представления ФАЛ в виде суперпозиции функций, составляющих функционально полную систему, при одновременной оптимизации ее технической реализации по некоторым критериям в условиях ряда ограничений. Критериями оптимизации могут быть объем оборудования (количество вентилей, корпусов), габариты, вес, энергопотребление, стоимость, быстродействие, надежность. В качестве ограничений могут выступать допустимые к использованию системы элементов, число элементов в корпусе, коэффициенты объединения по входу и разветвления по выходу логических элементов, необходимость реализации системы ФАЛ, а также ряд перечисленных выше критериев оптимизации.

К настоящему времени широкое применение получили:

1. Расчетный метод (метод непосредственных преобразований).

2. Расчетно-табличный метод (метод Квайна-МакКласки).

3. Метод Петрика (развитие метода Квайна-МакКласки).

4. Табличный метод (карты Карно).

5. Метод гиперкубов.

6. Метод факторизации.

7. Метод функциональной декомпозиции и др.

Первый метод применяется при числе переменных n <= 3 и основан на использовании операций склеивания, поглощения и развертывания. Ниже он будет рассмотрен подробно. Второй и третий методы используются при n ≤16 в профессиональных разработках и ориентированы на использование САПР с применением ЭВМ. Четвертый метод является самым распространенным инженерным методом минимизации ФАЛ для n ≤6. Шестой метод не имеет каких-либо существенных достижений при решении общих задач, более простых, чем метод перебора всех формул ФАЛ даже для n = 3. Практически он используется для уменьшения сложности минимальных функций, полученных с использованием первого или четвертого методов. Он основан на использовании скобочных форм и форм с групповыми инверсиями. Седьмой метод основан на представлении ФАЛ, зависящей от n переменных, в виде суперпозиций функций, зависящих от меньшего числа переменных, для которых можно применить выше перечисленные метод.