Логическая операция Стрелка Пирса

Математическая логика

Алгебра логики (определение и основные логические операции).

Алгебра логики (алгебра высказываний) — раздел математической логики, в котором изучаются логические операции над высказываниями^[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». От перемены мест операндов результат операции не изменяется.

Стрелка Пирса, как и Штрих Шеффера, образует базис для пространства булевых функций от двух переменных. Это означает, что, используя только стрелку Пирса, можно построить все остальные логические операции, например:

— отрицание

— конъюнкция

— дизъюнкция

—импликация