Законы алгебры логики

Своим существованием наука «алгебра логики» обязана английскому математику Джорджу Булю, который исследовал логику высказываний. Алгебра логики стала первой системой математической логики, в которой алгебраическая символика стала применяться к логическим выводам. Буль ставил перед собой задачу решить логические задачи с помощью методов, применяемых в алгебре. Любое суждение он пытался выразить в виде уравнений с символами, в которых действуют логические законы, подобные законам алгебры. Первый в России курс по алгебре логики был прочитан П. С. Порецким в Казанском государственном университете.

В математических выражениях Ложь отождествляется с логическим нулём, а Истина — с логической единицей.

Логические операции отрицания (НЕ), конъюнкции (И) и дизъюнкции (ИЛИ) определяются в привычном нам понимании. Также существуют дополнительные операции, такие как эквиваленция ${\displaystyle \leftrightarrow }$ («тогда и только тогда, когда»), импликация ${\displaystyle \rightarrow }$ («следовательно»), сложение по модулю два ${\displaystyle \oplus }$ («исключающее или»), штрих Шеффера ${\displaystyle \mid }$, стрелка Пирса ${\displaystyle \downarrow }$ и некоторые другие.

1. Коммутативность: ${\displaystyle x\circ y=y\circ x,\circ \in \{\land ,\lor ,\oplus ,\sim ,\mid ,\downarrow \}}$.
2. Идемпотентность: ${\displaystyle x\circ x=x,\circ \in \{\land ,\lor \}}$.
3. Ассоциативность: ${\displaystyle (x\circ y)\circ z=x\circ (y\circ z),\circ \in \{\land ,\lor ,\oplus ,\sim \}}$.
4. Дистрибутивность конъюнкций и дизъюнкции относительно дизъюнкции, конъюнкции и суммы по модулю два соответственно:
   • ${\displaystyle x\land (y\lor z)=(x\land y)\lor (x\land z)}$,
   • ${\displaystyle x\lor (y\land z)=(x\lor y)\land (x\lor z)}$,
   • ${\displaystyle x\land (y\oplus z)=(x\land y)\oplus (x\land z)}$.
5. Законы де Мо́ргана:
   • ${\displaystyle {\overline {x\land y}}={\bar {x}}\lor {\bar {y}}}$,
   • ${\displaystyle {\overline {x\lor y}}={\bar {x}}\land {\bar {y}}}$.
6. Законы поглощения:
   • ${\displaystyle x\land (x\lor y)=x}$,
   • ${\displaystyle x\lor (x\land y)=x}$.
7. Другие законы:
   • ${\displaystyle x\land {\bar {x}}=x\land 0=x\oplus x=0}$.
   • ${\displaystyle x\lor {\bar {x}}=x\lor 1=x\sim x=x\rightarrow x=1}$.
   • ${\displaystyle x\lor x=x\land x=x\land 1=x\lor 0=x\oplus 0=x}$.
   • ${\displaystyle x\oplus 1=x\rightarrow 0=x\sim 0=x\mid x=x\downarrow x={\bar {x}}}$.
   • ${\displaystyle {\bar {\bar {x}}}=x}$, инволютивность отрицания, закон снятия двойного отрицания.
8. Другие (2):
   • ${\displaystyle x\oplus y=x\land {\bar {y}}\lor {\bar {x}}\land y=(x\lor y)\land ({\bar {x}}\lor {\bar {y}})}$.
   • ${\displaystyle x\sim y={\overline {x\oplus y}}=1\oplus x\oplus y=x\land y\lor {\bar {x}}\land {\bar {y}}=(x\lor {\bar {y}})\land ({\bar {x}}\lor y)}$.
   • ${\displaystyle x\rightarrow y={\bar {x}}\lor y=x\land y\oplus x\oplus 1}$.
   • ${\displaystyle x\lor y=x\oplus y\oplus x\land y}$.
9. Дополнение законов де Мо́ргана:
   • ${\displaystyle x\mid y={\overline {x\land y}}={\bar {x}}\lor {\bar {y}}}$.
   • ${\displaystyle x\downarrow y={\overline {x\lor y}}={\bar {x}}\land {\bar {y}}}$.

Базовыми элементами, которыми оперирует алгебра логики, являются высказывания. Высказывания строятся над множеством {${\displaystyle B}$, ${\displaystyle \lnot }$, ${\displaystyle \land }$, ${\displaystyle \lor }$, ${\displaystyle 0}$, ${\displaystyle 1}$}, где ${\displaystyle B}$ — непустое множество, над элементами которого определены три операции:

${\displaystyle \lnot }$ отрицание (унарная операция),

${\displaystyle \land }$ конъюнкция (бинарная),

${\displaystyle \lor }$ дизъюнкция (бинарная),

а логический ноль 0 и логическая единица 1 — константы.

Также используются названия:

• Дизъю́нкт — пропозициональная формула, являющаяся дизъюнкцией одного или более литералов (например ${\displaystyle x_{1}\lor \neg x_{2}\lor x_{4}}$).
• Конъюнкт — пропозициональная формула, являющаяся конъюнкцией одного или более литералов (например ${\displaystyle x_{1}\land \neg x_{2}\land x_{4}}$).

Унарная операция отрицания в тексте формул оформляется либо в виде значка перед операндом (${\displaystyle \lnot x}$) либо в виде черты над операндом (${\displaystyle {\bar {x}}}$).

Логические выражения могут быть простыми и сложными. Простое логическое выражение состоит из одного высказывания и не содержит логических операций. В простом логическом выражении возможен только один результат — либо «истина», либо «ложь». Сложное логическое выражение содержит высказывания, объединённые логическими операциями. По аналогии с понятием функции в алгебре сложное логическое выражение содержит аргументы, которые являются высказывания. Истинность сложного высказывания можно определить, зная значение входящих в него высказываний.