Wikia

Математика

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

Обсуждение0
1426статей на этой вики

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

Определение Править

Высказывания строятся над множеством {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).

Унарные логические операции
x g1 (\lnot) g2 (=) g3 (1) g4 (0)
0 1 0 1 0
1 0 1 1 0

g1(x) — отрицание/негация (g1(x) = \negx = x')

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

Бинарные логические операции
x y f1 (\land) 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\cdoty = x\landy = min(x, y)),

f2(x, y) — дизъюнкция (f2(x, y) = x\lory = max(x, y)),

f3(x, y) — эквивалентность (f3(x, y) = x\simy = x\equivy = x\leftrightarrowy),

f4(x, y) — сумма по модулю два (f4(x, y) = x\oplusy),

f5(x, y) — импликация от y к x (f5(x, y) = x\leftarrowy = x\subsety),

f6(x, y) — импликация от x к y (f6(x, y) = x\rightarrowy = x\supsety),

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

f8(x, y) — штрих Ше́ффера («антиконъюнкция») (f8(x, y) = x\midy),

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\circy = y\circx, \circ\in{&, \lor, \oplus, \sim, \mid, \downarrow}.
  2. Идемпотентность: x\circx = x, \circ\in{&, \lor}.
  3. Ассоциативность: (x\circy)\circz = x\circ(y\circz), \circ\in{&, \lor, \oplus, \sim}.
  4. Дистрибутивность конъюнкций и дизъюнкции относительно дизъюнкции, конъюнкции и суммы по модулю два соответственно:
    • x\land(y\lorz) = (x\landy)\lor(x\landz),
    • x\lor(y\landz) = (x\lory)\land(x\lorz),
    • x\land(y\oplusz) = (x\landy)\oplus(x\landz).
  5. Законы де Мо́ргана:
    • \neg(x\landy) = (\neg x)\lor(\negy),
    • \neg(x\lory) = (\neg x)\land(\negy).
  6. Законы поглощения:
    • x\land(x\lory) = x,
    • x\lor(x\landy) = x.
  7. Другие (1):
    • x\land(\negx) = x\land0 = x\oplusx = 0.
    • x\lor(\negx) = x\lor1 = x\simx = x\rightarrowx = 1.
    • x\lorx = x\landx = x\land1 = x\lor0 = x\oplus0 = x.
    • x\oplus1 = x\rightarrow0 = x\sim0 = x\midx = x\downarrowx = \negx.
    • \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 logikahe:לוגיקה בוליאנית simple:Boolean algebra

Викия-сеть

Случайная вики