Predikátová logika, Katedra kybernetiky, FEL, ČVUT v Praze

Predik´ atov´ a logika, situaˇ cn´ı kalkulus, produkˇ cn´ı syst´ emy Jiˇr´ı Kl´ ema Katedra kybernetiky, ˇ FEL, CVUT v Praze

http://ida.felk.cvut.cz/moodle/

pLogika jako n´ astroj pro reprezentaci znalost´ı

Jaké vhodné vlastnosti demonstrovala výroková logika? − deklarativnost ∗ znalosti a usuzován´ı jsou pˇrirozenˇe oddˇeleny, ∗ proceduráln´ı jazyky – postrádaj´ı obecný mechanismus pro usuzován´ı. − moˇznost vyjádˇrit neúplnou informaci ∗ pomoc´ı disjunkce (a negace), ∗ “Z´ıtra odpoledne p˚ ujdu do kina nebo budu sportovat.” ∗ nen´ı samozˇrejmost´ı (databáze, datové struktury). − je kompoziˇcn´ım a kontextovˇe nezávislým jazykem ∗ význam vˇety je funkc´ı významu jejich ˇcást´ı, ∗ význam A ∧ B má vztah k pravdivosti A a B, ∗ na rozd´ıl od pˇrirozeného jazyka: “Pak to vidˇela.”


pPredik´ atov´ a logika (PL)

Výroková logika má omezenou expresivitu − problémy se ˇskálován´ım ve wumpusovˇe svˇetˇe, nemá silné mechanismy pro zobecnˇen´ı, − napˇr. rozmˇery bludiˇstˇe ∗ Vˇsechna pole soused´ıc´ı s wumpusem zapáchaj´ı. ∗ W1,2 ⇒ (S1,1 ∧ S2,2 ∧ S1,3), W2,1 ⇒ (S1,1 ∧ S2,2 ∧ S3,1) atd. − dále vztahy mezi objekty, ˇcas, − dˇr´ıve zm´ınˇený Aristotel˚ uv sylogismus o Sokratovi.

PL zavád´ı objekty a relace mezi nimi − inspiruje se v s´ıle pˇrirozeného jazyka, zachovává ale jednoznaˇcnost.

PL 1.ˇr´ adu (first-order logic, FOL) − zámˇerné omezen´ı expresivity: ∗ relace samotné nelze povaˇzovat za objekty, ∗ nelze zapisovat tvrzen´ı o vˇsech relac´ıch, tj. napˇr. obecnˇe definovat tranzitivitu.

logiky vyˇsˇs´ıch ˇrád˚ u − vˇetˇs´ı expresivita, obt´ıˇznˇejˇs´ı teorie i efektivn´ı pouˇzit´ı.


pPredik´ atov´ a logika 1.ˇr´ adu – syntaxe

Syntaxe – elementy jazyka − konstanty odkazuj´ı na konkrétn´ı objekty ∗ petr, pavel, skotsko, základy-umˇelé-inteligence (Prolog: zaˇc´ınaj´ı malým p´ısmenem). − predik´ aty vyjadˇruj´ı vztahy mezi objekty ˇci jejich vlastnosti ∗ muˇz(petr), otec(petr,pavel), ˇzije(petr,skotsko) (arita = poˇcet prvk˚ u relace). − funkce jako nepˇr´ımé odkazy na objekt ∗ otec(petr), ˇzije(petr) (jak je vidˇet, funkce lze nahradit predikáty). − promˇ enn´ e odkazuj´ı na mnoˇziny objekt˚ u, ∗ X, Y, Z (Prolog: zaˇc´ınaj´ı velkým p´ısmenem). − kvantifik´ atory urˇcuj´ıc´ı interpretaci promˇenných ∗ ∀ (pro vˇsechny) – pˇri jakékoli substituci objektu za promˇennou vˇeta plat´ı, ∗ ∃ (existuje) – lze nalézt objekt, který pˇri substituci za promˇennou zajist´ı platnost vˇety, ∗ ∀ X ∃ Y uˇc´ı(X,Y) – kaˇzdý pˇredmˇet má alespoˇn jednoho uˇcitele. − logick´ e spojky a závorky ∗ stejné jako ve výrokové logice.

V souvislosti se znaˇcen´ım konstant, funkc´ı a predikát˚ u mluv´ıme o symbolech.


pPredik´ atov´ a logika 1.ˇr´ adu – syntaxe

