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

 

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

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

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

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

(1.1)

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

Правила 1—4, 6—9 поясняются схемами (рис. 1.2 а — з) на двух ключах в соответствии с числом слагаемых (сомножителей) в соотношениях. Положению «Ключ включен» соответствует состояние «1», а положению «Ключ выключен» — состояние «0». Для логического сложения (правила 1—4) ключи в схемах соединены параллельно. Уровень высокого напряжения на выходе (F = 1) будет иметь место, если хотя бы один ключ находится в состоянии «1» (правила 2, 4; рис. 1.2 б, г). Результат суммы в правилах 1, 3 зависит от значения х(при Х =.1,F= 1, при х =0 F = 0; рис.1.2 а, в). Для логического умножения ключи соединены последовательно (рис.1.2 д — з). Уровень высокого напряжения на выходе (F = 1) будет только в том случае, если оба сомножителя равны единице (оба ключа включены). В противном случае результат умножения равен нулю (правила 6, 9; рис.1.2 д, з). Результат ум

 
 

ножения в правилах 7, 8 зависит от значения х (рис.1.2 е, ж).

 

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

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

(1.2)

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

(1.3)

 

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

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

 

Для многих случаев алгебраических преобразований полезными являются тождества, относящиеся к двум и трем переменным:

(1.5)

Выражения 2) и 3) называют законом поглощения; 1),5) – законом склеивания.

В справедливости тождеств 1 и 2 нетрудно убедиться, вынося за скобку в левой части переменную х. Тождество 3 доказывается с помощью распределительного закона х(х + у) = хх + ху = х + ху = х. Аналогично доказывается и тождество 4. Для доказательства тождества 5 раскроем скобки в левой части:

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

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

(1.6)

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

(1.7)

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

В общем случае теоремы де Моргана могут быть представлены в виде, предложенном Шенноном:

(1.8)

Теорема в таком виде утверждает, что инверсия любой функции получается заменой каждой переменной ее инверсией и одновременно взаимной заменой символов сложения и умножения. При практическом применении теоремы необходимо строго соблюдать группировки членов, выраженные как явными, так и неявными скобками. В качестве примера определим инверсию функции F = ху + ху. По правилу (1.8) находим:

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