А́лгебра ло́гики, раздел математической логики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операций над ними.

Алгебра логики возникла в середине 19 в. в трудах Дж. Буля (Boole. 1847, 1854) и развилась затем в работах Ч. C. Пирса, П. С. Порецкого, Б. Рассела, Д. Гильберта и др. Создание алгебры логики представляло собой попытку решать традиционные логические задачи алгебраическими методами. С появлением теории множеств (1870-е гг.) основным предметом алгебры логики стали высказывания и логические операции над ними. Под высказываниями понимаются предложения, относительно которых имеет смысл утверждать, истинны они или ложны; например, высказывание «кит – животное» истинно, в то время как высказывание «все углы – прямые» ложно. Употребляемые в обычной речи логические связки «и», «или», «если..., то», «эквивалентно», частица «не» и т. д. позволяют из уже заданных высказываний строить новые, более «сложные» высказывания. Так, из высказываний «$x>2$», «$x \leqslant 3$» при помощи связки «и» можно получить высказывание «$x>2$ и $x\leqslant 3$», при помощи связки «или» – высказывание «$x>2$ или $x\leqslant 3$ » и т. д.

Истинность или ложность получаемых таким образом высказываний зависит от истинности или ложности исходных высказываний и соответствующей трактовки связок как операций над высказываниями. Для обозначения истинности вводится символ «И» и для обозначения ложности – символ «Л». Затем вместо этих символов стали употреблять числа $1$ и $0$. Связки «и», «или», «если..., то», «эквивалентно» обозначаются соответственно знаками $\And$ (конъюнкция), $\vee$ (дизъюнкция), $\rightarrow$ (импликация), $\sim$ (эквивалентность); для отрицания вводится знак $\bar{\phantom{x}}$ (чёрточка сверху). Наряду с индивидуальными высказываниями, примеры которых приводились выше, стали использоваться также переменные высказывания, т. е. такие переменные, значениями которых могут быть любые наперёд заданные индивидуальные высказывания. Далее индуктивно вводится понятие формулы, являющееся формализацией понятия сложного высказывания. Пусть $A, B, C, \ldots$ обозначают индивидуальные, а $x, y, z, \ldots$ – переменные высказывания. Каждая из этих букв называется формулой. Если знак $*$ обозначает любую из перечисленных выше связок, а $\mathfrak{A}$ и $\mathfrak{B}$ формулы, то $(\mathfrak{A}*\mathfrak{B})$ и $\bar{\mathfrak{A}}$ суть формулы, например $((x \And y) \rightarrow \bar{z})$. Связки и частица «не» стали рассматриваться как операции над величинами, принимающими значения $0$ и $1$, и результатом применения этих операций также являются числа $0$ и $1$. Конъюнкция $x\And y$ равна $1$ тогда и только тогда, когда и $x$, и $y$ равны $1$; дизъюнкция $x\vee y$ равна $0$ тогда и только тогда, когда и $x$, и $y$ равны $0$; импликация $x\rightarrow y$ равна $0$ тогда и только тогда, когда $x$ равен $1$, а $y$ равен $0$; эквивалентность $x\sim y$ равна $1$ тогда и только тогда, когда значения $x$ и $y$ совпадают; отрицание $\bar{x}$ равно $1$ тогда и только тогда, когда $x$ равен $0$. Введённые операции позволяют каждой формуле при заданных значениях входящих в неё высказываний приписать одно из двух значений – $0$ или $1$. Тем самым каждая формула может одновременно рассматриваться как некоторый способ задания, или реализации, функций алгебры логики, т. е. таких функций, которые определены на наборах из нулей и единиц и которые в качестве значений принимают также $0$ или $1$. При этом формулы $\mathfrak{A}$ и $\mathfrak{B}$ называются равными (обозначение $\mathfrak{A}=\mathfrak{B}$), если они реализуют равные функции. Объектом изучения алгебры логики стали функции алгебры логики и различные операции над ними. В последующем класс функций алгебры логики был расширен до класса функций, аргументы которых и сами функции принимают в качестве значений элементы фиксированного конечного множества $E$; расширился также запас операций над функциями. Иногда под алгеброй логики понимается как раз последняя концепция. Для приложений, однако, наибольшее значение имеет всё-таки тот случай, когда мощность указанного множества $E$ равна двум, поэтому он будет рассмотрен особенно подробно. Излагаемые здесь результаты также тесно связаны с другим подходом в изучении высказываний – т. н. исчислением высказываний.

Для задания функций алгебры логики иногда используют таблицы, содержащие все наборы значений переменных и значения функций на этих наборах. Так, например, сводная таблица, задающая функции $\bar{x}$, $x\And y$, $x\vee y$, $x\rightarrow y$, $x\sim y$, имеет вид:

