IB112 Základy matematiky Základy matematické logiky Jan Strejček Obsah ■ Výroková logika ■ 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í vety, u které můžeme určit její pravdivost ■ složený výrok je poskládán z atomických výroků a spojek ■ Príklady: ■ venku prší (atomický výrok) ■ jestli budeš do osmiv 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ýroku a logických spojek budovat další výroky. ■ Zkoumá vztahy mezi pravdivostí ruzných výroku. IB112 Základy matematiky: Základy matematické logiky 4/76 Logické spojky Logické spojky = výrazy, kterými z výroků 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írne lišit od významů v bežném jazyce. Napr. "půjdů tam dnes nebo tam půjdů zítra" chápeme tak, že nastane jen jedna eventůalita. notace výraz v ceštine název -A A a B A v B A B AB "není pravda, že A" "A a B" "A nebo B" "jestliže A, tak B" "A práve tehdy, když B" negace konjunkce disjunkce implikace 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) Necht P = {a, b, c,...} je neprázdná množina výrokových symbolů. Výrokové formule nad P definujeme takto: 11 Každá výrokový symbol je výroková formule. 12 Jsou-li A, B výrokové formule, pak i (-A), (A a B), (A v B), (A == B), (A & B) jsou výrokové formule. 12 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 ■ Príklady výrokových formulí: (a == (-b)), (-((-a) v b)), (a a (b o (c == -a))),... ■ Odvození ((a a b) o (c == (-a))): ■ a, b, c jsu 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) o (c == (-a))) je také formule dle bodu 2. ■ Závorky v zápisu formulí casto vynecháváme, pokud tím není dotcena jednoznacnost. Napr. píšeme (a a b) o (c == -a) namísto ((a a b) o (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 nekdy také znací T, F. IB112 Základy matematiky: Základy matematické logiky 8/76 Valuace Definice (Valuace) Necht I je pravdivostní ohodnocení. Valuace I' je funkce přiřazující každé výrokové formuli A pravdivostní hodnotu 1 nebo 0 a spinující: ■ Je-li A atomická formule, pak ľ (A) = I (A). m I'(-A) = 1 pokud I'(A) = 0 a I'(-A) = 0 pokud I'(A) = 1. ■ I'(A A B) = 1 pokud I' (A) = I'(B) = 1. Jinak ľ (A A B) = 0. ■ I'(A v B) = 0 pokud I'(A) = I'(B) = 0. Jinak I'(A v B) = 1. ■ I'(A B) = 0 pokud I'(A) = 1 a I'(B) = 0. Jinak I'(A B) = 1. ■ I'(A ^ B) = 1 pokud I'(A) = I'(B). Jinak I'(A B) = 0. ■ Valuace je pravdivostním ohodnocením urCena jednoznaCne a je jeho rozšírení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á pri žádném ohodnocení. ■ splnitelná, pokud je pravdivá při nejakém ohodnocení. Formule A, B jsou ekvivalentní, psáno A = B, pokud jsou pravdivé pri stejných ohodnoceních. Příklady ■ tautologie: a v -a, a == a, a o --a, (a a -a) => b ■ kontradikce: a a-a, a o -a ■ ekvivalentní formule: a == b = b v -a IB112 Základy matematiky: Základy matematické logiky 10/76 Příklad Je formule ((a a b) <=> (c == (-a))) pravdivá pri ohodnocení /(a) = 1, /(b) = 0, /(c) = 1? IB112 Základy matematiky: Základy matematické logiky 11/76 Príklad Je formule ((a a b) ^ (c == (-a))) pravdivá při ohodnocení /(a) = 1, /(b) = 0, /(c) = 1? ■ /'(a) = 1, ľ(b) = 0, ľ(c) = 1 ■ ľ (a a b) = 0 ■ /'(-a) = 0 ■ /'(c == (-a)) = 0 ■ /'((a a b) (c == (-a))) = 1 ■ Zadaná formule je pri daném ohodnocení pravdivá. IB112 Základy matematiky: Základy matematické logiky 12/76 Vybrané taůtologie Mnohé taůtologie mají svoje názvy: ■ komůtativní zákony: (a a b) o (b a a), (a v b) o (b v a),... ■ asociativní zákony: ((a a b) a c) o (a a (b a c)),... ■ distribůtivní zákony: (a a (b v c)) o ((a a b) v (a a c)),... ■ zákon vyloůcení třetího: a v -a ■ zákon sporů: -(a a -a) ■ zákon totožnosti: a == a ■ zákon dvojí negace: a o --a ■ idempotence: (a a a) o a, (a v a) o a ■ de Morganovy zákony: -(a a b) o (-a v -b), -(a v b) o (-a A-b) IB112 Základy matematiky: Základy matematické logiky 13/76 Věta o implikaci Věta (Věta o implikaci, sémantický modus poněns) Pokud platí = Aa = A == B, pak platí = B. Důkaz Sporem. Necht' platí = A a = A == B a nechť B není taůtologie. Oznacme I ohodnocení, v kterém B není pravdivé, t.j. I'(B) = 0. Jelikož A je taůtologie, platí ľ (A) = 1. Dohromady dostáváme ľ (A == B) = 0 a proto A == B není taůtologie. 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í) pri všech ohodnoceních. ■ Každý rádek tabulky odpovídá jednomu ohodnocení. ■ Pocet řádku tabulky je 2n, kde n je pocet ruzných atomických formulí v dané formuli. Pravdivostní tabulka pro a == (b == c) a b c a == b (a == b) == c ~0~ 0 0 1 0 0 0 1 1 1 0 1 0 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 0 1 1 1 0 1 0 1 1 1 1 1 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 urcit, zdaje formule: ■ tautologie - ve všech rádcích je pravdivostní hodnota 1 ■ kontradikce - ve všech rádcích je pravdivostní hodnota 0 ■ splnitelná - v nejakém rá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 Príklad ■ Sestrojte pravdivostní tabulku pro formuli a == (b == c). ■ Rozhodnete, zdaje formule tautologie, kontradikce, splnitelná a zdaje 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 Príklad ■ Sestrojte pravdivostní tabůlků pro formůli a == (b == c). ■ Rozhodnete, zdaje formůle taůtologie, kontradikce, splnitelná a zda je ekvivalentní formůli (a = b) = c. a b c b == c a == (b == c) ~0~ 0 0 1 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 0 0 1 1 1 1 1 IB112 Základy matematiky: Základy matematické logiky 18/76 Príklad ■ Sestrojte pravdivostní tabulku pro formuli a == (b == c). ■ Rozhodnete, 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 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 1 1 0 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 i A a B a C. Definice (Literál, konjunktivní klauzule, DNF) Literál je atomická formule nebo její negace. Konjunktivní klauzule je konjunkce libovolného konečného poctu literálu. Formule A je v disjunktivní normální forme (DNF), je-li to jedna klauzule nebo disjunkce konecne mnoha konjunktivních klauzulí. Příklady ■ literály: a, b, -a, -c ■ konjunktivní klauzule: (a a -c a b), (-a a -c a -b a d) ■ formule v DNF: (a a -c a b) v (-a a -c a -b a d) v (-d) 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á, pridá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 -b. ■ Není-li formule pravdivá v žádném ohodnocení, pak je to kontradikce a je ekvivalentní kontradikci (a a -a) a ta je v DNF. a b (a ^ -b) 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á, pridá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 -b. ■ Není-li formule pravdivá v žádném ohodnocení, pak je to kontradikce a je ekvivalentní kontradikci (a A -a) a ta je v DNF. a b (a o -b) 1 1 0 1 0 1 0 1 1 0 0 0 w (a a -b) 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á, pridá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 -b. ■ Není-li formule pravdivá v žádném ohodnocení, pak je to kontradikce a je ekvivalentní kontradikci (a a -a) a ta je v DNF. a b (a o -b) 1 1 0 1 0 1 0 1 1 0 0 0 (a a -b) (-a a b) 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á, pridá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 -b. ■ Není-li formule pravdivá v žádném ohodnocení, pak je to kontradikce a je ekvivalentní kontradikci (a A -a) a ta je v DNF. a b (a o -b) 1 1 0 1 0 1 w (a A-b) Celkem: 0 1 1 w (-a a b) (a o -b) = 0 0 0 (aA-b) 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 poctu literálu. Formule A je v konjunktivní normální forme (CNF), je-li to jedna klouzule nebo disjunkce konecne mnoha klauzulí. Příklady ■ klauzule: (a v -c v b), (-a v -c v -b v d) ■ formule v CNF: (a v -c v b) a (-a v -c v -b v d) a (-d) 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á, pridá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 -b. ■ Je-li formule pravdivá pri všech ohodnoceních, je to tautologie a je ekvivalentní tautologii (a v -a) a ta je v CNF. a b (a ^ -b) 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) 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á, pridá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 -b. ■ Je-li formule pravdivá pri všech ohodnoceních, je to tautologie a je ekvivalentní tautologii (a v -a) a ta je v CNF. a b (a o -b) 1 1 0 1 0 1 0 1 1 0 0 0 IB112 Základy matematiky: Základy matematické logiky 27/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á, pridá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 -b. ■ Je-li formule pravdivá pri všech ohodnoceních, je to tautologie a je ekvivalentní tautologii (a v -a) a ta je v CNF. a b (a o -b) 1 1 0 w (-a v -b) 1 0 1 0 1 1 0 0 0 w (a v b) IB112 Základy matematiky: Základy matematické logiky 28/76 Konjunktivní normální forma (CNF) veta 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á, pridá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 -b. ■ Je-li formule pravdivá pri všech ohodnoceních, je to tautologie a je ekvivalentní tautologii (a v -a) a ta je v CNF. a b (a o -b) 1 1 0 w (-a v-b) 1 0 1 ^^H^^^HI Celkem: 0 1 1 (a o -b) = 0 0 0 w (a v b) (-a v-b) a (a v b) 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 f: {0,1}n {0,1}. ■ Pravdivostní funkce každé n-tici pravdivostních hodnot přiradí jednu pravdivostní hodnotu. ■ Každá formule s n (usporádanými) atomickými formulemi jednoznacřneř urcřuje pravdivostní funkci arity n. ■ Napr. 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ádrit pomocí výrokové formule? ■ Ano. Formuli sestrojíme z tabulky stejne, jako jsme z tabulky vytvorili 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. ■ 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 = -(-A v -B) lze každou konjunkci vyjádřit pomocí v, Proto je úplný i systém {v, ■ Podobne A v B = -(-A a -B) a proto je úplný i systém {a, ■ {=, -} 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 axor 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, Axor B = -(A o 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} tvorí úplné jednoprvkové systémy spojek. ■ Všechny tri spojky jsou v informatice významné. IB112 Základy matematiky: Základy matematické logiky 34/76 Množiny formůlí a vyplývání Definice (Splnitelnost, model, vyplývání) Necht 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žinyT. ■ T = A také cteme jako A je logickým dusledkem T. ■ Z nesplnitelné množiny T vyplývá libovolná formůle. ■ Splnitelnost konecné množiny klaůzůlí T lze rozhodnoůt pomocí pravdivostní tabůlky obsahůjící sloůpce pro všechny formůle z T. Platnost T = A lze rozhodnoůt analogicky. IB112 Základy matematiky: Základy matematické logiky 35/76 Príklad Zjistěte, zda je množina formulí T = {-b v a, -a v c} splnitelná a zda je jejím dUsledkem formule b == c. a b c -b v a -a v c b => c "ČT 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 Príklad Zjistete, zda je množina formulí T = {-b v a, -a v c} splnitelná a zda je jejím dUsledkem formule b == c. a b c -b v a -a v c 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 Príklad Zjistěte, zda je množina formulí T = {-b v a, -a v c} splnitelná a zda je jejím dUsledkem formule b == c. a b c -b v a -a v c 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 dusledkem T. IB112 Základy matematiky: Základy matematické logiky 38/76 Věta o dedukci a lemma o neutrální formuli Veřta (Veřta o dedukci, sémantická varianta) Bud' T množina výrokových formulí. Pak platí T = A => B práve když T u {A} = B. Veta (Lemma o neutrální formuli, sémantická varianta) Bud' T množina výrokových formulí. Pokud platí T u {A} = Ba T u {-A} = B, pak i T = B. IB112 Základy matematiky: Základy matematické logiky 39/76 Formální systémy ■ Pravdivost formulí lze zkoumat i na základe jejich syntaxe (bez interpretací, bez pravdivostních tabulek). Formální systém ■ umožnuje k formulím budovat důkazy ■ skládá se z ■ axiomů - tvrzení, jejichž pravdivost prijmeme bez dukazu ■ odvozovacích pravidel - konstrukce umožnující vytvářet dukazy ■ muže být ■ axiomatický - méne pravidel, více axiomu ■ předpokladový - více pravidel, méne axiomu ■ Ukážeme axiomatický systém pro výrokovou logiku využívajících pouze spojek == a IB112 Základy matematiky: Základy matematické logiky 40/76 Axiomatický systém Axiomy (A1) A == (B == A) (A2) (A == (B == C)) == ((A == B) == (A == C)) (A3) (-B == -A) = (A == B) Odvozovací pravidlo (P1) Z A a A = B plyne B. ■ A, B, C jsou libovolné výrokové formule. ■ Odvozovací nebo také inferenCnípravidlo (P1) se nazývá pravidlo odloůCení nebo modůs ponens. m V (P1) se formule A a A == B nazývají předpoklady, B se pak nazývá záver. ,r,-N - ■ ■ ■ i A A == B ■ (P1) se casto zapisuje jako---. B IB112 Základy matematiky: Základy matematické logiky 41/76 D u kaz Definice (Dukaz) KoneCnou posloupnost A1, A2,..., An výrokových formulí nazveme dukazem formule An, pokud pro každé i < n je Ai bud' axiomem nebo záverem odvozovacího pravidla, jehož predpoklady jsou mezi formulemi A1, A2,..., Ai —. Výroková formule A je dokazatelná, psáno - A, pokud existuje duukaz formule A. IB112 Základy matematiky: Základy matematické logiky 42/76 Príklad Dokažte A A. IB112 Základy matematiky: Základy matematické logiky 43/76 Príklad Dokažte h A == A. Řešení Dukazem je posloupnost A = ((A = A) = A), (A = ((A = A) = A)) = ((A = (A = A)) = (A = A)), (A = (A = A)) = (A = A), A = (A = A), A = A. Oznacíme-li formule v posloupnosti A1, A2A5, pak ■ A1 je (A1) pro volbu A, A == A za A, B, m A2 je (A2) pro volbu A, A == A, A za A, B, C, ■ A3 je záver (P1) s předpoklady A1, A2, ■ A4 je (A1) pro volbu A, A za A, B, m A5 je záver (P1) s předpoklady A3, A4. IB112 Základy matematiky: Základy matematické logiky 44/76 Zobecnení dokazatelnosti Definice Necht T je množina výrokových formulí. Konetcnou posloupnost A1, A2,..., An výrokových formulí nazveme dukazem formule An z T, pokud pro každé i < n je Ai bud' axiomem, prvkem T nebo záverem odvozovacího pravidla, jehož predpoklady jsou mezi formulemi A1, A2,..., Ai-1. Píšeme T - An m- A je totéž jako $- A. m Místo {A} - B píšeme pouze A - B. IB112 Základy matematiky: Základy matematické logiky 45/76 Věta o dedukci a lemma o neutrální formuli Veřta (Veřta o dedukci) Bud' T množina výrokových formulí. Pak platí T - A = B práve když T U {A}- B. Důkaz ji Smer "=>". Platí-li T - A == B, pak existuje dukaz A1, A2, . . . , An, A = B formule A = B z T. Pak ale A1, A2,..., An, A == B, A, B je dukaz formule B z T u {A}. ^| Dukaz "<$=" je komplikovanejší... □ IB112 Základy matematiky: Základy matematické logiky 46/76 Príklad Platí J h-A = (A = B), % h = A, " h (A = B) = (-B = -A), " h A = (-B = -(A = B)), % h (-A = A) = A. Důkaz Ukážeme (1), ostatní se lze dokázat podobne. Z (A1) plyne h-A = (-B = -A). m Z Vety o dedůkci dostáváme -A \—B == -A. m Z (A3) plyne h (-B = -A) = (A = B). m Pomocí modůs ponens tedy dostáváme -A h A == B. ■ Z Vety o dedůkci dostaneme h -A == (A == B). □ IB112 Základy matematiky: Základy matematické logiky 47/76 Vlastnosti axiomatického systému Veřta (Lemma o neutrální formuli) Bud' T množina výrokových formulí. Pokud platí T u {A} - Ba T u {-A} - B, paki T - B. Důkaz Postupneř dokážeme jj T - -A == B z Vety o dedukci, ^ T - -B == aplikací (P1) na (3) v předchozím príkladu a (1), ^ T u {-B} - z Vety o dedukci, ^ T u {-B} - A aplikací (P1) na (2) v predchozím příkladu a (3), ^ T - A == B z předpokladu a Vety o dedukci, ^ T u {-B} - B z (P1) a predcházejících dvou tvrzení, J T - -B == B z Vety o dedukci, ^ T - B aplikací (P1) na (5) v předchozím příkladu a (7). □ IB112 Základy matematiky: Základy matematické logiky 48/76 Korektnost a úplnost Veta (Korektnost a úplnost) Necht T je množina výrokových formulí a A je výroková formule. Pak platí T h A práve tehdy, když T |= A. ■ Implikace "=>" se nazývá korektnost (co dokážeme to platí). ■ K dukazu korektnosti stací ukázat, že (A1), (A2) i (A3) jsou pravdivé a že (P1) z pravdivých predpokladu odvodí vždy pravdivý záver. ■ Implikace "«=" se nazývá úplnost (dokážeme vše, co platí). ■ Existují i další formální systémy pro výrokovou logiku (napr. Gentzenovský systém). IB112 Základy matematiky: Základy matematické logiky 49/76 Predikátová logika IB112 Základy matematiky: Základy matematické logiky 50/76 Predikátová logika ■ Rozšiřuje výrokovou logiku. ■ Umožnuje presneji popsat výrok a díky tomu odvodit logická vyplývání, která ve výrokové logice odvodit nelze: ■ Každý clovek je smrtelný. ■ Sokrates je clovek. ■ Sokrates je smrtelný. ■ Výroky oznaccíme postupne a, b, c. Ve výrokové logice nelze odvodit logické vyplývání c z a, b, přestože c zjevne je dusledkem a, b. IB112 Základy matematiky: Základy matematické logiky 51/76 Jazyk predikátové logiky Jazyk predikátové logiky se zkládá z techto symbolu: ■ promenné: x,y,z,x1,x2,... m logické spojky: a, v, ==, m kvantifikátory: V (pro všechna), 3 (existuje) ■ rovnost: = m závorky: (,) ■ relacní neboli predikátové symboly: P, Q, R, P1, P2,... m funkcnísymboly: f,g,h, f1, f2,... m Každý predikátový symbol má pevne danou arity n > 0. ■ Každý funkcní symbol má pevne danou aritu n > 0 (pocet argumentu). ■ Funkce s aritou 0 se nazývají konstanty a znací se a, b, c,.... IB112 Základy matematiky: Základy matematické logiky 52/76 Konstanty, promenné a funkce ■ Konstanty, promenné i funkce slouží k oznacení objektů. ■ Objekty jsou prvky dané množiny objektu nazývané doména nebo univerzům. ■ Konstanty jsou vlastne jména objektu. ■ Promenné zastupují libovolné objekty. ■ Pomocí funkcí vytváríme složená jména objektu. Příklad ■ Uvažujme doménu nezáporných celých ccísel. ■ Konstanty jsou napr. 0,1, 42. ■ Príkladem binární funkce (funkce arity 2) je +. ■ Složené jméno objektu 3 je naprí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 jsoů všechna možná oznacení objektů. Definice (Termy) Termy definujeme takto: 11 Každá promenná je term. 12 Je-li f funkcní symbol arity n a t1, t2,..., tn jsou termy, pak i f (t1, t2,..., tn) je term. 12 Nic jiného není term. ■ Z bodů (2) plyne, že konstanty (nůlární fůnkce) jsoů také termy. ■ Prí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. ■ Prí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 mezidvema objekty. ■ Príklad: "x je násobek y" ~» Q(x, y) "x + 3 je násobek 2" ~» Q(x + 3,2) "x je 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) ríká, že pro všechny objekty x z domény platí P (x). ■ Pro konecnou doménu {a1, a2,..., an} je (Vx)P (x) ekvivalentní formuli P (a1) a P (a2) a ... a P (an). 3 - existenciální kvantifikátor ■ (3x)P(x) říká, že existuje (alespon jeden) objekt x z domény, pro který platí P(x) (neboli P(x) platí pro neřkteré objekty x). ■ Pro konecnou doménu {a1,a2,...,an} je (3x)P(x) ekvivalentní formuli P (a1) v P (a2) v ... v P (an). Prří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) ríká, že existuje smrtelný clovek (neboli nekterí 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: |1| Necht P je predikátový symbol arity n at1,..., tn jsou termy. Pak P(t1 , . . . , tn) je atomická predikátová formule. B Jsou-li t1, t2 termy, pak t1 = t2 je atomická predikátová formule. 13 Nic jiného není atomická predikátová formule. Predikátové formule definujeme takto: 11 Každá atomická predikátová formule je predikátová formule. 12 Jsou-li p, p predikátové formule, pak i -p, p v tp,p a tp,p :• p,p p jsou predikátové formule. |3| Je-li x promenná a p predikátová formule, pak (Vx)p a (3x)p jsou predikátové formule. M Nic jiného není predikátová formule. IB112 Základy matematiky: Základy matematické logiky 57/76 Přríklady Příklad No s elementární aritmetikou: konstanta 0, unární funkce následník s, binární funkce +, * ■ termy: s(0) reprezentuje 1, s(x) + s(s(0)) reprezentuje (x +1) + 2 ■ (Vx) 0 * x = 0 ... nula krát cokoliv je nula ■ (Vx) s(0) * x = x ... jedna krát libovolné ccíslo je totéž ccíslo ■ -(3x) s(x) = 0 ... v dané doméne nemá nula předchudce Prříklad ■ Necht R je binární predikát reprezentující binární relaci. ■ (Vx) R(x, x) ... R je reflexivní ■ (Vx)(Vy) (R(x, y) == R(y, x)) ... R je symetrická ■ (Vx)(Vy )(Vz) ((R(x, y) a R (y, z)) == R(x, z)) ... R je tranzitivní IB112 Základy matematiky: Základy matematické logiky 58/76 Vázaný a volný výskyt promeenných ■ Podformule formule p je každá souvislá cást p, která je také formulí. ■ Podformule ip ve formulích (Vx)ip a (3x)ip se nazývá oborem nebo rozsahem kvantifikátoru (fx) nebo (3x). ■ Výskyt promenné x ve formuli p je vázaný, je-li v rozsahu nejakého kvantifikátoru (fx) nebo (3x). ■ Výskyty, které nejsou vázané, jsou volné. ■ Príklad: ((fx)(3y)P (x, y, z)) == R (x, z) .. .vázaný/volný výskyt ■ Promenná se nazývá volná (resp. vázaná), existuje-li v dané formuli její volný (resp. vázaný) výskyt. ■ Formule bez volných promenných se nazývá sentence neboli uzavřená formule. ■ Formule bez kvantifikátoru se nazývá otevřená formule. ■ Zápis ^(x1, x2,..., xn) oznacuje formuli

V domény D definovaný dle tvaru termu takto: m Je-li t promenná x, pak |t |/>V = V (x). ■ Je-li t tvaru f(t1, t2,..., tn), pak |t|/,V = 1 (f) (|t1 |/,V, |t2|/,V, . . . , |tn|/,V). ■ Hodnota promenné je tedy prímo dána valuací této promenné. ■ Hodnotu termu f(t1, t2,..., tn) získáme tak, že vezmeme hodnoty termu t1, t2,..., tn a na tyto hodnoty aplikujeme funkci /(f) přiřazenou symbolu f interpretací /. ■ Hodnota termu závisí pouze na valuaci promenných, které se v termu vyskytují. IB112 Základy matematiky: Základy matematické logiky 62/76 Príklad Urcete hodnotu termu s(s(0)) * s(x + s(0)) při dríve definované interpretaci I a valuaci V (x) = 7. IB112 Základy matematiky: Základy matematické logiky 63/76 Príklad Urcete hodnotů termů s(s(0)) * s(x + s(0)) při dříve definované interpretaci I a valůaci V (x) = 7. ■ | 0 | i,v = 1(0) = 0 ■ | s(0) | i,v = I(s)( 10 | i,v ) = I(s)(0) = 0 + 1 = 1 ■ |s(s(0))|i,v = Ks^smiy) = I(s)(1) = 1 + 1 = 2 ■ ^(x + s^iy = I(s)(V(x) + 1) = I(s)(7 + 1) = 8 + 1 = 9 ■ ^(s(0)) * s(x+s(0))||,v = ^(s^Iy-^(x+s(0))||,v = 2 • 9 = 18 IB112 Základy matematiky: Základy matematické logiky 64/76 Príklad Urcete hodnotu termu s(s(0)) * s(x + s(0)) při dříve definované interpretaci I a valuaci V (x) = 7. ■ \0\i,v = 1(0) = 0 ■ \s(0)\i,v = I(s)(\0\i,v ) = I(s)(0) = 0 + 1 = 1 ■ \s(s(0))\i,v = I(s)(\s(0)\i,v) = I(s)(1) = 1 + 1 = 2 ■ \s(x + s(0))\i,v = I(s)(V(x) + 1) = I(s)(7 + 1) = 8 + 1 = 9 ■ \s(s(0)) * s(x+s(0))\i,v = \s(s(0))\i,v-\s(x+s(0))\i,v = 2 • 9 = 18 Totéž pri interpretaci ľ a valuaci V'(x) = b. IB112 Základy matematiky: Základy matematické logiky 65/76 Príklad Urcete hodnotu termu s(s(0)) * s(x + s(0)) pri dríve definované interpretaci I a valuaci V (x) = 7. ■ | 0 | i,v = 1(0) = 0 ■ | s(0) | i,v = I(s)( 10 | i,v ) = I(s)(0) = 0 + 1 = 1 ■ |s(s(0))|/,v = I(s)(\s(0)\i,v) = I(s)(1) = 1 + 1 = 2 ■ |s(x + s(0))\i,v = I(s)(V(x) + 1) = I(s)(7 + 1) = 8 + 1 = 9 ■ \s(s(0)) * s(x+s(0))\i,v = Is(s(0))Ii,v-\s(x+s(0))\i,v = 2 • 9 = 18 Totéž pri interpretaci ľ a valuaci V'(x) = b. m \s(x + s(0))\ľ,v = ľ(s)(a) = b m \s(s(0)) * s(x + s(0))\ľ,v = b IB112 Základy matematiky: Základy matematické logiky 66/76 Sémantika predikátové logiky V [x /d] znací valuaci lišící se od V pouze tím, že promenné x prřiřrazuje prvek d. Definice (Pravdivost predikátové formule) Formule p je pravdivá pri interpretaci I a valuaci V, psáno I, V = p, pokud p je tvaru ■ P(ŕ|, t2, . . . , tn) a ( | ŕ| | ItV, | t2 | I,V, . . . , | tn| ItV) £ I(P), ■ t1 = t2 a \t1 \I,V = | t2 |I,V m —p a I, V = p, m p1 v p2 a I, V = p1 nebo I, V = p2, ■ P1 a p2 a I, V = p1 a I, V = p2, ■ p1 => p2 a I, V = p1 nebo I, V = p2, ■ p1 ^ p2 a I, V = p1 a I, V = p2, nebo I, V = p1 a I, V = p2, ■ (Vx )p a I, V [x/d] = p pro každé d z domény D. m (3x )p a I, V [x/d] = p pro nejaké d z domény D. IB112 Základy matematiky: Základy matematické logiky 67/76 Pravdivost formule ■ Snadno se oveří, že pravdivost formule p pri interpretaci I a valuaci V záleží pouze na valuaci promenných, které jsou volné ve p a na interpretaci symbolu použitých ve formuli p. ■ Z toho okamžite plyne, že pravdivost sentencí vubec nazáleží na valuaci. Definice Predikátová formule p se nazývá ■ pravdivá pri interpretaci I, psáno I = p, jestliže p je pravdivá při interpretaci I a všech valuacích V. ■ pravdivá nebo tautologie, psáno = p, jestliže je pravdivá při všech interpretacích. m splnitelná, jestliže je pravdivá při nejaké interpretaci. IB112 Základy matematiky: Základy matematické logiky 68/76 Príklad Zjistete, zda je formule

(x) ^ (Vx)-^(x) ■ zaměnitelnost kvantifikátorů stejného typu: (Vx)(VyMx,y) ^ (Vy)(Vx)^(x,y), (3x)(3yMx, y) ^ (3y)(3xMx, y) ■ distributa kvantifikátorů: (Vx)(p(x) A V(x)) (Vx)^(x) A (Vx)^(x), (3x)(p(x) V ^(x)) ^ (3x)p(x) V (3x)^(x) ■ redukce univerzálního kvantifikátoru: (Vx)(VyMx, y) (VyMy, y) ■ (Vx)p(x) (3x)p(x) IB112 Základy matematiky: Základy matematické logiky 71/76 Teorie, model, důsledek Definice (Teorie, model, důsledek) Množina sentencí T se nazývá teorie. Interpretace I se nazývá model teorie T, jestliže I = p pro každé p e T. Formule p logicky vyplývá z teorie T (ip je důsledkem T), psáno T = ip, pokůd je ip pravdivá v každém modelů teorie T. Teorie T je sporná, pokůd nemá žádný model. V opaCném případe je teorie bezesporná. Prříklad ■ Formální zápis Sokratovy úvahy: {(Vx)((x) => S(x)), (Sokrates)} = S(Sokrates) IB112 Základy matematiky: Základy matematické logiky 72/76 Príklad teorie - Peanova aritmetika ■ Peanova aritmetika popisuje základy teorie císel. ■ Jazyk obsahuje konstantu 0, unární funkcní symbol s (následník), binární funkcní symboly + a *. ■ (Vx)-(0 = s(x)) m (Vx)(((y)(s(x) = s(y) = x = y) m (i x) x + 0 = x m (Vx)((Jy) x + s(y) = s(x + y) m ((x) x * 0 = 0 ■ (ix)(yy) x * s(y) = x * y + x M (\(x1) ... ((xn)(