O výrokové logice

Toto je čtvrtý díl seriálu o logice, který volně sleduje myšlenky D.Hofstadtera sepsané v jeho knize Gödel, Escher, Bach. Navigace: úvodní článek - předchozí díl - příští díl.

Několikrát jsem sliboval pravidla výrokové logiky jako formálního systému, a jest načase slibům dostát. Podobně jako u modelových formálních systémů v předchozích článcích, i teď je třeba definovat formální abecedu, říct, jaké řetězce jsou dobře formované, a nakonec udat axiomy a odvozovací pravidla. Výroková logika je „skutečný“ systém (narozdíl od předchozích dvou diskutovaných systémů, jejichž jediným účelem bylo ilustrovat ideu formálního systému), takže pravidel bude o něco více. Není to ale nic strašného — oproti systému MIU zde máme tu výhodu, že symboly mají svou interpretaci a odvozovací pravidla dávají smysl.

Nejdříve abeceda. Sada povolených znaků obsahuje (, ), ∧, ∨, ⇒, ¬. Krom těchto speciálních znaků povolíme i jakákoli písmena latinské abecedy, tedy A, B, C atd. Těchto písmen je pouze dvacet šest, může se ale stát, že bychom potřebovali větší počet. Proto, v případě potřeby, můžeme použít libovolné množství apostrofů ' jako diakritiku, a tvořit tak podřetězce fungující jako dodatečná písmena: B', Z'''' atd. Potřeba užívat apostrof v tomto článku nikde nenastane [*].

Není asi potřeba tajit interpretaci, kterou symboly budou mít; speciální symboly zastupují výrazy „není pravda, že“, „a“, „nebo“ a „jestliže ..., pak“, závorky slouží k jednoznačnému vymezení struktury a písmena (s případnými apostrofy) označují libovolné smysluplné výroky přirozeného jazyka. Znalost interpretace činí systém srozumitelnějším, zároveň ale způsobuje pokušení překračovat formální pravidla a provádět zbrklé nepovolené manipulace, které vypadají „logicky“, takže pozor. Příklady chybných úvah ještě budou následovat později.

Kromě abecedy potřebujeme i gramatiku, která je zde definována rekurzivně. Především, jakékoli písmeno následované libovolným množstvím apostrofů je dobře formovaný výraz. Příkladem jsou A, B''' nebo Z'. Rekurzivní pravidlo je toto: jsou-li x a y dobře formované výrazy, pak ¬x, (x∧y), (x∨y) a (x⇒y) jsou všechno dobře formované výrazy. Například ¬((P⇒Q)∧¬Q) je dobře formovaný výraz. Povšimněte si, že závorky jsou vždy spojeny s jedním ze znaků ∧, ∨ nebo ⇒ a nelze je bezostyšně přidávat nebo mazat. (P) není dobře formovaný výraz.

Odvozovacích pravidel je devět, a nejdřív napíšu a okomentuji prvních sedm.

1. Jestliže x a y jsou teorémy, pak (x∧y) je teorém.
   
2. Jestliže (x∧y) je teorém, pak x je teorém a y je teorém.
   
3. Dobře formovaný výraz vzniklý tak, že z teorému vyjmeme podřetězec ¬¬, nebo do teorému tento podřetězec vložíme, je teorém.
   
4. Jestliže x a (x⇒y) jsou teorémy, pak y je teorém.
   
5. Podřetězce tvaru (x⇒y) a (¬y⇒¬x) lze zaměňovat. (To znamená, že pokud například (P⇒¬Q) tvoří část nějakého teorému, pak nahradíme-li tuto část za (¬¬Q⇒¬P), získáme teorém.)
   
6. Podřetězce tvaru (¬x∧¬y) a ¬(x∨y) lze zaměňovat. (Ve stejném smyslu jako u předchozího pravidla.)
   
7. Podřetězce tvaru (x∨y) a (¬x⇒y) lze zaměňovat.
   

Tato pravidla mají svá standardní jména, například pravidlo VI je jeden z De Morganových zákonů a pravidlo IV se nazývá modus ponens. Podstatnější ale je, že dávají intuitivní smysl. Přidání a rozklad konjunkce v pravidlech I a II odpovídá způsobu, jak zacházíme se spojkou a. Přidání a odstranění dvojné negace je taktéž něco, v čem těžko najít nějakou obtíž. V aplikaci zbylých pravidel sice lidé občas chybují, nicméně normálně inteligentnímu člověku není obvykle zatěžko po upozornění si chybu uvědomit a opravit.

