Урок №21. Логические операции "импликация", "эквиваленция", "ислючающее ИЛИ". Таблицы истинности логических выражений.
Операция исключающее ИЛИ отличается от обычного ИЛИ только тем, что результат равен 0, если оба значения равны 1 (последняя строка в таблице истинности). То есть её результат — истина в том и только в том случае, когда два значения не равны (рис. 3.4).
Операции исключающее ИЛИ соответствует пословица «Либо пан, либо пропал», где выполнение обоих условий одновременно невозможно.
Исключающее ИЛИ в алгебре логики обозначается знаком ⊕, в языке Паскаль — словом хог (например, А хог В), а в языках С, Python, Java и Javascript — знаком ∧ (А ∧ В). Эту операцию можно представить через базовые операции (НЕ, И, ИЛИ) следующим образом:
Пока мы не можем вывести это равенство, но можем доказать его (или опровергнуть). Для этого достаточно для всех возможных комбинаций А и В вычислить значения выражения, стоящего в правой части равенства, и сравнить его со значением А ⊕ В для тех же исходных данных. Поскольку провести такие вычисления в уме достаточно сложно сначала вычислим значения ¬А, ¬В, ¬А • В и А • ¬В, а потом уже ¬А • В + А • ¬В. В таблице истинности появятся дополнительные столбцы для промежуточных результатов (рис. 3.5).
Легко видеть, что выражение ¬А • В + А • ¬В совпадает с А ⊕ В для всех возможных вариантов значений А и В. Это значит, что равенство доказано.
Возможен и другой вариант замены:
Докажите это равенство самостоятельно.
Мы часто используем логическую связку «если…, то», например: «Если пойдёт дождь, то я надену плащ» или «Если все стороны прямоугольника равны, то это квадрат». В логике эта связка называется импликацией (следованием, от лат. implicatio — сплетение, тесная связь) и обозначается стрелкой: А → В («если А) то В», «из А следует В»). Таблица истинности операции импликации показана на рис. 3.6.
Разобраться с импликацией будет легче, если мы рассмотрим конкретное высказывание, например такое: «Если хорошо работаешь, то получаешь большую зарплату». Обозначим буквами два простых высказывания: А — «Хорошо работаешь» и В — «Получаешь большую зарплату». Понятно, что если высказывание А → В истинно, то все, кто хорошо работают (А = 1), должны получать большую зарплату (Б = 1). Если же кто-то работает хорошо (А = 1), а получает мало (В = 0), то высказывание А → В ложно.
Лодыри и бездельники (А = 0) могут получать как маленькую (В = 0), так и большую зарплату (В = 1), это не нарушает истинность высказывания А → Б. Иногда, определяя импликацию, говорят так: из истины следует истина, а из лжи — что угодно. Это значит, что при ложном высказывании А высказывание В может быть как ложно, так и истинно.
Нужно обратить внимание на разницу между высказываниями вида «если А, то Б» в обычной жизни и в алгебре логики. В быту мы чаще всего имеем в виду, что существует причинно-следственная связь между А и Б, т. е. именно А вызывает Б. Алгебра логики не устанавливает взаимосвязь явлений; истинность высказывания А → Б говорит только о возможности такой связи. Например, с точки зрения алгебры логики может быть истинным высказывание «если Вася — студент, то Петя — лыжник».
Импликация чаще всего используется при решении логических задач. Например, формулировку вида «если А, то Б» можно записать как А → Б = 1.
Для импликации (в отличие от других изученных ранее операций с двумя переменными) не действует переместительный закон: если в записи А → Б поменять местами А и Б, то результат изменится: А → Б ≠ В → А. Внешне это видно по стрелке, которая указывает « направление ».
Импликацию можно заменить на выражение, использующее только базовые операции (здесь — только НЕ и ИЛИ):
А → B = ¬А + B.
Доказать это равенство вы уже можете самостоятельно.
Эквиваленция (её также называют эквивалентность, равносильность, логическое равенство) — это логическая операция, которая соответствует связке «тогда и только тогда». Высказывание А ↔ В (используются также обозначения А ≡ В и А ~ В) истинно в том и только в том случае, когда А и В равны (рис. 3.7).
Возможно, вы заметили, что эквиваленция — это обратная операция для исключающего ИЛИ (проверьте по таблицам истинности):
.
Здесь черта сверху, охватывающая всё выражение в правой части равенства, означает отрицание (инверсию), которое применяется к результату вычисления выражения А ⊕ В, а не к отдельным высказываниям.
Можно заменить эквиваленцию выражениями, которые включают только базовые логические операции:
Эти равенства вы можете доказать (или опровергнуть) самостоятельно.
Любую логическую функцию можно задать с помощью таблицы истинности, которая показывает, чему равно значение логического выражения при всех возможных комбинациях значений исходных переменных. Построим таблицу истинности для выражения
X = А и не В или не А и Б,
которое можно также записать в виде
Сколько строк в таблице истинности выражения с двумя переменными?
Будем вычислять выражение по частям: добавим в таблицу истинности дополнительные столбцы А • ¬В и ¬А • В, а потом выполним операцию ИЛИ с этими значениями (рис. 2.18).
Из этой таблицы истинности видно, что при некоторых значениях переменных значение X истинно, а при некоторых — ложно. Такие выражения называют вычислимыми.
Высказывание «Вася — школьник или он не учится в школе» всегда истинно (для любого Васи). Выражение, истинное при любых значениях переменных, называется тождественно истинным или тавтологией.
Высказывание «Сегодня безветрие, и дует сильный ветер» никогда не может быть истинным. Соответствующее логическое выражение всегда ложно, оно называется тождественно ложным или противоречием.
Если два выражения принимают одинаковые значения при всех значениях переменных, они называются равносильными или тождественно равными. Равносильные выражения определяют одну и ту же логическую функцию, т. е. при одинаковых исходных данных приводят к одинаковым результатам.