Antonín Sochor Klasická logika_______ Univerzita Karlova v Praze Nakladatelství Karolinum 20OI PŘEDMLUVA Tento text pojednává o matematické logice na třech různě obtížných úrovních. Uroveň I: Úvod celého textu a úvody jednotlivých kapitol se snaží objasnit, o co jde v matematické logice a v jednotlivých jejích částech. Při tomto popisu se snažíme co nejvíce omezit použití symboliky. Tyto části textu by tedy měly být přístupné pro všechny, kteří se chtějí seznámit alespoň v nejhrubších rysech s idejemi, výsiedky a směřováním matematické logiky. Snaze intuitivné vysvětlit základní ideje matematické logiky odpovídá neobvykle značný rozsah těchto neformálních částí našeho textu. Mezi nejvýznamnější výsledky matematické logiky patří věty o neúplnosti. Üvod ke čtvrté kapitole je pokusem popsat tento velkolepý objev co nejintuitivněji. Přitom se snažíme dokonce o neformální prokázání vět o neúplnosti, nikoli o pouhé jejich vyslovení. K nejzajímavějším výsledkům matematické logiky náleží prokazování toho, že nějaký důkaz neexistuje. Intuitivní objasnění metod, kterými lze takovéto výsledky získat, nalezne čtenář v druhé částí úvodu k poslední kapitole. Tyto úvody jsou pochopitelně psány i pro ty, kteří se chtějí s matematickou logikou seznámit podrobněji a budou pokračovat rovněž ve čtení dalšího textu. Těmto čtenářům však doporučuji, aby se později k úvodům jednotlivých kapitol znovu vrátili. Myšlenky úvodů se pochopitelně více objasní po projití příslušné kapitoly — po přečtení podrobnějšího a formálnějšího textu bude čtenář hlouběji chápat intuitivní výklad obsažený v úvodu. V textu se snažím i o návaznost na historický vývoj pojetí logiky. Za zajímavé pokládám zejména případy, kdy přístup matematické logiky vyzdvihuje jako závažná přesně ta místa, která za důležitá pokládala i antická nebo scholastická logika. Chci zdůraznit ty principy, jejichž významnost je nahlížena jak z formálního, tak i z intuitivního hlediska. Úroveň II: Kapitoly I a II jsou určeny pro všechny zájemce o základy logiky. Zde se již nevyhýbáme formálnímu zápisu, ale snažíme se ho zpřístupnit podrobným intuitivním popisem významu jednotlivých symbolů. Poměrně velkou pozornost také věnujeme vyzdvižení nejdůležitějších idejí. Tento přístup nás nutí nezachovat postup běžný v literatuře, tzn. nebudeme popisovat výsledky v řadě za sebou, v pořadí daném pouze vhodnosti formálního dovozování. Snaha o zvýraznění nejzávažnějších myšlenek je formálně naplněna tím, že v jednotlivých paragrafech našeho textu je poměrně málo vět (v průměru pouze tři); snad takovéto zvýrazněni nejdůležitějších míst přispěje k přehlednosti textu. K tomu, co by měl z logiky umět používat každý matematik, však patří i věty o zavádění nových symbolů (tedy alespoň vety z prvého paragrafu třetí kapitoly bez prokazování). Za povšimnutí stojí rovněž rozbor implicitně používaných výsledků matematické logiky v „normálním" matematickém důkaze (viz počátek §1 kap. IV). -> PŘEDMLUVA Úroveň III: Zbytek textu je určen zájemcům o hlubší studium matematické logiky a může být čten po jednotlivých partiích, které na sebe příliš neodkazují. Takovéto relativně samostatné oblasti jsou zejména: (a) věty o neúplnosti aritmetiky (leap. IV); ve čtvrté kapitole jsou poměrně lehké první dva paragrafy, které mohou sloužit jako krásná cvičení pro dokazování v axiomatických teoriích, (b) teorie modelů (kap. V); (c) rozhodnutelnost teorií (viz §1 kap. VI); (d) interpretace (viz §3 kap. VI); (e) souvislost dokazatelnosti a výrokové dokazatelnosti (§2 a §3 kap. III); tato partie patří k obtížnějším. (f) nedokazatelnost Goodsteinovy věty v Peanově aritmetice (dodatek k poslední kapitole); tato část náleží k těm partiím knihy, které dosud nebyly dostupné v česky psané literatuře. S výjimkou páté kapitoly se v celé knize nepředpokládají žádné matematické znalosti. Naproti tomu (zejména pro čtení textů třetí úrovně) se předpokládá schopnost a zejména ochota myslet. K teorii modelů je potřeba znát základy teorie množin. Aby se čtenář mohl zabývat pouze předloženým textem, jsou potřebné úvahy předvedeny ve cvičeních (zejména ve třetí kapitole). Tato cvičení mají poukazovat na vše potřebné z teorie množin, ale svou stručností jsou koncipována spíše jako připomínka toho, s čím se již čtenář někdy alespoň v minimální míře seznámil. * V době psaní tohoto textu byla autorova vědecká práce podporována z grantu 1019901 GA AV CR. Kniha byla napsána v TeXu. Autor je velmi vděčen recenzentům Prof. P. Hájkovi, DrSc. a RNDr. M. Matouškovi, CSc. za cenné připomínky a návrhy, které vedly ke zkvalitnění předkládané knihy. Poděkování náleží také kolegům K.Bendové, J. Kraj íčko vi, P. Pudlákovi a J. Sgallovi za rady a diskuse nad textem. Autor děkuje zejména L. Běhounkovi za pozorné přečtení textu a za připomínky, které značně přispěly ke zvýšení kvality knihy. Poděkování patří rovněž J. Hanákovi, Z. Honzíkové-Hanikové, R. Honzíkovi a M. Rösslerovi, kteří přečetli rozsáhlé části této knihy a poskytli cenná upozornění a dále také M. Pelišovi a B. Sobotkové za připomínky k některým částem textu. Děkuji také J. Mazúrkové, která napomohla zlepšit jazykovou stránku textu velice podstatným způsobem. Své ženě děkuji nejen za to, že pretrpela mé zahledění na práci na tomto textu, avšak také za to, že přitom byla ještě schopna pomoci odbornou radou ke zkvalitnění knihy. Přes to vše zůstává v knize mnoho nedopatření, nejasností a velice pravděpodobně i chyb. Prosím všechny, aby mě na tato místa upozornili; takováto pomoc mí případně umožní nabízet errata, a tím napomůže pozdějším studentům. A.S. ', ÚVOD Jak užívá rozum sebe sama? Neboť na tam záleží nejvíc! Marcus Aurelius, Hovory k sobě Většina příslušníků druhu homo sapiens si váží rozumu. Tato úcta k rozumu jde tak daleko, že pro (téměř všechny) středověké myslitele je dokonce i všemohoucí Bůh „podřízen" rozumu (sv. Tomáš Akvinský v Teologické sumě: „Odpovídám: Musí se říci, že pod všemohoucnost Boží nespadá, co obsahuje odporování."). Považujeme za samozřejmé, že umíme správně uvažovat, ale téměř nikdy si neklademe výslovně otázky typu: Nemůže nastat situace, kdy samo usuzování nás dovede do neřešitelných rozporů? Co to doopravdy znamená něco dokázat? V jakém rozsahu může být při dokazování (matematikova) intuice nahrazena mechanickým kalkulem? Existují meze našeho myšlení? Shodujeme se všichni v tom, co je správné usuzování? — Těmito a mnohými podobnými otázkami se zabývá matematická logika a alespoň v minimální míře budou předmětem i tohoto textu. Již na začátku však zdůrazněme, že v logice jde o to, jak usuzujeme (jak máme správně vyvozovat důsledky), a nikoli na podkladě čeho k závěrům přicházíme, neboli není předmětem logiky zkoumat, jakým způsobem a proč volíme předpoklady. Ověřování předpokladů, z nichž vyvozujeme (odvozujeme) důsledky, je otázkou zkušenosti, jiné vědy, nebo víry (přijímané někdy vědomě, často však podvědomě). V matematické logice se dokonce nestaráme o to, zda a v jakém smyslu jsou předpoklady pravdivé, ale pouze o to, zda je správné vyvození, a to může být správné i v případě, že předpoklady nejsou správné. Logika formuluje explicitně ty zdůvod-ňovací (dokazovací) kroky, které pokládáme intuitivně za správné a zkoumá takto vzniklý systém. Při takto vymezeném oboru zkoumání, matematické logice nepřísluší řešit otázku, zda postihuje celé lidské myšlení, tzn. jesth se rozum projevuje i jinými způsoby než vyvozováním důsledků z předpokladů. Naproti tomu ve vymezené oblasti — a je to oblast pokrývající podstatnou oblast lidského rozumu — dosahuje matematická logika hlubokého poznání. * Na základě středověkého chápání definujeme obvykle logiku jako vědu o správném uvažování, i když původní řecké chápání bylo poněkud širší (logos má více významů: řeč, slovo, myšlenka, rozum, smysl, etc.). Není účelem tohoto textu zkoumat dějiny logiky, učiňme jen několik poznámek. Za zakladatele logiky je pokládán Aristoteles {384-322 př. Kr.), který v Organonu11 podává systematický popis některých typů uvažování a odděluje správné úvahy l> viz [A] 7 i Vi ID od nesprávných. Aristoteles sice píše, že „v oboru tohoto našeho zkoumání ... nebylo započato vůbec nic", ale již u jeho předchůdců2' lze doložit užití logických principů, souvisejících zejména s principem sporu (Zénón z Eleje asi 490-430), u Platóna (427-347) např. princip typu jestliže z předpokladu A vyplývá negace A, pak platí negace AH. Doba rozkvetu logiky u Řeků trvala asi 150 let. Na Aristotela navazuje Theoťrastos z Eresu (asi 371-286, pokládaný také za zakladatele botaniky). Současně se rozvíjí zkoumání v Megarské škole, kde vynikají zejména Eukleidés z Megar (lat. Euclides) (f360 př. Kr.)3', Diodóros Kronos (f307 př. Kr.) a Filón z Megar (kol. 300 př. Kr.). Pokračovateli jsou stoikové Zénón z Kitia (asi 334-262, zakladatel stoické filozofie) a Chrýsippos ze Soloi (asi 281-208), který se udává jako poslední z velkých řeckých logiků41. Ze starověkých logiků je třeba ješté uvést Galéna (129-199, známého zejména jako lékaře) a Boethia (asi 480-524/5), který svými (komentovanými) překlady do latiny zprostředkoval antickou logiku pozdějším učencům. Na antické výsledky navázali středověcí myslitelé, např. formulaci dalších principů logiky. Vrchol scholastické logiky je kladen krátce po jejích začátcích, tzn. do 13. stol.; po 14. stol. nastává útlum. Jako představitele uveďme pouze Alberta Velikého (1193-12S0), jehož výklad Aristotelových spisu měl veliký význam pro další rozvoj logiky, Petra Hispánii (1210-1277, pozdějšího papeže Jana XXI), Dunse Scota (asi 12G4-13U8, tvůrce rilozoficko-teologického směru, který dokázal soupeřit sesměrem Tomáše Akvinského) a Wdiama Occama (1270-1347, známého formulaci tzv. Occamovy břitvy). Scholastická systematičnost ovlivnila nejen následující pojetí logiky, ale i její výuku, V minulém století začíná rozvoj matematické (symbolické) logiky, vyvolaný zejména potřebou upřesnit základy matematiky a zpřesnit pojmy matematické analýzy5'. Logickými paradoxy se zabývali již antičtí myslitelé (viz dále), nicméně objevení paradoxů v teorii množin6' přineslo další podnět k intenzivnímu zkoumání logiky. Uveďme alespoň krátký seznam význačných představitelů'' matematické logiky: pražský rodák B. Bolzano (1781-1848), G.Boole (1815-1864), A.de Morgan (1806-1871) G.Frege (1848-1925), G. Peano (1858-1932), D. Hubert (1862-1943), B.Russell (1872-1970), A.Tarski (1901-1983), Th.Skolem (1887-1963), A. Church (1903-1995), J.Herbrand (1908-1931), A.Turing (1912-1954), G.Gentzen (1909-1945, který v Praze přednášel, ale bohužel8' i zemřel), a zejména brněnský rodák 2) O antické logice se čtenář doví více např. v [Bo], [Be], [Kn-Kn] nebo v [So]. Ve dvovi posledně citovaných knihách je také popsána historie středověké logiky a počátky matematické logiky, Životopisné údaje o logicích staiSi doby se v různých pramenech liší, jedná se však o minimální rozdíly. 3' Eukleidés z Megar byl žákem Sokratovým, Aristoteles pak následovníkem Sokratova žáka Platóna, i to podpírá domněnky o vlivu Sokrata na vznik logiky. 4) Výsledky stoicko-megarské školy je bohužel nutno rekonstruovat z pozdějších prací, původní práce jsou ztraceny. 51 V r. 1879 publikoval Frege spis o predikátové logice [F] a v důsledku toho nékdy bývá tento rok spojován se vznikem matematické logiky. Jíní spojují počátek matematické logiky s prací G. Boolea [Boo] z r. 1854. V každém případe je vsak zjednodušením koncentrovat déiedobý proces vzniku této disciplíny na jediného představiteli; či na jedinou práci. 5> Z paradoxů teorie množin se zmíníme v našem textu pouze o nejznámějším, tj. Russellově paradoxu, viz cv. 29 kap. III. 7) Krátké poznámky shrnující životopisná data a nejvýznamnější publikace některých významných logiku nalezne čtenář např. v práci [,1-V]. ft) viz P. Vihan, Zpráva o posledních měsících a dnech Gerhaida Gentzena prožitých v Praze, S ÚVOD K. Gödel (1906-1978); ze starších autorů pak obzvláště G. W. Leibniz9' (1646-1716). Jména některých matematiků, kteří měli podstatný vliv na rozvoj teorie modelů najde čtenář u jednotlivých výsledků v páté kapitole. ' * Slovní spojení „matematická logika" má zdůraznit, že pro zkoumání našeho uvažování se často používají metody běžné v matematice. Význačným rysem matematické logiky jsou tedy ideatizace a fnrmalizace našeho usuzování. Zanedbáváme při tomto přístupu veškeré psychologické aspekty a zůstávají nám jen postupy, které je možno kdykoli znovu opakovat; dokonce ověřování, zda naše usuzování bylo korektní, je již natolik mechanické, že je lze svěřit stroji (při hledání cesty, která vede k prokázáni tvrzení, se však uplatňuje lidská intuice). Aspekt formalizace je tak výrazný, že se často mluví í o symbolické logice. Formalizace usuzování (dokazování) jednak vede k přesnému vymezení, co usuzováním rozumíme, a jednak umožní myslet o myšlení, přesněji řečeno myslet o formalizovaném myšlení. Otázka, zda formalizace usuzováni popsaná matematickou logikou skutečně vystihuje lidské usuzování, přísluší spíše do oblasti filozofie nebo psychologie a nebudeme ji soustavné diskutovat (i když později uvedené motivace základních odvozovacích principů matematické logiky lze také chápat jako argumentaci, že tyto principy skutečně popisují naše usuzování). Zdůrazněme ale, že právě formalizace umožnila ukázat řadu hlubokých vět o našem (takto vymezeném) usuzování, * Formalizace usuzování je podstatná i vzhledem k (logickým) paradoxům, ke kterým nyní obrátíme svou pozornost. Jak byste rozhodli, kdyby někdo zkoušel vaši soudnost stejným způsobem, jako je zkoušen Sancho Panza v druhém dílu Cervantovy knihy Duchaplný rytíř Don Quijote de la Mancha? Před Sancha předstoupil jakýsi muž a řekl: „Pane, velká reka dělila panství na dvě části, přes tu řeku vedl most a na jeho konci stála šibenice a pán té řeky, toho mostu a celého toho panství vydal zákon, který zněl takto: .Kdokoli chce přejít po tomto mostě, musí nejdříve odpřisáhnout, kam má namířeno a co tam hodlá dělat; a jestliže bude přísahat podle pravdy, budiž ihned propuštěn na druhou stranu, selže-li však, ať zemře na této šibenici, a nikomu nebudiž udělována milost!' Co se však jednou nestalo! Když vzali zase do přísahy jednoho člověka, prohlásil a odpřisáhl jim, že přišel jenom proto, aby skončil svou pozemskou pouť na té šibenici u mostu a za jinou záležitostí prý nepřišel. Soudcům byla ovšem ta přísaha divná a řekli si: ,Pustíme-li toho muže svobodně na druhou stranu, pálí nám tu právě křivě přísahal a podle zákona by měl skončit na šibenici, a jestliže ho dáme oběsit, sám přece přísahal, že sem přišel, aby zemřel na šibenicí, a kdo podle pravdy přísahá, má být podle téhož zákona propuštěn bez překážek.' A teď je na vás, pane vladaři, abyste sám rozhodl, co by měli ti soudcové udělat s oním mužem, neboť Pokroky matematiky, fyziky a astronomie 38 (1993), 291-296 ^J Leibnizův přínos spočívá zejména v ideji matematizace ostatních věd. Matematizace se stala jedním z nejdůležitějších rysů matematické logiky. 9 ÚVOD nevědí kudy kam a jde jim již z toho hlava kolem." Cervantův Sancho si uvědomil logický paradox a řekl: „Ten váš pocestný může zrovna tak lehce skončit na šibenici jako zůstat naživu, neboť pravda ho před smrtí ochrání a lež ho na smrt odsuzuje." Sancho proto doporučil onoho člověka propustit a (mimologickým) odůvodněním: „Když mají soudci stejně mnoho důvodů k tomu, aby jej na hrdle potrestali, jako k tomu, aby jej osvobodili, ať ho jen nechají přejít volnou nohou na druhý břeh, neboť chvályhodnější je přece vždycky konat dobro než rozmnožovat zlo. . .. Je-li spravedlnost na váhách, je lépe upustit v oné věci od trestů a přiklonit se spíše k milosrdenství." Analogické paradoxy je možno nalézt již u starších autorů10' Nejznámější je paradox lháře (chápaného jako člověka, který nikdy nemluví pravdu) připisovaný11' Eubúlidu z Milétu (4. st. př. Kr.). Paradox je tradován ve dvou verzích: „Kréťan Epimenidés řekl, že všichni Kréťané jsou lháři" nebo „V tomto okamžiku lžu" — ozvěnou první verze je pravděpodobně i verš 1,12 listu sv. Pavla Titovi: „Jeden z nich, jejich vlastni prorok, řekl: Kréťané jsou lháři ..."; druhá verze je citována Ciceronem (106-43 př. Kr): ,,Jestliže po pravdě řekneš, že lžeš, lžeš?". Uvědomme si, že první verze není neřešitelným paradoxem: pokud Epimenidés mluví pravdu, pälrkäždý Kréťan (a tedy i on sám) lže — spor; jestliže však Epimenidés lže, pak neplatí, že všichni Kréťané jsou lháři; za negaci výroku „všichni Kréťané jsou lháři" však považujeme výrok, že existuje alespoň jeden Kréťan, který mluví pravdu (alespoň někdy), a tedy pokud existují nejméně dva Kréťané, tak spor nedostáváme. V druhé verzi dostáváme spor v obou případech úplně stejně, jako se do sporů dostal Sancho12'. Z novějších uveďme ještě Berryho paradox. Existuje přirozené číslo, které nelze v češtině popsat pomocí méně než třiceti slabik, neboť všech slabik, a tedy i všech jejich (uspořádaných) třicetic je jen konečně mnoho. Nejmenší přirozené číslo, které nelze popsat pomocí méně než třiceti slabik, je však popsáno méně než dvaceti sedmi slabikami13'. Předchozí paradoxy14' jsou založeny na tom, že výpověď se vztahuje sama na ln' Podobný předchozímu je např. stoický paradox krokodýla, který můžeme formulovat následovně: Krokodýl unesl dítě a slibuje matce, že ho vrátí, právě když odpoví po pravdě na Dtázku „Vrátím dítě?" — pokud žena odpoví ANO, může krokodýl dítě vrátit i nevrátit a vždy dostojí svému slibu, odpoví-li žena NE, nedostoji krokodýl svému slibu nikdy. Do souvislosti s antickými paradoxy se sluší zasadit také známý Sokratův výrok, který je vybrán jako motto ke čtvrté kapitole. 1]) dle Diogérra Laertia '3' Snaha o řešeni se výrazně objevuje již v antice, napr. Aristoteles uvažuje některé věty jako pravdivé, ale lživé v nějakých aspektech. Filitás z Kou (340-285) se prý paradoxem tak zabýval, až „lhář ho zabil". l3) Poznamenejme, že v češtině se podstata Berryho paradoxu krásně projevuje již při jeho formulaci, protože kdybychom v popisu čísla nahradili slovo „třiceti" slovy „dvaceti sedmi", tak by počet slabik v popisu vzrostl na 2S, bylo by třeba tedy slova „dvaceti sedmi" nahradit slovy „dvaceti devíti", ale při tomto popisu počet slabik opět vzroste — na 21>. Paradox byl publikován v knize [W-R]. 14' Radu dalších paradoxů je možno nalézt v roztomilé knize [Smi). Bude-Li čtenář pozorný, jisté si povšimne, že volba mnohých paradoxů v citované knize směřuje k objasnění první věty o neúplnosti, kterou se v našem textu budeme zabývat v kap. IV. 10 ÜVOD sebe — napr. výpověď „lžu" aplikujeme na tuto větu samu, a z toho vyvozujeme, že není pravda, že lžu. Ve snaze odstranit paradoxy navrhl B. Russell15' rozdělovat myšlení do různých hladin (viz [W-R]), neboť tak se vyloučí vlastnosti, které lze aplikovat na sebe. Popisovat výpovědi z nějaké hladiny a rozhodovat o jejich pravdivosti je totiž v Russellove pojetí povoleno pouze z hladiny vyšší. V našem textu vystačíme se dvěma hladinami, k jejich přesnějšímu popisu se za okamžik vrátíme. * V prvních kapitolách textu zachováváme tradiční rozděleni na výrokový a predikátový počet, které se datuje již od antiky, neboť Aristoteles a jeho následovníci se zabývali predikátovým počtem, stoicko-megarská škola pak počtem výrokovým16'. Stoikové dokonce kladou základy axiomatického přístupu k výrokovému počtu17'. Vztah výrokového a predikátového počtu lze — s vědomím, že každé přirovnání je nepřesné — přirovnat ke vztahu chemie a fyziky. Chemie zkoumá jednu velikostní úroveň (molekulovou) hmotného světa a úrovně nižší (atomární a subatomární) i vyšší (fyziku těles) zkoumá fyzika; analogicky můžeme chápat, že výrokový počet vyděluje „střední" úroveň matematické logiky. Výrokový počet totiž zkoumá vlastnosti logických spojek a základním pojmem je přitom pojem výroku (nebo pojem výrokové proměnné), jehož strukturu již tento počet dále neanalyzuje. Naproti tomu predikátový počet se zajímá o predikáty, proměnné a logické funkce, na jejichž základě se vytvářejí výpovědi, kterým je přiřaditelná pravdivostní hodnota (výroky). Zkoumání tohoto druhu se dá chápat jako práce na úrovni „nižší", než je úroveň výrokového počtu. Dále predikátový počet pracuje s kvantifikací a formule se současně budují pomocí logických spojek a kvantifikátorů (v tomto směru jsou tedy logické spojky a kvantifikátory chápatelné na „stejné" úrovni a jejich užití opakovaně alternuje). Nicméně věta o prenexním tvaru (viz §5 kap. II) ukazuje na možnost posunout kvantifikaci až na závěr tvorby formule, a tento výsledek lze chápat jako možnost odsunutí tohoto prostředku predikátového počtu až na úroveň „vyšší", než je popis chováni logických spojek. Je zřejmé, že není třeba výrokový počet vydělovat a celou matematickou logiku je možno zkoumat najednou. Mnozí autoři takto postupují, neboť je to rychlejší a protože některé úvahy je možno provést najednou pro celou matematickou logiku. Při rozhodnutí, zda pojednat o celé matematické logice najednou, záleží tedy zejména na vkusu pisatele, dá-li přednost postupu od jednoduššího ke složitějšímu, anebo zvolí-li sevřenost výkladu. K oddělení zkoumáni výrokového a predikátového počtu nás vedou zejména následující důvody: 1) Popis vlastností logických spojek je nutno v každém případě provést. Metodou celé matematiky je abstrakce, která umožňuje prozkoumání toho jevu, který je právě zkoumán, očištěného od jevů dalších. V případě výrokového počtu tuto abstrakci neprovádíme ve snaze proniknout hlouběji (stejně důkladný rozbor můžeme a většinou dokonce musíme provádět i v případě, že celou matematickou logiku zkoumáme najednou), ale snažíme se její pomocí více vyzvednout specifické vlastnosti implikace a negace (na rozdíl od kvantifikace). 2) Výrokový počet je podstatně jednodušší a je možno v něm ukázat mnohé metody, které jsou pak ve složitější formě popsány v počtu predikátovém, tedy zvolený přístup je méně náročný a usnadňuje pochopem podstaty mnohých technik. 15) Russell je znám také svým paradoxem v teorii množin: zopakujme citaci cv. 29 kap. III. 16) V textu připisujeme některá pravidla výrokového počtu Rekům mimo tuto školu. Avšak takovéto odkazy je možno učinit pouze s licencí, že se odkazujeme na pravidla, která používali v případech, které dnes formalizujeme formulemi 3 predikáty. í7> viz cvičení 7 k první kapitole 11 ÚVOD Napr. sémantiku výrokového počtu je možno formulovat tak, že vystačíme s jediným modelem, sémantiku počtu predikátového nikoli; výrokový počet je rozhodnutelný (tedy v jistém směru „jednoduchý") a predikátový nikoli (podrobnosti viz dále). 3) O tom, v jakém smyslu lze omezit dokazování v predikátovém počtu na prostředky odpovídající počtu výrokovému, vypovídají poměrně hluboké věty uvedené v kap. III (zejména Hilbert-Ackermannova věta). Zdá se, že pochopení podstaty těchto vět usnadní předchozí samostatné zkoumání výrokového počtu. * Podle jiného hlediska dělíme logiku na syntax (zabývající se otázkou dokazatel-nosti) a sémantiku (zkoumající pravdivost)18'. Základním vztahem mezi sémantikou a syntaxí jsou věty o korektnosti a úplnosti (tzn. dokazatelné jsou právě všechny pravdivé formule, viz §3 kap. I a §5 kap. II). * Uvedli jsme, že při formalizaci myšlení je vhodné rozlišit dvě hladiny vyjadřování: hladinu („vyšší"), na které formalizaci provádíme, tzn. na které budujeme výrokový a predikátový počet, a hladinu výrokového a predikátového počtu (hladinu „formalizovaného myšlení1'). Podstatné je, že obě hladiny by měly zachycovat náš způsob myšleni, každá ale v jiné podobě. Na hladině „vyšší", kterou nazýváme meta-matematikou, provádíme intuitivní (neformalizované) úvahy a používáme běžného jazyka. Naproti tomu pro „nižší" hladinu (hladinu matematiky) budeme přesně definovat (z pozice metamatematiky) pojmy jazyka, formule, důkazu a dokazatelnosti (syntax) a pojmy modelu, splnitelnosti a pravdy (sémantika). Zopakujme, že rozlišením dvou hladin myšlení jsme schopni do značné míry {i když ne zcela) se vyvarovat „aplikace vlastnosti na sebe samu"; tímto způsobem odstraňujeme paradoxy výše uvedeného typu. V jakém smyslu zůstávají zbytky možnosti aplikovat vlastnost na sebe samu, budeme zkoumat ve čtvrté kapitole; v žádném případě však tyto úvahy už nevedou k paradoxům. V souvislosti s představou zkoumání formalizovaného myšlení z pozice metamatematiky neodolám a uvedu: „Rozum, právě tak jako oko, zatímco nám umožňuje vidět a vnímat ostatní věci, nezaznamenáva sám sebe; vyžaduje obratnost a úsilí po-odsunout ho na jistou vzdálenost a učinit ho sobě samému objektem" (John Locke, Esej o lidském rozumu). * Rozlišením hladin myšlení se zvýrazní otázka, co minimálně musíme vzít za „intuitivně zřejmé", tzn. jak silnou metamatematiku musíme předpokládat. Nejprve popíšeme několik přijatelných postojů, později budeme také argumentovat pro to, že naléhavost otázky po síle metamatematiky se jeví zcela různě z hlediska filozofie a matematiky. Pokud by se čtenáři zdály Tiásledující úvahy nadbytečné a vynechal by je, nechť se k nim vrátí před čtením úvodu kap. III. zejména však před kap. IV. 181 Syntax je možno popsat jako nauku o znacích jako takových a o vztazích mezi nimi. Sémantiku pak popíšeme jako nauku o významech znaků. L2 ÚVOD Přijetím potenciálního nekonečna rozumíme přijetí možnosti bez omezení aplikovat kdykoli znovu a znovu nějaký zvolený postup, např. postup „přičítám jedničky". Přijetím aktuálního nekonečna rozumíme akceptaci nekonečného souboru jako jednoho celku (akceptaci nekonečné množiny)19'. Nejprve si uvědomme, že postoj, který neakceptuje v potřebné míře ani potenciální nekonečno, nedostačuje pro vybudování formalizovane logiky. Bez předpokladu potenciálního nekonečna totiž není možné provádět ani nejjednodušší úvahy matematické logiky, např. bychom nemohli ani negovat každou formuli (teď mluvíme o existenci negace formule a nikoli o tom, zda tato negace je s něčím již dříve sestrojeným ekvivalentní}, nebylo by již možno definovat níže popsaným způsobem formule, a to ani výrokového ani predikátového počtu, o pojmu důkazu už vůbec nemluvě, etc. Vše by muselo být omezeno na předem danou složitost. Proto se postoj následně uvedený jako první možnost jeví jako nejslabší možný pro vybudování matematické logiky. 1) První možností tedy je přijmout v metamatematice potenciální nekonečno, ale aktuální nekonečno již neakceptovat. Z filozofického hlediska je poněkud protismyslné popisovat intuitivní postoj formální teorií, ale připusťme na okamžik takovýto popis jako výraz snahy o přesnější vymezení. Uvedenému finitnímu postojí by tedy odpovídala buďto Peanova aritmetika PA (viz §2 kap. IV), nebo teorie konečných množin ZFf\u (Zermelo-Fraenkelava teorie ZF }e popsána ve cv. 14 kap. III; ZFy\a je teorií ZF. ve které je axiom nekonečna nahrazen svojí negací. Teorie PA a ZF$-Ia jsou „stejně > silné", záleží jen na vkusu, zda dáte přednost jazyku teorie množin či aritmetiky21^). Potřebu jakési22' aritmetiky (potenciálního nekonečna) v metamatematice můžeme chápat jako podporu známého Kroneckerova výroku „Přirozená čísla jsou od Boha, ostatní vymysleli lidé.". Zastánci popisovaného postoje mají dostatek prostředků pro tvorbu syntaxe a ověření všech jejích tvrzen! uvedených v textu, a to jak výrokového tak predikátového počtu. V sémantice výrokového počtu potřebujeme při zkoumání k výrokových proměnných prověřit 2fc případů. V současném kontextu je podstatné, že takovýchto případů je pouze konečně mnoho, a tedy i sémantika výrokového počtu je zvládnutelná při uvedeném postoji (podrobněji viz §§1,3 kap. I). Naproti tomu model v predikátovém počtu definujeme (viz §2 kap. II) jako množinu spolu s některými relacemi na této množině. Většina matematicky zajímavých teorií má pouze nekonečné ' Ke vztahu potenciálního a aktuálního nekonečna přičiníme ještě několik poznámek v úvodu ke třetí kapitole. Je vsak potřeba zdůraznit, že přijetím potenciálního či dokonce aktuálního nekonečna nezpochybňujeme, že pro některé problémy je vhodné se omezit na konečné soubory (např. konečně mnoho výrokových proměnných a formule pouze určité složitosti), Mí viz první dva příklady §3 kap. VI **) Z těchto dvou možností se zdá intuitivnější použít pojmu teorie množin, a toto budeme činit v následujících paragrafech i my. I\ možnosti použít jazyk aritmetiky se velmi důkladně vrátíme v §3 kap. IV 22) Peanova aritmetika nezaručuje pouze existenci libovolně velkých přirozených čísel, ale jejím podstatným rysem je možnost indukce. Této možnosti při budování matematické logiky podstatně využijeme, řadu tvrzení budeme prokazovat indukcí. Nicméně pokud připustíme možnost formálního popisu metamatematiky, je namístě zkoumat i otázku, zda indukci (ekvivalentně schéma nahrazení v teorii konečných množin) potřebujeme v plné šíři. Úvahy tohoto druhu budou vedlejším produktem zkoumání ve čtvrté kapitole (ukážeme, že stačí indukce pro vlastnosti omezené složitosti). 13 ÚVOD modely. Důsledný finitista se proto musí obejít bez převážné části sémantiky predikátového počtu. Gödelova věta o úplnosti (viz §5 kap. II) v oboru konečných modelů prostě neplatí. To vede k tomu, že zastáváte-li uvedený postoj, nemůžete např. použít demonstraci (ryze syntaktické) věty o zavedení funkce provedenou sémantickými prostředky a uvedenou v §1 kap. III. ale musíte použít podstatně obtížnější cesty, např. demonstrace popsané v §3 téže kapitoly. 2) Druhý možný postoj je akceptovat aktuální nekonečno v „omezené míře"; takovýto postoj není mezi matematiky příliš rozšířen, zmiňujeme ho jen pro úplnost. Uvedený postoj by odpovídal např. Godel-Bemaysově teorii konečných množin GBpla (v GÖ-del-Bernaysově teorii GB, popsané ve ovH 21 kap. III, nahradíme opět axiom nekonečna jeho negací). Nyní sice stále nemáme nekonečné množiny, ale máme objekty (třídy), které jíž nekonečné jsou. (Každá množina je třídou, ale existují třídy, které nejsou množinami. Např. stále neexistuje množina všech přirozených čísel, ale existuje třídu — tedy objekt teorie — všech přirozených čísel.) Při akceptaci tohoto postoje můžeme definovat modely zcela analogicky, jak je popsáno dále v textu, ale nebudeme vyžadoval, aby jejich univerzum bylo množinou; připustíme, že je pouhou třídou. Při práci s třídami máme v uvedené formální teorii podstatně omezenější prostředky ne?, pro práci s množinami, ale GSdelovu větu o úplnosti již jsme schopni ukázat23*. 3) Poslední možností je plně akceptovat aktuální nekonečno. V tomto případě již jsou prostředky naprosto dostačující pro vše, co bude dále popsáno. Formalizací tohoto postoje je například Zermelo-Fraenkelova teorie množin ZF, ale můžeme uvažovat i její různá zesílení a popřípadě i oslabení. Při tomto přístupu se objevují problémy zcela nového druhu. Nyní máme škálu různých typů modelů a je zapotřebí zkoumat, které předpoklady (např. dodatečné axiomy) zaručují existenci modelů daných vlastností. Touto problematikou se zabývá teorie modelů, které se v tomto textu budeme věnovat v omezené míře v páté kapitole. Při podrobnějším rozboru je však situace i při popisovaném postoji složitější. Pto demonstrací věty o kompaktnosti použijem* nějakou forum axiomu výběru (formulaci tohoto axiomu viz §3 kap. I; v citovaném paragrafu dokonce ukážeme, že se bez nějakého předpokladu tohoto typu neobejdeme), O axiomu výběru je známo, že není v teorii množin dokazatelný (pro ZF viz [C]) a současně konstrukce konstruktivních množin zaručí i nedokazatelnost negace axiomu výběru (viz [G4]); je proto nejen možné, ale také vhodné začít rovnou v ZF s axiomem výběru již od samého počátku. Při zkoumání teorie modelů v kap. V se ukáže žádoucí pro některé úvahy přijímat dokonce podstatně silnější předpoklad, totiž zobecněnou hypotézu kontinua. Volba některého z předchozích stanovisek je podstatně důležitější z hlediska filozofie než z hlediska matematiky. Z filozofického hlediska je totiž hladina metama-tematiky pevně dána, neboť by měla popsat intuitivní postoj člověka. Naproti tomu v rámci matematiky lze (a často to také děláme, viz např. kap. rV) sílu metamate-matiky měnit. Můžeme např. na začátku skutečně začít na intuitivní hladině a vybudovat axiomaticky popsanou teorii (např. aritmetiku nebo teorii množin). V této teorii pak máme nebo vybudujeme přirozená čísla — nazývejme je formálními24' příp. matematickými přirozenými čísly. Tato formální přirozená čísla nemusí být totožná s intuitivními přirozenými čísly (přesněji: mohou existovat formální přirozená 23' Jiné teorie majíc) pouze konečné množiny, ale připouštějící nekonečné třidy jsou (v pořadí respektujícím mírné zesilování teorií) Kelley-Morseova teorie konečných množin a Vopěnkova alternativní teorie množin, kterým svoji silou odpovídají aritmetiky druhého či třetího řádu — v aritmetice druhého řádu připouštíme existenci množin přirozených čísel, v aritmetice třetího rádu dokonce existenci množin, jejichž prvky jsou množiny přirozených čísel, etc. 24' Nyní používáme výraz „formální" v poněkud jiném významu než dříve při vysvětlování symbolické logiky. L4 OVOD čísla, která v přirozeně popsatelném smyslu neodpovídají žádným metamatematic-kým přirozeným číslům). Analogicky můžeme uvnitř axiomaticky popsané teorie vybudovat „formalizovanou matematickou logiku". Přesněji řečeno teorii, která dříve byla na „nižší" hladině, začneme pokládat za hladinu metamatematiky a na její úrovni počneme budovat matematickou logiku. Opět nemusí původní matematická logika korespondovat s takovouto formalizovanou matematickou logikou. K upřesnění vztahu metamatematíckých a formálních přirozených čísel se v textu ještě několikrát vrátíme (viz např. §5 kap. II); formalizace matematické logiky je velmi podrobně popsána v kap. IV. Z ryze praktického hlediska uvidíme ve třetí kapitole, že přijetí jednoho z uvedených stanovisek ovlivní snadnost prokázání jedné a téže věty. Ve čtvrté kapitole se pak ukáže vhodné alespoň na okamžik zaujmout postoj přijímající pouze potenciální nekonečno. Naproti tomu v páté kapitole pohlédneme — byť jen klíčovou dírkou — na bohatství možností, které se otevřou přijetím aktuálního nekonečna. * V „nižší1' hladině budeme mít důkazy definované z pozice metamatematiky a z téže pozice budeme o těchto důkazech „dokazovat" různá tvrzení. Abychom se snadněji orientovali, budeme pro „důkaz" v rovině metamatematiky používat termínu demonstrace. Termín „věta" je v matematice běžně používán pro dokazatelné tvrzení v nějaké teorii a pro rozlišení je pak v metamatematice používán pojem „metavěta". V tomto smyslu jsou všechna tvrzení v textu metavětami, a to nám umožní v této souvislosti předponu „meta-" vynechávat bez nebezpečí nedorozumění. * V celém textu se zabýváme pouze logikou prvního řádu. V logikách vyšších řádů je povolena nejen kvantifikace (individuových) proměnných, ale i kvantifikace formulí; v mnoha ohledech jsou složitější než běžná logika a v některých vlastnostech se od ní podstatně liší. Uvidíme, že celá „běžná" matematika je formulovatelná v jazyce prvního řádu. Dále se také omezujeme na dvouhodnotovou logiku, o možnosti více-hodnotové, modálni a fuzzy logiky se zmíníme pouze ve cvičeních a v závěru textu. Z tohoto důvodu jsme zvolili jako název knihy slovní spojení klasická matematická logika. !" ZNAČENÍ Budeme se snažit o přehlednost tvrzení, z toho důvodu budeme myšlenkově podobná tvrzení formulovat jako části jedné vety; např. ve výrokovém počtu je třeba pro demonstrace dalších vět prokázat dokazatelnost pěti typů formulí, shrneme je tedy do jediné věty (viz §2 kap. I). Kromě těchto pěti typů formulí se však v matematice využívá velice mnoho tautologii výrokového počtu a opět mnoho z nich shrneme do jednoho seznamu (viz §3 kap. I). Analogicky se snažíme soustředit i definice do přehlednějších skupin. Jsme si vědomi toho, že tento přístup činí některé definice poměrně dlouhými, a proto pro pohodlí čtenáře označujeme konec definic symbolem D, v analogii s označením konce demonstrací symbolem ■. Současně se snažíme vyznačit věty a definice posunutím jejich textu poněkud doprava vzhledem k běžnému začátku řádků. V textu budeme konstruovat různé důkazy, tzn. jisté posloupností formulí, Pro zvýšení přehlednosti celkové ideje konstrukce budeme podtrhávat ty formule, jejichž užití je možno pokládat za realizaci této ideje. Drobným písmem vyznačujeme úvahy, které přinášejí méně důležité informace, na které již v dalších partiích nebude (příliš) navazováno. V našem textu se budeme snažit i o zachycení různé terminologie. Pojmy, které budeme užívat, jsou značeny tučně, tedy pojem, a pojmy, používané alternativně jinými autory značíme pojem. * Různého typu písma využijeme i pro snazší odlišení znaků pro různé pojmy; standardně budeme značit slova */,&,%... výrokové proměnné p, q, r,... výrokové formule A, 2, C, "D, T, Q, 01,... systémy výrokových formulí 7, S, 3t, Q,... ohodnocení výrokových proměnných v, w,... proměnné x, y, :, g, ti,..., xi, x2, - - ■, í, t) ■ ■ • predikáty P,Q,... konkrétní predikáty Seq,Hull, =,... logické funkce 5, ©, ■ ■ • konkrétní funkce S, +, ■, ífíaic,... konstanty c, £>,... termy ř, s, r,... formule predikátového počtu (někdy též =>, případně D)4), (3) „... a ...", „... i ...", „... a zároveň ..." (případně z latiny převzaté „.., et ...") jsou formalizovány konjunkcí, při jejím zápisu budeme používat symbolu &: (používá se též A), (4} „... nebo ..." (případně z latiny přijaté „... vel ...") bude formalizováno disjunkcí, při použití symbolu V 5', (5) „..., práve když ...", „... tehdy a jen tehdy, když ...", „... je ekvivalentní s .. .'• hudeme formalizovat ekvivalencí (někdy se také používá sousloví „oboustranná implikace"), přitom používáme znaku = (též <& nebo i-*)6'. Pravdivostní hodnoty příslušné k uvedeným obratům a popisující jejich obvyklé chápání jsou formulovány v §1, tam jsou také zmíněny příklady situací, kdy v běžné řeči dáváme obratům jiný význam. Někteří autoři používají všech těchto obratů rovnoprávně, zaplatí za to však větším poetem axiomů, neboť obraty nejsou na sobě nezávislé a axiomy musí tento vztah popsat. Jiní autoři volí za základní obraty jen některé z nich a zaplatí za to tím, že ostatní obraty je potřeba chápat jako zkratky za složitější výroky obsahující pouze vybrané základní obraty. Hlavní výhodou tohoto druhého přístupu je zjednodušení demonstrací postupujících podle složitosti formule, protože je potřeba prověřovat méně případů. Dokonce ani volba základních obratů při druhém přístupu není jednotná (nicméně téměř vždy je jako jeden z nich volena negace), záleží na vkusu a účelu. Je dokonce možné zvolit jenom jediný obrat, ale ten pak už musí být volen z obratů méně intuitivních (např. Shefferova operace; viz cv. 11 této kapitoly). V dalším textu zvolíme za základní obraty první dva, pro zkoumání důsledku se zdá volba implikace jako nejvhodnější, jinými přístupy se budeme zabývat ve cvičeních. Běžnými logickými operacemi tedy jsou negace (unární), implikace, konjunkce, disjunkce, ekvivalence (všechny binární), v predikátovém počtu pak navíc kvantifikace (viz následující kapitola); již jsme však uvedli, že v této kapitole se většinou omezíme jen na první dvě logické operace (a ostatní, relevantní pro výrokový počet, budeme chápat jako pouhé zkratky). Je nutno rozlišit logické operace od logických funkcí (neboli operací), kterými se budeme zabývat v predikátovém počtu. Symboly používané k označení negace, implikace, konjunkce, disjunkce a ekvivalence formulí (tzn. symboly ->, —>, &, V, =) se nazývají logické (též výrokové) spojky. V našem textu zásadně nebudeme používat =>ae jako symbolů ve formálním jazyce, ale vyhradíme tyto symboly v odpovídajícím významu do metamatematické hladiny. * *' Místo „ŕ/ implikuje &&" říkáme také, že „& je nutnou podmínkou pro s&* nebo „Jč/je postačující podmínkou pro S3". Analogicky při ekvivalenci místo „sď, pravé když 38" říkáme také, že „jž/ je nutnou a postačující podmínkou pro Š&". 5> Místo o disjunkci se někdy mluví o alternativě, což ale múze vést k nedorozumění, protože někteří autoři chápou alternativu (příp. alternaci) jako disjunkci ve vylučovacím smyslu. 6) Nékdy se formalizuje i obrat „. . . nebo ... ve vylučovacím smyslu", dnes v hgice nepatří mezi nejobvyklejší. Antičtí ftekové ho však užívali často (viz např. cvičení 7 této kapitoly) a také v souvislosti s počítači je hojně využíván. Uvědomme si, ze vylučující disjunkce je nahraditelná negací ekvivalence (viz cv. 5). 2!1 OVOD I V Kritice slov K. Čapek s půvabem jemu vlastním napadá logiku: „0 logickém důkazu je jediná pravda, že se nic nedá logicky dokazovat; což vám dokážu logicky. Buď dokazuji své tvrzení samými evidentními soudy; ale kdyby mé tvrzení plynulo evidentně z evidentních vět, bylo by samo evidentní, a tu by ovšem naprosto nepotřebovalo být dokazováno. Nebo dokazuji své tvrzení větami neevidentními, ale pak bych musel logicky dokazovat všechny tyto věty „usque ad infinitum", ..., z čehož logicky plyne, že logický důkaz je nemožný; a není-li tento logický důkaz naprosto přesvědčující, vidíte z toho, že logické dokazování opravdu za nic nestojí". K. Čapek zpochybňuje samu podstatu logiky, neboť pojem důkazu je jedním z jejích nejdůležitějších pojmů. Pokud bychom však přijali Čapkovy výhrady, musili bychom revidovat náš přistup k mnohem širší oblasti zahrnující celé lidské rozumové vyvozování. Připomeňme, že Eukleidés (315-271 př. Kr.) ve svých Základech jako prvý vyvozuje z několika axiomů ceíou nauku (geometrii, ale protože aritmetiku chápe jako součást geometrie, je možno říci, že celou tehdejší matematiku). Deduktivní metoda však neovlivnila pouze matematiku a vědy blízké matematice (např. teoretickou fyziku), ale zasahuje — a to dokonce i ve své formalizovane podobě — do velice mnoha oblastí lidského poznání; jako příklad uveďme knihu B. Spinozy Etika (s podtitulem: vyložená metodou geometrickou), kde je podávána filozofie metodou věta- důkaz7*. Naštěstí za chvíli nahlédneme, že Čapkovy námitky naprosto nereflektují lidskou zkušenost. V této kapitole budeme formálně definovat pojem důkazu pro počet výrokový, v příští pro predikátový. Pojetí je v obou případech naprosto stejné, liší se pouze axiomy logiky a dedukčními {odvozovacímt) pravidly přijímanými v tom kterém počtu. Je nutno velice zdůraznit, že v obou případech volíme axiomy logiky a de-dukční pravidla tak, aby formalizovaly kroky přijímané v intuitivních úvahách. Tedy např. dedukční pravidla budou formalizace intuitivních postupů odvozujících další pravdivá tvrzení z tvrzení, která jsme již za pravdivá přijali. Jinak řečeno axiomy a dedukční pravidla můžeme volit různě, ale vždy mají popisovat „intuitivní pojem odvozování", a v tomto ohledu jejich volba naprosto nemůže být nahodilá — podstatným cílem logiky již od antiky bylo popsat ty principy, kterými se řídí lidské uvažování. Navíc ovšem při běžném uvažování vycházíme z nějakých předpokladů. V diskusích běžného života obvykle tyto předpoklady neformulujeme přesně, jsou přítomny v našem uvažování pouze implicitně a právě toto běžné neujasnění základních východisek vede v mnoha diskusích k nedorozuměním, neboť co pro jednoho diskutujícího je zcela zřejmé (a na čem staví svou argumentaci), může být pro druhého nejasné, nebo dokonce nepřijatelné. Naproti tomu v matematické logice žádáme, aby předpoklady, které můžeme v důkaze použít, byly vymezeny zcela přesně. Předpoldady představují ta tvrzení, z kterých při dokazování dalších tvrzení vycházíme. Je totiž zřejmé, že při zdůvodňování nějakého tvrzení se nemohu do nekonečna odvolávat na stále zřejmější a zřejmější fakta: někdy musím jíž prohlásit, že tato fakta jsou (alespoň pro mne) tak zřejmá, že je již nebudu dokazovat. S partnerem se v diskusi buďto na nich shodneme (tzn. formálně řečeno přijmeme stejnou 7) Pro zajímavost uveďme první Spiuuzův axiom: „Vše co jest, jest buďto samo v aobé, anebo v něčem jiném." 21 KAPITOLA t VÝROKOVÝ POČET teorii, viz §3 následující kapitoly8'), nebo jame ochotni nadále společně přijatelné základy hledat, anebo zjistíme, že jeden přijímá jako základní fakt (o kterém odmítá diskutovat) přesně negaci základního faktu (příp. důsledku základních faktů) toho druhého. V posledním případě je již předem zřejmé, že diskuse, využívající jako argument zmíněný fakt, nemůže vést ke shodě. Při volbě předpokladů nejsme po formální stránce nijak omezeni, při nevhodné volbě se může „pouze" stát, že z nich dokážeme jakýkoli nesmysl (předpoklady jsou sporné}. Je však jasné, že z intuitivního hlediska nejsou jednotlivé systémy předpokladů rovnocenné. Popis vhodné volby je závislý na filozofickém pojetí pravdy a skutečnosti, a přesahuje tedy rámec matematické logiky. Poznamenejme, že volba axiomů logiky, dedukčních pravidel a předpokladů je možná až po zvolení systému formulí, které budeme vyšetřovat. Ve výrokovém počtu je potřeba dříve zvolit spojky, což jsme před okamžikem učinili, v predikátovém počtu je potřeba zvolit jazyk (formální definici viz §1 kap. II), tzn. rozhodnout o jaké vlastnosti a vztahy se budeme zajímat a s jakými objekty budeme pracovat. Přistupme k formálnímu pojmu důkazu. V matematické logice definujeme důkaz z nějakých předpokladů jako konečnou posloupnost formulí, při jejíž tvorbě smíme v každém jednotlivém kroku učinit ňekťěrbu z následujících činností: (a) napsat (vyslovit, myslet, etc.) jeden z předpokladů, (b) napsat axiom logiky, (c) napsat formuli, kterou dostaneme aplikací dedukčního pravidla na některé formule, které v posloupnosti předcházejí. Formule je dokazatelná (z nějakých předpokladů), jestliže existuje důkaz (z těchto předpokladů), jehož je posledním členem. Uvědomme si, že pokud má mít uvedený pojem důkazu rozumný smysl, musíme zvolit alespoň jedno dedukční pravidlo a alespoň jeden axiom nebo předpoklad9'. Zdůrazněme, že pravidla uvedená v následujících kapitolách jsou ryze syntaktická a neodvolávají se na sémantiku a že triviálně existuje algoritmus umožňující rozhodnout, zda formule je axiomem logiky či nikoli, a analogicky umožňující rozhodnout, zda jedna fonmde plyne z druhé/druhých pomocí některého z uvedených dedukčních pravidel. Mame-li předloženu nějakou posloupnost formulí, je ověření, zda se jedná o důkaz z určitých předpokladů, zcela mechanickou záležitostí (existuje algoritmus). Po vyslovení definice důkazu je již možné, a nutné, zdůraznit, v čem se matematický logik naprosto rozchází s citovaným výrokem K. Čapka. Para£rázuji-li jeho ' Důkaz z předpokladů ve výrokovém poctu je v jistém smyslu jen pomocný pojem, podstatná je dokazatelnost bez předpokladů. Naproti tomu v predikátovém počtu bychom se sice také bez předpokladů obešli, ale bylo by to nevýhodné {a hlavně naprosto nepřehledné, protože bychom neustále museli tyto předpoklady opakovat). Proto je v predikátovém počtu zvykem mluvit o důkazu ve zkoumané teorii, jinak řečeno sumarizovat předpoklady na začátku zkoumám jakožto axiomy teorie. 9^ Jako kuriozitu uveďme systém, který jednak pracuje s jedinou logickou spojkou (Shefferovou, víz cv. 11, která má význam „není pravda, že A nebo není pravda, že 23") značenou |, ale hlavně má jediný axiom a jediné dedukční pravidlo. Tato minimalizace je pochopitelně zaplacena ztrátou přehlednosti a intuitivního náhledu. Axiomem je [ř|(Q|3t)]|[[S|(S|S)||((T|Q)|[(;P|T)|(:P|T)])] a dedukční pravidlo dovoluje odvození formule Ji výrokového počtu z formulí 7 a !P|{Q]!R) výrokového poEtu. ÚVODÍ úvahu, mohu také jednoduše „dokázat", že nikdy nedojdu z Prahy do Prčic: při každém kroku se má pozice změní jen málo a Prčice jsou od Prahy dost daleko. Chyba Čapkovy úvahy spočívá v tom, že mnoha (byť malými) kroky je možno urazit velkou vzdálenost, což řada účastníků pochodu na uvedené trase prakticky prokázala. Analogicky není možno popřít, že i pomocí evidentních důkazových kroků je možno dojít (je-li jich hodně) k tvrzením značně neevidentním. * V lidském uvažování je možno vysledovat mnoho správných dokazovacích postupů a v průběhu vývoje logiky bylo vemú mnoho takovýchto pravidel formulováno a vyučováno {stále s možností nalézání dalších pravidel). Důležitým objevem matematické logiky je možnost volby poměrně malého počtu základních dokazovacích principů, které již pro popsání našeho usuzování (vyvozování) „plné posiači". Pro výrokový i predikátový počet popíšeme konkrétně takovéto dostatečně silné systémy — pro výrokový počet bude složený ze tří typů axiomů a jediného dedukčního pravidla. V textu je uvedena řada dokazovacích postupů (často včetně klasických názvů), nicméně je to jen zlomek těch, které byly v průběhu vývoje logiky formulovány. Matematická logika však přinesla obrovský posun: principy budeme uvádět jako příklady toho, co lze v námi zvoleném systému dokázat, a jako to, co máme používat, ale nikoli jako zákony, které je třeba se naučit vyjmenovávat. Přístup k logice jako k rozsáhlému systému pravidel, která je třeba se naučit, je zřetelný zejména od scholastiky a pokračuje až do 20. stol. Toto pojetí je sice nyní překonané, zdržme se však jakýchkoli negativních soudů, protože scholastický přístup reálně přispěl k rozvoji lidského myšlení. Slovním spojením „plně postačí" rozumíme, že jakýkoli jiný dokazovací princip, který je formalizací intuitivně správného vyvozovacího kroku (speciálně tedy i každý dodatečný axiom logiky popisující intuitivně pravdivé tvrzení), je dovodi-telný ze zvolených základních dokazovacích principů. Vyjádřeme předchozí tvrzeni pro výrokový počet ještě jinými slovy: přidáme-Ii k námi zvoleným axiomům výrokového počtu a/nebo k jedinému dedukčnímu pravidlu výrokového počtu jakýkoli další dokazovací princip, jsou jen dvě možnosti. Buďto i „důkazy", v kterých je tento dokazovací princip povolen, umožní dokázat jen (vždy) pravdivé výrokové formule, pak ale je dodatečný dokazovací princip zbytečný, neboť tytéž výrokové formule je možno dokázat i bez něho, anebo se pomocí nějakého „důkazu" povolujícího i dodatečný dokazovací princip podaří dokázat nějakou výrokovou formuli, která není (vždy) pravdivá, ale pak je tento dokazovací princip nepřijatelný. Odporovalo by přece naší intuici o pojmu dokazateluosti, kdybychom dokázali nepravdivý výrok. Dokonce bychom považovali za absurdní, kdybychom dokázali nějakou výrokovou formuli, která by byla nepravdivá, byť jen při jediném ohodnocení výrokových proměnných, ze kterých je vytvořena. Tímto pochopitelně nezpochybňujeme užitečnost různých jiných dokazovacích postupů (také jich řadu uvedeme), protože takovéto postupy mohou velice urychlovat a zpřehledňovat důkazy, pouze tvrdíme, že takovéto postupy jsou již nahraditelné pomocí vybraných základních dokazovacích principů. A už vůbec netvrdíme, že existuje jediná vhodná volba základních dokazovacích principů, dokonce i některé jiné 23 KAPITOLA I VÝROKOVÝ POČET možné volby základních dokazovacích principů ukážeme (viz závěr §2 a také cvičení 18-21). Systémy dokazovacích pravidel můžeme zhruba dělit na dvě skupiny: (a) hilbertovské systémy mající málo dedukčních pravidel a vice axiomů, (b) gentzenovské systémy mající naopak více pravidel a co nejméně axiomů. Systém popsaný v §2 je hilbertovský, příklady gentzenovských systémů lze nalézt ve cvičeních. * Je nutné poznamenat, že nebývá — dokonce ani v matematice — zvykem vytvářet důkazy tali, aby přesně vyhovovaly uvedené definici, bylo by to velmi zdlouhavé a špatně čitelné, ale každý správný důkaz musíme být, schopni předělat na důkaz vyhovující výše uvedené definici. V celém našem textu je jediný důkaz, který je skutečně posloupností majíci vlastnost vyžadovanou v definici důkazu. Je to důkaz naprosto triviálního tvrzení A —> A (viz §2). Na tomto důkazu by čtenář měl nahlédnout již uvedený fakt, že otázka prozkoumání, zda uvedená posloupnost formuh' je důkazem, je skutečně zcela mechanickou záležitostí. Na druhé straně ale čtenář pravděpodobně také prožije, že volba formulí výrokového počtu, které důkaz vytvářejí, je ■méně triviální a že vyžaduje jistou zkušenost a intuici. K problému, zda vystačíme se zkušeností nebo zda potřebujeme současně jak zkušenost tak i intuici, se vrátíme na konci tohoto úvodu. Ve čtvrté kapitole budeme způsobem běžným v matematice prokazovat aritmetická tvrzení. K prvému tam uvedenému důkazu však připojujeme komentář poukazující na to, které postupy matematické logiky (včetně postupů predikátového počtu) jsou v předvedeném důkazu použity implicitně. Těmito poukazy vlastně podáváme návod, jak by se musel k předvedenému důkazu konstruovat příslušný zcela formální důkaz. Hlavní náplní syntaxe výrokového počtu je ukázat metody, jak z existujících důkazů tvoříme důkazy jiné, a zejména prokázat možnost používat „důkazové bloky (schémata)". S pomocí takovýchto bloků pak ukazujeme dokazatelnost dalších tvrzení, a to podstatně jednodušeji. * Zmínili jsme se, že sémantiku výrokového počtu je možno popsat tak, že vystačíme s jediným modelem. Je jím pochopitelně dvouprvkový soubor {1,0}, jehož prvky představují pravdu a nepravdu, přičemž budeme uvažovat různá ohodnocení výrokových proměnných, tj. zobrazení souboru výrokových proměnných do {1,0}. Toto pojetí je v souladu s pojetím v predikátovém počtu, kde se také uvažují ohodnocení jako zobrazení do zkoumaného modelu. V jiné terminologii pokládáme každé jednotlivé ohodnocení za „model", a tedy je potřeba uvažovat řadu „modelů". * V úvodu celého textu již bylo uvedeno, že vztah syntaxe a sémantiky je obsahem vět o korektnosti a o úplnosti. Věta o korektnosti v případě výrokového počtu vypovídá, že každá dokazatelná formule výrokového počtu je vždy pravdivá, tzn. je pravdivá při každém ohodnocení základních výroků. Takováto výpověď evidentně odpovídá intuici, neboť požadavek, aby vše, co dokážeme, bylo také pravdivé, je zcela 24 ÜVOD I přirozený. Nadto intuitivně budeme pokládat za vhodný jen takový popis usuzování, který ho popíše „úplně", a tato idea je obsahem věty o úplnosti. Věta o úplnosti ve výrokovém počtu tvrdí, že každá vždy pravdivá formule výrokového počtu je v tomto počtu dokazatelná. Druhá z uvedených vět má za důsledek výše zmíněnou postačitelnost vybraných základních dokazovacích principů pro popis veškerého vyvozování relevantního pro výrokový počet, ale jejím důsledkem je také, že vyplnění tabulky pravdivostních hodnot představuje algoritmus, který rozhoduje, zda formule výrokového počtu je dokazatelná či nikoli (tedy výrokový počet je rozhodnutelný). Demonstrace věty o úplnosti navíc popisuje algoritmus, jak k dokazatelným výrokům příslušný důkaz sestrojit. Pro tvorbu důkazů ve výrokovém počtu lze napsat program, a pak už stačí pouhý stroj a není potřeba intuice matematika. Tedy z hlediska výrokového počtu matematika zcela nahradí robot10"1. Ke zcela jiným závěrům dojdeme však v případě predikátového počtu. ^ Zkoumanou otázkou äž dosud bylo, zda existuje důkaz. Pokud položíme otázku, zda existuje důkaz, který má nějakou vlastnost (např. je dostatečná jednoduchý), přestane být konstrukce takovéhoto důkazu triviálním problémem. 25 p FORMULE A SÉMANTIKA VÝROKOVÉHO POCTU V úvodu této kapitoly jsme již uvedli, že ve výrokovém počtu budeme pracovat s následujícími pojmy (a jejich znaky), a ukazovali jsme jejich intuitivní význam: (1) znaky pro výrokové proměnné (někdy se místo výrokové proměnné používá i název prvotní formule, případně (výrokový) atom)\ předpokládáme, že výrokových proměnných máme k dispozici nekonečně mnoho, i když v jakékoli úvaze (formálněji: v jakékoli formuli, v jakémkoli důkaze, etc.) se jich vyskytne jen konečný počet1'; výrokové proměnné budeme označovat p, q,r,...; (2) logické spojky -i, —» (alternativně navíc připouštíme &, V, =); (3) nadto budeme ještě používat pomocné symboly (závorky, méně obvyklé je použití teček); jejich význam spočívá „pouze" v určení, na které formule se ta která logická operace vztahuje, tzn. závorky vymezují rozsah výrokových spojek, neboli intuitivně řečeno pomocné symboly popisují, jali posloupnost symbolů „číst"; např. {^A) —» S čteme: jestliže neplatí .4, pak ®, ale jiné „uzávorkování" -i(.A —* B) čteme: neplatí, že z A plyne íí; ve cvičení se zmíníme o tzv. polské notaci, která se zcela obejde bez závorek '. Slovem nad určitou abecedou budeme rozumět konečnou posloupnost3' znaků (symbolů) z dané abecedy (prázdné slovo se připouští; pořadí symbolů v posloupnosti je podstatné, změnou pořadí symbolů změníme slovo). Říkáme, že znak <Ě; se vyskytuje na i-tém místě ve slově <Ěi... $„. Např. znak 0 se ve slově 1005 vyskytuje na druhém a třetím místě, tedy má dva výskyty. Slovo í i... *řm nazýváme pod-slovem slova i ... 3>n, jestliže existuje / < n tak, že znali lřj je totožný se znakem •řj+j pro každé j í m. Nahrazení podslova začínajícího na popsaném místě v daném slově jiným slovem vyjadřuje intuitivní představu (formálně: jsou-li slovo $i .. . $t, slovo í j ... f j a slovo ©i... Qj tri slova nad danou abecedou a je-li i' Ž k, pak slovem vzniklým nahrazením slova \ři... ty; začínajícího na místě i' ve slově $i ...$k slovem Oj . .. 0j rozumíme slovo $i ... 3v_i©i... ©j), (SBj V SBy) a (3j s äSy)) pro některá j, jf < i. Posloupnost á?i,..., á?t vyhovující uvedeným podmínkám nazýváme vytvářející posloupností formule jzf výrokového počtu4'. Formuli výrokového počtu, která se vyskytuje ve všech vytvářejících posloupnostech formule s& výrokového počtu, nazýváme podforrnulí formule sf. Ü Značení. Pro formule výrokového počtu budeme používat znaky A,"B,... Například posloupnost v, q, (p -* q)> ->(p -* q)> ->p. hv -»-■(p -» q)) je vytvářející posloupností formule (->p —* -i(p —t q)). Jestliže bude ze souvislosti patrné, že se jedná o formule výrokového počtu, budeme někdy sousloví „výrokového počtu" vynechávat. Uvědomme si, že slovo & p) je podslovem formule (p & p), nikoli však podforrnulí a že ke každé formuli existuje její vytvářející posloupnost obsahující pouze její podformule (toto můžeme rigorózně prokázat postupně indukcí pro jednotlivé formule z vytvářející posloupností). Ve vytvářející posloupnosti formule jsou evidentně všechny členy formulemi, a tedy je také zřejmé, že volba termínu „pod/wrrruzre" je vhodná, neboť každé slovo, které je podforrnulí formule, je samo formulí. Někdy se vytvářející posloupnost definuje tak, že obsahuje pauze podformule zkoumané formule (tzn. jako minimální možná). Umluvme se, že budeme závorky vynechávat, pokud to neohrozí čitelnost zápisu. Již v definici jsme nevyžadovali závorky kolem negované formule, v dalším textu budeme také vynechávat poslední („zcela vnější") dvojici závorek — tzn. budeme psát např. p &■ (p —» q) místo (p Sz (p —> q)). Navíc od okamžiku, kdy prokážeme asociativitu konjunkce a disjunkce, budeme vynechávat závorky i v případech vícečetných konjunkcí a disjunkcí, etc.5^ Při popisu abecedy, nad kterou vytváříme formule výrokového počtu, jsme uvažovali jediný typ závorek, neboť s ním vystačíme, ale pro usnadnění čtení se v matematickém textu běžně používá (což i my budeme činit v dalším textu) více typů závorek. V takovém případě je zvykem používat nejprve typ (,), a poté typ [,], pro ještě složitější výrazy je zvykem odlišovat závorky velikostí. 4' V knize [K-S-Ch] se používá termínu konstrukce formule. 5> Někdy se dokonce přijímá úmluva, že —* má nižší prioritu než ostatní spojky, coz umožní psát místo (A tt S) -t (C V 35) prostě A &i 3 -. e V D. 27 KAPITOLA I VÝROKOVÝ POČET Zopakujme, že definice formule záleží na volbě systému logických spojek. V naší definici jsme volili spojky -i a —», ale jako alternativu jsme připouštěli i další spojky {viz bod (2) a v definici formule bod (c); při ještě jiné volbě systému spojek jest třeba definici upravit obdobně). Při omezenější volbě, které dáme přednost, budeme slova typu A &: H, AVB a A = 23 chápat po řadě jako zkratky formulí -*(A —> -'S), -iA —> S a {A —* B) & (S —> A), které jsou vytvořeny na základě formulí AaS. Zopakujme, že při preferovaném pojetí se při demonstracích obejdeme bez indukčních kroků pro konjunkci, disjunkci a ekvivalenci, což je značná výhoda. Prosím čtenáře, aby se přesvědčil (pochopitelně až po definování pravdivostních hodnot formulí nad rozsáhlejší ze zmíněných abeced), že příslušné dvojice formulí (tedy např. formule A k li a --{A —» -'S)) nabývají téže pravdivostní hodnoty pro každé ohodnocení. Takovéto zjištění bude intuitivním ospravedlněním možnosti chápat formule vzniklé konjunkcí, disjunkcí a ekvivalencí jako pouhé zkratky. Věta, Nahriuiíme-U ve formuli její podformuli na kterémkoli m/s tě jinou formuli', dostáváme opět formuli. Demonstrace. Buď Si,... ,3* vytvářející posloupnost formule A. Dále buď dána podformule S formule A a buď dána formule C. Metamatematickou indukcí ukážeme, že pro i š k je slovo, vzniklé z 3t nahrazením slova S slovem C na kterémkoli místě, opět formulí. Je-li formule S, výrokovou proměnnou, není co ukazovat, neboť B; nemá pod-slova různá od sama sebe. Jestliže S, vznikla logickou operací aplikovanou na formule Bj a "By (případně na jednu formuli By), musí být S podformuli jedné z těchto formulí (nebo samotnou formulí S;) anebo vůbec není podslovem. Poslední tvrzení je sice velice intuitivní, avšak pfesné prokázáni provedeme opět metamatema-tickou indukcí podle složitosti formule (neboli podle její vytvářející posloupnosti). Nejprve si však uvědomme že (v důsledku správného „uzávorkování") pro žádné slovo <í>i ...ín, které je formulí nemůže existovat k' < n takové, aby buďto $1 . ..íf nebo 3v+i .-.$„ bylo formulí — avšak abychom byli schopní tvrzení prokázat musíme přesně dodržet definici formule, tzn. nesmíme žádné závorky vynechat. Předpokládejme tedy, že pro formule Ci.C^ je každá formule, která je podslovem kterékoli z této dvojice již podformuli příslušné formule. Nechť formule £> je podslovem formule Ci —* C2, kteréžto slovo není podformuli žádné z formulí Ci, Zl- Pak 'D nemůže být podslovem ani Ci, ani C-2, musí být tudíž vytvořeno z nějakých slov B^ jD2 pomocí implikace. Ovšem je-li formule T> tvaru Ti\ —• D3, jsou slova T>i a T>2 formulemi, a tudíž T>i je podformuli formule tit a D2 je podformuli fornrule Ca. Protože však "Di je „koncem slova" Gj a D2 je „počátkem slova" £-2, musí být 2)j totožné s Ci a současně T>-i totožné s 62- Analogickou Úvahu provedeme pro negaci, příp. pro další logické operace. Indukcí podle složitosti formule tedy prokážeme, že každá formule má požadovanou vlastnost. Na základě právě prokázaného jsou indukční kroky pro negaci a implikaci evidentní. Pro implikaci např. stačí uvážit pouze, že pokud je B podformuli formule S.; a/nebo formule Sj, je slovo ■er vzniklé z formule S, -+ Sj nahrazením formule S formulí C implikací, a to implikací s antecedentem (formulí před znakem —>) vzniklým z formule B; nahrazením formule S formulí G a konsekventem (formulí za znakem —») vzniklým z formule Sj nahrazením formule B formulí e — speciálně je tedy slovo ja/ formulí. ■ * 2N FORMULE A SÉMANTIKA VÝROKOVÉHO POCTU_________________jjl Zabývejme se teď pravdivostními hodnotami formulí výrokového počtu vzniklých pomocí logických spojek. Intuitivně je přirozené pokládat negaci výroku za nepravdivou, jestliže původní výrok pokládáme za pravdivý, a naopak v případě, že nějaký výrok pokládáme za nepravdivý, jeho negaci pokládáme za pravdivou. Již jsme zmínili, že v běžném jazyce nejsou obraty odpovídající logickým operacím chápány ve všech situacích stejně. Často uváděným příkladem nejednoznačnosti běžného jazyka je spojka „nebo", kterou někdy používáme ve vylučovacím smyslu, ale běžně nikoli. Při běžném chápání tedy považujeme za pravdivý i případ, platí-li oba členy. Naproti tomu při emocionálním zvolání „buď tu budu já, nebo ten pes" vylučujeme, že můžeme zůstat oba. V souhlase s obvyklejším přístupem budeme pokládat disjunkci za nepravdivou, pouze jsou-li nepravdivé oba její členy6'. Chápání konjunkce a ekvivalence nebude činit potíže — konjunkce je pravdivá, právě když jsou pravdivé oba její členy (takto již Stoikové) a ekvivalence je pravdivá, jestliže její členy jsou buď oba pravdivé, nebo oba nepravdivé. Hodnocení pravdivosti implikace v závislosti na ohodnocení pravdivosti výroků, z nichž je implikace složena, již nemusí být na první pohled tak zřejmé, ale jak již zdůrazněno v úvodu, při formalizaci uvažování musíme určit jednoznačně význam implikace (tedy hodnotit pravdivost implikace pouze v závislosti na hodnocení pravdivosti výroků do ní vstupujících). Reknu-li „jestliže bude zítra pršet, pak budu celý den doma" a druhý den venku lije a já jsem z domova pryč, pak jsem lhal; jestliže lije a jsem doma, pak jsem mluvil pravdu; jestbže svítí sluníčko, pak mohu dělat cokoli a vždy jsem mluvil pravdu, protože o tom, co budu dělat, když bude hezky, jsem nic netvrdil7'. V souladu s intuitivním chápáním důsledku nám tedy nezbude než implikaci pokládat za nepravdivou jenom v případě, že první výrok, nazývaný antecedent nebo předpoklad či premisa, je pravdivý a druhý výiok, nazývaný konsekvent uebo důsledek (též sukcedent či závěr), je nepravdivý. Toto chápání je doložitelné již u Diodóra Krona8'. Následující velice známé tabulky {někdy nazývané základní pravdivostní tabulky) shrnují právě popsané pravdivostní hodnoty. Uvědomte si, že každý sloupec druhé z následujících tabulek představuje funkci, která dvojici nul a jedniček přiřazuje hodnotu, která je nulou nebo jedničkou, přičemž přiřazená hodnota se nachází ve stejném řádku jako dvojíce, které jest přiřazena. Analogicky první tabulka představuje funkci, která jedničce nebo nule přiřadí nulu nebo jedničku (srovnej cv. 10 a 11). e' Stoikové vyšetřovali vice forem disjunkce, mezi nimi také námi zvolenou. 7) Gramatika rozlisuje věty příčinné, které (podle pravidel českého pravopisu) vyjadřují „příčinu (důvod) obsahu věty řídící" a jsou připojovány spojkami protože, poněvadž, že, jelikož a věty podmínkové, které vyjadřují „podmínku, při které může nastat děj věty řídící" a které se připojují spojkami jestliže, -li, kdyby, jestli, když. Není vhodné formalizovat implikací věty příčinné: větu „přišel jsem pozdě, protože nejela tramvaj" budeme brát za lživou v případě, že tramvaje jezdily. a' Diodóros Kronos vyžaduje navíc „souvislost" mezi antecedentem a konsekventem, tzn. oproti pojetí dnes běžnému pojetí ještě omezuje obor, kde je apbkovatelná implikace. Formulace přesně odpovídající naší je u jeho následovníka Filóna z Megar. Spor o význam spojek (koncentrovaný převážné do sporu o význam implikace) pokračuje až do 20. stol., a to včetně, většinou však probíhá vně matematické logiky. Při snaze přesně vymezit chápání implikace ve smyslu našeho textu se někdy mluví o materiální implikaci. 2\> KAPITOLA 1 VÝROKOVÝ POČET P ^p 0 1 1 D P q p^ q p& q pvq P = q 0 0 1 0 0 1 0 i 1 0 1 0 1 0 0 0 1 0 1 i 1 1 1 1 Na rozdíl od implikace nezávisí hodnoty konjunkce (analogicky disjunkce a ekvivalence) na pořadí formulí v nich se vyskytujících, a proto mluvíme o složkách konjunkce, etc., někdy též o konjunktech resp. disjunktech. Výše uvedené intuitivní zdůvodnění nám ukazuje, že následující formální definice je v souladu s běžným chápáním. Definice. Ohodnocením (též pravdivostním ohodnocením nebo valuací) výrokových proměnných rozumíme jakékoli zobrazení v přiřazující jednotlivým výrokovým proměnným hodnoty 0 nebo 1 (a definované na jejich systému). Metamatematickou indukcí (postupně pro členy vytvářející posloupnosti formule) definujeme pravdivostní hodnotu A[v] (někdy značenou i v(A)) jakékoli formule výrokového počtu A při ohodnocení v v souladu s výše uvedenými tabulkami následovně91: je-li 3 výrokovou proměnnou, je-li 3 [v] = 0, je-li 3[v] = 1, je-li 'S\v\ =t 0 nebo C[v] = 1, je-li 3fv] = 1 a současně C[v] = 0. Tautologií (nebo podrobněji výrokovou tautologií) nazýváme formuli A výrokového počtu, jejíž pravdivostní hodnota A[\r] je 1 při každém ohodnocení výrokových proměnných v; kontradikcí nazýváme formuli A, jejíž pravdivostní hodnota -4[vJ je 0 při každém ohodnocení výrokových proměnných v, Je-li A[v] = 1, říkáme, že formule A je při ohodnocení v pravdivá (někdy též splněna nebo v splňuje A). Neni-li formule pravdivá při nějakém ohodnoceni, říkáme (pochopitelně), že je při tomto ohodnocení nepravdivá. Formule je splnitelná, jestliže existuje ohodnocení, při kterém je pravdivá. Systém formulí je splnitelný, jestliže existuje ohodnocení, při kterém jsou (najednou) pravdivé všechny formule z tohoto systému10'. Říkáme, že formule A (resp. systém formulí S) je (tautologickým) důsledkem systému formulí 7 (a značíme 7 \= A, resp. 7 \= S)n), je-li .A (resp. každá formule ze systému S) pravdivá při každém ohodnocení, při kterém jsou pravdivé všechny formule ze systému 7. Místo být důsledkem systému 7 (1) S[v] = v(3), (2) (VB)[v] = 1, <-,S)[v] = 0, (3) (3 -+ e)[v] = i (3 -»e)[v] = o ) Jestliže bychom připustili i další spojky jako plnoprávné, museli bychom rozšířit následující definici, a to v souladu se základními pravdivostními tabulkami těchto spojek. ' Jestliže každé ohodnocení pokládáme za samostatný model, pak ohodnocení, při kterém je pravdivá formule (resp. jsou pravdivé všechny formule daného systému), nazýváme modelem této formule (respH tohoto systému), ' Znak |= je používán pro důsledek i v predikátovém počtu, ale používá se také ve významu splňování (pro predikátový počet viz §2 kap. II, pro výrokový počet nékdy v ]= A místo A[v] = 1) 30 FORMULE A SÉMANTIKA VÝROKOVÉHO POCTU_________________|1 se říká také (tautologický) vyplývat z, případně být (tautologický) odvoditelný z 7. Speciálně zápis |= A znamená, že A je tautologickým důsledkem prázdného systému, tzn. že je t antologiíX2). D Je dobré si uvědomit, že podmínky uváděné v jednotlivých dvouřádcích v předchozí definici jsou komplementární, a pro každé ohodnocení je tedy pravdivostní hodnota jakékoli formule určena, a to jednoznačně. Pokud systém 7 není splnitelný, je jeho důsledkem jakákoli formule. Pravdivostní hodnota formule závisí pouze na pravdivostních hodnotách výrokových proměnných v ní se vyskytujících a připomeňme, že těch je jenom konečně mnoho. Pro ověření, zda uvažovaná formule je splnitelná nebo zda je tautologií, stačí tedy vyšetřit konečně mnoho případů ohodnocení. Jsou to tedy algoritmicky rozhodnutelné úlohy a totéž platí i pro vlastnost „být tautologickým důsledkem konečného systému předpokladů''. Tautologie jsou formule, které nabývají pravdivostní hodnoty 1 při jakémkoli ohodnocení výrokových proměnných. Jedná se tedy o „vždy pravdivé" formule, tzn. o formule jejichž pravdivost je zaručena pouze jejich formou (strukturou formule). Analogicky kontradikce nabývají pravdivostní hodnoty 0 při jakémkoli ohodnocení výrokových proměnných, a představují tudíž „vždy nepravdivé" formule. Ohodnocení je definováno Da všech výrokových proměnných, kterých je nekonečné mnoho, a proto ohodnocení není konečným objektem. Nicméně již jsme uvedli, že splnitelnost jakékoli formule při daném ohodnocení závisí jen na hodnotách ohodnocení pro výrokové proměnné, které se vyskytuji v uvažované formuli. Zastánce fmitniho směru tedy nebude uvažovat jedno ohodnocení, ale mnoho ohodnocení, z nichž každé je ale jen konečným zobrazením ze systému výrokových proměnných do {0,1}. a definici splňování modifikuje tak, že -4[v] je definováno, právě když v definičním oboru v jsou (přinejmenším) všechny výrokové proměnné vyskytující se ve formuli A. Po této modifikaci je celá sémantika výrokového počtu k dispozici i nnitistovi, * Oblíbeným způsobem výpočtu pravdivostních hodnot jsou tabulky pravdivostních hodnot13* (též pravdivostní tabulky). Jednu z nich ukazuje následující příklad (který vede k ohodnocení formule -n(p —- ^q) —* p), ve kterém každý řádek přísluší jednomu ohodnocení dvojice výrokových proměnných p, q a v každém políčku se nachází pravdivostní hodnota formule uvedené v záhlaví sloupce při tomto ohodnocení. Je zapotřebí si uvědomit, že existují právě čtyři různá ohodnocení dvojice výrokových proměnných p a q, proto má následující tabulka čtyři řádky. Obecně tabulka pravdivostních hodnot formule vytvořené z k výrokových proměnných má 2k řádků a alespoň tolik sloupců, kolik je podformulí dané formule (pokud nevyužijeme nějakého zjednodušení zápisu}. P q -■q p-*-.q -.{p -» -.q) -,(p -» -.q) -*p 0 0 1 1 0 1 0 i 0 1 0 1 1 0 1 1 0 1 1 i 0 0 1 1 ' Formule, pro které platí ^= A = '3 se někdy nazývají ekvivalentní, viz také cv. 15. 13) Tabulky pravdivostních hodnot zavedl Ch. S.Peirce (1839-1914). 31 KAPITOLA I VÝROKOVÝ POČET Formule -i{p —f ^q) —* p jest tedy tautologií, formule p —> -iq nikoli. Dále si uvědomme, že pravdivostní hodnota formule ->(p —♦ -■q) je stejná jako pravdivostní hodnota formule p & q pro každé ohodnocení (tedy, že chápání druhé formule jako zkratky za formuli první je v souladu s intuicí). # Jestliže T je jakýkoli systém formulí výrokového počtu a A je jakákoli formule téhož počtu, pak 7, A značí systém formulí T rozšířený o formuli A (tj. v množinové terminologii 7, A je množinou TU {A}). Při této konvenci jest zřejmě 7 j= A, právě když systém 7, -'A není splnitelný. Přes svou trivialitu je tento vztah často používán a je sémantickou analogií syntaktického tvrzení, že 7, -^A je sporná, právě když A je dokazatelná v 7 {viz §2). Dalším často používaným a opět jednoduchým vztahem je (T, A |=2) «• (7\=A^'B), který je sémantickou obdobou syntakticky formulované věty o dedukci (viz opět následující paragraf). Jestliže totiž při každém ohodnoceni výrokových proměnných, při kterém jsou pravdivé všechny formule ze systému 7, je pravdivá i formule A —» 2, pak stačí uvážit definici pravdivostní hodnoty přirazené implikaci a vidíme, že pří každém ohodnocení výrokových proměnných, při kterém jsou pravdivé všechny formule ze systému 7, A, je pravdivá i formule 2. Naopak jestliže předpokládáme, že při každém ohodnocení výrokových proměnných, při kterém jsou pravdivé všechny formule ze systému 7, A, je pravdivá i formule S, pak uvažujeme-lí jakékoli ohodnocení výrokových proměnných, při kterém jsou pravdivé všechny formule ze systému 7, stačí opět pohlédnout na definici pravdivosti implikace a uvidíme, že při tomto ohodnocení je pravdivá i formule A^IS. Pro každé systémy formulí T, S, 3t platí evidentně (a) je-li S podsystémem 7, je 7 |= S, (b) je-li 7 ^ S a S |= 31, je 7 \= K. Podmínku (b) můžeme (využívajíce (a)) formulovat také ve tvaru (V) značí-li 7 systém všech formulí tautologický odvoditelných ze systému 7, jest 7=7. Jako důsledek věty o kompaktnosti vyslovené v §3 této kapitoly dostaneme — po jejím prokázání — navíc podmínku (c) jestliže 7 j= A, pak existuje konečný podsystém Q systému 7 takový, že lá> Uvedené podmínky formuloval A. Tarski, :i2 §2 SYNTAX VÝROKOVÉHO POCTU Vytváření formulí je součástí syntaxe, takže o úplných základech syntaxe výrokového počtu jsme již pojednali v předchozím paragrafu. V právě počínajícím paragrafu se budeme věnovat zejména dokazatelnosti ve výrokovém počtu. Za axiomy výrokového počtu vezmeme všechny formule, které jsou některého ze tří následujících tvarů, kde T, Q a Jí označují jakékoli formule výrokového počtu: VP1 P-*(Q-+3>), VP2 [7 - (Q -> K)] - [{7 - Q) - {7 -> K)], VP3 (-.tP-*-iQ)-+{Q-♦;?), Za dedukční (odvozovací) pravidlo přijmeme modus ponens, dovolující z dvojice formulí ľaJ^U vyvodit formuli Q. Před intuitivním zdůvodněním pravidel VP1-VP3 si uvědomme, že se jedná o schémata, neboť axiomem je formule uvedeného typu pro libovolné formule 7, Q, "R výrokového počtu. Jde tedy o nekonečně mnoho axiomů konečně mnoha typů1*. Jestliže přijmeme nějaké tvrzení jako předpoklad, pak pro nás toto přijaté tvrzení již vyplývá z čehokoli (formalizací této úvahy je VP1). Zdůrazněme, že tuto úvahu provedeme i v případě, kdy nevime, zda první tvrzení je pravdivé, a dokonce axiom přijímáme, i když 7 je nepravdivé — napr. -iQ —> (Q —* -■Q) je axiomem nezávisle na tom, zda Q je pravdivé! Jestliže z prvního tvrzení vyplývá druhé a z druhého vyplývá třetí, pak z prvého tvrzení již musí vyplývat třetí (tzn. vyplývání je tranzitivní). Uvedený dokazovací princip uvádí již Theofrastos z Eresu (lze připisovat i Aristotelovi), Jeho formalizací je formule (í> -» Q) -* [(Q -» K) -> (7 -» Ä)] výrokového počtu2', kterou budeme pro snazší zapamatování nazývat tranzitivitou implikace, i když tradici by více odpovídal název zákon hypotetického sylogismu. Schéma VP2 je mírně „zesílenou" verzí tranzitivity implikace (protože předpoklad J5 —> (Q —> Ä) je slabší než předpoklad Q —> 3?) a v popsané podobě ho využijeme v demonstraci věty o dedukci (někdy je nazýváno Fregův zákon). V matematice často místo toho, abychom dokazovali, že z jednoho tvrzení plyne druhé, ukazujeme, že z negace druhého tvrzení plyne negace prvního tvrzení; formalizací tohoto principu je VP3. Tento princip je obměnou zákona transpozice3í (T -» Q) —> {-iQ —> -i7), přijímaného již Stoíky (viz (4) třetí věty tohoto paragrafu a (2) z cvičení 7). Uvedený princip je i podstatou často užívaného principu důkazu sporem (viz dále, princip důkazu sporem se také nazývá reductio ad absurdum): jestliže z nějakého tvrzení dovodíme něco nepravdivého, pak princip důkazu sporem lJ Obměna našeho systému, mající pouze konečně mnoho axiomů (tří) a konečně mnoho dedukč-ních pravidel (dvě), je uvedena na konej paragTafu. 2> Si ekvivalentně (Q — K) — [(SP -* Q) — (SP — Ä)] *' nazývaného někdy též zákonem kontrapozice 33 KAPITOLA I VÝROKOVÝ POČET nám dovolí uzavřít, že nemůže být udržitelný náš původní předpoklad, tzn. že jsme dokázali negaci výchozího tvrzení. Dokazovací pravidlo modus ponens se ve starší literatuře označuje jako modus ponendo ponens (viz cvičení 8}, čeaky se nazývá pravidlo odloučenía anglicky převážně detachment rule. Je uváděno také již Theofrastein a bylo užíváno už před Aristotelem. Intuitivní správnost tohoto pravidla je zcela zřejmá, neboť jestliže ukážeme, že z jednoho tvrzení plyne druhé, a jestliže prokážeme první tvrzení, pak musíme přijmout za prokázané i druhé. Formule Q se někdy nazývá bezprostředním důsledkem formulí IP a. í -» Q. Pokud někdo věří více kalkulaci než odvolání na intuici, může .se ubezpečit o správnosti axiomů ověřením, že jde o tautologie (tento výpočet budeme stejně potřebovat pro větu o korektnosti v příštím paragrafu). Definice. Je-li T jakýkoli systém formulí výrokového počtu, pak důkazem ze systému předpokladů (axiomů) T4' (též prostě důkazem z předpokladů 7) rozumíme posloupnost formulí Di,...,Dt výrokového počtu takovou, že pro každé i Ä k vznikne formule T)j některým z následujících způsobů: (a) je axiomem výrokového počtu, (b) je jedním z předpokladů systému X, (c) vyplývá z formulí v důkazu předcházejících pomocí dedukčniho pravidla modus ponens (podrobněji: existuji j,j' < i tak, že Dy je formulí "Dj —»D;)-Posloupnost Di,..., Dfc, vyhovující výše uvedené podmínce, nazýváme také důkazem (poslední) formule výrokového počtu Dt ze systému předpokladů X. Formuli A výrokového počtu nazýváme dokazatelnou ze systému předpokladů X, jestliže existuje její důkaz z uvedeného systému. Dokazatelnost formule A ze systému předpokladů X značíme X h A. Dokazatelnost í ve výrokovém počtu rozumíme dokazatelnost bez předpokladů (tj. pro prázdný systém 7) a. v souhlase s předchozím ji značíme I- A. Formuli nazveme vyvratitelnou ze systému předpokladů X, jestliže její negace je dokazatelná ze systému předpokladů 7. Systém formulí výrokového počtu nazýváme sporný (též inkonzistentní), jestliže je v něm dokazatelná každá formule výrokového počtu (nad zkoumanou abecedou). Systém formuli, který není sporný, nazýváme bezesporný (též konzistentní). Q Naprosto triviálním, ale často používaným pozorováním je, že důkaz ze systému předpokladů Xje důkazem i z každého systému předpokladů S obsahujícího všechny formule z 7. Každá formule vyskytující se v důkazu ze systému předpokladů je pochopitelně dokazatelná z těchto předpokladů. Je také zcela zřejmé, že lze zobecnit pravidlo modus ponens na tvrzení, že jeli ze systému předpokladů 7 dokazatelná jak formule A —r 35, tak i formule A, pak je z téhož systému předpokladů T dokazatelná formule 25 — na toto jednoduché tvrzení se budeme odvolávat jako na princip modus ponens. Stačí totiž prodloužit V takovéto souvislosti budeme formule ze systému T nazývat předpoklady (axiomy). 34 SYNTAX VÝROKOVÉHO POCTU__________________________|2 (jakožto posloupnost formulí) důkaz formule A -* 2? o důkaz formule A, ověřit, že takto vznikne důkaz ze systému předpokladů 7, a tento důkaz dále prodloužit o jediný další krok použitím odvozovacího pravidla modus ponens. V dalším budeme konstruovat různé důkazy. V těchto konstrukcích je řada kroků zcela rutinních (např. použití modus ponens), avšak některé kroky se jeví pro ten který důkaz klíčové. Pro snazší pochopeni podstaty každého jednotlivého důkazu se budu, jak již uvedeno při popisu značení, snažit podtržením zdůraznit kroky, které jsou pro sestrojovaný důkaz — dle mého názoru — nejdůležitější. Pro přehlednost budeme také na pravé straně uvádět zdůvodnění jednotlivých kroků. Veta 15). \-A^A. Demonstrace. Následující posloupnost je důkazem ve výrokovém počtu: (A -+ {{A ->*)-. A}) - ({A ^(A^ A)] -*{A-> A)), VP2, do kterého dosadíme za 3> a ÍR formuli A a za Q dosadíme formuli A—* A, A —t [{A —> A) —> A], VP1, do kterého dosadíme za Ť formulí A a za Q dosadíme formuli A—* A, [A-* {A-^ A)] -+ (A ~* A), modus ponens, _A _» (>l _» A), VP1. do kterého dosadíme za ? i Q formuli A, A —t A, modus ponens. " * Následující věta o dedukci je jedním z prostředků, které zpřehledňují demonstrace a usnadňuji nalezení potřebných důkazů. Princip, který vyjadřuje věta o dedukci, bude mnohokrát použit v našem textu. Potřeba takovýchto prostředků (další budou formulovány v poslední větě tohoto paragrafu) je zcela očividná, neboť důkaz zcela triviálního tvrzení A ^ A měl pět kroků, plně provedené důkazy složitějších tvrzení by byly velice těžko průhledné a přetěžce bychom pro každé jednotlivé tvrzen! hledali znovu a znovu metodu konstrukce důkazu (na druhé straně po nalezení důkazu by ověření, že se jedná o důkaz, již obtížné nebylo, bylo by jenom zdlouhavé). Poznamenejme, že podobná věta o dedukci v predikátovém počtu má ještě širší použití. Pro některé účely je potřeba zdůraznit, že v demonstraci věty o dedukci není (a ani v predikátovém počtu nebude) použit VP3. Nadto si uvědomme, že VP3 nebyl použit ani v důkazu formule A —* A. Věta 2 (o dedukci). Pro každý systém formuli výrokového počtu 7 a pro každé formule výrokového počtu A. 25 plutí 7,A\-% & 7r-A->"B. Demonstrace. 4= K důkazu formule A —■ 55 ze systému předpokladů T stačí přidat dvojici formulí s> Formule A —> A se někdy nazývá zákon totožnosti, srovnej také 3 dále uvedeným zákonem vyloučeného třetího. 35 KAPITOLA I VÝROKOVÝ POČET A, jeden předpoklad ze systému 7, A, E, modus ponetis a získáme důkaz formule 33 ze systému předpokladů 7, A. =S- Nechť ©],..., X>t je důkaz formule 2 ze systému předpokladů 7, A (tedy Dit je totožná s fi). Indukcí budeme pro formule Di,...,23a demonstrovat, že 7\- A —> V, (dokonce induktivně dáme návod, jak transformovat důkaz formule "B ze systému předpokladů 7, A na důkaz formule A —► S ze systému předpokladů T). Rozeberme jednotlivé možnosti, jakými se pro i S k mohla do důlíazu dostat formule V^. (1) V, je buďto axiomem logiky a nebo některým z předpokladů z 7. Pak posloupnost formulí X>j -t (,£-»©<), axiom typu VP1, axiom výrokového počtu nebo jeden předpoklad ze systému T, -4-»Di, modus ponens je důkazem formule A —* CD; ze systému předpokladů 7. (2) Je-li D; formulí A (což je jeden z předpokladů z T,j4), pak h A -+ .A je obsahem předchozí věty, a stačí si tedy uvědomit, že h C zaručuje 7\- C. (3) Jestliže D* je bezprostředním důsledkem formulí D,- a Vy (tzn. užíváme-li na uvedené formule modus ponens), pak Vy je formulí V j —> D; a j, j' < i. Tedy dle indukčního předpokladu existuje posloupnost elt..., Qu., A — Vy která je důkaz formule A -» Vj ze systému předpokladů T (je-li rij = 0, je posloupnost elt..., C„ prázdnou posloupností). Současné indukční předpoklad také zaručuje existenci posloupnosti lB1,...,'Bn.,,A -t (Vj -t D,), která je dôkaz formule A -» Dj. ze systému předpokladů 7. Přidáme-li k posloupnosti £v,..., Q,h, A -+ D j, 3i,..., Sn.,, X -» [Vj -♦ Vi) tři formule (A -* (Vj -> Vi)) - ((A -. ©j) - (X - DJ), axiom typu VP2, (X —* V j) —i (A —> D;), modus ponens, A —i- Vi, modus ponens, dostaneme důkaz formule A —► Vi z předpokladů T. ■ Poznamenejme, že věta o dedukci je asi nejdůležitější ze všech prostředků zpřehledňujících demonstrace. V následujících větách uvedeme některé často používané typy formulí dokazatelných ve výrokovém počtu a zejména další často užívané „důkazové bloky'1, tzn. principy umožňující zkracování a zpřehledňování důkazů. Pro začátek si uvědomme, že princip modus ponens můžeme při použití věty o dedukci reformulovat tak, že jestliže 7\-A a T.XhS, pálí Thfi neboli intuitivně „vše co je dokázáno, lze použít při dalším dokazování". Dále je také evidentní, že pro libovolné 7 a libovolné formule A, 2 a C výrokového počtu jestliže 7\-A-r*B a 7\-%^>e, pak 7 h A — 6, 36 SYNTAX VÝROKOVÉHO POČTU_______________________________§2 neboť za uvedeného předpokladu je 7, A h 35, věta o dedukci aplikovaná na A —> 35, 7, A h e, princip modus ponens užívající Tbí^E, 7\-A^G, věta o dedukci. Na uvedený princip se budeme odvolávat jako na princip tranzitivity implikace. Zkrátí nám mnohokrát demonstrace (tento princip můžeme chápat i jako jinou formulaci tranzitivity implikace). Možnost odvodit vyslovený princip (při jehož odvození jsme použili VP2) lze pojímat jako upřesnění již deklarovaného faktu, že VP2 je „zesílením" principu tranzitivity implikace. Uvědomme si, že větl o dedukci (spolu s modus ponens) stiri poněkud rozdíl mení ukázáním dokazatelnosti formule ve výrokovém počtu a prokázáním, že k ní příslušný odvozovací princip je nahraditelný (tedy i správný) ve zvoleném systému. Např. přijímáme-li princip tranzitivity implikace, dostaneme dokazatelnost tranzitivity implikace tj, h (.4 —> B) —• [(3 —► {A -+ 33), (2) \--<-iA-*A, 6^ Od scholastické logiky je známo jako .,Ex impossibiii sequítur quodübet"; užitím pravidla (4) komentované věty na tento princip dostaneme (viz cv. 6) „Nutné vyplývá z čehokoli" neboli „Ne-cessarium sequitur ad quodlibet". 7) Zákon Dunse Scota. bychom mohli napsat (->A &c A) —• S, protože ->A lc A je „nemožné", srovnej „vyloučení kontradikce", tj. formuli (17) ze sez.ua.mu ke konci příštího paragrafu. Při převáděni (1) věty 3 na tvar (-v*! & A) -—• "B je vhodné využít formule (21) z téhož seznamu. 8í V této souvislosti je poněkud překvapující, že není známo, ze by se tato škola pokusila explicitně popsat pravdivostní hodnotu negace v závislosti na pravdivostní hodnotě příslušné FoTmule. Naproti tomu popis pro implikaci, kterou je možno považovat za „složitější", je dokumentován. 37 KAPITOLA I VÝROKOVÝ PQCET (3) r-yi^^Vl, (4) h(^-.S)-(5) \-A-+ [-.3 -♦ h-B - VI) -iA-*n- Demonstrace. (1) I-VI -> (-3 -» -i/l), VP1, VP3, i- VI-. (-VB- -*Vt), 1 r- (VB--01-i -VI) 2), -'S) h i-%A- -♦(■VI -ř-.-r VI), -.VI h {-v/l -+ ->->Vl), h (vi -» — x) - (--vi -t yt) -■VI h -t->A -* A, -y-tAbA, h -.vi -t yl, (3) )- -.-.vi -f vi. h (-.-.-vi -♦ vi) -»(yl -♦ -.vi) h A -* -.Vi, (4) A -> S h -.VI -♦ -.-.B, h (-.VI - -.-.3) -. (-3 -» Vi) A-»íh^S-tV, 1- (,/t-*S)^(-.3 —VI), (5) yi,ji-*s t- 3, princip tranzitivity implikace; (2) h -.-Jl -> (VI -* -.-.V), aplikace (1), věta o dedukci, VP3, princip modus ponens, věta o dedukci, věta o dedukcí; aplikace (2), VP3, princip modus ponens; (2) a (3) a dvojnásobně princip tranzitivity implikace, VP3, princip modus ponens, věta o dedukci; aplikace modus ponens na předpoklady, ■A I" (./l —* 3) -+ 3, věta o dedukci aplikovaná na for- muli A -+ 3, A b- ((A -> 3) - 3) ^ (VB - -,(yi -> 3)), (4) aplikované na formuli {A - 3) a formuli 3, ■A I '3 —t -.(yl —t 3), princip modus ponens, h-yi^ (-,'B _,-,(/!_ 3)), věta o dedukci. ■ Předchozí věta je formulováni pro libovolné formule jH, B výrokového počtu. První část následující věty však ukazuje, že případná formulace pouze pro výrokové proměnné by byla slabší jenom zdánlivě. Uvědomme si, že zákon Dunse Scota (spolu s modus ponens) umožňuje ukázat, že systém formulí T je sporný, právě když existuje formule yt taková, že z předpokladů Xje dokazatelná jak formule yl, tak i formule VI. * Motivujme nyní poněkud podrobněji tvrzení následující věty. Jak jsme již uvedli, jedná se o formulaci dalších odvozovacích principů. Na jedné straně použití těchto dodatečných odvozovacích principů podstatně zjednoduší konstrukci důkazů, ale na druhé straně následující věta prokazuje, že tyto principy jsou v každém jednotlivém případě nahraditelné pomocí jediného dedukčního pravidla modus ponens (při současném využití axiomů VP1-VP3), 38 SYNTAX VÝROKOVÉHO POCTU Ü» Výše jsme vlastně intuitivně zdůvodňovali vztah (5) předchozí věty jeho reformulací tvaru h .A -+ [3 -> ^{A -» -.3)] (viz (2) ze seznamu uvedeného v §3). Pokud v tvrzení (5) místo 3 píšeme -VB, získáme h A —> [-.-VB -» -.(yl —* -VB)]. Je celkem jednoduché reformulaci h A -» [3 -> -*{A -> -VB)] z dokazatelnosti y- A —t [-.-.S —» -.(yl —► -.3)] ukázat9'. Je však pochopitelně výhodnější prokázat jednou provždy možnost nahradit podformule formulemi s nimi ekvivalentními než hledat konstrukci důkazu pro každý jednotlivý případ zvlášť. Princip, o kterém je řeč, můžeme formulovat 3>i s Q,,...,yt s Q* h .A = 3, kde 3 vznikne nahrazením některýrM (tzn. ne nutně všech101) výskytů podformulí ?!,..., IP* formule yl po řadě formulemi Q.,..., Qfc. Dosud jsme však podrobněji nepopsali chování spojek, které zavádíme jako zkratky, a proto budeme princip formulovat raději ve tvaru 9, - Q,,Q. ~*9lt...,7k - Qfc,Qt -» 7k f- yl -> 3. Při této formulaci také více vynikne, že pro jednu implikaci, svazující formule A a.'S, potřebujeme (v obecném případě) obě implikace svazující 7i a Q;. Na druhé straně již pak triviálně symetrií dokážeme i druhou implikaci svazující formule yl a 3, K problematice popisu chovám dalších spojek se vrátíme na konci příštího paragrafu poté, co dokončíme, pokud možno v sevřené podobě, popis vlastností negace a implikace. Pak bude talie zřejmé, že obě uvedené formulace vyjadřují totéž. Poznamenejme, že v demonstraci analogické věty pro predikátový počet budeme muset rozlišit více případů (kvantifikace), ale podstatné je, že příslušná část demonstrace z tohoto paragrafu je aplikovatelná i při dosazování formulí predikátového počtu (viz formulaci v §3 kap. II). V příští kapitole již nebudeme demonstraci tudíž znovu opakovat. Důkaz sporem a důkaz rozborem případů jsou tak běžné odvozovati principy v matematice, že by neměly potřebovat přílišné vysvětlování. Běžnost těchto principů naopak způsobuje, že kdybychom nebyli schopni možnost použití těchto dovozovacích prostředků předvést, pokládali bychom náš systém za „slabý" (uveďme však, že např. intuicionistická logika nepřipouští důkaz sporem). Pro lepší orientaci připomeňme, že např. běžný důkaz, že součin dvou po sobě jdoucích přirozených čísel je sudý, používá rozbor případů, protože v něm rozlišíme případ, že x je sudé (a pak součin s čímkoli je sudý), a případ, kdy x je liché, ve kterémžto případu si uvědomíme, že potom je x + 1 sudé. Nicméně formulace principu důkazu rozborem případů může vyvolat jisté obtíže. Rozeberme tedy trochu podrobněji formulaci tvrzení (4) následující věty. Na první pohled se zdá nepřirozené, že na jedné (levé) straně se mluví o dokazatelnosti z předpokladu yl V 3 {tedy z disjunkce) a na straně druhé (pravé) se vyžaduje současná dokazatelnost jak z předpokladu A, tak i z předpokladu 3 (pro jednoduchost výkladu teď předpokládám, že systém T, použitý při obecné formulaci ve větě 4, je prázdný). Mnozí studenti by však pokládali za intuitivně přijatelnější, kdyby i na pravé straně se požadovala dokazatelnost z předpokladu A nebo z předpokladu 3. Takovéto oslabení požadavku na pravé straně však není přijatelné, jak vzápětí ukážeme. Uvažujme výrokové proměnné p a q a formuli p V q. Podle první věty tohoto 9' Stačí použít na začátku i na konci demonstrace větu o dedukci a jako jádro demonstrace užít tvrzení (3) předchozí věty, formuli A —> [-1-1B —• ~>(A —» -.B)] a princip tranzitivity implikace. ln' Tedy korektně dostaneme napr. f = Q h (0> — 7) = ("? — Q). 39 KAPITOLA I VÝROKOVÝ POČET paragrafu a podle věty o dedukci je p h p, a tedy (php nebo q h p); naproti tomu neni p V q h p. Z věty o dedukci bychom pak totiž dostali h (p V q) —> p, ale tato formule není pravdivá při ohodnocení, které proměnné p přiřazuje 0 a proměnné q přiřazuje 1, a tedy intuitivně cítíme, že posledně uvedená formule nemůže být dokazatelná ve výrokovém počtu (zcela rigorózně úvahu dokončíme použitím věty o korektnosti uvedené v následujícím paragrafu). Poslední princip je speciálním případem rozboru případů, neboť formule pV->p je zkratkou za formuli ^p —> -ip, a je tedy dokazatelná ve výrokovém počtu. Uveďme, že formule p V -rp je označována jako zákon vyloučeného třetího (tertium non datur), který byl velmi zdůrazňován již Chrýsippem ze Sotoi. Prosím čtenáře, aby si uvědomil, že důkaz sporem je svou strukturou dosti výjimečný. Běžně z předpokladů, které pokládáme za správné, vyvozujeme další tvrzení, při důkazu sporem naopak předpokládáme platnost toho, co chceme vyvrátit. Ve zněni věty o nahrazení se uvažuje posloupnost výrokových proměnných Pí,. . . , Pfc; chceme-li být naprosto přesní, musíme explicitně přijmout (implicitně evidentně přijímaný) předpoklad, že uvedené výrokové proměnné jsou od sebe různé, tj. že i-tá hodnota posloupnosti pí.....Pfc je různá od j-té pro různá i, j £ fe. Naproti tomu různost formulí Ti,., ., Tt se nevyžaduje. Věta 4. (1) (Věta o nahrazení). Jestliže formuje B výrokového počtu vznikne nahrazením všech výskytů (od sebe různých) výrokových proměnných Pí,-- -,Vk po řadě formnlemi ?u ,.., yk výrokového počtu ve formulí A, pak (r-X) =* (hS). (2) (Věta o ekvivalenci). Vznikne-li formuje 3 výrokového počtu z formuje A výrokového počtu nalirazením jejích podformulí ?i,..., 7k po řadě for-mulemi Qi,..., Qk výrokového počtu, pak řj -»Qi, Oi -f ?!,..., D»t -»S3», Qfc —Tk h A - %, tedy speciálně h A zaručí ?i -> Qlt Qx -♦ flt..., 3>fc _+ Qj.,Ofc -» 7k h S. Nadto pro každý systém 7 a všechny formule A, S a G výrokového počtu platí (3) (Věta o důkazu sporem). 7 h A «■ [7, ^A h -i(e ~» C)], (4) (Věta o důkazu rozborem případů). 7, A V 3 r-e «■ & [7,A\-e a současně 7, B h C], (5) (Věta o neutrální formuli). Q"hE » o [T,A\-S a. současně 7, ^A h e]. Demonstrace. (1) Buď Vu---,®* důkaz formule A. Uvažme posloupnost formulí *l,•-•)€*', kde Ci jsou (pro i £ k') formule vzniklé nahrazením výrokových proměnných Pi,...,Pi po řadě formulemi 3>i,..., 7k výrokového počtu ve formuli V,. Ukážeme, že posloupnost e i,..., £,,.. je opět důkazem. Je-li Dj axiomem výrokového počtu, je axiomem téhož typu i formule (3;. Tato úvaha je korektní v případě nahrazování výrokových proměnných. Avšak v případě nahrazování pOíi/oTTUuíi jinými formulemi již korektní neníu). Je také zřejmé, že pro korektnost uvedené úvahy potřebujeme, aby výrokové proměnné v posloupnosti pí,. . .,pt byly různé12'. Například nahrazením podformule q —• p výrokovou proměnnou q dostáváme z formule P ~* (i —*P)i která je axiomem, formuli p —» q, která již dokazatelná není (což by intuitivně mělo být zřejmé, přesná demonstrace využije větu o korektnosti z následujícího paragrafu). 12> Ku příkladu nahradíine-li r v axiomu [p -. (q — r)] -»[(p -. q) ->(p -, t)] jednou formuli p 40 SYNTAX VÝROKOVÉHO POCTU Jestliže formule X>i byla odvozena pomocí modus ponens aplikovaného na formule ©j,Dj', kde j,j' < i, pak formule Dj' je formulí D j —* D;. Po nahrazení výrokových proměnných Pi,,..,Pk P° řadě formulemi ?i,...,3** výrokového počtu ve formuli 33j —* Di dostaneme formuli 6,, —> 6; (tzn. provedeme-li napřed nahrazení a pak spojíme formule do implikace, dostaneme totéž, jako když napřed spojíme formule do implikace, a pak provedeme nahrazení; viz demonstrace věty §1). Formule C; tedy opět vyplývá z formulí Cj a &y pravidlem modus ponens. (2) Prokážeme opět indukcí, tentokrát postupně pro formule vyskytující se ve vytvářející posloupnosti formule A výrokového počtu. K prověření kroku pro konstrukci formule negací stačí prokázat tvrzení p ^ q, q —> p !----ip -> ^q, což je důsledkem (4) předchozí věty a věty o dedukci. Pro krok odpovídající konstrukci implikace stačí prokázat pí -* qt, qt -♦ Pi,p2 -» q2,q2 -» Pa r- (pí -+ p2) -> (qi.-n q2), což získáme dvojnásobnou aplikací principu tranzitivity implikace a věty o dedukci. (1) předchozí věty věta o dedukci princip modus ponens využívající 7 h A věta o dedukci VP3 a princip modus ponens princip modus ponens využívající h 6 —► 6 věta o dedukci aplikovaná na 7, A h & věta o dedukci aplikovaná na 7, B h £ (4) předchozí věty a princip modus ponens dvakrát užitý princip tranzitivity implikace (5) předchozí věty použité pro -iC a C třikrát užitá věta o dedukci; uvědomte si, že 7,7 h Q, právě když 7 h Q VP3 a princip modus ponens princip modus ponens. Nyní si stačí uvědomit, že A V B je zkratkou za ->A —► B. Obrácená implikace je triviální, neboť h A —» (-] 7, ^a h a -» -.(e -+ e) 7, --a \- -.(e -»e) *= 7\-^A 7h(e-7Y-A - -(e -* e) *e)-».A (4) <=7\-A -ThB -r, m - -.s)h^e^e [-,e --.(-.e-»ej] h-£ -h -(-e -»e) h(^e-T, (-wí - e)^e ^B)i-e a jednou ponecháme beze zmeny (tj. nahradíme T formulí r) a současně nahradíme-li q formulí p (tzn. uvažujeme-li posloupnost Pi,P'2,P3, kde pí a p2 jsou rovny r a P3 je rovné q), dostaneme formuli [p —* (p —* p)j —• [{p —» p) —» (p —t r)] a po dvojnásobném užití principu modus ponens bychom dále dostali, že je dokazatelná formule p —»■ r, jejíž n ed o kazatel nos t jsme již deklarovali. 41 KAPITOLA I VÝROKOVÝ POČET neboť dle zákona Dunse Scota h --(6 -+ C) -+ [(e -► 6) -» B] pro libovolnou formuli B výrokového počtu, a k ukázáni spornosti teorie T,- 6. * Již jsme zdůraznili, že zkoumaný systém axiomů a dokazovacího pravidla není jediný možný. Pokud by někdo chtěl mít jen konečně mnoho axiomů (nestačilo by mu konečně mnoho typů axiomů), mohl by přijmout za axiomy VPť VP2' VP3' p -• (q -+p), |P - (fl - I*)] - [(p -* q) - (p -» t)], (^p^-q)-*(q^p) a pravidlo modus ponens a pravidlo nahrazení ve výrokovém počtu (čímž myslíme pochopitelně pravidlo popsané větou o nahrazení, tj. pravidlo dovolující z formule T vyvodit jakoukoli formuli, která vznikne z formule 7 nahrazením všech výskytů (od "sebe různých) výrokových proměnných p i,..., p t po radě formuiemi 9i,...,7k)-V takovémto systému evidentně dokážeme — v důsledku věty o nahrazení — právě tytéž formule jako v námi vybraném systému. Uvědomte si, že pokud používáte náš původní systém, smíte nahrazovat proměnné v axiomech VP1'-VP3' pouze na začátku (a tak získáte naše axiomy VP1-VP3), naopak při použití pravidla nahrazení smíte nahrazovat v jakékoli již dokázané formuli. Tvrdíme, že „zvětšení" možností při druhém přístupu je nepodstatné. 42 §3 ÚPLNOST VÝROKOVÉHO POCTU, NORMÁLNÍ TVAR FORMULE Vztah mezi syntaxí a sémantikou výrokového počtu popisuji zejména věty o korektnosti a úplnosti, které dohromady vyjadřují rovnocennost vztahu dokazatelnosti a tautologického důsledku. Uvědomme si, že pro slabší verzi věty o úplnosti nepotřebujeme dodatečné předpoklady na sílu metamatematiky. Věta 1 (o korektnosti). Pro každý systém formulí 7 a icaždou Formuli A výrokového počtu platí (T\-A) =* (T(=A), speciálně tedy každá dokazatelná formule je tautologií, tj. (h A) => (j= A). Demonstrace. Nejprve je třeba ověřit, že každý axiom výrokového počtu je tautologií, ale k tomu stačí ukázat, že každá z formulí VP1'-VP3' výrokového počtu je tautologií, protože naliradíme-li v tautologii výrokové proměnné jakýmikoli formulemi výrokového počtu, dostaneme opět tautologii. Dále si uvědomíme, že jsou-li formule A a A —^ B tautologie, je tautologií i S (dokonce formule p —► [(p —* q) —* q] je tautologií). Je-li T>i,.. .,"Dk důkaz ve výrokovém počtu, ukážeme tedy indukcí, že pro každé í ž k, je D; tautológií. Je-li systém T prázdný, jsme hotovi. Předpokládejme tedy, zeje neprázdný a že T h A. Pak existuje konečný podsystém Ci,..., Cyt systému T tak, že Clr..., Cj. h A, protože v jakémkoli důkazu je možno použít jen konečně mnoho předpokladů. Takže ^-násobnou aplikací věty o dedukci dostáváme \- Ci —>(... —* (Ct —» A)...), a dle výše prokázaného je tedy |= ßj —i- (,..—» (C* —> j4)...). Tudíž stačí fc-násobně užít, vztahu (|= 2 -» C) =* (3 |= G) (viz závěr §1). ■ Větu o korektnosti je možno ekvivalentně formulovat tak, že žádný sporný systém formulí není splnitelný. Stačí si totiž uvědomit, že pro libovolnou formuli A a libovolný systém S formuli výrokového počtu je S, ->A sporný, právě když S h A, a současně S, -JI není splnitelný, právě když S (= A (a že prázdný systém není sporný). Analogicky lze reformulovat níže vyslovené věty o úplnosti tak, že každý bezesporný systém formulí je splnitelný (při slabší verzi se předpokládá konečnost systému S). Při demonstraci věty o úplnosti, ke které za okamžik přistoupíme, využijeme pomocný vztah, který je vhodné formulovat explicitně jako lemma, protože se na něj budeme odvolávat také ve třetí a rovněž v závěrečné kapitole. K jeho formulaci je výhodné přijmout dohodu o symbolice. Značení. Pro libovolnou formuli A a pro libovolné ohodnocení v definujeme výrokovou formuli A^vl tak, že >UVJ označuje samu formuli A za předpokladu, že A[v] = 1, a značí formuli ->A v případě, že A[v] = 0. i;; KAPtTOLA I VÝROKOVÝ POČET Nahlédněme, že pro každou formuli 23 a pro každé ohodnocení v je formule 25'VJ pravdivá. Lemma (A. Church). Pro libovolné' ohodnocení v výrokových proměnných a libovolnou formuli 2S výrokového pocta, ve která se vyskytuji nanejvýše výrokové proměnné pí,... ,pk jest Demonstraci provedeme indukcí podle složitosti formule 23. (1) Je-li 23 výrokovou proměnnou, je proměnnou Pí pro nějaké i á k, a v tomto případě tedy není co dokazovat. (2) Nechť p[vJ,... ,p[vJ h eH. Uvědomme si, že {-.e)l""J je buďto formule 6M (v případě, že ß[v] = 0, tj. {-^.)[v\ = 1), nebo formule -.^eľvJ (jestliže G[v] = 1). V prvém případě opětovně není co dokazovat, ve druhém využijeme h S —> —>—>C a princip modus ponens. (3) Buď tedy 23 tvaru e —> D, předpokládejme, že dokazovaný vztah platí pro formule e a TJ a rozlišme následující tri případy: (a) Je-li e[v] = 0, je (6 - 23) (v] = 1, a tedy TJ) (viz tvrzení (1) třetí věty §2) a princip modus ponens. (b) Je-li £[v] = 1, je {C ^ 23) [v] = 1, a tedy (G -> 23) M je opět formulí e -» TJ. Předpokládáme p1"-',..., p[vJ h 23, a tedy stačí použít VPI a princip modus ponens. (c) Zbývá poslední možnost, totiž C[v] = 1 a současně 23[v] = 0; v tomto případě je (e — 23)[v] = 0, a tedy (e -* 23) M je formulí -(e -» 23). Předpokládáme tudíž PaľvJ,.--,p[vJ I" C a pívJ,...,|>ívJ r- ^23. Na závěr použijeme he^ [-,£> —> -i(C —» 2J)] (viz bod (5) předposlední věty předchozího paragrafu), a tentokrát dvojnásobně princip modus ponens. ■ Věta 2 (o úplnosti1' ve slabší verzi, B.L.Post). Pro každý konečný systém formulí 7 a každou formulí A výrokového počtu platí (7[=A) =* pTr-A), speciálně tedy každá tauíoíogie je dokazatelná, tj. ((= Ji) =* (r- Ji). Demonstrace. V každé formuli výrokového počtu se vyskytuje jenom konečně mnoho výrokových proměnných (viz definici formule). Předpokládáme, že Ji je tautologií, ve které se vyskytují pouze výrokové proměnné pi,...«Pfc- Nejprve nahlédněme, že předpoklad, že JI je tautologií, zaručuje, že AľvJ je formulí A pro každé ohodnocení v. Pročež Churchovo lemma nám zajistí PÍ*j....,přji-A pro každé ohodnocení v. ^ Název věty odráží, že se podařilo úplně charakterizovat pojem tautologického důsledku pomocí dokazatelnosti při zvolených axiomech a dokazovacím pravidlu. ■1-1 ____________ÜPLNOST VÝROKOVÉHO POCTU, NORMÄLNÍ TVAR FORMULE__________§3 Využitím vety o neutrální formuli ukážeme, že z předchozího vztahu můžeme postupně vypustit kteroukoli proměnnou. Předpokládejme tudíž, že jsme již prokázali, že pro n < k a, každé ohodnocení v výrokových proměnných platí nrvJ nľvj „M |_ A Pí .....Pn >Pn+l r -n- Kromě ohodnocení v zkoumejme ještě ohodnocení w, které je pro všechny výrokové proměnné různé od pn+i shodné s w, ale pro p„+i položíme w(pn+i) = 1, právě když v(p„+i) = 0. Tato dvě ohodnocení zaručí vztahy pW,...(pM,pB+lHJl p[vJ,...,pí"J,-pn+il-A Podle věty o neutrální formuli obdržíme p[vJ,...,pMhA Takže provedeme-li vypouštění proměnných i;-krát získáme r- JI, tzn. dokazatel-nost tautologie JI ve výrokovém počtu bez předpokladů. Tím jsme dokončili demonstraci (\= A) => (h Ji), tzn. tvrzení věty pro speciální případ, že systém 7 neobsahuje žádný předpoklad. Zbývá zobecnit prokázané na konečné systémy formulí výrokového počtu. Předpokládejme tedy Si,..,,Bj. (= JI. Užijeme-li fc-násobně vztahu (T, 23 j= JI) =;> (7 |= 23 -► A) (viz §1), dostaneme [= 23, -+ (232 -• ...{©* -+ A)...) a podle předchozí části demonstrace dále obdržíme h Ti\ —» (232 —*-... (23* —* JI)...), tedy A^násobné užiti věty o dedukci ukončí demonstraci. ■ Uvedli jsme, že větu 2 lze ekvivalentně formulovat tak, že každý konečný bezesporný systém formulí je splnitelný. Předpokládejme totiž, že T je konečný neprázdný bezesporný systém formulí a budiž p proměnná vyskytující se v některé formuli ze systému 7. Bezespornost 7 zaručí, že není 7 I—>(p —» p), pročež v důsledku věty 2 není 7 |= ->(p —> p). To znamená, že existuje ohodnocení v takové, že Jl[v] = 1 pro každou formuli JI ze systému 7 (a -i(p —> p)(v] = 0). Naopak z naší reformulace plyne tvrzení věty 2, neboť jestliže pro konečný systém 7 není 7 h A, musí být 7, - q by musela být pravdivá. To vede k tomu, že hledané ohodnoceni v, pro které by nebyla formule VP2' pravdivá, by muselo splňovat v(r) = 0,v(p) = 1 a v(q) = 1. Pro takovéto ohodnocení je však antecedent formule VP2', tj. formule p —* (q -» r) nepravdivá, a tedy VP2' je pravdivé. * 45 KAPITOLA! VÝROKOVÝ POČET Syntaktická verze kompaktnosti (tzn. tvrzení, že pro každý systém 7 a každou formuli výrokového počtu ze vztahu 7 \- A plyne existence konečného podsystému S systému 7 takového, že S t- A) je triviální. Každý důkaz totiž může využít pouze konečně mnoha předpokladů (neboť důkaz je konečnou posloupností). Zobecnění předchozí věty na důkazy ze systému předpokladů je tedy možné jenom v případě, že pro každý systém předpokladů 7 a každou formuli A výrokového počtu by ze vztahu 7 \= A plynula existence konečného podsystému S systému 7 takového, že S [= A. Toto tvrzení je obsahem následující věty vztahující se k sémantické verzi kompaktnosti. Již jsme se zmínili, že její demonstrace vyžaduje nějakou formu axiomu výběru21. Věta 3 (o kompaktnosti). System formulí výrokového počtu 7 je splnitelný, právě když každý konečný podsystém systému 7 je splnitelný. Tedy pro každou formuli A výrokového počtu jest 7 |= A, právě když existuje konečný podsystém S systému 7 tak, že S \= A. Demonstrace. =*• je triviální. 4= Předpokládejme, že každý konečný podsystém S C T je splnitelný. Bud í dobré uspořádání všech výrokových proměnných vyskytujících se v 7. Chceme indukcí dle š sestrojit ohodnocení, při kterém budou všechny formule z 7 pravdivé. Pro každé p vyskytující se v T sestrojíme postupně (částečné) ohodnocení vp a to tak, že pro něj platí současně: (1) Vp je definované na všech q < p, (2) pro r < p je zobrazení vr částí zobrazení vp, (3) pro každé konečné S C CT existuje ohodnocení w D vp, při kterém jsou pravdivé všechny formule z S. Předpoklad o splnitelnosti ze začátku demonstrace je indukčním předpokladem pro nejmenší prvek v uspořádání á (a pro ohodnocení, které je prázdnou množinou). Nechť p je následovník q v uspořádání ^ (tzn. pro žádné r není q < t < p) a buď Vq (částečné) ohodnocení příslušné k q. Definujeme vp jako funkci, která je nadmnožinou funkce vq, a uavíe je definována v bodě q. Hodnota funkce vq v bodě q je 1, právě když pro každé konečné S C T existuje ohodnocení w D vq. pro které w(q) = 1 a při kterém jsou pravdivé všechny formule z S. Pokud právě vyslovená podmínka neplatí, definujeme hodnotu funkce vp v bodě q jakožto 0. Je potřeba pouze ukázat platnost části (3) indukčního předpokladu pro vv při druhé volbě. Nechť pro konečné S C T neexistuje ohodnocení w D vq, pro které w(q) = 1 a při kterém jsou pravdivé všechny formule z S, a dále buď konečné 31 C 7 dáno. Dle indukčního předpokladu pro q existuje w rozšíření vq, při kterém jsou pravdivé všechny formule z S a 31 a pro toto ohodnoceni je w(q) = 0. 2' Axiom výběťu AC je tvrzení, že pro každý systém neprázdných množin je možno najednou každé množině ze systému přiřadit (vybrat) jeden její prvek, tun. zaručuje existenci „výběrové" funkce. Je možno ukázat, že toto tvrzení je (v běžné teorii množin) ekvivalentní tvrzení, že na každé množině existuje dobré uspořádání- Popis pojmu uspořádání najde čtenář ve čtvrtém příkladu §2 následující kapitoly. Připomeňme, že uspořádání í na množině A je dobré, jestliže každá neprázdná část A má nejmenší prvek ve smyslu ^ 46 ____________ÚPLNOST VÝROKOVÉHO 1'OCTU. NORMÁLNÍ TVAR FORMULE__________|3 Je-li p limitní v uspořádání ž (tzn. pokud pro každé q < p existuje r takové, le q < t < p), definujeme příslušné vp jako sjednocení všech (částečných) ohodnocení Vq sestrojených pro q < p (definiční obor takto definovaného vp triviálně obsahuje každé q < p a podmínka (2) zaručí, že vv je funkcí). Při této definici platí pro vp i podmínka (3): kdyby totiž pro nějaké konečné SC7 neexistovalo ohodnocení w D vp, při kterém jsou pravdivé všechny formule z S, muselo by již existovat q < p talc, že pro (částečné) ohodnocení va příslušné k q už neexistuje ohodnocení w D vq, při kterém jsou pravdivé všechny formule z S (neboť v S se vyskytuje jen konečně mnoho proměnných a stačí tedy q zvolit tak, aby pro těchto konečně mnoho t platilo: jestliže r < p, pak r < q) — spor s indukčním předpokladem (3). Závěrem definujeme hledané ohodnocení definované na všech výrokových proměnných vyskytujících se v T jako sjednoceni indukcí sestrojených (částečných) ohodnocení. Druhá Část věty plyne triviálně z prokázaného (a naopak z druhé části věty plyne část první), neboť ÍR f= 3), právě když systém IR, ->D není splnitelný. ■ V předchozí demonstraci jsme použili axiom výběru pouze k existenci dobrého uspořádání uvažovaných výrokových proměnných. Tedy samotný předpoklad, že systém výrokových proměnných je spočetný, tzn. že je očíslován metamatematickými přirozenými čísly, již plně postačí pro prokázání věty o kompaktnosti. Prijímáme-Ii v metamatematice jenom potenciální nekonečno (viz úvod textu; postoj forma-lizovaný napr. teorií ZFpln), nemá předchozí veta rozumný smysl, protože pro konečné 7 není ra dokazovat a nekonečné 1 nemůže jako objekt teorie existovat. Akceptujeme-lí v metamatematice aktuální nekonečno jen částečné (postoj formalizovaný např. teorií GSpin), je existence dobrého uspořádání dokazatelná (v důsledku axiomu fundovanosti). * Rozeberme si podrobněji význam vety o kompaktnosti. Ukážeme, že z věty o kompaktnosti plyne, že každé uspořádání na množině lze rozšířit do lineárního uspořádání *'. Buď •< uspořádání na množině X a nechť systém výrokových proměnných je indexován dvojicemi prvků z X. Buď dále ¥ systém formulí sestávající se z formulí (1) Pa.f, Pto a < i>, (2) -i(p„,t íi Pt.a) pro různá a, b g X, (3) (p„,6 & Pb,c) —» Po,c, pro a,b, c £ X, (4) Po.b VVb.a pro a, b g X. Pro konečnou množinu Y lze každé uspořádáni na Y rozšířit do lineárního uspořádání (důkaz indukcí), a tedy každý konečný podsystém uvažovaného systému je splnitelný. V důsledku věty o kompaktnosti existuje ohodnocení v, při kterém je uvažovaný systém splněn a definujeme-li pro a, b £ X, že a & íi, právě když v(pflhb) = 1, získáme lineární uspořádám na X, které rozšiřuje ^. Podobné úvahy lze aplikova-t i na jiné vlastnosti, jedná se vždy o přenos vlastnosti z konečného systému na systém nekonečný. Důležitější je však si uvědomit, co jsme vlastně ukázali. (1) Pokud přijímáme větu o kompaktnosti za intuitivně zřejmou a dále pokládáme základní fakta teorie množin také za intuitivně zřejmá, ukázali jsme nutnost vzít za intuitivně jasnou i možnost rozšíření uspořádání do uspořádání lineárního. (2) Pokud nasi metamatematikou je některá formální teorie nekonečných množin, ukázali jsme, že v této teorii z předpokladu „věta o kompaktnosti" plyne „věta o rozšiřování uspořádání do lineárního uspořádání", ('S) Protože v ZF bez axiomu výběru není dokazatelné, že každou množinu lze lineárně uspořádat, ukázali jsme, že pro prokázáni věty o kompaktnosti je jistá forma axiomu výběru nezbytná. 3' Axiomy teorie lineárního uspořádání jsou uvedeny v příkladu 4 §2 kap. II. 47 KAPITOLA I VÝROKOVÝ POČET Za předpokladu platnosti věty o kompaktnosti již jednoduše odstraníme ve větě o úplnosti předpoklad konečnosti systému. Věta 4 (o úplnosti, silná verze). Pro každý system formuli 7 a každou formu/i A výrokového počtu platí (7\=A) =*■ (7\-A), takže systém formulí 7 výrokového počtu je splnitelný, právě když je bezesporný. Demonstrace, Jestliže 7 |= A, pak dle vety o kompaktnosti existuje konečný podsystém S systému 7 tak, že S \= A. Slabší verze věty o úplnosti pak zaručí S I- A, a tedy tím spíše jest TI- A. Zbývá ukázat důsledek formulovaný ve větě. Jestliže 7 není splnitelná, pak pro každou formuli A nad příslušnou abecedou platí 7 \= A dle definice tautologického důsledku a podle předchozí Ěásti jest tedy 7h A, tudíž je 7 sporná. Naopak pro každé ohodnocení proměnných a každou formuli nad příslušnou abecedou je z každé dvojice formulí A, ^A pravdivá právě jedna, a tedy jestliže existuje ohodnocení, při kterém jsou pravdivé všechny formule systému 7, pak alespoň jedna z formulí Ji, -Ji není tautologickým důsledkem systému 7, z čehož dostáváme bezespornost systému 7 jako důsledek věty o korektnosti. ■ * Uveďme nyní několik formulí dokazatelných ve výrokovém počtu (viz také cv. 3, 5-8). Do výběru se snažíme zařadit nejčastěji používané tautologie (již tento seznam je dosti dlouhý, seznam užívaných tautologií by přesáhl únosnou míru). Demonstraci dokazatelnosti je možno provést výpočtem pravdivostních hodnot, doporučuji však alespoň pro některé formule si důkaz skutečně sestrojit, je to téměř vždy dokonce rychlejší. K usnadnění navrhuji v pravé straně tabulky jednu z možných metod konstrukce důkazu, přičemž citace čísel z předchozího paragrafu se vztahují k třetí větě zmíněného paragrafu. (Při demonstraci je pochopitelně potřeba vždy nahradit formule obsahující jiné spojky než -■ a —» příslušnými formulemi obsahující pouze tyto spojky). Formule (1) zachycuje jistou komutativitu svázanou s implikací (implikace sama komutativní pochopitelně není) a bude nesčíslněkrát využita v našem textu. (1) [A — (3 -> C)] -> [3 -> (71 — e)] věta o dedukci. Následující tři formule popisují chovám konjunkce. V případě, že se bere konjunkce jako jedna ze základních operací, přijímají se často jako axiomy formule (2)-(4). Analogicky další tři formule popisují vlastnosti disjunkce a v případě akceptování disjunkce jakožto základní operace se často přijímají mezi axiomy rovněž formule (5)-(7): (5), (2) a (3) vše §2 a věta o ekvivalenci, (1) §2 aplikovaná na -.3, (4) a (2) obé §2, princip tranzitivity implikace, VPl aplikovaný na ->2, (4) a (2) obé §2, princip tranzitivity implikace, definice (dosazení do 7 —> 7), {2} (3) A -*{B-(A k 3) - (Ak-B)), A, (4) (Ji & 3) - 3, (5) (AVB)^ hA - S) 48 ÜPLNOST VÝROKOVÉHO POČTU, NORMÁLNÍ TVAR FORMULE__________§3 (6) A -(Ji V 3), (l)§2a(l), (7) S-t(^vS), VPl. Analogicky formule (8) a (9) popisují chování ekvivalence a jsou přijímány jako dodatečné axiomy v případě, že ekvivalence je chápána jako základní operace (kdybychom přijímali ekvivalenci a nikoli konjunkci, upravíme (8) a (9) do tvaru analogického (2)-(4)): (8) [(.a _, 3) & (3 _> A)} — {A = 3), definice (dosazení doJ-> IP), (9) (A = 3) — [(A -» 3) k (B — A)], definice {dosazení do 7 -* 7). Uvedli jsme, že předchozí formule popisují chování dalších spojek. Tomuto intuitivnímu tvrzení je možno dát zcela přesný matematický význam — např. každá formule 6, která má vlastnosti (2)-(4), již musí být ekvivalentní konjunkci, tj. x, _(s -t e),e —A,e -* % v e s (a & $). Formule (10)-(12) popisují komutativitu konjunkce, disjunkce a ekvivalence. Formule (13) a (14) popisují asociativitu konjunkce a disjunkce; jako jejich důsledek tedy dostáváme, že můžeme ve vícečlenných konjunkcích příp. disjunkcích vynechávat uzávorkování. (10) (A k 3) = (3 li A), (4), (2) a (3) vše §2, věta o ekvivalenci, (11) (Ji V 3) = (3 V Ji), (4), (2) a (3) vše §2, věta o ekvivalenci, (12) (Ji = 3) = (3 = Ji), (9), (10) a (8), princip tranzitivity implikace, (13) [(Ji k 3) k G] = [A k (S k e)], (2)-(4) a věta o dedukci, (14) [(JI V 3) V e] = [A V (3 V £)], věty o rozboru případů a dedukci. Formule (15) a (16) popisují vztah mezi konjunkcí a disjunkcí a jsou nazývány de Morganova pravidla. Vztah byl znám již ve středověku, v devatenáctém století znovu objeven. (15) i(jl k 3) = (-JÍ v ->$), (2) a (3) §2 a věta o ekvivalenci, (16) -.(.A V S) = (-iJl k ->B), (2) a (3) §2 a věta o ekvivalenci. Formule (17) se nazývá (zákon) vyloučení kontradikce (vyloučenísporu; takovýto princip se vyskytuje jíž u Aristotela), formule (18) je analogií věty o neutrální formuli. Formule (19) a (20) zachycují distributivitu konjunkce a disjunkce. Formule (21) se někdy nazývá slučování premis. Formule (22) a (23) vyjadřují, že k formuli můžeme beze změny smyslu přidat do konjunkce tautologii a do disjunkce kontra-dikci. Poslední dvě formule zachycují nepodstatnost opakování formule v konjunkci a disjunkci (idempotence). (17) -.(Ji ti -Ji), (2) a (3) §2, v. o ekvivalenci a h Ji -» Ji, (18) (-.Ji -^ Ji) -> Ji, -.Ji -» A, - 6], věta o dedukci, (2)-(4), modus ponens, (22) A = [A k (B -> B)], (2), (3), věta o dedukci a princip modus ponens, (23) A = [A V ->(B — S)], (22) aplikovaná na ->.A, (15) a věta o ekvivalenci, (24) A s (.A & A), (21) a věta o dedukci, (25) A = (AV A), (24), (16) a věta o ekvivalenci. * Závěrem uvedeme větu ukazující, že každou formuli výrokového počtu lze psát v poměrně jednoduchém tvaru. Uvědomme si, že při zadaném počtu výrokových proměnných umožní následující věta navíc předem odhadnout, kolik symbolů je zapotřebí, aby ke každé formuli s daným počtem výrokových proměnných existovala ekvivalentní formule výrokového počtu s tímto počtem symbolů. Definice. Literály rozumíme výrokové proměnné a jejich negace. G Věta 5 (o normálním tvaru, normální formě). Ke každé formuli A výrokového počtu existuji Formule B, G výrokového počtu, ve kterých jsou nejvýše výrokové proměnné vyskytující se ve formuli A, ŕbrmuie B je konjunkcí formuli, které jsou disjunkcemi literálů^ (konjunktivní normální tvar přip. forma), formule C je disjunfoí formulí, které jsou konjunkcemi literálů (disjunktivní normální tvar príp. forma) a piati h(jlsS)fe(A=e). Demonstrace. Nechť pi,...,pjt jsou právě všechny výrokové proměnné vyskytující se ve formuli A výrokového počtu. Buď e disjunkcí všech konjunkcí tvaru p[vJ &...& p[vJ, kde v je ohodnocení proměnných pí,.-., Pit, pro které je A[v] = 1; pokud takové v neexistuje, tzn. pokud je A kontradikcí, definujeme e jako formuli Pj k -ipi &:... Ji p* k - C[v]= 1. Naopak pokud pro ohodnocení v, w není v(p;) = w(p;) alespoň pro jedno i ž k, je (p[vJ Si... k p[vJ )[w] = 0, z čehož A[v] ss 0 =* e[v] = 0. Dle Poštový věty o slabé úplnosti je tedy h A = C. 4) Disjunkce literálů se nazýva klauzule. 50 ____________TjPLNOST VÝROKOVÉHO POČTU, NORMÁLNI TVAR FORMULE__________§3 Pro konstrukci konjunktivní normální formy sestrojme disjunktivní normální formu X> formule -VI, pakr- A = ->TJ a formuli B dostaneme aplikací tvrzení (15) a (16) předchozího seznamu na formuli ->3>, ■ O formuli v normálním disjunktivním (resp. konjunktívním) tvaru se někdy mluví jako o úplném tvaru, jestliže všechny členy disjunkce (resp. konjunkce) mají tytéž proměnné. V předchozí demonstraci jsme sestrojili úplné tvary. Navíc jestliže A není kontradikcí, v sestrojených členech disjunkce jejího disjunktivního normálního tvaru se nevyskytovaly současně nějaká výroková proměnná a negace této výrokové proměnné. 51 CVIČENÍ I 1) Ukažte, že (p —» q) -^ (p — -q) a -i{p —► -iq) —» (p —> q) jsou formule výrokového počtu, najděte všechny jejich podformule, určete všechny společné pod-formule. Je slovo q) —» (p společným podslovem, či dokonce společnou podformulí? Prokažte. Sestrojte tabulky pravdivostních hodnot těchto formulí. Je některá z nich tautologií? Vyjádřete formule ekvivalentně jednoduššími formulemi výrokového počtu. 2) Prokažte větu z §1 tím, že pro každou formuli vzniklou nahrazením podformule přímo sestrojíte její vytvářející posloupnost na základě vytvářejících posloupností formule, ve které nahrazujeme, a formule, kterou dosazujeme, 3) Jsou formule {q -» r) — ((-ip -> t) — [fp -* q) -* r]), -i(p -» q) — p a p —t {-ip — q) tautologiemi? Sestrojte (podejte návod konstrukce) jejich důkazy (návod: pro prvou formuli použijte tranzitivitu implikace a větu o neutrální formuli, pro druhou tvrzení (3) ze třetího paragrafu a způsob zavedení konjunkce, pro třetí zákon Dunse Scota) a zkuste jim dát intuitivní význam (dokazatelnost uvedených formulí využijeme v následujícím textu). Dále dokažte (p—>q) = (^p V q) a prokázané vy užij te k dokázání [(p & q)—>r] = [(P -» r) V (q -» t)]. Návod: Navíc užijte de Morganovo pravidlo, (25) §3, komutati-vitu a asociativitu disjunkce a větu o ekvivalenci. 4) Ukažte, že formule (q —* t) —* [(p — q) —» t] nem tautologií. Srovnejte intuitivní význam této formule a tranzitivity implikace. 5) Popište tabulku pravdivostních hodnot pro vylučující disjunkci a srovnejte ji s tabulkou pro negaci ekvivalence. Dokažte [(p V q) & -i(p k q)] = -i(p s q). 6) Při použití prvních čtyř tvrzení věty 3 §2 (a věty o ekvivalenci) ukažte a -»-.(-«j & 3>). 7) V naší notaci je možno zapsat základní pravidla Stoiků (nazývaná „nedokazovaná"), z nichž první odpovídá modus ponens (1) [(7 - Q) k 7} -» Q, (2) [{? -, Q) & -.Q] -* -.?, (3) (-.(O5 k Q) k 7] -* -iQ, (4) [(7®Q)k7]-^^Q, (5) [(JfflQ)j£-,f]^Q. Ukažte jejich korektnost za předpokladu, že © je symbol pro vylučující disjunkci. Uvažujte (4') a (5') vzniklé z (4) a (5) nahrazením vylučující disjunkce běžnou disjunkcí. Zvažte, zda takto vzniklá pravidla jsou korektní. Návod: pro jedno z pravidel nalezněte ohodnocení, při kterém neplatí. Uvažte následující dedukční pravidla: (a) (7 k Q) -* ft, -ft k Q h -.?, (b) (:p&Q)->:R,s-*:Pr-(s&Q)->3t. Ukažte jejich korektnost a rozmyslete si jejich intuitivní význam. Stoikové uváděli čtyři dedukční pravidla. Pravidla (a) a (h) odpovídají prvnímu a třetímu pravidlu Stoiků, přičemž musíme připustit i symetrická pravidla (? k Q) — 34, 7 & -3Í I----.Q a (T b. Q) -f S, S -> Q h (T ii S) -> X. Druhé a čtvrté pravidlo je ztraceno. Stoickemu vyjádření by přesněji odpovídalo formulovat (l)-(5) jako pravidla a (a), (b) jako „metapravidla". U Stoiků se však nalezne i pravidlo odpovídající větě o dedukci (což by umožnilo jejich metapravidla chápat 52 CVIČENÍ 1 jako pravidla). Stoikové používali číslovky místo výrokových proměnných, tedy např. „Jestliže prvé, pak druhé. Avšak prvé. Tedy druhé." 8) Kromě pravidla modus ponendo ponens (obvykle prostě modus ponens) („tvrdící tvrzením")T,T-t Qh Q byla pokládána za podstatná také pravidla modus tollendo toilers (často prostě modus tollens; „popírající popíráním") ->Q, 7 —> Q----i? (viz rovněž bod (2) předchozího cvičení), modus tollendo ponens -■?, 5VQ h Q a modus ponendo tollens 7, ->(7 kQ)\—iQ (viz také bod (3) předchozího cvičení). Odvozovací princip odpovídající větě o rozboru případů býval nazýván konstruktivní dilema a za důležité bylo pokládáno i destruktivní dilema -iQ V -ft,7 -* (Q k ft) h ->?. Prokažte korektnost těchto pravidel, příp. dokažte odpovídající formule (tj. formule vzniklé užitím věty o dedukci) ve výrokovém počtu. 9) Ukažte, že formule vzniklá jen (jakkoli iterovaným) použitím konjunkcí a disjunkcí (bez negace!) není nikdy tautologií ani kontradikcí. Není tedy možné použít pro výstavbu formulí pouze tuto dvojici operací. Dále ukažte, že pomoci negace a ekvivalence nevyjádříme implikaci (návod: počet ohodnocení, při kterých je implikace pravdivá, je lichý). Naproti tomu vyjádřete implikaci pomocí negace a konjunkce a také pomocí negace a disjunkce, z čehož vyvoďte, že pro výstavbu formulí můžeme používat tyto dvojice místo dvojice negace a implikace. 10) Ukažte, že pro každou funkci F zobrazující {0, l}n do {0,1} (tak zvanou booleovskou funkci) existuje formule A výrokového počtu, ve které se vyskytují pouze výrokové proměnné pj,...,p„ a taková, že pro každé ohodnocení v těchto proměnných platí A[v] = F(v(pi),. -. ,v(pn)). Návod: Uvažte demonstraci věty o normálním tvaru. 11) Nechť formule A\& (Shefferova operace, méně často nazývaná exkluzí) je vyjádřitelná formulí ->{A k B) (tj. obratem „neplatí současně .. .a .. .")1). Ukažte, že pro libovolné ohodnocení v výrokových proměnných p, q je (-p) [v] = (p|p)[v] a (p k q)[v] = ((p|7)|(p|i7))Iv]; vyjádřete imptikaci pomocí Sheíferovy operace. Při budování formulí je tedy možno používat pouze samotnou Shefferovu operaci. Zjistěte zda existují i jiné (a které) binární operace na formulích, jež mají stejnou vlastnost. Návod: Všech možných (booleovských) funkcí zobrazujících {0, l}2 do {0,1} je sice 16, ale okamžitě můžeme vyřadit ty operace F, pro které F(l, 1) = 1, protože pak nikdy nemůžeme pomocí F vyjádřit formuli -p, a analogicky vyřadíme ty operace F, pro které F(0,0) = 0. Zbudou jen čtyři možnosti, ale z nich dvě operace jsou ve skutečnosti unární; operace, která je vyjádřitelná formulí ->A k ->S se nazývá Peírceova (také Nicodova). Srovnejte obrat běžného jazyka „ani ... ani ..." s Peirceovou operaci. 12} Vyjádřete formule p k (q = ->p), (p —► q) k (q -* p) k (->p k q) a [p —* (q k r)] V q v normálním tvaru. Ukažte větu o normální formě bez použití věty o úplnosti. Návod: Podle složitosti formule výrokového počtu ukazujte existenci obou tvarú současně; při kroku pro negaci využijete existenci druhého tvaru a de Morganových pravidel, pří kroku pro implikaci využijete h (A —* ®) = {^A Ví), předpokládanou existenci obou tvarů a opět de Morganova pravidla. 1^ Existují i (nepřevažujíci) texty připisující StDikům chápání disjunkce ve významu uvedené formule. 53 KAPITOLA I VÝROKOVÝ POČET 13) Polská (bezzávorková, též prefixní) notace. Definujeme formule tak, že: (a) každá výroková proměnná je formulí, (b) je-li A formulí, je -~A formulí a je-li i B formulí, jsou formulemi i -*AB, V AG, & AB, -AB, (c) všechny formule dostaneme postupnou aplikací pravidel (a) a (b). Ukažte vzájemně jednoznačnou korespondenci formulí podle této definice a dle definice dříve zavedené a uvědomte si, že v polské notaci jsou k formuli A jednoznačně určeny jak formule, tak i operace, jimiž formule A vznikne, a to vše bez použití závorek (za cenu snížení přehlednosti textu). Název prefixní vyjadřuje, že logická spojka předchází formule, na které je operace aplikována. 14) Ukažte, že systém formulí T výrokového počtu je sporný, právě když existuje formule A výrokového počtu tak, že 7 I- (A & -\A), a to je, právě když existuje formule B tak, že 3"h 3 a současně T—iS. Prokažte. že formule výrokového počtu je splnitelná, právě když není kontradikcí. 15) Formule A, B výrokového počtu se nazývají (výrokově) ekvivalentní, jestliže A j= B a současně B |= A. Ukažte, že A |= B, právě když r- -A -> B, a že j4 a 3 jsou výrokově Ekvivalentní, právě když b A ~ li, tzn. právě když |= A = B. 16) Platí, že 7 h A a současně S h A, právě když T n S r- Al Platí, že 7 h A nebo S r- A, právě když Tu S h A? Prokažte nebo najděte protipříklady. Zaručuje v předchozích případech alespoň jedna podmínka druhou? 17) (Věta o dualite) Nechť ve formuli A výrokového počtu se vyskytují jenom spojky i,Íí,V« nechť formule B vznikne z A záměnou znaku le znakem V a znaku V znakem &: a záměnou výrokové proměnné její negací. Ukažte I----->A = 3. Návod: Prokazujte postupně podle složitosti formule při použití de Morganových pravidel. Formulujte rovněž pro formule obsahující další spojky. Návod: Užijte (p -* q) = (-,q _, -,p) a (p = q) = (^p = -.q). 18) Ukažte, že schéma VP3 lze nahradit schématem (-.Q -t -.?) -. [(-,£} -> 9) -> Q], Návod: Nejprve ukažte, že -.Q -t -.9, -,Q -t 9, ^Q je sporná, naproti tomu k prokázání ((-,0 - -,?) - [(^Q -» 5>) _ Q]) - [(^q _ -.j) _»(y _ Q)] v systému bez VP3 uvažte, že demonstrace věty o dedukci nevyužívá VP3, a prokažte, že z předpokladů 9, -.Q -» 9} -» Q] existuje důkaz formule Q využívající pouze VPI, VP2 a modus ponens (k čemuž využijte formuli 9 -* (-.Q -» 9) a tranzitivitu implikace). 19) Pravidlem řezu se nazývá dedukční pravidlo dovolující z formuh' -.JvQ a 9V9 odvodit formuli Q V 3c. Je často používáno (případně jeho obměny) v gentzenovských systémech. Ukažte korektnost tohoto pravidla. {Pro pravidlo řezu aplikované na literáty se užívá název pravidlo rezoluce.) Ukažte, že pravidlo řezu je vzájemně nahraditelné s pravidlem modus ponens za předpokladu, že ve zkoumaném gentzenovském systému smíme využívat záměny popsané formulí (23) §4 (tedy za předpokladu vhodné volby použitého gen-tzenovského systému). Návod: V systému popsaném v předchozím textu ukažte 54 CVIČENÍ i -.TvQ.fvKI- Q V 9.; naopak v gentzenovském systému (tzn. bez modus ponens!) ukažte, že 9 -» Q, 9 h Q využívajíce záměn popsaných formulí (23) a používajíce vyjádření formule 7 -* Q formulí -*9 V Q. 20) Uvažte dokazovací systém sestávající z jediného axiomu ^9 V 9 a z dedukč-ních pravidel: z 9 odvoď Q V ľ (prodloužení), z CPV 9 odvoď 9 (stažení či zjednodušení pro disjunkci), z TV(QvDt) odvoď (T V Q) V 9. (asociativita), zívQa -tfvtt odvoď Q V 9 (řez). Ukažte, že uvedený systém je korektní (nebo přímo prokažte uvedená dedukční pravidla v systému uvedeném v textu). Systém z tohoto cvičení je také úplný (viz napr. [Shl]), a tudíž stejně silný jako námi vyšetřovaný. 21) Uvažte dokazovací systém z dedukčních pravidel: (i) 9\-9, (2) jestliže T \- 2, pak 7- {9} h 9 -» Q (srovnej s větou o dedukci), (3) jestliže J h Q a S h -iQ, pak (TU S) - {-■?} r- 9 (srovnej s větou o důkazu sporem), (4) jestliže ThT^QaSI-T pak TU S h Q (srovnej s principem modus ponens). Dedukcí rozumíme posloupnost vztahů typu T r- 9, při jejíž konstrukci můžeme používat pravidla (l}-(4), případně aplikovaná na předchozí členy posloupnosti. Ukažte, že pro každý axiom výrokového počtu 9 existuje dedukce obsahující 0 h 9. Návod: (a) Pro VP1 zkoumejte (a doplňte) posloupnost 9 r- 9; 9 h Q — 9 (pravidlo (2), kde vynecháváme z jednoprvkového systému obsahujícího 9 formuli Q, přestože tam není), (b) pro VP2 použijte posloupnost 9 - (Q - 9.) h 9 - (Q - 9); 9 - Q H 9 -. Q; 9 h 9; y —. (Q —> K), ľ h Q -i 9.; 9 — Q, T r- Q; 9 — (9. -> 9.),9 -> Q, 9 h 31 a dále užijte trikrát pravidlo (2), (c) pro VP3 užijte tQ, ->Q -. -i? t- ->7; TI-Ti-Q-^J.Jr B (pravidlo (3)) a dvakrát použijte pravidlo (2). Ukažte naopak korektnost uvedených pravidel a dále pravidel (5) jestliže T I- P a S h Q, pak TU S h 9 k. Q, (6) jestliže T I- 9, pak 7 r- T v Q a také T h Q V í, (7) jestliže T h T i: Q, pak Ihfl také Thl i(QVQ), (8) jestliže TH ? V Q, jestliže !l"?^Sl jestliže Oi h Q — 9-, pak TU S U Ä h 3c. 22) Ukažte, že vztah h A = "B vytváří ekvivalenci na množině všech formulí výrokového počtu. Nechť S je „výběrová" množina příslušející této ekvivalenci (tj. pro každou formuli A existuje právě jedna formule 1? z množiny S tak, že r- A = S). Pro prvky S definujme A S S, právě když h B -r A Ukažte, že relace á je uspořádání, popište největší a nejmenší prvek. Zjistěte, zda se jedná o svaz či dokonce úplný svaz, pokuste se popsat suprema a infima — pokud existují. Jsou odpovědí v případě konečné množiny a nekonečné množiny výrokových proměnných tytéž? 23) Nezávislost jednotlivých syntaktických zákonů (VP1-VP3 a modus ponens) je možno ukazovat pomocí trojhoduotové sémantiky. Uvažme např. modifikovanou sémantiku výrokové logiky, ve které logické spojky nemají dvouhodnotové, ale následující troj hodnotové tabulky: -. 0 1 1/2 0 1 0 -t 0 1/2 1 0 1 1 1 1/2 0 1 1 1 0 1/2 1 Systém obsahující VPI, VP2 a modus ponens je korektní vůči uvedené sémantice v tom smyslu, že každý uvedený axiom má při každém pravdivostním ohodnocení hodnotu 1 a nadto nabývají-li formule í a 9 — Q při nějakém ohodnocení hodnoty 1, musí pro toto ohodnocení nabývat hodnotu 1 rovněž ferrmüe Q. Navíc totéž platí i pro formule (p -» q) -- [(p -» -q) -> -.p] a p -> (-p -* q). Naproti tomu pro 55 KAPITOLA I VÝROKOVÝ POČET VP3 existuje pravdivostní ohodnocení, které dává jinou hodnotu než 1. Totéž platí i o formulích -i-ip -> p a (->p —> ->q) — [(-.p — q) -+ p]. Prokažte. Uvažte následující ohodnocení implikace -> 0 1/2 I 0 1 1 1 1/2 0 1 1 1 0 1 1 Nezávislost kterého syntaktického zákona výrokového počtu na ostatních týkajících se pouze implikace prokazuje takováto sémantika? Zvolte ohodnocení negace, aby VP3 bylo korektní. Pokuste se využít zmíněnou metodu k prokázání dalších nezávislostí. 24) Přeformulujte sémantické podmínky Tarského (a)-(c) z konce §1 do syntaktické verze. Jsou tyto syntaktické podmínky prokazatelné? 25) Za cenu přímého důkazu několika formulí není potřeba při demonstraci věty o úplnosti užít větu o ekvivalenci. Prokažte větu o ekvivalenci na základě věty o úplnosti. Analogicky prokažte větu o nahrazení na základě věty o úplnosti. Formulujte důvod nepřijatelnost nahrazení jakékoli podformule jinou formulí ve větě o nahrazení využívajíce pojmů sémantiky. ■-.i) KAPITOLA II PREDIKÁTOVÝ POČET Vždyť na.s"e poznání je jen částečně, . . . ; až přijdu plnost, tehdy to, co ji čá&tečixé, bude překonáno.1) sv. Pavel, IKor. 13,9-10 V celém následujícím textu se již budeme zabývat predikátovým poetem. Úkolem této kapitoly je pojednat o základech této disciplíny. Místo o predikátovém počtu se někdy též hovoří o predikátové logice nebo o predikátovém kalkulu (v angličtině se často užívá také first order logic). Vztah mezi počty predikátovým a výrokovým byl poměrně široce diskutován v úvodu textu. Bylo tam i zmíněno, že je možno oba počty zkoumat najednou v rámci predikátového počtu. Poznamenejme, že v takovémto případě je namístě ztotožnit predikátový počet s klasickou matematickou logikou. Již výše jsme uvedli, že za zakladatele predikátového počtu je zcela všeobecně pokládán Aristoteles. Otázkám, jakou část predikátového počtu explicitně zkoumá a jaké výsledky předkládá, se budeme velice krátce věnovat na konci tohoto úvodu. Nicméně, již v tomto okamžiku uveďme z jeho Prvních analytik alespoň nejčastěji citované: „Sylogismus2^ je rozumový úkon, v němž, jsou-li dány určité předpoklady, vyplývá z jejich povahy nutně něco od těchto předpokladů odlišného." Tento citát snad nejlépe vystihuje Aristotelovo pojetí. Podstatné složky predikátového počtu představuje vyšetřování vlastností objektů a vztahů mezi nimi a dále vyšetřování vlastností kvantifikace. K objasnění těchto jevů nyní přistoupíme. * Pro danou oblast musíme nejprve rozhodnout, které vlastnosti a vztahy budeme pokládat za základní, a ty pak formaíizujeme predikáty. Takovýmito základními vlastnostmi a vztahy mohou být např. „být svobodný", „být manžely", „být dítětem toho a toho muže a té a té ženy", „ležet na té a té přímce" (v geometrii), „být prvkem té a té množiny", „rovnat se" (obé v teorii množin), etc. Uvědomme si, že u každé vlastnosti a vztahu víme (předpokládáme, že víme), o vztahu kolika objektů vypovídá (pokud vypovídá o jednotlivém objektu, mluvíme o vlastnosti, jinak mluvíme o vztahu) — první příklad je vlastností (tj. je unární), druhý, čtvrtý, pátý a šestý vypovídá o vztahu dvou objektů (binární) a třetí dokonce o vztahu tří objektů {ternární). Počet objektů vstupujících do zkoumaného vztahu nazýváme četností (někdy též árností) příslušného predikátu (místo o predikátu četnosti k mluvíme často zkráceně o A-árním predikátu). Opětovně si uvědomme nejednoznačnost běž- ' Motto je pochopitelně vybráno do protikladu s mottem pro výrokový počet, nicméně oprávněnost tohoto výběru vyplyne až z výsledků kap. IV. ' logický úsudek, podrobněji viz níže 57