Matematická logika Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Matematická logika Materiály ke kurzu MA007 Poslední modifikace: 29. září 2009 Antonín Kučera http://www.fi.muni.cz/usr/kucera/teaching.html J n ffl - = s Matematická logika Logika. Antonín Kučera Aristotelova logika Logický čtverec Sylogismy Bůh O Logika (z řeckého Aoyoc,) Booleova algebra logiky zkoumá způsob vyvozování Dva zákl. problémy y s. závěrů z předpokladů. Řešení 1. problému ^r ^^ Řešení 2. problému / Lidské uvažování \ O V běžné řeči se „logikou" Výroková logika Syntaxe / /^^\ \ označuje myšlenková cesta, Sémantika \ ( i -v \ \ která vedla k daným závěrům. Plnohodnotnost Logika Kompaktnost SystémX(^,-) \ \ J 1 O Logika nezkoumá lidské myšlení Korektnost \ \______/ / (psychologie) ani obecné hranice Úplnost lidského poznání (epistemologie). Predikátová ^k y logika Syntaxe ^^^ y^ o „Může všemohoucí Bůh stvořit Sémantika ---------------- kámen, který sám nedokáže Odvozovací systém Větao úplnosti uzvednout?" Větao neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. větao neúplnosti c : tJP - - & 29. září 2009 2/147 Matematická logika Antonín Kučera Logika. Neformální, formálni, matematická. Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti • Neformální logika studuje problematiku správné argumentace v přirozeném jazyce. • Formální logika definuje a studuje abstraktní odvozovací pravidla (tj. „formy úsudků"), jejichž platnost nezávisí na významu pojmů, které v nich vystupují. 9 Pojmem matematická logika se obvykle myslí dvě různé oblasti výzkumu: ■ aplikace poznatků z oblasti formální logiky na matematiku (např. snaha „vnořit" matematiku do logiky ve formě konečného systému axiomů a odvozovacích pravidel); □ aplikace matematických struktur a technik ve formální logice (např. teorie modelů, teorie důkazů, apod.) □ s ~ = ■= Matematická logika Antonín Kučera Aristotelova logika Uvod Aristotelova logika Logický čtverec Sylogismy ■ Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost SystémX(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Aristoteles (384-322 př. Kr.) Považován za zakladatele formální logiky. Zavedl a prozkoumal pojem sylogismu. Aristoteles zkoumal také pravdivostní módy a položil tak základy modálni logiky. □ g - = s Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Aristotelova logika. Logický čtverec. Nechť S a P jsou neprázdné vlastnosti. Aristoteles rozlišuje následující základní kategorická tvrzení: • A „všechna S jsou P" • E „žádná S nejsou P" • / „některá S jsou P" • O „některá S nejsou P" Mnemonika: Afflrmo—nEgO (tvrdím—popírám) □ s ~ = ■= Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,^) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Aristotelova logika. Logický čtverec. (2) A a O jsou kontradiktoricka, tj. nemohou být současně pravdivá ani současně nepravdivá. / a E jsou rovněž kontradiktoricka. A a E jsou kontrární, tj. mohou být současně nepravdivá ale ne současně pravdivá. / a O jsou subkontrární, tj. mohou být současně pravdivá ale ne současně nepravdivá. /je subalterní (podřízené) A, tj. /je pravdivé jestliže A je pravdivé, a současně A je nepravdivé jestliže /je nepravdivé. Podobně O je subalterní E. □ rff - - & 29. září 2009 Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Aristotelova logika. Sylogismy. Sylogismy jsou jednoduché úsudky tvaru Hlavní premisa Vedlejší premisa :. Závěr Obě premisy i závěr jsou kategorická tvrzení tvaru A, E, I, O obsahující dohromady právě tři vlastnosti S, M, P, kde ■ hlavní premisa obsahuje PaM; ■ vedlejší premisa obsahuje SaM; ■ závěr je tvaru S z P. Lze tedy rozlišit následující čtyři formy sylogismů: I: MxP II: PxM III: MxP IV: PxM SyM SyM MyS MyS :. S z P .-. S z P .-. S z P .-. S z P Celkem tedy existuje 4 • 43 = 256 sylogismů. □ s ~ = ■= Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,^) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Aristotelova logika. Sylogismy. (2) Jen 24 sylogismů je platných: „Barbara, Celarent, Darii, Ferioque prioris Césare, Camestres, Festino, Baroco secundae Tertia grande sonans recitat Darapti, Felapton Disamis, Datisi, Bocardo, Ferison. Quartae Sunt Bamalip, Calames, Dimatis, Fesapo, Fresison." m Forma I: AAA, EAE, All, ElO (Barbara, Celarent, Darii, Ferioque), AAI, EAO (subalterní módy); ■ Forma II: EAE, AEE, ElO, AOO, (Césare, Camestres, Festino, Baroco), AEO, EAO (subalterní módy); ■ Forma III: AAI, EAO, IAI, All, OAO, ElO (Darapti, Felapton, Disamis, Datisi, Bocardo, Ferison); ■ Forma IV: AAI, AEE, IAI, EAO, ElO (Bamalip, Calemes, Dimatis, Fesapo, Fresison), AEO (subalterní mód). O (ne)platnosti sylogismů se lze snadno přesvědčit pomocí Vennových diagramů (John Venn, 1834-1923). □ ŕff - - Š 29. září 2009 Matematická logika Antonín Kučera Aristotelova logika. Platnost sylogismů. Úvod Aristotelova logika Logický čtverec Sylogismy ^"^'"X ^"^x^""\ X—"V—X s—v—X Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému QDÖDÖ3 (3D Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost A E 1 (všechna S jsou P) (žádná S nejsou P) (některá S jsou P) • šedé oblasti jsou prázdné; o (některá S nejsou P) Predikátová logika • symbol „•" označuje neprázdné oblasti; Syntaxe Sémantika Odvozovací systém Větao úplnosti • bílé oblasti mohou být prázdné i neprázdné. Větao neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. větao neúplnosti □ gp ► < š ► •< š ► ~= 29. září 2009 9/147 Matematická logika Antonín Kučera Aristotelova logika. Platnost sylogismů. (2) Úvod Aristotelova logika Logický čtverec Sylogismy Booleova • Uvažme nyní např. AEE sylogismus druhé formy (Camestres): Všechna P jsou M ( l__1 J algebra logiky Dva zákl. problémy Řešení 1. problému Žádná S nejsou M WA/V/ Žádná S nejsou P [ j Řešení 2. problému Vjwy Výroková logika Syntaxe Sémantika Tento sylogismus je tedy platný. Plnohodnotnost Kompaktnost SystémX(^,-) • Pro AlO sylogismus druhé formy dostáváme: Korektnost -^——"^ ^*—•■»* ^^^^ Úplnost Predikátová logika Všechna P jsou M l l__1 j í ŕ__} j Syntaxe Některá S jsou M \V*5c\^/ V/'^cV' Sémantika Odvozovací systém .-. Některá S nejsou P iľ j (f j Větao úplnosti Větao Vjwy Vjwy neúplnosti Turingův stroj Důkaz věty o Druhý diagram podává protipříklad, sylogismus platný není. neúplnosti Godelův důkaz 2. větao neúplnosti □ ŕff - - Š 29. září 2009 10/147 Matematická logika Antonín Kučera Aristotelova logika. Platnost sylogismů. (3)| Uvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Rozeberme ještě AAI sylogismus třetí formy (Darapti): Všechna M jsou P Všechna M jsou S Některá S jsou P Tento sylogismus je v Aristotelově logice považován za platný. Je však třeba použít předpoklad, že každá vlastnost je neprázdná. Tento předpoklad ale přináší jisté problémy: Všechny skleněné hory jsou skleněné. Všechny skleněné hory jsou hory. :. Některé hory jsou skleněné. Hlavní i vedlejší premisa jsou na však nikoliv. úrovni pravdivá tvrzení, závěr □ s Matematická logika Antonín Kučera Booleova „algebra logiky Uvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost SystémX(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti George Boole (1815-1864) Aplikoval algebraické techniky při formalizaci procesu odvozování. Nalezl souvislost mezi algebrou a sylogismy. Booleova „algebra logiky" se chová podobně jako algebra čísel. Násobení odpovídá logické spojce „a současně", sčítání logické spojce „nebo", apod. (Odtud pocházejí pojmy „logický součin" a „logický součet".). □ g 9617 Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Algebra logiky. Motivační příklad. Uvažme následující sylogismus: Všechna S jsou M Žádná M nejsou P :. Žádná S nejsou P Pokud vlastnosti identifikujeme se soubory objektů univerza, pro které platí, můžeme uvedený sylogismus přepsat na ScM MnP = o SnP = o a dále na S n M' = 0 MnP = o SnP = o (1) (2) (3) Pokusme se nyní „odvodit" (3) z (1) a (2): □ s Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,^) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Algebra logiky. Motivační příklad. (2) • Z toho, že S n M' = 0 a 0 n X = 0 pro libovolné X dostáváme (S n M') n P = 0 (4) • Podobně z (2) plyne (M n P) n S = 0 (5). • Ze (4), (5) a faktu, že 0 u 0 = 0, plyne ((S n M') n P) u ((M n P) n S) = 0 (6) • Užitím asociativity a komutativity u a n dostáváme z (6) ((S n P) n M') u ((S n P) n M) = 0 (7) • Nyní podle distributivního zákona lze (7) přepsat na (S n P) n (M' u M) = 0 (8) • Jelikož X u X' = 1 a X n 1 = X pro libovolné X, dostáváme z (8) SnP = 0 což bylo dokázat. □ S - = Š 29. září 2 Matematická logika Algebra logiky. Motivační příklad. (3) Antonín Kučera Úvod Aristotelova logika Loqickv čtverec V předchozím příkladu jsme k dokázání sylogismu použili symbolickou Sylogismy manipulaci se symboly S, M a P podle následující« Dh algebraických identit Booleova algebra logiky (tj. nezabývali jsme se tím, jaký mají symboly u, n , 0, 1, a' výzm 3/77). Dva zákl. problémy Řešení 1. problému XuX = X XUX' = 1 Řešení 2. problému XnX = X xnx' = 0 Výroková logika Syntaxe Xu Y = YUX X" = X Sémantika Plnohodnotnost Xn Y = Ynx XU1 = 1 Kompaktnost Systémx(^,-) XU(YUZ) = (XUY)UZ xm = x Korektnost Úplnost xn(YnZ) = (XnY)nz xuo = x Predikátová xn(XuY) = X xno = 0 logika Syntaxe Xu(XnY) = X (X U Y)' = X'n y Sémantika Odvozovací systém xn(YuZ) = (XnY)u(Xn Z) (X n Y)' = X'u y Větao úplnosti Xu(YnZ) = (XuY)n(Xu Z) neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. větao neúplnosti a g - = Š 2! !. září 2009 15/147 Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Větao úplnosti Větao neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. větao neúplnosti Algebra logiky. Motivační příklad. (4) Tyto identity definují algebraickou strukturu, které se později začalo říkat Booleva algebra (případně Booleův svaz). V původní Booleově notaci se ■ místo X n Y píše X.Y (případně jen XY); ■ místo X u Y píše X + Y; ■ místo X' píše 1 - X. V této notaci pak identity dostávají číselnou podobu a Boole sám se pokoušel převést další číselné konstrukce (např. dělení, ale i Taylorův rozvoj) do své „algebry logiky". Tyto úvahy však již byly zcela mylné. □ g Matematická logika Algebra logiky. Dva základní problémy. Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova • Podle Boolea je každý sylogismus možné zapsat ve tvaru algebra logiky Dva zákl. problémy F}{P,M,A) = 0 Řešení 1. problému Řešení 2. problému F2{S,M,B) = 0 Výroková logika Syntaxe .-. F(S,P,C) = 0 Sémantika Plnohodnotnost kde F^{P,M,A), F2{S,M,B), F(S,P,C) jsou vhodné výrazy Kompaktnost Systémx(^,-) vytvořené ze symbolů 0, 1, u, n,' a symbolů v závorkách. Korektnost Úplnost • Symboly A, B, C plní roli „blíže neurčených vlastností" při přepisu Predikátová logika Syntaxe kategorických tvrzení / a O. Např. „některá S jsou P" Boole vyjádřil pomocí rovnosti S n A = P n A, tj. (S n A) n (P n A)' = 0, kde A je Sémantika Odvozovací systém blíže neurčená vlastnost. Tento postup není zcela korektní. Větao úplnosti Větao neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. větao neúplnosti □ ŕ5P - - Š 29. září 2009 17/147 Matematická logika Antonín Kučera Algebra logiky. Dva základní problémy. (2) Úvod Aristotelova logika Logický čtverec Sylogismy • Boole uvážil obecnější úsudky tvaru Booleova algebra logiky F}{A},...,Am,B},...,Bn) = 0 Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Fk{A},...,Am,B},...,Bn) = 0 Sémantika Plnohodnotnost .-. F(Bi,...,Bn) = 0 Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová • Cílem jeho snah bylo vyvinout metodu, která umožní logika Syntaxe ■ zjistit, zda je daný úsudek pravdivý; Sémantika Odvozovací systém ■ nalézt nejobecnější závěr (F) pro dané předpoklady (Fi,...,Fk). Větao úplnosti Větao neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. větao neúplnosti □ (JP - - & 29. září 2009 18/147 Matematická logika Antonín Kučera Algebra logiky. Booieova metoda. Uvod Aristotelova logika Logický čtverec Sylogismy Booieova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Definice 1 Nechť A = A-\,...,An.A -konstituent je výraz tvaru U n---i,• • •,xpk, kde k>~\,ýkjey pro nějaké 1 < j < i, Důkaz věty o neúplnosti Godelův důkaz 2. větao neúplnosti • (ýj o ty,) pro nějaká 1 < j,j' < i, kde o je jeden ze symbolů a, v, -^. □ (5P - - & 29. září 2009 25/147 Matematická logika Antonín Kučera Výroková logika. Syntaxe. (2) i Uvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost SystémX(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Větao úplnosti Větao neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. větao neúplnosti Poznámka 10 V dalším textu budeme často vynechávat v zápisech formulí vnější závorky. Např. místo (A v -iß) budeme psát A v -iß. Po zavedení sémantiky výrokové logiky budeme často vynechávat i další dvojice závorek v případě, kdy vzniklá syntaktická nejednoznačnost nepovede k sémantické nejednoznačnosti. □ g Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Výroková logika. Sémantika. Definice 11 Pravdivostní ohodnocení (valuace) je zobrazení v, které každé výrokové proměnné přiřadí hodnotu 0 nebo 1. Metamatematickou indukcí k délce vytvořující posloupnosti lze každou valuaci v jednoznačně rozšířit na všechny výrokové formule: • v(A) je již definováno; 0 jestliže v(íp) = 1; 1 jinak. "(-V0 V(ýi A i/>2) V(ýi V i/>2) V(ípi -> íp2) 0 jestliže v(i/>i) = 0 nebo v(ý2) = 0; 1 jinak. 0 jestliže v(ý-\) = 0 a současně v(xp2) = 0; 1 jinak. 0 jestliže v(i/>i) = 1 a současně v(xp2) = 0; 1 jinak. □ s ~ = 29. září 2009 27/147 Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,^) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Definice 12 • Výroková formule cp je d (resp. nepravdivá) při valuaci v, pokud v(, právě když pro každou valuaci v platí, že v((p) = v(\p). □ s Matematická logika Antonín Kučera Výroková logika. Sémantika. (3) Uvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingúv stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Příklad 13 • Formule A v B je pravdivá při valuaci v-\, kde v-\ (A) = v-\ (B) = 1, a nepravdivá při valuaci v2, kde v2{A) = 0. Jde tedy o splnitelnou formuli, která není tautologií. • Pro každou formuli (p platí, že (p je tautologie právě když -Kp není splnitelná. • Nechť (p, i/>, E, jsou výrokové formule. Pak: (p A xjj