Krátký příklad bývá lepší než deset stran vysvětlování, takže následuje modelové odvození. Budu předstírat, že (P⇒Q) je axiom (ve skutečnosti to není axiom, ale z něčeho vycházet musíme).

1. (P⇒Q) (falešný axiom)
   
2. (¬¬P⇒Q) (z 1, pravidlo III)
   
3. (¬P∨Q) (z 2, pravidlo VII)
   
4. ((P⇒Q)∧(¬P∨Q)) (z 1 a 3, pravidlo I)
   
5. (¬¬(P⇒Q)∧¬¬(¬P∨Q)) (z 4, pravidlo III užito dvakrát)
   
6. ¬(¬(P⇒Q)∨¬(¬P∨Q)) (z 5, pravidlo VI)
   

A tak dále. Odvozený „teorém“ (nezapomeňte, že je stejně falešný, jako axiom, z kterého byl získán) není zrovna elegantní, ale takové už teorémy (falešné i pravé) povětšinou bývají. Všimněte si, jak jsem pečlivě doplňoval dvojité negace v krocích 2 a 5. Na první pohled by se zdálo, že jsem si to mohl ušetřit a například rovnou pravidlem VII převést (P⇒Q) na (¬P∨Q). Takové zdání je ale špatně: pravidlo VII je definováno tak, že manipulovaný řetězec obsahující ⇒ musí začínat na ¬, což není příklad (P⇒Q). Zkratkovité odvození by sice vedlo ke správnému výsledku, ale bylo by prohřeškem proti zásadám formality.

Pokud stále netrpělivě čekáte na axiomy, možná vám přišlo divné, proč jsem v úvodu modelového odvození nepoužil skutečný axiom. Důvod je ten, že výroková logika (alespoň v naší formulaci) žádné axiomy nemá. Aby stejně prázdná nebyla i množina teorémů, musí existovat pravidlo generující teorémy z ničeho. Tuto roli hrají poslední dvě pravidla, která jsem si nechal nakonec. Osmé pravidlo je

• Jestliže z předpokladu x lze odvodit y, pak (x⇒y) je teorém.
  

To zní jednoduše, ale lépe na příkladu ilustrovat, jak pravidlo funguje.

1.    ¬¬P (premisa pravidla VIII)
   
2.    P (z 1, pravidlo III)
   
3. (¬¬P⇒P) (z 1 a 2, pravidlo VIII)
   
4. (¬P∨P) (z 3, pravidlo VII)
   

Což je odvození jednoho z nejjednodušších teorémů výrokové logiky: (¬P∨P). (Mimochodem, častěji se setkáme s tvarem (P∨¬P). Uměli byste z (¬P∨P) odvodit (P∨¬P)? Ne, nemáme pravidlo umožňující prohazovat pořadí argumentů disjunkce. Řešení viz [1].)

Explicitně se na pravidlo VIII (které se mimochodem oficiálně jmenuje Věta o dedukci) odvolávám v prvním a ve třetím řádku, ale ve skutečnosti k pravidlu patří i řádek 2, který se jakoby odehrává uvnitř něho. Ke grafickému zvýraznění této skutečnosti jsou řádky odsazeny doprava. Výrazy, které se objevují na odsazených řádcích, lze akceptovat jako teorémy uvnitř odsazeného úseku, nikoli však vně.

Uvnitř Věty o dedukci lze použít jakékoli odvozovací pravidlo, včetně Věty samotné. Můžeme tak dostat několik úrovní zanoření v sobě, a proces získává rekurzivní strukturu. Tvrzení o neakceptovatelnosti teorémů z odsazených řádků po Hofstadterově vzoru zformuluji jako nezávislé pravidlo (i když jej lze stejně dobře vnímat jako část pravidla VIII):

• V každé úrovni zanoření lze používat teorémy získané o jednu či více úrovní výše, nikoli však teorémy získané v úrovních nižších.
  

Příklad korektního odvození s více zanořenými úrovněmi:

1. (¬P∨P) (známý teorém)
   
2.    P (premisa, 1. úroveň zanoření)
   
3.       Q (premisa, 2. úroveň zanoření)
   
4.       (¬P∨P) (z 1, přenos z 0. úrovně zanoření dle pravidla IX)
   
5.    (Q⇒(¬P∨P)) (z 3 a 4, VIII)
   
6. (P⇒(Q⇒(¬P∨P))) (z 2-5, VIII)
   

Příklad chybného odvození:

1.    P (premisa, 1. úroveň zanoření)
   
2. (P⇒P) (z 1, VIII)
   