Аналогично устроены таблицы для произвольных функций алгебры логики. Это т. н. табличный способ задания функций алгебры логики. Сами таблицы иногда называются истинностными таблицами. Для преобразования формул в равные формулы важную роль играют следующие равенства:

$$x \And y=y \And x, \quad x \vee y=y \vee x \tag{1}$$(закон коммутативности),

$$\begin{aligned} (x \And y) \And z & =x \And(y \And z), \\ (x \vee y) \vee z & =x \vee(y \vee z) \tag{2} \end{aligned}$$(закон ассоциативности),

$$\begin{aligned} & x \And(x \vee y)=x, \\ & x \vee(x \And y)=x \tag{3} \end{aligned}$$(закон поглощения),

$$\begin{aligned} & x \And(y \vee z)=(x \And y) \vee(x \And z), \\ & x \vee(y \And z)=(x \vee y) \And(x \vee z) \tag{4} \end{aligned}$$(закон дистрибутивности),

$$x \And \bar{x}=0 \tag{5}$$(закон противоречия),

$$x \vee \bar{x}=1 \tag{6}$$(закон исключённого третьего),

$$\begin{gathered} x \rightarrow y=\bar{x} \vee y, \\ x \sim y=(x \And y) \vee(\bar{x} \And \bar{y}) . \tag{7} \end{gathered}$$Эти равенства позволяют уже без помощи таблиц получать другие равенства. Методом получения последних являются т. н. тождественные преобразования, которые меняют, вообще говоря, выражение, но не функцию, реализуемую этим выражением. Например, при помощи законов поглощения получается закон идемпотентности $x\vee x=x$. Упомянутые равенства в ряде случаев позволяют существенно упростить запись формул освобождением от «лишних скобок». Так, соотношения (1) и (2) дают возможность вместо формул $\left.\left(\ldots\left(\mathfrak{A}_1\And\mathfrak{A}_2\right) \And \ldots\right) \And \mathfrak{A}_s\right)$ и $\left.\left(\ldots\left(\mathfrak{B}_1 \vee \mathfrak{B}_2\right) \vee \ldots\right) \vee \mathfrak{B}_s\right)$ использовать более компактную запись $\mathfrak{A}_1 \And \mathfrak{A}_2 \And \ldots \And \mathfrak{A}_s$ и $\mathfrak{B}_1 \vee \mathfrak{F}_2 \vee \ldots \vee \mathfrak{R}_s$. Первое из этих соотношений называется конъюнкцией сомножителей $\mathfrak{A}_1, \ldots, \mathfrak{A}_s$, а второе – дизъюнкцией слагаемых $\mathfrak{B}_1, \ldots, \mathfrak{B}_s$. Равенства (5), (6), (7) показывают также, что константы $0$ и $1$, импликацию и эквивалентность, рассматривая их как функции, можно выразить через конъюнкцию, дизъюнкцию и отрицание. Более того, всякая функция алгебры логики может быть реализована формулой, записываемой с помощью символов $\&$, $\vee$, $\bar{\phantom{x}}$.

Множество всех формул, в построении которых участвуют переменные высказывания и некоторые из символов $\&$, $\vee$, $\rightarrow$, $\sim$, $\bar{\phantom{x}}$ и констант $0$ и $1$, называется языком над данными символами и константами. Равенства (1)–(7) показывают, что для всякой формулы в языке над $\&$, $\vee$, $\rightarrow$, $\sim$, $\bar{\phantom{x}}$, $0$, $1$ найдётся равная ей формула в языке над $\&$, $\vee$, $\bar{\phantom{x}}$, $0$, $1$, например:

