Проблема разрешимости и минимизация формул логики

 

Очень большая группа логических задач связана с проблемой разрешимости, то есть с решением вопроса о том, к какому классу логических формул (тавтологий, тождественно-ложных, нейтральных) принадлежит данная формула логики.

В логике высказываний используется два основных способа разрешения:

1) табличный способ определения формул логики;

2) приведение к нормальным логическим формам и последующая минимизация формулы.

 

В качестве примера проверим корректность следующего рассуждения:

«Если команда “Спартак” выиграет следующую игру, а “Зенит” сыграет вничью или потерпит поражение, и “Торпедо” потерпит поражение, то “Спартак” выходит в финал. Но “Торпедо” одержало победу. Следовательно, команда “Спартак” в финал не вышла».

Логическая формула, соответствующая этому рассуждению (механизм ее составления разобран выше) выглядит следующим образом:

((pÙ(q Ú r) Ù s)®t)Ù )®

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

Удалим знаки импликации и строгой дизъюнкции согласно законам (1) и (6):

(p (q + r) ( + ) s + t) + .

Применим к полученной формуле законы де Моргана (32) и (33):

( + (q + r) + ( + ) + + ) + =

 

+ (q + r) + ( + ) + + t + + =

 

( (q + r) ( + ) ) + +

 

Воспользуемся теперь законом двойного отрицания (31):

(p (q + r) ( + ) s ) + s +

Используя закон поглощения (24) окончательно получаем:

s + = t ® s

Полученная формула, очевидно, является нейтральной, следовательно, приведенное рассуждение некорректно.

 

Рассмотрим пример другого рассуждения.

«Если Иванов сдает экзамен по логике, то Петров сдает зачет по философии. Иванов сдает экзамен по логике или экзамен по истории. Если Иванов сдает экзамен по истории, то Сидоров сдает экзамен по анатомии. Но Сидоров не сдает экзамен по анатомии. Следовательно, Петров сдает зачет по философии».

Проверим корректность этого рассуждения. Логическая формализация позволяет представить его в виде следующей формулы:

((p ® q) Ù (p Ú r) Ù (r ® s) Ù ) ® q

Воспользуемся той же процедурой, что и в предыдущем случае.

Удаляем знаки импликации:

 

(( + q) (p + r) ( + s) ) + q

Применяем законы де Моргана и закон двойного отрицания:

 

( + q) + (p + r) + ( + s) + + q =

_

( ) + ( ) + ( ) + s + q =

p + + r + s + q

Воспользуемся законом дистрибутивности (22). Тогда в нашей формуле следует произвести эквивалентные замены:

q + p = (q + p) (q + )

s + r = (s + r) (s + )

Получаем:

(q + p) (q + ) + (s + r) (s ) + ( )

Используем закон исключения третьего (10):

((q + p) И) + ((s + r) И) +

 

 

Исключим логическую константу И в соответствии с законом (11):

q + p + s + r + Ù

Используя закон дистрибутивности (22), получаем:

q + p + s + (r + ) (r + )

В соответствии с законом исключения третьего и исключения констант имеем:

q + p + s + r +

Согласно закону коммутативности (18), порядок, в котором осуществляется операция дизъюнкции, не влияет на логическое значение формулы, поэтому, переставив дизъюнкты, получаем:

q + s + r + p + = q + s + r + И = И

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