Sbírka příkladů k předmětu MA007 – Matematická logika Petr Novotný Ľuboš Korenčiak Fakulta informatiky Masarykovy univerzity Û¡¢£¤¥¦§¨ª«¬­Æ°±²³´µ·¸¹º»¼½¾¿Ý Autoři děkují Fondu rozvoje vysokých škol za podporu vzniku této sbírky v rámci projektu „Rozšíření studijních materiálů k předmětu matematická logika,“ projekt č. FRVS/511/2013. Úvod Základním cílem vědního oboru matematické logiky je konstrukce a studium tzv. formálních systémů. Zjednodušeně řečeno, formální systém je nějaký matematický model abstraktního myšlení. Takový model se obvykle skládá ze sady symbolů a souboru pravidel pro manipulaci s těmito symboly. Důležité je, že uvedené symboly nenesou a priori žádný význam (ten jim „zvenčí“ musí dodat někdo, kdo tyto symboly interpretuje) a manipulace s nimi je čistě mechanická. Jedná se tedy o model takového druhu myšlení, které je v principu simulovatelné našimi běžnými počítači. Zda takový model poskytuje veškeré lidské myšlení, to je hluboká filosofická otázka, kterou se v tomto předmětu zabývat nebudeme. I přesto je užitečné se matematickou logikou zabývat, minimálně ze dvou níže uvedených důvodů. Z matematického hlediska je užitečné mít jasno v tom, kdy je nějaký výsledek skutečně nevyvratitelně dokázán, a za jakých předpokladů. V matematice se prakticky nikdy nepoužívají stoprocentně formální důkazy, neboť takové důkazy by byly pro člověka nečitelné. Vždy se nechává prostor pro čtenáře, aby si doplnil některé myšlenkové kroky, a důkaz se pokládá za dostatečný, pokud svého čtenáře přesvědčí. Takovýmto důkazům v našem předmětu říkáme metadůkazy, neboť využívají něco co leží mimo zkoumaný formální systém, například čtenářovy znalosti či intuici. Matematici si dlouho vystačili pouze s těmito metadůkazy. Časem ovšem zjistili, že matematika založená na intuitivním chápání základních pojmů v sobě obsahuje neřešitelné spory, viz například známý Russelův paradox. Začala tedy snaha o striktní formalizaci matematiky, která by ji zbavila veškerého nánosu intuice. Existovalo dokonce přesvědčení, že veškerou matematiku lze redukovat na několik základních axiomů a mechanickou manipulaci s nimi. Paradoxně to byl právě logik Kurt Gödel, který svými větami o neúplnosti ukázal, že něco takového v principu není možné. Na druhou stranu se ukazuje, že i když není možné zmechanizovat veškerou matematiku, je možné zmechanizovat v podstatě veškerou matematiku kterou kdy lidé používali. Existuje několik projektů, jejichž cílem je s pomocí počítačů najít mecha- i ÚVOD ii nické důkazy co největšího množství známých matematických tvrzení (viz např. projekty Mizar a Metamath). Vzhledem k tomu, že některé slavné důkazy mají desítky, ba i stovky stran, a jsou tedy těžko zkontrolovatelné i těmi nejlepšími matematiky, jde zajisté o chválihodný počin. Mimo to, studium formálních důkazů umožnilo matematikům uvědomit si, jaké předpoklady (axiomy) potřebují k provedení daného důkazu. Některá základní tvrzení z různých oborů (např. topologie či matematické analýzy) se opírají o tzv. axiom výběru, který i dnes (byť jen ve velmi malé míře) vyvolává jistou kontroverzi – jak vzhledem ke své nekonstruktivní podstatě, tak vzhledem k některým neintuitivním výsledkům, které umožňuje dokázat. Snad ještě důležitější je informatický pohled na matematickou logiku. Jak již bylo řečeno, matematická logika modeluje ty oblasti přemýšlení, které jsou simulovatelné počítačem. Poskytuje nám tedy přirozený jazyk, pomocí kterého lze počítači předkládat různé úlohy k řešení. Například v oblasti verifikace programů obvykle chceme formálně dokázat, že nějaký systém má nějakou vlastnost, obvykle popsatelnou vhodnou logickou formulí. To ovšem často může být nadlidský úkol, neboť zmíněné systémy bývají vysoce komplexní (a i kdyby byl důkaz proveditelný člověkem, u systémů jako jsou řídící jednotky letadel či operační systémy v jaderných elektrárnách nemusí být žádoucí spolehnout se pouze na úsudek člověka). V takové situaci je ideálním řešením předat počítači vhodnou formální specifikaci systému a požadované vlastnosti a nechat jej mechanicky najít důkaz správnosti/bezpečnosti atd. daného systému. Abychom mohli počítače naprogramovat k řešení těchto problémů, či vůbec používat výsledné programy (tj. umět specifikovat vlastnosti systémů pomocí formulí různých logik), je třeba mít alespoň základní přehled o tom, jak logické systémy fungují. Pevně doufáme, že tato sbírka úloh, opatřená doplňujícími vysvětlujícími komentáři, napomůže čtenáři k získání tohoto přehledu. Obsah Úvod i 1 Syntax výrokové logiky 2 1.1 „Standardní“ výroková logika . . . . . . . . . . . . . . . . . . 2 1.2 Obecné systémy výrokové logiky . . . . . . . . . . . . . . . . 9 2 Sémantika výrokové logiky 12 3 Nestandardní logické systémy 26 4 Dokazovací systém pro výrokovou logiku 37 5 Syntax predikátové logiky 46 6 Sémantika predikátové logiky I 53 7 Sémantika predikátové logiky II 62 8 Teorie predikátové logiky 71 9 Dokazovací systém predikátové logiky 79 10 Věta o kompaktnosti 101 11 Kanonická struktura 109 A Vybrané zajímavosti 117 A.1 Löwenheimova-Skolemova věta a nestandardní modely aritmetiky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 A.2 Nestandardní analýza . . . . . . . . . . . . . . . . . . . . . . 126 1 Kapitola 1 Syntax výrokové logiky 1.1 „Standardní“ výroková logika V této sekci se setkáme s prvním formálním systémem: výrokovou logikou s operátory ¬, ∨, ∧, →. Existují však i systémy vyrokové logiky s jinými množinami operátorů. Budeme se jimi pro jednoduchost zabývat více až v kapitole 3. Neformálně řečeno, syntax formálního systému nám říká, o jaké symboly se v daném systému zajímáme a jak s nimi můžeme manipulovat. O manipulaci se symboly se více dozvíme v kapitole o odvozovacích systémech, zde se zaměříme pouze a jen na symboly samotné. Připomeňme si definice z přednášky. Definice 1.1 Abeceda výrokové logiky je soubor následujících symbolů: • Spočetně mnoho znaků pro výrokové proměnné (např. A, B, C, . . . nebo X1, X2, X3, . . . ). • Symboly pro logické spojky: ’¬’, ’∨’, ’∧’ a ’→’. • Symboly pro závorky: ’(’ a ’)’. Připomínáme, že z pohledu syntaxe nenesou tyto symboly žádný hlubší význam. Například se nikde neříká, že symbol ∧, který se ve formulích výrokové logiky typicky vyskytuje, se má interpretovat jako, standardní logická spojka „AND“. Přiřazovat význam těmto symbolům budeme až v další kapitole. Ve skutečnosti nebudeme přiřazovat význam pouze symbolům samotným ale též řetězcům (slovům) z nich vytvořeným. Zároveň nás však budou zajímat pouze ty řetězce, které mají určitý speciální tvar, tzv. formule výrokové logiky. 2 KAPITOLA 1. SYNTAX VÝROKOVÉ LOGIKY 3 Definice 1.2 Formule výrokové logiky je slovo ϕ nad abecedou výrokové logiky, pro které existuje tzv. vytvořující posloupnost, tj. konečná posloupnost slov ψ1, . . . , ψk (kde k ≥ 1) taková, že ψk = ϕ a pro každé 1 ≤ i ≤ k má slovo ψi jeden z následujících tvarů: • ψi je výroková proměnná, nebo • ψi je tvaru ¬ψj, pro nějaké j < i, nebo • ψi je tvaru (ψj ◦ ψj ) pro nějaké j, j < i, kde ◦ ∈ {∨, ∧, →}. Výše uvedená definice říká, že formule výrokové logiky jsou přesně ta slova, která lze v konečném počtu kroků vytvořit z jistých základních stavebních prvků (proměnných) pomocí různých syntaktických konstrukcí (spojek). Vzpomeňme si, že podobný postup se používá například pro definici syntaxe regulárních výrazů. Z definice je ihned vidět, že je-li ψ1, . . . , ψk vytvořující posloupnost pro nějakou formuli ϕ, pak pro libovolné 1 ≤ i < k je ψ1, . . . , ψi vytvořující posloupnost pro ψi. Zejména všechna slova vyskytující se ve vytvořující posloupnosti jsou samy o sobě formulemi. V této cvičebnici budeme standardně značit výrokové proměnné velkými znakamy latinské abecedy a formule výrokové logiky malými znaky řecké abecedy. Příklad 1.1 Určete, které z následujících slov jsou formulemi výrokové lo- giky. a) (X ∧ Y ) b) ¬((X ∧ Y ) → (Y ∨ Z)) c) (X1 ∧ ∨X2) d) k i=1 Xi – jedná se o symbolický zápis konjunkce k proměnných, pro jenoznačnost uzávorkovaných zprava, tj. o slovo tvaru (X1 ∧ (X2 ∧ (· · · ∧ (Xk−1 ∧ Xk)) . . . )) e) ∞ i=1 Xi f) ((X → Y ∧ Z)) KAPITOLA 1. SYNTAX VÝROKOVÉ LOGIKY 4 Řešení Probereme pouze některé případy. Slovo z příkladu b) je formule, neboť pro něj máme například následující vytvořující posloupnost: ψ1 = X, ψ2 = Y , ψ3 = Z, ψ4 = (ψ2 ∨ ψ3), ψ5 = (ψ1 ∧ ψ2), ψ6 = (ψ5 → ψ4), ψ7 = ¬ψ6. Slovo z příkladu e) není formule, neboť formule je vždy konečná posloupnost znaků. Slovo z příkladu f) rovněž není formule. Na první pohled je toto tvrzení zřejmé, ale jak jej formálně dokázat? Musíme ukázat, že žádná z nekonečně (dokonce nespočetně) mnoha všech možných vytvořujích posloupností nemůže být vytvořující posloupností pro slovo ((X → Y ∧ Z)). Způsob, jakým lze tento důkaz provést, je uveden níže. Jedním z možných způsobů jak ukázat, že dané slovo s není formulí výrokové logiky, je následující: ukážeme, že každá formule výrokové logiky má určitou vlastnost P, kterou zadané slovo P nemá. To, že nějakou vlastnost mají všechny formule výrokové logiky, lze nejlépe dokázat tzv. indukcí vzhledem ke struktuře formule. Tento princip je možné vyjádřit následovně: Věta 1.3 [O strukturální indukci.] Nechť P je nějaká vlastnost taková, že: a) Každá formule tvaru X, kde X je libovolná proměnná, má vlastnost P. b) Mají-li formule ψ1 a ψ2 vlastnost P, pak i formule ¬ψ1, (ψ1 ∧ ψ2), (ψ1 ∨ ψ2) a (ψ1 → ψ2) mají vlastnost P. Pak libovolná formule výrokové logiky má vlastnost P. Použití strukturální indukce ilustrujeme na příkladu 1.1 f). Chceme ukázat, že slovo ((X → Y → Z)) není formulí výrokové logiky. Ukážeme tedy, že každá formule ϕ výrokové logiky má následující vlastnost P: P: každý výskyt výrokové proměnné ve slově ϕ sousedí s nejvýše jedním výskytem binárního operátoru v tomto slově. Je ihned vidět, že slovo ((X → Y → Z)) tuto vlastnost nemá (jediný výskyt Y v tomto slově sousedí se dvěma výskyty operátoru →) a pokud zmíněné tvrzení vskutku platí, nemůže být toto slovo formulí. Metadůkaz tvrzení povedeme strukturální indukcí. Ve skutečnosti metadokážeme silnější tvrzení, a sice že každá formule ϕ má následující vlastnost: P’: každý výskyt proměnné ve slově ϕ sousedí s nejvýše jedním výskytem binárního operátoru a zároveň, pokud se nějaká proměnná vyskytuje na konci či na začátku slova ϕ, pak tento výskyt proměnné nesousedí s žádným výskytem binárního operátoru. KAPITOLA 1. SYNTAX VÝROKOVÉ LOGIKY 5 a) Báze: Ve formuli tvaru X, kde X je výroková proměnná, se žádné binární operátory nevyskytují. Taková formule tedy triviálně má vlastnost P . b) Indukční krok: Nechť ψ1, ψ2 jsou libovolné formule mající vlastnost P . Formule ¬ψ1 má rovněž tuto vlastnost, neboť připojení unárního operátoru ¬ na začátek slova tuto vlastnost zřejmě nijak neovlivní. Nechť nyní ◦ ∈ {∨, ∧, →} je libovolný binární operátor. Sporem předpokládejme, že slovo (ψ1 ◦ ψ2) nemá vlastnost P . Protože toto slovo začíná a končí závorkami (a nikoliv proměnnými), musí platit, že je v něm výskyt nějaké proměnné X sousedící se dvěma výskyty binárního operátoru. Pro určitost předpokládejme, že tento výskyt je v podslově ψ1 (v opačném případě lze postupovat symetricky). Pak binární operátor vyskytující se vlevo od tohoto výskytu rovněž leží v podslově ψ1, což znamená, že operátor ležící vpravo od tohoto výskytu v podslově ψ1 neleží (to by byl spor s předpokladem, že slovo ψ1 má vlastnost P ).1 Ale pak slovo ψ1 končí výskytem proměnné, kterému předchází výskyt binárního operátoru – to je opět spor s předpokladem, že slovo ψ1 má vlastnost P . Tím je metadůkaz hotov. Všimněte si, že v metadůkazu jsme použili standardní trik používaný v metadůkazech založených na indukci, kterým je zesílení dokazovaného tvrzení. Pokud bychom chtěli strukturální indukcí přímo dokazovat, že všechny formule mají původní vlastnost P, metadůkaz by se patrně ve druhém bodu „zasekl“. Neuměli bychom totiž vyloučit možnost, že slova ψ1 a ψ2 sice mají vlastnost P, ale formule ψ1 končí výskytem proměnné jemuž předchází výskyt binárního operátoru. Příklad 1.2 Dokažte, že mezi libovolnými dvěma binárnímy operátory ve formuli výrokové logiky je alespoň jeden výskyt (levé či pravé) závorky. Příklad 1.3 Dokažte, že slovo z příkladu 1.1 c) není formulí výrokové lo- giky. Délkou formule ϕ (značíme |ϕ|) se rozumí počet znaků abecedy výrokové logiky, ze kterých se formule skládá. Příklad 1.4 Dokažte, že každá formule ϕ výrokové logiky, ve které se nevyskytuje operátor negace, má následující vlastnosti: 1 Toto tedy znamená, že onen vpravo se vyskytující binární operátor je oním „◦“ oddělujícím podslova ψ1 a ψ2. V důkazu ovšem tento fakt nepotřebujeme. KAPITOLA 1. SYNTAX VÝROKOVÉ LOGIKY 6 a) |ϕ| je liché číslo. b) Počet výskytů proměnných ve formuli ϕ je alespoň |ϕ| 4 . Řešení Metadokážeme obě dvě tvrzení zároveň. Přesněji řečeno, ukážeme, že libovolná formule ϕ splňuje následující metaimplikaci: Pokud se ve formuli nevyskytuje operátor negace, pak její délka je 4m−3, kde m je počet výskytů proměnných v této formuli. (*) Z toho vyplývají obě požadovaná tvrzení, neboť 4m − 3 je vždy liché číslo a m ≥ 4m−3 4 = m − 3 4. Postupujeme strukturální indukcí: Báze. Pokud ϕ = X, kde X je proměnná, pak máme m = 1 a |ϕ| = 1 = 4m − 3. Tvrzení tedy platí. Indukční krok. Předpokládejme, že tvrzení platí pro nějaké formule ϕ1 a ϕ2. Formule tvaru ¬ϕ1 evidentně obsahuje výskyt operátoru negace a triviálně tedy splňuje metaimplikaci (*). Nyní uvažme libovolnou formuli ϕ tvaru (ϕ1 ◦ ϕ2), kde ◦ ∈ {∨, ∧, →}. Pro i ∈ {1, 2} označme mi počet výskytů proměnných ve formuli ϕi. Zřejmě m =m1 + m2 (nepřidali jsme žádné nové výskyty proměnných). Dále dle indukčního předpokladu máme |ϕi| = 4mi − 3, pro obě i ∈ {1, 2}. Konečně |ϕ| = |ϕ1| + |ϕ2| + 3 (k ϕ1 a ϕ2 jsme přidali dvě závorky a operátor ◦). Dohromady dostáváme |ϕ| = |ϕ1| + |ϕ2| + 3 = 4m1 − 3 + 4m2 − 3 + 3 = 4 · (m1 + m2) − 3 = 4m − 3. Tvrzení tedy platí. Vskutku tedy platí, že pro libovolnou formuli ϕ máme |ϕ| = 4m − 3, kde m je počet výskytů proměnných v této formuli. Příklad 1.5 Dokažte, že počet výskytů závorek (levých i pravých dohromady) v libovolné formuli ϕ výrokové logiky je roven dvojnásobku počtu výskytů binárních operátorů ve ϕ. Příklad 1.6 Pro libovolnou formuli výrokové logiky ϕ označme B(ϕ) a N(ϕ) počet výskytů binárních operátorů, resp. operátorů ¬, ve formuli ϕ. Najděte vztah mezi těmito hodnotami a délkou formule ϕ (tj. nalezněte vhodnou funkci f dvou celočíselných proměnných takovou, že pro libovolnou formuli ϕ platí f(B(ϕ), N(ϕ)) = |ϕ|). Příslušný vztah pak dokažte pomocí strukturální indukce. Příklad 1.7 Rozhodněte, zda platí následující tvrzení. Své rozhodnutí zdů- vodněte. KAPITOLA 1. SYNTAX VÝROKOVÉ LOGIKY 7 a) Ke každé formuli výrokové logiky existuje jednoznačně určená vytvořující posloupnost. b) Ke každé formuli výrokové logiky existuje konečně mnoho vytvořujících posloupností. c) Pokud budeme požadovat, aby se ve vytvořující posloupnosti neopakovaly formule, pak je vytvořující posloupnost každé formule určena jednoznačně až na pořadí formulí v posloupnosti. Z definice vytvořující posloupnosti víme, že každou formuli ϕ lze psát v jednom z následujících tvarů: X, kde X je proměnná, nebo ¬ψ či (ψ1 ◦ ψ2), kde ψ, ψ1, ψ2 jsou formule a ◦ je binární operátor. Jsou však formule ψ, ψ1, ψ2, na které můžeme rozložit formuli ϕ, určeny jednoznačně? Pokud má formule ϕ tvar ¬ψ, pak je jasně vidět, že formule ψ je určena jednoznačně. V případě formule tvaru (ψ1 ◦ ψ2) ale není okamžitě jasné, proč by takovou formuli nebylo možné psát ve tvaru (θ1 ◦θ2), kde θ1, θ2 jsou formule různé od ψ1, resp. ψ2. Následující příklady nám pomohou ukázat, že tato nejednoznačnost vskutku nastat nemůže. Příklad 1.8 Dokažte, že každá formule ϕ výrokové logiky je dobře uzávorkována, tj. že se v ní vyskytuje stejný počet pravých a levých závorek a zároveň se v každém prefixu ψ slova ψ vyskytuje nejvýš tolik pravých závorek, co levých. Dále dokažte, že každý výskyt binárního operátoru v libovolné formuli je uzavřen alespoň v jedné dvojici závorek. Definice 1.4 Řekneme, že nějaký binární operátor ◦ má ve formuli ϕ vnější výskyt, pokud platí ϕ = (ψ1 ◦ ψ2), kde ψ1, ψ2 jsou formule, ve kterých je každý výskyt binárního operátoru uzavřen v alespoň jedné dvojici závorek. Oním vnějším výskytem operátoru ◦ je právě výskyt oddělující podslova ψ1 a ψ2. Alternativně se dá říci, že výskyt binárního operátoru ve formuli ϕ je vnější, pokud je uzavřen pouze v jediné dvojici závorek. Příklad 1.9 Dokažte, že v každé formuli se vyskytuje nejvýše jeden vnější výskyt binárního operátoru. Jako důsledek pak ukažte následující: pokud máme ϕ = (ψ1 ◦ ψ2) = (θ1 ◦ θ2), kde ◦ je binární operátor a ψ1, ψ2, θ1, θ2 jsou formule, pak ψ1 = θ1 a ψ2 = θ2. Během provádění důkazu si pečlivě uvědomte, která z výše uvedených tvrzení v důkazu používáte. Každou formuli lze tedy jednoznačně rozložit na jisté kratší formule, tzv. podformule. KAPITOLA 1. SYNTAX VÝROKOVÉ LOGIKY 8 Definice 1.5 Pro formuli ϕ výrokové logiky definujme množinu jejích podformulí Sub(ϕ) takto: • pokud ϕ = X, pak Sub(ϕ) = {X}, • pokud ϕ = ¬ψ, kde ψ je formule, pak Sub(ϕ) = {ϕ} ∪ Sub(ψ), • pokud ϕ = (ψ1 ◦ ψ2), kde ψ1, ψ2 jsou formule, pak Sub(ϕ) = {ϕ} ∪ Sub(ψ1) ∪ Sub(ψ2). Všimněte si, že každá formule je svou podformulí. Příklad 1.10 K následujícím formulím najděte množinu všech jejích pod- formulí: a) ϕ = (((¬X1 → X2) → ¬(X3 ∧ ¬¬X4)) → (¬X1 → X2)) b) ψ = (Xk → (Xk−1 → (Xk−2 . . . (X2 → X1) . . . ))) Řešení Sub(ϕ) = {ϕ, ((¬X1 → X2) → ¬(X3 ∧ ¬¬X4)), (¬X1 → X2), ¬X1, X1, X2, ¬(X3 ∧ ¬¬X4), (X3 ∧ ¬¬X4), X3, ¬¬X4, ¬X4, X4}. Sub(ψ) = {Xi | 1 ≤ i ≤ k} ∪ {ψi | 1 ≤ i ≤ k}, kde ψ1 = X1 a pro i > 1 je ψi = (Xi → ψi−1). Nyní navážeme na příklad 1.7. Příklad 1.11 Ukažte, že ke každé formuli ϕ existuje právě jedna (až na pořadí formulí v posloupnosti) vytvořující posloupnost ψ1, . . . , ψk, v níž se vyskytují pouze formule ze Sub(ϕ), z toho každá právě jednou. Příklad 1.12 Nechť B(ϕ) a N(ϕ) jsou stejná čísla jako v příkladu 1.6. Dokažte, že každá formule ϕ má vytvořující posloupnost délky nejvýše N(ϕ) + 2B(ϕ) + 1. Dále dejte příklad formule ψ mající vytvořující posloupnost délky ostře menší než N(ψ) + 2B(ψ) + 1. KAPITOLA 1. SYNTAX VÝROKOVÉ LOGIKY 9 Poznámka 1.6 V okamžiku, kdy se v dalších kapitolách nebudeme zaměřovat na syntaxi výrokové logiky jako takovou, často budeme implicitně využívat různých syntaktických konvencí. Například budeme často vynechávat vnější závorky, tzn. psát např. X → Y namísto správného (X → Y ). Také budeme užívat různých syntaktických zkratek, například budemeli pracovat s výše zmíněnou „standardní“ výrokovou logikou, pak budeme zápis X ↔ Y chápat jako syntaktickou zkratku pro formuli (X → Y ) ∧ (Y → X). Je důležité si uvědomit, že užíváním těchto konvencí neměníme výše uvedenou definici syntaxe standardní výrokové logiky, pouze používáme stručnější zápis pro správně utvořené formule. 1.2 Obecné systémy výrokové logiky Obecně lze zavést výrokovou logiku i s jinými operátory. Můžeme například uvážit „omezenou“ výrokovou logiku, v níž se vyskytují pouze operátory ¬ a → a například zápis X ∨ Y je pouze syntaktickou zkratkou pro formuli (¬X → Y ). Nebo můžeme naopak obohatit standardní výrokovou logiku z předchozí kapitoly o binární operátor ↔ – v takovém případě se (X ↔ Y ) stává formulí příslušného systému a nikoliv pouze syntaktickou zkratkou. Můžeme též používat zcela netradiční operátory, včetně operátorů arity vyšší než 2. Níže je zopakována formální definice z přednášky. Definice 1.7 Nechť F1, . . . , Fk je konečný soubor operátorů, přičemž každý operátor má přiřazenu svou aritu, což je nezáporné celé číslo. Definujeme formální logický systém L(F1, . . . , Fk), kde • abeceda je tvořena spočetně mnoha znaky pro proměnné, znaky pro závorky a symboly pro výše uvedené operátory F1, . . . , Fk; • formule ϕ systému L(F1, . . . , Fk) je slovo nad výše zmíněnou abecedou, pro nějž existuje tzv. vytvořující posloupnost, tj. konečná posloupnost slov ψ1, . . . , ψk (kde k ≥ 1) taková, že ψk = ϕ a pro každé 1 ≤ i ≤ k má slovo ψi jeden z následujících tvarů: – ψi je výroková proměnná, nebo – ψi je tvaru F (ψj1 , . . . , ψjn ), kde 1 ≤ ≤ k, n je arita F a jm < i pro všechna 1 ≤ m ≤ n. Pokud n = 1, píšeme F ψ1 namísto F (ψ1) (tj. vynecháváme vnější závorky u unárních operátorů), jeli n = 2, používáme infixový zápis (tj. píšeme (ψ1F ψ2) namísto F (ψ1, ψ2)). KAPITOLA 1. SYNTAX VÝROKOVÉ LOGIKY 10 V dalším textu budou příklady obsahovat přesné vymezení toho, jaký logický systém právě používáme. Pokud bude toto vymezení chybět, implicitně se má za to, že používáme standardní výrokovou logiku z předchozí podkapitoly. Uvědomme si, že všechny syntaktické pojmy (jako například podformule) lze jednoduše rozšířit i na tyto obecné systémy výrokové logiky. Konkrétně pojem podformule bychom definovali induktivně takto: Sub(X) = X, kde X je proměnná, a Sub(F(ϕ1, . . . , ϕn)) = {F(ϕ1, . . . , ϕn)}∪ n i=j Sub(ϕi). Stejně jako u standardní výrokové logiky lze ukázat, že tato definice je jednoznačná. Příklad 1.13 Uvažme formální logický systém L(¬, ), kde ¬ má aritu 1 a má aritu 3. Rozhodněte, které z následujících slov jsou formulemi tohoto systému. Pro ta, která identifikujete jako formule, najděte vytvořující posloupnost. a) (X Y ) b) (¬¬X, Y, ¬X) c) ¬ (X, (X, Y, ¬Z), Z) d) ¬(X Y Z) Příklad 1.14 Mějme stejný logický systém jako v předchozím příkladu. Pro libovolnou formuli ϕ tohoto systému označme T(ϕ) počet výskytů operátoru v této formuli. Dokažte, že každá formule ϕ má 2T(ϕ) + 1 výskytů proměnných. Příklad 1.15 Mějme stejný logický systém a nechť T(ϕ) je stejné číslo jako v předchozím příkladu. Nechť dále N(ϕ) je počet výskutů operátoru negace ve ϕ. Dokažte, že pro každou fromuli ϕ existuje vytvořující posloupnost délky nejvýše N(ϕ) + 3T(ϕ) + 1. Příklad 1.16 Dokažte, že pro libovolný logický systém L(F1, . . . , Fk) a libovolnou formuli ϕ tohoto systému platí, že posledním znakem ve ϕ je buď pravá závorka, nebo proměnná. Řešení Nechť L(F1, . . . , Fk) je libovolný, ale nadále pevně zvolený logický systém. Důkaz vedeme strukturální indukcí. • Báze ϕ = X kde X je proměnná. Zřejmě ϕ končí na X KAPITOLA 1. SYNTAX VÝROKOVÉ LOGIKY 11 • Indukční krok ϕ je tvaru Fj(ϕ1, . . . , ϕn), kde 1 ≤ j ≤ k, n je arita Fj a kde ϕ1, . . . , ϕn splňují požadovanou vlastnost. Pokud n = 1, pak dle definice (podle které vynecháváme závorky u unárních operátorů) končí ϕ stejným znakem, kterým končí ϕn. Dle indukčního předpokladu je tímto znakem proměnná nebo pravá závorka. Je-li n ≥ 2, pak formule ϕ nutně končí pravou závorkou. Definice 1.8 (Nahrazení podformulí) Uvažme libovolný logický systém L(F1, . . . , Fk) a libovolnou formuli ϕ tohoto systému. Nechť ϕ1, . . . , ϕm je nějaká vytvořující posloupnost pro ϕ (označme tuto posloupnost ∆) a nechť ξ1, θ1, . . . , ξ , θ jsou nějaké formule uvažovaného systému, kde ξi = ξj pro i = j. Uvažme posloupnost formulí ∆ která je definovaná takto: nejprve do ∆ postupně za sebe zařadíme vytvořující posloupnosti pro formule θ1, θ2, . . . , θ a za takto vzniklou posloupnost připojíme posloupnost formulí ϕ1, . . . , ϕm, kde pro libovolné 1 ≤ i ≤ m platí ϕi =    θj pokud ϕi = ξj pro nějaké j, ϕi pokud ϕi = ξj pro všechna j a ϕi je proměnná, Fj(ϕj1 , . . . , ϕjk ) pokud ϕi = ξj pro vš. j a ϕi = Fj(ϕj1 , . . . , ϕjk ) Zřejmě ∆ je vytvořující posloupnost pro formuli ϕm. Tuto formuli označme ϕ(ξ1/θ1, ξ2/θ2, . . . , ξ /θ ). Příklad 1.17 Dokažte, že formule ϕ(ξ1/θ1, ξ2/θ2, . . . , ξ /θ ) je definována korektně, tj. že nezávisí na volbě vytvořující posloupnosti ∆ pro ϕ. Příklad 1.18 Mějme formuli ϕ = (X → (Y ∧ ¬Z)). Nalezněte formule θ = ϕ((X → Y )/Z), ρ = ϕ((Y ∧¬Z)/¬(Y → Z)) a µ = ϕ(X/(Y ∧Z), Y/X). Řešení Máme θ = ϕ, ρ = (X → ¬(Y → Z)) a µ = ((Y ∧Z) → (X ∧¬Z)). Kapitola 2 Sémantika výrokové logiky V předchozí kapitole jsme se seznámili s tím, jak vypadají formule výrokové logiky ze syntaktického hlediska. Doposud pro nás formule nebyly ničím jiným než řetězci písmenek a jiných značek. Teprve nyní těmto řetězcům přiřadíme nějaký význam, neboli sémantiku. Budeme pracovat se dvěma standardními pravdivostními hodnotami: pravda (true, 1) a nepravda (false, 0). Výrokové proměnné ve formulích zastupují tzv. atomické výroky, které jsou buď pravdivé, nebo nepravdivé, a které již nelze dále rozložit na jednodušší výroky. Atomický výrok sám o sobě pravdivý či nepravdivý ovšem není, jeho pravdivostní hodnotu je třeba proměnným přiřadit „z vnějšku“, pomocí tzv. valuace. Definice 2.1 Valuace je zobrazení, které každé ze spočetně mnoha proměnných přiřadí hodnotu 1 nebo 0. Níže budeme zápisem Var značit (spočetný) soubor všech proměnných. Pravdivost atomických výroků, a tedy ani formulí, které se z nich skládají, nelze vyhodnotit bez znalosti valuace. Na druhou stranu libovolnou valuaci je možné jednoznačně rozšířit z proměnných na formule a vyhodnotit tak pravdivost libovolné formule. Definice 2.2 Nechť v: Var → {1, 0} je valuace a ϕ je libovolná formule. Rozšíříme v na soubor všech formulí. Hodnotu v(ϕ) definujeme induktivně takto: • pokud ϕ = X, pak v(X) je již definováno; • pokud ϕ = ¬ϕ , pak v(ϕ) = 1 tehdy a jen tehdy když v(ϕ ) = 0; 12 KAPITOLA 2. SÉMANTIKA VÝROKOVÉ LOGIKY 13 • pokud ϕ = ϕ1 ∧ ϕ2, pak v(ϕ) = 1 tehdy a jen tehdy když v(ϕ1) = v(ϕ2) = 1; • pokud ϕ = ϕ1 ∨ ϕ2, pak v(ϕ) = 0 tehdy a jen tehdy když v(ϕ1) = v(ϕ2) = 0; • pokud ϕ = ϕ1 → ϕ2, pak v(ϕ) = 0 tehdy a jen tehdy když v(ϕ1) = 1 a zároveň v(ϕ2) = 0. Předchozí definice definuje valuaci pro formule standardní výrokové logiky. Sémantice obecných logik se budeme věnovat v příští kapitole. Definice 2.3 Řekneme, že formule ϕ je pravdivá ve valuaci v, pokud v(ϕ) = 1. Formule ϕ je tautologie, resp. kontradikce, jestliže je pravdivá v každé, resp. není pravdivá v žádné valuaci. Řekneme, že formule je splnitelná, pokud je pravdivá v alespoň jedné valuaci. Řekneme, že formule ϕ a ψ jsou ekvivalentní, píšeme ϕ ≈ ψ, pokud v(ϕ) = v(ψ) pro libovolnou valuaci v. Příklad 2.1 Rozhodněte a dokažte, zda jsou následující formule splnitelné. a) X ∧ ¬X b) X ∧ (Y → ¬X) c) (X ∨ Y ) ∧ (¬X ∨ ¬Z) ∧ (¬Y ∨ Z) d) ((X ∧ Y ) → ¬Z) ∧ ((X ∧ ¬Z) → ¬Y ) ∧ (¬(X ∧ Y ) → (X ∧ ¬X)) e) ((X ∧ Y ) ∨ ¬(X ∨ Y )) → (¬X ∧ X) Řešení Odpovědi jsou následující: a) NE, b) ANO, c) ANO , d) NE, e) ANO. Formule v b) je splněna libovolnou valuací v takovou, že v(X) = 1 a v(Y ) = 0. Formule v c) je splněna například libovolnou valuací v níž v(X) = 1, v(Y ) = v(Z) = 0. Formule v e) je splněna libovolnou valuací v splňující to, že právě jedna z proměnných X, Y se ve v zobrazí na 1. To, že formule v d) není splnitelná bychom mohli ověřit například sestrojením pravdivostní tabulky. Protože ale velikost pravdivostních tabulek roste exponenciálně s počtem proměnných, je často výhodnější argumentovat slovně. Označme ϕ = ((X ∧ Y ) → ¬Z) ϕ1 ∧ ((X ∧ ¬Z) → ¬Y ) ϕ2 ∧ (¬(X ∧ Y ) → (X ∧ ¬X) ϕ3 ). KAPITOLA 2. SÉMANTIKA VÝROKOVÉ LOGIKY 14 Sporem předpokládejme, že existuje valuace v taková, že v(ϕ) = 1. Pak musí být v(ϕ1) = v(ϕ2) = v(ϕ3) = 1. Protože zřejmě v(X ∧ ¬X) = 0, musí platit v(¬(X ∧ Y )) = 0, jinak by totiž platilo v(ϕ3) = 0. Musí tedy platit v(X) = v(Y ) = 1. Protože v(ϕ1) = 1, musí navíc platit i v(¬Z) = 1. Protože i v(ϕ2) = 1, z v(X) = 1 a v(¬Z) = 1 plyne v(¬Y ) = 1, spor s tím, že v(Y ) = 1. Příklad 2.2 Řekneme, že valuace v a v jsou na proměnných {X, Y, Z} různé, pokud pro některou proměnnou A ∈ {X, Y, Z} platí v(A) = v (A). Zadejte formuli výrokové logiky ϕ s proměnnými X, Y, Z, takovou že ϕ je pravdivá právě při 3 valuacích různých na {X, Y, Z} (tedy pravdivá při 3 z 8 valuací různých na {X, Y, Z}). Řešení Takových formulí je nekonečně mnoho, jedna z možných je ϕ = X ∧ (Y ∨ Z) Nad rámec zadání zdůvodníme správnost našeho řešení tabulkou všech valuací různých na {X, Y, Z}. v(X) v(Y ) v(Z) v(ϕ) 1 1 1 1 1 1 0 1 1 0 1 1 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 Příklad 2.3 Rozhodněte a dokažte, zda jsou následující formule tautologi- emi. a) X → (Y → X) b) ((X → Y ) → Z) → (X → (Y → Z)) c) (X → (Y → Z)) → ((X → Y ) → Z) d) (X → (Y → Z)) → ((X → Y ) → (X → Z)) e) (X ∨ Y ) → (¬Y → X) f) ((X ∧ Y ) ∨ Z) → (¬X → ¬(Y ∨ ¬Z)) KAPITOLA 2. SÉMANTIKA VÝROKOVÉ LOGIKY 15 Příklad 2.4 Najděte formule výrokové logiky ϕ a ψ takové, že jsou současně splněny všechny následující podmínky: • ϕ → ψ je tautologie, • ϕ ↔ ψ není tautologie, • ψ → ϕ je splnitelná. Příklad 2.5 Rozhodněte, zda pro libovolné formule ϕ, ψ, ξ výrokové logiky platí ϕ → (ψ → ξ) ≈ (ϕ → ψ) → ξ Své tvrzení zdůvodněte. Příklad 2.6 Rozhodněte a zdůvodněte, zda existují takové formule ϕ a ψ výrokové logiky, pro které současně platí, že • ϕ → ψ je splnitelná, ale není tautologie, • a zároveň ψ → ϕ není splnitelná. Řešení Takové formule neexistují. Abychom to ukázali, vezměme si libovolnou dvojici formulí ϕ a ψ splňující první podmínku, tj. to, že formule ϕ → ψ je splnitelná, a ukažme, že nemůže platit druhá podmínka, tj. že i formule ψ → ϕ musí být splnitelná. Protože formule ϕ → ψ není tautologie, musí existovat valuace v∗ taková, že v∗(ϕ → ψ) = 0. Z definice sémantiky pro operátor → plyne, že nutně v∗(ψ) = 0. Z toho ale (rovněž díky definici sémantiky pro →) plyne v∗(ψ → ϕ) = 1, což ukazuje, že formule ψ → ϕ je splnitelná. Příklad 2.7 Dejte příklad formulí ϕ a ψ takových, že • ϕ → ψ je tautologie a zároveň • ψ → ϕ je kontradikce. Příklad 2.8 Nechť A je výroková proměnná. Rozhodněte a dokažte, zda existuje formule ϕ taková, že a) ϕ → (ϕ → A) ≈ A b) ϕ → (ϕ → A) ≈ ¬A c) ϕ → (A → ϕ) ≈ A d) (ϕ → A) → ϕ ≈ ¬A KAPITOLA 2. SÉMANTIKA VÝROKOVÉ LOGIKY 16 Příklad 2.9 V jisté zemi žijí dva druhy lidí: poddaní, kteří na otázku vždy odpoví pravdivě, a politici, kteří vždy zalžou. Pocestný z ciziny, který se chce dostat do hlavního města, přijde na neoznačenou křižovatku. Naštěstí jde kolem někdo z místních – spěchá však, a odpoví tak pocestnému pouze na jedinou otázku. Na co se má pocestný zeptat, aby s jistotou zjistil, která cesta vede do města? (Na otázku musí jít odpověďed stylem ano/ne.) Příklad 2.10 V ještě jiné zemi žijí tři druhy lidí: poddaní, kteří vždy říkají pravdu, politici, kteří vždy lžou, a obchodníci, kteří lžou či říkají pravdu dle své libosti. Cestovatel zrovna sedí v místní krčmě a baví se s hospodským (který je poddaným a říká tedy pravdu). Hospodský řekne cestovateli: „Vidíš tamhlety tři lidi co sedí u stejného stolu? Jeden z nich je poddaný, jeden je politik a jeden je obchodníkem. Pokud pomocí třech otázek zjistíš, kdo je kdo, máš u mě pivo zadarmo. Na každou otázku ti může odpověděd jen jeden z nich, ale můžeš si vždycky vybrat, který.“ Cestovatel má vskutku žízeň. Jaké otázky (a komu) má položit? (Na otázky musí opět jít odpovědět stylem ano/ne). (Hint: Nejprve pomocí dvou otázek identifikujte obchodníka.) Příklad 2.11 Je následující soubor formulí splnitelný? Rozhodněte a zdů- vodněte. T = { B ↔ D, A → B, (A ∨ B ∨ D) ∧ (¬A ∨ C) ∧ (¬C ∨ ¬D), D → (A ↔ C))} Příklad 2.12 V systémech pro správu balíčků v linuxu (např. dpkg nebo RPM) je využita výroková logika pro řešení závislostí mezi balíčky. Jedním z problémů je zajistit, aby repozitář neobsahoval žádné rozbité balíčky, které není možné nainstalovat. Značně zjednodušeně máme systém jako trojici (P, d, C), kde • P je množina balíčků, • d : P → 2P přiřazuje každému balíčku p množinu balíčků, na kterých p závisí, a • C ⊆ P × P je symetrická relace dvojic balíčků, které jsou spolu v kon- fliktu. Instalace je množina balíčků Q ⊆ P. Řekneme, že instalace Q je zdravá, pokud a) pro každý balíček p ∈ Q platí d(p) ⊆ Q a zároveň b) pro každé dva balíčky p, q ∈ Q platí (p, q) ∈ C. KAPITOLA 2. SÉMANTIKA VÝROKOVÉ LOGIKY 17 Dále řekneme, že balíček p je nainstalovatelný, pokud existuje zdravá instalace Q obsahující p. Popište algoritmus, který pro zadaný systém (P, d, C) a balíček p ∈ P vypíše formuli výrokové logiky ϕ, takovou že ϕ je splnitelná ⇐⇒ balíček p je nainstalovatelný. (2.1) Algoritmus by měl běžet v čase polynomiálním vzhledem k |P|. Dokažte, že výsledná formule splňuje metaekvivalenci (2.1). Řešení Pro každý balíček q ∈ P budeme používat výrokovou proměnnou Xq, jejíž valuace intuitivně odpovídá tomu, zda q patří do instalace Q. Algoritmus vrátí formuli ϕ = ϕ1 ∧ ϕ2 ∧ ϕ3, kde (intuitivě vysvětleno) ϕ1 = Xp vynutí p ∈ Q, ϕ2 = q∈P (Xq → r∈d(q) Xr) vynutí ke každému q ∈ Q také jeho závislosti a ϕ3 = (q,r)∈C (¬Xq ∨ ¬Xr) vynutí, aby v instalaci nebyly konfliktní balíčky. Je zřejmé, že ke konstrukci formule ϕ je zapotřebí počet kroků polynomiální vzhledem k |P| (konkrétně můžeme použít horní odhad na počet kroků O(|P|2)). Nad rámec zadání ještě dokážeme ekvivalenci (2.1). • “⇒”: Nechť v je valuace, při které je ϕ pravdivá. Ukážeme, že množina balíčků Q = {q | v(Xq) = 1} je zdravá instalace obsahující p. Z definice dostáváme v(ϕ1) = v(ϕ2) = v(ϕ3) = 1. Zřejmě p ∈ Q, protože v(Xp) = 1. Sporem dokážeme, že Q je zdravá. Předpokládejme, že Q není zdravá. Pak buď a) existují balíčky q ∈ Q a r ∈ Q takové, že r ∈ d(q). V tom případě dostáváme v(Xq) = 1 a v(Xr) = 1, a tedy v(ϕ2) = 0, spor. Nebo b) existují balíčky q, r ∈ Q takové, že (q, r) ∈ C. V tom případě dostáváme v(Xq) = v(Xr) = 1, a tedy v(ϕ3) = 0, spor. KAPITOLA 2. SÉMANTIKA VÝROKOVÉ LOGIKY 18 • “⇐”: Nechť Q je zdravá instalace obsahující p. Ukážeme, že ϕ je pravdivá při valuaci v definované v(X) = 1 pokud existuje q ∈ Q, takové že X = Xq, 0 jinak. a) Zřejmě v(ϕ1) = 1, protože Q obsahuje p. b) Uvažme libovolný balíček q ∈ P a položme ϕ2,q = Xq → r∈d(q) Xr. Pokud q ∈ Q, pak zjevně v(ϕ2,q) = 1. Pokud q ∈ Q, pak také d(q) ⊆ Q, protože Q je zdravá. Tedy také v(ϕ2,q) = 1. Celkově v(ϕ2) = 1, protože v(ϕ2,q) = 1 pro každé q ∈ P. c) Uvažme libovolné konfliktní balíčky (q, r) ∈ C. Pak buď q ∈ Q nebo r ∈ Q, protože Q je zdravá. Tedy v(¬Xq∨¬Xr) = 1 a celkově v(ϕ3) = 1. Formule ϕ je pravdivá při valuaci v, protože v(ϕ1) = v(ϕ2) = v(ϕ3) = 1. Příklad 2.13 Máme 3n úkolů a m lidí, z nichž každý je schopen vyřešit právě 3 konkrétní úkoly. Soubor n z těchto m lidí nazveme dobrý, právě když každý úkol umí vyřešit některý z vybraných n lidí. To stejné formálněji: Jsou dána čísla n, m ∈ N. Označme N = {1, . . . , 3n}. Dále je dán soubor S = {N1, . . . , Nm}, kde Ni ⊆ N a |Ni| = 3 pro každé i ∈ {1, . . . , m}. Podsoubor T ⊆ S nazveme dobrý, právě když T = N a |T| = n ( T značí jako obyvkle množinu právě těch prvků, které patří do aspoň jedné množiny z T). Řešení Jak dokážeme, uvedenou vlastnost má například formule ϕ = 3n i=1 m j=1 i∈Nj Aj ∧ 3n i=1 m j=1 i∈Nj m k=j+1 i∈Nk ¬(Aj ∧ Ak). Nechť n, m, S = {N1, . . . , Nm} je libovolný validní vstup. Pro každou valuaci v můžeme uvažovat jí příslušný podsoubor Tv = {Ni | i ∈ {1, . . . , m}, v(Ai) = 1}. KAPITOLA 2. SÉMANTIKA VÝROKOVÉ LOGIKY 19 Naopak pro libovolný podsoubor T ⊆ S můžeme uvažovat valuaci vT definovanou předpisem v(Aj) = 1 pro j ∈ {1, . . . , m} taková, že Nj ∈ T, a v(X) = 0 pro ostatní výrokové proměnné X. Zřejmě v      3n i=1 m j=1 i∈Nj Aj      = 1, právě když pro všechna i ∈ N existuje j ∈ {1, . . . , m} takové, že i ∈ Nj a v(Aj) = 1, tedy právě když Tv = N. Dále zřejmě v      3n i=1 m j=1 i∈Nj m k=j+1 i∈Nk ¬(Aj ∧ Ak)      = 1, právě když pro pro všechna i ∈ N existuje nejvýš jedno j ∈ {1, . . . , m} takové, že i ∈ Nj a v(Aj) = 1, tedy právě když množiny v Tv jsou po dvou disjunktní. Pokud Tv = N (připomeňme, že |N| = 3n a každá množina Ni je trojprvková) a prvky podsouboru T jsou po dvou disjunktní, pak jich musí být právě n, a tedy T je dobrý podsoubor. Naopak je-li T dobrý, pak jsou zřejmě jeho prvky po dvou disjunktní. Dohromady tedy dostáváme, že je-li ϕ splněna nějakou valuací v, pak Tv je dobrý podsoubor souboru S; naopak pokud je T nějaký dobrý podsoubor souboru S, pak vT (ϕ) = 1. Příklad 2.14 (Sudoku) (Pokud je na Vás následující zadání na první přečtení moc abstraktní, dosaďte si za n trojku. Zadání pak odpovídá klasickému sudoku 9 × 9.) Nechť n ≥ 3 je přirozené číslo. Zadáním sudoku typu n2×n2 máme formálně na mysli matici Z typu n2×n2, kde každá buňka matice obsahuje jednu z hodnot {1, . . . , n2, ⊥} (⊥ reprezentuje nepředvyplněné políčko). Řešením takového zadání Z je libovolná matice RZ stejného typu, jejíž buňky obsahují čísla z množiny {1, . . . , n2} a která splňuje následující: • pro libovolné (i, j) takové, že Z(i, j) = ⊥, platí Z(i, j) = RZ(i, j) (tj. nelze přepsat předvyplněná čísla ze zadání); • pro libovolné 1 ≤ i, j ≤ n2 platí, že v i-tém řádku ani v j-tém sloupci matice RZ se žádná hodnota neopakuje. KAPITOLA 2. SÉMANTIKA VÝROKOVÉ LOGIKY 20 • pro libovolné 0 ≤ k, < n platí, že množina {RZ(n·k+i, n· +j) | 1 ≤ i, j ≤ n} obsahuje všechna čísla z množiny {1, . . . , n2}. (Jinak řečeno, rozdělíme-li matici RZ přirozeným způsobem na podmatice typu n×n, tak se v žádné podmatici nevyskytuje dvakrát totéž číslo.) Popište algoritmus, který pro dané zadání sudoku Z zkonstruuje formuli výrokové logiky ϕZ takovou, že ϕZ je splnitelná ⇔ existuje řešení RZ sudoku Z. Dále popište algoritmus který, dostane-li na vstup valuaci splňující Vámi uvedenou formuli ϕZ (například ve formě tabulky pravdivostních hodnot pro proměnné ve formuli), zkonstruuje z této valuace řešení sudoku Z. Oba dva algoritmy by měly běžet v čase polynomiálním vzhledem k n. Příklad 2.15 Je následující formule s výrokovými proměnnými A, B, C splnitelná? Rozhodněte a dokažte. (A → ¬A) ∧ ((B ↔ C) ∧ (¬A → C)) Příklad 2.16 (SAT solver) Najděte co nejrychleji splňující valuaci. (A ∨ B ∨ C) ∧ (¬A ∨ ¬D ∨ ¬E) ∧ (B ∨ C ∨ ¬E) ∧ (D ∨ ¬A ∨ B)∧ (¬A ∨ B ∨ E) ∧ (A ∨ B ∨ ¬D) ∧ (¬A ∨ ¬B ∨ ¬E) ∧ (¬B ∨ C ∨ ¬D)∧ (D ∨ ¬A ∨ ¬B) ∧ (¬A ∨ B ∨ C) ∧ (¬A ∨ ¬B ∨ ¬C) ∧ (¬A ∨ ¬C ∨ D)∧ (¬D ∨ ¬B ∨ ¬C) ∧ (A ∨ ¬C ∨ E) ∧ (¬A ∨ B ∨ A) ∧ (C ∨ ¬B ∨ D)∧ (A ∨ ¬B ∨ C) ∧ (D ∨ E ∨ ¬C) Definice 2.4 Nechť T je soubor výrokových formulí. Řekneme, že T je splnitelný, pokud existuje valuace v taková, že pro každou formuli ϕ ∈ T platí v(ϕ) = 1. O takové valuaci řekneme, že splňuje soubor T. Dále řekneme, že formule ψ je tautologickým důsledkem souboru formulí T, píšeme T |= ψ, jestliže pro libovolnou valuaci v splňující soubor T platí v(ψ) = 1. Definice 2.5 Neorientovaný graf je dvojice G = (V, E), kde V je množina vrcholů a E ⊆ {{u, v} | u, v ∈ V } je množina hran mezi vrcholy (tedy množina nejvýše dvouprvkových neprádných množin). Klika v neorientovaném grafu je podmnožina vrcholů C ⊆ V , kde každé dva vrcholy u, v ∈ C jsou spojené hranou, tedy {u, v} ∈ E. KAPITOLA 2. SÉMANTIKA VÝROKOVÉ LOGIKY 21 Příklad 2.17 Nechť G je neorientovaný graf. Nalezněte systém formulí T takový, že T je splnitelný ⇐⇒ G obsahuje kliku o velikosti alespoň 3 Příklad 2.18 Nechť G je neorientovaný graf a k ∈ N. Nalezněte systém formulí T takový, že T je splnitelný ⇐⇒ G obsahuje kliku o velikosti k a T lze sestrojit v polynomiálním čase vzhledem k velikosti G a k. Definice 2.6 Orientovaný graf je dvojice G = (V, E), kde V je množina vrcholů a E ⊆ V 2 je množina orientovaných hran mezi vrcholy. Nechť G = (V, E) je orientovaný graf a |V | = n. Hamiltonovská kružnice (HK) v orientovaném grafu G je posloupnost vrcholů u0, u1, . . . , un−1 taková, že pro všechna 0 ≤ i ≤ n − 1 platí (ui, ui+1 mod n) ∈ E a pro všechna 0 ≤ i < j ≤ n − 1 platí vi = vj. Příklad 2.19 Nechť G = (V, E) je orientovaný graf o n vrcholech. Nalezněte systém formulí T takový, že T je splnitelný ⇐⇒ G obsahuje Hamiltonovskou kružnici (2.2) a T lze sestrojit v polynomiálním čase vzhledem k velikosti n. Řešení Použijeme výrokové proměnné Eu,w, kde u, w ∈ V , a Xi,w, kde i je celé číslo mezi 0 a n − 1 a w ∈ V . Proměnná Eu,w intuitivně reprezentuje výrok „mezi vrcholy u a w vede hrana“, zatímco Xi,w reprezentuje výrok „vrchol w je i-tým vrcholem na Hamiltonovské kružnici H“, kde H je nějaká HK grafu G. Systém T pak vypadá následovně: T = {η} ∪ {ϕi,w, ψi,w | 0 ≤ i ≤ n − 1, w ∈ V } ∪ {θi, ξi | 0 ≤ i ≤ n − 1}, kde KAPITOLA 2. SÉMANTIKA VÝROKOVÉ LOGIKY 22 η = (u,w)∈E Eu,w ∧ u,w∈V (u,w)∈E ¬Eu,w, ϕi,w = Xi,w → ( u∈V u =w ¬Xi,u), ψi,w = Xi,w → ( 0≤j≤n−1 j=i ¬Xj,w), θi = u,w∈V (Xi,u ∧ Xi+1 mod n,w) → Eu,w , ξi = w∈V Xi,w. Nebudeme formálně dokazovat, že systém T splňuje metaekvivalenci (2.2), uvedeme pouze intuitivní zdůvodnění. Nejprve předpokládejme, že existuje valuace v splňující systém T . Formule η vynutí, aby valuace proměnných Eu,w kódovala vstupní graf G (tj. aby v(Eu,w) = 1 právě když mezi u a w vede hrana). Formule typu ϕi,w (je jich celkem n) dohromady vynutí, že nejvýše jedna z proměnných z množiny {Xi,w | w ∈ V } bude mít přiřazeno true (intuitivně nejvýše jeden vrchol může být i-tým vrcholem konkrétní HK), podobně n formulí tvaru ψi,w dohromady vynutí, že nejvýše jedna z proměnných {Xj,w | 0 ≤ j ≤ n − 1} bude mít přiřazeno true (tj. žádný vrchol se na HK neopakuje). Konečně n formulí typu ξi vynutí, aby pro každé 0 ≤ i ≤ n−1 existovalo alespoň jedno w ∈ V takové, že Xi,w bude mít přiřazeno true. Pokud tedy dohromady vynutí, že pro libovolnou splňující valuaci v definujeme posloupnost u0, . . . un−1 tak, že ui je jediný vrchol w splňující v(Xi,w) = 1, pak tato posloupnost obsahuje všechny vrcholy grafu G. Navíc, formule tvaru θi vynutí, aby pro každé i vedla hrana mezi vrcholy ui a ui+1 mod n. Posloupnost u0, . . . un−1 je tedy Hamiltonovskou kružnicí. Naopak se snadno ukáže, že pokud u0, . . . , un−1 je HK grafu G, pak můžeme zkonstruovat splňující valuaci v následovně: pro všechny vrcholy u, w položíme v(Eu,w) = 1 právě když mezi u a w vede hrana, a pro všechna 0 ≤ i ≤ n − 1 a všechna w ∈ V položíme v(Xi,w) = 1 právě když ui = w. Všem ostatním proměnným přiřadí v hodnotu 0. Příklad 2.20 Nechť T je splnitelný soubor výrokových formulí a nechť ϕ je libovolná výroková formule. Rozhodněte a dokažte, zda platí následující tvrzení: KAPITOLA 2. SÉMANTIKA VÝROKOVÉ LOGIKY 23 a) jestliže T |= ϕ, pak T |= ¬ϕ, b) jestliže T |= ¬ϕ, pak T |= ϕ. Příklad 2.21 Nechť T je libovolný neprázdný soubor výrokových formulí a nechť ϕ, ψ jsou libovolné výrokové formule. Rozhodněte a dokažte, zda platí následující tvrzení: a) Pokut T |= ϕ → ψ, pak buď T |= ψ nebo T |= ¬ϕ. b) Je-li T = {¬ξ | ξ ∈ T} (tj. T obsahuje právě negace formulí ze souboru T), pak T |= ϕ právě když T |= ¬ϕ. Řešení a) Tvrzení neplatí. Jako protipříklad uveďme situaci, kdy ϕ = A, ψ = B a T = {A → B}. Zřejmě {A → B} |= A → B. Zároveň ale neplatí {A → B} |= ¬A ani {A → B} |= B. Pro první zmíněný příklad stačí uvážit valuaci v takovou, že v(A) = v(B) = 1. Pak v(A → B) = 1 a v(¬A) = 0. Pro druhý případ (neplatí {A → B} |= B) stačí uvážit valuaci v takovou, že v (A) = v (B) = 0. Pak opět v (A → B) = 1, avšak v (B) = 0. b) Tvrzení neplatí. Jako protipříklad mějme situaci kdy T = {A ∧ B} a ϕ = A. Zřejmě {A ∧ B} |= A, neplatí však {¬(A ∧ B)} |= ¬A. Abychom ukázali druhé tvrzení, stačí uvážit valuaci v takovou, že v(A) = 1 a v(B) = 0. Pro tuto valuaci platí v(¬(A ∧ B)) = 1, avšak v(¬A) = 0. Příklad 2.22 Nechť T1, T2, . . . je posloupnost splnitelných souborů výrokových formulí. Rozhodněte a dokažte, zda soubory ∞ i=1 Ti a ∞ i=1 Ti jsou splnitelné. Příklad 2.23 Nechť S je soubor všech splnitelných formulí výrokové logiky a S je soubor všech tautologií výrokové logiky. Rozhodněte a dokažte, zda jsou soubory S, resp. S splnitelné. Příklad 2.24 Nechť T1, T2, . . . je posloupnost nesplnitelných souborů výrokových formulí taková, že pro libovolné i platí Ti+1 Ti (tj. Ti+1 je vlastní podmnožinou Ti). Rozhodněte a dokažte, zda je soubor ∞ i=1 Ti vždy nutně nesplnitelný, či naopak vždy nutně splnitelný. KAPITOLA 2. SÉMANTIKA VÝROKOVÉ LOGIKY 24 Řešení Soubor ∞ i=1 Ti může být jak splnitelný, tak nesplnitelný. Uvažme nejprve soubor výrokových formulí T = {Xi ∧ ¬Xi | i ≥ 1}. Neformálně řečeno, soubor T obsahuje nekonečně mnoho „kopií“ formule X ∧¬X, přičemž abychom tyto kopie rozlišili, nahradíme proměnnou X v i-té kopii proměnnou Xi (tj. rozlišení provedeme pomocí indexů proměnných). Dále položme Ti = T \ {X1 ∧ ¬X1, . . . , Xi ∧ ¬Xi} = {Xj ∧ ¬Xj | j ≥ i + 1}. Pak soubor Ti není splnitelný, neboť obsahuje nesplnitelnou formuli Xi ∧ ¬Xi. Avšak ∞ i=1 Ti je prázdný soubor (ověřte!), který je z definice splnitelný. Na druhou stranu uvažme situaci kdy Ti = (T ∪ {X0 ∧ ¬X0}) \ {X1 ∧ ¬X1, . . . , Xi ∧ ¬Xi} = {Xj ∧ ¬Xj | j ≥ i + 1} ∪ {X0 ∧ ¬X0}. Znovu zřejmě platí, že každý soubor Ti je nesplnitelný, ovšem tentokrát je nesplnitelný i soubor ∞ i=1 Ti = {X0 ∧ ¬X0}. Příklad 2.25 Mějme libovolný neprázdný soubor výrokových formulí T a formuli ϕ takovou, že T |= ϕ. Rozhodněte a dokažte, zda existuje konečný vlastní podsoubor T T takový, že T |= ϕ. Věta 2.7 [o kompaktnosti] Nechť T je soubor formulí výrokové logiky. T je splnitelný právě když každá konečná část T je splnitelná. Příklad 2.26 Mějme libovolný nekonečný soubor výrokových formulí T a formuli ϕ takovou, že T |= ϕ. Rozhodněte a dokažte, zda existuje konečný podsoubor T T takový, že T |= ϕ. Řešení Tvrzení platí. Jeden způsob, jak toto tvrzení dokázat, je s použitím věty o korektnosti a úplnosti pro Lukasiewiczův odvozovací systém pro výrokovou logiku (viz kapitola 4, kde se k tomuto příkladu ještě vrátíme). Protože jsme se však v této sbírce dosud odvozovacími systémy nezabývali, ukážeme si alternativní důkaz tohoto tvrzení pomocí věty o kompaktnosti. Nejprve si uvědomme, že soubor T ∪ {¬ϕ} není splnitelný. Pokud by totiž existovala valuace v splňující tento soubor, musela by tato valuace zejména splňovat soubor T. Protože dle předpokladu T |= ϕ, muselo by platit i v(ϕ) = 1 a tedy v(¬ϕ) = 0, spor. Dle věty o kompaktnosti tedy existuje konečný soubor formulí T0 T ∪{¬ϕ} který není splnitelný. Pokud T0 T, pak za hledaný soubor T ze zadání můžeme vzít přímo T0, neboť libovolná formule (tedy i ϕ) je tautologickým důsledkem nesplnitelného souboru formulí. V opačném případě lze psát T0 = T1 ∪ {¬ϕ}, kde T1 ⊆ T. Tvrdíme, že T1 |= ϕ. Pokud je T1 nesplnitelný, pak toto platí triviálně. V opačném případě uvažme libovolnou valuaci v splňující T1. Pak musí platit, že v(¬ϕ) = 0, jinak by T0 byl splnitelný. Tedy v(ϕ) = 1. Protože v byla libovolná valuace splňující T1, platí T1 |= ϕ. KAPITOLA 2. SÉMANTIKA VÝROKOVÉ LOGIKY 25 Příklad 2.27 Následující příklady není těžké vyřešit bez použití věty o kompaktnosti, zkuste je ale vyřešit pomocí této věty. a) Nechť A je spočetná množina. Dokažte, že existuje lineární uspořádání na A. b) Nechť S je nekonečný jazyk nad abecedou {0, 1}. Dokažte, že existuje nekonečné slovo a1a2a3 · · · takové, že pro každé i ∈ N je a1 · · · ai prefixem nějakého prvku z S. c) Nechť A, B jsou spočetné množiny a R ⊆ A × B je relace taková, že pro každé a ∈ A je Ba = {b | (a, b) ∈ R} konečný neprázdný soubor. Dokažte, že pokud pro každou konečnou část A ⊆ A existuje injektivní funkce fA : A → B taková, že fA ⊆ R (zde funkci fA chápeme jako relaci), pak existuje také injektivní funkce f : A → B taková, že f ⊆ R. Příklad 2.28 Nechť ϕ, ψ a ξ jsou formule výrokové logiky. Dokažte, že platí: a) (ϕ → ψ) ≈ (¬ϕ ∨ ψ) b) ¬(ϕ ∧ ψ) ≈ (¬ϕ ∨ ¬ψ) c) ¬(ϕ ∨ ψ) ≈ (¬ϕ ∧ ¬ψ) d) (ϕ ∧ (ψ ∨ ξ)) ≈ ((ϕ ∧ ψ) ∨ (ϕ ∧ ξ)) e) (ϕ ∨ (ψ ∧ ξ)) ≈ ((ϕ ∨ ψ) ∧ (ϕ ∨ ξ)) Příklad 2.29 Převeďte formuli (A → B) ∧ ((C → E) → ¬(C ∧ ¬D)) do DNF. Příklad 2.30 Převeďte formuli (A → B) ∨ ((C → E) → ¬(C ∧ ¬D)) do CNF. Kapitola 3 Nestandardní logické systémy Jak již bylo zmíněno v první kapitole, existují systémy výrokové logiky s různými množinami operátorů. V této kapitole budeme analyzovat tyto systémy z hlediska jejich "popisné síly". Kritérium, podle kterého budeme popisnou sílu hodnotit, je schopnost vyjádřit výrokové funkce. Definice 3.1 Výroková funkce je funkce F : {0, 1}n → {0, 1}, kde n ≥ 1. Intuitivně n-ární výroková funkce je totální funkce, která každému n-árnímu vektoru nul a jedniček přiřadí nulu, nebo jedničku. Příklad výrokové funkce můžeme vidět v tabulce 3. Příklad 3.1 Kolik je všech n-árních výrokových funkcí? Řešení Pro n-ární funkci máme 2n řádků v tabulce. V posledním sloupci tabulky můžeme mít 2počet řádků různých vektorů nul a jedniček. Každý vektor reprezentuje jednu výrokovou funkci. Tedy počet všech n-árních výrokových funkcí je 22n . 1 1 0 1 0 1 0 1 1 0 0 0 Tabulka 3.1: Příklad binární výrokové funkce zadané tabulkou - jde o klasickou funkci „XOR“. 26 KAPITOLA 3. NESTANDARDNÍ LOGICKÉ SYSTÉMY 27 Nyní si obecně definujeme logický systém pro libovolný konečný soubor výrokových funkcí. Definice 3.2 Nechť F1, . . . , Fk je konečný soubor výrokových funkcí. Definujeme formální logický systém L(F1, . . . , Fk), kde • Abeceda je tvořena znaky pro výrokové proměnné, závorkami a znaky F1, . . . , Fk pro uvedené výrokové funkce. • Pojem formule systému L(F1, . . . , Fk) je definován v definici 1.7. • Valuace rozšíříme z výrokových proměnných na formule předpisem v(F(ψ1, . . . , ψn)) = F(v(ψ1), . . . , v(ψn)). Všimněme si, že nyní už máme formálně zadefinovanou syntax i sémantiku obecného logického systému. Dosud uvažovaný logický systém je podle definice 3.2 L(¬, ∨, ∧, →). Dříve zavedené sémantické pojmy (splnitelnost, pravdivost, atd.) se opírají pouze o pojem valuace a „fungují“ tedy v libovolném systému L(F1, . . . , Fk). Od tohoto okamžiku budeme směřovat k definici plnohodnotnosti logického systému, což je schopnost popsat libovolnou výrokovou funkci. K tomu je nutné definovat pro libovolnou formuli logického systému její výrokovou funkci. Pro účely tyto definice zvolme libovolné (ale dále pevné) lineární uspořádání na souboru všech výrokových proměnných. Definice 3.3 Nechť ϕ je formule L(F1, . . . , Fk) a nechť X1, . . . , Xn je vzestupně uspořádána posloupnost (vzhledem k ) všech výrokových proměnných, které se ve ϕ vyskytují. Formule ϕ jednoznačně určuje výrokovou funkci Fϕ : {0, 1}n → {0, 1} danou předpisem Fϕ(−→u ) = v−→u (ϕ), kde v−→u je valuace definovaná takto: • v−→u (Xi) = −→u (i) pro každé 1 ≤ i ≤ n (kde −→u (i) značí i-tou složku vektoru −→u ), • v−→u (Y ) = 0 pro ostatní proměnné Y . Z definice Fϕ v definici 3.3 plyne, že −→u ∈ {0, 1}n je n-ární vektor nul a jedniček. Tento vektor −→u nám díky lineárnímu uspořádání na souboru všech výrokových proměnných jednoznačně určuje valuaci v−→u na výrokových proměnných a tím pádem i na libovolné formuli ϕ. Pro libovolný takový vektor a formuli ϕ lze tedy jednoznačně definovat hodnotu výrokové funkce Fϕ(−→u ) na vektoru −→u jako valuaci v−→u (ϕ). Z definice funkce určené formulí přímo plyne, že pokud ϕ ≈ ϕ , kde formule ϕ obsahuje stejné proměnné jako ϕ , pak Fϕ = Fϕ . KAPITOLA 3. NESTANDARDNÍ LOGICKÉ SYSTÉMY 28 1 1 0 1 0 1 0 1 1 0 0 1 Tabulka 3.2: Výroková funkce pro Schefferův operátor ϕ ψ ≈ ¬(ϕ ∧ ψ) 1 1 0 1 0 0 0 1 0 0 0 1 Tabulka 3.3: Výroková funkce pro Schröderův operátor ϕ | ψ ≈ ¬(ϕ ∨ ψ) Příklad 3.2 Mějme nějaký logický systém L(F1, . . . , Fk). Nechť ϕ je libovolná formule tohoto systému a nechť ξ1, θ1, . . . , ξ , θ jsou formule takové, že ξj ≈ θj pro všechna 1 ≤ j ≤ . Dokažte, že ϕ ≈ ϕ(ξ1/θ1, . . . , ξ /θ ) (viz definice 1.8). Příklad 3.3 Mějme logický systém L(F1, . . . , Fk). Nechť ϕ a ξ1, . . . , ξ jsou libovolné formule tohoto systému. Dokažte, že v libovolné valuaci v platí v(ϕ(X1/ξ1, . . . , X /ξ )) = v (ϕ), kde v je valuace definovaná následovně: pro libovolné 1 ≤ j ≤ klademe v (Xj) = v(ξ ), pro jakoukoliv jinou proměnnou Y klademe v (Y ) = v(y). Řešení Postupujeme indukcí vzhledem ke struktuře formule ϕ. Pokud ϕ = X, kde X je proměnná, máme dvě možnosti: buď X = Xj pro nějaké 1 ≤ j ≤ a pak v(ϕ(X1/ξ1, . . . , X /ξ )) = v(ξj) = v (Xj) = v (ϕ), nebo X není rovna ani jedné z proměnných Xj a potom v(ϕ(X1/ξ1, . . . , X /ξ )) = v(X) = v (X). Nechť nyní ϕ = Fi(ϕ1, . . . , ϕai ), kde ai je arita funkce Fi. Pak platí, že ϕ(X1/ξ1, . . . , X /ξ ) = Fi(ϕ1, . . . , ϕai ), kde pro všechna 1 ≤ r ≤ ai je ϕr = ϕr(X1/ξ1, . . . , X /ξ ). Pro libovolnou valuaci v máme v(ϕ(X1/ξ1, . . . , X /ξ )) = Fi(v(ϕ1), . . . , v(ϕai )) = Fi(v (ϕ1), . . . , v (ϕ )) = v (ϕ), kde druhá rovnost plyne z indukčního předpokladu. KAPITOLA 3. NESTANDARDNÍ LOGICKÉ SYSTÉMY 29 Definice 3.4 Systém L(F1, . . . , Fk) je plnohodnotný, jestliže pro každou výrokovou funkci F existuje formule ϕ systému L(F1, . . . , Fk) taková, že F = Fϕ. Věta 3.5 Logický systém L(¬, ∨, ∧) je plnohodnotný. Důkaz Použitím tabulky výrokových funkcí a disjunktivní normální formy, viz přednáška. Termín plnohodnotnosti není samoúčelný. Například v počítačích jsou veškeré výpočty vykonávány v dvojkové soustavě a na nejnižší úrovni jsou výpočty implementovány pomocí tranzistorů nebo diod spájených do hradel, které jsou schopny vykonávat jednoduché logické operace (AND, OR, NOT, NAND, NOR, XOR). V obvodech se nemusí vyskytovat všechny typy hradel (z ekonomických důvodů), zpravidla je ale výběr hradel takový, aby bylo možné implementovat libovolnou funkci, tedy aby byl systém hradel plnohodnotný. Další aplikace plnohodnotnosti je při dokazování vlastností logických systémů. Například doteď jsme pracovali se systémem L(¬, ∨, ∧, →) a víme, že systém L(¬, ∨, ∧) je plnohodnotný. Tedy dokážeme → ekvivalentně vyjádřit pomocí systému L(¬, ∨, ∧) a můžeme používat → pouze jako syntaktickou zkratku. Požití systému L(¬, ∨, ∧) namísto systému L(¬, ∨, ∧, →) může vést k zjednodušení důkazů např. budeme mít méně případů ověřování při strukturální indukci. Abychom obecně dokázali, že je nějaký logický systém plnohodnotný, měli bychom správně ukázat, jak pro libovolnou výrokovou funkci nalézt příslušnou formuli, která tuto funkci zadává. Ve skutečnosti často využíváme faktu, že nějaký jiný logický systém je plnohodnotný. Pokud bychom např. měli formálně správně metadokázat, že systém L(¬, ∧) je plnohodnotný s pomocí toho, že systém L(¬, ∧, ∨) je plnohodnotný, měli bychom ukázat, že pro libovolnou formuli ϕ logického systému L(¬, ∧, ∨) existuje formule ψ logického systému L(¬, ∧) taková, že Fϕ = Fψ. Následující příklad ukazuje, že ve skutečnosti stačí ukázat, že systém L(¬, ∧) dokáže vyjádřit všechny spojky logického systému L(¬, ∧, ∨). Příklad 3.4 Mějme formální logické systémy L1 = L(F1, . . . , Fk) a L2 = L(G1, . . . , G ). Předpokládejme, že pro libovolné 1 ≤ i ≤ k existuje formule ψi systému L2 taková, že Fψi = Fi. Pak pro libovolnou formuli ϕ systému L1 existuje formule ψ systému L2 taková, že Fϕ = Fψ. KAPITOLA 3. NESTANDARDNÍ LOGICKÉ SYSTÉMY 30 Řešení Dle definice 3.3 lze předpokládat, že pro libovolné 1 ≤ i ≤ k se ve formuli ψi vyskytuje právě ki různých proměnných X1, . . . , Xai , kde ai je arita funkce Fi. Nechť L1, resp. L2, označuje soubor všech formulí systému L, resp. L2. Uvažme též logický systém L = L(F1, . . . , Fk, G1, . . . , G ) a označme L soubor všech formulí tohoto systému. Zřejmě L1 ∪L2 ⊆ L. Definujeme transformaci T : L1 → L2, která nahrazuje spojku Fi formulí ψi induktivně takto: pokud Y je libovolná proměnná, pak klademe T(Y ) = Y . Pokud ϕ je formule tvaru Fi(ξ1, . . . , ξai ), pak klademe T(ϕ) = ψi(X1/T(ξ1), X2/T(ξ2) · · · , Xai /T(ξai )). Jinak řečeno, T(ϕ) vznikne nahrazením proměnné Xj ve formuli ψi formulí T(ξj), přičemž nahrazení provedeme současně pro všechna 1 ≤ j ≤ ai (viz definice 1.8). Ukážeme, že pro libovolnou formuli ϕ ∈ L1 platí následující tvrzení: ve ϕ a T(ϕ) se vyskytují stejné proměnné a Fϕ = F(T(ϕ)). Pak pro libovolnou formuli ϕ systému L1 je formule T(ϕ) formulí systému L2 pro kterou platí Fϕ = FT(ϕ). Postupujeme indukcí vzhledem ke struktuře formule ϕ. Pokud ϕ je proměnná, pak T(ϕ) = ϕ a triviálně platí Fϕ = FT(ϕ). Pokud ϕ ∈ L1 je tvaru Fi(ξ1, . . . , ξai ), pak formule ξ1, . . . , ξai rovněž náleží L1 a platí tedy pro ně indukční předpoklad. Zejména platí, že libovolná proměnná se vyskytuje ve ϕ, právě když se vyskytuje v nějakém ξj, 1 ≤ j ≤ ai což dle indukčního předpokladu nastane právě tehdy, když se tato proměnná vyskytuje v nějakém T(ξj) a tedy i v T(ϕ). Ve formulích ϕ a T(ϕ) se tedy vyskytují stejné proměnné. Dále pro libovolný vektor u ∈ {0, 1}ai platí Fϕ(u) = Fi(Fξ1 (u), . . . , Fξai (u)) = Fi(FT(ξ1)(u), . . . , FT(ξai )(u)) = Fψi (FT(ξ1)(u), . . . , FT(ξai )(u)) = FT(ϕ)(u), kde druhá rovnost plyne z indukčního předpokladu, třetí rovnost plyne z toho, že Fψi = Fi a poslední rovnost plyne z příkladu 3.3. Tím je tvrzení dokázáno. Příklad 3.5 Rozhodněte a dokažte, zda je logický systém L(¬, ∧) plnohod- notný. Řešení Platí (X ∨ Y ) ≈ ¬(¬X ∧ ¬Y ) (dá se ukázat např. tabulkou). Dle příkladu 3.4 tedy v systému L(¬, ∧) lze vyjádřit všechny výrokové funkce, které jsou vyjádřitelné v systému L(¬, ∨, ∧). Protože druhý zmíněný systém je plnohodnotný, je i L(¬, ∧) plnohodnotný. KAPITOLA 3. NESTANDARDNÍ LOGICKÉ SYSTÉMY 31 Toto schéma důkazu je možné využít automaticky, proto při ukázaní plnohodnotnosti systému L(F1, . . . , Fn) na základě plnohodnotnosti jiného systému L(G1, . . . , Gk) postačí, když ukážeme, že pro každou m-ární výrokovou funkci Fi(ϕ1, . . . , ϕm) systému L(G1, . . . , Gk), která se nevyskytuje v {F1, . . . , Fn}, existuje formule ϕ systému L(F1, . . . , Fn), t.ž. Fi(ϕ1, . . . , ϕm) ≈ ϕ nebo Fi = Gϕ. Příklad 3.6 Rozhodněte a dokažte, zda je logický systém L(∧) plnohod- notný. Řešení Tvrzení neplatí. Abychom to ukázali, dokážeme, že libovolná formule ϕ systému L(∧) má následující vlastnost P: P: pokud se ve ϕ vyskytuje pouze jedna výroková proměnná (bez újmy na obecnosti ji označíme X1), pak X1 ≈ ϕ. Uvědomme si, že z toho již plyne, že v systému L(∧) není možné vyjádřit negaci. Pro libovolnou formuli ϕ tohoto systému pak totiž platí platí Fϕ(0) = FX1 (0) = 0 = ¬(0). Fakt, že každá formule ϕ splňuje vlastnost P dokážeme strukturální indukcí. • Báze: Pro formuli X1 zřejmě platí X1 ≈ X1. • Indukční krok: Je-li ϕ tvaru ϕ1 ∧ ϕ2, kde ϕ1 i ϕ2 mají vlastnost P, pak mohou nastat dva případy. Buď ϕ obsahuje více než jednu proměnnou, v kterémžto případě ϕ triviálně splňuje P. Nebo ϕ obsahuje jen jednu proměnnou (označme ji X1) a tedy i ϕ1, ϕ2 obsahují pouze tuto proměnnou. Protože ϕ1, ϕ2 mají vlastnost P, musí platit ϕ1 ∧ ϕ2 ≈ X1 ∧ X1 ≈ X1, kde první ekvivalence plyne z příkladu 3.2 a druhá je triviální. Příklad 3.7 Rozhodněte a dokažte, zda jsou následující logické systémy plnohodnotné. a) L(¬) b) L(∧, ∨) c) L(¬, →) d) L(|) KAPITOLA 3. NESTANDARDNÍ LOGICKÉ SYSTÉMY 32 Příklad 3.8 Dejte příklad výrokové formule ϕ logického systému L(→, ¬) takovou, že Fϕ : {0, 1}2 → {0, 1} (tedy funkce "vyjádřená"formulí ϕ) je dána následující tabulkou (v posledním sloupci jsou hodnoty pro vstup určený prvními dvěma sloupci): 1 1 0 1 0 1 0 1 1 0 0 0 Příklad 3.9 Pro výrokovou logiku mějme formální logický systém L(•, m), kde • je unární výroková funkce taková, že pro libovolné a ∈ {0, 1} je •(a) = 1 a m je ternární tzv. majoritní funkce, tj. funkce taková, že pro libovolné a, b, c ∈ {0, 1} máme m(a, b, c) = a pokud a = b c jinak. Rozhodněte a dokažte, zda existují formule ϕ, ψ systému L(•, m) takové, že a) Fϕ = F¬X, b) Fψ = FX∨Y . (Zde ¬ a ∨ jsou standardní operace „negace“ a „disjunkce“.) Řešení Než popíšeme řešení, uvědomme si, že majoritní funkce vždy vrací tu z hodnot 0, 1, která se mezi jejími třemi argumenty vyskytne alespoň dvakrát. ad a): Taková formule v systému L(•, m) neexistuje. Abychom to dokázali, ukažme, že pro libovolnou formuli ϕ tohoto systému s jednou proměnnou platí Fϕ = id{0,1} nebo Fϕ = F•X. Postupujeme strukturální indukcí. Pokud ϕ = X, pak zřejmě Fϕ = id{0,1}. Pokud ϕ = •ψ, pak Fϕ = F•X. Předpokládejme tedy, že ϕ = m(ψ1, ψ2, ψ3), kde pro ψ1, ψ2, ψ3 dokazované tvrzení platí. Mohou nastat dva případy. Buď pro alespoň dva indexy j ∈ {1, 2, 3} platí Fψj = F•X a pak (z definice majoritní funkce) i Fϕ = F•X. Nebo pro alespoň dva indexy j ∈ {1, 2, 3} platí Fψj = id{0,1}, a pak i Fϕ = id{0,1}. Tím je požadované tvrzení dokázáno. ad b): Taková formule existuje, stačí uvážit například ψ = m(X, Y, •X). Rovnost Fψ = FX∨Y lze ověřit sestrojením pravdivostních tabulek pro obě formule. (Ověřte!) KAPITOLA 3. NESTANDARDNÍ LOGICKÉ SYSTÉMY 33 Příklad 3.10 Pro formuli ϕ = A → (B → (C → D)) nalezněte ekvivalentní formuli v logickém systému L(|), kde | je Shefferův operátor (t.j. ψ | ξ ≈ ¬(ψ ∧ ξ)). Příklad 3.11 Mějme formuli výrokové logiky ϕ ≡ (X ↔ Y ). Najděte k ní ekvivalentní formuli v logickém systému L(→, ¬), pokud taková existuje. Příklad 3.12 K následující formuli zadejte ekvivalentní formuli v (neplnohodnotném) logickém systému L(∧, →). ((B ∧ ¬C) ∨ ¬A) ∨ (B ∧ D) Příklad 3.13 K následující formuli zadejte ekvivalentní formuli v (neplnohodnotném) logickém systému L(∨, →). ¬((¬B ∨ A) ∧ (¬C ∨ A) ∧ ¬D) Příklad 3.14 Mějme binární výrokovou funkci → zadávající standardní implikaci a unární výrokovou funkci takovou, že (1) = 0 (0) = 0 Rozhodněte a dokažte, zda formální logický systém L(→, ) je plnohod- notný. Pro výrokové funkce → a používejte ve formulích tohoto systému shodné symboly, tedy → a . V důkazu můžete využít plnohodnotnost jiných logických systémů z přednášky. Definice 3.6 Výroková funkce F je Schefferovská, jestliže L(F) je plnohodnotný systém. Příklad 3.15 Dokažte následující tvrzení: Výroková funkce F arity n ≥ 1 je Shefferovská právě tehdy, když platí následující podmínky: a) F(P, . . . , P) ≈ ¬P (P je výroková proměnná) b) pro nějaká x1, . . . , xn ∈ {P, Q} (P, Q jsou různé výrokové proměnné) platí, že F(x1, . . . , xn) není ekvivalentní ani ¬P ani ¬Q. (Výše F značí n-ární výrokovou spojku příslušející funkci F.) KAPITOLA 3. NESTANDARDNÍ LOGICKÉ SYSTÉMY 34 Řešení <=: Předpokládejme platnost podmínek 1. a 2. a nechť proměnné x1, . . . , xn ∈ {P, Q} jsou takové, že F(x1, . . . , xn) není ekvivalentní ani ¬P ani ¬Q. Idea: Následující pravdivostní tabulka ukazuje, jakých pravdivostních hodnot může nabývat formule F(x1, . . . , xn). P Q F(x1, . . . , xn) F(x1, . . . , xn) 1 1 0 0 1 0 0 1 0 1 0 1 0 0 1 1 Z tabulky je zřejmé, že máme pouze dvě možnosti. Ostatní možnosti jsou vyloučeny podmínkami 1. a 2. V prvním případě se symbol F chová jako spojka (NOR) a ve druhém případě jako | (NAND). Obě tyto spojky jsou Shefferovské, což nám dá požadovaný výsledek. Formální důkaz: Pro x, y ∈ {0, 1} označme uxy = (uxy 1 , . . . , uxy n ) ∈ {0, 1}n vektor délky n definovaný takto: uxy i = x pokud xi = P y pokud xi = Q Pozorování: (a) F(u00) = 1 a F(u11) = 0 (plyne přímo z podmínky 1.) (b) Pokud by platilo, F(u10) = 0 a F(u01) = 1, pak by bylo F(x1, . . . , xn) ≈ ¬P (c) Pokud by platilo, F(u10) = 1 a F(u01) = 0, pak by bylo F(x1, . . . , xn) ≈ ¬Q Tudíž možnosti (b) a (c) by byly v rozporu s naším předpokladem. Z toho plyne, že nám zbývají pouze dvě možnosti, jak se může funkce F chovat na vektorech uxy. Tyto možnosti jsou i. F(u10) = F(u01) = 0 ii. F(u10) = F(u01) = 1 V případě i. platí, že F = F . V případě 2 pak platí F = F|. Dle příkladu 3.4 existuje pro každou formuli ϕ systému L( ) (v případě i.), resp. systému L(|) (v případě 2) formule ψ systému L(F) taková, že Fϕ = Fψ. Protože KAPITOLA 3. NESTANDARDNÍ LOGICKÉ SYSTÉMY 35 systémy L( ) a L(|) jsou plnohodnotné (viz přednáška), musí být i systém L(F) plnohodnotný, tj. funkce F je Shefferovská. =>: Důkaz provedeme obměnou. Předpokládejme nejprve, že neplatí podmínka a) ze zadání příkladu. Máme celkem tři možnosti. (i.) F(1, . . . , 1) = 1 a F(0, . . . , 0) = 0 (ii.) F(1, . . . , 1) = 1 a F(0, . . . , 0) = 1 (iii.) F(1, . . . , 1) = 0 a F(0, . . . , 0) = 0 Následující tvrzení ukazuje, že ani v jednom z výše uvedených případů, nemůže být funkce F Shefferovská. Tvrzení: Nechť ϕ je formule L(F) obsahující právě jednu výrokovou proměnnou P. (i.) Jestliže F(1, . . . , 1) = 1 a F(0, . . . , 0) = 0 pak Fϕ(1) = 1 (ii.) Jestliže F(1, . . . , 1) = 1 a F(0, . . . , 0) = 1 pak Fϕ(1) = 1 (iii.) Jestliže F(1, . . . , 1) = 0 a F(0, . . . , 0) = 0 pak Fϕ(0) = 0 Důkaz: ad (i.): Indukcí vzhledem k délce vytvořující posloupnosti pro ϕ. • Jestliže ϕ je výroková proměnná P a ν je valuace taková, že ν(P) = 1 a ν(Y ) = 0 pro ostatní výrokové proměnné Y , pak zřejmě Fϕ(1) = ν(ϕ) = ν(P) = 1. • Jestliže ϕ je tvaru F(ψ1, . . . , ψn) pro nějaké formule ψ1, . . . , ψn a ν je valuace taková, že ν(P) = 1 a ν(Y ) = 0 pro ostatní výrokové proměnné Y , pak z indukčního předpokladu plyne, že ν(ψi) = 1 pro 1 ≤ i ≤ n a tedy Fϕ(1) = ν(F(ψ1, . . . , ψn)) = F(ν(ψ1), . . . , ν(ψn)) = F(1, . . . , 1) = 1 Body (ii.) a (iii.) se dokáží úplně stejně. Z výše uvedeného tvrzení tedy plyne, že pokud není splněna podmínka a) ze zadání, pak funkce F není Shefferovská, neboť neexistuje formule ϕ systému L(F) taková, že Fϕ = F¬. Nyní předpokládejme, že podmínka a) je splněna, ale není splněna podmínka b) Dokážeme, že pro každou formuli ϕ ∈ L(F) s právě jednou výrokovou proměnnou P platí buď ϕ ≈ P nebo ϕ ≈ ¬P. Důkaz povedeme indukcí vzhledem k délce vytvořující posloupnosti pro ϕ. KAPITOLA 3. NESTANDARDNÍ LOGICKÉ SYSTÉMY 36 • Jestliže ϕ je výroková proměnná P, pak zřejmě ϕ ≈ P. • Jestliže ϕ je tvaru F(ψ1, . . . , ψn), pak z indukčního předpokladu plyne, že buď ψi ≈ P nebo ψi ≈ ¬P pro 1 ≤ i ≤ n. Pak (viz. příklad 3.2) ϕ ≈ F( ˜P1, . . . ˜Pn) kde ˜Pi = P pokud ψi ≈ P ¬P pokud ψi ≈ ¬P Uvažme nyní formuli ϕ = F(x1, . . . , xn), kde xi = P pokud ˜Pi = P a xi = Q jinak. Nechť přitom IP (resp. IQ) je množina všech indexů takových, že xi = P (resp. xi = Q). Protože předpokládáme, že podmínka 2. není splněna, dostaneme, že buď ϕ ≈ ¬P nebo ϕ ≈ ¬Q. V prvním případě to zejména znamená, že v(ϕ ) = v ∗ (ϕ ) pro libovolné dvě valuace takové, že v(P) = v − (P). Nyní pro libovolnou valuaci v uvažme valuaci v∗ takovou, že v ∗ (Q) = v(¬P) a v ∗ (X) = v(X) pro proměnné X = Q. Pak pro libovolnou valuaci v platí v(ϕ) = v∗(ϕ ) = v(ϕ ) = v(¬P), kde druhá rovnost plyne z toho, že v(P) = v ∗ (P) a třetí z toho, že ϕ ≈ ¬P. Tedy ϕ ≈ ¬P. Podobně se ukáže, že pokud ϕ ≈ ¬Q pak i ϕ ≈ ¬Q. Z výše uvedeného plyne, že neexistuje formule ϕ ∈ L(F) taková, že Fϕ(1) = 1 a Fϕ(0) = 1 a tudíž F není Shefferovská. Příklad 3.16 Rozhodněte a dokažte (bez použití Příkladu 3.15!) zda jsou následující formální logické systémy plnohodnotné. a) L(→)1 b) L(↔) Příklad 3.17 Pokuste se na základě klasifikace z Příkladu 3.15 odvodit vzorec vyjadřující počet n-árních Shefferovských funkcí (viz. přednáška). 1 Symbol → zde zastupuje binární funkci, která udává sémantiku (tj. pravdivostní tabulku) implikace Kapitola 4 Dokazovací systém pro výrokovou logiku Podstatnou motivací pro vznik matematické logiky bylo studium platnosti úsudků, tedy toho, zda nějaké tvrzení logicky vyplývá ze zadaných předpokladů. Řečeno jazykem výrokové logiky: zajímá nás, zda pro daný soubor formulí T a danou formuli ϕ platí T |= ϕ. Navíc bychom rádi toto ověření korektnosti zautomatizovali, aby o platnosti úsudku vskutku nebylo pochyb. Je-li soubor T konečný, např. T = {ϕ1, . . . , ϕk}, pak lze ukázat, že T |= ϕ právě když (ϕ1 ∧· · ·∧ϕk) → ϕ je tautologie. Přitom otázku, zda nějaká formule je tautologie, může relativně snadno zodpovědět počítač (například sestrojením tabulky pravdivostních hodnot, existují ovšem mnohem efektivnější algoritmy). Tento přístup má ovšem dvě zásadní nevýhody. Za prvé, soubor předpokladů nemusí být nutně konečný (s takovými soubory se setkáme zejména později v predikátové logice). V takovém případě není výše uvedený postup vůbec použitelný, a to ani v tom případě, kdy je soubor T nějakým způsobem konečně reprezentovatelný, tj. zpracovatelný počítačem. Za druhé, znalost toho, že (ϕ1 ∧ · · · ∧ ϕk) → ϕ je tautologie, nás sice přesvědčuje o tom, že ϕ je důsledkem T, nedává ale žádný vhled do toho, proč tomu tak je. Jinak řečeno, nedozvíme se nic o struktuře daného úsudku, o tom, jakým myšlenkovým procesem lze danou formuli z předpokladů od- vodit. Z tohoto důvodu zavádíme pojem odvozovacího systému, tj. souboru pravidel, pomocí nichž lze ryze syntakticky, bez jakékoliv znalosti sémantiky, vytvářet („odvozovat“) z nějakých předpokladů nové formule. Oddělení syntaxe od sémantiky je důležité, aby tuto činnost mohl vykonávat i stroj, který sémantiku „nechápe“. Cílem je získat takový odvozovací systém, pomocí 37 KAPITOLA 4. DOKAZOVACÍ SYSTÉM PRO VÝROKOVOU LOGIKU38 kterého lze odvodit nějakou formuli ϕ z nějakého souboru formulí T právě když T |= ϕ. Neformálně řečeno, odvozovací systém je dán souborem axiomů (či schémat axiomů) a souborem odvozovacích pravidel. V této části se soustředíme na tzv. Lukasiewiczův odvozovací systém pro L(→, ¬) (vzpomeňme si, že libovolnou logickou spojku lze vyjádřit pomocí ¬ a →). Ten je dán násle- dovně: Schémata axiómů: • A1: ϕ → (ψ → ϕ) • A2: (ϕ → (ψ → ξ)) → ((ϕ → ψ) → (ϕ → ξ)) • A3: (¬ϕ → ¬ψ) → (ψ → ϕ) Odvozovací pravidlo: • MP: Z ϕ a ϕ → ψ odvoď ψ. (modus ponens) Definice 4.1 Buď T soubor formulí. • Důkaz (či odvození) formule ψ ze souboru předpokladů T je konečná posloupnost formulí ϕ1, · · · , ϕk, kde ϕk je ψ a pro každé ϕi, kde 1 ≤ i ≤ k, platí alespoň jedna z následujících podmínek: – ϕi je prvek T; – ϕi je instancí jednoho ze schémat A1–A3; – ϕi vznikne aplikací pravidla MP na formule ϕm, ϕn pro vhodné 1 ≤ m, n < i. • Formule ψ je dokazatelná z předpokladů T, psáno T ψ, jestliže existuje důkaz ψ z předpokladů T. Jestliže T ψ pro prázdné T, říkáme že ψ je dokazatelná a píšeme ψ. Tím, že odvození probíhá postupně, v jednotlivých krocích, lze sledovat strukturu příslušného úsudku. Navíc v každém korektní odvození se využije pouze konečně mnoho předpokladů, počítač tedy může provést důkaz i z nekonečného souboru T, je-li tento soubor nějakým způsobem reprezentovatelný v počítači. Je-li daný odvozovací systém korektní, pak máme zaručeno, že všechny odvozené formule jsou důsledky původních předpokladů. Je-li systém navíc úplný, pak lze pomocí něj odvodit právě formule vyplývající z daných předpokladů. Pro Lukasiewiczův systém byly na přednášce dokázány následující věty: KAPITOLA 4. DOKAZOVACÍ SYSTÉM PRO VÝROKOVOU LOGIKU39 Věta 4.2 [o dedukci] Nechť ϕ, ψ jsou formule a T soubor formulí. Pak pro Lukasiewiczův systém platí: T ∪ {ψ} ϕ právě když T ψ → ϕ. Věta 4.3 [o korektnosti] Nechť ϕ je formule a T soubor formulí. Pak pro Lukasiewiczův systém platí: jestliže T ϕ, pak T |= ϕ. Věta 4.4 [o úplnosti] Nechť ϕ je formule a T soubor formulí. Pak pro Lukasiewiczův systém platí: jestliže T |= ϕ, pak T ϕ. Předchozí věty ukazují, že Lukasiewiczův systém je přesnou formalizací úsudků ve výrokové logice (se spojkami ¬, →). Příklady odvození v Lukasiewiczově systému je možné nalézt na slidech k přednášce. Příklad 4.1 Nechť P a Q jsou výrokové proměnné. Rozhodněte, zda jsou následující formule dokazatelné. Pokud u některé formule rozhodnete, že je dokazatelná, nalezněte její důkaz v Lukasiewiczově systému. a) P → (Q → P) b) P → P c) P → Q Příklad 4.2 Rozhodněte a dokažte, zda pro každou formuli ϕ výrokové logiky platí buď ϕ, nebo ¬ϕ. Příklad 4.3 Mějme konečný soubor formulí výrokové logiky T a formuli ϕ takovou, že T |= ϕ. Dokažte (bez odvolání se na větu o úplnosti), že T ϕ. Můžete mimo jiné využít toto tvrzení (a nemusíte ho dokazovat): Pro libovolnou formuli ϕ výrokové logiky takovou, že |= ϕ, platí ϕ. Příklad 4.4 Rozhodněte a dokažte, zda pro libovolný soubor T formulí výrokové logiky a pro libovolné formule ϕ, ψ platí T ∪ {ϕ} ϕ → ψ. Řešení Toto obecně neplatí. Uvažme T prázdný soubor, ϕ = A a ψ = B, kde A, B jsou výrokové proměnné. Zřejmě platí A |= A → B. Stačí uvážit valuaci v takovou, že v(A) = 1 a v(B) = 0. Tato valuace splňuje soubor {A}, ovšem v(A → B) = 0. Dle věty o korektnosti musí platit A A → B. Příklad 4.5 Rozhodněte a dokažte, zda existuje formule výrokové logiky ϕ, která není tautologie, a soubor formulí T takový, že platí T ϕ. KAPITOLA 4. DOKAZOVACÍ SYSTÉM PRO VÝROKOVOU LOGIKU40 Věty o korektnosti a úplnosti jsou mocným nástrojem, na přednášce však byly dokázány pouze pro Lukasiewiczův systém.1 Ve zbytku této části budeme zkoumat různé jiné odvozovací systémy, u nichž korektnost ani úplnost a priori předpokládat nemůžeme. Příklad 4.6 Mějme odvozovací systém s jedním schématem axiomu A1: ϕ → ϕ a s pravidlem modus ponens. Nechť ϕ je formule systému L(→, ¬). Rozhodněte a dokažte, zda platí následující tvrzení. a) Pokud ϕ, pak |= ϕ. b) Pokud |= ϕ, pak ϕ. Příklad 4.7 Uvažme formální logický systém L(¬, •) se dvěmi unárními výrokovými funkcemi, kde ¬ je standardní negace a • je unární výroková funkce taková, že pro libovolnou formuli ψ platí •ψ ≈ (ψ ∨ ¬ψ). Uvažme dále následující odvozovací systém S pro L(¬, •). Systém S obsahuje jedno schéma axiomů A1: • ¬ψ a následující 3 odvozovací pravidla: P1: z • ψ odvoď • • • ψ, P2: z • •ψ odvoď ψ, P3: z • ¬¬¬ψ odvoď ¬ • ψ. Důkaz formule ϕ v systému S (z prázdného souboru předpokladů) je konečná posloupnost formulí ξ1, . . . , ξk, kde ξk je ϕ a navíc pro každé ξi, kde 1 ≤ i ≤ k, platí alespoň jedna z následujících podmínek: − ξi je instancí schématu A1; − ξi vznikne aplikací jednoho z pravidel P1-P3 na formuli ξj, pro vhodné 1 ≤ j < i. Řekneme, že formule ϕ je v systému S dokazatelná (značíme S ϕ), existuje-li její důkaz v systému S. Rozhodněte a dokažte, zda pro libovolnou formuli ϕ logického systému L(¬, •) platí: jestliže S ϕ, pak |= ϕ. 1 V literatuře lze nalézt mnoho jiných korektních a úplných odvozovacích systémů pro výrokovou logiku, těmi se však v této sbírce nebudeme zabývat. KAPITOLA 4. DOKAZOVACÍ SYSTÉM PRO VÝROKOVOU LOGIKU41 Řešení Tvrzení neplatí. Dokážeme to tak, že v tomto systému odvodíme konkrétní formuli, která není tautologií. Uvažme tedy například následující důkaz formule ¬ • X v systému S: 1) • ¬¬¬X instance A1 (pro ψ = ¬¬X) 2) ¬ • X P3 na 1) Zřejmě ale ¬ • X není tautologie (je to dokonce kontradikce). Příklad 4.8 2 Uvažme odvozovací systém S z předchozího příkladu. Rozhodněte a dokažte, zda je v systému S dokazatelná formule • • ¬X, kde X je výroková proměnná. Řešení Danou formuli nelze v systému S odvodit. Abychom to mohli dokázat, (meta)dokážeme nejprve platnost následujícího tvrzení: Tvrzení 4.5 Nechť ϕ je libovolná formule dokazatelná v systému S. Pak počet výskytů symbolu • ve ϕ před prvním výskytem jakéhokoliv jiného symbolu (než •) je lichý, nebo nulový. Z předchozího tvrzení pak ihned plyne nedokazatelnost formule • • ¬X v systému S, neboť v této formuli je počet výskytů symbolu • před prvním výskytem jiného symbolu roven 2; je tedy sudý a nenulový. (Meta)důkaz Tvrzení 4.5: Fixujme důkaz ξ1, . . . , ξk formule ϕ (ten existuje, neboť dle předpokladu je ϕ dokazatelná). Pro i ∈ {1, . . . , k} označme li počet symbolů • „na začátku“3 ξi. Indukcí vzhledem k i ukážeme, že pro všechna i ∈ {1, . . . , k} je li liché číslo, nebo nula. Předpokládejme, že i = 1. Pak ξi musí být instancí schématu A1 a musí tedy mít tvar •¬ψ pro nějakou formuli ψ. Ihned vidíme, že li = 1. Nyní předpokládejme, že i > 1 a že pro všechna j < i je li liché číslo, nebo 0. Mohou nastat následující případy: • ξi je instancí schématu A1. Pak lze stejně jako výše ukázat, že li = 1. • ξi vznikne aplikací P1 na ξj, kde j < i. Ihned vidíme, že li = lj + 2. Z indukčního předpokladu víme, že lj je buď nula, nebo liché číslo. Z definice pravidla P1 ale zároveň vidíme, že ξj musí mít tvar •ψ pro 2 Zadání tohoto příkladu bylo inspirováno takzvaným MU-puzzle z knihy Douglase Hofstadtera Gödel, Escher, Bach: An Eternal Golden Braid. 3 Kdybychom chtěli být co nejformálnější, mohli bychom definovat li jakožto délku nejdelšího prefixu slova ξi skládajícího se pouze ze symbolů •. KAPITOLA 4. DOKAZOVACÍ SYSTÉM PRO VÝROKOVOU LOGIKU42 nějakou formuli ψ. Zejména tedy musí být lj ≥ 1 a tudíž lj = 0. Dohromady dostáváme, že lj musí být liché číslo a tedy i li = lj + 2 je liché číslo. • ξi vznikne aplikací P2 na ξj, kde j < i. Podobně jako v předchozím případě vidíme, že li = lj − 2. Z indukčního předpokladu víme, že lj je buď nula, nebo liché číslo. Z definice pravidla P2 ale zároveň vidíme, že ξj je tvaru • • ψ pro vhodné ψ. Zejména tedy lj = 0. Dohromady dostáváme, že lj musí být liché a tedy i li = lj − 2 je liché. • ξi vznikne aplikací P3 na ξj, kde j < i. Pak ξi musí mít tvar ¬ • ψ pro nějakou formuli ψ a tedy li = 0. Tím je Tvrzení 4.5 dokázáno. Všimněme si, že ačkoliv není odvozovací systém S korektní (viz předchozí příklad), nelze v něm odvodit libovolnou formuli. Příklad 4.9 Uvažme formální logický systém L(¬, •) se dvěmi unárními výrokovými funkcemi, kde ¬ je standardní negace a • je unární výroková funkce taková, že pro libovolnou formuli ψ platí •ψ ≈ (ψ ∧ ¬ψ). Uvažme dále následující odvozovací systém R pro L(¬, •). Systém R obsahuje jedno schéma axiomů A1: ¬ • ψ a následující 3 odvozovací pravidla: P1: z ¬ • ψ odvoď ¬ • ¬ • ψ, P2: z ¬ • ψ odvoď ¬ • ¬ψ, P3: z ψ odvoď ¬¬ψ. Důkaz formule ϕ v systému R je definován obdobně jako v příkladu 4.7. Řekneme, že formule ϕ je v systému R dokazatelná (značíme R ϕ), existuje-li její důkaz v systému R. Rozhodněte a dokažte, zda pro libovolnou formuli ϕ platí: jestliže R ϕ, pak |= ϕ. Řešení Tvrzení platí. Chceme dokázat: pro každou formuliϕ logického systému L(¬, •) platí ϕ ⇒|= ϕ. KAPITOLA 4. DOKAZOVACÍ SYSTÉM PRO VÝROKOVOU LOGIKU43 Stačí ukázat, že libovolná instance schématu A1 je tautologie, a že pokud je tautologií vstup některého z pravidel P1–P3, je tautologií i jeho výstup (tj. že každé pravidlo je korektní – z tautologie vždy odvodí tautologii). A1: ukážeme, že |= ¬ • ϕ pro libovolnou formuli ϕ. Fixujme libovonou ale nadále pevnou valuaci v a formuli ϕ. Pak v(•ϕ) = v(ϕ ∧ ¬ϕ) = 0, což vyplývá z definice spojek •, ¬ a ∧. Z toho a z definice negace vyplývá, že v(¬ • ϕ) = 1. Abychom snadněji dokázali korektnost pravidel P1 a P2, dokážeme si následující pomocné tvrzení. Tvrzení 4.6 Formule ϕ logického systému L(¬, •) je tautologie, právě když obsahuje alespoň jeden výskyt symbolu • a počet výskytů symbolu negace před prvním výskytem symbolu • je lichý. (Meta)důkaz Tvrzení 4.6: Nejprve ukážeme, že libovolná formule systému L(¬, •), která obsahuje lichý výskyt symbolu ¬ před prvním výskytem symbolu •, je tautologie. Potom ukážeme, že žádná jiná formule systému L(¬, •) nemůže být tautologie. Výše jsme ukázali, že v(•ξ) = 0 pro libovolnou formuli ξ a valuaci v. Z definice negace dále plyne ξ ≈ ¬¬ξ pro libovolnou ξ. Tedy pro formuli ψ = ¬ . . . ¬ • ϕ, která má lichý počet negací před prvým výskytem • platí ψ ≈ ¬ • ϕ. Výše jsme ukázali, že ¬ • ϕ je tautologie a tedy i ψ je tautologie. Ukažme nyní, že formule nemající uvedený tvar nemůže být tautologií. Mohou nastat dva případy: buď ϕ neobsahuje •, nebo obsahuje • a před prvním výskytem • má sudý počet výskytů symbolu ¬. Nejprve předpokládejme, že ψ obsahuje • a před prvním výskytem • má sudý počet negací, tj. má tvar ψ = ¬ . . . ¬ • ϕ. Z ξ ≈ ¬¬ξ pro libovolnou ξ plyne ψ ≈ •ϕ. Výše jsme ukázali, že v(•ξ) = 0 pro libovolnou formuli ξ a valuaci v. Tedyψ není tautologie (je to dokonce kontradikce). Zbývá ukázat, že formule ψ, která neobsahuje •, není tautologie. Mohou nastat 2 případy: buď ψ obsahuje sudý počet negací, nebo lichý počet negací. Zjevně ψ obsahuje právě 1 výrokovou proměnnou, označme ji A. V případe, že ψ obsahuje sudý počet negací, uvažme valuaci v takovou, že v(A) = 0. Opětovným použitím ξ ≈ ¬¬ξ pro libovolnou ξ dostáváme, že v(ψ) = 0, tedy ψ není tautologie. Podobně pro případ, kdy ψ obsahuje lichý počet negací (volíme valuaci t.ž. v(A) = 1). Z Tvrzení 4.6 plyne, že výstupy P1 a P3 ¬•¬•ψ a ¬•¬ψ jsou tautologie, tedy pravidla P1 a P2 jsou korektní.4 4 Všimněte si, že v důkazu jsme vůbec nemuseli zkoumat tvar vstupů těchto pravidel. KAPITOLA 4. DOKAZOVACÍ SYSTÉM PRO VÝROKOVOU LOGIKU44 Korektnost pravidla P3 vyplývá z toho, že ξ ≈ ¬¬ξ pro libovolnou formuli ξ. Příklad 4.10 Uvažme odvozovací systém R z předchozího příkladu. Dokažte, že libovolná formule ϕ systému L(¬, •), která je tautologií, je v odvozovacím systému R dokazatelná. Řešení Nechť ψ je libovolná tautologie systému L(¬, •). Z Tvrzení 4.6 plyne, že ψ = ¬ . . . ¬ • ϕ, kde počet výskytu symbolu ¬ před prvním výskytem • je roven 2n + 1 pro nějaké n ∈ N0. Uvažme důkaz ξ1, . . . ξn+1 formule ψ v systému R, kde ξ1 = ¬•ϕ je instancí (A1), a pro libovolné 2 ≤ i ≤ n+1 je ξi+1 = ¬¬ξi formule vzniklá aplikací (P3) na ξi. Příklad 4.11 V této úloze se budeme zabývat systémem L(→, ¬) výrokové logiky. Uvažujme následující schémata axiomů: A1: (¬¬ϕ → ϕ), A2: ¬ϕ. Dále pro libovolnou množinu S ⊆ {1, 2} nechť DS označuje odvozovací systém s pravidlem modus ponens, kde axiomy jsou právě ty formule, které jsou instancí schématu As pro aspoň jedno s ∈ S. (Tedy v systému D∅ nejsou žádné formule axiomy, v systému D{1} jsou axiomy právě instance schématu A1 apod.) Odvozovací systém nazýváme korektní, právě když každá v něm dokazatelná formule je tautologie. Obráceně odvozovací systém nazveme úplný, právě když každá tautologie je v něm dokazatelná. O každém ze systémů D∅, D{1}, D{2}, D{1,2} rozhodněte a dokažte, zda je korektní a zda je úplný. Řešení V odvozovacím systému D∅ není žádná formule axiomem, takže žádná posloupnost (kladné délky) formulí není důkaz, a tedy žádná formule není dokazatelná. Takový odvozovací systém je tedy triviálně korektní, ale není úplný, neboť například tautologie (A → A) v něm není dokazatelná. Podívejme se nyní na systém D{2}. Jak uvidíme, v tomto odvozovacím systému jsou dokazatelné jen jeho axiomy, což (meta)dokážeme indukcí vzhledem k délce (formálního) důkazu: Dle definice důkazu může být jeho první formulí jedině axiom. Nyní předpokládejme, že máme důkaz sestávající pouze z instancí schématu A2. Dle definice důkazu pak další formule bude opět axiomem nebo vznikne aplikací MP na formule již obsažené v důkazu. MP lze ale aplikovat jen v případě, že jedna z formulí začíná levou KAPITOLA 4. DOKAZOVACÍ SYSTÉM PRO VÝROKOVOU LOGIKU45 závorkou, avšak všechny instance schématu A2 začínají negací. V D{2} tak není dokazatelná například tautologie (A → A), takže D{2} není úplný. Na druhou stranu v D{2} je dokazatelná formule ¬A (je totiž axiomem), která zřejmě není tautologie, takže tento odvozovací systém není ani korektní. V systému D{1} je situace podobná — opět jsou dokazatelné jen jeho axiomy. Tentokrát ovšem bude zdůvodnění, proč nelze aplikovat MP, trochu obtížnější. Předpokládejme pro spor, že v nějakém důkazu vznikla některá formule aplikací pravidla MP na formule α, (α → β) a uvažme první formuli, která takto vznikla (formule α, (α → β) jsou tedy instancemi schématu A1). Formule α je tedy tvaru (¬¬ϕ → ϕ), takže druhá z formulí je tvaru ((¬¬ϕ → ϕ) → β), což není možné, jelikož druhým znakem každé instance schématu A1 je negace. Uvážíme-li navíc, že všechny axiomy tohoto odvozovacího systému jsou zřejmě tautologie, dostáváme, že je korektní. Není ovšem úplný, jelikož v něm není dokazatelná například tautologie (A → A). Konečně v odvozovacím systému D{1,2} je každá formule ξ dokazatelná: (¬¬ξ, (¬¬ξ → ξ), ξ) je zřejmě její důkaz (instance A2 pro ϕ = ¬ξ, instance A1 pro ϕ = ξ, aplikace MP na předchozí dvě). Takový odvozovací systém je tedy triviálně úplný, ale není korektní, neboť například formule A je dokazatelná, ale není tautologie. Kapitola 5 Syntax predikátové logiky Predikátová logika je rozšířením výrokové logiky. V predikátové logice proměnné nemusí nabývat pouze hodnot pravda/nepravda, ale mohou nabývat hodnot z libovolného předem určeného univerza. Dále predikátová logika umožňuje vyjadřovat se o vztazích mezi prvky tohoto univerza pomocí tzv. predikátů. Pro definici syntaxe predikátové logiky nejprve definujeme jazyk. Definice 5.1 Jazyk (stejně jako jazyk s rovností) je systém predikátových symbolů a funkčních symbolů, kde u každého symbolu je dána jeho četnost (arita), která je nezáporným celým číslem. Predikátové symboly arity nula v jistém smyslu odpovídají konstantám True a False, funkční symboly arity nula jsou symboly pro konstanty. Predikátovým a funkčním symbolům se také říká mimologické symboly. Jazyk je tedy plně určen mimologickými symboly. Rozdíl mezi jazykem a jazykem s rovností se projeví v tom, že do predikátové logiky pro jazyk s rovností přidáme speciální logický symbol =, jehož sémantika bude definována speciálním způsobem. Pro lepší pochopení budeme definice ilustrovat na příkladu z algebry. Víme že pologrupa je dvojice (M, ·), kde • M je nosná množina, • · : M × M → M a • · je asociativní (tedy pro každé k, l, m z M platí (k ·l)·m = k ·(l ·m)). Jazyk teorie pologrup tedy bude jazykem s rovností obsahující jeden funkční symbol · arity 2. 46 KAPITOLA 5. SYNTAX PREDIKÁTOVÉ LOGIKY 47 Definice 5.2 Abecedu predikátové logiky pro jazyk L tvoří následující sym- boly: • Znaky pro proměnné x, y, z, . . . , kterých je spočetně mnoho. • Mimologické symboly, tj. predikátové a funkční symboly jazyka L. • Je-li L jazyk s rovností, obsahuje abeceda speciální znak = pro rovnost. • Logické spojky → a ¬. • Symbol ∀ pro univerzální kvantifikátor. • Závorky ( a ). Definice 5.3 Termem jazyka L je slovo t nad abecedou predikátové logiky pro jazyk L, pro které existuje vytvořující posloupnost slov t1, · · · , tk, kde k ≥ 1, tk je t, a pro každé 1 ≤ i ≤ k má slovo ti jeden z následujících tvarů: • proměnná, • f(ti1 , · · · , tin ), kde 1 ≤ i1, · · · , in < k, f je funkční symbol jazyka L, a n je arita f. Poznámka 5.4 U binárních funkčních symbolů (a později také predikátů) dovolíme pro větší čitelnost infixový zápis. U funkčních (a predikátových) symbolů arity nula budeme psát c místo c(). Pro term (x · y) · z jazyka pologrup {·} existuje například následující vytvořující posloupnost x, y, z, (x · y), (x · y) · z. Posloupnost není určena jednoznačně a term (x · y) · z má nekonečně mnoho jiných vytvořujících posloupností. Dále si všimneme, že term musí mít konečnou délku (vzhledem k počtu znaků), protože má konečnou vytvořující posloupnost a každým krokem ve vytvořující posloupnosti přidáme maximálně konečně mnoho znaků. Definice 5.5 Term je uzavřený, jestliže neobsahuje proměnné. Uzavřený term musí tedy obsahovat minimálně jeden funkční symbol arity 0. Příklad 5.1 Mějme jazyk s rovností {f, g, h, i}, kde všechny symboly jsou funkční. Určete které z následujících termů jsou uzavřené: • f(g, h), • f(g, h(g, f)), • f(g, f(h, i)). KAPITOLA 5. SYNTAX PREDIKÁTOVÉ LOGIKY 48 Řešení • ano, term neobsahuje proměnné a f má aritu 2 a g, h mají aritu 0, • ne, není to term, protože funkční symbol f by musel mít současně aritu 0 a 2, • ano, term neobsahuje proměnné a f má aritu 2 a g, h, i mají aritu 0. Definice 5.6 Formule predikátového počtu jazyka L je slovo ϕ nad abecedou predikátové logiky pro jazyk L, pro které existuje vytvořující posloupnost slov ψ1, · · · , ψk, kde k ≥ 1, ψk je ϕ, a pro každé 1 ≤ i ≤ k má slovo ψi jeden z následujících tvarů: • P(t1, · · · , tn), kde P je predikátový symbol jazyka L arity n a t1, · · · , tn jsou termy jazyka L. • t1 = t2, je-li L jazyk s rovností a t1, t2 jsou termy jazyka L. • ¬ψj pro nějaké 1 ≤ j < i, • (ψj → ψj ) pro nějaká 1 ≤ j, j < i, • ∀x ψj, kde x je proměnná a 1 ≤ j < i. Pro formuli ϕ = ∀x∀y∀z (x·y)·z = x·(y ·z) jazyka pologrup {·} existuje například následující vytvořující posloupnost (x · y) · z, x · (y · z), (x · y) · z = x · (y · z), ∀z (x · y) · z = x · (y · z), ∀y∀z (x · y) · z = x · (y · z), ϕ. Poznámka 5.7 Ve zbytku textu budeme používat následující „zkratky“: • ∃x ϕ značí ¬∀x ¬ϕ • ϕ ∨ ψ značí ¬ϕ → ψ • ϕ ∧ ψ značí ¬(ϕ → ¬ψ). • ϕ ↔ ψ značí (ϕ → ψ) ∧ (ψ → ϕ), kde symbol ∧ dále „rozvineme“ podle předchozího bodu. I pro predikátovou logiku lze využít techniku indukce vzhledem k délce vytvořující posloupnosti. Když budeme dokazovat složitější tvrzení tvaru „pro každou formuli predikátového počtu pro jazyka L platí. . . “, je někdy nutné využít strukturální indukci dvakrát: pro pomocné tvrzení o termech KAPITOLA 5. SYNTAX PREDIKÁTOVÉ LOGIKY 49 (zde vedeme důkaz indukcí vzhledem ke struktuře termu) a pro tvrzení o formulích. Tento postup bude použit například v příkladu 7.2. Zde uvedeme jen jednoduchý příklad, nejprve ale zaveďme a procvičme další pojmy, které budeme potřebovat. Definice 5.8 Každý výskyt proměnné ve formuli predikátového počtu je buď volný nebo vázaný podle následujícího induktivního předpisu: • Ve formuli tvaru P(t1, · · · , tn) jsou všechny výskyty proměnných volné. • Výrokové spojky nemění charakter výskytů proměnných, tj. je-li daný výskyt proměnné ve formuli ψ volný (resp. vázaný), je odpovídající výskyt ve formulích ¬ψ, ϕ → ψ, ψ → ϕ rovněž volný (resp. vázaný). • Ve formuli ∀x ψ je každý výskyt proměnné x (včetně výskytu za kvantifikátorem) vázaný; byl-li výskyt proměnné různé od x volný (resp. vázaný) ve formuli ψ, je odpovídající výskyt ve formuli ∀x ψ rovněž volný (resp. vázaný). Definice 5.9 • Proměnná se nazývá volnou (resp. vázanou) ve formuli, má-li v ní volný (resp. vázaný) výskyt. • Formule je otevřená, jestliže v ní žádná proměnná nemá vázaný výskyt. • Formule je uzavřená (také sentence), jestliže v ní žádná proměnná nemá volný výskyt. • Zápis ϕ(x1, · · · , xn) značí, že všechny volné proměnné ve formuli ϕ jsou mezi x1, · · · , xn (nemusí nutně platit, že každá z těchto proměnných je volná ve ϕ). • Univerzální uzávěr formule ϕ je formule tvaru ∀ x1 · · · ∀ xn ϕ, kde proměnné x1, · · · , xn jsou právě všechny volné proměnné formule ϕ. Všimneme si, že proměnná může být ve formuli současne volná i vázaná, např. proměnná x ve formuli P(x) → ∀xP(x). Příklad 5.2 Napište univerzální uzávěr pro následující formule: • P(x) → ∃x (x = y ∧ P(z)), • ∀x (P(x) = Q(y)) → x ∧ ∃y (Q(y, z)). KAPITOLA 5. SYNTAX PREDIKÁTOVÉ LOGIKY 50 Řešení Vyřešíme první bod, druhý se vyřeší podobně. Jednoduše identifikujeme všechny proměnné, které mají v zadané formuli volný výskyt. Jsou to proměnná x v podformuli P(x) a proměnné y, z v podformuli ∃x (x = y ∧ P(z)). Teď už jen stačí přidat univerzální kvantifikátory před zadanou formuli. Výsledek je tedy: ∀x∀y∀z(P(x) → ∃x (x = y ∧ P(z))). Teď už následuje slíbená aplikace strukturální indukce. Příklad 5.3 Nechť máme jazyk s rovností L = {P, f}, kde P je binární predikátový symbol a f je ternární funkční symbol. Dokažte, že pro každou otevřenou formuli jazyka L platí, že obsahuje sudý počet výskytů proměn- ných. Řešení Nejdřív dokážeme pomocné tvrzení. Tvrzení 5.10 Nechť máme výše definovaný jazyk L. Každý term tohoto jazyka obsahuje lichý počet výskytů proměnných. Důkaz Tvrzení dokážeme pro libovolný term t jazyka L pomocí strukturální indukce. Báze. Pokud t = x, kde x je proměnná, pak t obsahuje jeden výskyt proměnné a tvrzení platí. Indukční krok. Předpokládejme, že tvrzení platí pro nějaké termy t1, t2 a t3, tedy obsahují p1, p2 a p3 výskytů proměnných, kde p1, p2 a p3 jsou lichá čísla. Term f(t1, t2, t3) obsahuje p1 + p2 + p3 výskytů proměnných, což je zřejmě liché číslo. Teď dokážeme tvrzení ze zadání příkladu. Důkaz Tvrzení dokážeme pro libovolnou otevřenou formuli ϕ jazyka L pomocí strukturální indukce. Báze. Nechť je formule ϕ tvaru P(t1, t2) nebo t1 = t2, kde t1 a t2 mají p1 a p2 výskytů proměnných. Z předchozího tvrzení víme, že libovolný term obsahuje lichý počet výskytů proměnných. Zřejmě ϕ obsahuje p1+p2 výskytů proměnných, což je sudé číslo. Indukční krok. Předpokládejme, že tvrzení platí pro nějaké formule ϕ1 a ϕ2, tedy obsahují p1 a p2 výskytů proměnných a obě jsou to sudá čísla. Pokud je ϕ tvaru ¬ϕ1 tak obsahuje p1 výskytů proměnných, což je sudé číslo. Pokud je ϕ tvaru ϕ1 → ϕ2, tak obsahuje p1 + p2 výskytů proměnných, což je sudé číslo. Formule tvaru ∀xϕ nemusíme uvažovat, protože taková formule obsahuje vázaný výskyt proměnné x přímo za kvantifikátorem, tedy není otevřená. KAPITOLA 5. SYNTAX PREDIKÁTOVÉ LOGIKY 51 Definice 5.11 Term t je substituovatelný za proměnnou x ve formuli ϕ, jestliže žádný výskyt proměnné v termu t se nestane vázaným po provedení substituce termu t za každý volný výskyt proměnné x ve formuli ϕ. Jeli t substituovatelný za x ve ϕ, značí zápis ϕ(x/t) formuli, která vznikne nahrazením každého volného výskytu x ve ϕ termem t. Příklad 5.4 Mějme jazyk L = {P, Q} s rovností, kde P i Q jsou unární predikátové symboly. Pro každou z následujících formulí rozhodněte, zda je term f(y) substituovatelný za x, a pokud ano, proveďte substituci a zapište výslednou formuli. • ∀y∀xx = y, • ∀x(P(x) → P(y)) → Q(x) ∧ ∃yQ(y), • ∀y(P(x) → ∀xP(x)) → z = y. Řešení V první formuli není žádný volný výskyt proměnné x, tedy zadaný term je substituovatelný a výsledná formule je ∀y∀xP(x) = P(y). V druhé formuli bodě je term daný term opět substituovateln y, výsledná formule je ∀x(P(x) → P(y)) → f(y) ∧ ∃yQ(y). V posledním bodě není term Q(f(y)) substituovatelný za x protože v podformuli ∀y(P(x) → ∀xP(x)) se nachází volný výskyt x, ale y by se v této podformuli stála vázanou. Definice 5.12 Nechť ϕ je formule a t1, · · · , tn termy, které jsou v uvedeném pořadí substituovatelné za proměnné x1, · · · , xn ve ϕ (předpokládáme, že x1, · · · , xn jsou různé). Symbol ϕ(x1/t1, · · · , xn/tn) značí formuli, která vznikne „simultánním nahrazením“ každého volného výskytu xi termem ti pro každé 1 ≤ i ≤ n. Přesněji, ϕ(x1/t1, · · · , xn/tn) je formule ϕ(x1/z1) · · · (xn/zn)(z1/t1) · · · (zn/tn), kde z1, · · · , zn jsou (různé) proměnné, které se nevyskytují v t1, · · · , tn ani mezi x1, · · · , xn. Rozdíl mezi simultánním a postupným nahrazením ilustrujeme na příkladě. Formule P(x, y)(x/y, y/x) je po aplikování simultánního nahrazení P(y, x), zatímco formule P(x, y)(x/y)(y/x) je po aplikování prvního nahrazení P(y, y)(y/x) a po aplikování druhého nahrazení P(x, x). Simultánní nahrazení se používá při důkazu věty o úplnosti pro predikátovou logiku KAPITOLA 5. SYNTAX PREDIKÁTOVÉ LOGIKY 52 (konkrétně ve věte o konstantách), který ale v cvičebnici neuvádíme. Definice simultánního nahrazení je zde kvůli konzistenci s přednáškou a na procvičení tohoto pojmu. Příklad 5.5 Uvažme formuli ϕ = ∀y((P(x) → ∃zP(y))∧P(z)) → (P(y) ↔ P(z)). Zapište formule ϕ(y/x)(x/z) a ϕ(y/x, x/z). Kapitola 6 Sémantika predikátové logiky I Sémantika predikátové logiky se silně opírá o pojem realizace jazyka. Abychom uměli říct, zda je nějaká formule pravdivá, musíme vědět, jakých hodnot mohou nabývat proměnné a jaký význam mají predikátové a funkční symboly. Definice 6.1 Realizace M jazyka L je zadána • neprázdným souborem M, nazývaným univerzum (případně nosič). Prvky univerza nazýváme individui. • Přiřazením, které každému n-árnímu predikátovému symbolu P přiřadí n-ární relaci PM na souboru M, • přiřazením, které každému m-árnímu funkčnímu symbolu přiřadí funkci fM : Mm → M. Ohodnocení je zobrazení přiřazující proměnným prvky univerza M. Realizace je vlastně svět, ve kterém se budeme pohybovat. Univerzum je to, z čeho se svět skládá. Prvky univerza mohou být úplně libovolné, napr. přirozená čísla, ovoce, auta,... Definování funkcí a relací nám zase určuje jaké zákonitosti platí mezi jednotlivými prvky univerza. To že n-ární predikátový symbol je definovaný jako n-ární relace koresponduje s tím, že predikátové symboly zadávají vlastnosti systému. Danou vlastnost splňují jenom ty ntice univerza, které se nachází v relaci (tedy v množině n-tic). Následujícími dvěma definicemi zavedeme pojem pravdivosti formule v realizaci. 53 KAPITOLA 6. SÉMANTIKA PREDIKÁTOVÉ LOGIKY I 54 Definice 6.2 Realizace termu t při ohodnocení e v realizaci M, psáno tM[e] (případně jen t[e], je-li M jasné z kontextu), definujeme induktivně takto: • x[e] = e(x) • f(t1, · · · , tm)[e] = fM(t1[e], · · · , tm[e]) (pro m = 0 je na pravé straně uvedené definující rovnosti fM(∅)). Tedy v případě fixované realizace nám každý term představuje nějaký prvek univerza. Teď už máme v rukách vše potřebné pro zadefinování pravdivosti formule. Definice 6.3 (A. Tarski) Buď M realizace L, e ohodnocení a ϕ formule predikátového počtu jazyka L. Ternární vztah M |= ϕ[e] definujeme indukcí ke struktuře ϕ takto: • M |= P(t1, · · · , tm)[e] právě když (t1[e], · · · , tm[e]) ∈ PM. • Jestliže L je jazyk s rovností, pak M |= (t1 = t2)[e] právě když t1[e] a t2[e] jsou stejná individua. • M |= ¬ψ[e] právě když neplatí M |= ψ[e]. • M |= (ψ → ξ)[e] právě když M |= ξ[e] nebo neplatí M |= ψ[e]. • M |= ∀x ψ[e] právě když M |= ψ[e(x/a)] pro každý prvek a univerza M, kde ohodnocení e(x/a) je takové, že proměnné x přiřadí prvek a a každé jiné proměnné y přiřadí hodnotu e(y). Jestliže M |= ϕ[e], říkáme, že ϕ je pravdivá v M při ohodnocení e. Jestliže M |= ϕ[e] pro každé e, je ϕ pravdivá v M, psáno M |= ϕ. Jediný složitější bod v Tarského definici je definice pravdivosti formule tvaru ∀x ψ[e]. Zde musíme zaručit, že formule ϕ je pravdivá pro libovolný prvek univerza, který můžeme nahradit za každý výskyt proměnné x, který je vázaný uvedeným prvním výskytem kvantifikátoru ∀. Teď procvičíme definice na jednoduchých příkladech. Příklad 6.1 Mějme jazyk L = {P} bez rovnosti, kde P je unární predikátový symbol. Znegujte formuli ϕ ≡ ∀x ∃y (P(x) → ¬P(y)). Tedy najděte formuli ψ ekvivaletní formuli ¬ϕ takovou, že ψ obsahuje negaci pouze na úrovni predikátových symbolů (podobně jako formule ϕ). Uzavřené formule ξ, ξ jazyka L nazýváme ekvivalentní, pokud pro každou realizaci M jazyka L platí M |= ξ, právě když M |= ξ . KAPITOLA 6. SÉMANTIKA PREDIKÁTOVÉ LOGIKY I 55 Řešení ∃x∀y(P(x) ∧ P(y)). Příklad 6.2 Mějme jazyk L = {·} s rovností, kde · je binární funkční symbol. Dejte příklad uzavřené formule ϕ predikátového počtu jazyka L takové, že pro libovolnou realizaci M jazyka L platí M |= ϕ právě tehdy, když a) (M, ·M) je pologrupa b) (M, ·M) je monoid c) (M, ·M) je grupa Řešení a) V předchozí kapitole jsme uvedli, že binární funkce musí splňovat asociativitu. Tedy formulí ϕ musíme vynutit, aby pro libovolné tři prvky x, y, z ∈ M platilo, že x · (y · z) = (x · y) · z. Tedy výsledn8 formule zajišťující vlastnosti pologrupy je ϕ1 = ∀x∀y∀z (x · (y · z) = (x · y) · z). b) Podobně jako pro předchozí bod si zjistíme definici monoidu. Kromě asociativity musí ještě existovat jednotkový prvek. Formule na vynucení jednotkového prvku je ∃x∀y(x · y = x ∧ y · x = x). Musíme si uvědomit, že asociativita a existence jednotkového prvku musí platit současně, tedy mezi naše vytvořené formule musíme dát konjunkci. Výsledná formule je tedy ϕ2 = ϕ1 ∧ ∃x∀y(x · y = x ∧ y · x = x). c) Okrem asociativity a existence jednotkového prvku x musíme zaručit existenci inverzního prvku pro každé y ∈ M. Pokud bychom věděli, že proměnná x se realizuje jako jednotkový prvek, mohli bychom použít formuli ∀y∃z(y ·z = k ∧z ·y = k). To, že x se realizuje jako jednotkový prvek musíme vynutit vhodným rozšířením naší formule. Výslednou formuli pro vynucení existence inverzního prvku složíme ze dvou částí: • formule pro existenci jednotkového prvku, • formule pro existenci inverzního prvku za předpokladu, že x je jednotkový prvek. Proto výsledná formule pro existenci inverzního prvku je ϕ2 = ∃x(∀y(x · y = x ∧ y · x = x) ∧ ∀y∃z(y · z = x ∧ z · y = x)). Všimneme si, že existenční kvantifikátor musí být před celou složenou formulí, aby se x vskutku v celé formuli realizovalo jako jednotkový prvek. Tedy výsledná formule zajišťující všechny vlastnosti grupy je ϕ1 ∧ ϕ2. KAPITOLA 6. SÉMANTIKA PREDIKÁTOVÉ LOGIKY I 56 Příklad 6.3 Mějme jazyk L = {∼} s rovností, kde ∼ je binární predikátový symbol. Dejte příklad uzavřené formule ϕ predikátového počtu jazyka L takové, že pro libovolnou realizaci M jazyka L platí M |= ϕ právě tehdy, když a) ∼M je relace ekvivalence na M b) ∼M je relace uspořádání na M Řešení a) ∀x(x ∼ x) ∧ ∀x∀y∀z((x ∼ y ∧ y ∼ z → x ∼ z) ∧ ∀x∀y(x ∼ y → y ∼ x) b) ∀x(x ∼ x) ∧ ∀x∀y∀z((x ∼ y ∧ y ∼ z → x ∼ z) ∧ ∀x∀y((x ∼ y ∧ y ∼ x) → x = y) Příklad 6.4 Mějme jazyk L = {<} s rovností, kde < je binární predikátový symbol. Uvažme tři realizace N, Z, Q jazyka L s nosiči N, Z, Q (množiny přirozených, celých a racionálních čísel), které interpretují symbol < jako standardní ostré uspořádání na příslušné množině čísel. Dejte příklad uzavřené formule ϕ predikátového počtu jazyka L takové, že a) N |= ϕ, Z |= ϕ, Q |= ϕ, b) N |= ϕ, Z |= ϕ, Q |= ϕ, c) N |= ϕ, Z |= ϕ, Q |= ϕ. Řešení a) ϕ ≡ ∃x∀y(x = y ∨ x < y) (tedy existuje nejmenší prvek), b) ϕ ≡ ∀x∃y(y < x ∧ ∀z(z < y ∨ x < z ∨ z = y ∨ z = x)) (neexistuje nejmenší prvek, a zároveň ke každému prvku existuje prvek bezprostředně menší- mezi tyto dva už není možné zařadit další prvek), c) ϕ ≡ ∀x∀y(x < y → ∃z(x < z ∧ z < y)) (mezi každé dva prvky lze zařadit další). 1 KAPITOLA 6. SÉMANTIKA PREDIKÁTOVÉ LOGIKY I 57 Příklad 6.5 Mějme jazyk L = {·} s rovností, kde · je binární funkční symbol. Uvažme tři realizace Z, Q, R s nosiči Z, Q, R (množiny celých, racionálních a reálných čísel), které intepretují symbol · jako standardní násobení čísel. Dejte příklad uzavřené formule ϕ predikátového počtu jazyka L takové, že Q |= ϕ, R |= ϕ. Příklad 6.6 Nechť L = {+, ∗} je jazyk s rovností, kde + a ∗ jsou binární funkční symboly. Dále nechť M je realizace tohoto jazyka, kde univerzum je množina přirozených čísel s nulou a +M a ∗M jsou standardní operace sčítání a násobení. Zadejte formuli ϕ(x, y) se dvěma volnými proměnnými x a y takovou, že pro libovolné ohodnocení e platí M |= ϕ[e], právě když e(x) · e(y) je dělitelné druhou mocninou nějakého prvočísla. Příklad 6.7 Nechť L je jazyk s rovností a se dvěma binárními funkčními symboly + a ∗. Dále nechť R = (R≥0, +R≥0 , ∗R≥0 ) a Q = (Q≥0, +Q≥0 , ∗Q≥0 ) jsou dvě realizace tohoto jazyka, které mají za nosič nezáporná reálná, resp. nezáporná racionální čísla a kde funkční symboly + a ∗ jsou realizovány standardní operací sčítání a násobení na příslušných množinách. Zadejte formuli ϕ v jazyce L takovou, že R |= ϕ a Q |= ϕ. Příklad 6.8 Nechť L je jazyk s rovností a dvěma binárními funkčními symboly + a ∗. Označme R = (R, +R, ∗R) realizaci tohoto jazyka s reálnými čísly jako nosičem, kde operace + a ∗ jsou realizovány standardními operacemi sčítání a násobení na množině reálných čísel. Zadejte formule ϕ1, ϕ2 a ϕ3 s volnou proměnnou x, příp. y takové, že pro libovolné ohodnocení e platí: a) R |= ϕ1(x)[e], právě když e(x) = 0 b) R |= ϕ2(x)[e], právě když 0 ≤ e(x) c) R |= ϕ3(x, y)[e], právě když e(x) ≤ e(y) kde ≤ je standardní uspořádání reálných čísel. Příklad 6.9 Mějme jazyk L = {f, ≤, D} s rovností, kde f je unární funkční symbol, ≤ je binární predikátový symbol a D je binární funkční symbol. 1 také lze použít formuli ¬ψ1 ∧ ¬ψ2 kde ψ1 je formule z 1. a ψ2 je formule z 2. KAPITOLA 6. SÉMANTIKA PREDIKÁTOVÉ LOGIKY I 58 Mějme realizaci M, jejímž nosičem jsou reálná čísla, fM je libovolná funkce nad reálnými čísly, ≤M je standardní uspořádání a DM přiřadí dvěma reálným číslům jejich rozdíl v absolutní hodnotě, tedy DM(a, b) = |a − b|. Zadejte formuli ϕ v jazyku L s volnou proměnnou l tak, že pro libovolné ohodnocení e platí M |= ϕ[e] právě když e(l) = lim x→∞ fM(x) Pro připomenutí: Říkáme, že l ∈ R je limita funkce f v nekonečnu, pokud pro libovolné kladné ε existuje kladné A takové, že pro všechna x > A platí |g(x) − l| < ε. Příklad 6.10 Mějme jazyk L = {P} s rovností, kde P je binární predikátový symbol. Dále mějme formule ϕ ≡ ∀x ∃y ∃z (¬(y = z) ∧ P(x, y) ∧ P(x, z)) ψ ≡ ∃x ∀y ∀z ((P(y, x) ∧ P(z, x)) → y = z) Zadejte realizaci M jazyka L takovou, že • M |= ϕ a zároveň M |= ψ, • M |= ϕ a zároveň M |= ψ. Řešení • ({a, b}, PM = {(x, y) | x, y ∈ M}), • ({a, b, c}, PM = {(a, a), (a, b), (b, a), (b, c), (c, a), (c, b)}). Příklad 6.11 Mějme jazyk L = {S, N} s rovností, kde S a N jsou binární funkční symboly. Mějme realizaci M, jejíž nosič je množina N (přirozená čísla bez nuly), SM je standardní sčítání na množině N a NM je standardní násobení na množině N. Zadejte formuli ϕ v jazyku L s volnou proměnnou x tak, že pro libovolné ohodnocení e platí M |= ϕ[e] právě když e(x) je prvočíslo. Pro připomenutí: Říkáme, že přirozené číslo x je prvočíslo, pokud je dělitelné právě dvěma čísly: x a 1. KAPITOLA 6. SÉMANTIKA PREDIKÁTOVÉ LOGIKY I 59 Příklad 6.12 Mějme jazyk L = {S, N} s rovností, kde S a N jsou binární funkční symboly. Mějme realizaci M, jejíž nosič je množina N (přirozená čísla bez nuly), SM je standardní sčítání na množině N a NM je standardní násobení na množině N. Zadejte formuli ϕ v jazyku L s volnou proměnnou x tak, že pro libovolné ohodnocení e platí M |= ϕ[e] právě když e(x) je násobek čísla 3. Příklad 6.13 Mějme jazyk L = {f, ≤, D} s rovností, kde f je unární funkční symbol, ≤ je binární predikátový symbol a D je binární funkční symbol. Mějme realizaci M, jejíž nosič jsou reálná čísla, fM je libovolná funkce nad reálnými čísly, ≤M je standardní uspořádání a DM přiřadí dvěma reálným číslům jejich rozdíl v absolutní hodnotě, tedy DM(a, b) = |a − b|. Zadejte formuli ϕ v jazyce L takovou, že M |= ϕ právě když fM je spojitá funkce Pro připomenutí: Reálná funkce je spojitá, pokud je spojitá v každém bodě x ∈ R. Reálná funkce f je spojitá v bodě c ∈ R, pokud limx→c f(x) = f(c), tedy pokud pro každé > 0 existuje δ > 0 takové, že pro libovolný bod x, který splňuje |x − c| < δ, platí |f(x) − f(c)| < . Příklad 6.14 Mějme jazyk L = { } s rovností, kde je binární funkční symbol. Mějme dále realizaci M jazyka L, jejímž nosičem je 2N (tj. množina všech podmnožin přirozených čísel) a kde M je množinový rozdíl. Zadejte formuli ϕ v jazyce L s jednou volnou proměnnou x takovou, že pro libovolné ohodnocení e platí M |= ϕ[e] právě když e(x) je jednoprvková podmnožina množiny N. Pro připomenutí uvádíme stručnou ilustraci chování operace M: {5, 6} M {3, 5, 7} = {6}, {1, 3} M {1, 2, 3} = ∅. Příklad 6.15 Mějme jazyk L = {+, ∗} s rovností, kde + a ∗ jsou binární funkční symboly. Mějme dále realizaci M jazyka L, jejímž nosičem je množina všech kladných celých čísel Z>0 a kde + a ∗ se realizují jako standardní KAPITOLA 6. SÉMANTIKA PREDIKÁTOVÉ LOGIKY I 60 sčítání, resp. násobení na této množině. Zadejte formuli ϕ jazyka L se dvěma volnými proměnnými x a y takovou, že pro libovolné ohodnocení e platí: M |= ϕ[e] ⇔ e(x) = max{k | k = 2l pro nějaké l ≥ 0 a zároveň k ≤ e(y)}. (Tj. e(x) musí být největší mocnina dvou menší nebo rovna e(y).) Příklad 6.16 Mějme jazyk L = {+, N} s rovností, kde + je binární funkční symbol a N je unární predikátový symbol. Mějme dále realizaci M jazyka L, jejímž nosičem je množina R≥0 všech nezáporných reálných čísel, + se realizuje jako standardní sčítání a NM obsahuje právě všechna celá čísla obsažená v R≥0. Zadejte formuli ϕ jazyka L se dvěmi volnými proměnnými x a y takovou, že pro libovolné ohodnocení e platí: M |= ϕ[e] ⇔ e(x) = e(y) . (Tj. e(x) je celá část e(y) – největší celé číslo menší nebo rovno e(y).) Příklad 6.17 Mějme jazyk L = {+, ∗} s rovností, kde + a ∗ jsou binární funkční symboly. Mějme dále realizaci M jazyka L, jejímž nosičem je množina N0 všech přirozených čísel s nulou, + se realizuje jako standardní sčítání a ∗ se realizuje jako standardní násobení. Zadejte formuli ϕ jazyka L se třemi volnými proměnnými x, y a z takovou, že pro libovolné ohodnocení e platí: M |= ϕ[e] ⇔ e(z) = 0 a e(x) je zbytek po dělení čísla e(y) číslem e(z) . Neformálně popište význam formule. Příklad 6.18 Mějme jazyk L = {≤} s rovností, kde ≤ je binární predikátový symbol. Mějme dále realizaci M jazyka L, jejímž nosičem je množina 2N všech podmnožin přirozených čísel a kde ≤M je standardní množinová inkluze. Zadejte formuli ϕ jazyka L se dvěma volnými proměnnými x a y takovou, že pro libovolné ohodnocení e platí: M |= ϕ[e] ⇔ množiny e(x) a e(y) mají neprázdný průnik. Neformálně popište význam své formule. Příklad 6.19 Mějme jazyk L = {+, ∗} s rovností, kde + a ∗ jsou binární funkční symboly. Mějme dále realizaci M jazyka L, jejímž nosičem je množina N0 všech přirozených čísel s nulou, + se realizuje jako standardní sčítání KAPITOLA 6. SÉMANTIKA PREDIKÁTOVÉ LOGIKY I 61 a ∗ se realizuje jako standardní násobení. Zadejte formuli ϕ jazyka L se třemi volnými proměnnými x, y a z takovou, že pro libovolné ohodnocení e platí: M |= ϕ[e] ⇔ e(x) = 0 a e(x) je největší společný dělitel čísel e(y) a e(z). Neformálně popište význam své formule. Příklad 6.20 Nechť ϕ je formule predikátového počtu jazyka L taková, že x je jediná volná proměnná ve ϕ. Rozhodněte, zda pro libovolnou realizaci M jazyka L a libovolnou proměnnou y substituovatelnou za x ve ϕ platí a) M |= ϕ → (ϕ(x/y)), b) M |= ϕ → ∃y (ϕ(x/y)). Kapitola 7 Sémantika predikátové logiky II V této kapitole uvedeme abstraktnější a také složitější příklady týkající se sémantiky predikátové logiky. Příklad 7.1 Rozhodněte, zda platí následující tvrzení: Mějme nějaký jazyk L, realizaci M jazyka L a formuli ϕ predikátového počtu jazyka L. Pak M |= ϕ právě tehdy, když M |= ¬ϕ Řešení Implikace "zleva doprava"platí. Dokážeme tedy následující tvrzení: Tvrzení 7.1 Jestliže M |= ϕ, pak M |= ¬ϕ. Důkaz Předpokládejme, že M |= ϕ. Pak (z definice) pro každé ohodnocení e platí M |= ϕ[e]. Nosič M je neprázdný (z definice realizace) a tedy existuje alespoň jedno ohodnocení e takové, že M |= ϕ[e]. Pak ale M |= ¬ϕ[e] a tedy M |= ¬ϕ. Implikace "zprava doleva"neplatí. Dokážeme tedy: Tvrzení 7.2 Existují jazyk L, realizace M jazyka L a formule ϕ predikátového počtu jazyka L takové, že M |= ϕ a zároveň M |= ¬ϕ. Důkaz Položme L = {P} kde P je unární predikátový symbol. Realizaci M definujeme následovně: nosič M = {a, b} a PM = {a} (PM je unární relace). Konečně položme ϕ = P(x). Nyní nechť e je ohodnocení takové, že e(x) = a. Pak M |= P(x)[e], protože e(x) = a ∈ PM a tedy M |= ¬P(x)[e]. Z toho plyne, že M |= ¬P(x). 62 KAPITOLA 7. SÉMANTIKA PREDIKÁTOVÉ LOGIKY II 63 Dále nechť e je ohodnocení takové, že e(x) = b. Pak M |= P(x)[e] a tedy M |= P(x). Celkem tedy M |= ¬P(x) a zároveň M |= P(x), což bylo dokázat. Příklad 7.2 Rozhodněte, zda platí následující tvrzení: Mějme jazyk L, realizaci M jazyka L a uzavřenou formuli ϕ predikátového počtu jazyka L. Pak M |= ϕ právě tehdy, když M |= ¬ϕ Řešení Tvrzení platí. Nejprve ovšem dokážeme následující pomocné tvr- zení. Tvrzení 7.3 Je-li t term jazyka L a e1, e2 jsou ohodnocení taková, že e1(x) = e2(x) platí pro každou proměnnou x vyskytující se v t, pak t[e1] = t[e2]. Důkaz Tvrzení dokážeme metaindukcí vzhledem k délce vytvořující posloupnosti pro t (t.j. strukturální indukcí). • Je-li t = x proměnná, pak t[e1] = x[e1] = e1(x) = e2(x) = x[e2] = t[e2] • Je li t = f(t1, . . . , tn) kde f je n-ární funkční symbol jazyka L a t1, . . . , tn jsou termy, pak t[e1] = f(t1, . . . , tn)[e1] = fM (t1[e1], . . . , tn[e1]) = fM (t1[e2], . . . , tn[e2]) = f(t1, . . . , tn)[e2] = t[e2], kde druhá rovnost plyne z indukčního předpokladu. Nyní si uvědomme, že tvrzení tvaru „pro všechny uzavřené formule ϕ platí. . . “, nelze přímo dokázat strukturální indukcí, neboť uzavřené formule vznikají z neuzavřených přidáním kvantifikátorů. Tvrzení ze zadání příkladu je tudíž příliš slabé, protože neříká nic o neuzavřených formulích. Musíme tedy dokázat následující silnější tvrzení. Tvrzení 7.4 Je-li ϕ formule predikátového počtu jazyka L a e1, e2 libovolná ohodnocení taková, že e1(x) = e2(x) pro každou proměnnou x volnou ve ϕ, pak platí: M |= ϕ[e1], právě tehdy když M |= ϕ[e2]. KAPITOLA 7. SÉMANTIKA PREDIKÁTOVÉ LOGIKY II 64 Důkaz Tvrzení dokážeme metaindukcí vzhledem k délce vytvořující posloupnosti pro ϕ. • Je-li ϕ ≡ P(t1, . . . , tn), kde P je n-ární predikátový symbol a t1, . . . , tn jsou termy, pak M |= ϕ[e1] ⇔ (t1[e1], . . . , tn[e1]) ∈ PM ⇔ (t1[e2], . . . , tn[e2]) ∈ PM ⇔ M |= ϕ[e2], kde druhá ekvivalence plyne z Tvrzení 7.3 a z toho, že ve ϕ jsou všechny proměnné volné, tedy e1 a e2 se shodují na všech proměnných majících výskyt ve ϕ. • Je-li L jazyk s rovností a ϕ ≡ t1 = t2, kde t1,t2 jsou termy, pak podobně jako v předchozím bodě máme M |= ϕ[e1] ⇔ t1[e1] = t2[e1] ⇔ t1[e2] = t2[e2] ⇔ M |= ϕ[e2], • Je-li ϕ ≡ ¬ψ, pak M |= ϕ[e1] ⇔ M |= ψ[e1] ⇔ M |= ψ[e2] ⇔ M |= ϕ[e2], kde druhá ekvivalence plyne z indukčního předpokladu a z toho, že libovolná proměnná je volná v ψ tehdy a jen tehdy, když je volná ve ϕ. • Je-li ϕ ≡ ψ1 → ψ2, pak M |= ϕ[e1] ⇔ buď M |= ψ2[e1] nebo M |= ψ1[e1] ⇔ buď M |= ψ2[e2] nebo M |= ψ1[e2] ⇔ M |= ϕ[e2], kde druhá ekvivalence plyne z indukčního předpokladu a z toho, že libovolná proměnná je volná v ψ1 nebo v ψ2 tehdy a jen tehdy, když je volná ve ϕ. KAPITOLA 7. SÉMANTIKA PREDIKÁTOVÉ LOGIKY II 65 • Je-li ϕ ≡ ∀y ψ, pak M |= ϕ[e1] ⇔ pro každé a ∈ M platí M |= ψ[e1(y/a)] ⇔ pro každé a ∈ M platí M |= ψ[e2(y/a)] ⇔ M |= ϕ[e2], kde druhou ekvivalenci lze zdůvodnit takto: Z definice plyne, že pokud je libovolná proměnná x volná v ψ, pak buď x je y nebo x je volná ve ϕ. Z toho plyne, že pro libovolnou proměnnou x, která je volná v ψ a pro libovolné a ∈ M platí, že e1(y/a)(x) = e2(y/a)(x). Požadovaná ekvivalence potom plyne z indukčního předpokladu. Nyní dokážeme tvrzení ze zadání příkladu. ⇒ : Tento směr byl v obecnější podobě dokázán v Příkladu 7.1. ⇐ : Předpokládejme, že M |= ϕ. Potom existuje ohodnocení e takové, že M |= ϕ[e]. Protože žádná proměnná není volná ve ϕ, dostaneme z předchozího tvrzení, že M |= ϕ[e ] a tedy M |= ¬ϕ[e ] pro libovolné ohodnocení e . Z definice plyne, že M |= ¬ϕ. Příklad 7.3 Mějme jazyk L = {P, Q} bez rovnosti, kde P a Q jsou unární predikátové symboly. Rozhodněte a dokažte, zda pro každou realizaci M jazyka L platí M |= ∀x (P(x) ↔ Q(x)) → (∀x P(x) ↔ ∀x Q(x)) Řešení [Neformálně] Platí. Mějme libovolnou realizaci M a ohodnocení e takové, že M |= ∀x (P(x) ↔ Q(x))[e]. Pro každé a ∈ M tedy platí M |= P(x) ↔ Q(x)[e(x/a)]. Tedy pro každé a ∈ M platí e[x/a](x) ∈ PM, právě když e[x/a](x) ∈ QM, a tedy platí a ∈ PM, právě když a ∈ QM (protože e[x/a](x) je a). Předpokládejme, že M |= ∀x P(x)[e]. Obdobnou argumentací jako výše dostáváme, že pro všechna a ∈ M platí a ∈ PM. Dle výše dokázaného to znamená, že pro všechna a ∈ M platí a ∈ QM. tedy M |= ∀x Q(x)[e]. Symetricky se ukáže i platnost opačné implikace, tedy celkově dostáváme M |= (∀x P(x) ↔ ∀x Q(x))[e]. Řešení [Formálně] Mějme libovolnou realizaci M a libovolné ohodnocení e. Výraz M |= ∀x (P(x) ↔ Q(x)) → (∀x P(x) ↔ ∀x Q(x)) [e]. KAPITOLA 7. SÉMANTIKA PREDIKÁTOVÉ LOGIKY II 66 z definice platí pokud M |= ∀x (P(x) ↔ Q(x)) [e] nebo M |= ∀x P(x) ↔ ∀x Q(x) [e] Předpokládejme, že M |= ∀x (P(x) ↔ Q(x)) [e], potřebujeme dokázat, že M |= ∀x P(x) ↔ ∀x Q(x) [e] což dle definice platí, pokud M |= ∀x P(x)[e], právě když M |= ∀x Q(x) [e]. Úpravou předpokladu dle definice máme M |= (P(x) ↔ Q(x)) [e(x/a)] pro všechna a ∈ M, a tedy pro každé a ∈ M platí M |= P(x) [e(x/a)], právě když M |= Q(x) [e(x/a)]. (7.1) Nyní můžeme dokázat požadovanou ekvivalenci. Předpokládejme její levou stranu, tedy, že platí M |= ∀x P(x) [e], to je z definice právě když pro libovolné a ∈ M platí M |= P(x) [e(x/a)] což s pomocí tvrzení (1) platí, právě když pro libovolné a ∈ M M |= Q(x) [e(x/a)] což je z definice právě když M |= ∀x Q(x) [e]. KAPITOLA 7. SÉMANTIKA PREDIKÁTOVÉ LOGIKY II 67 Dostali jsme pravou stranu dokazované ekvivalence. Celkově tedy pro zvolené e platí M |= ∀x (P(x) ↔ Q(x)) → (∀x P(x) ↔ ∀x Q(x)) [e]. Protože jsme zvolili e libovolně, dostáváme M |= ∀x (P(x) ↔ Q(x)) → (∀x P(x) ↔ ∀x Q(x)). Příklad 7.4 Nechť L je jazyk bez rovnosti s jedním unárním predikátovým symbolem P. Rozhodněte a dokažte, zda pro každou realizaci M jazyka L platí M |= P(x) → ∀xP(x) Příklad 7.5 Nechť L = {f, g} je jazyk s rovností, kde f a g jsou unární funkční symboly. Rozhodněte a dokažte, zda pro libovolnou realizaci M jazyka L platí M |= ∀y (f(x) = y → g(y) = x) → g(f(x)) = x. Příklad 7.6 Mějme jazyk L s rovností a unárním predikátovým symbolem P. Rozhodněte a dokažte, zda je následující formule pravdivá v každé realizaci jazyka L: (∀x P(x) ↔ ∃x P(x)) → ∀x ∀y (x = y) Příklad 7.7 Nechť ϕ je formule predikátového počtu jazyka L taková, že x je jediná volná proměnná ve ϕ. Rozhodněte, zda pro libovolnou realizaci M jazyka L a libovolnou proměnnou y substituovatelnou za x ve ϕ platí M |= ϕ → ϕ(x/y). Řešení Odpověď: Tvrzení neplatí! Zdůvodnění: Nechť L = {P} kde P je unární predikátový symbol. Definujme realizaci M takto: • M = {a, b} • PM = {a} Nyní uvažme ohodnocení e takové, že e(x) = a a e(y) = b a formuli ϕ ≡ P(x). Zřejmě M |= (P(x) → P(x)(x/y))[e], protože e(x) = a ∈ PM a e(y) = b ∈ PM. Poznámka: M |= ϕ → ∃yϕ(x/y) platí pro libovolnou realizaci jazyka L. KAPITOLA 7. SÉMANTIKA PREDIKÁTOVÉ LOGIKY II 68 Příklad 7.8 Rozhodněte, zda existuje jazyk L s rovností a jeho realizace M taková, že pro všechny formule ϕ predikátového počtu jazyka L platí M |= ϕ. Své tvrzení zdůvodněte. Řešení Neexistuje protože ∀x(x = x) je pravdivá pro libovolnou realizaci jazyka L. Příklad 7.9 Nechť L je jazyk bez rovnosti a s jedním binárním predikátovým symbolem P. Rozhodněte, zda pro libovolnou realizaci M jazyka L existuje ohodnocení e takové, že M |= ( (∃xP(x, y)) → ∃zP(x, z) )[e] Své tvrzení zdůvodněte. Řešení Tvrzení platí, mohou nastat 2 případy: • PM = ∅, pak uvedená formule je triviálně pravdivá pro libovolné ohodnocení, protože není pravdivý předpoklad implikace, tedy M |= ∃xP(x, y)[e] pro žádné e a tedy M |= ( (∃xP(x, y)) → ∃zP(x, z) )[e]. • Existuje a, b ∈ M, t.ž. (a, b) ∈ PM. Zvolíme e tak, aby platilo e(x) = a. Je zřejmé, že M |= ∃zP(x, z)[e] a tím pádem i M |= ( (∃xP(x, y)) → ∃zP(x, z) )[e]. Příklad 7.10 Nechť L je prázdný jazyk s rovností. Rozhodněte a dokažte, zda existuje formule ϕ jazyka L taková, že pro každou realizaci M jazyka L existují ohodnocení e, e taková, že M |= ϕ[e] a zároveň M |= ϕ[e ]. Řešení Neexistuje. Předpokládejme, že existuje taková formule ϕ. Vezměme realizaci M s jednoprvkovým nosičem M = {a}. V této realizaci existuje jen jedno ohodnocení e (toto ohodnocení přiřadí všem proměnným prvek a). Z definice nemůže současně platit M |= ϕ[e] a M |= ϕ[e], tedy docházíme ke sporu s podmínkami, které má ϕ splňovat. KAPITOLA 7. SÉMANTIKA PREDIKÁTOVÉ LOGIKY II 69 Příklad 7.11 Mějme jazyk L = {R} s rovností, kde R je binární predikátový symbol. Uvažme následující formule predikátové logiky jazyka L: ϕ1 = ∃x (∀y ¬R(y, x)) ∧ ∀z(∀y ¬R(y, z) → z = x) ϕ2 = ∀x∀y∀z ((R(y, x) ∧ R(z, x)) → y = z) ϕ3 = ∀x∀y R(x, y) → ∃z(z = y ∧ R(x, z)) ϕ4 = ∀x∀y∀z∀u (R(x, y) ∧ R(x, z) ∧ R(x, u)) → (y = z ∨ y = u ∨ z = u) Nalezněte realizaci M jazyka L jejíž nosič má alespoň 6 prvků a pro kterou platí M |= ϕ1 ∧ϕ2 ∧ϕ3 ∧ϕ4. Svou volbu realizace M zdůvodněte.1 Dokažte, že neexistuje realizace M jejíž nosič by měl 22013 prvků a pro kterou by platilo M |= ϕ1 ∧ ϕ2 ∧ ϕ3 ∧ ϕ4. Řešení Nejprve si uvědomme, že každou realizaci M jazyka L je možné neformálně vnímat jako (potenciálně nekonečný) graf s množinou vrcholů M a množinou hran RM. Intuitivně, formule ϕ1 říká, že v tomto grafu existuje právě jeden vrchol do kterého nevede žádná hrana. Formule ϕ2 říká, že do každého vrcholu vede nejvýše jedna hrana. Formule ϕ3 vynucuje, že žádný vrchol nemá přesně jednoho následníka a formule ϕ4 říká, že každý vrchol má nejvýše dva následníky. Konjunkci těchto formulí splňuje zejména každý binární strom, pokud tedy chceme realizaci s alespoň 6 prvky, lze uvážit realizaci M s nosičem M = {1, 2, 3, 4, 5, 6, 7}, v níž RM = {(1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7)}. Pro druhou část zadání si stačí uvědomit, že každá realizace s konečným nosičem, ve které je pravdivá konjunkce uvedených formulí, má nosič liché mohutnosti. Vskutku, každá taková realizace M je vlastně orientovaný graf, jehož každá komponenta slabé souvislosti2 má jeden ze dvou následujících tvarů: a) Binární strom. Přitom M má právě jednu takovou slabě souvislou komponentu, neboť ϕ1 vynucuje, že v grafu je právě jeden vrchol do 1 Zdůvodnění nemusí mít formu zcela formálního důkazu, ale musí být pochopitelné a přesvědčivé. Ideální bude, pokud v přirozeném jazyce co nejlépe popíšete význam formulí ϕ1-ϕ4, tj. popíšete vlastnosti, které realizace musí mít, aby v ní daná formule byla pravdivá, a poté ověříte, že Vaše realizace tyto vlastnosti má. 2 Množina vrcholů C daného orientovaného grafu je slabě souvislá, pokud pro libovolné dva vrcholy u, v ∈ C platí, že pokud zapomeneme orientaci jednotlivých hran, pak u je dosažitelná z v. Komponenta slabé souvislosti je pak každá maximální (vzhledem k inkluzi) slabě souvislá množina vrcholů. KAPITOLA 7. SÉMANTIKA PREDIKÁTOVÉ LOGIKY II 70 kterého nevede žádná hrana: tento vrchol je nutně binárního stromu (formule ϕ2 vynucuje, že jde skutečně o strom a formule ϕ3 a ϕ4 vynucují binárnost). b) Komponenta, ve které do každého vrcholu vede jedna hrana. Tvrdíme, že taková komponenta má (velmi intuitivně) tvar kružnice, na jejímž každém vrcholu je „přivěšený“ binární strom, tj. například komponenta s vrcholy A, B, C, 1, 2, 3, 4, 5 a hranami (A, B), (B, C), (C, A), (A, 1), (B, 2), (C, 3), (3, 4), (4, 5). Formalizujte toto intuitivní tvrzení! Snadno nahlédneme, že jediná komponenta typu a) (binární strom) má lichý počet vrcholů, zatímco libovolná komponenta typu b) má sudý počet vrcholů (několik stromů s lichým počtem vrcholů a ke každému stromu příslušející vrchol na kružnici, celkem tedy sudý počet). Počet vrcholů grafu je tedy lichý a nemůže být roven číslu 22013. Příklad 7.12 Mějme jazyk L = {·} s rovností, kde · je binární funkční symbol. Mějme formuli ϕ ≡ ∀x ∀y (x · y = y · x). Rozhodněte a dokažte, zda a) pro každou realizaci M jazyka L platí M |= ϕ, b) existuje realizace M jazyka L taková, že M |= ϕ. Příklad 7.13 Mějme jazyk L = {P} bez rovnosti, kde P je binární predikátový symbol. Rozhodněte a dokažte, zda pro libovolnou realizaci M jazyka L platí následující tvrzení: a) M |= ∀x ∀z (P(x, z) → ∃y P(x, y)) b) M |= (∀x ∃y P(x, y)) → (∃y ∀x P(x, y)) c) M |= (∃y ∀x P(x, y)) → (∀x ∃y P(x, y)) Kapitola 8 Teorie predikátové logiky V předchozích kapitolách jsme zavedli pojem realizace, na který nahlížíme jako na svět, o kterém se pomocí predikátových formulí vyjadřujeme. Vzhledem k tomuto světu definujeme pravdivost formulí. V této kapitole se budeme zabývat tím, jak pomocí formulí vymezit nějaký soubor světů (tj. realizací) pro které platí určité zákonitosti. Využijeme k tomu soubory formulí – tzv. teorie. Definice 8.1 Buď L jazyk (příp. jazyk s rovností). • Teorie (s jazykem L) je soubor T formulí predikátového počtu jazyka L. Prvky T se nazývají axiomy teorie T. • Realizace M jazyka L je model teorie T, psáno M |= T, jestliže M |= ϕ pro každé ϕ z T. Takže teorie je jednoduše soubor formulí. Je důležité si uvědomit, že tento soubor může být nekonečný. Definici si procvičíme na dvou jednoduchých příkladech. Příklad 8.1 Nechť L = {P} je jazyk s rovností, kde P je binární predikátový symbol a a je nulární funkční symbol. Zadejte nějaký model k následující teorii T v jazyce L. T = { ∀x P(x, x), ∀x ∀y ((P(x, y) → P(y, x)), ∀x ∀y ∀z ((P(x, y) ∧ P(y, z)) → P(x, z)) } 71 KAPITOLA 8. TEORIE PREDIKÁTOVÉ LOGIKY 72 Řešení První formule vynucuje, aby realizace PM predikátového symbolu P v každém modelu M teorie T byla reflexivní. Tímto vlastně vyloučíme všechny realizace, které nemají reflexivní PM. Podobně druhá formule vynucuje symetrii a třetí tranzitivitu. Tím pádem pro libovolný model M teorie T platí, že PM je současně reflexivní, symetrická a tranzitivní. Modelem tedy mohou být například realizace ({a, b, c}, PM = {(x, x) | x ∈ M}) anebo (N, PM = {(x, y) | x2 = y2}). Příklad 8.2 Mějme jazyk L = ∅ s rovností. Dejte příklad teorie T s jazykem L takové, že její modely jsou právě realizace s nekonečným nosičem. Řešení Formule ∃x∃y¬(x = y) je pravdivá pouze v realizacích s alespoň dvouprvkovým nosičem. Podobně formule ∃x∃y∃z(¬(x = y) ∧ ¬(y = z) ∧ ¬(x = z)) je pravdivá pouze v realizacích s alespoň tříprvkovým nosičem. Obecně pro n ∈ {2, 3, . . .} formule ϕn ≡ ∃ x1 · · · ∃ xn 1≤i,j≤n i =j ¬(xi = xj) je pravdivá právě v realizacích s alespoň n-prvkovým nosičem. Hledaná teorie T je tedy {ϕn | n ∈ {2, 3, . . .}}. Vskutku, libovolná realizace M s nekonečným nosičem zřejmě splňuje M |= ϕn pro libovolné n (neboť zřejmě má alespoň n-prvkový nosič). Na druhou stranu žádná realizace M, která je modelem T, nemůže mít konečný nosič, neboť kdyby měla dejme tomu n-prvkový nosič (pro nějaké n ∈ N), nemohlo by platit M |= ϕn+1. Metaekvivalence požadovaná v zadání je tedy splněna. Nekonečné teorie mají striktně vyšší vyjadřovací sílu jako konečné teorie. V předchozím příkladě jsme použili nekonečnou teorii. Pomocí konečné teorie příklad vyřešit nelze. Formální argument poskytneme až v kapitole 10 pomocí věty o kompaktnosti v Příkladu 10.5. Definice 8.2 Buď L jazyk (příp. jazyk s rovností). Teorie je splnitelná, jestliže má model. Příklad 8.3 Mějme jazyk L = {S} s rovností, kde S je unární funkční symbol. Dejte příklad splnitelné konečné teorie T s jazykem L takové, že všechny její modely mají nekonečný nosič. KAPITOLA 8. TEORIE PREDIKÁTOVÉ LOGIKY 73 Řešení Uvažme T = {∀x∀y(S(x) = S(y) → x = y), ∃y∀x¬(S(x) = y)}. Nejprve ukážeme, že teorie T nemá konečný model. Nechť M je model teorie T. Potom SM je injektivní funkce definovaná na M, která není surjektivní. Taková funkce ovšem nemůže existovat na konečném souboru, a proto M musí být nekonečný soubor. Nyní ukážeme, že T je splnitelná. Definujme realizaci M jazyka L takto: • M = N0 (přirozená čísla s nulou) • SM(n) = n + 1 pro n ∈ N0 Je zřejmé, že M |= T. Všimněte si, že zadání předchozího příkladu se od příkladu 8.2 liší (kromě jiného jazyka) v tom, že jsme nepožadovali, aby modely teorie byly právě realizace s nekonečným nosičem. Například realizace s nosičem N, ve které se S realizuje jako identita, není modelem teorie z řešení předchozího příkladu. Máme-li soubor světů, kterými se zabýváme, omezený na modely nějaké teorie, můžeme se bavit o tom, zda je nějaká formule v těchto světech pravdivá. Například si můžeme zadefinovat teorii monoidů T tím, že do ní zahrneme formuli vynucující asociativitu a existenci jednotkového prvku, tedy T = {∀x∀y∀z ((x · y) · z = x · (y · z)), ∃x∀y (x · y = y ∧ y · x = y)}. Tím pádem se budeme pohybovat jen ve světech (tj. realizacích), které jsou monoidy. Dále nás může zajímat, zda platí, že v každém monoidu existuje nejvýše jeden jednotkový prvek. Tedy se budeme ptát, zda je formule ∀x∀y∀z((x · z = z ∧ z · x = z ∧ y · z = z ∧ z · y = z) → x = y) pravdivá v každém modelu teorie T. Definice 8.3 Buď L jazyk (příp. jazyk s rovností). Formule ϕ je sémantickým důsledkem teorie T, psáno T |= ϕ, jestliže ϕ je pravdivá v každém modelu teorie T. Příklad 8.4 Nechť ϕ ≡ ∀x¬(S(x) = x) a nechť T je teorie z řešení Příkladu 8.3. Rozhodněte, zda platí T |= ϕ. KAPITOLA 8. TEORIE PREDIKÁTOVÉ LOGIKY 74 Řešení Odpověď: Neplatí! Zdůvodnění: Definujme realizaci M jazyka L takto: • M = N0 • SM(0) = 0 a SM(i) = i + 1 pro i ≥ 1 Realizace M je zřejmě modelem T a zároveň M |= ϕ. Příklad 8.5 Nechť T je konečná teorie s jazykem L. Dokažte, že existuje konečná teorie T s jazykem L taková, že M |= T právě tehdy, když M |= T pro libovolnou realizaci M jazyka L. Řešení Nejprve předpokládejme, že T = {ϕ1, . . . , ϕn} kde ϕ1, . . . , ϕn jsou uzavřené formule. Uvažme T = { n i=1 ¬ϕi}. Pro libovolnou realizaci M jazyka L platí M |= n i=1 ¬ϕi ⇔ M |= n i=1 ¬ϕi[e] pro každé ohodnocení e ⇔ M |= ¬ϕi[e] pro nějaké i a pro každé ohodnocení e ⇔ M |= ¬ϕi pro nějaké i ⇔ M |= ϕi pro nějaké i ⇔ M |= T kde druhá ekvivalence plyne z uzavřenosti formulí ϕ1, . . . , ϕn a Tvrzení 7.4 z řešení Příkladu 7.2 (M |= ¬ϕi[e] pro nějaké i a nějaké e a tudíž pro všechna e, protože ¬ϕi je uzavřená) a čtvrtá ekvivalence je přímo tvrzení dokázané v Příkladu 7.2. V obecném případě nemusí být formule z T uzavřené. Tuto situaci řeší následující jednoduché tvrzení. Tvrzení 8.4 Nechť ϕ je formule predikátového počtu jazyka L a nechť x je proměnná. Potom pro libovolnou realizaci M jazyka L platí M |= ∀xϕ právě tehdy, když M |= ϕ. Důkaz M |= ∀xϕ ⇔ M |= ∀xϕ[e] pro každé ohodnocení e ⇔ M |= ϕ[e(x/a)] pro každé ohodnocení e a pro každé a ∈ M ⇔ M |= ϕ[e] pro každé ohodnocení e ⇔ M |= ϕ, kde třetí metaekvivalenci je možné zdůvodnit takto: ⇒ plyne z toho, že každé ohodnocení e je možné psát ve tvaru e = e(x/e(x)), zatímco ⇐ plyne jednoduše z toho, že e(x/a) je jedno konkrétní ohodnocení. KAPITOLA 8. TEORIE PREDIKÁTOVÉ LOGIKY 75 Příklad 8.6 Nechť L = {∼, a} je jazyk s rovností, kde ∼ je binární predikátový symbol a a je nulární funkční symbol. Zadejte nějaký model k následující teorii T v jazyce L. T = { ∀x ∃y (x ∼ y), ∀x ∀y ((x ∼ y ∧ y ∼ x) → (x = a ∧ y = a)) } ∪{ ϕn | n ∈ N, n ≥ 2 }, kde ϕn ≡ ∃ x1 · · · ∃ xn 1≤i,j≤n i =j ¬(xi = xj) ∧ ¬(xi ∼ xj) Příklad 8.7 Mějme jazyk L = {P, ◦} bez rovnosti, kde ◦ je binární funkční symbol a P je unární predikátový symbol. Mějme dále teorii T s jazykem L: T = {P(x ◦ y) ↔ ¬(P(x) ∧ P(y))}. Zadejte nějaký term t jazyka L takový, že v libovolném modelu M teorie T platí M |= P(t). Své řešení stručně zdůvodněte. Příklad 8.8 Mějme jazyk L = {P, a, f} s rovností, kde P je binární predikátový symbol, a je nulární funkční symbol a f je unární funkční symbol. Dále mějme teorii T = { ∀x P(x, x), ∀x ∀y ((P(x, y) ∧ P(y, x)) → x = y), ∀x ∀y ∀z ((P(x, y) ∧ P(y, z)) → P(x, z)), ∀x (P(x, a) ↔ ¬(P(f(x), a))) } Zadejte realizaci M jazyka L takovou, že je modelem teorie T. Příklad 8.9 Mějme jazyk L = {f} s rovností, kde f je binární funkční symbol. Pro libovolné přirozené číslo n ≥ 2 uvažme následující formuli ψn: ψn ≡ ∃x1∃x2 . . . ∃x2n 1≤i 0, protože fi M(a) = b ∈ PM. Celkem tedy T |= P(fi(0)) a dle věty o korektnosti T P(fi(0)). Příklad 11.2 Popište kanonickou strukturu teorie T2 = {P(x)} s jazykem L. Řešení Kanonická struktura M2 teorie T2 se liší od struktury M1 z Příkladu 11.1 pouze v interpretaci predikátového symbolu P. Dokážeme, že PM2 = {fi(0) | i ≥ 0}. Dle definice kanonické struktury musíme ukázat, že T P(fi(0)) pro i ≥ 0. Důkaz může vypadat takto: T P(x) P(x) ∈ T T ∀xP(x) GEN T ∀xP(x) → P(x)(x/fi(0)) P4 T P(x/fi(0)) MP KAPITOLA 11. KANONICKÁ STRUKTURA 111 Příklad 11.3 Popište kanonickou strukturu teorie T3 = {∃x P(x)} s jazykem L. Řešení Kanonická struktura M3 teorie T3 se liší od struktur M1 a M2 z předchozích příkladů pouze v interpretaci predikátového symbolu P. Dokážeme, že PM3 = ∅. Ukážeme, že T |= P(fi(0)) pro i ≥ 0. Požadovaný výsledek pak plyne z věty o korektnosti. Nechť M je realizace jazyka L definovaná následovně: • M = {a, b} • fM(a) = a a fM (b) = b • 0M = b • PM = {a} Zřejmě M |= T, protože PM = ∅, a zřejmě také M |= P(fi(0)) pro i ≥ 0, protože fi M(0M) = b ∈ PM. Celkem tedy T |= P(fi(0)). Všimněte si, že kanonická struktura M3 není modelem T3. Příklad 11.4 Nechť L je jazyk bez rovnosti s jedním nulárním funkčním symbolem C, jedním unárním funkčním symbolem g a jedním unárním predikátovým symbolem Q. Popište realizaci M jazyka L takovou, že M je kanonickou strukturou teorie T = {Q(g(C))}. Zdůvodněte, že M je skutečně kanonická struktura teorie T. Příklad 11.5 Nechť L = {A, B, f, P} je jazyk bez rovnosti, kde A a B jsou nulární funkční symboly, f je unární funkční symbol a P je unární predikátový symbol. Popište realizaci M jazyka L takovou, že M je kanonickou strukturou teorie T = {P(A), ¬P(B)}. Zdůvodněte, že M je skutečně kanonická struktura teorie T. Příklad 11.6 Mějme jazyk L = {A, g, P} bez rovnosti, kde A je nulární funkční symbol, g je unární funkční symbol a P je unární predikátový symbol. Uvažme dále následující teorii T s jazykem L: T = {A, P(x) → P(g(g(x)))}. Popište kanonickou strukturu teorie T. Svůj výsledek zdůvodněte. KAPITOLA 11. KANONICKÁ STRUKTURA 112 Příklad 11.7 Mějme jazyk L = {P, f, A, B} s rovností, kde P je unární predikátový symbol, f je unární funkční symbol a A, B jsou nulární funkční symboly (konstanty). Uvažme následující teorii T tohoto jazyka: T = {P(A), ∀x(P(x) → P(f(x))), f(A) = f(f(B))}. Nechť M je kanonická struktura teorie T. a) Popište nosič realizace M. b) Popište realizaci PM predikátového symbolu P v kanonické struktuře M. Dokažte, že Vaše řešení obsahuje PM jako podmnožinu (tj. pro všechny prvky nosiče, které podle Vás nenáleží do PM formálně dokažte, že do PM vskutku patřit nemohou.) Řešení Nosičem realizace M je soubor M všech uzavřených termů jazyka L, tj. soubor M = {fi(A), fi(B) | i ≥ 0} (kde f0(A) = A a f0(B) = B). Tvrdíme, že PM = {fi(A) | i ≥ 0} ∪ {fj(B) | j ≥ 2}. Abychom dostáli zadání, musíme ukázat, že B ∈ PM a f(B) ∈ PM. Z definice kanonické struktury to znamená ukázat T P(B) a T P(f(B)), přičemž podle věty o korektnosti stačí ukázat, že T |= P(B) a T |= P(f(B)). Uvažme realizaci M jazyka L danou následovně: • jejím nosičem je soubor M = {a, b, c}, • AM = a, BM = b, • fM (a) = a, fM (b) = c, fM (c) = a, • PM = {a}. Zřejmě M je modelem teorie T: M |= P(A), neboť AM = a ∈ PM , M |= ∀x(P(x) → P(f(x))), neboť fM (a) = a ∈ PM a konečně M |= f(A) = f(f(B)). neboť oba uvedené uzavřené termy se v M realizují jako prvek a. Zároveň ale M |= P(B) (neboť BM = b ∈ PM ) a M |= P(f(B)) (neboť fM (BM ) = c ∈ PM ). Nalezli jsme tedy model teorie T ve kterém uvedené formule nejsou pravdivé, tyto formule tedy nemohou být jejím sémantickým důsledkem. KAPITOLA 11. KANONICKÁ STRUKTURA 113 Příklad 11.8 Mějme jazyk L = {P, f, A} bez rovnosti, kde P je unární predikátový symbol, f je unární funkční symbol a A je nulární funkční symbol (konstanta). Uvažme následující teorii T tohoto jazyka: T = {P(A), ∀x P(x) ∨ P(f(x)) }. Nechť M je kanonická struktura teorie T. a) Popište nosič realizace M. b) Popište realizaci PM predikátového symbolu P v kanonické struktuře M. Dokažte, že Vaše řešení obsahuje PM jako podmnožinu (tj. pro všechny prvky nosiče, které podle Vás nenáleží do PM dokažte, že do PM vskutku patřit nemohou). Příklad 11.9 Mějme jazyk L = {P, A, f, g} s rovností, kde P je unární predikátový symbol, A je konstanta (tj. nulární funkční symbol) a f, g jsou unární funkční symboly. Mějme dále následující teorii T s jazykem L: T = {P(A), A = f(A), P(f(x)) → P(g(f(x))), P(g(x)) → P(f(g(x)))}. Označme M kanonickou strukturu teorie T. Popište nosič této kanonické struktury a relaci PM. Své řešení zdůvodněte. Řešení Nejprve popišme nosič M kanonické struktury M, tj. soubor všech uzavřených termů daného jazyka. Chceme-li tento soubor popsat formálně zcela přesně, jakožto množinu slov nad abecedou {A, f, g, (, )}, můžeme použít například tuto formu zápisu z teorie formálních jazyků: M = k≥0 Mk, kde Mk = {f(, g(}k · {A} · {)}k . Popřípadě též můžeme říct, že M je jazyk generovaný gramatikou s kořenovým neterminálem S a s pravidly {S → A, S → f(S), S → g(S)}. V pořádku je i klasický matematický zápis, kdy se nestaráme o závorky a zavádíme zkratky f0(t) = g0(t) = t a fi+1(t) = f(fi(t)), gi+1(t) = g(gi(t)), pro libovolný term t. Pak lze psát například M = {zi1 1 (zi2 2 (· · · z ik−1 k−1 (zik k (A)) · · · ) | k ≥ 0, zj ∈ {f, g} a ij ≥ 0 pro 1 ≤ j ≤ k}. Nyní popišme realizaci PM predikátového symbolu P v kanonické struktuře M. Využijeme opět posledně zmíněný zkratkovitý zápis, kde pro libovolný term t klademe (f ◦ g)0(t) = t a (f ◦ g)i+1(t) = f(g(t)). PM = {gi ((f ◦ g)j (fk (A))) | k ≥ 0, j ≥ 0, i ∈ {0, 1}}. KAPITOLA 11. KANONICKÁ STRUKTURA 114 (Neformálně: postupujeme-li od nejvnitřnější aplikace funkčního symbolu na A, pak nejprve se může objevit libovolné množství aplikací symbolu f, jakmile se však objeví první aplikace symbolu g, musí se střídat aplikace symbolů g a f, přičemž můžeme skončit jak aplikací symbolu f, tak aplikací symbolu g.) Nyní ukažme, že pro všechny t ∈ PM vskutku platí T P(t). Označme ti,j,k term gi((f ◦ g)j(fk(A))). Chceme tedy ukázat následující: Věta 11.3 Pro libovolné i ∈ {0, 1}, j, k ≥ 0 platí T P(ti,j,k). Nejprve dokážeme, že Věta 11.3 platí pro libovolný term tvaru t0,0,k, k ≥ 0. Použijeme následující pomocné tvrzení: Tvrzení 11.4 V libovolném modelu M teorie T platí AM = fk M (AM ),1 pro libovolné k ≥ 0. Důkaz Nechť M je libovolný model teorie T. Pro k = 0 je tvrzení triviální, pro k = 1 plyne z toho, že T obsahuje formuli A = f(A). Předpokládejme, že tvrzení platí pro nějaké k ≥ 0, tj. že AM = fk M (AM ). Protože fM je funkce, platí též fM (AM ) = fk+1 M (AM ). Ale dle výše uvedeného platí fM (AM ) = AM , dohromady tedy AM = fk+1 M (AM ). Z výše uvedeného tvrzení a z definice pravdivosti pro formule tvaru P(t) přímo plyne, že v libovolném modelu M teorie T platí M |= P(A) právě když M |= P(fk(A)), pro libovolné k ≥ 0. Ovšem M |= P(A), neboť tato formule je axiomem teorie T. Tedy v libovolném modelu teorie T je pro libovolné k ≥ 0 pravdivá formule P(fk(A)), tj. T |= P(t0,0,k). Z věty o úplnosti plyne, že T P(t0,0,k). Nyní dokážeme platnost Věty 11.3 pro zbylé termy tvaru ti,j,k. Všimněme si, že pro libovolné j, k ≥ 0 je t1,j,k = g(t0,j,k) a pro libovolné k ≥ 0, j > 0 je t0,j,k = f(t1,j−1,k). Stačí tedy ukázat následující: a) Pro libovolné k ≥ 0 platí T P(t0,0,k). b) Pokud T P(t0,j,k), pak T P(t1,j,k). c) Pokud T P(t1,j,k), pak T P(t0,j+1,k). Ad a). Bylo již dokázáno výše. 1 Všimněte si, že symbol = je zde použit jako metasymbol, ne jako mimologický symbol pro rovnost. KAPITOLA 11. KANONICKÁ STRUKTURA 115 Ad b). Snadno se ukáže, že T P(t0,j,k) → P(t1,j,k): (1) T P(f(x)) → P(g(f(x))) axiom T (2) T ∀x (P(f(x)) → P(g(f(x)))) GEN na (1) (3) T ∀x (P(f(x)) → P(g(f(x)))) → (P(t0,j,k) → P(t1,j,k)) inst. P4 (4) T P(t0,j,k) → P(t1,j,k) MP na (2), (3). (V kroku (3) mohou nastat dvě možnosti. Pokud j ≥ 1, pak jde o instanci schématu specifikace, kde se za x dosadí term t1,j−1,k. Pokud j = 0, pak se za x musí dosadit term t0,0,k−1. Pokud navíc k = 0, pak nelze výše zmíněný důkaz použít. Stačí ale argumentovat, že formule P(A) → P(g(A)) vyplývá z teorie T, neboť v každém modelu M teorie T je AM = fM (AM ) a gM (AM ) = gM (fM (AM )). Platí tedy M |= P(A) → P(g(A)) právě když platí M |= P(f(A)) → P(g(f(A))). Buď jsou tedy z T dokazatelné obě tyto formule, nebo žádná z nich, stačí tedy vyřešit případ kdy k > 0.) Dále dle předpokladu máme T P(t0,j,k). Zapišme za sebe důkazy formulí P(t0,j,k) a P(t0,j,k) → P(t1,j,k) a na konec této posloupnosti přidejme formuli P(t1,j,k), kterou dostaneme aplikací MP na dvě výše zmíněné formule. Tato posloupnost je zřejmě důkazem formule P(t1,j,k) z teorie T, tedy T P(t1,j,k). Ad c). Metadůkaz je symetrický k případu b). Tím je dokončen důkaz Věty 11.3. Zbývá dokázat, že termy tvaru ti,j,k jsou jediné uzavřené termy daného jazyka, pro které je formule P(t) dokazatelná z T. Využijeme následující tvrzení: Tvrzení 11.5 Mějme uzavřený term t mající jeden z následujících tvarů: g(g(t0)) či f(f(t1)), kde t0, t1 jsou libovolné termy takové, že t1 obsahuje alespoň jeden výskyt symbolu g. Pak existuje model M teorie T takový, že tM ∈ PM a fM (tM ) = gM (tM ) = tM . Důkaz Uvažme realizaci M s nosičem {a, b, c, d}, kde AM = a, PM = {a, b, c}, a kde fM a gM jsou zadány výše uvedeným diagramem. M je modelem teorie T neboť: AM = a ∈ PM a tedy M |= P(A); pro libovolné individuum i, které náleží do PM a zároveň leží v obraze funkce fM (tj. i = a nebo i = c) je též gM (i) ∈ PM a tedy M |= P(f(x)) → P(g(f(x))) (symetricky se ukáže pro formuli P(g(x)) → P(f(g(x)))); a konečně a = fM (a) a tedy M |= A = f(A). Dále vidíme, že pro libovolné individuum i je g2 M (i) = d. Dále vidíme, že žádný term t1 obsahující alespoň jeden výskyt symbolu g se nemůže realizovat jako prvek a. Ovšem pro každé individuum i různé od a máme f2 M (i) = d. KAPITOLA 11. KANONICKÁ STRUKTURA 116 a b c d fM fM fM fM , gM gM gM gM PM AM Každý term t mající tvar uvedený v dokazovaném tvrzení se tedy v M realizuje jako prvek d ∈ PM . Ihned vidíme, že platí fM (tM ) = gM (tM ) = d = tM . Každý uzavřený term t daného jazyka je možné jednoznačně zapsat ve tvaru z1(z2(. . . zm(A) . . . )), kde m ≥ 0 a pro 1 ≤ l ≤ m je zl ∈ {f, g}. Pokud t není tvaru ti,j,k pro žádné i, j, k, pak nutně m ≥ 2 a zl = zl+1 pro nějaké 1 ≤ l < m. Pokud navíc zl = f, musí existovat l > l takové, že zl = g. Uvažme model M teorie T z předchozího tvrzení. Z tvrzení vyplývá, že zlM (zl+1M (. . . zmM (AM ) . . . )) ∈ PM a že tM = z1M (z2M (. . . zmM (AM ) . . . )) = zlM (zl+1M (. . . zmM (AM ) . . . )). Dohromady tM ∈ PM . Tedy pro term t který nemá tvar ti,j,k platí M |= P(t). Protože M je modelem T, máme T |= P(t) a dle věty o korektnosti i T P(t). Tím je důkaz hotov. Příloha A Vybrané zajímavosti V rámci přednášky „Matematická logika“ na Fakultě informatiky MU je možné se seznámit se základními pojmy a výsledky z tohoto oboru. Matematická logika je však mnohem hlubší oblastí, než by se z této úvodní přednášky mohlo zdát. V této části naší sbírky bychom tedy chtěli dát čtenáři možnost seznámit se s některými dalšími zajímavými výsledky. Obsah následujícího textu bezprostředně navazuje na obsah zmíněného kurzu logiky a neformálním způsobem jej rozšiřuje. Naší snahou je podat tuto rozšiřující látku přístupným a spíše neformálním způsobem, od čtenáře tedy neočekáváme zvláštní znalosti mimo pochopení látky z přednášky, na kterou tento text navazuje. Doufáme, že i tyto rozšiřující kapitoly si najdou své čtenáře a budou jim sloužit jako vydatné „krmivo pro mozek.“ A.1 Löwenheimova-Skolemova věta a nestandardní modely aritmetiky Značná část přednášky byla věnována Gödelovu důkazu neúplnosti Peanovy aritmetiky. V této kapitole si sestrojíme tzv. nestandardní model aritmetiky, tedy takovou realizaci jazyka L = {0, S, +, ·}, v níž jsou pravdivé přesně ty sentence jazyka L, které jsou pravdivé pro standardní přirozená čísla, ovšem která se od standardních přirozených čísel diametrálně liší. Nejprve si připomeňme samotnou Peanovu aritmetiku. Fixujme jazyk L = {0, S, +, ·} s rovností, kde 0 je nulární funkční symbol, S je binární funkční symbol a + a · jsou binární funkční symboly. PA (Peanova aritmetika) je teorie s jazykem L obsahující následující axiomy: • ∀x S(x) = 0 117 PŘÍLOHA A. VYBRANÉ ZAJÍMAVOSTI 118 • ∀x∀y (S(x) = S(y) → x = y) • ∀x x + 0 = x • ∀x∀y x + S(y) = S(x + y) • ∀x x · 0 = 0 • ∀x∀y x · S(y) = (x · y) + x • (ϕ(x/0) ∧ ∀x (ϕ → ϕ(x/S(x)))) → ∀x ϕ, kde ϕ je formule s jednou volnou proměnnou x. (Připomeňme, že tato teorie obsahuje ve skutečnosti nekonečný počet axiomů – poslední odrážka reprezentuje schéma axiomů, v němž dosazením libovolné formule s jednou volnou proměnnou x za ϕ dostaneme jeden konkrétní axiom Peanovy aritmetiky). Takzvaným standardním modelem aritmetiky máme na mysli realizaci N, jejímž nosičem je soubor N všech přirozených čísel (s nulou), a v níž se funkční symboly realizují následovně: • 0N je číslo 0, • SN je operace následníka, tj. funkce SN zobrazí libovolné přirozené číslo n na číslo o 1 větší, • +N a ·N jsou standardní sčítání, resp. standardní násobení přirozených čísel. Je zřejmé, že realizace N je vskutku modelem Peanovy aritmetiky. Budeme se nyní zabývat otázkou, zda má PA i jiné modely. Ačkoliv se zdá, že uvedené axiomy precizně popisují strukturu přirozených čísel, vskutku existují i modely Peanovy aritmetiky, které nejsou standardnímu modelu N izomorfní. Takový model nazveme nestandardním modelem. Existence nestandardního modelu plyne mimo jiné přímo z Gödelovy věty o neúplnosti, která říká, že Peanova aritmetika je neúplnou teorií, a z příkladu 9.17, ve kterém jsme ukázali, že každá teorie, která má až na isomorfismus jediný model, je úplná. Ve skutečnosti můžeme dokázat mnohem silnější tvrzení. Uvažme teorii ThN = {ϕ | ϕ je sentence jazyka L a N |= ϕ}. Teorie ThN se také nazývá skutečná aritmetika, neboť obsahuje právě ty sentence jazyka L, které jsou pravdivé ve standardním modelu N. Je PŘÍLOHA A. VYBRANÉ ZAJÍMAVOSTI 119 zřejmé, že teorie ThN je úplná teorie. Vskutku, ThN je splnitelná (a tedy dle příkladu 9.5 i bezesporná), neboť N je jejím modelem. Navíc dle příkladu 7.2 pro každou sentenci ϕ jazyka L platí buď N |= ϕ (a tedy ThN ϕ, neboť v tomto případě ϕ ∈ ThN), anebo N |= ¬ϕ (v kterémžto případě N ¬ϕ). Jde tedy o teorii, která je rozšířením Peanovy aritmetiky (všechny Peanovy axiomy náleží do ThN), které ovšem není konzervativní (neboť Peanova aritmetika úplná není, zatímco ThN úplná je). Teorie ThN tedy popisuje strukturu přirozených čísel tak přesně, jak jen to je v logice prvního řádu možné. Tento popis je dokonce tak precizní, že není žádným konečným způsobem prezentovatelný: neexistuje algoritmus, který by pro danou formuli rozhodl, zda je axiomem ThN či nikoliv (pokud by takový algoritmus existoval, byla by ThN rekurzivní úplnou teorií obsahující Peanovu aritmetiku, spor s Gödelovou větou o neúplnosti). Přesto stále existují modely teorie ThN, které nejsou standardnímu modelu N izomorfní. Plyne to mimo jiné z Löwenheimovy-Skolemovy věty (viz přednáška), která říká, že každá teorie se spočetným jazykem, která má nekonečný model, má model libovolné nekonečné kardinality. Zejména tedy teorie ThN má model s nespočetným nosičem, který zřejmě nemůže být izomorfní modelu N. Stále však nemáme příliš představu o tom, jak takový nestandardní model aritmetiky vlastně vypadá. Navíc jsme důkaz existence nestandardního modelu odbyli poměrně triviálním způsobem. Skutečně zajímavá otázka zní následovně: existuje nestandardní model teorie ThN (a tedy i Peanovy aritmetiky) se spočetným nosičem? Kupodivu je odpověď opět ano! V následujících odstavcích si existenci takového modelu dokážeme a příslušný nestandardní model si i do jisté míry popíšeme. Nejprve si ale zformulujeme variantu Löwenheimovy-Skolemovy věty, která nám pro jisté teorie umožní ukázat existenci modelu se spočetným nosičem. Důkaz věty 82 ve slajdech ukazuje pouze to, že libovolná teorie s nějakým jazykem L , která má model s nekonečným nosičem, má pro libovolné kardinální číslo κ ≥ |L | model mohutnosti alespoň κ. My bychom chtěli ukázat, že má model mohutnosti přesně κ. Pro jednoduchost uvážíme konkrétní jazyk – výše fixovaný jazyk aritmetiky L. Věta A.1 [o existenci spočetného modelu] Nechť T je libovolná teorie jazyka aritmetiky, která má model s nekonečným nosičem. Pak T má model se spočetným nosičem. Důkaz Uvažme teorii T = T ∪{ϕn | n ∈ N}, kde pro libovolné n ∈ N je ϕn formule ∃x1 . . . ∃xn 1≤i 0, m ∈ Z} (p, n) (q, m) pokud p < q, nebo p = q a n ≤ m (zde < a ≤ je standardní ostrá, resp. neostrá nerovnost v příslušném číselném oboru). Ačkoliv tedy mohou být symboly + a · v nestandardních spočetných modelech realizovány různými způsoby, uspořádání indukované operací +M je vždy stejné. Uspořádanou množinu (X, ) si můžeme neformálně představit následovně: vezměme klasicky uspořádanou množinu všech nezáporných racionálních čísel. Odeberme z ní nulu a místo ní přidejme „kopii“ standardně uspořádaných přirozených čísel, tj. stoupající zdola ohraničený nekonečný řetězec. Dále na místo každého pozitivního racionálního čísla umisťme „kopii“ standardně uspořádaných celých čísel, tj. zdola i shora neohraničený nekonečný řetězec. Nakonec všechny prvky přidané na místo nějakého racionálního čísla q prohlašme za ostře větší než libovolný prvek přidaný na místo libovolného racionálního čísla p < q. Situaci ilustruje následující obrázek, v němž šipky reprezentují funkci SM. Podáme neformální zdůvodnění věty A.2. Nejprve si povšimněme, že ThN |= ∀x∀y∃z (x + z = y ∨ y + z = x), tedy uspořádání ≤M je lineární. Dále ThN |= ∀x 0 + x = x 1 Zobrazení f mezi dvěma uspořádanými množinami (A, ≤) a (B, ) se nazývá izomorfismus uspořádaných množin, jestliže je to bijekce a pro libovolnou dvojici prvků a, a ∈ A platí a ≤ a ⇔ f(a) f(a ). PŘÍLOHA A. VYBRANÉ ZAJÍMAVOSTI 123 0M SM(0M) S2 M(0M) Mezi každými dvěma oboustranně neomezenými řetězci je další oboustranně neomezený řetězec, stejně tak před každým a po každém oboustranně neomezeném řetězci je další oboustranně neomezený řetězec. Obrázek A.1: Náčrt uspořádané množiny (X, ). a tedy 0M je nejmenším prvkem uspořádané množiny (M, ≤M). Podobnými argumenty je možné ukázat, že 0M ≤M SM(0M) ≤M S2 M(0M) ≤M · · · , a že pro libovolné n ∈ N již mezi individui Sn M(0M) a Sn+1 M (0M) v uspořádání ≤M žádné jiné individuum neleží. To ukazuje, že lineárně uspořádaná množina (M, ≤M) „začíná“ zespoda ohraničeným nekonečným2 řetězcem izomorfním množině (N, ≤). Prvky tohoto iniciálního řetězce (tj. prvky tvaru Sn M(0M) pro nějaké n) nazýváme standardní čísla, neboť operace +M a ·M se na tomto iniciálním úseku chovají jako standardní sčítání a násobení přirozených čísel. Ostatní individua z M nazveme nestandardní čísla. Označme N soubor všech nestandardních čísel v M. Uvažme binární relaci ekvivalence ∼ na souboru N definovanou násle- dovně: a ∼ b právě když existuje n ∈ N takové, že Sn M(a) = b, nebo Sn M(b) = a. Nechť C je libovolná třída rozkladu N/∼ a a ∈ C je její libovolný prvek. Pak pro libovolné n ∈ N je Sn M(a) ∈ C. Navíc pro libovolné n ∈ N existuje individuum an ∈ C takové, že Sn M(an) = a. Pokud by tomu tak nebylo, existovalo by individuum a ∈ C které by neleželo v obraze SM. Ovšem jediným takovým individuem je 0M (protože M je modelem Peanovy aritmetiky), což je standardní číslo, které nepatří do N. Protože dle definice je třída C tvořena právě těmi individui, ze kterých lze dosáhnout či které jsou dosažitelné z individua a, vidíme, že C jakožto uspořádaná podmnožina uspořádané množiny (M, ≤M) je oboustranně neohraničený nekonečný řetězec. Navíc lze opět ukázat, že libovolné individuum neležící v C je ostře větší či ostře menší než libovolný prvek C.3 Vidíme tedy, že část uspořádané 2 Nekonečným, neboť ThN |= ∀x∀y(S(x) = S(y) → x = y). 3 Neboť ThN |= ∀x ¬∃y (x = y ∧ S(x) = y ∧ ∃u∃v (x + u = y ∧ y + v = S(x))). PŘÍLOHA A. VYBRANÉ ZAJÍMAVOSTI 124 množiny (M, ≤M) „nad“ iniciálním segmentem standardních čísel se skládá z (jednoho či více) oboustranně neohraničených řetězců. Nyní ukážeme, že těchto řetězců je nekonečně mnoho. Vskutku, fixujme libovolné nestandardní číslo a ∈ N. Pro libovolné n ∈ N máme ThN |= ∀x∀y∀z (∃u (u = 0 ∧ x + u = y) → ∃u (u = 0 ∧ (x + z) + u = y + z)). To znamená, že pro libovolné n ∈ N je Sn M(a) = Sn M(0M)+M a