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

 

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

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

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

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

(2.1)

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

Правила 1-4, 6-9 поясняются схемами (рис. 2.2 а - з) на двух ключах в соответствии с числом слагаемых (сомножителей) в соотношениях.

Рис. 2.2. Схемы, иллюстрирующие операции логического сложения (а-г) и логического умножения (д-з)

 

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

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

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

(2.2)

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

(2.3)

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

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

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

(2.5)

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

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

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

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

(2.6)

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

(2.7)

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

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

(2.8)

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

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