Основные теоремы логического вывода

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

Формула R является логическим следствием формул F1,F2,…,Fk тогда и только тогда, когда импликация (F1&F2& …&Fk ® R) общезначима.

Необходимость. Пусть R является логическим следствием формулы F1F2 … Fk. Докажем общезначимость импликации. Если все формулы F1,F2,…,Fk истинны в некоторой интерпретации, то импликация также истинна, так как R является следствием из этого множества формул и истинна.. Если же в множестве этих формул хотя бы одна ложна, то импликация также истинна. Следовательно, импликация общезначима.

Достаточность. Пусть формула общезначима. Тогда для всякой интерпретации, в которой для всех формулы истинны, формула также истинна. А поскольку общезначимая, в этой конкретной интерпретации формула R также истинная в силу определения импликации.

Формула R является логическим следствием формул F1,F2,…,Fk тогда и только тогда, когда формула невыполнима.

Так как формула общезначима, то ее отрицание невыполнимо. По правилу де Моргана получаем доказательство.

Заметим, что такой способ доказательства проще, чем построение и анализ таблиц истинности.

Дата добавления: 2014-11-08; просмотров: 587; Нарушение авторских прав

Мы поможем в написании ваших работ!