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

Алгебра логики (алгебра высказываний) — раздел математической логики, в котором изучаются логические операции над высказываниями^[1]. Чаще всего предполагается, что высказывания могут быть только истинными или ложными, то есть используется так называемая бинарная или двоичная логика, в отличие от, например, троичной логики.

Основоположником её является Дж. Буль, английский математик и логик, положивший в основу своего логического учения аналогию между алгеброй и логикой. Алгебра логики стала первой системой математической логики, в которой алгебраическая символика стала применяться к логическим выводам в операциях с понятиями, рассматриваемыми со стороны их объёмов. Буль ставил перед собой задачу решить логические задачи с помощью методов, применяемых в алгебре. Любое суждение он пытался выразить в виде уравнений с символами, в которых действуют логические законы, подобные законам алгебры.

Впоследствии усовершенствованием алгебры логики занимались У. С. Джевонс, Э. Шрёдер, П. С. Порецкий, Ч. Пирс, Г. Фреге, разработавший теорию исчисления высказываний, Д. Гильберт, добившийся успехов в области применения метода формализации в операциях с логическими высказываниями. Внесли свой вклад Б. Рассел, придавший вместе с А. Уайтхедом, математической логике современный вид; И. И. Жегалкин, заслугой которого явилась дальнейшая разработка исчисления классов и значительное упрощение теории операций логического сложения; В. И. Гливенко вынес предмет алгебры логики далеко за рамки изучения объёмных операций с понятиями.

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

Определение

Базовыми элементами, которыми оперирует алгебра логики, являются высказывания.

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

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

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

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

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

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

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

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

Аксиомы

${\bar {\bar {x}}}=x$ , инволютивность отрицания, закон снятия двойного отрицания
$x\lor {\bar {x}}=1$
$\ x\lor 1=1$
$\ x\lor x=x$
$\ x\lor 0=x$
$\ x\land {\bar {x}}=0$
$\ x\land x=x$
$\ x\land 0=0$
$\ x\land 1=x$

Логические операции

Простейший и наиболее широко применяемый пример такой алгебраической системы строится с использованием множества B, состоящего всего из двух элементов:

B

= { Ложь, Истина }

Как правило, в математических выражениях Ложь отождествляется с логическим нулём, а Истина — с логической единицей, а операции отрицания (НЕ), конъюнкции (И) и дизъюнкции (ИЛИ) определяются в привычном нам понимании. Легко показать, что на данном множестве B можно задать четыре унарные и шестнадцать бинарных отношений и все они могут быть получены через суперпозицию трёх выбранных операций.

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

Логика высказываний послужила основным математическим инструментом при создании компьютеров. Она легко преобразуется в битовую логику: истинность высказывания обозначается одним битом (0 — ЛОЖЬ, 1 — ИСТИНА); тогда операция $\neg$ приобретает смысл вычитания из единицы; $\lor$ — немодульного сложения; & — умножения; $\leftrightarrow$ — равенства; $\oplus$ — в буквальном смысле сложения по модулю 2 (исключающее Или — XOR); $\mid$ — не превосходства суммы над 1 (то есть $A$ $\mid$ $B$ = $(A+B)<=1$ ).

Впоследствии булева алгебра была обобщена от логики высказываний путём введения характерных для логики высказываний аксиом. Это позволило рассматривать, например, логику кубитов, тройственную логику (когда есть три варианта истинности высказывания: «истина», «ложь» и «не определено»), комплексную логику и др.

Свойства логических операций

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

Существуют методы упрощения логической функции: например, Карта Карно, метод Куайна - Мак-Класки

История

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

См. также

Примечания

↑ Алгебра логики // Большая советская энциклопедия : [в 30 т.] / гл. ред. А. М. Прохоров. — 3-е изд. — М. : Советская энциклопедия, 1969—1978.

[1] Алгебра логики // Большая советская энциклопедия : [в 30 т.] / гл. ред. А. М. Прохоров. — 3-е изд. — М. : Советская энциклопедия, 1969—1978.

[1]