Импликация и эквивалентность

Основные законы алгебры логики

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

Законы де Моргана. Отрицание дизъюнкции (логическое сложение) эквивалентно конъюнкции (логическое умножение) отрицаний. Отрицание конъюнкции эквивалентно дизъюнкции отрицаний. Эти свойства иногда выражают словами: «конъюнкция двойственна дизъюнкции».

Операция переменной с её инверсией. Закон непротиворечия: Высказывание не может быть одновременно истинным и ложным. Логическое произведение высказывания и его отрицания ложно.

Любая логическая формула может быть выражена через три базовые логические операции (ранее рассмотренные), однако на практике часто используют еще две логические связки. Первая из них называется импликацией (лат. implico – тесно связаны) и служит для задания так называемых условных высказываний. В русском языке этой логической операции соответствуют фразы если..., то... или когда..., тогда...

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

Операция A→B определяет логическую функцию, тождественно совпадающую с функцией

А ∨ В.

Пример 1. Сложное высказывание: «Если на улице дождь, то на улице мокро». Обозначим через А простое высказывание «на улице дождь», а через В – «на улице мокро». Тогда логической формулой этого сложного высказывания будет импликация: A→B.

Пример 2. Если число Х делится на 4, то оно делится на 2. Это означает, что высказывание (Х делится на 4) → (Х делится на 2) истинно при всех Х.

Другой распространенной операцией является эквивалентность (равнозначность, равносильность). Ее аналог в разговорной речи – фразы, подобные словосочетанию тогда и только тогда, когда... или если и только если... Для ее обозначения используется символ ↔ (или =, или ~).

Эквиваленцию A↔B можно выразить через отрицание, дизъюнкцию и конъюнкцию:

(А ∨ В) & (A ∨ B)

Пример 1. Сложное высказывание: «В зачетную книжку выставляется оценка за экзамен тогда и только тогда, когда он сдан». Обозначим через А простое высказывание «В зачетную книжку выставляется оценка за экзамен», а через В – «Экзамен сдан». Тогда логическая формула сложного высказывания запишется в виде: A↔B.

Пример 2. Многоугольник является вписанным в круг, если его вершины лежат на окружности.

Дата добавления: 2014-11-06