Основные операции и законы

Основные операции

Общепринятым для цифровой электроники стандартом является использование двух элементарных сигналов: условно \(0\) и \(1\). В связи с этим наиболее простой моделью такой электроники является отображение \(\mathbf{2}^m\to \mathbf{2}^n\), имеющее, грубо говоря, \(m\) двоичных входов и \(n\) двоичных выходов (символом \(\mathbf{2}\) здесь обозначено множество \({0,1}\)).

Отображения \(\mathbf{2}^n\to \mathbf{2}\) мы будем называть логическими операциями арности \(n\) или \(n\)-арными операциями. Элементарные величины \(0\) и \(1\) можно считать операциями арности \(0\). Всего \(n\)-арных операций, как нетрудно вычислить, \(2^{2^n}\). В частности, есть четыре унарных операции и шестнадцать бинарных. Наиболее интересны следующие:

Отрицание: \(\lnot 0 = 1\) и \(\lnot 1 = 0\).

Альтернативные обозначения: \(\lnot x = \overline{x} = \,!x\).

Конъюнкция: \(x\land y = 1\) тогда и только тогда, когда \(x=1\) и \(y=1\).

Альтернативные обозначения: \(x\land y = x\cdot y = x\times y = xy = x \& y\).

Дизъюнкция: \(x\lor y = 1\) тогда и только тогда, когда хотя бы кто-то из \(x\) или \(y\) равен \(1\).

Альтернативные обозначения: \(x\lor y = x\,|\,y = x+y\).

Сложение (или XOR от eXclusive OR): \(x\oplus y = (x+y)\bmod 2\).

Альтернативные обозначения: \(x\oplus y = x+y\).

Импликация: \(x\Rightarrow y = \overline{x} \lor y\).

Штрих Шеффера (или NAND от Not AND): \(x\,|\,y = \lnot(xy)\).

Стрелка Пирса (или NOR от Not OR): \(x\downarrow y = \lnot(x\lor y)\).

Как можно заметить, некоторые обозначения используются сразу для нескольких операций. Поэтому мы остановимся на некоторой единой системе обозначений: \(\lnot x\) и \(\overline{x}\) — для отрицания, \(xy\) и \(x\land y\) — для конъюнкции, \(x\lor y\) — для дизъюнкции, \(x + y\) — для сложения.

Алгебраические свойства

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

Законы де Моргана: \(\overline{x\land y} = \overline{x}\lor\overline{y}\) и \(\overline{x\lor y} = \overline{x}\land\overline{y}\).

Снятие двойного отрицания: \(\lnot\lnot x = x\).

Третьего не дано: \(x\lor\overline{x} = 1\).

Коммутативность: \(xy=yx\) (выполняется также для \(\lor\) и \(+\)).

Ассоциативность: \(x(yz)=x(yz)\) (выполняется также для \(\lor\) и \(+\)).

Дистрибутивность: \(x(y+z)=xy+xz\) (выполняется также для \(\lor,\land\) и \(\land,\lor\)).

Идемпотентность: если \(n\geqslant 1\), то \(x^n=x\).