Predikátová logika Luboš Popelínský E-mail: popel@fi.muni.cz http://nlp.fi.muni.cz/uui/ Obsah: • Predikátová logika • Základní pojmy. Syntax • Sémantika predikátové logiky • Normální formy v predikátové logice Úvod do umělé inteligence 7/12 1/16 Predikátová logika Predikátová logika • plně přejímá výsledky výrokové logiky • zabývá se navíc strukturou jednotlivých jednoduchých výroků - na základě této analýzy lze odvodit platnost některých výroků, které ve výrokové logice platné nejsou Příklad: mějme následující výroky (+ označení výrokovými symboly): Každý člověk je smrtelný, (p) Sokrates je člověk, (q) Sokrates je smrtelný, (r) Na základě výrokové logiky nevyplývá r z p a q; přesto je úsudek zřejmě platný (na jiné úrovni, než je výroková logika). Úvod do umělé inteligence 7/12 2/16 Základní pojmy. Syntax Základní pojmy. Syntax • Predikát je n-ární relace; vyjadřuje vlastnosti objektů a vztahy mezi objekty. • konstanty reprezentují jména objektů (individuí); jedná se o prvky předem specifikované množiny hodnot - domény 9 proměnné zastupují jména objektů, mohou nabývat libovolných hodnot z dané domény • n-ární predikáty lze chápat jako množiny takových n-t\c konstant, pro které je predikát splněn • příklady: doména: přirozená čísla s nulou predikát x < 4 lze chápat jako {0,1, 2, 3} doména: {0,1, 2} predikát x < y lze chápat jako {(0,1), (1, 2), (0, 2)} Úvod do umělé inteligence 7/12 3/16 Základní pojmy. Syntax Funkce, termy. Kvantifikátory 9 funkce reprezentují složená jména objektů o příklad: nechť funkce f(x,y) reprezentuje sčítání. Pak f(1,2) (stejně jako f (2,1), ŕ(0, 3)) jsou možná složená jména pro konstantu 3. • poznámka: konstanty jsou nulární funkce • výrazy složené pouze z funkčních symbolů, konstant a proměnných = termy. Příklad termu: /r(x,g'(y,/7(x,y), l),z) • termy nabývaj9 hodnot z dané domény • např. pro doménu přirozených čísel s nulou term 2 + (2 * x) může nabývat hodnot z množiny {2, 4, 6,... } Složené predikáty lze vytvářet i pomocí kvantifikátorů o univerzální (obecný) kvantifikátor V: VxP(x) - pro každý prvek x domény platí P(x) • existenční kvantifikátor 3: 3xP(x) - existuje alespoň jeden prvek x domény, pro který platí P(x) Úvod do umělé inteligence 7/12 4/16 Základní pojmy. Syntax Poznámky k zavedenému formálnímu jazyku 9 pro predikátovou logiku 1. řáduje charakteristické, že jediný přípustný typ proměnných jsou objektové (individuální) proměnné (a pouze ty lze vázat kvantifikátory). V logice druhého řádu jsou povoleny i predikátové proměnné. • konkrétní volbou (konstant), funkčních a predikátových symbolů lze formulovat specifický jazyk, pro který budou jistě platit obecné logické principy. Navíc pro něj mohou platit v závislosti na vlastnostech zvolených prvků i jiné (mimologické) principy, které je ovšem třeba specifikovat pomocí axiomů nebo pravidel. Takový jazyk je pak označován jako jazyk prvního řádu. Příklad - jazyk elementární aritmetiky: zvolené symboly: konstanta 0, unární funkce následník s, binární +, * možné termy: 0, s(0), s(x), (x + y) * 0, (s(s(0)) + (x * y)) * s(0) možné formule: s(0) = (0 * x) + s(0), 3x(y = x * z), Vx((x ŕ 0) 3y(x = s(y))) Úvod do umělé inteligence 7/12 5/16 Základní pojmy. Syntax Vázaný a volný výskyt proměnných • podformule formule A je libovolná spojitá podčást A, která je sama formulí Příklad: formule A = 3x((VyP(z)) =4> P(x,y)) má kromě sebe samé následující podformule: (VyP(z)) =4> P(x,y), VyP(z), P(x,y), P(z) • výskyt proměnné x ve formuli A je vázaný, pokud existuje podformule B formule A, která obsahuje tento výskyt x a začíná Vx, resp. 3x. Výskyt proměnné je volný, není-li vázaný. Příklad: výskyt proměnné x v předchozí formuli A je vázaný (hledanou podformulí je celá A), proměnné y a z jsou volné 9 proměnná x se volně vyskytuje v A, má-li tam alespoň jeden volný výskyt • sentence predikátové logiky je formule bez volných výskytů proměnných (všechny výskyty všech proměnných jsou vázané) • otevřená formule je formule bez kvantifikátorů Úvod do umělé inteligence 7/12 6/16 Základní pojmy. Syntax Substituce proměnných • ,skutečnými proměnnými\ za které lze dosadit (udělit jim hodnotu, provést substituci), jsou pouze volné proměnné • term ŕ je substituovatelný za proměnnou x ve formuli A, pokud pro každou proměnnou y obsaženou v t neobsahuje žádná podformule A tvaru VyB, 3yB volný výskyt proměnné x 9 je-li t substituovatelný za x v A, označíme A(x/ť) výraz, který vznikne z A nahrazením každého volného výskytu x termem ŕ • příklad: ve formuli A — 3xP(x,y) je možné provést například následující substituce: A(y/z) = 3xP(x,z), A(y/2) = 3xP(x,2), /4(y//r(z, z)) = 3xP(x, f (z, z)). Není však možné substituovat /4(y//r(x, x)) = 3xP(x, /^Xjx)), protože by došlo k nežádoucí vazbě proměnných. Úvod do umělé inteligence 7/12 7/16 Sémantika predikátové logiky Sémantika predikátové 1 logil ky • pro analýzu sémantiky potřebujeme nejprve specifikaci jazyka (doména, konstanty, funkční a predikátové symboly) o příklad: formální jazyk s jediným binárním predikátovým symbolem P(x,y) a jediným binárním funkčním symbolem f (x, y) lze chápat mj. jako ■ přirozená čísla s < a + ■ racionálni čísla s > a max ■ celá čísla s > a * • interpretace (realizace) jazyka predikátové logiky je struktura / složená z ■ libovolné neprázdné množiny D (domény, oboru interpretace) ■ zobrazení /(/") : D"D pro každý n-ární funkční symbol f, n > 0 ■ A7-ární relace /(P) C D" pro každý n-ární predikátový symbol P, n > 1 Úvod do umělé inteligence 7/12 8/16 Sémantika predikátové logiky Interpretace jazyka: přík ;lac 1 Příklad: mějme jazyk s binárním predikátovým symbolem P(x,y), binárním funkčním symbolem f(x,y) a symboly pro konstanty a, 3i, a2,..., bi, i>2,..., který chceme interpretovat jako celá čísla s > a +. • D je množina celých čísel, • /(a) = 0, /(ai) = 1, /(a2) = 2,..., /(bi) = -1, l(b2) = -2,... (jedná se o nulární funkce), •/(0 = + (funkce zadaná pomocí rovnosti funkcí: zobrazení l(f) definujeme jako funkci sčítání celých čísel; pak např. /(/r)(4, —2) = 2), • /(P) = > (relace zadaná pomocí rovnosti relací: /(P) definujeme jako relaci ,větší než' pro celá čísla; např. (2,-1) G /(P)) Úvod do umělé inteligence 7/12 9/16 Sémantika predikátové logiky Interpretace proměnných a termů interpretace volných proměnných spočívá v jejich ohodnocení, což je libovolné zobrazení V (valuace) z množiny všech proměnných do D ohodnocení, které přiřazuje proměnné x prvek d £ D a na ostatních proměnných splývá s valuací V, označíme \/[x/c/] hodnotou termu t v interpretaci / a valuaci V je prvek \ t\lv £ D takový, ze ■ je-li t proměnná, \t\lv = V{t) ■ je-li t = f(ŕi,..., tn), pak |ŕ|; v je hodnotou funkce l(f) pro argumenty I ^11 /, V ' ' ' ' ' I ^n I /, v příklad: mějme interpretaci / z předchozího příkladu (celá čísla s > a +) a valuaci V(x) — 2. Pak \f{bi, f(bi, b2))\, v = +(-1, +(-2, -2)) = -5 \f(f(a, h), f(x, 3l))\lv = +(+(0, -1), +(2,1)) = 2 Úvod do umělé inteligence 7/12 10 / 16 Sémantika predikátové logiky Splnitelnost formulí Formule A je splňována interpretací / a valuací V, pokud • A je P(ti,..., t„) a (|íi|,|V,..., \tn\lv) G /(P) e íi = Í2 a |ŕi|, v = \ t2\1 v (oba termy reprezentují týž prvek) e -16 a /, V nesplňují fí e tvaru 6 A C a /, V splňují fí i C e 6 V C a /, V splňují B nebo C e tvaru B C a /, V nesplňují B nebo splňují C eB^Ca /, V splňují 6 i C nebo nesplňují 6 i C e VxB a /, V[x/oř] splňují B pro libovolné d e D e 3x6 a /, V[x/c/] splňují B alespoň pro jedno oř G D • A • A • A o A 9 A • A • A • 4 Úvod do umělé inteligence 7/12 11 / 16 Sémantika predikátové logiky Splnitelnost - príklad Příklad: mějme dříve uvedenou interpretaci / (celá čísla s > a +), mějme jinou interpretaci /' téhož formálního jazyka (celá čísla s > a *, od / se liší pouze definicí l\f) — *) a valuace definované na proměnné x takto: V1(x) = -2, V2(x) = 2 • formuli VxP(/r(x, ai),x) interpretujeme v / jako Vx(x + 1 > x); formule je splňována / a libovolnou valuací. V /' interpretujeme formuli jako Vx(x * 1 > x) - není splněna pro libovolnou valuaci. • VxP(x,y) interpretujeme (v / i /') jako Vx(x > y), formule není splňována / (ani /') a libovolnou valuací • formule P(x, a) interpretovaná (v / i /') jako x > 0 je splňována / (i /;) a V2, není splňována / (ani /;) a V\ • formule Vx(P(x, a) 3yP(x,y)) interpretovaná (v / i /;) jako Vx((x > 0) ^> 3y(x > y)) je splňována / (i /;) a libovolnou valuací Úvod do umělé inteligence 7/12 12 / 16 Sémantika predikátové logiky Pravdivost formulí a jejich klasifikace • formuli A nazveme pravdivou v interpretaci /, je-li splňována / pro libovolnou valuaci, píšeme |=, A 9 pravdivost formule záleží pouze na valuaci volných proměnných, které se v ní vyskytují o pravdivost sentence (uzavřené formule) nezávisí na valuaci vůbec Formule A predikátové logiky se nazývá o tautologie, je-li pravdivá pro každou interpretaci (tj. pro každou / platí |=, A), značíme |= A 9 splnitelná, pokud existuje alespoň jedna interpretace a valuace, které ji splňují (př.: VxP(x,x)) • kontradikce, je-li -iA tautologie (tj. |= ^A) Úvod do umělé inteligence 7/12 13 / 16 Normální formy v predikátové logice Normální formy v predikátové logice Prenexová normální forma (pnf) • cíl: převést libovolnou (uzavřenou) formuli do tvaru, v němž jsou všechny kvantifikátory na začátku a následuje otevřené (= bez kvantifikátorů) jádro v nkf (ndf) Qxi... Qxn^A^ V ... V Aij ) A (A2l V ... V A2l2) A ... A {Ami V ... V Amim)) • příklad: VxVy3zVw((P(x,y) V -Q(z)) A (P(x, w) V /?(y, w))) • Věta: pro každou formuli existuje ekvivalentní formule v konjunktivní (disjunktivní) prenexové normální formě. Úvod do umělé inteligence 7/12 14 / 16 1. eliminovat zbytečné kvantifikátory 2. přejmenovat korektně proměnné tak, aby u každého kvantifikátoru byla jiná proměnná 3. eliminovat všechny spojky různé od -i, A a V 4. přesunout negaci dovnitř, je-li potřeba: -\/xA nahradit 3x^/4 -■(v4 A B) nahradit V -.6 apod. 5. přesunout kvantifikátory doleva (o e {A, V}, Q e {V, 3}): A o QxB nahradit Qx(A o B) QxA o B nahradit Qx(A o B) 6. použít distributivní zákony k převodu jádra do nkf (ndf): A V (B A C) nahradit (A V B) A (A V C) (/4 A 6) V C nahradit (>4 V C) A(BVC) Úvod do umělé inteligence 7/12 15 / 16 Normální formy v predikátové logice Převod do pnf - příklad Příklad: převeďte do konjunktivní pnf formuli Vx3y^(P(x,y) => Vz/?(y)) V -dx/?(y)) Wx2^(?(x2) (přesun negace 2x) 5. Vxi(3y(P(xi,y) A ->R(y)) Wx2^Q(x2)) (posun Vxi doleva) Vxi3y((P(xi,y) A ->P(y)) Wx2^Q(x2)) (posun 3y doleva) Vxi3yVx2((P(xi,y) A ->R(y)) V -iQ(x2)) (posun Vx2 doleva) 6. Vxi3yVx2((P(xi,y) V -./?(y) V ->