Syntaxe – definice korektn´ıch výrokových formul´ı − term je kaˇzdá konstanta, promˇenná nebo funkce na nˇe aplikovaná ∗ odkazuje na objekt, nic jiného termem nen´ı (tj. predikáty nejsou termy). − dobˇre utvoˇrenou formul´ı (well-formed formula (WFF)) jsou ∗ atomick´ e formule p(t1, . . . , tn), kde p je predikátový symbol a ti termy, ∗ formule ¬p a p ⇒ q, pokud p a q jsou WFF, ∗ formule ∀Xp, pokud X je promˇenná a p WFF.

Syntaxe poznámky − WFF m˚ uˇze obsahovat volné promˇenné (nevázané kvantifikátorem), ∗ to p˚ usob´ı problémy pˇri interpretaci WFF, vˇ eta je WFF pouze s vázanými promˇennými. − z hlediska definice jsou spojky ∨, ∧, ⇔ a kvantifikátor ∃ odvozené.


pPredik´ atov´ a logika 1.ˇr´ adu – s´ emantika, interpretace

Jak urˇcovat platnost vˇet v PL 1.ˇrádu? Je dána kontextem, ale ...

Ovˇeˇrován´ı pravdivosti pro vˇsechny modely? − pracujeme s velkými nebo neomezenými doménami (napˇr. reálná ˇc´ısla), − v d˚ usledku m˚ uˇze existovat i neomezený poˇcet model˚ u.

Interpretace definuje: − které objekty, predikáty a fce odpov´ıdaj´ı pˇr´ısluˇsným symbol˚ um a jejich význam ˇ ∗ dom´ ena ∆ = {Jiˇr´ı Kléma, Filip Zelezn´ y, STM Y33ZUI, BK X33KUI}, ∗ interpretace konstant: lC : C → ∆, jirka odkazuje na Jiˇr´ıho Klému, zui na pˇredmˇet STM Y33ZUI, atd. ∗ interpretace predikát˚ u s aritou n: lP : P → P (∆n), uˇc´ı odkazuje na vztah mezi uˇcitelem a pˇredmˇetem, uˇc´ı/2 = {{jirka,zui},{filip,kui}}.

Je formule ∀X(p(X) ∨ q(X)) ⇒ (∀Xp(X) ∨ ∀Xq(X)) tautologi´ı? − pro vyvrácen´ı staˇc´ı nalézt interpretaci v n´ıˇz formule neplat´ı, − napˇr. v interpretaci ∆={a,b}, pD = {a}, qD = {b}, − levá strana implikace plat´ı: X=a: p(a)∨q(a) = T ∨F = T , X=b: p(b)∨q(b) = F ∨T = T , − pravá strana ne: X=b: p(b) = F , ∀Xp(X) = F podobnˇe pro X=a a ∀Xq(X) = F .


pInference v PL 1.ˇr´ adu – unifikace

Jak korektnˇe substituovat za volné promˇenné resp. termy pˇri srovnáván´ı výraz˚ u? − dotaz: Koho zná Jirka? − ?zna(jirka,X) – vraˇt vˇsechny korektn´ı substituce za volnou promˇennou vzhledem ke KB, − KB: Jirka zná Filipa. Václava zná kaˇzdý. Kaˇzdý zná svoji matku. Monika nˇekoho zná. − zna(jirka, f ilip), ∀Y zna(Y, vaclav), ∀Zzna(Z, matka(Z)), ∃W zna(monika, W ), − zna(jirka, f ilip), zna(Y, vaclav), zna(Z, matka(Z)), zna(monika, s1), − substituce: θ1 = {X|f ilip}, θ2 = {jirka|Y, X|vaclav}, θ3 = {jirka|Z, X|matka(jirka)}, − hledáme co nejobecnˇ ejˇs´ı substituci, aby výrazy byly unifikovatelné.

