Доказательство полноты исчисления высказываний

Семь теорем.

2) . Запишем аксиому а3 в следующем виде: вместо В подставим формулу А, а вместо А подставим

1. примем двойное отрицание А за гипотезу, тогда по предположению выводится

2. Теперь из пунктов 1 и 2 выводится правая часть формулы

3. (теорема 1)

4. следовательно по т1 и 3 выводится

5. по теореме дедукции

3) Запишем аксиому а3, подставив вместо В , тогда а3=

1. по 2) и 1 выводится правая часть

2.

3. принимаем А за гипотезу, тогда по пр. из пунктов 2, 3 по МР

4.

5.

4) запишем третью аксиому а3

1.

2.

3.

4. (пр.)

5.

6.

7. применяя ТД второй раз получаем

5) запишем аксиому а3

1.

2.

3.

4.

5.

6. применяя ТД дважды, получаем требуемую формулу

6)

1. Запишем предыдущую теорему в виде гипотеза

Примем за гипотезу, и выведем из нее посылку . Тогда

вывод теоремы непосредственно следует из теоремы дедукции и теоремы 5.

Чтобы реализовать указанную цель, принимаем за гипотезу.

Тогда

2. ,

3

4 из пунктов 2,3 получаем , |-

Тогда цель выполнима по теореме дедукции из предыдущегопункта 4.

7) запишем а3

1.

2. запишем 6) в следующем виде:

3. по МР, следовательно по ТД из

4.

5. по ТД

8) запишем а3

1.

2. покажем предыдущие

3.

4.

5. , таким образом второй пункт доказан

6.

7.

8. ТД первый раз

ТД второй раз

Осталось показать, что всякая тавтология выводима в исчислении высказываний.

Лемма:

Пусть - формула от переменных над связками .

Пусть набор значений переменных. .

Покажем из гипотез ½¾

Здесь если ; если

если ; , если

Доказательство индукцией по числу связок в формуле .

Число связок равно 0 : ½¾ ; ½¾ Утверждение справедливо.

Пусть утверждение справедливо для любых формул с не более чем связками ; .

Покажем справедливость для F с i +1 связкой

1. F₁ и F₂ – формулы с не более чем i связками

Рассмотрим произвольный набор переменных .

А)

Пусть гипотезы соответствующие набору

По индуктивному предположению:

1. ½¾ ù ;

2. ½¾ ù ;

а1. ù (ù ù )

1. а1. ½¾ ù ù

5. 1. (ù ù ) ½¾

½¾ что и требовалось

В)

1. ½¾ ù ;

2. ½¾ ;

4. ù ½¾ что и требовалось

С)

1. ½¾ ;

2. ½¾ ;

а1. ½¾ .

D)

1. ½¾ ;

2. ½¾ ù ;

7.. (ù ù

что и требовалось

2.

a) это и есть F^’

b) это и есть F’

Утверждение:

Любая тавтология выводима.

Рассмотрим два произвольных набора значений переменных отличающихся последней компонентой.

Пусть гипотезы которые соответствуют этим наборам будут и , тогда в силу предыдущей леммы и того, что F тавтология имеем: ; ; то:

По восьмой теореме имеем . В силу того что произвольно, точно так же можно избавиться от .

Пока не избавимся от всех гипотез и придем к .

Упражнения:

Доказать:

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

Дата добавления: 2017-01-13