Wumpusova jeskyně. Rezoluční metoda. Predikátová
logika.
Luboš Popelínský
E-mail: popel@fi.muni.cz http://nlp.fi.muni.cz/uui/
Obsah:
9 Wumpusova jeskyně
• Rezoluční metoda
• Predikátová logika
Úvod do umělé inteligence 7/12 1/31
Wumpusova jeskyně
Wumpusova jeskyně
4
3
2
> Zápach ^>		'^Vánek ^	^^^^
	^Zápach	n 1 JAMA 1	
	V Třpyt \ A		
"^Zápach >		Vánek ^[	
START	^^Vánek ^	^^^^	'^Vánek ^
1	2	3	4
Úvod do umělé inteligence 7/12 2/31
Wumpusova jeskyně
PEAS pro Wumpusovu jeskyni
P(erformance measure) - míra výkonnosti, zlato +1000 Mrm-smrt -1000, -1 za krok, -10 za užití šípu
E(nvironment) - prostředí, vedle = vlevo, vpravo, nahoře, dole Místnosti vedle Wumpuse zapáchají. V místnosti vedle jámy je vánek. V místnosti je zlato ^ je v ní třpyt. Výstřel zabije Wumpuse, pokud jsi obrácený k němu. Výstřel vyčerpá jediný šíp, který máš. Zvednutím vezmeš zlato ve stejné místnosti. Položení odloží zlato v aktuální místnosti.
A(ctuators) - akční prvky Otočení vlevo, Otočení vpravo, Krok dopředu, Zvednutí, Položení, Výstřel
S(ensors) - senzory Zápach, Vánek, Třpyt, Náraz do zdi, Chroptění Wumpuse
Úvod do umělé inteligence 7/12 3/31
Wumpusova jeskyně
Wumpus: Hrajeme
	2.4	i.'	4,4
