Табличный способ определения истинности сложного выражения имеет ограниченное применение, так как при увеличении числа логических переменных приходится перебирать слишком много вариантов. В таких случаях используют способ приведения формул к нормальной форме. Формула имеет нормальную форму, если в ней отсутствуют знаки эквивалентности, импликации и двойного отрицания, а все знаки отрицания относятся только к переменным, а не к выражениям.
Следующие формулы преобразований дополняют сформулированные выше законы булевой алгебры и позволяют приводить формулы к нормальной форме.
| !( !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 = 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 веке".
Знакомый археолог определил, что каждый из них прав только в одном из двух предположений. Где и в каком веке изготовлен сосуд?