Математическая логика и теория алгоритмов

Итак, из случаев 1) и 2) следует, что применение правил вывода MP и Gen сохраняет то свойство формул, что применение к ним функ­ ции h снова приводит к тавтологии. Теперь докажем, что если А - теорема, то h { A ) - тавтология. Пусть формула А есть теорема теории Кх, т.е. существует ее вывод в К\. где Вп=А и каждое из 5, {1< i< п) является либо аксиомой, либо непо­ средственным следствием по MP либо по Gen из предыдущих формул этой последовательности. Тогда h{B,) является тавтологией для любо­ го г, в частности, тавтология h{B „)=h(B). Если бы существовала формула В ъ К\ такая, что |- В и В (выводимо В и 1В ) , то по доказанному h { B ) и h(] 5)=1 h{B) были бы тавтологиями, что невозможно. Значит, не существует формулы В та­ кой, что \-В тл [-15, следовательно, всякое исчисление предикатов первого порядка непротиворечиво. Что и требовалось доказать. О полноте исчисления предикатов первого порядка (теории К]). Как было ранее замечено, в дедуктивных теориях вводят различ­ ные понятия полноты. Исчисление предикатов первого порядка назы­ вается полным в широкомсмысле, если каждая логическая общезна­ чимая формула является теоремой. Можно доказать, что во всяком исчислении предикатов первого порядка каждая теорема является логически общезначимой формулой. Кроме того, можно доказать, что ка­ ждая логически общезначимая формула из Ki является теоремой в Ki Следовательно, во всяком исчислении пре­ дикатов первого порядка теоремами явля­ ются те и только те формулы, которые логически общезначимы (теорема Гёделя о полноте). Таким образом, исчисление предикатов первого порядка (теория К { ) является полной в широком смысле теорией. Теория К считается полной в узком смысле, если для любой замкнутой формулы^ доказуемо А либо I a . 175