1.3	22	s.a	1.3
12 OK	22	4.5	1.2
1.1 E OK.	2,1 OK	3.1	1.1
(a)
li =r Sjjffaf; ůůW
t)K - SsIe square
1' = Pit
Si = Srevncrt
V = VisilsO
1.1	2.1	3.-1	4.4
1.3	2.3	32	42
1.5 OK	5.5 P?	a.z	42
1,1 V UK	B	3.1 p,	4,1
Figuře 7.3 ]"he íixst step taken by ůie agent in úie wumpus world, fa} "The ijíitiaL situation, alter percept 'tfone. A'úites JVime, None* None], (b) After moving to [2,1 J and perceiving [Ntme, Breeze. Arone, JVůwí, None).
1,4	2,-1	3,4	4.4
	2.3	3,3	4,3
"a s ok	22 ok	32	42
1.1 V ok	řl B V Ok	3"1 P,	4.1
[XI =fl.gsrt
if = Ěr??ze
t; = ejjň?r. suw
OK = S&Ib square
I" = Pj'f
V = WaiiaJ
1,4	2 1 It	3,-1	4.4
1,3 wt	S (r B	3.3 F?	42
1.2 S V UK	22 V OK	32	42
1.1 V UK	W fl V OK	3"' PI	4.1
Úvod do umělé inteligence 7/12 4/31
Wumpusova jeskyně
Vlastnosti problému Wumpusovy jeskyně
pozorovatelné ne jen lokální vnímání iľfE
deterministické ano přesně dané výsledky
episodické ne sekvenční na úrovni akcí
statické ano Wumpus a jámy se nehýbou
diskrétní ano
více agentů ne Wumpus sám je spíš vlastnost prostředí
Úvod do umělé inteligence 7/12 5/31
Wumpusova jeskyně
Elementární výroky pro Wumpusovu jeskyni
Definujeme výrokové symboly pro i J G 1,2,3,4:
Jjj je pravda <^> Na [i j] je Jáma.
Wjj je pravda     Wumpus je na [ij], živý či mrtvý.
Co je modelem pro naši hru?
Úvod do umělé inteligence 7/12 6/31
Wumpusova jeskyně
Model pro naši Wumpusovu jeskyni
Definujeme výrokové symboly pro i J £ 1,2,3:
Jjj je pravda ^ Na [i j] je Jáma.
Wjj je pravda ^ Wumpus je na [ij], živý či m
Co je modelem pro naši hru?
^1,3,^3,3,^4,4,1^3,1 mají hodnotu True
Úvod do umělé inteligence 7/12 7/31
Báze znalostí KB
Wumpusova jeskyně
Elementární výroky, jejichž pravdivostní hodnota se odvodí z J,j a W,j :
Vjj je pravda ^ agent cítí na [i j] Vánek. Z/j je pravda ^ agent cítí na [ij] Zápach.
• platí pro všechny jeskyně:
- Rl:-Ji,i
■ "V poli je Vánek     ve vedlejším poli je Jáma." vedlejší = vlevo, vpravo, nahoře, dole. Pro pole sousední s [1,1]:
R2: VM & (J1>2 V J2,i)
R3: V2,i     (Ji,i V J2>2 V J3,i)
• pro tuto instanci hry:
- R4: -.VM
■ R5: V2,i
KB = Rl A R2 A /?3 A /?4 A /?5
Úvod do umělé inteligence 7/12 8/31
Stav: [Zápach, Vánek, Třpyt] Sensory: [falše, falše, falše]
KB = jak uvedeno = pravidla Wumpusovy jeskyně + pozorování KB |= "[1, 2] je bezpečné pole"
model checking (kontrola modelů) = jednoduchý způsob logické inference
Kontrola všech modelů je bezesporná a úplná (pro konečný počet výrokových symbolů)
jak víme, složitost 0(2n) pro n výrokových symbolů, NP-úplný problém
Úvod do umělé inteligence 7/12 9/31
Rezoluční metoda		
Rezoluční metod	a	
Rezoluce: další formální systém
• vhodná pro strojové dokazování (Prolog)
o metoda založená na vyvracení: dokazuje se nesplnitelnost formulí
• pracujeme s formulemi v konjuktivní normální formě (též klauzulárním tvaru), ale používáme jinou notaci:
• klauzule je konečná množina literálů (chápaná jako jejich disjunkce); je pravdivá, pokud alespoň jeden prvek je pravdivý. Prázdná klauzule □ je vždy nepravdivá - neobsahuje žádný pravdivý prvek.
Příklad klauzule: {p, -iq, r} (tj. p V -iq V r)
• formule je (ne nutně konečná) množina klauzulí (chápaná jako jejich konjunkce, tedy nkf); je pravdivá, je-li každý prvek pravdivý. Prázdná formule 0 je vždy pravdivá - neobsahuje žádný nepravdivý prvek. Příklad formule: {{-q}, {-p, q}, {p, q, r}} (tj.
-■q A (-ip V q) A (p V q V r))
Úvod do umělé inteligence 7/12        10 / 31
Rezol učni pravidlo
Rezoluční metoda
• rezoluční pravidlo: nechť C\ — {p} U C(, C2 = {^p} U C2 jsou klauzule, jejich rezolventou je C = C[ U C2 (rezolvovali jsme na literálu p)
• rezoluční pravidlo zachovává splnitelnost (lib. valuace splňující C\ a C2 splňuje i C; klauzule Ci, C2 označujeme jako rodiče, C jako potomka)
• rezoluční důkaz klauzule C z formule S je konečná posloupnost klauzulí Ci, C2,..., C„, kde Cn = Ca každé C; je buď prvkem S, nebo rezolventou klauzulí Cy, Q pro j, /c < /. Existuje-li tento důkaz, je C rezolučně dokazatelná z S (píšeme S \-r C). Odvození □ z S je vyvrácením S.
« příklad: dokažte C = {^q} z S = {{p, r}, {^q, -ir}, {^p}} Ci = {p, r} (prvek S), C2 = {^g, ^r} (prvek S), C3 = {p, ^q} (rezolventa Ci, C2), C4 = {^p} (prvek S), C = C5 = {^q} (rezolventa C3, C4)
Úvod do umělé inteligence 7/12        11 / 31
Rezoluční metoda		
Rezoluce - stromy		
přehlednější formou rezolučních důkazů jsou stromy • strom rezolučního důkazu C z S je binární strom T s vlastnostmi:
■ kořenem T je C
■ listy T jsou prvky S
■ libovolný vnitřní uzel C, s bezprostředními následníky Cý, Ck je rezolventou
Q3 Ck
o příklad: strom důkazu C = {^q} z S = {{p, r}, {^q, -"r}, {^p}}
Úvod do umělé inteligence 7/12        12 / 31
Rezoluční metoda
Příklad: Rezoluční vyvrácení
• příklad: vytvořte strom rezolučního vyvrácení formule
(p V r) A (q V -ir) A ->q A (-.p V ř) A -is A (s V -it)
Úvod do umělé inteligence 7/12        13 / 31
Rezoluční metoda
Příklad: Rezoluční vyvrácení
• příklad: vytvořte strom rezolučního vyvrácení S (dokažte S \-r □), je-li
S = {{p, r}, {g, ^r}, {->q}, {->p, t}, {--«}, {s, ->í}}
Úvod do umělé inteligence 7/12        14 / 31
Rezoluční metoda
Rezoluce - vlastnosti
• Věta (korektnost a úplnost rezoluce): rezoluční vyvrácení formule S existuje právě tehdy, když je S nesplnitelná.
• důsledek: existuje-li rezoluční strom s listy z množiny S a kořenem □, pak je S nesplnitelná
• obecné schéma důkazu "formule A je log. důsledkem množiny formulí T": vytvoříme konjunkci T' všech prvků z T, formuli T' A -iA převedeme do nkf a ukážeme nkf(7; A ^A) \-r □
• výhody pro strojové zpracování: systematické hledání důkazu, práce s jednoduchou datovou strukturou, jediné odvozovací pravidlo
a problém: strategie generování rezolvent - prohledávaný prostor může být příliš velký; př.: {{p}, {p, ^q}, {^p, q, r}, {^p, ^r}, {r}} - postup, kdy rezolvujeme 2. a 3. klauzuli na p a výsledek poté se 4. na r, k důkazu nevede
Úvod do umělé inteligence 7/12        15 / 31
Rezoluční metoda		
Zjemnění rezoluce		
• snaha omezit prohledávaný prostor
■ ukončením prohledávání neperspektivních cest
■ určením pořadí při procházení alternativních cest
• = další podmínky na rodičovské klauzule nebo rezolventu v definici rezoluce
• každé omezení rezolučního pravidla je korektní, ne každé zachovává úplnost.
Příklady možných zjemnění
• vyloučení klauzulí s literálem, který je ve formuli S pouze v jedné paritě
• T-rezoluce: žádná z rodičovských klauzulí není tautologie, tautologie obsahuje týž literál v obou paritách např. {p, -iq, -ip, r}
• nechť A je libovolná interpretace, ^4-rezoluce (sémantická rezoluce) je rezoluce, kde alespoň jedna z rodičovských klauzulí je v A nepravdivá.
(Budou-li rodiče v dané valuaci pravdiví, bude v ní pravdivý i potomek - touto cestou k nesplnitelnosti nedojdeme, yl-rezoluce je korektní a úplná.)
Úvod do umělé inteligence 7/12        16 / 31
Rezoluční metoda		
Wumpus: rezoluce		
Postup řešení:
Vyjdeme z definice: Zjišťujeme, zda cíl G je logickým důsledkem KB, KB |= G.
1. Určíme cíl G, např. "je pole [1,2] bezpečné".
2. Znalostní bázi spolu s negovaným cílem KBU^G převedeme do konjunktivní normální formy
3. Přepíšeme tuto knf do množinové notace, máme množinu S.
4. Dokazujeme, zda S je nesplnitelná.
5. Pokud ano, G je logickým důsledkem KB
Nevýhoda? Pro každou změnu KB a každý cíl G musíme opakovat všechny kroky.
Úvod do umělé inteligence 7/12        17 / 31
Wu mpus: rezoluce
Rezoluční metoda
Lépe :
1. Iniciální znalostní bázi KBq - to, co platí pro všechny instance Wu m pusovy jeskyně - převedeme do konjunktivní normální formy.
2. Přepíšeme tuto knf do množinové notace, máme množinu S.
3. Varianta 1:
1. Určíme cíl G a převedeme ->G do konjunktivní normální formy, přepíšeme do množinové notace, množina Sg
2. Dokazujeme, zda S U Sg je nesplnitelná.
3. Pokud ano, G je logickým důsledkem KB.
4. Varianta 2:
1. Najdeme všechny logické důsledky, tj. kořeny všech rezolučních stromů;
2. Vybereme jeden z nich, např. další z bezpečných polí;
3. Všechny důsledky = klauzule, přidáme do KB
5. V obou variantách: Novou znalost KBnew (= množina klauzulí) sjednotíme s dosavadní St, tj. KB v čase t : Sŕ+i = St U KBnew
Úvod do umělé inteligence 7/12        18 / 31
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        19 / 31
Predikátová logika
Základní pojmy
• 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
• 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        20 / 31
Predikátová logika
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 ^(2,1), r(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ývají 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        21 / 31
Predikátová logika
Poznámky k zavedenému formálnímu jazyku
• predikátová logika 1. řádu : jen objektové (individuální) proměnné 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        22 / 31
Predikátová logika
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é
• 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        23 / 31
Predikátová logika
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
• 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 ŕ
9 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), A(y/f(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        24 / 31
Predikátová logika
Sémantika predikátové logiky
• pro analýzu sémantiky potřebujeme nejprve specifikaci jazyka - doménu, konstanty, funkční a predikátové symboly
• 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ální čí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    n > 0
■ A7-ární relace l(P) C D" pro každý n-ární predikátový symbol P, n > 1
Úvod do umělé inteligence 7/12        25 / 31
Predikátová logika		
Interpretace jazyka: přík	lad	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,
o /(a) = 0, /(ai) = 1, /(a2) = 2,..., /(bi) = -1, l(b2) = -2,... (jedná se o nulární funkce),
• /(O = +
(funkce zadaná pomocí rovnosti funkcí: zobrazení /(ŕ) 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        26 / 31
Predikátová logika
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, Ďi), f(x, ai))|í>v = +(+(0, -1), +(2,1)) = 2
Úvod do umělé inteligence 7/12        27 / 31
r
Splnitelnost formulí
Predikátová logika
Formule A je splňována interpretací / a valuací V, pokud A ie P(íi,...,ín) a (|íi| ) e l(P)
e ti = Í2 a |ti|, v = \ t2\1 v (oba termy reprezentují týž prvek) e -16 a /, V nesplňují B e tvaru B A C a /, \/ splňují 6 i C e 6 V C a /, V splňují B nebo C e tvaru B =5- 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 /, \/[x/c/] splňují B alespoň pro jedno d E D
• A
• A
• A
• A
• A
• A
• A
• A
Úvod do umělé inteligence 7/12        28 / 31
Predikátová logika
Splnitelnost - pří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: Vi(x) = -2, V2(x) = 2
• formuli VxP(r(x, 3i),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        29 / 31
Predikátová logika
Pravdivost formulí a jejich klasifikace
• formuli A nazveme pravdivou v interpretaci /, je-li splňována / pro libovolnou valuaci, píšeme |=, A
• 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á
9 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        30 / 31
Shrnutí
Predikátová logika
Víme,
• jak popsat a řešit Wumpusovu jeskyni ve výrokové logice 9 co je rezoluční metoda ve výrokové logice
• jak budovat rezoluční důkaz
• jak definovat syntax a sémantiku predikátové logiky
Úvod do umělé inteligence 7/12        31 / 31