3.    Q (premisa, 1. úroveň zanoření)
   
4.       R (premisa, 2. úroveň zanoření)
   
5.       P (z 1, přenos podle IX)
   
6.    (R⇒P) (z 4 a 5, VIII)
   
7. (Q⇒(R⇒P)) (z 3-6, VIII)
   
8. (R∧(Q⇒(R⇒P))) (z 4 a 7, I)
   

Osmý řádek je zjevně chybný: užívá R jako teorém na nulté úrovni, ale čtvrtý řádek je zanořen o dvě úrovně níže. Chybný je i řádek 5. Sice se přenáší z vyšší úrovně do nižší, ale řádek 1 není přímo nadřazen řádku 5, nýbrž leží na paralelní větvi. Do pátého řádku lze přenést Q z řádku 3, nikoli ale P z řádku 1.

Než přejdeme k další diskusi, dovolím si upozornit, že popsaná formulace výrokové logiky není v žádném případě jediná možná. Zde uvedená verze je Gentzenova, kterou ve své knize užil Hofstadter, ačkoli jsem si dovolil změnit pár nepodstatných detailů, například grafickou podobu symbolů. Jiné verze výrokové logiky mohou používat trochu odlišnou sadu pravidel, nebo i jinou abecedu a gramatiku. Například je možné úplně vynechat znak ⇒ a výrok „jestliže x, pak y“ formalizovat rovnou jako (¬x∨y). Pravidlo VII se pak přesune do roviny interpretací a ze systému jej můžeme vypustit [*]. Jiné verze výrokové logiky mohou naopak obsahovat pravidel více. Tradičně zaváděným partnerem modu ponentu je modus tollens — pravidlo, které říká:

• Jestliže ¬y a (x⇒y) jsou teorémy, pak ¬x je teorém.
  

Všechny podobné modifikace musejí mít jednu věc společnou, aby se o nich dalo mluvit jako o různých formulacích výrokové logiky: musí produkovat stejnou sadu teorémů (nebo aspoň isomorfní sadu teorémů, liší-li se varianty svými abecedami). Pakliže se ale systémy s různými množstvími pravidel shodují v tom, jaké jsou schopny odvodit teorémy, nemá nutně ten „květnatější“ z nich nějaká pravidla „navíc“?

Ukazuje se, že ano. Takový modus tollens je již obsažen v úsporné verzi výrokové logiky obsahující pouze pravidla I - IX. Můžeme totiž provést odvození:

1. ¬y (předpoklad)
   
2. (x⇒y) (předpoklad)
   
3. (¬y⇒¬x) (z 2, pravidlo V)
   
4. ¬x (z 1 a 3, pravidlo IV)
   

Postup je to sice triviální, ale aby se stal regulérním odvozením v rámci výrokové logiky, je nutné nahradit symboly x a y nějakými konkrétními řetězci. Tak jako tak ale vidíme, že pravidlo X můžeme beztrestně použít jako zkratku za odození kombinující pravidla IV a V. Podobné zkratky můžeme nazývat odvozenými pravidly. Je ale dobré pamatovat, že odvozená pravidla nemají stejný status jako ta pravidla, která jsou v systému napevno zadaná. Jsou totiž vždy nutně odvozena mimo systém (připomínám, že v rámci systému nelze provádět operace s řetězci obsahujícími volné proměnné, jako je x v příkladu výše). Chceme-li mít formální odvození, musíme všechny zkratky rozepsat pomocí základních pravidel. Zavedeme-li odvozená pravidla do seznamu odvozovacích pravidel, přísně vzato získáme jiný formální systém.

Čtenář může snadno nabýt dojmu, že opatrnost, se kterou obcházím teorémy a manipulace s nimi, je přehnané hnidopišství. Dobře, modus tollens nebo prohození pořadí argumentů disjunkce nejsou zahrnuty v seznamu odvozovacích pravidel, ale jejich použitím stejně nikdy neodvodím nepravdivý teorém, tak o co jde? Jenže při formálním odvozování není nikdy opatrnost na škodu, přinejmenším ze začátku, než si člověk osahá chyby, kterých se lze neformální manipulací dopustit. Uvažme třeba ještě jednou náš první dokázaný teorém (P∨¬P). Tedy slovy „buď P, nebo ¬P“. To svádí k doměnce, že buď P, nebo ¬P je teorém výrokové logiky. Takový neformálně učiněný závěr je ovšem chybný: ani P, ani ¬P teorémy nejsou! Jak již bylo koneckonců řečeno, P lze interpretovat jako jakoukoli smysluplnou větu v přirozeném jazyce, například „George Bush je zednář“. Interpretace našeho teorému pak zní: „Buď George Bush je zednář, nebo George Bush není zednář.“ To je nepochybně pravdivý výrok — byť ne zrovna informativní. Stejně tak není pochyb o tom, že je pravdivá jedna z vět „George Bush je zednář“ a „George Bush není zednář“. Ale zatímco složená disjunkce je teorémem výrokové logiky, ani jedna z jejích částí teorémem není. Bohudík — bylo by podezřelé, kdyby příslušnost George Bushe k zednářům byl určena jako logická nutnost.

