Полнота теории L

Справедлива теорема о полноте L. Если формула Ф теории L является тавтологией, то она – теорема теории L.

Доказательство этой теоремы основывается на лемме об условной выводимости:

Пусть Ф – формула теории L, содержащая переменные – булев вектор, т.е. есть И или Л для каждого . Тогда , где – истинное значение формулы Ф при .

Напомним, что означает А, а .

Доказательство леммы приведено в [2].

Так как Ф – тавтология, то для любого булева вектора – И, . Полагая – И, а затем – Л, получим, в частности, и . Воспользовавшись теоремой о дедукции и утверждением (ж) леммы 2 (п.4.1) в виде , получим . Поступая таким же образом и далее, отбросим последовательно все допущения и придем к тому, что .

Следствие о выводимости тавтологий логики высказываний. Пусть – формула алгебры высказываний, которая является сокращением (см. определения Д1-Д3 п.4.1), формулы Ф – теории L. Тогда является тавтологией тогда и только тогда, когда Ф есть теорема теории L.

Как уже отмечалось, определения (Д1-Д3) составлены из пар равносильных формул. Поэтому в силу теоремы об эквивалентной замене (п.2.6) , т.е. Ф является или не является тавтологией вместе с . Остается сослаться на теорему о полноте L и теорему общезначимости теории L.

Следствие о выводимости из допущений. Пусть , Ф - формулы теории L. Утверждение имеет место тогда и только тогда, когда (т.е. формула Ф выводима из допущений тогда и только тогда, когда она является их логическим следствием).

Действительно, рассматриваемые соотношения можно переписать в виде (по теореме о дедукции) и (по определению логического следствия). Легко убедится, например, методом «от противного», , поэтому последнее соотношение можно переписать в виде , и утверждение вытекает из следствия о выводимости тавтологий алгебры высказываний.

Следствие о выводимой эквивалентности. Формулы и Ф теории L равносильны тогда и только тогда, когда они выводимо эквиваленты, т.е. и .

Упражнения

1. Доказать теоремы теории L:

а) ;

б) ;

в) .

ТЕМА V

Дата добавления: 2015-11-14