$$(x \rightarrow y) \sim z=((\bar{x} \vee y) \And z) \vee((\overline{\bar{x} \vee y}) \And \bar{z}).$$Особую роль в последнем языке играет класс формул, которые могут быть записаны в виде $\mathfrak{A}_1 \vee \mathfrak{A}_2 \vee \ldots \vee \mathfrak{A}_s$, $0$ или $1$, где $s\geqslant 1$ и каждое $\mathfrak{A}_i$ – либо переменное высказывание, либо его отрицание, либо конъюнкция таковых, при этом каждое $\mathfrak{A}_i$ не содержит одинаковых сомножителей и не содержит сомножителей вида $x$ и $\bar{x}$ одновременно и все $\mathfrak{A}_i$ попарно не равны. Здесь скобки опускаются, т. к. предполагается, что операция конъюнкции связывает «сильнее», чем дизъюнкция, т. е. при вычислении по заданным значениям переменных следует сначала вычислять значения $\mathfrak{A}_1, \ldots, \mathfrak{A}_s$. Эти выражения называются дизъюнктивными нормальными формами (д. н. ф.). Каждую формулу $u$ в языке над $\&$, $\vee$, $\rightarrow$, $\sim$, $\bar{\phantom{x}}$, $0$, $1$, реализующую функцию алгебры логики, отличную от $0$, при помощи равенств (1)–(7), можно привести к равной ей дизъюнктивной нормальной форме, содержащей все переменные формулы $u$ и любое число других переменных, причём каждое $\mathfrak{A}_i$ в этой дизъюнктивной нормальной форме содержит одни и те же переменные. Такая дизъюнктивная нормальная форма называется совершенной дизъюнктивной нормальной формой формулы $u$; для $0$ совершенной дизъюнктивной нормальной формой является сама формула $0$. Возможность приведения к совершенной дизъюнктивной нормальной форме лежит в основе алгоритма, устанавливающего равенство или неравенство двух наперёд заданных формул. Алгоритм этот состоит в следующем: приводят исследуемые формулы $u_1$ и $u_2$ к совершенным дизъюнктивным нормальным формам, содержащим все те переменные, которые есть как в $u_1$, так и в $u_2$, и смотрят, совпадают полученные выражения или нет; если совпадают, то $u_1=u_2$, если нет, то $u_1\neq u_2$. Важную роль в алгебре логики и её приложениях играет сокращённая дизъюнктивная нормальная форма, т. е. такая, для которой выполнены следующие условия: 1) в ней нет таких пар слагаемых $\mathfrak{A}_i$ и $\mathfrak{A}_j$, что всякий сомножитель из $\mathfrak{A}_i$ имеется и в $\mathfrak{A}_j$; 2) для всяких двух слагаемых $\mathfrak{A}_i$ и $\mathfrak{A}_j$, из которых одно содержит сомножителем некоторое переменное, а другое – отрицание этого переменного (при условии, что другого переменного, для которого это же имеет место, в данной паре слагаемых нет), имеется (в этой же дизъюнктивной нормальной форме) слагаемое $\mathfrak{A}_k$, равное конъюнкции остальных сомножителей этих двух слагаемых. Всякая дизъюнктивная нормальная форма при помощи равенств (1)–(7) может быть приведена к равной ей сокращённой дизъюнктивной нормальной форме. Например, сокращённой дизъюнктивной нормальной формой для формулы $((x \sim(y \rightarrow z)) \rightarrow(x \And z))$ является $\bar{x}\And \bar{y} \vee z \And x \And y$. Формулы $u_1$ и $u_2$ равны тогда и только тогда, когда их сокращённые дизъюнктивные нормальные формы совпадают. Кроме дизъюнктивных нормальных форм, употребляются также конъюнктивные нормальные формы (к. н. ф.), т. е. выражения, которые можно получить из дизъюнктивных нормальных форм путём замены в них знаков $\vee$ на $\&$, a $\&$ на $\vee$ и $0$ на $1$. Например, из дизъюнктивной нормальной формы $x\& y\vee \bar{x} \& z$ получается конъюнктивная нормальная форма $(x\vee y) \And (\bar{x} \vee z)$. Операция (или функция) $f$ называется двойственной для операции $\psi$, если таблица, задающая $f$, получается из таблицы, задающей $\psi$, путём замены в ней всюду $0$ на $1$ и $1$ на $0$ (включая замену значений функций). Например, конъюнкция и дизъюнкция двойственны между собой, отрицание двойственно самому себе, константы $1$ и $0$ двойственны друг другу и т. д. Преобразование формул, при котором знаки всех операций в выражении заменяются на знаки двойственных им операций, константа $0$ заменяется на $1$, а $1$ на $0$, называется преобразованием двойственности. Если верно равенство $\mathfrak{A}=\mathfrak{B}$ и $\mathfrak{A}^*$ двойственно $\mathfrak{A}$, а $\mathfrak{B}^*$ двойственно $\mathfrak{B}$, то верно равенство $\mathfrak{A}^*=\mathfrak{B}^*$, называющееся двойственным предыдущему; это т. н. принцип двойственности. Примерами двойственных равенств являются пары законов (1), (2), (3); равенство (5) двойственно равенству (6), каждая конъюнктивная нормальная форма двойственна некоторой дизъюнктивной нормальной форме. Совершенная конъюнктивная нормальная форма и сокращённая конъюнктивная нормальная форма определяются как такие конъюнктивные нормальные формы, что двойственные им выражения являются соответственно совершенной дизъюнктивной нормальной формой и сокращённой дизъюнктивной нормальной формой. Совершенные и сокращённые дизъюнктивные нормальные формы и конъюнктивные нормальные формы используются для решения задачи обзора всех гипотез и всех следствий заданной формулы. Под гипотезой формулы $\mathfrak{A}$ понимается такая формула $\mathfrak{B}$, что $(\mathfrak{B} \rightarrow \mathfrak{A})=1$; а под следствием формулы $\mathfrak{A}$ – такая формула $\mathfrak{B}$, что $(\mathfrak{A} \rightarrow \mathfrak{B})=1$. Гипотеза формулы $\mathfrak{A}$ называется простой, если она есть конъюнкция переменных или их отрицаний и после отбрасывания любого из её сомножителей перестаёт быть гипотезой формулы $\mathfrak{A}$. Аналогично следствие формулы $\mathfrak{A}$ называется простым, если оно есть дизъюнкция переменных или их отрицаний и после отбрасывания любого из её слагаемых перестаёт быть следствием формулы $\mathfrak{A}$. Решение задачи обзора гипотез и следствий основано на указании алгоритма, строящего все простые гипотезы и следствия для заданной формулы, и на получении из них при помощи законов (2)–(7) всех остальных гипотез и следствий. Алгоритм опирается на следующие факты. Если $\mathfrak{A}=\mathfrak{B}$, то $\mathfrak{A}$ и $\mathfrak{B}$ имеют одни и те же гипотезы и следствия соответственно. Слагаемое дизъюнктивной нормальной формы является гипотезой этой дизъюнктивной нормальной формы, сомножитель конъюнктивной нормальной формы – следствием этой конъюнктивной нормальной формы. Если $\mathfrak{A}$ – гипотеза выражения $\mathfrak{B}$, то $\mathfrak{A} \And\mathfrak{S}$ есть тоже гипотеза для $\mathfrak{B}$; если $\mathfrak{A}$ – следствие выражения $\mathfrak{B}$, то $\mathfrak{A} \vee \mathfrak{S}$ есть тоже следствие из $\mathfrak{B}$. Если $\mathfrak{A}$ и $\mathfrak{S}$ – гипотезы выражения $\mathfrak{B}$, то $\mathfrak{A} \vee \mathfrak{S}$ – тоже гипотеза для $\mathfrak{B}$; если $\mathfrak{A}$ и $\mathfrak{S}$ – следствия из $\mathfrak{A}$, то $\mathfrak{A} \& \mathfrak{S}$ – тоже следствие из $\mathfrak{A}$. У совершенной дизъюнктивной нормальной формы нет других гипотез (не содержащих букв, не входящих в эту дизъюнктивную нормальную форму), кроме дизъюнкций некоторых её слагаемых или дизъюнктивных нормальных форм, равных им. У совершенной конъюнктивной нормальной формы нет других следствий, кроме конъюнкций некоторых её сомножителей или равных им выражений. Сокращённая дизъюнктивная нормальная форма есть дизъюнкция всех своих простых гипотез; сокращённая конъюнктивная нормальная форма есть конъюнкция всех своих простых следствий. Сокращённая дизъюнктивная нормальная форма имеет важные приложения. Прежде всего следует отметить задачу минимизации функций алгебры логики, являющуюся частью задачи синтеза управляющих систем. Минимизация функций алгебры логики состоит в построении такой дизъюнктивной нормальной формы для заданной функции алгебры логики, которая реализует эту функцию и имеет наименьшее суммарное число сомножителей в своих слагаемых, т. е. имеет минимальную сложность. Такие дизъюнктивные нормальные формы называются минимальными. Каждая минимальная дизъюнктивная нормальная форма для заданной отличной от константы функции алгебры логики получается из сокращённой дизъюнктивной нормальной формы этой функции путём выбрасывания некоторых слагаемых. Для отдельных функций сокращённая дизъюнктивная нормальная форма может совпадать с минимальной дизъюнктивной нормальной формой. Это имеет место, например, для монотонных функций, т. е. таких функций, которые реализуются формулами над $\&$, $\vee$, $0$, $1$.

