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

Не следует путать с булевой алгеброй.

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

Определение

Базовыми элементами, которыми оперирует алгебра логики, являются высказывания. Высказывания строятся над множеством {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$).

Аксиомы

1. $\bar {\bar x}=x$
2. $x+\bar x=1$
3. $\ x+1=1;$
4. $\ x+x=x;$
5. $\ x+0=x;$
6. $\ x*\bar x=0$
7. $\ x*x=x;$
8. $\ x*0=0;$
9. $\ x*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).

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

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

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

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

История

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

См. также

• Булева алгебра
• Булева функция
• Битовые операции