2. Основы теории логических функций

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

Запись логической функции в виде суммы произведений переменных называют дизъюнктивной нормальной формой (ДНФ):

х + у z + х у z + х у z,

а запись функции в виде произведения сумм – конъюнктивой нормальной формой (КНФ):

х (х + у) (у + z) (х + у + z).

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

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

Логическая функция наиболее наглядно и полно представляется так называемой таблицей соответствия или истинности, в которой для каждой комбинации значений переменных указывается значение функции. Таким образом, таблица истинности определяет алгоритм работы создаваемой цифровой схемы. От табличного представления функции переходят к аналитической записи ее в СДНФ или СКНФ.

П усть в качестве примера функция F задана в виде таблицы. Для комбинаций переменных 2, 7, 8 функция F истинна (т. е. F = 1), что означает для указанных комбинаций равенство единице следующих произведений: х у z = 1, х у z = 1 и х у z = 1. Комбинации переменных, при которых функция истинна, называют конституентами единицы или минтермами. Представление логической функции в виде суммы минтермов определяет ее СДНФ, т. е. в данном случае

F = х у z + х у z + х у z.

Номер комбинации	x	y	z	F
1	0	0	0	0
2	0	0	1	1
3	0	1	0	0
4	0	1	1	0
5	1	0	0	0
6	1	0	1	0
7	1	1	0	1
8	1	1	1	1

Ф ункция, определяемая таблицей истинности, может быть представлена не только ее единичными, но и нулевыми значениями. Так, на основании таблицы рассматриваемая функция ложна (F = 0 или F = 1), если истинно каждое из произведений

x у z, х у z, х у z, х у z, х у z, т. е.

F = x у z + х у z + х у z + х у z + х у z.

Воспользовавшись законом инверсии, приходим к записи функции в СКНФ:

F = (х + у + z) (х + у + z) (х + у + z) (x + у + z) (х + у + z).

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

ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ

Математическим аппаратом анализа и синтеза цифровых систем служит алгебра логики (булева алгебра), которая изучает связь между переменными (сигналами), принимающими только два («0», «1») значения. Символы «0» и «1» в алгебре логики характеризуют состояния переменных или состояния их функций, в связи с чем эти символы нельзя рассматривать как арифметические числа. Алгебра логики является алгеброй состояний, а не алгеброй чисел, и для нее характерны основные действия, отличные от принятых в обычной алгебре действий над числами.

Аксиомы, законы, тождества и теоремы алгебры логики

В алгебре логики любая переменная может иметь состояние «0» или «1». Поэтому в алгебре логики каждой двоичной переменной, например х, ставится в соответствие обратная или дополнительная к ней (инверсная) переменная, такая, что:

е сли х – 0, то х = 1, если х = 1, то х = 0.

П еременную х следует читать как НЕ х.

В алгебре логики в случае одной переменной х действуют следующие правила (аксиомы):

1) х + 0 = х, 6) х ·0 = 0,

2) х + 1 = 1, 7) х · 1 = х,

3) х + х = х, 8) х · х = х,

4 ) х + х = 1, 9) х · х =0,

5 ) (х) = х, 10) (х) = х.

Правила 1÷4 характеризуют операцию логического сложения (д и з ъ ю н к ц и и ), правила 6÷9 – операцию логического умножения (конъюнкции) и правила 5,10 – операцию инверсии. Знак логического сложения «+» читается ИЛИ (например, правило 1: «х или 0 равен х»). Знак логического умножения « · » читается И (например, «х и 0 равен 0»).

Для алгебры логики, как и для обычной алгебры, действительны следующие законы.

Переместительный закон (закон коммутативности) для логического сложения и умножения:

1) х + у = у + х,

2) х · у = у · х.

Сочетательный закон (закон ассоциативности) для логического сложения и умножения:

1) х + у + z = (х + у) + z = х + (у + z),

2) x · y · z = (x · y) · z = x · (y · z).

Распределительный закон (закон дистрибутивности логического умножения по отношению к сложению):

х (у + z) = х · у + х · z.

К основным законам алгебры логики относятся законы инверсии для логических операций сложения и умножения (теоремы де Моргана):

х + у + z = х · у · z ,

т. е. инверсия суммы переменных есть произведение их инверсий;

х · у · z = х + у + z ,

т. е. инверсия произведения переменных есть сумма их инверсий.

Справедливость соотношений для двух переменных подтверждает табл. 1.

Таблица 1

x	y	x	y	х + у	х·у	x + y	x ·y	x ·y	x + y
0	0	1	1	0	0	1	1	1	1
0	1	1	0	1	0	0	0	1	1
1	0	0	1	1	0	0	0	1	1
1	1	0	0	1	1	0	0	0	0