В языке над $\&$, $\vee$, $\rightarrow$, $\sim$, $0$, $1$, $+$, где знак $+$ интерпретируется как сложение по модулю $2$, устанавливаются следующие соотношения:

$$x \vee y=((x \And y)+x)+y, \tag{8}$$$$x \rightarrow y=\bar{x} \And y, \; x \sim y=(x+y)+1, \tag{9}$$$$x+y=(x \And y) \vee(\bar{x} \And \bar{y}), \quad 1=x \vee \bar{x} . \tag{10}$$Эти формулы позволяют переводить формулы в языке над $\&$, $\vee$, $\rightarrow$, $\bar{\phantom{x}}$, $0$, $1$ в равные им формулы в языке над $\&$, $+$, $1$ и обратно. Тождественные преобразования в последнем языке осуществляются при помощи равенств, установленных для конъюнкции, и дополнительных:

$$x+y=y+x, \tag{11}$$$$(x+y)+z=x+(y+z), \tag{12}$$$$x \And (y+z)=x \And y+x \And z, \tag{13}$$$$x \And x=x, \quad x+(y+y)=x, \quad x \And 1=x ; \tag{14}$$здесь по-прежнему считается, что конъюнкция связывает сильнее, чем знак $+$. Этих равенств достаточно для того, чтобы из них при помощи тождественных преобразований так же, как и при рассмотрении языка над $\&$, $\vee$, $\rightarrow$, $\sim$, $\bar{\phantom{x}}$, $0$, $1$, можно было вывести любое верное равенство в языке над $\&$, $+$, $1$. Выражение в этом языке называется приведённым полиномом, если оно либо имеет вид $\mathfrak{A}_1+\mathfrak{A}_2+\ldots+\mathfrak{A}_s$, где $\mathfrak{A}_i$ есть или $1$, или переменное, или конъюнкция различных переменных без отрицаний, $\mathfrak{A}_i \neq \mathfrak{A}_j$ при $i \neq j$, $s \geqslant 1$, либо равно $1+1$. Например, выражение $x \And y \And z+x \And y+1$ является приведённым полиномом. Всякую формулу алгебры логики при помощи тождественных преобразований можно привести к приведённому полиному. Равенство $\mathfrak{A}=\mathfrak{B}$ имеет место тогда и только тогда, когда приведённый полином для $\mathfrak{A}$ совпадает с приведённым полиномом для $\mathfrak{B}$. Кроме рассмотренных языков, существуют и другие языки, равносильные им (два языка называются равносильными, если при помощи некоторых правил преобразований каждая формула одного из этих языков переводится в некоторую равную ей формулу в другом языке, и обратно). В основу такого языка достаточно положить любую систему операций (и констант), обладающую тем свойством, что через операции (и константы) этой системы можно представить всякую функцию алгебры логики. Такие системы называются функционально полными. Примерами полных систем являются $\{\overline{x \vee y}\}$, $\{x \vee y, \bar{x}\}$, $\{x+y, 1, x \And y\}$ и т. п. Существует алгоритм, который по произвольной конечной системе функций алгебры логики устанавливает её полноту или неполноту. Он основан на следующем факте. Система функций алгебры логики является полной тогда и только тогда, когда она содержит такие функции $f_1(x, y, \ldots, v)$ и $f_2(x, y, \ldots, v)$, что $f_1(0,0, \ldots, 0)=1$ и $f_2(1,1, \ldots, 1)=0$, а также функции $f_3$, $f_4$ и $f_5$, где $f_3 \neq f_3^*$, $f_4$ не монотонная, а для $f_5$ приведённый полином содержит слагаемое $\mathfrak{A}$, в котором больше одного сомножителя. Рассматриваются и такие языки, в основе которых лежат системы операций, не являющиеся функционально полными, и таких языков бесконечно много. Среди них имеется бесконечно много попарно несравнимых языков (в смысле отсутствия переводимости при помощи тождественных преобразований с одного языка на другой). Однако для всякого языка, построенного на основе тех или иных операций алгебры логики, существует такая конечная система равенств этого языка, что всякое равенство выводимо при помощи тождественных преобразований из равенств этой системы. Такая система называется дедуктивно полной системой равенств данного языка. Например, равенства (1)–(6) составляют полную систему равенств языка над $\&$, $\vee$, $\bar{\phantom{x}}$, $0$, $1$.

Рассматривая тот или иной из упомянутых выше языков вместе с некоторой полной системой равенств этого языка, иногда отвлекаются от табличного задания операций, лежащих в основе языка, и от того, что значениями его переменных являются высказывания. Вместо этого допускаются различные интерпретации языка, состоящие из той или иной совокупности объектов (служащих значениями переменных) и системы операций над объектами этого множества, удовлетворяющих равенствам из полной системы равенств языка. Так, язык над $\&$, $\vee$, $\bar{\phantom{x}}$, $0$, $1$ в результате такого шага превращается в язык булевой алгебры; язык над $\&$, $+$, $1$ превращается в язык булева кольца (с единицей), язык над $\&$, $\vee$, $\bar{\phantom{x}}$ превращается в язык дистрибутивной решётки и т. д.

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