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

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

Определение

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

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

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

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

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

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

Унарные логические операции x g1 ($\lnot$) g2 (=) g3 (1) g4 (0) 0 1 0 1 0 1 0 1 1 0 g1(x) — отрицание/негация (g1(x) = $\neg$x = x') g2(x) — тождественная функция (g2(x) = x)

Бинарные логические операции x y f1 ($\and$) f2 ($\lor$) f3 ($\equiv$) f4 ($\oplus$) f5 ($\subset$) f6 ($\supset$) f7 ($\downarrow$) f8 ($\mid$) 0 0 0 0 1 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 0 0 1 1 1 1 1 1 0 1 1 0 0 x y f9 f10 f11 f12 f13 f14 f15 f16 0 0 0 0 1 1 0 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 1 0 0 1 1 0 1 0 1 1 0 0 0 0 1 1 1 0 Здесь 0 и 1 — тождественные нуль и единица соответственно, f1(x, y) — конъюнкция (f1(x, y) = x&y = x$\cdot$y = x$\and$y = min(x, y)), f2(x, y) — дизъюнкция (f2(x, y) = x$\lor$y = max(x, y)), f3(x, y) — эквивалентность (f3(x, y) = x$\sim$y = x$\equiv$y = x$\leftrightarrow$y), f4(x, y) — сумма по модулю два (f4(x, y) = x$\oplus$y), f5(x, y) — импликация от y к x (f5(x, y) = x$\leftarrow$y = x$\subset$y), f6(x, y) — импликация от x к y (f6(x, y) = x$\rightarrow$y = x$\supset$y), f7(x, y) — стрелка Пи́рса = функция Да́ггера = функция Ве́бба («антидизъюнкция») (f7(x, y) = x$\downarrow$y). f8(x, y) — штрих Ше́ффера («антиконъюнкция») (f8(x, y) = x$\mid$y), f9(x, y), f10(x, y) — инверсии импликаций f5 и f6, f11—f14 — функции только одного аргумента, f15, f16 — тождества. Все вышеперечисленные функции называются логическими связками.

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

Простейшим и наиболее широко применяемым примером такой алгебраической системы является множество 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$\and$(y$\lor$z) = (x$\and$y)$\lor$(x$\and$z),
   • x$\lor$(y$\and$z) = (x$\lor$y)$\and$(x$\lor$z),
   • x$\and$(y$\oplus$z) = (x$\and$y)$\oplus$(x$\and$z).
5. Законы де Мо́ргана:
   • $\neg$(x$\and$y) = ($\neg$ x)$\lor$($\neg$y),
   • $\neg$(x$\lor$y) = ($\neg$ x)$\and$($\neg$y).
6. Законы поглощения:
   • x$\and$(x$\lor$y) = x,
   • x$\lor$(x$\and$y) = x.
7. Другие (1):
   • x$\and$($\neg$x) = x$\and$0 = x$\oplus$x = 0.
   • x$\lor$($\neg$x) = x$\lor$1 = x$\sim$x = x$\rightarrow$x = 1.
   • x$\lor$x = x$\and$x = x$\and$1 = x$\lor$0 = x$\oplus$0 = x.
   • x$\oplus$1 = x$\rightarrow$0 = x$\sim$0 = x$\mid$x = x$\downarrow$x = $\neg$x.
   • ${\bar {\bar {x}}}=x$.
8. Другие (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}$ = $(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$.
9. Другие (3) (Дополнение законов де Мо́ргана):
   • $x \mid y$ = $\neg (x\land y)$ = $\neg x\lor\neg y$.
   • $x\downarrow y$ = $\neg (x\lor y)$ = $\neg x\land\neg y$.

История

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

cs:Booleova logika he:לוגיקה בוליאנית simple:Boolean algebra