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

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

Определение

Базовыми элементами, которыми оперирует алгебра логики, являются высказывания. Высказывания строятся над множеством \{B, ¬, , , 0, 1\}, где B — непустое множество, над элементами которого определены три операции: ¬ отрицание (унарная операция), конъюнкция (бинарная), дизъюнкция (бинарная), а логический ноль 0 и логическая единица 1 — константы. Так же используются названия

  • Дизъюнкт — пропозициональная формула, являющаяся дизъюнкцией одного или более литералов (например x1¬x2x4).
  • Конъюнкт — пропозициональная формула, являющаяся конъюнкцией одного или более литералов (например x1¬x2x4).
Унарная операция отрицания в тексте формул оформляется либо в виде значка перед операндом (¬x) либо в виде черты над операндом (x¯), что компактнее, но в целом менее заметно.

Аксиомы


  1. x¯¯=x, инволютивность отрицания, закон снятия двойного отрицания
  2. xx¯=1
  3.  x1=1
  4.  xx=x
  5.  x0=x
  6.  xx¯=0
  7.  xx=x
  8.  x0=0
  9.  x1=x

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

Простейший и наиболее широко применяемый пример такой алгебраической системы строится с использованием множества B, состоящего всего из двух элементов: B = \{ Ложь, Истина \} Как правило, в математических выражениях Ложь отождествляется с логическим нулём, а Истина — с логической единицей, а операции отрицания (НЕ), конъюнкции (И) и дизъюнкции (ИЛИ) определяются в привычном нам понимании. Легко показать, что на данном множестве B можно задать четыре унарные и шестнадцать бинарных отношений и все они могут быть получены через суперпозицию трёх выбранных операций. Опираясь на этот математический инструментарий, логика высказываний изучает высказывания и предикаты. Также вводятся дополнительные операции, такие как эквиваленция («тогда и только тогда, когда»), импликация («следовательно»), сложение по модулю два («исключающее или»), штрих Шеффера , стрелка Пирса и другие. Логика высказываний послужила основным математическим инструментом при создании компьютеров. Она легко преобразуется в битовую логику: истинность высказывания обозначается одним битом (0 — ЛОЖЬ, 1 — ИСТИНА); тогда операция ¬ приобретает смысл вычитания из единицы;  — немодульного сложения; \& — умножения;  — равенства;  — в буквальном смысле сложения по модулю 2 (исключающее Или — XOR);  — непревосходства суммы над 1 (то есть A B = (A + B) \textless= 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):
    • xx¯=x0=xx=0.
    • xx¯=x1=xx=xx=1.
    • xx=xx=x1=x0=x0=x.
    • x1=x0=x0=xx=xx=x¯.
    • x¯¯=x, инволютивность отрицания, закон снятия двойного отрицания.

  8. Другие (2):
    • xy=xy¯x¯y=(xy)(x¯y¯).
    • xy=xy¯=1xy=xyx¯y¯=(xy¯)(x¯y).
    • xy=x¯y=xyx1.
    • xy=xyxy.

  9. Другие (3) (Дополнение законов де Моргана):
    • xy=xy¯=x¯y¯.
    • xy=xy¯=x¯y¯.
Существуют методы упрощения логической функции: например, Карта Карно, метод Куайна - Мак-Класки

История

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