Substituce a unifikace nutná pro jakoukoli inferenci, viz. generalizovaný modus ponens A, A ⇒ B p01, . . . , p0n, (p1 ∧ p2 ∧ · · · ∧ pn ⇒ q) → B Subst(θ, q) Subst(θ, p0i) = Subst(θ, pi) − Kdyˇz se dva lidé znaj´ı, tak se zdrav´ı. → ∀XY (zna(X, Y ) ⇒ zdravi se(X, Y )) − aplikace MP na KB ` zdravi se(jirka, f ilip), zdravi se(Y, vaclav), zdravi se(U, matka(U )), zdravi se(monika, s1).


pInference v PL 1.ˇr´ adu – rezoluˇ cn´ı pravidlo

U rezoluce unifikace zejména pˇri identifikaci doplˇnkových literál˚ u ˇ zná kaˇzdý z katedry. → ∀X(z katedry(X) ⇒ zna(X, vlada)), − Vládu − klauzule: ¬z katedry(X) ∨ zna(X, vlada) − klauzule viz. minulý slajd: ¬zna(U, V ) ∨ zdravi se(U, V ), − substituce: θ = {V |vlada, X|U }, − rezolventa: ¬z katedry(U ) ∨ zdravi se(U, vlada).


pRezoluce v PL 1.ˇr´ adu – pˇrevod do CNF (1)

Obt´ıˇznˇejˇs´ı pˇrevod do CNF neˇz u výrokové logiky – promˇenné a kvantifikátory ˇ ımané, kteˇr´ı znaj´ı Markuse, budˇ nenávid´ı Caesara nebo si mysl´ı, ˇze kaˇzdý kdo Pˇr: Vˇsichni R´ nˇekoho nenávid´ı je blázen. ∀X (riman(X) ∧ zna(X, markus)) ⇒ (nenavidi(X, caesar) ∨ ∀Y ∃Z(nenavidi(Y, Z) ⇒ ma za blazna(X, Y ))) Obecné kroky pˇrevodu: 1. odstranˇen´ı implikac´ı ∀X ¬(riman(X) ∧ zna(X, markus))∨ (nenavidi(X, caesar) ∨ ∀Y ¬(∃Znenavidi(Y, Z)) ∨ ma za blazna(X, Y ))) 2. pˇresun negac´ı k atomickým formul´ım ∀X ¬riman(X) ∨ ¬zna(X, markus)∨ nenavidi(X, caesar) ∨ ∀Y ∀Z(¬nenavidi(Y, Z) ∨ ma za blazna(X, Y )) 3. skolemizace – eliminace existenˇcn´ıch kvantifikátor˚ u, − zde ˇzádný výskyt, ale: ∀X∃Y otec(Y, X) → ∀Xotec(s1(X), X) − s1 je v daném pˇr´ıpadˇe Skolemovou funkc´ı (kaˇzdému X pˇriˇrazuje otce)


pRezoluce v PL 1.ˇr´ adu – pˇrevod do CNF (2)

Obecné kroky pˇrevodu (pokr.): 5. oddˇelen´ı jmen promˇenných − pro formule typu: ∀Xriman(X) ∨ ∀Xrek(X) → ∀Xriman(X) ∨ ∀Y rek(Y ) 6. pˇresun univerzáln´ıch kvantifikátor˚ u zcela vlevo – prenexn´ı tvar, ∀XY Z ¬riman(X) ∨ ¬zna(X, markus)∨ nenavidi(X, caesar) ∨ ¬nenavidi(Y, Z) ∨ ma za blazna(X, Y ) 7. pˇresun disjunkc´ı k literál˚ um − aplikace distributivn´ıch zákon˚ u a ∨ (b ∧ c) → (a ∨ b) ∧ (a ∨ c) 8. eliminace univerzáln´ıch kvantifikátor˚ u – bezkvantifikátorové jádro. ¬riman(X) ∨ ¬zna(X, markus)∨ nenavidi(X, caesar) ∨ ¬nenavidi(Y, Z) ∨ ma za blazna(X, Y )


pKlade Zuzana vaj´ıˇ cka? – motivaˇ cn´ı pˇr´ıklad 3

:: Pokud vám ˇreknu, ˇze:

(S1) Ptakopysk a jeˇzura jsou jedin´ı savci kladouc´ı vejce.

(S2) Pouze ptáci a savci jsou teplokrevn´ı.

(S3) Zuzana, m˚ uj pásovec, je teplokrevná a nemá peˇr´ı.

(S4) Kaˇzdý pták má peˇr´ı.

:: a zeptám se: (D) Klade Zuzana vejce?


pKlade Zuzana vaj´ıˇ cka? – motivaˇ cn´ı pˇr´ıklad 3

:: Pokud vám ˇreknu, ˇze:

(S1) Ptakopysk a jeˇzura jsou jedin´ı savci kladouc´ı vejce.

(S2) Pouze ptáci a savci jsou teplokrevn´ı.

(S3) Zuzana, m˚ uj pásovec, je teplokrevná a nemá peˇr´ı.

(S4) Kaˇzdý pták má peˇr´ı.

:: a zeptám se: (D) Klade Zuzana vejce? :: Inference v pˇrirozeném jazyce:

Zuzana nemá peˇr´ı a proto nen´ı pták.

Zuzana je teplokrevná a nen´ı pták, proto mus´ı být savec.

Zuzana je savec a pásovec, protoˇze nen´ı jeˇzura ani ptakopysk nem˚ uˇze klást vejce.

:: Jak realizovat strojovˇe? Reprezentace pomoc´ı ˇretˇezc˚ u je problematická z hlediska odvozován´ı nových tvrzen´ı ...


pKlade Zuzana vaj´ıˇ cka – d˚ ukaz rezoluc´ı (1) :: Pˇrepis do predikátové logiky 1.ˇrádu:

(S1) ∀X(savec(X) ∧ vejce(X) ⇒ jezura(X) ∨ ptakopysk(X))

(S2) ∀X(teplokrevny(X) ⇒ ptak(X) ∨ savec(X))

(S3) pasovec(zuzana) ∧ teplokrevny(zuzana) ∧ ¬peri(zuzana)

(S4) ∀X(ptak(X) ⇒ peri(X))

(F) ∀X(pasovec(X) ⇒ ¬(ptakopysk(X) ∨ jezura(X)))

(D) vejce(zuzana)


pKlade Zuzana vaj´ıˇ cka – d˚ ukaz rezoluc´ı (1) :: Pˇrepis do predikátové logiky 1.ˇrádu:

(S1) ∀X(savec(X) ∧ vejce(X) ⇒ jezura(X) ∨ ptakopysk(X))

(S2) ∀X(teplokrevny(X) ⇒ ptak(X) ∨ savec(X))

(S3) pasovec(zuzana) ∧ teplokrevny(zuzana) ∧ ¬peri(zuzana)

(S4) ∀X(ptak(X) ⇒ peri(X))

(F) ∀X(pasovec(X) ⇒ ¬(ptakopysk(X) ∨ jezura(X)))

(D) vejce(zuzana)

:: Transformace do klauzáln´ı formy:

(C1) ¬savec(X) ∨ ¬vejce(X) ∨ jezura(X) ∨ ptakopysk(X)

(C2) ¬teplokrevny(X) ∨ ptak(X) ∨ savec(X)

(C3,4,5) pasovec(zuzana) ∧ teplokrevny(zuzana) ∧ ¬peri(zuzana)

(C6) ¬ptak(X) ∨ peri(X)

(C7,8) (¬pasovec(X) ∨ ¬ptakopysk(X)) ∧ (¬pasovec(X) ∨ ¬jezura(X))

(C9) vejce(zuzana)


pKlade Zuzana vaj´ıˇ cka – d˚ ukaz rezoluc´ı (2) :: Strom rezoluˇcn´ıho zam´ıtnut´ı:

:: Tvrzen´ı, ˇze Zuzana klade vejce je ve sporu s teori´ı. Zuzana vejce neklade.


pPL ve wumpusovˇ e svˇ etˇ e

PL je dostateˇcnˇe expresivn´ı pro popis wumpusova svˇeta a inferenci v nˇem

reprezentace prostˇred´ı − sousednost jeskyn´ı ∀XY AB [sousedi([X, Y ], [A, B]) ⇔ [A, B] ∈ {[X + 1, Y ], [X − 1, Y ], [X, Y + 1], [X, Y − 1]}] − diagnostická pravidla – od pozorovatelných jev˚ u k jejich pˇr´ıˇcinám – pro výskyt vánku ∀S (vanek(S) ⇒ ∃R (sousedi(R, S) ∧ sachta(R))), ∀S (¬vanek(S) ⇒ ¬∃R (sousedi(R, S) ∧ sachta(R))), − kauzáln´ı pravidla – vlastnosti prostˇred´ı generuj´ı vnˇejˇs´ı projevy – pro jeskynˇe ∀R (sachta(R) ⇒ ∀S (sousedi(R, S) ⇒ vanek(S))), ∀S [∀R sousedi(R, S) ⇒ ¬sachta(R)] ⇒ ¬vanek(S), − výˇse uvedená diagnostická a kauzáln´ı pravidla jsou ekvivalentn´ı zápisu: ∀S (vanek(S) ⇔ ∃R (sousedi(R, S) ∧ sachta(R))) .

obt´ıˇznˇejˇs´ı je zachycen´ı vn´ımán´ı, reflexe, modifikace prostˇred´ı − vn´ımán´ı (T vyjadˇruje ˇcas, resp. ˇc´ıslo kroku) ∀T SB (senzory([S, B, trpyt], T ) ⇒ trpyt(T )) − reflexe ∀T (trpyt(T )) ⇒ nejlepsi akce(uchop, T ))


pSledov´ an´ı zmˇ en

fakta plat´ı v konkrétn´ıch situac´ıch, sp´ıˇse neˇz vˇeˇcnˇe,

situaˇ cn´ı kalkul je jedn´ım ze zp˚ usob˚ u reprezentace zmˇen ve FOL, − predikáty dˇel´ı na nemˇenné (rigid, eternal) a flexibiln´ı (fluents), − pˇridává situaˇcn´ı argument ke kaˇzdému predikátu s moˇznou zmˇenou platnosti, − flexibiln´ı napˇr. drzi(zlato, nyni), term nyni oznaˇcuje situaci, − nemˇenný napˇr. sachta(R), sousedi(R, S), − situace jsou vázány result funkc´ı, − výsledkem result(a, s) je situace, do n´ıˇz dospˇejeme proveden´ım akce a v situaci s.


pPopis a pouˇ zit´ı akc´ı

“d˚ usledkový” axiom – popisuje zmˇeny, které jsou výsledkem akce − ∀s seZlatem(s) → drzi(zlato, result(uchop, s))

axiom “rámce” – popisuje, co akce nezmˇ enila − ∀s maSip(s) → maSip(result(uchop, s))

probl´ em r´ amce: jak elegantnˇe zvládnout fakta beze zmˇeny (a) reprezentaˇcn´ı – vyhni se axiom˚ um rámce, pro F flexibiln´ıch predikát˚ u a A akc´ı potˇrebujeme O(F A) axiom˚ u rámce. (b) inferenˇcn´ı – vyhni se opakovanému pˇrepisován´ı k udrˇzen´ı informace o stavu,

kvalifikaˇ cn´ı probl´ em − vˇerný popis reálných akc´ı vyˇzaduje nekoneˇcnou péˇci, − co kdyˇz zlato bude kluzké nebo pˇribité k zemi nebo . . . ?

probl´ em d˚ usledku − skuteˇcné akce maj´ı mnoho skrytých d˚ usledk˚ u, − s agentem se pˇresouvá vˇse co drˇz´ı, se zlatem se pˇresouvá i prach, rukavice se opotˇrebovávaj´ı,


pPopis a pouˇ zit´ı akc´ı

axiomy “následných stav˚ u” ˇreˇs´ı reprezentaˇcn´ı problém rámce,

kaˇzdý axiom se dotýká predikátu (a nikoli akce samotné) P plat´ı po proveden´ı akce ⇔ [akce vedla ke splnˇen´ı P ∨ P jiˇz platilo a akce P nezneplatnila]

pro manipulaci se zlatem ∀a, s drzi(zlato, Result(a, s)) ⇔ [(a = uchop ∧ seZlatem(s)) ∨ (drzi(zlato, s) ∧ a 6= uvolni)]

dostaneme F axiom˚ u s celkovým poˇctem literál˚ u O(AE) (E je poˇcet efekt˚ u na akci).


pProbl´ em r´ amce a lidsk´ y mozek

Sherlock Holmes a pes, který neˇstˇekal "Is there any point to which you would wish to draw my attention?" "To the curious incident of the dog in the night-time." "The dog did nothing in the night-time." "That was the curious incident," remarked Sherlock Holmes.

Co tedy um´ı lidský mozek a pamˇeˇt? − ani lidská pamˇeˇt neukládá vˇse, − ale nˇekdy se tak tváˇr´ı, zjednoduˇsen´ı si lidé neuvˇedomuj´ı, − soustˇred´ı se na akci, rámec je rekonstruován, − proto maj´ı i lidé problém povˇsimnout si toho, co se nestalo.


pVytv´ aˇren´ı pl´ an˚ u

poˇcáteˇcn´ı podm´ınky v bázi znalost´ı − poloha(agent, [1, 1], s0), poloha(zlato, [1, 2], s0),

dotaz: − Zjisti(KB, ∃s drzi(zlato, s)), − tj., v jaké situaci budu drˇzet zlato?

ˇ odpovˇed: − {s/result(uchop, result(jdi vpred, s0))}, − tj., jdi vpˇred a poté uchop zlato,

pˇredpoklady: − agent se zaj´ımá pouze o plány zapoˇc´ınaj´ıc´ı v s0, − s0 je jedinou situac´ı popsanou v KB.


pVytv´ aˇren´ı pl´ an˚ u: lepˇs´ı zp˚ usob

vyjádˇri plány jako posloupnosti akc´ı [a1, a2, . . . , an],

planResult(p, s) je výsledkem proveden´ı plánu p ve stavu s − projekˇcn´ı u´loha – jaká je výsledná situace po aplikován´ı dané posloupnosti akc´ı? pozice(agent, [1, 1], s0) ∧ pozice(zlato, [1, 2], s0) ∧ ¬drzi(O, s0) pozice(zlato, [1, 1], result([jdi([1, 1], [1, 2]), uchop(zlato), jdi([1, 2], [1, 1])], s0)) − plánovac´ı u´loha – jaká posloupnost akc´ı vede k dané situaci?

dotaz Zjisti(KB, ∃p drzi(zlato, planResult(p, s0))) − má ˇreˇsen´ı {p/[jdi vpred, uchop]},

definice planResult v rámci result − ∀s planResult([ ], s) = s, − ∀a, p, s planResult([a|p], s) = planResult(p, result(a, s)),

viz pl´ anov´ an´ı prob´ırané dˇr´ıve − specializované plánovac´ı systémy uspˇeˇsnˇejˇs´ı neˇz obecné usuzován´ı.


pSituaˇ cn´ı kalkul: pˇr´ıklad

Mˇejme logickou KB definuj´ıc´ı vzdálenost mezi ˇceskými mˇesty: − vzdal(praha, brno, 202), vzdal(brno, zlin, 100),

stav agenta nechˇt je dán jeho polohou a benz´ınem v nádrˇzi − pozice(M esto, Stav), nadrz(Benzin, Stav), − spotˇreba nechˇt je 6l/100km,

zapiˇste axiom definuj´ıc´ı predikát delkaCesty(P,D) − napˇr´ıklad delkaCesty([praha, brno, zlin], 302),

zapiˇste situaˇcn´ı axiom definuj´ıc´ı následky akce projdiCestu(P ) − postihnˇete zmˇenu pozice agenta a objemu benz´ınu v nádrˇzi,

jsou potˇreba axiomy rámce?


pSituaˇ cn´ı kalkul: pˇr´ıklad

rekurzivn´ı definice delkaCesty(P,D): ∀X delkaCesty([X], 0) ∀X, Y, L, D1, D2 vzdal(X, Y, D1) ∧ delkaCesty([Y |L], D2) ⇒ delkaCesty([X, Y |L], D1 + D2)

pro následky akce projdiCestu(P ) je tˇreba sledovat splnˇen´ı pˇredpoklad˚ u ∀X, Y, B, D, P, S pozice(X, S) ∧ delkaCesty(P, D) ∧ nadrz(B, S)∧ (B > D ∗ 6/100) ∧ f irst(P,X) ∧ last(P, Y ) ⇒ pozice(Y, Result(projdiCestu(P ), S))∧ nadrz(B − D ∗ 6/100, Result(projdiCestu(P ), S))

akce projdiCestu(P ) mˇen´ı oba flexibiln´ı predikáty, axiomy rámce nejsou tˇreba − byly by tˇreba napˇr´ıklad pro hypotetický predikát pojizdnostV ozu(P ojizdnost, Stav).


pKdy predik´ atov´ a logika nen´ı vhodn´ a?(1)

Pro nemonot´ onn´ı odvozován´ı → nemonotónn´ı logiky, − monotónnost PL – pˇridán´ım nového tvrzen´ı nelze zruˇsit platnost tvrzen´ı dˇr´ıve odvozeného, − protipˇr´ıkladem je vhodnost pˇripuˇstˇen´ı obecných tvrzen´ı a jejich výjimek: ∗ Kaˇzdý pták létá. Tuˇcnˇáci jsou ptáci. Quido je tuˇcnˇák. ` Quido létá. ∗ výjimka: Tuˇcnˇáci nelétaj´ı. ` Quido nelétá. ∗ v PL jde o nekonzistentn´ı bázi znalost´ı a lze z n´ı rezoluc´ı odvodit cokoli.

Pro práci s ˇ casem → temporáln´ı modáln´ı logika, − lze i pˇr´ımo v PL ∗ zabit(caesar,brutus,-44), ∀ X Y T (zabit(X,Y,T) ∧ T


pKdy predik´ atov´ a logika nen´ı vhodn´ a?(2)

Vyjádˇren´ı nejistoty → fuzzy logika, Dempster-Shaferova teorie, pravdˇepodobnost − pˇr´ıˇciny: omezená pozorovatelnost svˇeta, nedeterministické vztahy mezi objekty nebo výsledky akc´ı, zjednoduˇsen´ı kv˚ uli efektivitˇe, − pˇr´ıklad fuzzy pravidla: pokud je chladn´ e poˇ cas´ı a cena ropy je n´ızk´ a, pak je topen´ı zapnuto naplno, − lingvistick´ e promˇ enn´ e nabývaj´ı mnoˇziny hodnot, kaˇzdá hodnota je fuzzy mnoˇ zinou.

Vyjádˇren´ı pˇresvˇ edˇ cen´ı, v´ıry → podpˇr´ıpad nejistoty, modáln´ı logika − pˇr´ıklad 1: Alenka v´ı, ˇze je Bert´ık pˇresvˇedˇcen, ˇze Cyril lˇze. Alenka vˇeˇr´ı, ˇze Bert´ık je neomylný. Tedy: Alenka vˇeˇr´ı, ˇze Cyril lˇze. ˇ − pˇr´ıklad 2: A v´ı, ˇze Václav Klaus je Václav Klaus. Václav Klaus je prezidentem CR. ˇ ??? Plat´ı, ˇze: A v´ı, ˇze Václav Klaus je prezidentem CR


pProdukˇ cn´ı syst´ em

Soubor produkˇcn´ıch pravidel − pravidlo: situace ⇒ akce, obecná znalost, − situaˇcn´ı ˇcást pravidla popisuje podm´ınku, za n´ıˇz m˚ uˇze být pravidlo pouˇzito − situace = konjunkce podm´ınek, − akce (pˇridej, odeber, zmˇenˇ) nebo jejich sekvence,

Báze dat (pracovn´ı pamˇeˇt) − popisuje okamˇzitý stav problému, − obsahuje poˇcáteˇcn´ı i odvozená data,

Inferenˇcn´ı stroj (interpret pravidel) − porovnává bázi dat se situacemi v pravidlech, − vyb´ırá vhodná pravidla (ˇreˇs´ı konflikty), − provád´ı jimi definované akce – upravuje pamˇeˇt, − pˇr´ımé (nebo zpˇetné) ˇretˇezen´ı – konˇc´ı nesplnˇen´ım ˇzádné ze situac´ı.


ˇ pCinnost produkˇ cn´ıho syst´ emu

Prob´ıhá obvykle v cyklu − rozpoznán´ı situace ⇒ vykonán´ı akce − souˇcást´ı jsou: instanciace promˇenných pravidla, výbˇer jediného pravidla, zmˇena obsahu pracovn´ı pamˇeti,

Strategie ˇreˇsen´ı konfliktu − preference pravidel s vˇetˇs´ım poˇctem podm´ınek na levé stranˇe, − zákaz opakován´ı pravidla z pˇredchoz´ıho kroku (ochrana proti zacyklen´ı), − upˇrednostnˇen´ı novˇejˇs´ıch dat, uˇzitých k aktivaci pravidla,

Efektivita v reálných u´lohách? − nejv´ıce ˇcasu se obvykle spotˇrebuje na nalezen´ı podmnoˇziny instanc´ı pouˇzitelných pravidel, − to lze urychlit jej´ım zachován´ım i pro pˇr´ıˇst´ı kroky (mˇen´ı se malá ˇcást pracovn´ı pamˇei), − dále i kompilace pravidel do efektivnˇejˇs´ı reprezentace, nebo jejich struktury (stromy), − reference mezi pravidly a daty - testujeme pouze nadˇejná pravidla.


pProdukˇ cn´ı syst´ em pro wumpus˚ uv svˇ et % environment - example rule generate_stench(S) if agent(S) and wumpus(W) and call(adjacent(W,S)) then knows_stench(S).

% working memory gold((2,4)) and wumpus((1,3)) and pit((3,1)) and pit((3,3)) and pit((4,4)) and

% agent reasoning - example rule no_pit(N) if agent(A) and not knows_breeze(A) and call(adjacent(A,N)) then knows_no_pit(N)

knows_no_wumpus((1,1)) and knows_no_pit((1,1)) and knows_ok((1,1)) and agent((1,1))


pProdukˇ cn´ı syst´ emy - souvislosti

Formalismus prohledáván´ı stavového prostoru, − stav je uloˇzen v pamˇeti, situace definuje stav (jejich mnoˇzinu), akce realizuje zmˇenu stavu, − pˇrirozený model lidského ˇreˇsen´ı problém˚ u,

Logické systémy reprezentace lze chápat i jako speciáln´ı tvar produkˇcn´ıch systém˚ u − logická pravidla jsou speciáln´ım pˇr´ıpadem produkˇcn´ıch pravidel, − pˇri omezen´ı na Hornovy klauzule lze usuzovat pˇr´ımým ˇretˇezen´ım,

Analogie s ˇcinnost´ı mozku − pravidla . . . dlouhodobá pamˇeˇt, − báze dat . . . krátkodobá operativn´ı pamˇeˇt, − inference . . . kognitivn´ı funkce,

Souvislost s proceduráln´ım programem − také vykonává instrukce nad daty, − ale silná modularita - neuspoˇrádaná mnoˇzina pravidel vs posloupnost instrukc´ı, − interakce mezi pravidly je velmi omezená (pˇres obsah pamˇeti).


pPraktick´ e vyuˇ zit´ı – s´ emantick´ y web (1)

HTML reprezentace – lidsky srozumitelná ale nevhodná pro automatické zpracován´ı − vyhledáván´ı zaloˇzené na kl´ıˇcových slovech má omezené moˇznosti ∗ nedostateˇcná u´plnost (recall) ˇci naopak pˇresnost (precision), ∗ citlivost na zmˇenu kl´ıˇcových slov (napˇr. zámˇena synonym), ∗ výsledkem vyhledáván´ı jsou jednotlivé stránky ˇci dokumenty – integrace je na ˇclovˇeku, ∗ v d˚ usledku nejde o automatické z´ıskáván´ı informac´ı, ale zjiˇsˇtován´ı jejich um´ıstˇen´ı, − podobná omezen´ı pˇri jiných ˇcastých u´konech ∗ u´drˇzba obsahu stránek – zastaráván´ı, nekonzistence apod., ∗ z´ıskáván´ı znalost´ı – nelze dolován´ı dat jako u databáz´ı (r˚ uznorodost, rozptýlenost), ∗ porovnáván´ı obsahu – porovnej vˇsechny výrobky daného typu (ne ale v jednom katalogu, ale u r˚ uzných prodejc˚ u, v r˚ uzných zem´ıch, v r˚ uzných mˇenách, apod.),



Sémantický web − je rozˇs´ıˇren´ım souˇcasného webu – informace maj´ı pˇridˇelen dobˇre definovaný význam, − dovoluje vyˇsˇs´ı m´ıru automatizovaného (strojového) zpracován´ı, − vyuˇzit´ı SW agent˚ u – autonomn´ıch a pˇredcházej´ıc´ıch poˇzadavky uˇzivatele.



Pouˇzité prvky a technologie − konceptualizace dat na www ve formˇe ontologi´ı, − standardizovaný popis www zdroj˚ u, − XML – zápis strukturovaných metadat – dat o datech, − RDF (Resource Description Framework) – vyjádˇren´ı vztah˚ u mezi metadatovými prvky – syntaktický zápis v XML, identifikátory URI (Universal Resource Identifier) pro pojmenováván´ı, − RDF Schema (Resource Description Framework) – jazyk pro popis ontologie – vyjádˇren´ı sémantiky popisovaných dat.

Antoniou, van Harmelen: A Semantic Web Primer, MIT Press, 2004


pPraktick´ e vyuˇ zit´ı – s´ emantick´ y web (4) – pˇr´ıklad

. Pˇrechod od HTML k ontologické konceptualizaci


pShrnut´ı

Je obt´ıˇznˇejˇs´ı tvoˇrit a spravovat znalosti o promˇenlivém svˇetˇe − obecné problémy – d˚ usledku a zejména rámce, − i lidská pamˇeˇt rámec rekonstruuje pouze pˇribliˇznˇe, − reprezentace zmˇen ve FOL → situaˇcn´ı kalkul,

dalˇs´ı zp˚ usoby reprezentace znalost´ı − produkˇcn´ı systém,

praktická ilustrace − sémantický web,

kde se dozv´ıte v´ıce? − A4M33RZN – Pokroˇcilé metody reprezentace znalost´ı, − A4M33AU – Automatické usuzován´ı.


pDoporuˇ cen´ e doplˇ nky – zdroje pˇredn´ aˇsky ˇ :: Cetba

Russel, Norvig: AI: A Modern Approach, Logical Agents, chapter 7 − reprezentace z pohledu inteligentn´ıho agenta, − dostupná v pdf – http://aima.cs.berkeley.edu/newchap07.pdf.

Maˇr´ık a kol. Umˇ el´ a inteligence 1 − kapitola Reprezentace znalost´ı: základn´ı formáty, logika, sémantické s´ıtˇe, rámce, ˇ sen´ı u´loh a dokazován´ı vˇet: predikátová logika a d˚ − kapitola Reˇ ukazn´ı prostˇredky.

Maˇr´ık a kol. Umˇ el´ a inteligence 2 − kapitola Znalostn´ı inˇzenýrstv´ı: praktická, znalostn´ı systémy v konkrétn´ıch aplikac´ıch.


Predikátová logika, Katedra kybernetiky, FEL, ČVUT v Praze

Recommend Documents