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

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

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

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

Определение

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

Высказывания строятся над множеством { ${\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}}}$ ), что компактнее, но в целом менее заметно.

Аксиомы

1. ${\displaystyle {\bar {\bar {x}}}=x}$ , инволютивность отрицания , закон снятия двойного отрицания
2. ${\displaystyle x\lor {\bar {x}}=1}$
3. ${\displaystyle \ x\lor 1=1}$
4. ${\displaystyle \ x\lor x=x}$
5. ${\displaystyle \ x\lor 0=x}$
6. ${\displaystyle \ x\land {\bar {x}}=0}$
7. ${\displaystyle \ x\land x=x}$
8. ${\displaystyle \ x\land 0=0}$
9. ${\displaystyle \ x\land 1=x}$

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

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

${\displaystyle B}$ = { Ложь, Истина }

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

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

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

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

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

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. Другие (1):
   • ${\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. Другие (3) (Дополнение законов де Мо́ргана ):
   • ${\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}}}$ .

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

История

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

См. также

• Булева алгебра
• Булева функция
• Битовые операции
• Логика высказываний
• Функциональная полнота

Примечания