Алгебра высказываний

Основные понятия алгебры логики

Высказывание – это повествовательное предложение, которое либо истинно, либо ложно. В высказывании говорится о единственном событии. Высказывание «Москва – столица России» является истинным, а высказывание «Волга впадает в Черное море» - ложным.

Не всякое предложение является высказыванием. К высказываниям не относятся вопросительные и восклицательные предложения; предложения, в которых не может быть единого мнения о том, истинны они или ложны.

Из двух предложений можно образовать новые предложения с помощью союзов: «И», «ИЛИ», «ЕСЛИ… ТО…», «ТОГДА И ТОЛЬКО ТОГДА, КОГДА», также с помощью частицы «НЕ» или словосочетания «НЕВЕРНО, ЧТО», которые в алгебре высказываний называются логическими связками.

Высказывания обозначаются большими буквами латинского алфавита. Высказывания принимают значения «истина» (1) или «ложь» (0).

В алгебре высказываний определены действия над высказываниями, в результате выполнения которых получают новые высказывания.

Пусть А и В простые высказывания.

Инверсией (отрицанием) называется логическая операция, проводимая с одним высказыванием, с помощью связки «НЕ ВЕРНО, ЧТО». Обозначения инверсии: (подчеркивание сверху), NOT, НЕ. А читается, как «неверно, что А».

Конъюнкцией (логическим умножением) называется операция объединения простых высказываний в одно с помощью союза «И». Обозначения конъюнкции: *, Ù, &, AND, И. А & В читается, как «А и В».

Дизъюнкцией (логическим сложением) называется операция объединения простых высказываний в одно с помощью союза ИЛИ. Обозначение дизъюнкции6 +, Ú, OR, ИЛИ. А Ú В читается, как «А или В».

Импликацией (логическим следованием) называется операция объединения двух простых высказываний в одно с помощью союза «ЕСЛИ …, ТО…». Обозначение импликации: Þ. А Þ В читается, как «если А, то В» или «из А следует В».

Эквивалентностью (логическим равенством) называется операция объединения двух простых высказываний в одно с помощью союза «ТОГДА И ТОЛЬКО ТОГДА, КОГДА…». Обозначение эквивалентности: Û. А Û В читается, как «А эквивалентно В тогда и только тогда, когда из А следует В и из В следует А».

Неэквивалентностью (логическим неравенством, исключающим ИЛИ) называется операция объединения двух простых высказываний в одно с помощью союза «ТОГДА и ТОЛЬКО ТОГДА, КОГДА…». Обозначения: Å, XOR. А Å В читается, как «А не эквивалентно В тогда и только тогда, когда из А не следует В, а из В не следует А».

При определении значения логического выражения учитывают старшинство или приоритет логических операций: сначала выполняется инверсия, затем конъюнкция, а потом дизъюнкция. Для изменения указанного порядка используют скобки.