Основные правила вывода исчисления предикатов.

Правила вывода

1) «не разобрал слово» как в ИВ

2) Правило обобщения: то

3) Правило введения квантора существования: C(x) – содержит свободные вхождения х, F- не содержит.

9. Производные правила вывода в исчислении предикатов: правила переименования связанных переменных, правило связывания квантором.

Правило переименования связанных переменных

1)

2)

F(x) не содержит свободных вхождений y, но содержит свободные вхождения х, ни одно из которых не входит в область действия квантора по у.

Доказательство:

1) – гипотеза

2) По аксиоме (Р1) справедлива формула

3) К шагу 2 применим правило обобщения

4) MP для (1) и (3):

Для квантора существования доказать самостоятельно!

Правило связывания кванторов.

_K

1) F(x) – гипотеза по условию

2) По т.2 ИВ _L , то есть формула доказуема для любого В, в том числе и для доказуемов формуле В. Значит _K

3) По правилу обощения , B не содержит свободных вхождений х.

4) Из (3) по правилу заключения МР (для В и ) следует доказуемость _K .