Алгебра логики

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

Общепринятым для цифровой электроники стандартом является использование двух элементарных сигналов: условно \(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\).

СДНФ и многочлены Жегалкина

Рассмотрим следующую задачу: имея некий набор операций, научиться выражать произвольную операцию в виде комбинации имеющихся. Оказывается, для набора \(\land,\lor,\lnot\) эта задача решается особенно легко: если \(f(x) = 1\) только для \(x=(x_1,x_2,\ldots,x_n)=(a_1,a_2,\ldots,a_n)\), то

\[ f(x_1,x_2,\ldots,x_n)= (\lnot^{\lnot a_1} x_1)(\lnot^{\lnot a_2} x_2)\ldots (\lnot^{\lnot a_n} x_n) \]

В общем случае достаточно взять дизъюнкцию таких выражений для всех \(a\), для которых \(f(a)=1\).

Результатом такой манипуляции является штуковина (дизъюнкция конъюнкций), называемая совершенной дизъюнктивной нормальной формой (коротко СДНФ) операции \(f\). Например, импликация имеет СДНФ

\[ x\Rightarrow y = \overline{x}\,\overline{y}\lor \overline{x}y\lor xy \]

Нетрудно заметить, что СДНФ определена с точностью до перестановки конъюнктов внутри дизъюнктов и перестановки самих дизъюнктов.

С набором операций \(\land,+,1\) ситуация не сильно сложнее: интерполяционная формула Лагранжа для вершин \(n\)-мерного куба даёт выражение

\[ f(x) = \sum_a f(a) (x_1+\overline{a_1}) (x_2+\overline{a_2})\ldots (x_n+\overline{a_n}) \]

Верность равенства тривиально проверяется подстановкой \(a\) или же замечанием о том, что эта формула получена путём формальной замены в СДНФ дизъюнкции на сумму (поскольку для любого значения \(x\) не более чем один из дизъюнктов равен 1, сумма дизъюнктов СДНФ равна их дизъюнкции).

После раскрытия скобок и приведения подобных получается сумма одночленов, каждый из которых любую из переменных содержит в не более чем первой степени. Такая сумма называется многочленом Жегалкина функции \(f\). Различных одночленов \(2^n\), поэтому различных многочленов Жегалкина \(2^{2^n}\) — ровно столько же, сколько и \(n\)-арных операций. Поскольку любая операция имеет хотя бы один многочлен Жегалкина, то, согласно принципу Дирихле, любая операция имеет ровно один многочлен Жегалкина.

Например, импликация имеет многочлен Жегалкина

\[ x\Rightarrow y = (x+1)y+(x+1)(y+1)+xy = xy + x + 1 \]

Алгебры Гейтинга

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

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

Моделью интуиционистской логики или алгеброй Гейтинга называется множество \(X\), элементы \(0,1\in X\), операции \(\land,\lor,\Rightarrow: X^2\to X\) и бинарное отношение \(\rightarrow\) (называемое метаследствием) на множестве \(X\), удовлетворяющие следующим свойствам:

Рефлексивность: \(x\rightarrow x\) для всех \(x\).

Транзитивность: если \(x\rightarrow y\) и \(y\rightarrow z\), то \(x\rightarrow z\).

Строгость: если \(x\rightarrow y\) и \(y\rightarrow x\), то \(x=y\).

Начальный объект: \(0\rightarrow x\) для всех \(x\).

Конечный объект: \(x\rightarrow 1\) для всех \(x\).

Точная нижняя грань: \(z\rightarrow x\) и \(z\rightarrow y\) тогда и только тогда, когда \(z\rightarrow x\land y\).

Точная верхняя грань: \(x\rightarrow z\) и \(y\rightarrow z\) тогда и только тогда, когда \(x\lor y\rightarrow z\).

Сопряжение: \(x\land y\rightarrow z\) тогда и только тогда, когда \(x\rightarrow y\Rightarrow z\).

Простейшей нетривиальной алгеброй Гейтинга является рассмотренная выше двухзначная логика \(X={0,1}\), в которой \(0\to 0\), \(0\to 1\), \(1\to 1\) (а операции \(\land\), \(\lor\), \(\Rightarrow\) определены стандартно).

