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

Известно, что любая логическая формула может быть выражена через три ранее рассмотренные логические операции, однако на практике часто используют еще две логические связки. Первая из них называется импликацией и служит для задания так называемых условных высказываний. В русском языке этой логической операции соответствуют фразы если..., то... или когда..., тогда... Импликация - двухместная операция: часть формулы до импликации называют основанием условного высказывания, а часть, расположенную за ней - следствием. В логических формулах импликация обозначается знаком ->. Операция A -> B определяет логическую функцию, тождественно совпадающую с функцией!A || B.

Пример

Дано сложное высказывание: "Если выглянет солнце, то станет тепло". Требуется записать его в виде логической формулы.

Обозначим через А простое высказывание "выглянет солнце", а через В - "станет тепло". Тогда логической формулой этого сложного высказывания будет импликация: A -> B.

Другой распространенной операцией является эквивалентность. Ее аналог в разговорной речи - фразы, подобные словосочетанию тогда и только тогда, когда... или если и только если... Для ее обозначения используется символ <-> или просто =. Мы будем использовать для обозначения эквивалентности обе эти формы. Отметим, что логическая формула A <-> B эквивалентна формуле (A -> B) && (B -> A).

Пример

Дано сложное высказывание: "В зачетную книжку выставляется оценка за экзамен тогда и только тогда, когда он сдан". Нужно преобразовать высказывание к логической формуле. Обозначим через А простое высказывание "В зачетную книжку выставляется оценка за экзамен", а через В - "Экзамен сдан". Тогда логическая формула сложного высказывания запишется в виде A <-> B.

Приведем таблицу истинности, задающую операции импликации и эквивалентности:

A B A -> B A <-> B

T T T T

T F F F

F T T F

F F T T

Рассмотренные нами логические операции в порядке убывания приоритетов располагаются так: отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность.

Преобразование логических выражений

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

Следующие формулы преобразований дополняют сформулированные выше законы булевой алгебры и позволяют приводить формулы к нормальной форме.!(!A) = A.

!(A && B) =!A ||!B.

!(A || B) =!A &&!B.

!(A -> B) = A &&!B.

A -> B =!A || B.

A <-> B = (A && B) || (!A &&!B) =(!A || B) && (A ||!B).

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

Пример

Следователь допрашивал четырех гангстеров по делу о похищении автомобиля.

Джек сказал: "Если Том не угонял автомобиля, то его угнал Боб".

Боб сказал: "Если Джек не угонял автомобиля, то его угнал Том".

Фред сказал: "Если Том не угонял автомобиля, то его угнал Джек".

Том сказал: "Если Боб не угонял автомобиля, то его угнал я".

Удалось выяснить, что Боб солгал, а Том сказал правду. Правдивы ли показания Джека и Фреда? Кто угнал машину?

Решение

Определим следующие простые высказывания: А - "машину угнал Боб"; В - "машину угнал Том";

С - "машину угнал Джек"; D - "машину угнал Фред".

Запишем (и сразу упростим) сложные высказывания, выражающие приведенные факты:

(1)!B -> A =!(!B) || A = B || A (истинность неизвестна);

(2)!C -> B =!(!C) || B = C || B = F (высказывание ложно);

(3)!B -> C =!(!B) || C = B || C = C || B (истинность неизвестна);

(4)!A -> B =!(!A) || B = A || B = T (высказывание истинно).

Заметим, что после упрощения высказывание (3) совпало с высказыванием (2), которое ложно. Таким образом, высказывание (3), произнесенное Фредом, также ложно.

Из ложности высказывания (2) следует ложность каждого дизъюнкта, входящего в него, т. е. C = F и B = F.

Подставив найденное значение B в высказывание (4) получаем A || B = A || F = T, что возможно лишь если A = T, т. е. машину угнал Боб.

Рассмотрим высказывание Джека (1): B || A = F || T = T - оно истинно.

Итак, Джек сказал правду, а Фред соврал. Машину угнал Боб.

Пример

Кто из людей A, B, C и D играет, а кто не играет в шахматы, если известно следующее:

а) если А или В играет, то С не играет;

б) если В не играет, то играют С и D;

в) С играет.

Решение

Определим следующие простые высказывания: А - "А играет в шахматы"; В - "В играет в шахматы";

С - "С играет в шахматы"; D - "D играет в шахматы".

Запишем сложные высказывания, выражающие известные факты:

a) (A && B) ->!C;

б)!B -> C && D;

в) C.

Запишем произведение (конъюнкцию) указанных сложных высказываний. Так как все они истинны, то и произведение тоже истинно:

((A || B) ->!C) && (!B -> C && D) && C = T.

Упростив эту формулу, получим

!A &&!B && C && D = T.

Отсюда по свойствам конъюнкции получаем, A = F, B = F, C = T, D = T. Значит, в шахматы играют C и D, а A и B - не играют.

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

Пример

Упростим логическую формулу!((A || B) ->!(B || C)).

Решение!((A || B) ->!(B || C)) =

!(!(A || B) ||!(B || C)) =

!(!(A || B)) &&!(!(B || C)) =

(A || B) && (B || C) = { дистрибутивность операции ИЛИ }

(A || B) && B || (A || B) && C =

A && B || B || A && C || B && C =

B && (A || T) || C && (A && B) =

B || A && C || B && C =

B && (T || C) || A && C = B || A && C.

Задания

Упростите следующую логическую формулу и определите ее истинность:

(A -> B) && (B -> (C ||!A)) && (!D -> (A &&!C)) && (D -> A).

Определите значение формул:

1) ((C || B) -> B) && (A && B) -> B;

2) ((C || B) -> B) && (A || B) -> B.

В нарушении правил обмена валюты подозреваются четыре работника банка - A, B, C и D. Известно следующее:

a) Если A нарушил, то и B нарушил правила обмена валюты.

б) Если B нарушил, то и C нарушил или A не нарушал.

в) Если D не нарушил, то A нарушил, а C не нарушал.

г) Если D нарушил, то и A нарушил.

Кто из подозреваемых нарушил правила обмена валюты? Решите задачу с помощью логических операций.

Алеша, Боря и Гриша нашли в земле старинный сосуд. Рассматривая удивительную находку, каждый высказал по два предположения:

Алеша: "Это сосуд греческий и изготовлен в V веке".

Боря: "Это сосуд финикийский и изготовлен в III веке".

Гриша: "Это сосуд не греческий и изготовлен в IV веке".

Знакомый археолог определил, что каждый из них прав только в одном из двух предположений. Где и в каком веке изготовлен сосуд?

Дата добавления: 2014-01-20