Теорема Гёделя о полноте

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Теоре́ма Гёделя о полноте́ исчисле́ния предика́тов является одной из фундаментальных теорем математической логики: она устанавливает однозначную связь между логической истинностью высказывания и его выводимостью в логике первого порядка. Впервые эта теорема была доказана Куртом Гёделем в 1929.

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


Иными словами, если \Phi - тождественно истинная формула исчисления предикатов, то \Phi доказуема в исчислении предикатов.[1]

Доказательство[править | править вики-текст]

Из тождественной истинности \Phi получаем, что множество \{\neg \Phi \} не имеет модели. Из теоремы о существовании модели следует, что \{\neg \Phi \} противоречиво, то есть \neg \Phi \vdash - теорема исчисления предикатов. По правилу вывода \frac{\Gamma, \neg \Phi \vdash}{\Gamma \vdash \Phi} получаем, что \Phi доказуема.[1]

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. 1 2 Ершов, 1987, с. 139

Литература[править | править вики-текст]