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

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

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

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

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

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

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

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

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

Бинарные логические операции x y f1 () f2 () f3 () f4 () f5 () f6 () f7 () f8 () 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 = xy = xy = min(x, y)), f2(x, y) — дизъюнкция (f2(x, y) = xy = max(x, y)), f3(x, y) — эквивалентность (f3(x, y) = xy = xy = xy), f4(x, y) — сумма по модулю два (f4(x, y) = xy), f5(x, y) — импликация от y к x (f5(x, y) = xy = xy), f6(x, y) — импликация от x к y (f6(x, y) = xy = xy), f7(x, y) — стрелка Пи́рса = функция Да́ггера = функция Ве́бба («антидизъюнкция») (f7(x, y) = xy). f8(x, y) — штрих Ше́ффера («антиконъюнкция») (f8(x, y) = xy), f9(x, y), f10(x, y) — инверсии импликаций f5 и f6, f11—f14 — функции только одного аргумента, f15, f16 — тождества. Все вышеперечисленные функции называются логическими связками.

Логические операции Править

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

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

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

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

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

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

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

1. Коммутативность: xy = yx, {&, }.
2. Идемпотентность: xx = x, {&, }.
3. Ассоциативность: (xy)z = x(yz), {&, }.
4. Дистрибутивность конъюнкций и дизъюнкции относительно дизъюнкции, конъюнкции и суммы по модулю два соответственно:
   • x(yz) = (xy)(xz),
   • x(yz) = (xy)(xz),
   • x(yz) = (xy)(xz).
5. Законы де Мо́ргана:
   • (xy) = ( x)(y),
   • (xy) = ( x)(y).
6. Законы поглощения:
   • x(xy) = x,
   • x(xy) = x.
7. Другие (1):
   • x(x) = x0 = xx = 0.
   • x(x) = x1 = xx = xx = 1.
   • xx = xx = x1 = x0 = x0 = x.
   • x1 = x0 = x0 = xx = xx = x.
   • .
8. Другие (2):
   • = = .
   • = = = .
   • = = .
9. Другие (3) (Дополнение законов де Мо́ргана):
   • = = .
   • = = .

История Править

Своим существованием наука обязана английскому математику Джорджу Булю, который исследовал логику высказываний. Первый в России курс по алгебре логики был прочитан П. С. Порецким в Казанском государственном университетеcs:Booleova logikahe:לוגיקה בוליאנית simple:Boolean algebra zh:布尔逻辑