Элементы анализа и синтеза логических структур
На рис. 3.1, а приведено функциональное обозначение цифрового устройства с тремя входами и одним выходом. Каждый из входных сигналов А, В и С может принимать лишь два значения: 1 и 0. Выходной сигнал F, который можно рассматривать как логическую функцию входных переменных А, В, С, на каждом их наборе может быть равен 1 или 0.
В простейшем случае функция F(A,B,C) может быть задана словесным описанием. Например, функция F равна 1, если все три ее переменные или любая пара из них равны 1, в противном случае F = 0.
Любая логическая функция может быть задана в виде таблицы истинности. На рис. 3.1, б представлена таблица истинности для функции трех переменных, описанной выше словесно. Она определена на восьми наборах, которые располагаются в порядке нарастания десятичного эквивалента N их двоичного кода. В правом столбце указаны значения логической функции F на каждом наборе. Задание логической функции таблицей истинности не всегда удобно, так как при большом числе переменных она становится слишком громоздкой. В этом смысле наиболее привлекателен аналитический способ задания функций в виде так называемых структурных формул, показывающих, какие логические операции необходимо выполнить над входящими в них переменными, чтобы получить значения данной функции. По таблице истинности можно составить выражение для логической функции в СДНФ (совершенной дизъюнктивной нормальной форме), т.е. в виде суммы логических произведений, соответствующих единичным наборам функции:
 |
(3.2)
Выражение (3.2) записано с использованием операций логического сложения (дизъюнкции), логического умножения (конъюнкции) и логического отрицания (инверсии), которые выполняют простейшие логические элементы ИЛИ, И и НЕ соответственно. Для каждого единичного набора составляется логическое произведение входных переменных, в которое переменная входит с инверсией при нулевом ее значении на данном наборе. Эти логические произведения объединяются затем знаком логического сложения.
На рис. 3.2 представлены таблицы истинности и условные графические обозначения двухвходовых логических элементов. Кроме указанных выше, на практике широко используются элементы И-НЕ, ИЛИ-НЕ, Исключающее ИЛИ. Логическая функция последнего (функция «неравнозначность» или сумма по модулю два) в СДНФ записывается в виде 
Соотношения, вытекающие из принципа работы простейших логических элементов (аксиомы алгебры Буля):
Х+1=1; Х·1=Х; Х Å 1=
;
X+0= Х; X·0=0 X Å 0 =Х;
X+X=Х; X·X=Х; X Å X=0;
X+=1; X· =0; X Å =1.
Для преобразования аналитических выражений логических функций (например, с целью их упрощения) используются следующие законы булевой
алгебры (по имени английского ученого середины 19 века Дж. Буля, разработавшего математический аппарат алгебры логики):
1) переместительный А+В = В+А, АВ = ВА;
2) сочетательный (А+В)+С = А+(В+С), (АВ) С = А(ВС);
3) распределительный А(В+С) = АВ+АС;
4) двойственности 
5) двойного отрицания 
Записанная ранее в СДНФ логическая функция трех переменных (3.2) может быть представлена в виде (ей соответствует схема устройства на рис. 3.1, в)
.
Набор логических элементов И, ИЛИ, НЕ называют основным базисом или основной функционально полной системой элементов. Последнее означает, что с помощью этих элементов можно реализовать устройство, осуществляющее сколь угодно сложную логическую операцию. Каждый из элементов И-НЕ и ИЛИ-НЕ также обладает функциональной полнотой. Например, любую логическую функцию путем эквивалентных преобразований с помощью законов булевой алгебры можно привести к базису И-НЕ (логический элемент НЕ легко получается из элемента И-НЕ путем объединения его входов).
Логические функции можно отобразить на диаграммах Венна (рис.3.3). Пусть левый круг соответствует области прямых значений переменной А, правый – области прямых значений переменной В. Тогда область, образующаяся при пересечении кругов, соответствует логическому произведению АВ. Область, образующаяся при наложении кругов, соответствует логической сумме А + В. Часть круга А, куда не входит В, соответствует логическому произведению 
. Операции неравнозначности соответствует область, занимаемая двумя сегментами: и 
.