Теорема 3.1. (теорема о дедукции)

Теорема о дедукции. Полнота ИВ.

Если Г, В+А, то Г+ВА, где Г — набор некоторых формул Г ={F₁F₂,...,F_n}.

Следствие 3.1. Тогда и только тогда F₁F₂,...,F_n +A, когда

+ F₁ (F2... (F_n-1 (F_n A))...)

Доказательство. Пусть F₁F₂,...,F_n +A. Тогда, применяя теорему о дедукции, имеем F₁F₂,...,F_n-1 +F_nA. Аналогично F₁F₂,...,F_n-2 +F_n (F_nA), и т. д. Продолжая процесс необходимое число раз, получаем

+ F₁(F₂,,, (F_n-1(F_nA))...)

Для доказательства достаточности предположим, что +В, где B= F₁(F₂,,, (-»(F_n-1(FnA))...). Воспользуемся теоремой из предыдущей главы F1+В. По правилу заключения получаем F₁+ (F₂...- (F_n-1(F_nA))...), Далее через n шагов имеем F₁F₂,...,F_n +A.

Таким образом, благодаря следствию З.1., проверка выводимости формулы А из формул F₁F₂,...,F_n, сводится к проверке доказуемости формулы

F₁(F₂,,, (F_n-1(F_nA))...)

Напомним, что формула А называется тождественно истинной (или тавтологией), если значение формулы А равно единице при любых наборах значений пропозициональных переменных. Следующая теорема сводит проверку доказуемости формулы к проверке ее тождественной истинности.

Теорема 3.2. (о полноте). Формула А доказуема тогда и только тогда, когда А тождественно истинна (тавтология): +А <=> А-тавтология.

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

Пример. Докажем, что Р+Р. По теореме о дедукции это равносильно тому, что +(РР). В свою очередь, по теореме о полноте, достаточно доказать, что (РР) тавтология. Составляя таблицу истинности для формулы (РР), убеждаемся, что (РР) тождественно истинна и, следовательно, доказуема.

Дата добавления: 2014-01-04