Для полноты картины приведём явным образом пример трёхзначной алгебры Гейтинга. На множестве \(X={0,\alpha,1}\) метаследствие определим так, что \(0\to \alpha\to 1\). В качестве операций \(\land\) и \(\lor\) возьмём бинарные минимум и максимум. С импликацией несколько сложнее: если \(x\to y\), то \(x\Rightarrow y = 1\). Три оставшихся случая определяются равенством \(x\Rightarrow y = y\).

Отрицание обычно определяют так: \(\lnot x = x\Rightarrow 0\) (чуть позже мы увидим, почему). Заметим, что \(\lnot\alpha = 0\), а \(\lnot 0 = 1\). Вывод: в нашей модели можно наблюдать невыполнение закона о снятии двойного отрицания. Ещё раз отметим, что все «незаконы» интуиционистской логики невозможно наблюдать даже в совокупности всех конечных моделей. Поэтому для установления свойств, присущих всем алгебрам Гейтинга, приходится общаться с аксиомами напрямую.

Несколько законов интуиционистской логики

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

Начнём с того, что поскольку \(x\land y\to x\land y\), то \(x\land y\to x\) и \(x\land y\to y\). Аналогично, для дизъюнкции \(x\to x\lor y\) и \(y\to x\lor y\).

Пусть \(z\to x\) и \(z\to x\Rightarrow y\). Поскольку всегда \(z\to z\), то \(z\to z\land x\). А из того, что \(z\to x\Rightarrow y\), следует \(z\land x\to y\). В итоге имеем цепочку \(z\to z\land x\to y\), откуда \(z\to y\). Возможность в рамках любых предположений (в нашем случае \(z\)) из истинности \(x\) и \(x\Rightarrow y\) заключать истинность \(y\) заметили ещё древние греки. А от римлян нам досталось название этого принципа — Modus Ponens (в переводе «способ вывода»).

В заключение покажем, что (внутреннее) следствие \(\Rightarrow\) по смыслу аналогично метаследствию \(\to\). Заметим сперва, что из \(x\to 1\) и \(x\to x\) следует \(x\to 1\land x\). В обратную сторону следствие мы доказали в начале этого раздела. Поэтому \(x=1\land x\). Но в таком случае \(x\to y\) имеет место тогда и только тогда, когда \(1\land x\to y\), что, в свою очередь, эквивалентно \(1\to x\Rightarrow y\).

Упражнения

Запишите явно дистрибутивность для пары операций \(\lor,\land\) и пары \(\land,\lor\).
Докажите все свойства, перечисленные во втором разделе, путём подстановки всевозможных значений переменных.
Функция голосования определяется так: \(\Gamma(x,y,z)=1\) тогда и только тогда, когда среди \(x,y,z\) есть хотя бы две единицы. Постройте СДНФ и многочлен Жеглакина для \(\Gamma\).
Докажите, что существует единственная трёхзначная алгебра Гейтинга.
Докажите, что отображение \(x\mapsto x\land y\) алгебры Гейтинга в себя является монотонным (из \(a\to b\) следует \(a\land y\to b\land y\)).
Договоримся запись \(a\land c\to b\land c\) сокращать до \(a\to_c b\). Докажите, что отношение \(\to_c\) удовлетворяет всем аксиомам интуиционистской логики, за исключением строгости, а кроме того, выполнено \(1\to_c c\).
Докажите, что в любой алегбре Гейтинга имеет место \(x\to \lnot\lnot x\). Указание: результат предыдущего упражнения позволяет, рассматривая стрелки вида \(\to_c\), где \(c=a_1\land a_2\land\ldots\land a_n\), вести рассуждения «в рамках предположений \(a_1\), \(a_2\), ..., \(a_n\)». Это позволяет, сперва предположив \(x\), воспользоваться стандартным приёмом «от противного», предположив \(\lnot x\) и получив каким-нибудь способом \(0\) в рамках сделанных предположений.