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

Определение

---

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

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

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

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

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

|+ Унарные логические операции |-align="center" ! x || g₁ ($\backslash lnot$) || g₂ (=) || g₃ (1) || g₄ (0) |-align="center" | 0 || 1 || 0 || 1 || 0 |-align="center" | 1 || 0 || 1 || 1 || 0 g₁(x) — отрицание/негация (g₁(x) = $\backslash neg$x = x')

g₂(x) — тождественная функция (g₂(x) = x)

|+ Бинарные логические операции |- align="center" | ! x || y || width="0px"| || f₁ ($\backslash land$) || f₂ ($\backslash lor$) || f₃ ($\backslash equiv$) || f₄ ($\backslash oplus$) || f₅ ($\backslash subset$) || f₆ ($\backslash supset$) || f₇ ($\backslash downarrow$) || f₈ ($\backslash mid$) |- align="center" | | 0 || 0 || width="0px"| || 0 || 0 || 1 || 0 || 1 || 1 || 1 || 1 |- align="center" | | 0 || 1 || width="0px"| || 0 || 1 || 0 || 1 || 0 || 1 || 0 || 1 |- align="center" | | 1 || 0 || width="0px"| || 0 || 1 || 0 || 1 || 1 || 0 || 0 || 1 |- align="center" | | 1 || 1 || width="0px"| || 1 || 1 || 1 || 0 || 1 || 1 || 0 || 0 |- align="center" | ! x || y || width="0px"| || f₉ || f₁₀ || f₁₁ || f₁₂ || f₁₃ || f₁₄ || f₁₅ || f₁₆ |- align="center" | | 0 || 0 || width="0px"| || 0 || 0 || 1 || 1 || 0 || 0 || 1 || 0 |- align="center" | | 0 || 1 || width="0px"| || 0 || 1 || 1 || 0 || 0 || 1 || 1 || 0 |- align="center" | | 1 || 0 || width="0px"| || 1 || 0 || 0 || 1 || 1 || 0 || 1 || 0 |- align="center" | | 1 || 1 || width="0px"| || 0 || 0 || 0 || 0 || 1 || 1 || 1 || 0 Здесь 0 и 1 — тождественные нуль и единица соответственно,

f₁(x, y) — конъюнкция (f₁(x, y) = x&y = x$\backslash cdot$y = x$\backslash land$y = min(x, y)),

f₂(x, y) — дизъюнкция (f₂(x, y) = x$\backslash lor$y = max(x, y)),

f₃(x, y) — эквивалентность (f₃(x, y) = x$\backslash sim$y = x$\backslash equiv$y = x$\backslash leftrightarrow$y),

f₄(x, y) — сумма по модулю два (f₄(x, y) = x$\backslash oplus$y),

f₅(x, y) — импликация от y к x (f₅(x, y) = x$\backslash leftarrow$y = x$\backslash subset$y),

f₆(x, y) — импликация от x к y (f₆(x, y) = x$\backslash rightarrow$y = x$\backslash supset$y),

f₇(x, y) — стрелка Пи́рса = функция Да́ггера = функция Ве́бба
(«антидизъюнкция») (f₇(x, y) = x$\backslash downarrow$y).

f₈(x, y) — штрих Ше́ффера («антиконъюнкция») (f₈(x, y) = x$\backslash mid$y),

f₉(x, y), f₁₀(x, y) — инверсии импликаций f₅ и f₆,

f₁₁—f₁₄ — функции только одного аргумента,

f₁₅, f₁₆ — тождества.

Все вышеперечисленные функции называются логическими связками.

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

---

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

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

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

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

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

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

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

---

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

Алгебра | Математическая логика

Booleova logika | Boolean logic | Boolean algebra | 布尔逻辑