IB112 Základy matematiky Základy matematické logiky Jan Strejček Obsah ■ Výroková logika m výrokové formule, pravdivostní ohodnocení a valuace ■ pravdivost a splnitelnost ■ normální formy ■ úplný systém spojek ■ axiomatický systém ■ Predikátová logika ■ termy, kvantifikátory, predikátové formule ■ interpretace, valuace, pravdivost ■ axiomatický systém IB112 Základy matematiky: Základy matematické logiky 2/76 Výroková logika IB112 Základy matematiky: Základy matematické logiky 3/76 Výroky a výroková logika Výroky = tvrzení = oznamovací věty, u které můžeme určit její pravdivost ■ složený výrok je poskládán z atomických výroků a spojek ■ Příklady: ■ venku prší (atomický výrok) ■ jestli budeš do osmi v pyžamu, tak bude pohádka (složený výrok) ■ Výroky budeme označovat velkými písmeny A,b,C,... Výroková logika ■ Popisuje, jak lze z výroků a logických spojek budovat další výroky. ■ Zkoumá vztahy mezi pravdivostí různých výroků. IB112 Základy matematiky: Základy matematické logiky 4/76 Logické spojky Logické spojky = výrazy, kterými z výroku vyrábíme složené výroky ■ Príklady: "není pravda, že A", "A, ledaže by b" m V matematické logice používáme jen vybrané spojky, jejichž význam se může mírně lišit od významu v běžném jazyce. Např. "půjdu tam dnes nebo tam půjdu zítra" chápeme tak, že nastane jen jedna eventualita. notace výraz v češtině název "není pravda, že A" negace aab "A a b" konjunkce Av b "A nebo b" disjunkce A^b "jestliže A, tak b" implikace A^b "/A právě tehdy, když b" ekvivalence IB112 Základy matematiky: Základy matematické logiky 5/76 Výrokové formule ■ Výrokové formule mohou obsahovat pouze výrokové symboly (reprezentují výroky), logické spojky a závorky (,). Definice (Výrokové formule) Nechť P = {a, b, c,...} je neprázdná množina výrokových symbolů. Výrokové formule nad P definujeme takto: d Každá výrokový symbol je výroková formule. B Jsou-li A, B výrokové formule, pak i (->A), (A A B), (A v B), (A B), (A B) jsou výrokové formule. Q Nic jiného není výroková formule. ■ Výrokové symboly nazýváme atomické formule. ■ Ostatní výrokové formule se nazývají složené. IB112 Základy matematiky: Základy matematické logiky 6/76 Poznámky ■ Příklady výrokových formulí: (a (->£>)), (—■((—■a) v b)), (aA(Ď«(c^ ■ ■ ■ ■ Odvození ((a A b) (c (->a))): ■ a,b,c jsou formule dle bodu 1. ■ (a A b) a (-^a) jsou formule dle bodu 2. ■ (c =^ (^a)) je pak také formule dle bodu 2. ■ Konečně ((a A b) <^ (c => (^a))) je také formule dle bodu 2. ■ Závorky v zápisu formulí často vynecháváme, pokud tím není dotčena jednoznačnost. Např. píšeme (a A b) (c => -ia) namísto ((a A b) (c (->a))). IB112 Základy matematiky: Základy matematické logiky 7/76 Pravdivostní ohodnocení ■ Pravdivost výrokové formule závisí pouze na pravdivosti atomických formulí, které se ve formuli vyskytují. ■ Pravdivost atomických formulí je dána pravdivostním ohodnocením, pravdivost složených formulí je dána valuací. Definice (Pravdivostní ohodnocení) Pravdivostní ohodnocení (neboli interpretace) je funkce I: P ->• {0,1} přiřazující každé atomické formuli pravdivostní hodnotu 1 (pravda) nebo 0 (nepravda). ■ Pravdivostní hodnoty 1,0 se někdy také značí T, F. IB112 Základy matematiky: Základy matematické logiky 8/76 Valuace Definice (Valuace) Nechť I je pravdivostní ohodnocení. Valuace ľ je funkce přiřazující každé výrokové formuli A pravdivostní hodnotu 1 nebo O a splňující: m Je-li A atomická formule, pak ľ (A) = l(A). ■ ľ{^A) = 1 pokud ľ {A) = O a ľ{^A) = O pokud ľ {A) = 1. ■ ľ (A A B) = 1 pokud ľ {A) = ľ(B) = 1. Jinak ľ (A A B) = 0. ■ ľ (A V6)=0 po/čud = ľ(B) = 0. J/na/c v B) = 1. ■ /'(^ =>• fl) = 0 pokud ľ {A) = 1 a /'(B) = 0. J/na/c ľ {A =>B) = 1. ■ /'(^ B) = 1 po/čud /'(^) = /'(£)■ ^a/c /'(^ 4» B) = 0. ■ Valuace je pravdivostním ohodnocením určena jednoznačně a je jeho rozšířením. ■ Valuaci a pravdivostní ohodnocení tedy lze ztotožnit. IB112 Základy matematiky: Základy matematické logiky 9/76 Pravdivost formule Definice Výroková formule A se nazývá ■ pravdivá při ohodnocení I, jestliže ľ (A) = 1. ■ pravdivá nebo tautologie, psáno \= A, pokud je pravdivá při všech ohodnoceních. ■ kontradikce, pokud není pravdivá při žádném ohodnocení. ■ splnitelná, pokud je pravdivá při nějakém ohodnocení. Formule A, B jsou ekvivalentní, psáno A = B, pokud jsou pravdivé při stejných ohodnoceních. Příklady ■ tautologie: a v -^a, a=> a, a« —■—ia, (a A -ia) => b ■ kontradikce: a A -^a, a ^a ■ ekvivalentní formule: a => b = dv-ia IB112 Základy matematiky: Základy matematické logiky 10/76 Příklad Je formule ((a A b) <^ (c (^a))) pravdivá při ohodnocení /(a) = 1, l(b) = 0, /(c) = 1? IB112 Základy matematiky: Základy matematické logiky 11/76 Příklad Je formule ((a A b) <^ (c (^a))) pravdivá při ohodnocení /(a) = 1, l(b) = 0, /(c) = 1? ■ /'(a) = 1, ľ(b) = 0,/'(c) = 1 ■ ľ(a a b) = 0 m /'(-a) = 0 ■ /'(c^ (-a)) = 0 ■ /'((a A /?) 4» (c=* (-.a))) = 1 ■ Zadaná formule je při daném ohodnocení pravdivá. IB112 Základy matematiky: Základy matematické logiky 12/76 Vybrané tautologie Mnohé tautologie mají svoje názvy: ■ komutativní zákony: (a A b) (b A a), (a v b) (b v a),... ■ asociativní zákony: ((a AĎ)Ac)(aA(í?A c)),... ■ distributivní zákony: (a A (b v c)) ((a A £>) v (a A c)),... ■ zákon vyloučení třetího: a v -ia ■ zákon sporu: -i(a A -ia) ■ zákon totožnosti: a a ■ zákon dvojí negace: a —■— ■ idempotence: (aAa)»a, (ava)«a ■ de Morganovy zákony: -.(a A í>) -o- (->a V -■/?), -.(a v £>) ^ (-.a A -.6) IB112 Základy matematiky: Základy matematické logiky 13/76 Věta o implikaci Věta (Věta o implikaci, sémantický modus ponens) Pokud platí |= A a |= A =>- B, pak platí |= B. Důkaz Sporem. Nechť platí |= A a |= A B a nechť B není tautologie. Označme / ohodnocení, v kterém B není pravdivé, t.j. I'(B) = 0. Jelikož A je tautologie, platí l'(A) = 1. Dohromady dostáváme ľ {A B) = 0 a proto /A B není tautologie. To je spor. □ IB112 Základy matematiky: Základy matematické logiky 14/76 Pravdivostní tabulka ■ Pravdivostní tabulka zaznamenává pravdivost dané formule (a jejích podformulí) při všech ohodnoceních. ■ Každý řádek tabulky odpovídá jednomu ohodnocení. ■ Počet řádků tabulky je 2n, kde n je počet různých atomických formulí v dané formuli. a b c a^b (a ti) => c Pravdivostní tabulka pro (a ti) => c 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 0 0 0 0 0 IB112 Základy matematiky: Základy matematické logiky 15/76 Využití pravdivostní tabulky ■ Z pravdivostní tabulky lze dle výsledných pravdivostních hodnot pro danou formuli snadno určit, zda je formule: ■ tautologie - ve všech řádcích je pravdivostní hodnota 1 ■ kontradikce - ve všech řádcích je pravdivostní hodnota 0 ■ splnitelná - v nějakém řádku je pravdivostní hodnota 1 ■ Srovnáním dvou pravdivostních tabulek snadno rozhodneme i ekvivalenci formulí. ■ Jelikož existuje algoritmus rozhodující zda je výroková formule pravdivá, říkáme, že výroková logika je rozhodnutelná. IB112 Základy matematiky: Základy matematické logiky 16/76 Příklad ■ Sestrojte pravdivostní tabulku pro formuli a (b c). ■ Rozhodněte, zdaje formule tautologie, kontradikce, splnitelná a zda je ekvivalentní formuli (a => b) => c. a b c b => c a =^ (b c) 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 IB112 Základy matematiky: Základy matematické logiky 17/76 Příklad ■ Sestrojte pravdivostní tabulku pro formuli a (b c). ■ Rozhodněte, zdaje formule tautologie, kontradikce, splnitelná a zda je ekvivalentní formuli (a => b) => c. a b c b => c a = > (b=> c) 0 0 0 1 1 0 0 1 1 1 0 1 0 0 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1 IB112 Základy matematiky: Základy matematické logiky 18/76 Příklad ■ Sestrojte pravdivostní tabulku pro formuli a (b c). ■ Rozhodněte, zdaje formule tautologie, kontradikce, splnitelná a zda je ekvivalentní formuli (a => b) => c. a b c b => c a = > (b=> c) 0 0 0 1 1 0 0 1 1 1 0 1 0 0 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1 ■ Není tautologie ani kontradikce, je splnitelná a není ekvivalentní formuli (a => b) => c. IB112 Základy matematiky: Základy matematické logiky 19/76 Disjunktivní normální forma (DNF) ■ Jelikož je disjunkce asociativní, tedy (A v B) v C = A v (B v C), píšeme pouze A v B v C. Podobně lze psát \ AaB aC. Definice (Literal, konjunktivní klauzule, DNF) Literát je atomická formule nebo její negace. Konjunktivní klauzule je konjunkce libovolného konečného počtu literátů. Formule A je v disjunktivní normální formě (DNF), je-li to jedna klauzule nebo disjunkce konečně mnoha konjunktivních klauzulí. Příklady ■ literály: a, b, -^a, -ic ■ konjunktivní klauzule: (a A ->c A b), (->a A -ic A -*b a d) m formule v DNF: (a A A b) V (-.a A A -.b A d) V (-.oř) IB112 Základy matematiky: Základy matematické logiky 20/76 Disjunktivní normální forma (DNF) Ke každé výrokové formuli existuje ekvivalentní formule v DNF. Ekvivalentní formule v DNF lze sestrojit z pravdivostní tabulky: ■ Pro každé ohodnocení, kde je formule pravdivá, přidáme do vytvářené formule v DNF jednu konjunktivní klauzuli, která bude pro každý pravdivý atomický výrok a obsahovat literál a a pro každý nepravdivý atomický výrok b literál ■ Není-li formule pravdivá v žádném ohodnocení, pak je to kontradikce a je ekvivalentní kontradikci (a A -ia) a ta je v DNF. a b (a o -■/?) 1 1 0 1 0 1 0 1 1 0 0 0 IB112 Základy matematiky: Základy matematické logiky 21/76 Disjunktivní normální forma (DNF) Ke každé výrokové formuli existuje ekvivalentní formule v DNF. Ekvivalentní formule v DNF lze sestrojit z pravdivostní tabulky: ■ Pro každé ohodnocení, kde je formule pravdivá, přidáme do vytvářené formule v DNF jednu konjunktivní klauzuli, která bude pro každý pravdivý atomický výrok a obsahovat literál a a pro každý nepravdivý atomický výrok b literál ■ Není-li formule pravdivá v žádném ohodnocení, pak je to kontradikce a je ekvivalentní kontradikci (a A -ia) a ta je v DNF. a b (a o -■/?) 1 1 0 1 0 1 0 1 1 0 0 0 ~> (a A -ib) IB112 Základy matematiky: Základy matematické logiky 22/76 Disjunktivní normální forma (DNF) Ke každé výrokové formuli existuje ekvivalentní formule v DNF. Ekvivalentní formule v DNF lze sestrojit z pravdivostní tabulky: ■ Pro každé ohodnocení, kde je formule pravdivá, přidáme do vytvářené formule v DNF jednu konjunktivní klauzuli, která bude pro každý pravdivý atomický výrok a obsahovat literál a a pro každý nepravdivý atomický výrok b literál ■ Není-li formule pravdivá v žádném ohodnocení, pak je to kontradikce a je ekvivalentní kontradikci (a A -ia) a ta je v DNF. a b (a o -■/?) 1 1 0 1 0 1 -> (a A -*b) 0 1 1 -> (-ia A /?) 0 0 0 IB112 Základy matematiky: Základy matematické logiky 23/76 Disjunktivní normální forma (DNF) Ke každé výrokové formuli existuje ekvivalentní formule v DNF. Ekvivalentní formule v DNF lze sestrojit z pravdivostní tabulky: ■ Pro každé ohodnocení, kde je formule pravdivá, přidáme do vytvářené formule v DNF jednu konjunktivní klauzuli, která bude pro každý pravdivý atomický výrok a obsahovat literál a a pro každý nepravdivý atomický výrok b literál ■ Není-li formule pravdivá v žádném ohodnocení, pak je to kontradikce a je ekvivalentní kontradikci (a A -ia) a ta je v DNF. a b (a o -■/?) 1 1 0 1 0 1 -> (a A -*b) Celkem: 0 1 1 -> (-ia A b) (a -üb) = 0 0 0 (aA-■/?) v (-.a Ab) IB112 Základy matematiky: Základy matematické logiky 24/76 Konjunktivní normální forma (CNF) ■ Definice CNF je analogická definici DNF, akorát konjunkce a disjunkce se prohodí. Definice (klauzule, CNF) (Disjunktivní) klauzule je disjunkce libovolného konečného počtu literátů. Formule A je v konjunktivní normální formě (CNF), je-li to jedna klouzule nebo disjunkce konečně mnoha klauzulí. Příklady ■ klauzule: (av^cv b), (-.a v -.c v -.6 v d) m formule v CNF: (a v -.c v b) A (-.a v ->c v ->b v d) A (-.ar) IB112 Základy matematiky: Základy matematické logiky 25/76 Konjunktivní normální forma (CNF) Ke každé výrokové formuli existuje ekvivalentní formule v CNF. Ekvivalentní formule v DNF lze sestrojit z pravdivostní tabulky: ■ Pro každé ohodnocení, kde je formule nepravdivá, přidáme do vytvářené formule v CNF jednu klauzuli, která bude pro každý nepravdivý atomický výrok a obsahovat literál a a pro každý pravdivý atomický výrok b literál Je-li formule pravdivá při všech ohodnoceních, je to tautologie a je ekvivalentní tautologii (a v -ia) a ta je v CNF. a b (a o -■/?) 1 1 0 1 0 1 0 1 1 0 0 0 IB112 Základy matematiky: Základy matematické logiky 26/76 Konjunktivní normální forma (CNF) Rěta^^^^^^^^^^^^^^^ Ke každé výrokové formuli existuje ekvivalentní formule v CNF. Ekvivalentní formule v DNF lze sestrojit z pravdivostní tabulky: ■ Pro každé ohodnocení, kde je formule nepravdivá, přidáme do vytvářené formule v CNF jednu klauzuli, která bude pro každý nepravdivý atomický výrok a obsahovat literál a a pro každý pravdivý atomický výrok b literál Je-li formule pravdivá při všech ohodnoceních, je to tautologie a je ekvivalentní tautologii (a v -ia) a ta je v CNF. a b (a o -■/?) 1 1 0 1 0 1 0 1 1 0 0 0 ~> (-lav-ib) IB112 Základy matematiky: Základy matematické logiky 27/76 Konjunktivní normální forma (CNF) Rěta^^^^^^^^^^^^^^^ Ke každé výrokové formuli existuje ekvivalentní formule v CNF. Ekvivalentní formule v DNF lze sestrojit z pravdivostní tabulky: ■ Pro každé ohodnocení, kde je formule nepravdivá, přidáme do vytvářené formule v CNF jednu klauzuli, která bude pro každý nepravdivý atomický výrok a obsahovat literál a a pro každý pravdivý atomický výrok b literál Je-li formule pravdivá při všech ohodnoceních, je to tautologie a je ekvivalentní tautologii (a v -ia) a ta je v CNF. a b (a o -■/?) 1 1 0 -> (-lav-ib) 1 0 1 0 1 1 0 0 0 -> (avfc) IB112 Základy matematiky: Základy matematické logiky 28/76 Konjunktivní normální forma (CNF) Ke každé výrokové formuli existuje ekvivalentní formule v CNF. Ekvivalentní formule v DNF lze sestrojit z pravdivostní tabulky: ■ Pro každé ohodnocení, kde je formule nepravdivá, přidáme do vytvářené formule v CNF jednu klauzuli, která bude pro každý nepravdivý atomický výrok a obsahovat literál a a pro každý pravdivý atomický výrok b literál Je-li formule pravdivá při všech ohodnoceních, je to tautologie a je ekvivalentní tautologii (a v -ia) a ta je v CNF. a b (a o -■/?) 1 1 0 -> (-lav-ib) 1 0 1 Celkem: 0 1 1 (a -üb) = 0 0 0 -> (avfc) (-■a v -ib) a (a v fe) IB112 Základy matematiky: Základy matematické logiky 29/76 Pravdivostní funkce ■ Význam výrokových formulí lze také definovat pomocí pravdivostních funkcí. Definice (Pravdivostní funkce) Pravdivostní funkce arity n je funkce /::{0,1}n-^{0,1}. ■ Pravdivostní funkce každé /i-tici pravdivostních hodnot přiřadí jednu pravdivostní hodnotu. ■ Každá formule s n (uspořádanými) atomickými formulemi jednoznačně určuje pravdivostní funkci arity n. ■ Např. a A b odpovídá binární pravdivostní funkci f(x, y) = x ■ y. IB112 Základy matematiky: Základy matematické logiky 30/76 Pravdivostní funkce ■ Pravdivostní funkci lze zapsat tabulkou. X y z f{x, y,z) 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 0 ■ Lze každou pravdivostní funkci vyjádřit pomocí výrokové formule? IB112 Základy matematiky: Základy matematické logiky 31/76 Pravdivostní funkce ■ Pravdivostní funkci lze zapsat tabulkou. X y z f{x, y,z) 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 0 ■ Lze každou pravdivostní funkci vyjádřit pomocí výrokové formule? ■ Ano. Formuli sestrojíme z tabulky stejně, jako jsme z tabulky vytvořili formuli v DNF (nebo CNF). IB112 Základy matematiky: Základy matematické logiky 32/76 Úplný systém spojek Definice (Úplný systém spojek) Množinu logických spojek nazveme úplný systém spojek, pokud lze každou pravdivostní funkci vyjádřit pomocí výrokové formule používající pouze spojky z dané množiny m Jelikož lze každou pravdivostní funkci popsat formulemi v DNF i v CNF, je množina {a, v, -■} úplným systémem spojek. ■ Protože platí A a B = -.(-TI v -■£?) lze každou konjunkci vyjádřit pomocí v, -i. Proto je úplný i systém {v, -■}. ■ Podobně A v B = -.(-vA a -■£?) a proto je úplný i systém {a, -■}. ■ {=>, -1} je také úplný systém. ■ Existuje jednoprvkový úplný systém spojek? IB112 Základy matematiky: Základy matematické logiky 33/76 Další logické spojky a b a xor b a nand b a nor b 1 1 0 0 0 1 0 1 1 0 0 1 1 1 0 0 0 0 1 1 ■ XOR - exclusive or, A xor B = -^(Ao B) m NAND - Shefferova funkce, A nand B = -^{A A B) m NOR - Nicodova funkce, A nor B = -*(A V B) m {nand} i {nor} tvoří úplné jednoprvkové systémy spojek. ■ Všechny tři spojky jsou v informatice významné. IB112 Základy matematiky: Základy matematické logiky 34/76 Množiny formulí a vyplývání Definice (Splnitelnost, model, vyplývání) Nechť T je množina výrokových formulí. Množina T je splnitelná, pokud existuje ohodnocení, při kterém jsou pravdivé všechny formule z T. Takové ohodnocení se nazývá model množiny T. Formule A logicky vyplývá z množiny T, psáno T \= A, pokud je A pravdivá v každém modelu množiny T. m T |= A také čteme jako A je logickým důsledkem T. m Z nesplnitelné množiny T vyplývá libovolná formule. ■ Splnitelnost konečné množiny klauzulí T lze rozhodnout pomocí pravdivostní tabulky obsahující sloupce pro všechny formule z T. Platnost T \= A lze rozhodnout analogicky. IB112 Základy matematiky: Základy matematické logiky 35/76 Příklad Zjistěte, zda je množina formulí T = {-■£> v a, ->a v c} splnitelná a zda je jejím důsledkem formule b^ c. a b c -■ave b => c 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 IB112 Základy matematiky: Základy matematické logiky 36/76 Příklad Zjistěte, zda je množina formulí T = {-■£> v a, ->a v c} splnitelná a zda je jejím důsledkem formule b^ c. a b c -■ave b => c 0 0 0 1 1 0 0 1 1 1 0 1 0 0 1 0 1 1 0 1 1 0 0 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 m T je splnitelná. IB112 Základy matematiky: Základy matematické logiky 37/76 Příklad Zjistěte, zda je množina formulí T = {-■£> v a, ->a v c} splnitelná a zda je jejím důsledkem formule b^ c. a b c -■ave b => c 0 0 0 1 1 1 0 0 1 1 1 1 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 1 0 1 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 ■ T je splnitelná. ■ b => c je důsledkem T. IB112 Základy matematiky: Základy matematické logiky 38/76 Věta o dedukci a lemma o neutrální formuli Věta (Věta o dedukci, sémantická varianta) Buď T množina výrokových formulí. Pak platí T \= A^ B právě když T u {A} \= B. Věta (Lemma o neutrální formuli, sémantická varianta) Buď T množina výrokových formulí. Pokud platí T u {A} \= B a Tu{-u4} |= B,pakiT\= B. IB112 Základy matematiky: Základy matematické logiky 39/76 Formální systémy ■ Pravdivost formulí lze zkoumat i na základě jejich syntaxe (bez interpretací, bez pravdivostních tabulek). Formální systém ■ umožňuje k formulím budovat důkazy ■ skládá se z ■ axiomů - tvrzení, jejichž pravdivost přijmeme bez důkazu ■ odvozovacích pravidel - konstrukce umožňující vytvářet důkazy ■ může být ■ axiomatický - méně pravidel, více axiomů ■ předpokladový - více pravidel, méně axiomů ■ Ukážeme axiomatický systém pro výrokovou logiku využívajících pouze spojek a -i. IB112 Základy matematiky: Základy matematické logiky 40/76 Axiomatický systém Axiomy (A1) A=> {B^A) (A2) (A =>• {B C)) =>• ((4 =>• B) =>• (4 =>• C)) (A3) (-.fl -.4) =>• {A =>• fí) Odvozovací pravidlo (P1) Z A a A ^ B plyne e. ■ A, B, C jsou libovolné výrokové formule. ■ Odvozovací nebo také inferenčn í pravidlo (P1) se nazývá pravidlo odloučení nebo modus ponens. m V (P1) se formule A a A B nazývají předpoklady, B se pak nazývá závěr. ,™ - . . . , A A=> B ■ (P1) se často zapisuje jako-=-. B IB112 Základy matematiky: Základy matematické logiky 41/76 Důkaz Definice (Důkaz) Konečnou posloupnost A^ ,A2,...,An výrokových formulí nazveme důkazem formule An, pokud pro každé i < n je A, buď axiomem nebo závěrem odvozovacího pravidla, jehož předpoklady jsou mezi formulemiA^,A2,...,A -i■ Výroková formule A je dokazatelná, psáno h A, pokud existuje důkaz formule A. IB112 Základy matematiky: Základy matematické logiky 42/76 Příklad Dokažte h A =>- A. IB112 Základy matematiky: Základy matematické logiky Dokažte h A =>- A Řešení Důkazem je posloupnost ((A=>A) =>• A), (4 ^ {(A ^ A) ^ =>• ((4 =>(A=> A)) ^(A^ A)), (A=>(A=> A)) ^(A^A),A^(A^ A), A^A. Označíme-li formule v posloupnosti A, A, • • • A5, pak ■ A je (A1) pro volbu A, A =>- A za A, B, m A2 je (A2) pro volbu A, A =>- A A za /A, e, C, ■ A je závěr (P1) s předpoklady A, A2, m A4 je (A1) pro volbu A, A za A, B, m A5 je závěr (P1) s předpoklady A3,A4. IB112 Základy matematiky: Základy matematické logiky Zobecnění dokazatelnosti Definice Nechť T je množina výrokových formulí. Konečnou posloupnost A^,A2,...,An výrokových formulí nazveme důkazem formule An z T, pokud pro každé i < n je A, buď axiomem, prvkem T nebo závěrem odvozovacího pravidla, jehož předpoklady jsou mezi formulemi A^ ,A2,..., A -i ■ Píšeme T h An ■ h A je totéž jako 0 h A ■ Místo {A} h B píšeme pouze A h B. IB112 Základy matematiky: Základy matematické logiky 45/76 Věta o dedukci a lemma o neutrální formuli Věta (Věta o dedukci) Buď T množina výrokových formulí. Pak platí T h B právě když T U {A} h B. Důkaz Q Směr "=>". Platí-li T h A B, pak existuje důkaz A,, A2,.. ■, An, A =>- B formule A B z T. Pak ale A-\,A2,...,An,A^ B, A, B je důkaz formule BzTu {A}. B Důkaz "<í=" je komplikovanější... □ IB112 Základy matematiky: Základy matematické logiky 46/76 Příklad Platí d I—B), Q h -,-,A A, 0h(M6)^ (-.fl=* -.4), Q \-A=>{-^B=>^{A=>B)), S h (-.4 A) A. Důkaz Ukážeme (1), ostatní se lze dokázat podobně. ■ Z (A1) plyne \-->A=> {^B -,A). m Z Věty o dedukci dostáváme -*A\—>B -.A m Z (A3) plyne h (-.fl -A) =>{A=> B), m Pomoci modus ponens tedy dostáváme -*A h A B. m Z Věty o dedukci dostaneme I—- B z Věty o dedukci, B 71—" se nazývá korektnost (co dokážeme to platí). ■ K důkazu korektnosti stačí ukázat, že (A1), (A2) i (A3) jsou pravdivé a že (P1) z pravdivých předpokladů odvodí vždy pravdivý závěr. ■ Implikace se nazývá úplnost (dokážeme vše, co platí). ■ Existují i další formální systémy pro výrokovou logiku (např. Gentzenovský systém). IB112 Základy matematiky: Základy matematické logiky 49/76 Predikátová logika IB112 Základy matematiky: Základy matematické logiky Predikátová logika ■ Rozšiřuje výrokovou logiku. ■ Umožňuje přesněji popsat výrok a díky tomu odvodit logická vyplývání, která ve výrokové logice odvodit nelze: ■ Každý člověk je smrtelný. ■ Sokrates je člověk. ■ Sokrates je smrtelný. ■ Výroky označíme postupně a, b, c. Ve výrokové logice nelze odvodit logické vyplývání c z a, b, přestože c zjevně je důsledkem a, b. IB112 Základy matematiky: Základy matematické logiky 51/76 Jazyk predikátové logiky Jazyk predikátové logiky se zkládá z těchto symbolu: ■ proměnné: x, y, z, x-\, x2,... ■ logické spojky: -,, a, v, =>, o ■ kvantifikátory: V (pro všechna), 3 (existuje) ■ rovnost: = m závorky: (,) ■ relační neboli predikátové symboly. P, Q, R, P-i, P2,... m funkční symboly: f,g,h,f-\,f2,-- m Každý predikátový symbol má pevně danou arity n > 0. ■ Každý funkční symbol má pevně danou aritu n > 0 (počet argumentu). ■ Funkce s aritou 0 se nazývají konstanty a značí se a, b, c,.... IB112 Základy matematiky: Základy matematické logiky 52/76 Konstanty, proměnné a funkce ■ Konstanty, proměnné i funkce slouží k označení objektů. ■ Objekty jsou prvky dané množiny objektů nazývané doména nebo univerzum. ■ Konstanty jsou vlastně jména objektů. ■ Proměnné zastupují libovolné objekty. ■ Pomocí funkcí vytváříme složená jména objektů. Příklad ■ Uvažujme doménu nezáporných celých čísel. ■ Konstanty jsou např. 0,1,42. ■ Příkladem binární funkce (funkce arity 2) je +. ■ Složené jméno objektu 3 je například 1 + 2 nebo (1 + 1) + 1. ■ Složené jméno objektu je i x + 2 nebo (x + 2) + (z + x). IB112 Základy matematiky: Základy matematické logiky 53/76 Termy ■ Termy jsou všechna možná označení objektů. Definice (Termy) Termy definujeme takto: O Každá proměnná je term. □ Je-li f funkční symbol arity n a U, k, ■ ■ ., tn jsou termy pak i f {U, k,..., tn) je term. Q Nic jiného není term. ■ Z bodu (2) plyne, že konstanty (nulární funkce) jsou také termy. ■ Příklady termů: a, 0, x, f(x, 0, a), f(g(a, 0), 2, h(h(y))) IB112 Základy matematiky: Základy matematické logiky 54/76 Predikát ■ Nulární predikát je výrok (jako ve výrokové logice). ■ Unární predikát ■ popisuje vlastnost objektu, ■ odpovídá výroku, ze kterého odstraníme označení jednoho objektu. ■ Příklad: Predikát P odpovídá pojmu "být smrtelný" "Objekt x je smrtelný" ~-> P(x) "Sokrates je smrtelný" ~+ P(Sokrates) ■ Binární predikát ■ popisuje vztah mezi dvěma objekty. ■ Příklad: "x je násobek y" ~+ Q(x,y) "x + 3 je násobek 2" Q(x + 3,2) "xje menší než 7" ~-> x < 7 (infixová notace) ■ Predikát arity n popisuje vztah mezi n objekty. IB112 Základy matematiky: Základy matematické logiky 55/76 Kvantifikátory V - univerzální neboli obecný kvantifikátor ■ (Vx)P(x) říká, že pro všechny objekty x z domény platí P(x). ■ Pro konečnou doménu {a-i, a2,..., an} je (Vx)P(x) ekvivalentní formuli P(a-i) A P(a2) A ... A P(an). El - existenciální kvantifikátor ■ (3x)P(x) říká, že existuje (alespoň jeden) objekt x z domény, pro který platí P(x) (neboli P(x) platí pro některé objekty x). ■ Pro konečnou doménu {a-i, a2,..., an} je (3x)P(x) ekvivalentní formuli P(a-i) v P(a2) v ... v P(an). Příklad ■ Nechť P odpovídá pojmu "být smrtelný". ■ Uvažujme doménu všech lidí. ■ (Vx)P(x) říká, že všichni lidé jsou smrtelní. ■ (3x)P(x) říká, že existuje smrtelný člověk (neboli někteří lidé jsou smrtelní). IB112 Základy matematiky: Základy matematické logiky 56/76 Predikátové formule Definice (Predikátové formule) Atomické predikátové formule definujeme takto: O Nechť P je predikátový symbol arity n a U,... ,tn jsou termy Pak P(ři,..., tn) je atomická predikátová formule. B Jsou-li ři, t2 termy, pak ři = t2 je atomická predikátová formule. B Nic jiného není atomická predikátová formule. Predikátové formule definujeme takto: d Každá atomická predikátová formule je predikátová formule. B Jsou-li (p, V> predikátové formule, pak i -k/j, (fVý^^ý^^ý^oý jsou predikátové formule. Q Je-li x proměnná a

R(x, z)) ...R\e tranzitivní IB112 Základy matematiky: Základy matematické logiky 58/76 Vázaný a volný výskyt proměnných ■ Podformule formule je každá souvislá část , která je také formulí. ■ Podformule ip ve formulích (Vx)V> a (3x)ip se nazývá oborem nebo rozsahem kvantifikátoru (Vx) nebo (3x). ■ Výskyt proměnné x ve formuli ip je vázaný, je-li v rozsahu nějakého kvantifikátoru (Vx) nebo (3x). m Výskyty, které nejsou vázané, jsou volné. ■ Příklad: ((Vx)(3y)P(x, y, z)) R(x, z) ... vázaný/volný výskyt ■ Proměnná se nazývá volná (resp. vázaná), existuje-li v dané formuli její volný (resp. vázaný) výskyt. ■ Formule bez volných proměnných se nazývá sentence neboli uzavřená formule. ■ Formule bez kvantifikátorů se nazývá otevřená formule. ■ Zápis (p(x-\, x2,..., xn) označuje formuli

a I, V i,, m tp-i v tp2 a I, V \= tp-i nebo l,V\= tp2, m V>1 A -02 a I, V |= V>1 al,V\=ip2, m tp-i => tp2 a I, V "01 nebo l,V\= tp2, m Vi & i>2 a I, V h V>1 a /, V h V>2, neĎo l,l/Nia',^ V>2, ■ (Vx)i/> a /, V[x/d\ h ^ pra /(ažc/é d z domény D. m (3x)tp a I, V[x/d] \= tp pro nějaké d z domény D. IB112 Základy matematiky: Základy matematické logiky 67/76 Pravdivost formule ■ Snadno se ověří, že pravdivost formule ip při interpretaci / a valuaci V záleží pouze na valuaci proměnných, které jsou volné ve

logicky vyplývá z teorie T (ip je důsledkem T), psáno T |= V, pokud je V> pravdivá v každém modelu teorie T. Teorie T je sporná, pokud nemá žádný model. V opačném případě je teorie bezesporná. Příklad ■ Formální zápis Sokratovy úvahy: {(Vx)(C(x) S(x)), C(Sokrates)} |= S(Sokrates) IB112 Základy matematiky: Základy matematické logiky 72/76 Příklad teorie - Peanova aritmetika ■ Peanova aritmetika popisuje základy teorie čísel. ■ Jazyk obsahuje konstantu 0, unární funkční symbol s (následník), binární funkční symboly + a *. ■ (Vx)--(O = s(x)) ■ (Vx)(Vy)(s(x) = s(y) x = y) m (yx) x + 0 = x m (Vx)(Vy) x + s(y) = s(x + y) ■ (Vx) x * 0 = 0 ■ (Vx)(Vy) x * s(y) = x * y + x ■ (VXt ) . . . (Vxn) ((0, X-|, . . . , Xn) A A (VX0) ( - -' =^V0 (A4) ax/'om kvantifikátoru (Vx)(=> (Vx)V'), pokud x není volná ve (A5) ax/'om substituce (yx)(f(x) (f(t), kde (ŕ) vznikne z f(xA,..., x,-_i, x, x,+1,..., xn) = f(Xi,..., X/_i, y, x,+1,..., xn) m x = y => P(xt ,..., x,-_i, x, x,+1,..., x„) P(x1,...,x(_1,y,x(+1,...,xn) IB112 Základy matematiky: Základy matematické logiky 74/76 Axiomatický systém predikátové logiky Odvozovací pravidla (P1) Z (p a (p => V plyne V-(P2) Z plyne (Vx)

, a dokazatelnosti z teorie T, psáno 7" h , se definují podobně jako ve výrokové logice. Věta (Gódelova věta o úplnosti) Pro libovolnou predikátovou formuli (p platí IB112 Základy matematiky: Základy matematické logiky |= íp právě když h