Teorema completității lui Godel

Teorema lui Gödel privind completitudinea calculului predicatului este una dintre teoremele fundamentale ale logicii matematice : stabilește o relație fără ambiguitate între adevărul logic al unui enunț și deductibilitatea acestuia în logica de ordinul întâi . Această teoremă a fost demonstrată pentru prima dată de Kurt Gödel în 1929 .

O formulă este derivabilă în calculul predicatului de ordinul întâi dacă și numai dacă este validă (adevărată în orice interpretare pentru orice substituție ).

Cu alte cuvinte, dacă este o formulă identică adevărată a calculului predicatului, atunci este demonstrabilă în calculul predicatului. [unu] $\Phi$ $\Phi$

Dovada

Din adevărul identic rezultă că setul nu are model . Din teorema existenței modelului rezultă, care este contradictorie, adică teorema de calcul predicat. Prin regula de inferență , obținem că este demonstrabil. [unu] $\Phi$ $\{\neg \Phi \}$ $\{\neg \Phi \}$ $\neg \Phi \vdash$ ${\frac {\Gamma ,\neg \Phi \vdash }{\Gamma \vdash \Phi ))$ $\Phi$

Vezi și

Note

↑ 1 2 Ershov, 1987 , p. 139.

Literatură

Ershov Yu.L. , Paliutin E.A. Logica matematică. — M .: Nauka, 1987. — 336 p.