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, …  xN: (x+1)N  pro všechna přirozená čísla x platí…  Existenční kvantifikátor   existuje, některý, …  xN: (x-100)N  existuje přirozené číslo x takové, že…  Zesílený existenční kvantifikátor !  existuje právě jeden, jediný, …  !xN: (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, kN  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 kN, 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