Логические следствия

Формула В именуется логическим следствием совокупности формул А ₁, А ₂,..., А_m, если каждый набор логических значений переменных, обращающий в истину все формулы А ₁, А ₂,..., А_m, обращает в истину и формулу В.

Теорема 1. Формула В является логическим следствием формул А ₁, А ₂ ,..., А_m тогда и только тогда, когда формула

А ₁ & А ₂ &...& А_m B

является теоремой ИВ.

Теорема 2. Формула В является логическим следствием формул А ₁, А ₂ ,..., А_m тогда и только тогда, когда формула

А ₁ & А ₂ &...& А_m & B

противоречива.

Из теорем 1 и 2 следует, что проверка, является ли формула B логическим следствием совокупности формул { А ₁, А ₂,..., А_m }, сводится к доказательству общезначимости или противоречивости некоторой ППФ.

Рассмотрим следующий пример.

Пример 2. Предполагается доказать справедливость следующих утверждений

1. Если Джон убийца и пистолет у него, то Смит пистолет обнаружит;

2. Если Смит обнаружит пистолет и передаст его Бобу, то Смит рапорт не напишет;

3. Если босс к делу причастен, то Смит передаст пистолет Бобу и напишет рапорт.

Требуется доказать, что если Джон убийца и пистолет унего, то босс к делу не причастен.

Запишем посылки 1 – 3 в символическом виде:

А & В C; (1)

C & D E; (2)

F D & E. (3)

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

А & В F. (4)

Покажем, что из истинности всех посылок следует истинность заключения, т.е. что утверждение (4) является логическим следствием утверждений (1) – (3).

Совокупность посылок представляем в виде формулы

(А & В C)&(C & D E)&(F D & E).

Эта формула эквивалентна следующей КНФ:

K ₁=( А В C) & ( C D E)&( F D) &( F E).

Формулу (4) также представим в виде КНФ:

K ₂=( А В F).

Согласно теореме 2, формула (4) является логическим следствием формул (1) – (3) тогда и только тогда, когда формула K ₁& K ₂ противоречива. Имеем

K ₁& K ₂=( А В C) & ( C D E)&( F D) &( F E)& A & B & F =

A & B & F & C &( D E)& D & E.

Противоречивость последней формулы очевидна, ибо три дизъюнкта, ( D E), D и Е, одновременно не могут быть истинными. Таким образом, заключение (4) действительно вытекает из утверждений (1)- (3), является их логическим следствием.

Далее общезначимые формулы будем обозначать символом, а противоречивые – символом ÿ. Какочевидно, A A = и A & A =ÿ.

Как известно, проблема определения по КНФ, является ли она выполнимой (непротиворечивой), относится к числу NP -полных. В предположении Р NР полиномиальных по временной вычислительной сложности (числу выполняемых элементарных операций) алгоритмов решения этой проблемы не существует. Выполнимость КНФ от n переменных может быть определена путем последовательного тестирования всех наборов логических значений этих переменных (общее число наборов равно 2 ⁿ).

Практика показала, что достаточно часто эффективным средством определения противоречивости КНФ является принцип резолюции.

Дата добавления: 2015-06-27