Математическая логика
Алгебра логики (определение и основные логические операции).
Алгебра логики (алгебра высказываний) — раздел математической логики, в котором изучаются логические операции над высказываниями[1]. Чаще всего предполагается, что высказывания могут быть только истинными или ложными, то есть используется так называемая бинарная или двоичная логика, в отличие от, например, троичной логики.
Логические операции
Простейший и наиболее широко применяемый пример такой алгебраической системы строится с использованием множества B, состоящего всего из двух элементов:
B = { Ложь, Истина }
Как правило, в математических выражениях Ложь отождествляется с логическим нулём, а Истина — с логической единицей, а операции отрицания (НЕ), конъюнкции (И) и дизъюнкции (ИЛИ) определяются в привычном нам понимании. Легко показать[ неопределённость ], что на данном множестве B можно задать четыре унарные и шестнадцать бинарных отношений и все они могут быть получены через суперпозицию трёх выбранных операций.
Свойства основных логических операций
1. Коммутативность: x 
y = y x, 
{&, 
}.
2. Идемпотентность: x x = x, {&, 
}.
3. Ассоциативность: (x y) z = x (y z), {&, 
}.
4. Дистрибутивность конъюнкций и дизъюнкции относительно дизъюнкции, конъюнкции и суммы по модулю два соответственно:
· 
,
· 
,
· 
.
5. Законы де Мо́ргана:
· 
,
· 
.
6. Законы поглощения:
· 
,
· 
.
7. Другие (1):
· 
.
· 
.
· 
.
· 
.
· 
, инволютивность отрицания, закон снятия двойного отрицания.
8. Другие (2):
· 
.
· 
.
· 
.
· 
.
9. Другие (3) (Дополнение законов де Мо́ргана):
· 
.
· 
.
Существуют методы упрощения логической функции: например, Карта Карно, метод Куайна - Мак-Класки
Логическая операция Штрих Шеффера
Штрих Шеффера, обычно обозначаемый |, эквивалентен операции НЕ-И и задаётся следующей таблицей истинности:
| X | Y | X|Y |
Таким образом, высказывание X | Y означает, что X и Y несовместны, т.е. не являются истинными одновременно. От перемены мест операндов результат операции не изменяется.
Штрих Шеффера, как и стрелка Пирса, образует базис для пространства булевых функций от двух переменных. То есть используя только штрих Шеффера можно построить остальные операции. Например,
— отрицание
— дизъюнкция
— конъюнкция
— константа 1
Логическая операция Стрелка Пирса
Стрелка Пирса, обычно обозначаемая ↓, эквивалентна операции НЕ-ИЛИ и задаётся следующей таблицей истинности:
| X | Y | X ↓ Y |
Таким образом, высказывание «X ↓ Y» означает «ни X, ни Y». От перемены мест операндов результат операции не изменяется.
Стрелка Пирса, как и Штрих Шеффера, образует базис для пространства булевых функций от двух переменных. Это означает, что, используя только стрелку Пирса, можно построить все остальные логические операции, например:
— отрицание
— конъюнкция
— дизъюнкция
—импликация