Jiná častá chyba je zaměňování odvozovacích pravidel s významy symbolů; zvlášt silně k tomu svádí ⇒. S použitím Věty o dedukci v kombinaci s jedním z dalších pravidel jsme schopni odvodit teorémy, které svou formou připomínají ono další pravidlo. Například k pravidlu II máme teorémy ((P∧Q)⇒P) a ((P∧Q)⇒Q), k pravidlu III (P⇒¬¬P), k pravidlu VII ((P∨Q)⇒(¬P⇒Q)) a tak dále. Je snadné přehlédnout ten rozdíl a myslet si, že druhé odvozovací pravidlo je ve skutečnosti axiom logiky říkající ((P∧Q)⇒P). Když stejnou chybu uděláme pro čtvrté pravidlo a identifikujeme modus ponens s teorémem ((P∧(P⇒Q))⇒Q), dostáváme se do pozice Želvy z Carrollova eseje...

Podívejme se na ještě jedno odvození, které má značný význam pro konsistenci systémů obsahujících logiku.

1.     P∧¬P (premisa)
   
2.     P (z 1, II)
   
3.     ¬P (z 1, II)
   
4.        ¬Q (premisa)
   
5.        P (z 2, IX)
   
6.     (¬Q⇒P) (z 4 a 5, VIII)
   
7.     (¬P⇒¬¬Q) (z 6, V)
   
8.     ¬¬Q (z 3 a 7, IV)
   
9.     Q (z 8, III)
   
10. ((P∧¬P)⇒Q) (z 1 až 9, VIII)
    

Výsledný teorém vyjadřuje takzvaný princip exploze, jenž říká, že ze sporu plyne cokoli, protože znak Q můžeme interpretovat jakkoli, nezávisle na P. (A pochopitelně, symboly P a Q v odvození ((P∧¬P)⇒Q) lze nahradit jakýmikoli jinými symboly nebo dokonce řetězci, a dovození zůstane platné.) Formální logika nás tak zásobuje přehršlí teorémů: „Jestliže je Bush zednář a zároveň Bush není zednář, pak Saturn obíhá kolem Země.“ „Jestliže je dnes středa a zároveň není středa, pak sedmnáct krát sedm je rovno nule.“ Zkrátka, přijímáme-li za teorém výrok a zároveň jeho negaci, můžeme z něj odvodit jakýkoli jiný výrok. Proto je případná nekonsistence formálního systému vnímána jako mnohem větší problém, než jeho neúplnost. V nekonsistentním systému jsou všechny dobře formované výrazy teorémy, a takový systém je pochopitelně k ničemu.

Výroková logika je stavěna tak, aby fungovala pro prakticky libovolnou interpretaci alfabetických symbolů P, Q aj. To má svou zápornou stránku: všechny teorémy formální logiky platí nezávisle na tom, co za tyto symboly dosadíme. Jsou to všechno tautologie, a málokdo si cení tautologií. Triviální pravdy typu „buď Bush je zednář, nebo Bush není zednář“ se nezdají dostatečně hodnotnou odměnou za námahu spojenou se strojovým vykonáváním odvozovacích instrukcí. Formální logika ale nemá za cíl být sama o sobě zdrojem hlubokých pravd o světě. Její ambicí je produkovat pravdivé výroky a pouze pravdivé výroky. Pokud tuto roli zvládá, může se stát základem složitějších systémů, z kterých lezou o poznání zajímavější teorémy.

Poznámky:
1. Hledané odvození může vypadat například takto:

1. (¬P∨P) (známý teorém)
   
2. (¬¬P⇒P) (z 1, pravidlo VII)
   
3. (¬P⇒¬¬¬P) (z 2, V)
   
4. (P∨¬¬¬P) (z 3, VII)
   
5. (P∨¬P) (z 4, III)
   

Samozřejmě může (P∨¬P) odvodit i přímo pomocí Věty o dedukci, podobně jako jsme odvodili (¬P∧P).