Практическая информатика



         

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


Заметим, что после упрощения высказывание (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 && 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.




Содержание  Назад  Вперед