Predikátová logika Teoretické základy informatiky. ZS 2008/09 2 Úvod Nestačí zkoumat vlastnosti jediného objektu Potřebujeme se ptát, zda danou vlastnost má z dané množiny alespoň jeden prvek každý prvek Příklady výroků, které nelze formalizovat výrokovou logikou Každé prvočíslo je liché Existuje dívka, která je chytrá a zároveň krásná Teoretické základy informatiky. ZS 2008/09 3 Kvantifikátory Univerzální kvantifikátor každý, všechny, ... xN: (x+1)N pro všechna přirozená čísla x platí... Existenční kvantifikátor existuje, některý, ... xN: (x-100)N existuje přirozené číslo x takové, že... Zesílený existenční kvantifikátor ! existuje právě jeden, jediný, ... !xN: (x-1)N existuje jediné přirozené číslo x, pro které... Teoretické základy informatiky. ZS 2008/09 4 Formální jazyk predikátové logiky Individuální jména (konstanty) označují konkrétní objekt a, b, c, ... Individuální proměnné neoznačují konkrétní objekt, mají svůj definiční obor x, y, z, ... Funkční symboly přiřazují prvkům definičního oboru jiné prvky f, g, h, ... Predikátové symboly označují vlastnosti a vztahy P, Q, R, ... Logické spojky , , , , Kvanitifikátory , Závorky Teoretické základy informatiky. ZS 2008/09 5 Arita (četnost) = počet operandů/parametrů/argumentů Podle počtu operandů rozlišujeme operátory na nulární unární binární ternární ... +,-,*,/, ,,, jsou binární operátory jejich arita je 2, mají 2 operandy) , jsou unární operátory jejich arita je 1, mají 1 operand Teoretické základy informatiky. ZS 2008/09 6 Term Term označuje prvek definičního oboru Každá konstanta je term Každá individuální proměnná je term Je-li f funkční symbol arity n a t1, t2, ... tn jsou termy, pak f(t1, t2, ... tn) je rovněž term Nic jiného není term Teoretické základy informatiky. ZS 2008/09 7 Formule predikátového kalkulu Výsledkem formule bude logická hodnota (pravda/nepravda) Je-li P predikátový symbol arity m a t1, t2, ... tm jsou termy, pak P(t1, t2, ... tm) je (atomická) predikátová formule. Jsou-li , predikátové formule, pak i (), (), (), (), () jsou predikátové formule Je-li predikátová formule a x individuální proměnná, pak i (x), (x) jsou predikátové formule Nic jiného není predikátová formule Teoretické základy informatiky. ZS 2008/09 8 Příklad jazyka predikátové logiky Pracujeme s množinou lidí Konstanty (konkrétní lidé) p = Pavel, r = Radka Funkční symboly o(x) = otec člověka x m(x) = matka člověka x Predikátové symboly k(x) = x umí hrát na kytaru (x, y) = x má rád y Příklady formalizovaných predikátových výroků Pavel má rád Radku: (p, r) Pavlův otec umí hrát na kytaru: k(o(p)) Pavlova matka má ráda Radčina otce: (m(p), o(r)) Radka má ráda každého, kdo umí hrát na kytaru: (x)(k(x)(r,x)) Všichni mají rádi Pavla: (x)(x,p) Existuje člověk, který má rád všechny, kteří umí hrát na kytaru: (x)(y)(k(y)(x,y)) Teoretické základy informatiky. ZS 2008/09 9 Volný a vázaný výskyt proměnné Def: Řekneme, že výskyt proměnné x je vázáný, nachází-li se proměnná x v nějaké podformuli formule tvaru (x) nebo (x) Def.: Podformule z předchozí definice se nazývá obor (platnosti) kvantifikátoru Výskyt proměnné je tedy vázaný, je-li v oboru platnosti nějakého kvantifikátoru Def.: Výskyt proměnné, který není vázaný, se nazývá volný. Jedna proměnná může mít ve formuli jak volný, tak vázaný výskyt! Def.: Formule, která neobsahuje volné proměnné, se nazývá uzavřená. Def.: Forumule, která není uzavřená, se nazývá otevřená. Teoretické základy informatiky. ZS 2008/09 10 Sémantika predikátové logiky Též hovoříme o realizaci PL Dosud definované objekty (termy, formule...) popisovaly pouze syntaxi Sémantika svazuje jazyk s objekty reálného světa Definujeme univerzum, tedy množinu objektů, jejichž vlastnosti zkoumáme Funkční symboly odpovídají zobrazením na univerzu Predikátové symboly popisují vlastnosti a vztahy prvků univerza Teoretické základy informatiky. ZS 2008/09 11 Ohodnocení proměnných Def.: Libovolné zobrazení z množiny všech proměnných do univerza nazveme ohodnocení proměnných. Ohodnocení proměnných tedy každé proměnné přiřadí prvek univerza (=hodnotu) Ohodnocení proměnné x prvkem m značíme e(x) = m e(x/m) Teoretické základy informatiky. ZS 2008/09 12 Hodnota termu Term je definován induktivně, tedy i jeho hodnota bude definována induktivně Hodnotu termu t při ohodnocení proměnných e značíme t[e] t[e] = e(x), je-li t proměnná x t[e] = f(t1[e], ..., tn[e]), kde f je n-ární funkční symbol aplikovaný na termy t1... tn. Příklad: Hodnota termu x+y bude při ohodnocení proměnných e(x)=1, e(y) = 2 rovna e(x)+e(y)=1+2=3. Teoretické základy informatiky. ZS 2008/09 13 Pravdivost atomické formule Víme, že atomická predikátová formule vzniká aplikací n-árního predikátového symbolu na n termů V konkrétní realizaci predikátové logiky pak dokážeme určit, zda je konkrétní predikát pravdivý či nikoliv Predikáty svým způsobem odpovídají tomu, co byly výroky ve výrokové logice Unární predikát je tedy pravdivý právě tehdy, když prvek, jenž je hodnotou termu, který je argumentem daného predikátového symbolu, má požadovanou vlastnost. Predikát vyšší arity je pak pravdivý právě tehdy, když hodnoty vstupních termů splňují vlastnosti (vztahy) požadované při definici významu predikátu. Teoretické základy informatiky. ZS 2008/09 14 Pravdivost formule I. Formule je definována induktivně, tedy i pravdivost formule bude definována induktivně: Jsou-li , formule, x je proměnná, pak () je pravdivá právě tehdy, když je nepravdivá a naopak () je pravdivá právě tehdy, když jsou obě formule , současně pravdivé Analogicky ostatní spojky: (), (), () Viz pravdivostní tabulky ve výrokové logice (x) je pravdivá tehdy, jestliže je formule pravdivá při libovolném ohodnocení proměnné x Tedy za x si můžeme dosadit libovolný prvek univerza a formule musí být pravdivá (x) je pravdivá tehdy, jestliže existuje takové ohodnocení proměnné x, při němž je formule pravdivá. Tedy stačí, abychom našli jediný prvek univerza, který při dosazení za x způsobí pravdivost formule Teoretické základy informatiky. ZS 2008/09 15 Pravdivost formule II. Pravdivost uzavřené formule je určena jednoznačně v závislosti na realizaci jazyka Pravdivost formule tedy závisí pouze na ohodnocení volných proměnných Def.: Formule se nazývá logicky platná (též tautologie), jestliže je pravdivá při libovolné realizaci jazyka PL Def.: Formule se nazývá logicky neplatná (též kontradikce), jestliže není pravdivá při žádné realizaci jazyka PL Def.: Formule se nazývá splnitelná, jestliže existuje alespoň jedna realizace, v níž je pravdivá. Teoretické základy informatiky. ZS 2008/09 16 Příklady tautologií PL Všechny tautologie výrokové logiky jsou i tautologiemi v predikátové logice (x)P(x) (x)P(x) (x)P(x) (x)P(x) Pravidla pro negování predikátových formulí (x)(y)P(x,y) (y)(x)P(x,y) (x)(y)P(x,y) (y)(x)P(x,y) Na pořadí týchž kvantifikátorů nezáleží Na pořadí různých kvantifikátorů záleží Nelze rozhodnout konečným algoritmem, zda je daná formule tautologie Protože univerzum může být nekonečná množina Teoretické základy informatiky. ZS 2008/09 17 Negace predikátových formulí Pravidla pro negování logických spojek zůstávají v platnosti (a b) (a b) (a b) (a b) (a b) (a b) (a b) ((a b) (b a)) Nová pravidla pro negování kvantifikátorů (x)P(x) (x)P(x) (x)P(x) (x)P(x) Teoretické základy informatiky. ZS 2008/09 18 Příklady negací Negujte formuli (x)(P(x)Q(x)) Řešení: (x)(P(x)Q(x)) (x) (P(x)Q(x)) (x)(P(x)Q(x)) Negujte formuli (x)P(x) (y)Q(y) Řešení: (x)P(x)(y)Q(y) (x)P(x)(y)Q(y) Negujte formuli: ()()(P()Q()) Řešení: ()()(P()Q()) ()()(P()Q()) ()()(P()Q()) Vyslovte negace následujících přísloví: Kdo jinému jámu kopá, sám do ní padá. Komu není rady, tomu není pomoci. Kdo o kom před tebou, ten o tobě za tebou Teoretické základy informatiky. ZS 2008/09 19 Existenční a univerzální uzávěr predikátové formule Def.: Nechť je otevřená formule PL a x1, x2, ... xn jsou všechny její volné proměnné. Pak formuli (x1)(x2)...(xn) nazveme existenční uzávěr formule (x1)(x2)...(xn) nazveme univerzální uzávěr formule Vlastnosti existenčního a univerzálního uzávěru: Existenční i univerzální uzávěry jsou uzavřené formule PL Formule je splnitelná, je-li splnitelný její existenční uzávěr Formule je kontradikcí, není-li splnitelný její existenční uzávěr Formule je tautologií, je-li její univerzální uzávěr tautologií. Teoretické základy informatiky. ZS 2008/09 20 Typické úlohy predikátové logiky Najděte takové ohodnocení proměnných, pro něž je (otevřená) formule pravdivá Univerzum U = {1,2,3,4} P(x,y) = (x 13) Vyjdeme z předpokladu, že x 2 a postupně dojdeme k závěru, že 6x+3>13 x 2 6x 12 6x + 1 12 + 1 6x + 1 13 6x + 3 > 13 Teoretické základy informatiky. ZS 2008/09 36 Nepřímý důkaz Nepřímý důkaz je přímé dokázání obměny implikace Příklad: Dokažte, že pro všechna celá čísla platí: je-li n2 liché, pak i n je liché. (n)(L(n2)L(n)) Obměna: (n)(S(n)S(n2)) Což je snadné dokázat Teoretické základy informatiky. ZS 2008/09 37 Důkaz sporem Předpokládáme neplatnost dokazovaného tvrzení a poté přímým důkazem (tj. nezpochybnitelnými implikacemi) dojdeme k evidentní kontradikci. Dokazovaná věta tudíž musí (za předpokladu bezespornosti teorie) platit Teoretické základy informatiky. ZS 2008/09 38 Důkaz sporem - příklad Dokažte, že pro všechna celá čísla platí: jeli n2 liché, pak i n je liché. (n)(L(n2)L(n)) Vyslovíme negaci dokazovaného tvrzení (n)(L(n2)S(n)) Protože ale S(n) n = 2k, kN n2 = (2k)2 = 2*2*k2 S(n2) Dostáváme tedy spor L(n2) S(n2) Negace věty nemůže platit, musí tedy platit dokazovaná věta Teoretické základy informatiky. ZS 2008/09 39 Důkaz matematickou indukcí Používá se při důkazu tvrzení platného pro všechna přirozená čísla Tvrzení dokážeme pro první prvek Dokážeme, že platí-li pro nějaký prvek, platí i pro jeho následníka Tím pádem víme, že platí pro všechny prvky Teoretické základy informatiky. ZS 2008/09 40 Matematická indukce - příklad Dokažte, že pro všechna přirozená čísla platí 1+2+...+n = n(n+1)/2 Dokážeme platnost pro n = 1: 1 = 1*2/2 = 1 Dokážeme, že platí-li tvrzení pro kN, platí i pro k+1 1+2+...+k = k(k+1)/2 1+2+...+k+(k+1) = (k+1)(k+2)/2 Upravujeme výraz na pravé straně implikace 1+2+...+k+(k+1) = (k+1)(k+2)/2 k(k+1)/2 + (k+1) = (k+1)(k+2)/2 k/2 + 1 = (k+2)/2 k + 2 = k + 2 Implikace je tedy pravdivá Uvedené tvrzení platí pro všechna přirozená čísla Teoretické základy informatiky. ZS 2008/09 41 Konstrukční důkaz Máme-li dokázat existenci určitého objektu, zkonstruujeme jej Příklad: Dokažte, že existuje pravoúhlý trojúhelník s celočíselnými délkami stran. Důkaz: Na základě Pythagorovy věty můžeme větu přeformulovat jako a,b,c N: a2 + b2 = c2 Pak snadno ukážeme, že pro a = 3, b = 4 a c = 5 uvedené tvrzení platí Teoretické základy informatiky. ZS 2008/09 42 Ryze existenční důkaz Dokážeme existenci požadovaného objektu, aniž bychom jej museli konstruovat Příklad: Je dán bílý čtverec 10x10cm a v něm je 101 bodů obarveno na červeno. Dokažte, že při libovolném obarvení těchto bodů existuje trojúhelník s obsahem 1cm2 který obsahuje alespoň dva červené body. Důkaz: Obsah čtverce je 100cm2, obsah trojúhelníka je 1cm2. Do čtverce lze vepsat právě 100 trojúhelníků. Kdyby v každém z nich byl 1 červený bod, museli bychom 101. bod umístit do trojúhelníka, kde už jeden červený bod je. Použili jsme tzv. Dirichletův princip