Элементы алгебры логики и синтеза комбинационных схем. Формы записи логических уравнений

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

· математически записывать логические сообщения и связи между ними;

· реализовать логические уравнения в виде логических схем, т.е. переходить от аналитического описания процесса к его схемной реализации в виде логического автомата;

· оптимизировать реализацию логических автоматов (минимизировать число элементов, обеспечить их однородность и т.д.).

Логические операции могут быть представлены графически с помощью диаграмм Венна (см. рис. 5.3.1.).

a) б) в)

Рис. 5.3.1. Диаграммы Венна: а) А+В (ИЛИ); б) (НЕ); в) АВ (И)

Т.е. алгебра логики использует ранее рассмотренные логические операции, причем порядок выполнения операций существует вполне определенный. Сначала выполняется операция "НЕ", затем " И" и наконец "ИЛИ ". Для изменения порядка операций применяют скобки. Вычитания и деления в алгебре логики нет. Как и в обычной алгебре действуют следующие законы:

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

А+В+С=А+С+В=В+А+С;

А·В·С=А·С·В=В·А·С;

2. Сочетательный (ассоциативности)

А+В+С=А+(В+С)=(А+В)+С;

А·В·С=А·(В·С)=(А·В)·С

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

3. Распределительный (закон дистрибутивности)

А·(В+С)=А·В+А·С.

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

1. А+А=А			5. А·А=А			9. =А
2. А+Ā=1			6. А·Ā=0			10. А+А·В+А·С=А
3. А+0=А			7. А·0=0			11. А+Ā·В=А+В
4. А+1=1			8. А·1=А

Следующие два тождества называются либо формулами, либо теоремами де Моргана. Эти же тождества называются еще законами инверсий, а именно:

12.

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

13.

т.е. произведение инверсий равно инверсии суммы (иначе можно – инверсия суммы равна произведению инверсий; – инверсия произведения равна сумме инверсий)

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

Или: инверсия любой функции получается заменой каждой переменной её инверсией и одновременно взаимной заменой символов сложения и умножения.

Например: , а инверсия будет

Доказывается справедливость закона инверсии с помощью таблицы истинности. Так для двух переменных получим результат в виде табл.5.3.1

Таблица 5.3.1.

A	B		____ A+B		___ A·B

Все перечисленные тождества могут быть доказаны и с помощью диаграмм Венна. К примеру, на рис. 5.3.1., а) заштрихована площадь, соответствующая тождеству 11. Тождеству 12, его левой и правой частям, соответствует заштрихованная площадь на рис. 5.3.2., а на рис. 5.3.3., заштрихованная площадь соответствует формуле де Моргана- 13.

Использование законов инверсии может приводить к существенному упрощению функции, а следовательно и средств ее реализации.