Открыть главное меню

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

Содержание

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

Базовыми элементами, которыми оперирует алгебра логики, являются высказывания.

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

  отрицание (унарная операция),
  конъюнкция (бинарная),
  дизъюнкция (бинарная),

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

Так же используются названия

Унарная операция отрицания в тексте формул оформляется либо в виде значка перед операндом ( ) либо в виде черты над операндом ( ), что компактнее, но в целом менее заметно.

АксиомыПравить

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

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

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

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

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

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

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

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

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

  1. Коммутативность:  .
  2. Идемпотентность:  .
  3. Ассоциативность:  .
  4. Дистрибутивность конъюнкций и дизъюнкции относительно дизъюнкции, конъюнкции и суммы по модулю два соответственно:
    •  ,
    •  ,
    •  .
  5. Законы де Мо́ргана:
    •  ,
    •  .
  6. Законы поглощения:
    •  ,
    •  .
  7. Другие (1):
    •  .
    •  .
    •  .
    •  .
    •  , инволютивность отрицания, закон снятия двойного отрицания.
  8. Другие (2):
    •  .
    •  .
    •  .
    •  .
  9. Другие (3) (Дополнение законов де Мо́ргана):
    •  .
    •  .

Существуют методы упрощения логической функции: например, Карта Карно, метод Куайна - Мак-Класки

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

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

См. такжеПравить

ПримечанияПравить

  1. Алгебра логики // Большая советская энциклопедия : [в 30 т.] / гл. ред. А. М. Прохоров. — 3-е изд. — М. : Советская энциклопедия, 1969—1978.