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


         

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


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

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

!( !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 (высказывание истинно).



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