Основные положения алгебры логики

В отличие от аналоговых электронных устройств, в цифровых устройствах (ЦУ) входные и выходные сигналы могут принимать ограниченное количество состояний. В соответствии с логическим соглашением (ГОСТ 2.743-82), в зависимости от конкретной физической реализации элементов ЦУ, более положительному значению физической величины, "H" - уровень, соответствует состояние " логическая 1 ", а менее положительному значению,"L - уровень" - " логический 0 ". Такое соглашение называется положительной логикой. Обратное соотношение называется отрицательной логикой. В ГОСТ'е 19480 - 89 даны наименования, определения и условные обозначения основных параметров и характеристик цифровых микросхем.

Теоретической основой проектирования ЦУ является алгебра-логики или булева алгебра, оперирующая логическими переменными. Для логических переменных, принимающих только два значения,существуют 4 основных операции. Операция логическое "И" (AND) конъюнкция или логическое умножение, обозначается * или /\. Операция логическое "ИЛИ" (OR), дизъюнкция или логическое сложение, обозначается + или \/. Операция логическое "НЕ" (NOT), изменение значения, инверсия или отрицание, обозначается чертой над логическим выражением. Инверсия иногда будет в тексте обозначаться знаком " ~ ". Операция эквивалентности обозначается "=". Следующие соотношения являются аксиомами.

Из (1, 2) и (1',2') следует: x + x = x и x * x = x. (5)

Из (1, 3) и (2',3') следует: x + 0 = x и 0 * x = 0. (6)

Из (2, 3) и (1',3') следует: 1 + x = 1 и x * 1 = x. (7)

Из (3) и (3') следует: x +~x = 1 и~x * x = 0. (8)

Из (4) и (4') следует: ~(~x) = x. (9)

И, наконец, из (1,1'), (2,2'), (3,3') и (4,4') следует:

~(x0+x1) = ~x0 * ~x1 и ~(x0 * x1) = ~x0 + ~x1. (10)

Последние выражения (10) называют принципом двойственности или теоремой Де Моргана (инверсия логической суммы равна логическому произведению инверсий и наоборот). Соотношения двойственности для n переменных, часто записывают в виде:

~(x1 +.. + xn) = ~x1 *..* ~xn и

~(x1 *.. * xn) = ~x1 +.. + ~xn (11)

На функции И и ИЛИ распространяются обычные алгебраические законы - переместительный, сочетательный и распределительный, которые легко доказываются методом перебора: x1 op x0 = x0 op x1 - переместительный, x2 op x1 op x0 = (x2 op x1) op x0 - сочетательный и x2*(x1+x0) = (x2*x1) + (x2*x0) и x2 + (x1*x0) = (x2+x1) * (x2+x0) - распределительный, где операция op может быть, либо И, либо ИЛИ. Наряду с тремя основными логическими функциями, называемыми также переключательными, существуют и другие.