Resolution & Refutation (review) Short Quiz Prolog Introduction & Exercise
, ,
(KB P false) KB P
Translate facts and rules into predicate logic Tranform sentence into CNF (conjunctive normal form) / horn clause / well formed formula p1 ... p j .... pn1 r1 ...rn2 s1 .... s n3 q1 ... qk .... qn 4 SUBST ( , p1 ... p j 1 p j 1 .... pm s1 ... sn 3 r1 ...rn 2 q1 ... qk 1 qk 1 .... qn )
1. 2. 3. 4. 5. 6.
Eliminate implications & bi-conditionals Move inwards Standardize variables: each quantifier has different ones Skolemize: choose a “fact” to eliminate Eliminate Distribute ^ over v
Buktikan bahwa “Marcus membenci Caesar” Facts 1. 2. 3. 4.
Marcus adalah seorang manusia Marcus orang Pompei Marcus mencoba membunuh Caesar Caesar adalah seorang penguasa
1. 2.
Semua orang Pompei adalah orang Romawi Semua orang Romawi setia pada Caesar atau membenci Caesar Setiap orang setia pada minimal 1 orang Orang hanya mencoba membunuh penguasa yang kepadanya mereka tidak setia
Rules
3. 4.
Facts: 1. man(marcus) 2. pompeian(marcus) 3. tryassassinate(marcus,caesar) 4. ruler(caesar) Rules: 1. x pompeian(x) roman(x) 2. x roman(x) loyalto(x, caesar) v hate(x,caesar) 3. x y loyalto(x, y) 4. x y man(x) ^ ruler(y) ^ tryassassinate(x,y) loyalto(x,y) Prove that: hate(marcus, caesar), use refutation.
Make CNF from rules pompeian(x) v roman(x) roman(x) v loyalto(x,caesar) v hate(x,caesar) loyalto(x,y) (man(x) ^ ruler(y) ^ tryassassinate(x,y)) v loyalto(x,y) man(x) v ruler(y) v tryassassinate(x,y) v loyalto(x,y) Apply substitutions into variable, and try to change rules into facts. 1. 2. 3. 4.
PROLOG = “Programmation en logique” (Marseille, 1972) Declarative programming language with procedural elements Used for problems of AI / knowledge-based (expert) systems Motivation: reconcile use of logic as declarative knowledge representation with procedural representation of knowledge Strengths: Logical descriptions of problems, instead of HOW to solve them let computer work out the solution Well-suited for problems involving search Simple programs can be understood by reading the code Limitations Flow of control / procedural semantics
Prolog-program = collection of clauses = meta programming Facts Rules Goals (queries), shaped liked facts Facts describe properties of objects and relations between objects; comparable to tables in a relational database
student
Name
interest
Name
Hans Tina Lars Frida Prolog notation: Prolog notation: student(hans). interest(hans,math). student(tina). interest(tina,datalogi). student(lars). interest(lars,physics). student(frida). interest(frida,math).
Hans Tina Lars Frida
Subject
Math Datalogi Physics Math
Prolog notation (facts):
<predicate_name>(arg1, arg2…).
Simple IF-THEN statements “Every reasonable student is interested in math.” interest(X,math) :- student(X). head
body
All specified conditions in the body (all clauses) must be true to make the predicate in the head true. Conjunctions (AND connected): mother(X,Person) :- parent(X,Person),sex(X,female). Disjunctions (OR connected): interest(X,prolog) :- interest(X,artificial_intelligence). interest(X,prolog) :- interest(X,logic).
Goals are queries One ore more subgoals ?- student(thomas). => no Pattern matching: a fact matches a goal if Same predicate Same corresponding arguments. Goals can contain variables: ?- student(X). => X = hans ; => X = tina ; => X = lars ; => X = frida ; => no. Variables are instantiated( included in rules),but cannot be declared!
Leftmost-depth-first search for solutions Matching: either two terms are identical, or they become identical by variable substitution (resolution based on pred.logic) Processing of subgoals from left to right Backtracking (from goal try to substitute variables into facts or rules) 1: 2: 3: 4: 5: ?- p(Z).
1 Z=a
s(Z)
s(a). s(b). q(a). p(X) :- s(X). p(Y) :- q(Y). p(Z) 5
4 2
Z=b
q(Z)
3 Z=a
The Prolog interpreter uses backward chaining: starting from a goal (theorem) prove the goal by searching for rules whose ”head” (action part) matches the goal Given are the following rules: 1 E AC X
2 H F C 3 H BE
H
4 CB 5 X H
F&C
B&E
facts
AND
AND
prove
A, B
OR
F
C
B
E
X
AND B
A
C B
http://www.swi-prolog.org (ver. 5.6.62) Graphical User Interface (XPCE) Interface with Java, C++ Steps: Consult / Compile Goal search / Execute Debug > Graphical Debugger Trace: show you how the unification &
substitution occurs
Use prolog to prove the “Marcus’s Case” man(marcus). pompeian(marcus). ruler(caesar). tryassassinate(marcus, caesar). roman(X) :- pompeian(X). hate(X, Y) :- man(X), ruler(Y), tryassassinate(X, Y). loyalto(X, Y) :- man(X), ruler(Y).
George
x Mum
Spencer
x Kydd
Elizabeth
Diana
x Charles
Anne
William
Harry
Peter
x Philip
x Mark
Zara
Margaret
Andrew
Beatrice
x Sarah
Eugenie
Edward
Buat fakta berdasarkan pohon keluarga di atas Buat aturan untuk aturan: saudaraLaki(X,Y) X berjenis kelamin laki-laki, X dan Y adalah anak dari seseorang, X dan Y bukan orang yang sama
saudaraPerempuan(X,Y) X berjenis kelamin perempuan, X dan Y adalah anak dari seseorang, X dan Y bukan orang yang sama bersaudaraKandung(X,Y) X dan Y memiliki ayah dan ibu yang sama, X dan Y bukan orang yang sama kakek(X,Y,Z) X adalah ayah dari Y, Y adalah ayah dari Z nenek(X,Y,Z) X adalah ibu dari Y, Y adalah ibu dari Z
Simple data structure to process non-numeric relation A list is a set of ordered sequential elements [2,2,1,1,4,4,5,6] [b,u,d,i] [budi, iwan, wati] How to use a list? Simple case: empty [] Ordered element: [head|tail] ▪ [2,2,1,1,4,4,5,6] [ 2 | [2,1,1,4,4,5,6] ]
[a,b,c] unifies with [Head|Tail] resulting in Head=a and Tail=[b,c] [a] unifies with [H|T] resulting in H=a and T=[] [a,b,c] unifies with [a|T] resulting in T=[b,c] [a,b,c] doesn't unify with [b|T] [] doesn't unify with [H|T] [] unifies with []. Two empty lists always can be unified.
Predicate: member(X,List). X is a member of List, in case of: 1. X is a head, or 2. X is a member of the tail member(X,[X|Tail]). member(X,[Head|Tail]):member(X,Tail).
reverse([],X,X). reverse([X|Y],Z,W) :- reverse(Y,[X|Z],W). reverse([1,2,3],[],A) reverse([2,3],[1],A) reverse([3],[2,1],A) reverse([],[3,2,1],A) true A = [3,2,1]
1. [a,b,c,d]=[a,[b,c,d]]. 2. [a,b,c,d]=[a|[b,c,d]]. 3. [a,b,c,d]=[a,b,[c,d]]. 4. [a,b,c,d]=[a,b|[c,d]]. 5. [a,b,c,d]=[a,b,c,[d]]. 6. [a,b,c,d]=[a,b,c|[d]]. 7. [a,b,c,d]=[a,b,c,d,[]]. 8. [a,b,c,d]=[a,b,c,d|[]]. 9. []=_. 10. []=[_]. 11. []=[_|[]].
What should Prolog give as result?
Develop a dictionary to translate number 1..10 from Indonesian to English and vice versa, example: Translate([satu, sembilan],Y). Y = [one,nine] Translate(Z,[one]). Z = [satu] Translate([],[]).