A (p (

) V (

9 □ rS Matematická logika Antonín Kučera Uvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost SystémX(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingúv stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Poznámka 14 „Identity" z posledního bodu příkladu 13 umožňují dále zpřehlednit zápis formulí. Např. místo (AvB)vC můžeme (nejednoznačně) psát AvBvC. Tato nejednoznačnost nevede k problémům, neboť příslušné definice a tvrzení „fungují" pro libovolné možné uzávorkování. Poznámka 15 V teorii výpočetní složitosti se dokazuje, že problém zda daná výroková formule (p je splnitelná (resp. tautologie) je NP-úplný (resp. co-NP-úplný). Otázka, zda existuje efektivní (polynomiální) algoritmus pro uvedené problémy, je ekvivalentní otázce zda P = NP. Definice 16 Formule (p je tautologickým důsledkem souboru formulí T, psáno T\= 1 J □ rS Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost SystémX(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Výroková logika. Systém X(F17 Definice 18 Nechť Fi, • • • ,Fk je konečný soubor výrokových funkcí. Definujeme formální logický systém X(F1, • • •, Fk), kde • Abeceda je tvořena znaky pro výrokové proměnné, závorkami a znaky T\r- ,Tk pro uvedené výrokové funkce. • V definici vytvořující posloupnosti formule (viz definice 9) požadujeme, aby xpi bylo buď výrokovou proměnnou nebo tvaru Tj(ýh, • • •, t/%), kde 1 < j}, • • • ,jn < i & n je arita Fs. • Valuace rozšíříme z výrokových proměnných na formule předpisem Poznámka 19 Ve smyslu definice 18\e dosud uvažovaný systém výrokové logiky systémem £(A, v, ->, -■). Dříve zavedené sémantické pojmy (splnitelnost, pravdivost, atd.) se opírají pouze o pojem valuace a „fungují" tedy v libovolném systému X(F1 ,••• ,Fk). * □ (JP - - ~= 29. září 2009 32 Matematická logika Antonín Kučera Výroková logika. Systém £(Fi,- , Fk). (2) Uvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Pro účely následující definice zvolme libovolné (ale dále pevné) lineární uspořádání E na souboru všech výrokových proměnných. Definice 20 Nechť

Xj podle toho, zda u,(y) = 1 nebo u,(y) = 0. Nyní se lehce ověří, že F = Fv. u neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. větao neúplnosti □ (JP - - ~= 29. září 2009 34/147 Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Výroková logika. Plnohodnotnost. (2) Uvažme následující výrokové funkce: X Y XaY X Y X| Y 0 0 1 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 0 X Y Z 0(X,V,Z) 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 0 Funkce a se nazývá Schroderův operátor. Platí

,--) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Výroková logika. Plnohodnotnost. (3) Následující systémy výrokové logiky jsou plnohodnotné: • £(a,v,-.) • £(a,-.) • X(v^) • £(->,-) • £(a) •£(l) • £(©) Věta 22. (pVxpx -i(-xp A -iip) (p A xp « -i(-xp V -iip) CpVxpx -i(p —> xp ->Gp ~ (p A (p, CpVxp -iCp « (p \(p, (p A Xp : ->(p « Q() A (

),£(-.), atd. □ s 29. září 2009 36/147 Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Výroková logika. Shefferovské spojky Definice 23 Výroková funkce F je Shefferovska jestliže X(F) je plnohodnotný systém. Věta 24 • Nechť S(n) značí počet všech Shefferovských funkcí arity n > 1. Pak S(n) = 2(2n"1-1)(2(2n"1-1) - 1). (Pro n = 1,2,3,4,5,... dostáváme postupně 0,2,56,16256,1073709056,... j J Jelikož lirrv S(n) 22r> 11 A, je (pro velká n) zhruba čtvrtina ze všech výrokových funkcí arity n Shefferovska. J □ s Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,^) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Výroková logika. Shefferovské spojky. (2) Poznámka 25 Výsledky o Shefferovských funkcích nalézají uplatnění při výrobě logických obvodů; na „podkladové desce" se např. vytvoří hustá síť binárních |-hradel. Obvody různé funkce se pak realizují jejich vhodným propojením. Integrovaný obvod 4011 CMOS se čtyřmi |-hradly. □ s 29. září 2009 38/147 Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva záki. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Větao úplnosti Větao neúplnosti Turingův stroj Důkaz věty o neúplnosti Godeiův důkaz 2. větao neúplnosti Výroková logika. Normální formy. Definice 26 • Literal je formule tvaru X nebo ->X, kde X je výroková proměnná; • Klauzule je formule tvaru ^ v • • • v tn, kde n > 1 a každé t\ je literal. • Duální klauzule je formule tvaru ^ a • • • a tn, kde n > 1 a každé t\ je literal. 9 Formule v konjunktivním normálním tvaru (CNF) je formule tvaru d a • • • A Cm, kde m > 1 a každé C, je klauzule. O Formule v disjunktivním normálním tvaru je formule tvaru d v • • • v Cm, kde m > 1 a každé C, je duální klauzule. Okamžitým důsledkem věty 22 je následující: Věta 27 Pro každou formuli cp existuje ekvivalentní formule v disjunktivním normálním tvaru. □ r5P - - & 29. září 2009 39/147 Matematická logika Antonín Kučera Výroková logika. Normální formy. (2) Uvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva záki. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost SystémX(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Větao úplnosti Větao neúplnosti Turingův stroj Důkaz věty o neúplnosti Godeiův důkaz 2. větao neúplnosti Věta 28 Pro každou formuli cp existuje ekvivalentní formule v konjunktivním normálním tvaru. Důkaz. Podle Věty 27 existuje k cp ekvivalentní formule v disjunktivním normálním tvaru, tj. (p ~ Vľ=i D/> kde n > 1 a každé D, je duální klauzule. Metaindukcí vzhledem k n: • n = 1. Pak V,=i Di je současně v CNF. Í1A-A4. Platí Indukční krok: Nechť D-i n+1 n+1 m m m k D, « Div\/Dí « D,v/\C, « /\D,VC, « /\/\(ťjVCi) /=2 ;=1 ;=1 ;=1 y'=1 D /=1 □ S 29. září 2009 40/147 Matematická logika Antonín Kučera Výroková logika. Normálni formy. (3) Uvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Příklad 29 Formuli (A - » B) A (B -> C) A(C->A) lze v CNF reprezentovat jako • (-.A V B) A(-.B VC) A(- iCvA) nebo • (-.A v C) A(-.C VB) A(-.B V/A). CNF tedy není určena jedno; inačně až na pořadí klauzulí a literálů. □ s 29. září 2009 41/147 Matematická logika Antonín Kučera Výroková logika. Věta o kompaktnosti. Uvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Systém x(->,--) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Věta 30 (o kompaktnosti) Nechť T je soubor formulí výrokové logiky. T je splnitelný právě když každá konečná část T je splnitelná. Důkaz. Směr „=>" je triviální. Dokážeme ,,<=". Zavedeme pomocný pojem: soubor V výrokových formulí je dobrý, jestliže každý konečný podsoubor V je splnitelný. Nechť i/>i, i/>2/• • • je posloupnost všech formulí výrokové logiky. Metamatematickou indukcí definujeme pro každé /' > 1 dobrý soubor S,: • Si = T. Soubor S-\ je dobrý neboť T je dobrý. >/+i í Si u {xpi} jestliže S, u {i/;,-} je dobrý; [ S,-u H/;/} jinak. Alespoň jeden ze souborů S, u {i/;,-} a S, u {-n/;,-} musí být dobrý; jinak existují konečné Ví c S, u {i/;,-} a V2 c S, u {-n^,-}, které nejsou splnitelné. Jestliže Ví c S, nebo V2 c S,, máme ihned spor s tím, že Si je dobrý; jinak \/^ u V2 obsahuje i/;,- i -n/;,-, proto i (Ví u V2) \ {^„-1^/} c Si je nesplnitelný, spor. □ (JP - - Š 29. září 2009 Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Výroková logika. Věta o kompaktnosti. (2) Nechť S = U/^i Si. Dokážeme, že S má následující vlastnosti: • S obsahuje (p právě když S neobsahuje -> ý právě když S neobsahuje (p nebo obsahuje i/>. Buď v valuace definovaná takto: v(A) = 1 právě když A patří do S. Indukcí k délce vytvořující posloupnosti se nyní snadno ověří (s využitím výše uvedených vlastností S), že: • S obsahuje (p právě když v( {1, • • •, k} taková, že f (u) ž f {v) pro každé (u, v) e H. □ s Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Výroková logika. Věta o kompaktnosti. (4) Věta 31 Graf Q = (U,H) je k-obarvitelný právě když každý konečný podgraf Q je k-obarvitelný. Důkaz. Nechť Buj je výroková proměnná pro každý uzel u a každé 1 < i < k. Buď T soubor tvořený následujícími formulemi: • ßu,i v • • • v BU/k pro každý uzel u; • Buj -> -iBuj pro každý uzel u a každé 1 < i,j < k, kde /' ^ y; • Buj -> -iBVfi pro každé (u, v) e H a 1 < i < k. Platí následující pozorování: • Graf Q je /c-obarvitelný právě když soubor T je splnitelný. • Každý konečný podgraf Q je /c-obarvitelný právě když každý konečný podsoubor T je splnitelný. Nyní stačí aplikovat větu 30. D □ S 29. září 2009 45/147 Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,^) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Výroková logika. Systém £( V této části se soustředíme na £,(->, -■). Uvažme následující odvozovací systém proX(-»,-0 (Lukasiewicz, 1928): Schémata axiómů: (i/, -> 4)) -> ((

odvoď i/;, (modus ponens) □ s Matematická logika Antonín Kučera Výroková logika. Systém £(■ Uvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systéi Systém X{-Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turinguv stroj Důkaz věty o neúplnosti Gödel úv důkaz 2. věta o neúplnosti Definice 32 Buď T soubor formulí. • Důkaz formule xp z předpokladů T je konečná posloupnost formulí (p. 1) W -> ((

((

(

W -* ,-■). (4) Antonín Kučera Úvod Aristotelova logika Logický čtverec Příklad 34 Sylogismy Booleova algebra logiky Pro libovolné formule cp, xp platí {cp, -■ ) Dva zákl. problémy Řešení 1. problému Řešení 2. problému Důkaz. Následující posloupnost formulí je důkazem xp z {cp, -<^lp —> ->Gp předpoklad MP na 2), 1) Korektnost Úplnost 4) (-.1/; -> -cp) - ^(op^xp) A3 Predikátová 5) Cp^xp MP na 3),4) logika 6) 9 předpoklad Syntaxe Sémantika 7) $ MP na 6),5) Odvozovací systém Větao úplnosti D Větao neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. větao neúplnosti □ s - - 1 29. září 2009 49/147 Matematická logika Antonín Kučera Výroková logika. Věta o dedukci. Uvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systém x(->,--) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Větao úplnosti Větao neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. větao neúplnosti Věta 35 (o dedukci) Nechť cp, xp jsou formule a T soubor formulí. Pak Tu {xp} \- cp právě když T \- xp —> cp. J Důkaz. „<=": Nechť £i, • • •, £& je důkaz formule xp -> cp z předpokladů T. Pak £i, • • •, šk, 4>> f Je důkaz formule cp z předpokladů T u {xp} (poslední formule vznikne aplikací MP na xp a E,k). „=>": Nechť £i, • • •, £,k je důkaz cp z předpokladů T u {xp}. Metaindukcí k j dokážeme, že T \- xp -> E,s pro každé 1 -» £i), i/> -» £i. První formule je instancí A1, druhá aplikací MP na £i a první formuli. Máme tedy důkaz xp -> <^ z T. Je-li 4i formule xp, platí T \- xp -> xp podle příkladu 33. □ g Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost SystémX(^) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Indukční krok: Je-li formule fy instancí axiómu nebo prvek T u {i/>}, postupujeme stejně jako výše (místo £i použijeme fy). Je-li fy výsledkem aplikace MP na £m, £„, kde 1 < m,n fy. Podle I. P navíc platí T\-xp^£,maT\-xp^ (£m -> fy). Důkazy xp -> E,m a xp -> (£m -> fy) z T nyní zřetězíme za sebe a připojíme následující formule: ■ (*/>- ^(4m- > m - -((V ^4m)^ (V" - £y)) ■ ty- ^m)- ► (!/;-> ^y) ■ \\) - >Zl První formule je instancí A2, tedy důkaz formule xp -» fyz další dvě T. vzn iknou aplikací MP Máme D □ S Matematická logika Antonín Kučera Výroková logika. Věta o korektnosti. Uvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost SystémX(^,^) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Věta 36 (o korektnosti) Nechť (p je formule a T soubor formulí. Jestliže T \- cp, pak T \= cp. J Důkaz. Nechť ^,--- ,ž,k\& důkaz cp z T. Indukcí vzhledem k j dokážeme, že T \= fy pro každé 1 (

V) (b) h -1-19 —> (p (c) h 9 —> -1-19 (d) v {

i/;) - »(-V- »-.9) (e) h cp -> (-.1/; - ->-i( i/;) - > ((^ - ->vo- »V) □ s - Matematická logika Antonín Kučera Výroková logika. Věta o úplnosti. (2) Uvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systém x(->,--) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Důkaz. (a): Podle příkladu 34 platí { {f -> Xp) (b): Platí 1) h -i-i

(-i^9 —» -i-i- 2) {-i-i^»} h -i^9 —» -1-1-i

(- 4) {-1-1^9} h -i-i^9 —> (p 5) {-.-.(p} h (p 6) h -i-i^9 —» (p (c): Platí 19) ■xp^xp) 1) h -1-1 -i

-i-icp w podle (a) věta o dedukci A3 MP na 2),3) věta o dedukci věta o dedukci podle (b) i(p) A3 MP na 1),2) □ s 'o *: O 'o T3 *: D CO ^ CD ■a 1 -a "O CD •—^T" CD g o "ô Q_ iS o !i >CD ■ •—^ ÍTT -—^ CT 0> C^T" CD ■^^ .£2 CM q CO -q CO "O % (Č T r -s- r r ' r ' -L T T -s- ô-T T T t -v r logi j. ^ r f r — T — ^ T Ä 1 r T ^ ft M t í t ô. r o-7 o- o-Y ö-Y s- -L T á s- r^ľ ^co ô- ~*~ -L w^ _L > s__ s__ _,__ o fo Q_ fo Q_ i— O o atická ika Kučera a Š I ^ E E E ^ í£ s s s S> S r O) £ 2 2 — cco| i > O CO E •0) CO ._ šr g ■- 2 o W co 5"í= N n ■a Matem log ntonín ■o g B o 11 o Oi0'ä.ä P = E 9E tS >■ Q Ui > a o ,t >. -O) .E q >, i 1 ■£. a ■o í£ S> O) 1 ! ä U O > : 2 « .§■ 1 5 .§" im m 3 °3 a> > d) ■a =o < o < o -■ m ,2 -g Q tt ffi ^ en cn a xĺ m í o B) B) O > J J F Qc C5 ■^- í ^ O O S T r ^: .* D ^T" v" X) s,/ 1 «1 « ■Q 1 •S -—. co -*—** CD --- O CD C~~ ^T1 O N "O c CD C C >CD ^-^ Q_ co -q > co >a5 o x >a5 £2 ^ > Q. CM ><2 Q_ > ^ o x Q. a> > T -s- ô-r r T r r -s- í? ^1 ť T T ^~ ■s-T m t -S-s-T '-$--$- r L^, ô- r r *—' r -3-r ^Ľ^ r ' ^ fT -Tii T ô. logik; r T s(0 Y o- ô- s- ö-Y -L w^ —^ _L w^ _L _L _L —^ _L > o TS -—s ^—- ^—s ^-s ^-s ^-s ^-s ^-s ^—S-^—s *Ĺ Q_ ■i- O > atická ika Kučera a Š K >. -a, O) o ti CO "g* 8 ^ T —, m o o J. (0 o O) > II řrokov yntaxe émantik Inohodr ompakti ystém i Korektní 1 U > o N O > TJ o 5 o a o c Q. -3 tih o 1 < o < _, B) > C R Q c C5 CS! Matematická logika Výroková logika. Věta o úplnosti. (5) Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova Definice 38 Nechť v je valuace a (p formule. Jestliže v( -.-.i/;, proto {X;, • • • ,X*} h -.-,1/; užitím MP □ g _ = Š 29. září 2009 57/147 Matematická logika Antonín Kučera Výroková logika. Věta o úplnosti. (6) Uvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systém x(->,--) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Větao úplnosti Větao neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. větao neúplnosti Je-li cp = xp -> £, kde {X,",• • • ,Xvk) \- xpv a {X;,• • • ,Xvk) \- E,v rozlišíme následující možnosti: ■ v{xp -> E,) = 1. Máme tedy dokázat, že {X,",• • • ,Xvk) \- xp -> £. Jestliže v(xp) = 0, platí {X,",• • • ,Xvk] v- -mp. Podle lematu 37 (a) dále platí h -^ -> (xp -> £), proto {X*,■ ■ ■ ,Xvk] v- xp -> E, užitím MP • Jestliže v(E) = 1, platí {X,",• • • ,Xvk) \- E,. Podle A1 platí h 4 -> (xp -> £), proto {X;,• • • ,Xvk] v- xp -> E, užitím MP ■ v(xp -> E,) = 0. Pak {X;, • • • ,Xvk) v- xp a {X,",• • • ,Xvk] v- -.£. Máme dokázat, že {X,",• • • ,Xvk] v- ^(xp -> £). Podle lematu 37 (e) platí h 1// ->(-.£ -> -.(i// -> £))> proto {X*,--- ,Xvk] v- -( E,) opakovaným užitím MP D □ g Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Věta 40 (o úplnosti) Nechť (p je formule a T soubor formulí. Jestliže T\=cp, pak T \- cp. J Důkaz. Nejprve uvážíme případ, kdy T je prázdný soubor. Nechť (p je tautologie aX-i,-- ,Xk všechny výrokové proměnné, které se ve (p vyskytují. • Podle Churchova lematu platí {XJO • • • ,X%} \- (p pro libovolné v. • Ukážeme, že všechny XY lze postupně „eliminovat", až dostaneme důkaz cp z prázdného souboru formulí. Předpokládejme, že pro dané 0 < n < k jsme již prokázali, že {Xl---,XlXvn+}}ycp pro libovolné v. Dokážeme, že pak také {Xj7, • • • ,X#} \- (p pro libovolné u. □ s ~ = 29. září 2009 59/147 Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,^) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Výroková logika. Věta o úplnosti. (8) Buď tedy u libovolná valuace. Nechť ^, u2 jsou valuace definované takto: • u1(Xn+1) = 1,u2(Xn+1) = 0 • pro každé Y * Xn+1 platí ^(Y) = u2(Y) = u(Y). Platí 1) {XjV-^X^X^lhp předpoklad pro v = ^ 2) {XjV-^X^X^jr-p předpoklad pro v = u2 3) {X1"/---/X^}i-Xn+1 -xp věta o dedukci na 1) 4) {XjV-.^lr-^X^ -^(P věta o dedukci na 2) 5) v- (Xn+i -> ((-Xn+1 - xp)- -> (p) podle lematu 37 (f) 6) {x»,---,xz}\-(p 2x MP na 5) s využitím 3),4) □ g Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Nyní uvážíme obecný případ. Buď T libovolný soubor formulí a

i, • • •, i/>n} formulí z T takový, že {i/>i, • • •, i/>n} h (^2 -» (l/>3 ~» • • • (ýn ~» i,• • • ,i/>n} i-

tedy také T h 9. D □ s 29. září 2009 61/147 Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,^) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Výroková logika. Historické poznámky. Výroková logika nebyla rozvíjena samostatně, ale jako součást složitějších formálních systémů. Gottlob Frege (1848-1925) položil základy predikátové logiky a zavedl „moderní" odvozovací systém. „Výrokový fragment" tohoto systému vypadá takto (verze z roku 1879): ■ 1: P^{Q ■ 2: (P^(Q^ R)) - ((P ^Q)^(P^ R)) ■ 3: {P^{Q ■ 4: (P -> Q) ■ 5: -.-.P-» P ■ 6: P -> —P ■ Odvozovací pravidla: MP a substituce Fregeho výsledky byly vědeckou komunitou ignorovány zhruba 20 let. □ (JP - - & 29. září 2009 P) R))- > ((P - Q) - ->(P R))- > (Q - (P - >R)) (-.Q- --P) Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Výroková logika. Historické poznámky. (2) Giuseppe Peano (1858-1932) doporučil na mezinárodním matematickém kongresu v Paříži (rok 1900) mladému Bertrandu Russellovi (1872-1970) studovat Fregeho práce. Russell v roce 1901 objevil inkonzistenci ve Fregeho systému (Russellův paradox), současně plně docenil Fregeho myšlenky. V letech 1910-1913 byla publikována třídílná Principia Mathematica (autoři Whitehead, Russell). Tato monografie měla hluboký vliv na vývoj logiky v následujících desetiletích. Věnována byla Fregemu. Pro fragment výrokové logiky byly použity následující axiómy a odvozovací pravidla: ■ 1 ■ 2 D 3 ■ 4 ■ 5 {PV P)^ P Q^{PvQ) [PvQ)^{QvP) (Pv(QvR))^(Qv(PvR)) (Q^R)^((PvQ)^(PvR)) Odvozovací pravidla: MP a substituce □ s Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,^) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Výroková logika. Historické poznámky. (3) V roce 1917 nalezl Jean Nicod následující zjednodušení axiomatického systému z Principia Mathematica: ■ 1: (Pv P)^ P ■ 2: P -> (P v Q) u 4: (P v (Q v R)) -^(Qv(Pv R)) ■ 5: (Q -> R) -> ((P VQ)^{PV R)) m Odvozovací pravidla: MP a substituce □ s Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Výroková logika. Historické poznámky. (4) Ve stejném roce publikoval Henry Sheffer následující axiomatický systém založený na Shefferově operátoru: ■ Axióm: (P|(Q|R))|((S|(S|S))|((Ü|Q)|((P|Ü)|(P|Ü)))) a Odvozovací pravidla: substituce a „z F a F|(G|H) odvoď H" David Hubert (1862-1943) a Wilhelm Ackermann (1896-1962) publikovali v roce 1928 následující systém: ■ 1: (Pv P)^ P ■ 2: P -> (P v Q) u 4: (P v Q) ^ (Q v P) ■ 5: (Q -> R) -> ((P VQ)^{PV R)) m Odvozovací pravidla: MP a substituce V roce 1927 navrhl John von Neumann (1903-1957) aplikovat substituci pouze na axiómy. Vznikly systémy založené na schématech axiómů. □ s Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,^) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Výroková logika. Historické poznámky. (5) Jan Lukasiewicz (1878-1956) prezentoval svůj odvozovací systém (použitý v přednášce) v roce 1928. Další odvozovací systémy: ■ V roce 1947 zjednodušili Götling a Rasiowa systém z Principia Mathematica do následující podoby: • 1: (Pv P)^ P • 2: P^(PvQ) • 3: (Q -> R) -> ((P vQ)^{Pv R)) • Odvozovací pravidla: MP a substituce ■ V roce 1953 prezentoval Meredith systém s jediným schématem a jediným odvozovacím pravidlem: • Schéma axiómu: ((((9 -»i/;) -» (^g -> -i£)) -» g) -> y) -> ((ľ -> 9) -> U -> 9)) • Odvozovací pravidlo: MP □ (JP - - Š 29. září 2009 6f Matematická logika Antonín Kučera Predikátová logika. Vznik a vývoj. Uvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost I Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti • Predikátová logika (také logika prvního řádu) se opírá o pojem vlastnosti (tj. predikátu). Umožňuje formulovat tvrzení o vlastnostech objektů s využitím kvantifikátorů. • Např. Aristotelova logika je z dnešního pohledu fragmentem predikátové logiky. • Formule prvního řádu byly součástí Fregeho systému, později se objevily ve 3. dílu Schröderovy monografie Algebra der Logik (1910) a monografii Principia Mathematica (Whitehead, Rüssel). • Logika prvního řádu byla definována jako samostatný systém až v monografii Hilberta a Ackermanna Grundzügen der theoretischen Log/k (1928). □ s Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Větao úplnosti Větao neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. větao neúplnosti Predikátová logika. Syntaxe. Definice 41 Jazyk (stejně jako jazyk s rovností) je systém predikátových symbolů a funkčních symbolů, kde u každého symbolu je dána jeho četnost (arita), která je nezáporným celým číslem. Poznámka 42 • Predikáty arity nula v jistém smyslu odpovídají výrokovým proměnným, funkční symboly arity nula jsou symboly pro konstanty. • Predikátovým a funkčním symbolům se také říká mimologické symboly. Jazyk je tedy plně určen mimologickými symboly. • Rozdíl mezi jazykem a jazykem s rovností se projeví v tom, že do predikátové logiky pro jazyk s rovností přidáme speciální logický symbol = jehož sémantika bude definována speciálním způsobem. □ (JP - - & 29. září 2009 68/ 47 Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Větao úplnosti Větao neúplnosti Turingův stroj Důkaz věty o neúplnosti Gödel ův důkaz 2. větao neúplnosti Predikátová logika. Syntaxe. (2) Příklad 43 • Jazyk teorie množin je jazykem s rovností, který obsahuje jeden predikátový symbol e arity 2. • Jazyk teorie pologrupje jazykem s rovností, který obsahuje jeden funkční symbol „•" arity 2. Definice 44 Abecedu predikátové logiky pro jazyk £ tvoří následující symboly: • Znaky pro proměnné x,y,z,..., kterých je spočetně mnoho • Mimologické symboly, tj. predikátové a funkční symboly jazyka £. • Je-li £ jazyk s rovností, obsahuje abeceda speciální znak = pro rovnost. • Logické spojky -> a ->. • Symbol V pro univerzální kvantifikátor. • Závorky ( a ). □ (5P - = & 29. září 2009 69/147 Matematická logika Antonín Kučera Predikátová logika. Syntaxe. (3) Uvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systém x(->,--) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Větao úplnosti Větao neúplnosti Turingův stroj Důkaz věty o neúplnosti Gödel ův důkaz 2. větao neúplnosti Definice 45 Termem jazyka £ je slovo t nad abecedou predikátové logiky pro jazyk £, pro které existuje vytvořující posloupnost slov U, • • •, tk, kde k > 1, tk je t, a pro každé 1 < i < k má slovo tj jeden z následujících tvarů: • proměnná, • f (ti,, • • •, tjn), kde 1 < h, • • •, in < k, f je funkční symbol jazyka £, a n je arita f. Term je uzavřený, jestliže neobsahuje proměnné. Poznámka 46 U binárních funkčních symbolů (a později také predikátů) dovolíme pro větší čitelnost infixový zápis. U funkčních (a predikátových) symbolů arity nula budeme psát c místo c(). □ s ~ = 29. září 2009 70/147 Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Predikátová logika. Syntaxe. (4) Příklad 47 • (x • y) • z je termem jazyka pologrup (v prefixové notaci •(•(*, y), z)) • 0 + (S(0) + S(S(0))) je termem jazyka 0, S, +, kde 0, S a + jsou po řadě funkční symboly arity nula, jedna a dva. □ s Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,^) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Predikátová logika. Syntaxe. (5) Definice 48 Formule predikátového počtu jazyka £ je slovo

~\,ýkjey pro nějaké 1 < j < i, • (ýj -> ty?) pro nějaká 1 < j,j' < i, • Vx xpj, kde x je proměnná a 1 ip • (p A ip značí -1(9 —> -iip). • (p <-» ip značí {(p -> ip) A(ip -> cp), kde symbol a dále „rozvineme' podle předchozího bodu. Příklady formulí: • Vx P(x, y) A 3x (P(x, x) v Q(c)) • Vx3x(P(x,x) WyVxQ(x)) □ rS 29. září 2009 73/1 47 Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost SystémX(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Predikátová logika. Syntaxe. (7) Definice 50 Každý výskyt proměnné ve formuli predikátového počtu je bud volný nebo vázaný podle následujícího induktivního předpisu: • Ve formuli tvaru P(ř1, • • •, r„) jsou všechny výskyty proměnných volné. • Výrokové spojky nemění charakter výskytů proměnných, tj. je-li daný výskyt proměnné ve formuli ip volný (resp. vázaný), je odpovídající výskyt ve formulích ->ip, cp —> ip,ip —> cp rovněž volný (resp. vázaný). • Ve formuli Vx ip je každý výskyt proměnné x (včetně výskytu za kvantifikátorem) vázaný; byl-li výskyt proměnné různé od x volný (resp. vázaný) ve formuli ip, je odpovídající výskyt ve formuli Vx ip rovněž volný (resp. vázaný). Příklady (volné výskyty jsou červené): • \/xP(x,y)v\/yP(x,y) • \/x(P(x,y)v\/yP(x,y)) □ g Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Predikátová logika. Syntaxe. (8) Definice 51 • Proměnná se nazývá volnou (resp. vázanou) ve formuli, má-li v ní volný (resp. vázaný) výskyt. • Formule je otevřená, jestliže v ní žádná proměnná nemá vázaný výskyt. • Formule je uzavřená (také sentence), jestliže v ní žádná proměnná nemá volný výskyt. • Zápis [e] právě když není M \= i/>[e]. • M h (i/> -» £,) [e] právě když M\=£[e] nebo není M h4>le]- • M h Vx i/>[e] právě když M \= i/>[e(x/a)] pro každý prvek a univerza M. Jestliže M\= Vx P(x) • Neplatí M \= (Vx P ^x)^Vx-P(x))^Vx (P(x) - -nP(x)) □ s Matematická logika Antonín Kučera Predikátová logika. Teorie. Uvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost SystémX(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Definice 58 Buď £ jazyk (příp. jazyk s rovností). • Teorie (s jazykem £) je soubor T formulí predikátového počtu jazyka £. Prvky T se nazývají axiómy teorie T. 9 Realizace M jazyka £ je model teorie T, psáno M\=T, jestliže M^cp pro každé

(i/, -> 4)) -> (Op -> VO -> (

4)) ■ P3: (^ -> -ni/;) -> ty -> xp)) —> (9 —> Vxi/>), kde x nemá volný výskyt ve cp. Odvozovací pravidla: ■ MP: Z(p acp ^ xp odvoď i/>. {modus ponens) ■ GEN: Z 9 odvoď Vx (p. (generalizace) □ g Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Predikátová logika. Odvozovací systém. (2) Je-li £ jazyk s rovností, přidáme dále následující axiómy rovnosti: • R1: x = x • R2: {x^=y^ A---^xn=yn^P{x^l^^^ rxn))^ P{y^l^^^ ryn), kde P je predikátový symbol arity n. • R3: {x^=y^ A---^xm=ym)^{f{x^l^^^ lxm)=f{y^l^^^ rym)), kde f je funkční symbol arity m. □ s Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,^) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Predikátová logika. Odvozovací systém. (3) Definice 60 Buď T teorie jazyka £. Důkaz formule xp v teorii T je konečná posloupnost formulí cp}, • • •, ), ve které nahradíme výrokové proměnné formulemi predikátové logiky tak, že daná výroková proměnná je nahrazena vždy touž formulí, obdržíme formuli predikátové logiky, která je dokazatelná v odvozovacím systému predikátové logiky pouze pomocí P1-P3aMP. Poznámka 63 (Neplatnost „obecné" věty o dedukci) Za předpokladu korektnosti odvozovacího systému pro predikátovou logiku neplatí \- (p -> Vxcp. Platí ovšem {cp} \- Vxcp. Proto obecně neplatí, že T \= (p -> xp právě když T u {(p) \= xp. □ s Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Predikátová logika. Věta o dedukci. Věta 64 (o dedukci) Nechť T je teorie jazyka £, xp uzavřená formule jazyka £ a

": Nechť £i, • • •, £,k je důkaz formule xp -> p v T. Pak <^, • • •, E,k, xp,

(!/;- * £,)) • ty- ^4m) ^(- ^y) • xp —, <^y První form ule je nstancí P2, dalš ídvě vzniknou aplikací MP Máme tedy důkaz formule xp -> ^ v 7. Je-li 4y výsledkem aplikace GEN na £m, kde 1 < m < j, je £y- tvaru Vx£m. Podle I.P platí T \- xp -> E,m. K tomuto důkazu nyní stačí připojit formule • Vx (xp -> £m) • Vx(i/;->£m)->(i/;->Vx£m) První vznikne aplikací GEN, druhá je instancí P5, třetí vznikne aplikací MP Dostaneme tak důkaz formule xp -> £y- v T. □ S - = Š 29. září; D Matematická logika Antonín Kučera Predikátová logika. Kvantifikace. Uvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Lema 65 Pro každé formule (p a xp platí: O i-(Vx( (cp -> Vxi/>), pokud x není volná ve formuli cp; Q h(Vx()) <-> (Bx

i/;), pokud x není volná ve formuli xb; O i-(3x(9- ■*!/;)) <-> (cp ->Bxi/>), pokud x není volná ve formuli cp; O i-(3x( (VX(p ->i/;), pokud x není volná ve formuli xb. Důkaz. Pozorování: (a) Jestliže \- (p -> xb a současně \- xb -> cp, pak \- cp <-» xb. To plyne z toho, že (A -> B) -> ((ß -» A) -> (A <-» B)) je výroková tautologie (viz poznámka 62). (b) (tranzitivita implikace). Jestliže T \- cp -> E, a současně T \- E, T h 9 -»xb. Stačí použít poznámku 62 a tautologii (A - C) - ((C - B) - (A - B)). xb, pak □ s Matematická logika Antonín Kučera Predikátová logika. Kvantifikace. (2) Uvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost SystémX(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti (c) Nechť (p(x), xp{x) jsou formule. Pak \- Vx (cp -> xp) -> Vx (-n/; -> -19), neboť 1) ,. vx o?-> vo-> o?-> vo 2) h (cp _» ip) _» (^ _» ^p) 3) h Vx ((p -» i/;) -» (-.i/; -» -.9) 4) Vx (9 -» i/;) h -n/; -» -19 5) Vx (

xp) h Vx (-.1/; -> -. xp)) -> {(p -> Vxxp), neboť tato formule je instancí P5. Důkaz opačné implikace vypadá takto: 1) 2) hVxxp ^ xp i-(Vxi/;->i/;)->(( 3) 4) 5) 6) h {(p —> Vxip) —> {(p —> y (p —> Vx i/; \- (p —> xp (p —> Vx xp v- Vx {(p —> xp) v- (cp^Mxxp) -> (Vx((p Vxxp)^(cp^xp)) B)_>((C-/\)-(C-B)) je tautologie, viz pozn. 62 MP na 1),2) věta o dedukci GEN věta o dedukci □ s Matematická logika Antonín Kučera Pre< dikátová logika. Kvantifikace. (4) Úvod O Nejprve ukážeme, že \- Vx (

xp) - ->(Bxi/>). Aristotelova logika 1) h Vx (-iip —> ->cp) —> (-iip —> Vx ->cp) podle 1. Logický čtverec Sylogismy 2) h Vx (

xp) -> Vx (-n/; -> -< xp)) -> {-^xp -> Vx -< Vx ->cp) —> (-iVx ->cp —> xp) taut. (-.B -> A) -> (-.A - -B) Řešení 1. problému 5) h Vx {(p -> xp) -> (-.Vx -<

xp) —> (3x (p ^ xp) reformulace Syntaxe Sémantika Nyní opačný směr \- (3x (p -> xp) -> Vx (

xp): Plnohodnotnost Kompaktnost SystémX(^,-) 1) h (-11/; —> Vx -19) —> Vx (-iip —> -19) podle 1. Korektnost Úplnost 2) h (-iVx-19 —> t/>) —> (-11/; —> Vx-xp) taut. (-.B -> A) -> (-.A - -B) Predikátová 3) h (-iVx -xp —»i/;) —» Vx (-11/; —> -19) tranz. impl. na 1), 2) logika 4) 3x^ —> 1/; h Vx (-11/; —> -xp) věta o dedukci Syntaxe Sémantika 5) 3x 9 —> 1/; h -ii/> —> -19 P4aMP Odvozovací systém Větao úplnosti 6) 3x (p ^ xp \- (p ^ xp (-.A -> -.B) -> (A -> B) a MP Větao 7) 3x 9 —> 1/; h Vx {(p —> xp) GEN neúplnosti Turingův stroj 8) \- (3x (p —> xp) —> Vx {(p —> xp) věta o dedukci Důkaz věty o neúplnosti Godelův důkaz D 2. větao neúplnosti □ g - = Š 29. záříi >009 94/147 Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Predikátová logika. Věta o korektnosti. Věta 66 Nechť T je teorie a (p formule jazyka teorie T. Jestliže T \- cp, pak T\= op. Důkaz. Stačí ověřit následující tvrzení: • Je-li i/> instancí jednoho ze schémat P1-P5 (příp. také R1-R3, pokud jazyk teorie T je jazyk s rovností) a M je model T, pak M^xp. • Je-li M model T a i/>, E, formule jazyka teorie T, kde M \= i/> a • Je-li M model T a i/> formule jazyka teorie T, kde M^xp, pak AihVxý. Metaindukcí vzhledem k /' je pak již triviální ukázat, že je-li i/>i, • • •, i/>fc důkaz formule op v T a M je model T, pak T \= ýj pro každé 1 < i < k. D □ S Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,^) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Predikátová logika. Úplnost (úvod). Lema 67 Následující tvrzení jsou ekvivalentní: O Pro každou teorii T a pro každou formuli op jazyka teorie T platí, že jestliže T^op, pak T h op. O Každá bezesporná teorie má model. Důkaz. (1. => 2.) Buď T bezesporná teorie. Pak existuje formule op jazyka teorie T, která není v T dokazatelná (tj. T y- op). Obměnou 1. pak ale dostáváme, že op není sémantickým důsledkem T (tj. T y= op). To znamená, že existuje takový model 7, kde není pravdivá op. Zejména má tedy T model. □ g Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti (2. => 1.) Užitím 2. dokážeme obměnu 1. Nechť tedy Ty- cp, a nechť čp je univerzální uzávěr cp. Ukážeme, že 7 u {-Kp} je bezesporná; pak podle 2. má 7 u {-Kp} model, tedy 7 y= cp. 7 u {-up} je bezesporná: Předpokládejme naopak, že 7 u {-Kp} je sporná. Pak 1) 7 u {-up} h (p 7 u {-up} je sporná 2) 7 h -up -»(p věta o dedukci 3) h (-up -»(p) -» ^ (-./A -»/A) -» /A je tautologie, viz pozn. 62 4) T\-p MPna2),3) 5) T \- cp opakovaně P4 a MP Obdrželi jsme tedy spor s tím, že 7 y- cp. D □ S Matematická logika Antonín Kučera Predikátová logika. Úplnost (úvod). (3) Uvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost SystémX(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Cílem dalšího postupu je dokázat, že každá bezesporná teorie má model. Tato konstrukce obsahuje dva základní obraty: • Zavede se pojem kanonické struktury pro danou teorii 7. Tato struktura obecně není modelem 7. Ukážeme, že pokud 7 vyhovuje dalším podmínkám (je henkinovska a úplná), pak kanonická struktura je modelem 7. • Ukážeme, že každou bezespornou teorii je možné vhodným způsobem rozšířit tak, aby byla henkinovska a úplná. □ g Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Predikátová logika. Rozšíření teorie. Definice 68 • Teorie S je rozšíření teorie T, jestliže jazyk teorie obsahuje jazyk teorie Tav teorii S jsou dokazatelné všechny axiómy teorie T. • Rozšíření S teorie T se nazývá konzervativní, jestliže každá formule jazyka teorie T, která je dokazatelná vS,je dokazatelná ivT. • Teorie S aT jsou ekvivalentní, jestliže S je rozšířením T a současně T je rozšířením S. Příklad 69 • Teorie komutativních grup je nekonzervativní rozšíření teorie grup. • Teorie grup je nekonzervativní rozšíření teorie monoidů (tvrzení Vx3y x • y = 1 nelze dokázat v teorii monoidů). • Gödel-Bernaysova teorie tříd je konzervativním rozšířením Zermelo-Fraenkelovy teorie množin. □ s Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,^) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Predikátová logika. Věta o konstantách. Věta 70 (o konstantách) Nechť S je rozšíření T vzniklé obohacením jazyka teorie T o nové navzájem různé konstanty C}, • • •, ck (nové axiómy nepřidáváme), a nechť x-i, • • •, xk jsou navzájem různé proměnné. Pak pro každou formuli

: K důkazu

i,--- ,ýk je důkaz i{c/y) instancí téhož schématu. • Je-li i/;,- axióm teorie T, pak se v i/;,- nevyskytuje c a formule i/;,- a 4>i{c/y) jsou tedy totožné. □ g - - Š 29. září 2009 101 Matematická logika Antonín Kučera Predikátová logika. Věta o konstantách. (2) Uvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Jestliže xpj vyplývá z xp-s a xpm pomocí MP, je xpm tvaru \p-s —> i/>,- a formule 4>m{c/y) je tedy formulí 4>j{c/y) -> xpi(c/y). Takže formule 4>i{c/y) vyplývá z 4>j{c/y) a 4>m{c/y) pomocí MR Jestliže i/;,- vyplývá z i/>y- pomocí GEN, je i/;,- tvaru Vxi/>y-. Stačí si uvědomit, že (Vxi/>y-)(c/y) je tatáž formule jako Vx (i/>y(c/y)), neboť x a y jsou různé. Ukázali jsme, že 7 h ( (x/y) (y/x) je totéž co 9 D □ s - = š Matematická logika Antonín Kučera Predikátová logika. Henkinovské teorie. Uvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systém x(->,--) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Definice 71 • Teorie T je henkinovská, jestliže pro každou formuli cp jazyka teorie T s jednou volnou proměnnou x existuje v jazyce teorie T konstanta c taková, že T \- Bxcp -> 3y£(x/y): 1) {Vy-.£(x/y)} h Vy-.£(x/y) 2) {Vy-.£(x/y)} h-.£(x/y)(y/x) P4 a MP 3) {Vy-4(x/y)l \- -4 přepis 4) {Vy-4(x/y)} h Vx-4 GEN 5) h Vy-i^(x/y) -» Vx-i£ dedukce 6) h 3x4 -> 3y4(x/y) taut. (A -> B) (-.B->-./l) a MP. □ s - = š Matematická logika Antonín Kučera Predikátová logika. Henkinovské teorie. (3) Úvod Aristotelova logika Loqickv čtverec Nechť R značí teorii vzniklou pouhým přidáním konstanty c9 k T. Nechť Sylogismy ip je formule jazyka teorie T taková, že S \-ip. Nechť y je proměnná, Booleova algebra logiky která se nevyskytuje ani ve (p(x/Cp)) -> i/> předpoklad S = R U {3xcp -> (p(x/y)) -> i/; věta o konstantách Kompaktnost 4) T h Vy((3xcp -> cp(x/y)) -> i/,) GEN Systém x(->,--) Korektnost 5) T h 3y(3x(p -> (p(x/y)) -> ip lema 65 (2) a MP Úplnost 6) h (3x(p -> By 3y(3x(p -> (p(x/y)) terna 65 (3) Predikátová logika 7) T h (3x(p -> By ip tranz, implikace Syntaxe Sémantika Odvozovací systém 8) 9) \- 3x(p —> 3ycp(x/y) T\-ip dokázáno výše MP Větao úplnosti Větao D neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. větao neúplnosti intiStlŠ** - Š 29. září 2009 104/147 Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Predikátová logika. Henkinovské teorie. (4) Věta 73 (o henkinovském rozšíření) Ke každé teorii existuje henkinovska teorie, která je jejím konzervativním rozšířením. Důkaz. Buď 7 teorie. Pro každé n > 0 definujeme teorii Tn takto: • T0 = T. Teorie 7/+1 vznikne z 7, tak, že pro každou formuli (p(x) jazyka teorie 7, přidáme novou konstantu c9 a formuli 3xp -> , může být v důkazu formule i/> použito jen konečně mnoho axiómů E,},--- ,£,k, které nepatří do 7,. Užitím věty o henkinovské konstantě /c-krát po sobě dostáváme 7/ \-1/;, proto T \- xp podle I.P Uvažme teorii S = Uľ=o Tn. Teorie S je konzervativní rozšíření 7, neboť každý důkaz v S používá jen konečně mnoho axiómů a je tedy důkazem v nějaké 7m. Teorie S je zjevně henkinovska. d □ ě5P _ = Š 29. září 2009 10! Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,^) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Predikátová logika. Henkinovské teorie. (5) V následující větě využíváme Zornovo lema, které říká následující: Nechť (A, <) je uspořádaná množina. Jestliže pro každý spočetný řetěz a0 < a^ < a2 • • • existuje v A horní závora, pak {A,<) má maximální prvek. Zornovo lema je ekvivalentní s axiomem výběru. □ g - = s Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Predikátová logika. Henkinovské teorie. (6) Věta 74 (o zúplňování teorií) Ke každé bezesporné teorii existuje její rozšíření se stejným jazykem, které je úplnou teorií. Důkaz. Uvažme uspořádanou množinu (T,c), kde T je soubor všech bezesporných teorií obsahujících T. Každý spočetný řetězec T0 c Ti c T2 • • • má v (T,c) horní závoru U/^o T. Zde je třeba ověřit, že U/^o Ti je skutečně bezesporná teorie (a tedy prvek T): pokud by tato teorie byla sporná, existuje v ní důkaz kontradikce. Tento důkaz ale používá jen konečně mnoho axiómů, proto je důkazem i v nějaké T,, tedy Ti je sporná, spor. □ s - = & Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,^) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Predikátová logika. Henkinovské teorie. (7) Podle Zornova lematu tedy existuje maximální bezesporná teorie

-<

A) -» ((-.A -» A) -» (i/; A -.i/;)) je výroková tautologie (použijeme 2x MP). Tedy 1/ je sporná, spor. Pokud je jazyk teorie T konečný nebo spočetný, lze se použití Zornova lematu snadno vyhnout. Dokazovaná věta pak žádnou formu axiómu výběru nevyužívá. d □ g - = s Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Predikátová logika. Kanonická struktura. Definice 75 Buď T teorie, kde jazyk teorie T obsahuje alespoň jednu konstantu. Kanonická struktura teorie T je realizace M jazyka teorie T, kde • univerzum M je tvořeno všemi uzavřenými termy jazyka teorie T; • relizace funkčního symbolu f arity n je funkce ím, která uzavřeným termům U, • • •, tn přiřadí uzavřený term ř(ř1, • • •, r„); • realizace predikátového symbolu P arity m je predikát PM definovaný takto: PM(ři, • • •, řm) platí právě když T \- P(ři, • • •, tm). □ rS1 ~ = -E Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost SystémX(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Predikátová logika. Kanonická struktura. (2) Věta 76 (o kanonické struktuře) Nechť T je úplná henkinovska teorie, a nechť jazyk teorie T je jazykem bez rovnosti. Pak kanonická struktura teorie T je modelem T. Důkaz. Nechť M je kanonická struktura teorie T. Ukážeme, že pro libovolnou formuli

. Buď -n/) libovolná uzavřená instance. Jelikož i/) je uzavřená instance xp, podle IP platí 7 \- ip právě když M \= if>. Dále 7 \- -n/> právě když Ty i/) (7 je bezesporná) právě když M y= xp (IP) právě když M \= -n/>. (p = xp -> E,. Každá uzavřená instance této formule je tvaru xp ^ £,, xf> je uzavřená instance xp a | je uzavřená instance £. kde Nechť 7 h i/; -» |. Jelikož i/) je uzavřená formule a 7 je upíná, platí buď 7 h xp nebo 7 h -n/). V prvém případě dále 7 h | (MP) a užitím IP celkem dostáváme M \= xp a M \= |. Proto také y\4 |= i/) -» |. V druhém případě Ty xp (7 je bezesporná), proto M y= xp (IP), tudíž M h i? -> I- Nechť M \= xp -> |. Pak buď M ^ ý nebo M h I- V prvém případě ľŕif podle IP, tudíž 7 h -n/) neboť 7 je úplná. Proto 7 h xp -» | užitím tautologie -./A -» (/A -» ß) a MP V druhém případě 7 h |, proto 7h i/) -» | užitím tautologie /A -»(ß -» /A) a MP □ rjP - - ^ 29. září 2009 11 Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost SystémX(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Predikátová logika. Kanonická struktura. (4) (p = \/xxp. Buď Vxxp libovolná uzavřená instance. Pak xp(x), jinak by Vxxp nebyla uzavřená. ■ Nechť 7 h Vxxp. Pak pro libovolný uzavřený term ř platí 7 \- xp(x/t) (P4 a MP). Podle IP M \= xp(x/t). Jelikož tento argument funguje pro libovolný uzavřený term ř, platí také M \= Vxxp. A -+A Nechť T yMxx}. Pak také 7 y Vx -.-.t/J (kdyby 7 v Vx -.-.i/J, dostaneme dále 7 h -i-n/; (P4 a MP) a 7 h xp (tautologie -■-a MP), 7 h Vx^ (GEN), spor). Jelikož Ty Vx-i-h/;, platí 7 \- -Nx^^xp neboť 7 je úplná. Tedy 7 h 3x-ií/^. Jelikož 7 je henkinovská, platí 7 h 3x->ip —> ->ip(x/c) Tedy 7 h -n/>(x/c) a proto T ľ xp(x/c) neboť 7 je bezesporná. Podle IP M £ i/5(x/c), tedy M h ^ý(x/c). Proto M ^ Vx^. D □ g - = s Matematická logika Antonín Kučera Predikátová logika. Kanonická struktura. (5) Uvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Věta 77 Nechť T je úplná henkinovské teorie, a nechť jazyk teorie T je jazykem s rovností. Pak T má model. Důkaz. Buď S teorie (s jazykem bez rovnosti), která vznikne rozšířením T o nový binární predikátový symbol = a axiomy R1-R3. Symbol = v teorii S je tedy mimologický a může být realizován „jakkoliv", Axiomy R1-R3 jsou v S „normální" axiómy. Stačí nám ukázat, že S má takový model, kde = je realizován jako identita. Takový model pak jistě bude i modelem T (kde = je chápáno jako logický symbol). □ s - = & Matematická logika Antonín Kučera Predikátová logika. Kanonická struktura. (6) Uvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost SystémX(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Buď M kanonická struktura teorie S, a nechť ~ je realizace = v S (tj. ři ~ t2 právě když S \- U = ř2). Dokážeme, že ~ je nutně ekvivalence: • reflexivita: S \- x=x (R1), S \- Mxx=x (GEN), S v- Mxx=x -> ř=ř (P4), S h ř=ř (MP). Tedy ř ~ ř. • symetrie: nechť s ~ ř, tj. S \- s=t. Platí S h {x^=y^ Ax2=y2) -» (xi=X2 -» yi=/2) (R2, = hraje i roli P). Užitím GEN, P4 a MP dostaneme S \- (s=ř A s=s) -> (s=s -> t=s). Užitím MP dostaneme S \- t=s. • Tranzitivita: podobně. □ g - = & Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Predikátová logika. Kanonická struktura. (7) Nyní již můžeme definovat strukturu O pro jazyk teorie S: 9 Nosičem O jsou třídy rozkladu nosiče M podle ~. • Funkční symbol f arity n je realizován takto: řo([ři]/---/[řn]) = [řM(ři/---/t.)] • Predikátový symbol P arity m je realizován takto: Po([ři]/ • • • / [tm]) právě když PM{Ur • • ,tm) Korektnost této definice (tj. nezávislost na volbě reprezentantů) se dokáže pomocí R1-R3 podobným stylem jako výše. Snadno se ověří, že realizací uzavřeného termu ř ve struktuře O je [s] právě když S \- s=t. To znamená, že predikátový symbol = je v O realizován jako identita. □ s - = & Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,^) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Predikátová logika. Kanonická struktura. (8) Zbývá ukázat, že Oje modelem S. Podobně jako ve vářá 76 budeme chtít prokázat, že pro libovolnou formuli (p{x\,. ..,xn) jazyka teorie S platí • Jestliže ři, • • •, tn jsou uzavřené termy jazyka teorie S, pak T h (p{x} /ři,• • • ,xn/tn) právě když O \= (p{x} /[ři], • • • ,xn/[tn]). Jelikož S je henkinovská a úplná, platí podle věty 76 • T^(p{x}lUr-- ,xn/tn) právěkóyžM\=(p{xi/U,---,xn/tn) Stačí tedy ukázat, že • M \= " je triviální. Pro opačnou implikaci stačí ukázat, že T je bezesporná (pak T má model podle věty o úplnosti). Kdyby T byla sporná, existoval by důkaz formule i/> a -h/; v T. Tento důkaz je konečný, využívá tedy jen konečně mnoho axiómů 7, které tvoří spornou podteorii 7, spor. d □ g - = s Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Predikátová logika. Löwenheimova-Skolemova věta. Poznámka 80 Z důkazu věty 73 plyne, že každá bezesporná teorie s jazykem bez rovnosti má model kardinality max{|X|,N0} (při rozšíření teorie na henkinovskou bylo přidáno |£| • N0 nových konstant). Toto pozorování neplatí pro teorie s jazykem s rovností (např. pro T = {Vxx=c}). Nicméně lze dokázat následující: Věta 81 Nechť T je teorie a nechť pro každé n e N existuje model teorie T jehož nosič má mohutnost alespoň n. Pak T má nekonečný model. Důkaz. Je-li jazyk teorie T jazykem bez rovnosti, plyne tvrzení ihned z poznámky 80. Jinak pro každé n e N definujeme formuli (pn = Vxi • • • Vxn3y x-i ty A • • • A xnžy a teorii Sn = T u {cp-\, • • •, cpn}. Podle předpokladu věty má každá Sn model. Podle věty o kompaktnosti má proto model i teorie U/^i Sn- Tento model je nutně nekonečný a je i modelem teorie T. d □ g - - Š 29. září2009 11! Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,^) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Predikátová logika. Löwenheimova-Skolemova věta. (2) Věta 82 (Löwenheimova-Skolemova) Nechť T je teorie s jazykem L, která má nekonečný model. Nechť k je nekonečný kardinál takový, žex> \£\. Pak T má model mohutnosti k. Důkaz. Nechť M je nekonečný model T. Jazyk £ rozšíříme o systém {c, \ i Hfly informatiky (jako vědy). Syntaxe Sémantika ""*" m o Turingův stroj je matematickým Plnohodnotnost y50í modelem „hloupého Kompaktnost Systém X(-»,--) ^^ĚĚ m_ odvozovače", který má k dispozici Korektnost "^| w papír, tužku a gumu, a který Úplnost Predikátová iúk si pamatuje konečně mnoho logika JjF ^-> >í schémat axiómů. Syntaxe Sémantika Odvozovací systém o Význam Turingova stroje coby Věta o úplnosti Alan Turing (1912-1954) modelu reálných výpočetních Věta o zařízení se projevil až v druhé neúplnosti Turingův stroj polovině 20. století. Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti □ r3P - = Š 29. září 2009 122/147 Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Věta o neúplnosti. Turingův stroj. (2) Je-li Z konečná abeceda, značí symbol Z* soubor všech konečných slov složených z prvků Z (prázdné slovo značíme symbolem e). Délku slova w značíme len(w). Pro každé 1 < / < len(w) značí symbol w(i) Mý znak slova w (zleva). Jazyk nad abecedou Z je podmnožina Z*. Turingův stroj je matematický model výpočetního zařízení, které je vybaveno konečně-stavovou řídící jednotkou („hlava odvozovače"), jednosměrně nekonečnou pracovní páskou („papír"), a čtecí/zápisovou hlavou („tužka/guma"). Na začátku výpočtu je na pásce zapsáno konečné vstupní slovo, hlava je na nejlevější pozici, a stavová jednotka je v počátečním stavu. Stroj na základě svého momentálního kontrolního stavu a symbolu pod čtecí hlavou provede „výpočetní krok", tj. změní svůj kontrolní stav, nahradí symbol pod čtecí hlavou jiným symbolem, a posune čtecí hlavu vlevo nebo vpravo. Výpočet se zastaví, pokud stroj dojde do konfigurace, jejíž kontrolní stav je akceptující nebo zamítající. Pro některá slova může stroj také nezastavit (cyklit). Vstupní slovo je akceptované, jestliže stroj po konečně mnoha krocích dojde do akceptující konfigurace. Soubor všech vstupních slov, která stroj akceptuje, tvoří jazyk akceptovaný daným strojem. □ g - - Š 29. září 2009 12: Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,^) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Věta o neúplnosti. Turingův stroj. (3) Definice 83 Turingův stroj je devítice M = (Q, Z, V,,_,, >, q0, qa, qr, ö), kde • Q je konečný soubor kontrolních stavů; • Z je konečná vstupní abeceda; • r je konečná pásková abeceda (kde I c r a Q n r = 0); • ■_, e r je prázdný znak; 9 > e r je levý konec pásky; • Qo, Qa, qr £ Q je po řadě počáteční, akceptující a zamítající stav (q0/ qa/ qr jsou navzájem různé). • ö : Q x \~ ^ Q x \~ x {L, R} je přechodová funkce, kde ■ pro každé p e Q platíô(p, >) = {q, >, R) pro nějaké q e Q; m ö(qa, c) = (qa, c, R) pro každé c e ľ; ■ ö(qr, c) = (qr, c, R) pro každé c e V. □ g - = Š 29. září Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Konfigurace stroje M je konečné slovo uqv, kde u, v e P a q e Q. Počáteční konfigurace pro slovo w e Z* je konfigurace q0>w. Krok výpočtu je binární relace i-> na množině konfigurací definovaná takto: ■ Jestliže ö(q,a) = (p,b, L), pak ucqav \-* upcbv pro každé u, v e P a c e r. d Jestliže ) = (p,b, R), pak uqav \-* ubpv' pro každé u, v e V* kde v' = v pokud v je neprázdné, jinak v' = ,_,. ■ h» obsahuje jen to, co lze odvodit pomocí předchozích dvou pravidel. Slovo w e Z* je akceptované strojem M, jestliže q0>w \->* uqav pro nějaké u, v e P. Jazyk akceptovaný strojem M, označovaný L(M), je soubor všech w eY.*, které jsou akceptované strojem M. □ s - = & 29. září 2009 125/147 Matematická logika Antonín Kučera Věta o neúplnosti. Vlastnosti jazyků. Uvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost SystémX(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Jazyk L c z* je rekurzivně vyčíslitelný, jestliže L = L(M) pro nějaký Turingův stroj M. Jazyk L c z* je rekurzivní, jestliže L = L(M) pro nějaký Turingův stroj M, který zastaví pro každé vstupní slovo. Jednoduché pozorování je, že jazyk L c z* je rekurzivní právě když L i L jsou rekurzivně vyčíslitelné (kde L = Z* \ L). Uvažme soubor všech Turingových strojů se vstupní abecedou {0,1}. Bez újmy na obecnosti lze předpokládat, že kontrolní stavy a symboly páskové abecedy každého takového stroje jsou prvky nějaké fixní spočetné množiny. Pak každý Turingův stroj M se vstupní abecedou {0,1} lze jednoznačně zapsat jako slovo code(M) e {0,1 }*. Navíc lze předpokládat, že každé u e {0,1 }* je kódem nějakého stroje Mu se vstupní abecedou {0,1}. Uvažme jazyk Accept = {u e {0, "\}*\MU akceptuje u). Lze snadno (i když technicky) dokázat, že Accept je rekurzívně vyčíslitelný (lze zkonstruovat stroj U, který pro dané vstupní slovo u e {0,1 }* „simuluje" výpočet stroje Mu na slově u). Ukážeme, že Accept není rekurzívní. Podle jednoho z předchozích bodů pak jazyk Accept není rekurzivně vyčíslitelný. □ g - - Š 29. září 2009 1; 52 Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Věta o neúplnosti. Jazyk Accept Věta 84 Jazyk Accept není rekuzivní. J Důkaz. Předpokládejme, že Accept je rekurzivní. Pak také Accept je rekurzivní, tj. existuje Turingův stroj M se vstupní abecedou {0,1}, který zastaví pro každé vstupní slovo a L(M) = Accept. Nechť v = code(M). Platí v e L (M)? • Ano. Pak v č L(MV) = L(M), spor. • Ne. Pak v e L(MV) = L(M), spor. Z předpokladu existence stroje M se nám podařilo odvodit spor. Stroj M tedy neexistuje. d Poznámka 85 V důkazu předchozí věty se objevuje určitá forma autoreference (stroj M zkoumá „sám sebe" tak, že analyzuje svůj vlastní kód). Každý známý důkaz věty o neúplnosti se o nějakou formu autoreference opírá. □ Ě5P _ = Š 29. září 2009 1 Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,^) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Věta o neúplnosti. Peanova aritmetika. Jedním z pokusů o vytvoření rekurzivní a úplné teorie aritmetiky byl následující systém nazývaný Peanova aritmetika (seznam Peanových axiómů bývá v literatuře uváděn v různých podobách): • Vx S(x) + 0 • VxVy S(x)=S(y) -> x=y • Vx x+0 = x • VxVy x+S(y) = S(x+y) • Vx x*0 = 0 • VxVy x*S(y) = {x*y) + x • (cp(0)AVx(cp(x)^cp(S(x)))) volnou proměnnou x. Vx(p(x), kde (p je formule s jednou □ g - = s Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Věta o neúplnosti. Peanova aritmetika. (2) Každou formuli jazyka aritmetiky je možné zapsat jako slovo nad abecedou {v, +, *, 0, S, (,),V, ->, ->, =, #}. Různé proměnné zapisujeme jako řetězce složené z v různé délky (např. místo x,y,z můžeme psát v, vv, wv apod.). Podobně můžeme i každou konečnou posloupnost formulí zapsat jako slovo nad výše uvedenou abecedou, kde symbol # použijeme pro oddělení jednotlivých formulí. Definice 86 Teorie T jazyka aritmetiky je rekurzivní, jestliže jazyk tvořený zápisy všech důkazů v T je rekurzivní. □ s - = & Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,^) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Věta o neúplnosti. Peanova aritmetika. (3) Lze snadno (i když technicky) dokázat, že např. Peanovy axiómy tvoří rekurzivní teorii. Definici rekurzivity teorie lze samozřejmě rozšířit i na teorie nad jinými jazyky. Rekurzivní teorie odpovídají (na intuitivní úrovni) právě teoriím, které umožňují „mechanické odvozování". Triviální pozorování o rekurzivních teoriích podává následující věta. Věta 87 Nechť T je rekurzivní teorie jazyka aritmetiky. Pak jazyk tvořený všemi formulemi dokazatelnými v T je rekurzivně vyčíslitelný. □ g - = & Matematická logika Antonín Kučera Věta o neúplnosti. Jazyk Valid. Uvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Nechť Valid resp. Provable jsou jazyky nad abecedou {v, +, *, 0, S, (,), V, ->, -i, =} obsahující zápisy všech formulí jazyka Peanovy aritmetiky, které jsou pravdivé v realizaci (N0/*,+) resp. dokazatelné ze systému axiomů Peanovy aritmetiky. Zjevně Provable c Valid, neboť Peanova aritmetika je korektní. Naším cílem je ukázat, že tato inkluze je vlastní, tj. že existují formule pravdivé v (N0/*,+), které nejsou z Peanových axiómů dokazatelné. Jelikož jazyk Provable je podle věty 87 rekurzivně vyčíslitelný, stačí ukázat, že Valid není rekurzivně vyčíslitelný (je vidět, že pak Provable + Valid i pro libovolnou jinou rekurzivní teorii aritmetiky). □ s - = & Matematická logika Antonín Kučera Věta o neúplnosti. Godelův predikát ß Uvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systém x(->,--) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Z hlediska důkazu věty o neúplnosti je jednou z podstatných vlastností přirozených čísel jejich schopnost „kódovat" libovolně dlouhé konečné posloupnosti přirozených čísel. • Definujeme 4-ární predikát ß na nezáporných celých číslech předpisem ß{a,b,i,x) <^=> x = a mod (1 +b(1 + /')) • Buď S nekonečná posloupnost nezáporných celých čísel, a,b e N0. Řekneme, že S splňuje ß (pro dané a ab), jestliže pro každé /' e N0 platí j8(a,b,/, S(i)). • Pro každé a, b e N0 existuje jediná posloupnost splňující ß; tou je posloupnost Sarb daná předpisem «Sa,/>(0 = a mod(1 + 0(1 + /')). • Predikát ß je vyjádřitelný v jazyce aritmetiky, neboť x = a mod b lze napsat jako a>0Aö>0A3/c(/c>0A k*b < a A (/c + 1)*b > a A x = a-(/c*b)) □ g - = & Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turinguv stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Věta o neúplnosti. Godelův predikát /». (2) Věta 88 Pro každou konečnou posloupnost n0, • • •, nk nezáporných celých čísel existují n, m e N0 taková, že ns = Sn,m{j) Pro každé 0 < j < k. To znamená, že pro každé 0 < j < k platíß(n, m, j, x) <^=> x = nľ Důkaz, (osnova) • Nechť m = (max{/c, n0/• • •,nk})\ Čísla p, = 1 + m(1 + /'), kde 0 < /' < k, jsou navzájem nesoudělná a n, < p, pro každé 0 < /' < k. • Dále pro každé 0 < /' < k definujeme C/ = Po.....Pk/Pi Nyní pro každé 0 < /' < k existuje presne jedno d,, 0 < d, < p,, takové, že (c, -d,) mod pi = 1 • Definujeme n = Yjcrdrni (=0 Pro každé 0 < /' < k platí n, = n mod p,, což je tvrzení věty. D □ S - = -E 29. září 2009 133/147 Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,^) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turinguv stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Veta o neúplnosti. Důkaz Věta 89 Jazyk Valid není rekurzivně vyčíslitelný. J Důkaz. Ukážeme, že existuje Turinguv stroj M, který pro každé vstupní slovo u nad abecedou {0,1} zastaví v konfiguraci, kdy je na pásce zapsáno slovo w nad abecedou {v, +, *, 0, S, (,), V, ->, ->, =} takové, že v e Accept právě když w e Valid. Pokud by tedy jazyk Valid byl akceptovaný nějakým strojem M', stačilo by „napojit stroje M a M' za sebe" a dostali bychom stroj akceptující jazyk Accept, což je spor. Stroj M pro dané vstupní slovo u e {0,1 }* „vypočítá" formuli jazyka aritmetiky, která říká „nenípravda, že stroj Mu akceptuje slovo u". □ g - = s Matematická logika Antonín Kučera Věta o neúplnosti. Důkaz. (2) Uvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Pozorování: Nechť yo---yď\e zápis iniciální konfigurace stroje Mu pro slovo u. Stroj Mu akceptuje slovo u právě když existují €, c e N0 a řetězec S nad abecedou l~u u Qu u {#} tvaru «0#«i # • • • a^# tak, že platí: • d < c; • délka (x\ je c - 1 pro každé 0 < /' < € ; • a0 je zápisem iniciální konfigurace Mu pro slovo u, doplněným zprava znakem ■_■ na délku c-1; • a\ i-» a,-+i pro každé 0 < /' < €\ • v řetězci at se vyskytuje akceptující stav stroje Mu. Cílem našeho dalšího úsilí je „zakódovat" podmínku z předchozího pozorování jako formuli jazyka aritmetiky. Klíčovým obratem je použití Gödelova predikátu ß, pomocí kterého vyjádříme existenci řetězce S. □ g - = š 29. září 2009 135/147 Matematická logika Antonín Kučera Věta o neúplnosti. Důkaz. (3) Uvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systém x(->,--) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Při kódování požadavku „a-, \-> «,+i pro každé 0 < ; < t se uplatní následující pozorování: existuje soubor C(MU) kompatibilních šestic tvořený (některými) šesticemi znaků nad abecedou l~u u Qu u {#} takový, že pro každou konfiguraci a délky c-1, každé slovo y nad abecedou ru u Qu u {#} délky c-1, a každý znak s této abecedy platí následující: a h» y a s = # právě když pro každé 0 < /' < c-3 tvoří trojice znaků od pozice i ve slově a# následovaná trojicí znaků od pozice i ve slově y s kompatibilní šestici (pozice ve slovech číslujeme od Oj. Soubor kompatibilních šestic lze pro každý Turingův stroj sestrojit algoritmicky na základě jeho přechodové funkce. Stroj M tedy dokáže vypočítat soubor C(MU) kompatibilních šestic stroje Mu. □ g - = & Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Věta o neúplnosti. Důkaz. (4) Každému a e l~u u Qu u {#} přidělíme jedinečné přirozené číslo [a]. Podmínku z předchozího pozorování pak zapíšeme jako 31 3c 3m 3n (d < c A INIT(m, n, c) A COMP(m, n, c,i) A ACC{m, n, c,l)) kde jednotlivé podformule vyjadřují následující: • „Posloupnost Smrn začíná zápisem iniciálním konfigurace Mu pro slovo u, doplněným zprava znakem ,_, na délku c-1. Pak následuje znak #". d INIT{m,n,c) = /\j3(m,n,/,[}//]) A ;=o V/(d )S(m,n,/,[u])) A ß{m,n,c-A,[if\) □ [fp ~ = -E 29. září 2009 137/147 Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost SystémX(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj I Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Věta o neúplnosti. Důkaz. (5) • ,,V posloupnosti Sm,n tvoří odpovídající trojice znaků v sousedních konfiguracích kompatibilní šestice". COMP{m,n,c,€) = V/' Vy ((/' < € A j < c-3) -> MATCH{m,n,i-c+ j,c)) kde MATCH(m, n, k, c) je formule TRlO{m, n,k, [a], [b], [c]) A TRIO(m, n,k+c, [d\, [e], [f]) {a,b,c,d,e,f)eC{Mu) TRIO{m,n,p,x,y,z) = ß(m,n,p,x)Aß(m,n,p+'\,y)Aß(m,n,p+2,z) „Poslední konfigurace je akceptující". (Předpokládejme, že akceptující stav stroje Mu je q.) ACC(m,n,c,£) 3; (/' , -i, =} a lze je tedy kódovat čísly stejným způsobem jako konfigurace Turingových strojů. Pro každou formuli cp označíme symbolem \cp\ číslo, které je jejím kódem. Lema 91 (Gödelovo lema o pevném bodě) Pro každou formuli i/>(x) existuje uzavřená formule t taková, že PA \- t <-» i/>(|t1). (Formule t říká „i/> platí pro můj kód".) Důkaz, (osnova) Pro libovolnou fixní proměnnou x0 lze sestrojit formuli SUBST(x,y,z), která říká následující: • „Číslo z je kódem formule, kterou získáme substitucí proměnné x0 za konstantu s hodnotou x ve formuli s kódem y." Např. Sl/BST(5,r i/;(y)) právě když AAhVy(y = ra(ľc7(xo)l)l^^(y)) • vy(y = rtx(r Hy)) = vy(y = m -> Hy)) • M \= Vy (y = při -> \\>{y)) právě když N \= ^(TtI) Předchozí argument se opírá o sémantickou ekvivalenci jistých formulí; ekvivalence těchto formulí je ale ve skutečnosti dokazatelná v PA. Např. PA h (Vy (y = M -> i//(y))) ^ ^(M) což je třeba v posledním bodu. Proto PA \- t <-» ^(fxl). n □ s - = š 29. září 2009 141/147 Matematická logika Antonín Kučera Věta o neúplnosti. Godelův důkaz. (4) Uvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost SystémX(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Věta 92 (1. věta o neúplnosti, Gödelova) Lze sestrojit uzavřenou formuli g, která je pravdivá v N, ale není dokazatelná v PA. Důkaz, (osnova) Ukáže se, že i důkazy (tj. konečné posloupnosti formulí) je možné kódovat čísly, a že existuje formule PROOF(x,y), která říká, že x je kódem důkazu (v RA) pro formuli s kódem y. Dokazatelnost v PA lze pak zapsat formulí • PROVABLE(y) = 3x PROOF\x,y) Pak pro každou uzavřenou formuli (p platí • PA v- cp právě když N \= PROVABLE^cpI) Dále lze ukázat • PA \-

-,PROVABLE{\q\) Pak ale musí platit N \= g; kdyby totiž N \= - <-> PROVABLE{\PROVABLE{\(p~\y\) I tato formule je v PA dokazatelná. ■ Bezespornost teorie PA lze vyjádřit formulí CONSIS = ^PROVABLE(\í A ^1), kde 4 je (nějaká) formule. □ g - = & Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Věta o neúplnosti. Tvrzení o RA v RA. (2) Jsou ale i metatvrzení o formulích aritmetiky, která jako formule aritmetiky vyjádřit nelze. Typicky se jedná o tvrzení týkající se pravdivosti. ■ Tvrzení „N |= ,--) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Věta o neúplnosti. 2. věta o neúplnosti Úvahy o vyjádřitelnosti některých vlastností teorie PA formulemi aritmetiky hrají klíčovou roli v důkazu následujícího tvrzení: Věta 93 (2. věta o neúplnosti, Gödelova) Je-li PA bezesporná, pak CONSIS není v PA dokazatelná. (Jinými slovy: v „dostatečně silné" teorii lze dokázat její vlastní bezespornost jen v případě, že je tato teorie sporná.) Důkaz, (osnova) Nechť g je formule zkonstruovaná v důkazu věty 92 (která o sobě říká, že je nedokazatelná). Uvažme následující metatvrzení: • „Jestliže PA \- g, pak platí PA \- PROVABLE([g~}) a současně PA h ^PROVABLE(Iq])u Toto tvrzení je nejen pravdivé, ale lze ho vyjádřit formulí aritmetiky, která je navíc dokazatelná v PA: • PA h PROVABLE(\gV) -> {PROVABLE{\PROVABLE{\Q\y\) A PROVABLE(\^PROVABLE(\g-\)~\)) Proto platí také PA v- PROVABLE^q\) -> ^CONSIS. □ g - - Š 29. září 2009 146/147 Matematická logika Antonín Kučera Úvod Aristotelova logika Logický čtverec Sylogismy Booleova algebra logiky Dva zákl. problémy Řešení 1. problému Řešení 2. problému Výroková logika Syntaxe Sémantika Plnohodnotnost Kompaktnost Systémx(^,-) Korektnost Úplnost Predikátová logika Syntaxe Sémantika Odvozovací systém Věta o úplnosti Věta o neúplnosti Turingův stroj Důkaz věty o neúplnosti Godelův důkaz 2. věta o neúplnosti Věta o neúplnosti. 2. věta o neúplnosti. (2) Obměnou uvedeného tvrzení dostáváme • PA h CONSIS -> ^PROVABLE{\q\] Kdyby PA v- CONSIS, platilo by také PA h -^P ROV ABLE {\ g~\) (aplikací MP). Už dříve jsme ale ukázali (viz důkaz věty 92), že • PA h g <-> ^PROVABLE{\q\] Další aplikací MP tedy dostáváme PA \- g. Výše jsme ale ukázali, že předpoklad PA \- g implikuje, že PA je sporná. Celkem tedy dostáváme, že předpoklad PA \- CONSIS implikuje, že PA je sporná. d Na intuitivní úrovni: druhá věta o neúplnosti říká, že bezespornost „dostatečně silné" teorie (např. teorie množin) nelze v této teorii dokázat. Jediná možnost je použít metaargumenty, tj. zdůvodnit bezespornost dané teorie pomocí teorie „vyšší". Ani bezespornost této vyšší teorie není ovšem možno prokázat v ní samé. Na nějaké úrovni nám prostě nezbývá, než v bezespornost uvěřit, resp. ji předpokládat. Gödelovy výsledky o neúplnosti mají tedy i svůj epistemologický význam. □ Ě5P _ = Š 29. září 2009 14;