Викия

Математика

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

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Поделиться

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

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

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

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

Викия-сеть

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