Knowledge Representation

• To pass the Turing test a computer must

store large amounts of knowledge
• Knowledge=data+rules
• Rules can be general or related to specific
fields
 Rules examples
• If x>y and y>z then x>z
• If x is a parent of y and y is a parent of z
then x is a grand parent of z
• If patient has high tepmerature and soar
throught then he has flu
 Knowledge Representation
• A good knowledge representation method
should have:
• representational adequacy
• Inferential adequacy
• Acquisitional adequacy
 Logic
• A major knowledge representation method
• Two types: propositonal, predicate
 Proposional Logic
• Simple statements are represented by symbols
p, q, …
• Compound statements are constructed by
connecting symbols with logical connectives
• Basic logical connectives: and, or, not
• Other logical connectives:  <-> exclusive or.
The connectives can be written in terms of basic
connectives.
• Example: , exclusive or.
• Truth table
 Example
• Represent in propositional logic
– Ali is at home
– Ali is at school
– Ahmad is at school
– Sami is at school
– Ali is at home or sami is at school
– Ali is at home or ali is at school
– Ali is at home and ahmad is not at school
– If both ali and ahmad are at school then Sami is not at
home
Proposional logic disadvantage
• Consider
– Every university student has passed Tawjeehi
– Ali is a university student
• Representing these statements in symbols
does not support inference of “Ali has
passed Tawjeehi"
 Predicate Logic
Uses:
• Predicates
• Logical connectives
• Quantifiers
 Predicates
• A predicate represents a simple statement
• General form
predicate-name(arg1,…,argn)
• Examples
Student(ali)// assuming student(x) means x is a student
Teacher(ahmad) //assuming that Teacher(x) means x is a
teacher
Father(jamal,sami) //assuming Father(x,y) means x is the father of y
G(5,3) // G(x,y) means x>y
Sum(4,5,9) //assuming Sum(i,j,k) means i+j=k
 Logical connectives
• And
• Or
• Not
• 
• …
 Quantifiers
• Existential quantifier: xp(x), p is true for
some value x
• Universal quantifier: xp(x), p is true for all
values x in the universe
• Example
x pass(x,ai-second-exam)
x pass(x,ai-second-exam)
 Examples
Let
B(x,y) mean “element x belongs to set y”
G(x,y) mean “x>y”
Represent each of the following in predicate logic
5 belongs to s1
6 belongs to s2 and 3 does not belong to s1
All elements in s1 are positive
Set s1 is [strict] subset of s3
Every element in s4 is greater than 7
Any element in s5 is larger than any element in s6
Any element in s6 is larger than some element in s7
All elements in the intersection of s5 and s7 are positive
 Order of quantifiers
Consider likes(x,y): person x likes food y.
xy likes(x,y)

yx likes(x,y)

yx likes(x,y)//every food is liked by someone

xy likes(x,y)//there is some who likes all kinds of food

xy likes(x,y)//every person likes some food

yx likes(x,y)//there is a food that is liked by all people

 Clause form
• Simple form needed for inference
• Literal: predicate or negation of a
predicate
• Clause: zero or more literals connected
with or
• examples
 Convert to clause form
• Input: a predicate logic statement S
• Output: one or more clauses representing S
• Steps:
1. Eliminate 
• Use ab is equivalent to ab
• Examples
x p(x)  x t(x)
(ab)c
(ab)(cd)
2. Reduce scope of negation to a
single predicate
• Use:
(p) = p
(ab) = (a b)
(ab) = (ab)
 xp(x) = xp(x)
 xp(x) = xp(x)
3. Use a different variable for every
quantifier
• example
4. Eliminate 
• Case I:  does not occur inside the scope
of any . Remove  and replace variable
with a new constant denoting unknown
value.
• Examples
x student(x)
x student(x)  x teacher(x)
x [student(x)  teacher(x)]
xy teaches(x,y)
4. Eliminate 
• Case II:  occurs inside the scope of one
or more . Remove  and replace variable
with a new function of  variables. The
function denotes unknown relation.
• Examples
xy father(y,x)
xyz p(x,y,z)
5. Drop quantifiers. All variables are
implicitly universally quantified
6. Convert the statement into the
form
C1C2…  Cn.
Often use:
A(BC)=(AB)(AC)
(AB)(CD)=(AC)(AD)(BC)(BD)
7. Separate clauses. and becomes
implicit
Example
(AC)(AD)(BC)(BD) becomes
1. AC
2. AD
3. BC
4. BD
8. Make clauses use different
variables
Example
x[p(x)r(x)] becomes
1. p(x)
2. r(y)
 Example
“Every element in S is > an element in T”
x(B(x,S)  y(B(y,T)GT(x,y)))
x(B(x,S) y(B(y,T)GT(x,y)))
x(B(x,S)  (B(f(x),T)GT(x,f(x))))
B(x,S)  (B(f(x),T)GT(x,f(x)))
(B(x,S)  B(f(x),T))(B(x,S)  GT(x,f(x)))
The resulting clauses
B(x,S)  B(f(x),T)
B(x,S)  GT(x,f(x))
 Exercises
Convert to clause form:
xy[z p(x,y,z) w r(x,y,w)] 
x t(x)  yz s(y,z)

Final Answer:
p(c1,c2,c3)  t(c5)  s(c6,c7)
r(c1,c2,c4)  t(c5)  s(c6,c7)
 Resolution
• Based on proof by contradiction.
• Basic step
Given two clauses:
p  r
p
-------------
r
• Modus ponens: from pr and p, can infer r
More resolution examples
prt
p
-------------
rt

pr
pt
-------------
 rt
More resolution examples
prt
psq
-------------
 rtsq

p
p
-------------
  (empty clause contradiction)
 Resolution with Variables

prime(X)  GT(X,2)
prime(5)
----------------------------------

 GT(5,2)
 Unification
• Resolution requires contradiction
between 2 literals
• Literals containing variables contradict if
One of them is negated and
The two predicates can be made
identical by consistently replacing
variables with values (unification)
 Unifier
• The list of variables substitutions that
make two expressions identical is called a
unifier for the two expressions
• The unifier whose result subsumes any
other unifier’s result is known as most
general unifier [MGU]
• Example the MGU for prime(X) and
prime(5) is [X=5]
 Another Example
p(x)
p(y)
Universe = {1, 3, 5}
-----------------------
Some possible unifiers
[x=1, y=1]
[x=3, y=3]
[x=5, y=5]
[x=y] //MGU
[y=x] //MGU
 Unification cases
e1 e2 MGU
c1 c1 []

c1 c2 none
x x []
x y [x=y] or [y=x]
x c1 [x=c1]
x f(c1) [x=f(c1)]
x f(y) [x=f(y)]
x f(x) none
p(x) r(x) none
p(x,y) p(x) none
p(x,y,z) p(c1,c2,c3) [x=c1, y=c2, z=c3]
p(x,x) p(c1,c2) none
p(x,x) p(c1,c1) [x=c1]
 Unification Algorithm
unify(E1, E2){
if (E1 or E2 is a variable or a constant){
if (E1 and E2 are identical) return [ ];
if (E1 is a variable)
if (E1 occurs in E2)
return none;
else
return [E1=E2]
if (E2 is a variable)
if (E2 occurs in E1)
return none;
else
return [E2=E1]
}//if
If (initial predicates in E1 and E2 are different) return none;
If (E1 and E2 have different number of arguments) return none;
RESULT=[ ];
for(I=1; I<=number of arguments; I++){
TEMP=unify(I’th_arg(E1), I’th_arg(E2));
if (TEMP== none) return none;
if (TEMP != [ ]){
apply TEMP to remainder of E1 and E2;
append TEMP to RESULT;
}//if
}//for
Return RESULT;
}
 Example
Unify
p(X,Y,f(X,W),g(W,Z),X)
p(a,f(Z),f(Z,f(a)),g(f(X),a),Z)
 Resolution Algorithm

Input: a set of statements F (knowledge base) and a statement G to be

derived from F (F ⊢ G)
Output: SUCCESS (proof successful) or FAILURE (proof unsuccessful)
Steps
1. Convert all statements in F to clause form. Call resulting set of clauses C.
2. Negate G, convert result to clause form, add resulting clause(s) to C.
3. Select two clauses a, b such that a and b contradict on some literal, and
resolving a and b produces a new clause  C. If no such clauses can be
found return FAILURE.
4. r=resolve(a, b)
5. If (r==)return SUCCESS
6. add r to C
7. Go to 3
 Hints for selecting clauses
• Select G or a clause derived from G;
following the belief that G causes the
contradiction
• Prefer shorter clauses; closer to empty
clause
 Examples
Show that:

{p  q, p} ⊢ q //algorithm should return SUCCESS

{p  q, q} ⊢ p //algorithm should return FAILURE

 Example
Clauses
Show that
1.  p(X)  q(X)
{x [p(x)  q(x)],
2.  q(Y)  r(Y)
x [q(x)  r(x)],
3. s(Z)
x s(x),
4. p(W)
x p(x),
5.  s(U)   r(U)  k(U)
x [s(x)r(x)  k(x)]}
6.  k(c)
⊢
x k(x)
 Clauses C
1.  p(X)  q(x)
2.  q(Y)  r(Y)
3. s(Z)
4. p(W)
5.  s(U)   r(U)  k(U)
6.  k(c)
 Iteration 1
5.  s(U)   r(U)  k(U)
6.  k(c)
MGU: [U=c]
Resolution result:
7.  s(c)   r(c)
 Clauses C
1.  p(X)  q(x)
2.  q(Y)  r(Y)
3. s(Z)
4. p(W)
5.  s(U)   r(U)  k(U)
6.  k(c)
7.  s(c)   r(c)
 Iteration 2
3. s(z)
7.  s(c)   r(c)
MGU: [Z=c]
Resolution result:
8.  r(c)
 Clauses C
1.  p(X)  q(x)
2.  q(Y)  r(Y)
3. s(Z)
4. p(W)
5.  s(U)   r(U)  k(U)
6.  k(c)
7.  s(c)   r(c)
8.  r(c)
 Iteration 3
2.  q(Y)  r(Y)
8.  r(c)
MGU: [Y=c ]
Resolution result:
9.  q(c)
 Clauses C
1.  p(X)  q(x)
2.  q(Y)  r(Y)
3. s(Z)
4. p(W)
5.  s(U)   r(U)  k(U)
6.  k(c)
7.  s(c)   r(c)
8.  r(c)
9.  q(c)
 Iteration 4
1.  p(X)  q(X)
9.  q(c)
MGU: [X=c ]
Resolution result:
10.  p(c)
 Clauses C
1.  p(X)  q(x)
2.  q(Y)  r(Y)
3. s(Z)
4. p(W)
5.  s(U)   r(U)  k(U)
6.  k(c)
7.  s(c)   r(c)
8.  r(c)
9.  q(c)
10.  p(c)
 Iteration 5
4. p(W)
10.  p(c)
MGU: [W=c ]
Resolution result:
11. 
 Example
Given
1.uv [on(u,v)  above(u,v)]
2.xyz [above(x,y) above(y,z)above(x,z)]
3. on(b2,b1) //book b2 is on book b1
4. on(b1,t) //b1 is on table
Show that

above(b2,t)
 Convert into clauses
1.  on(U,V)  above(U,V)
2.  above(X,Y)  above(Y,Z)  above(X,Z)
3. on(b2,b1)
4. on(b1,t)
5. above(b2,t)
 Iteration 1
5. above(b2,t)
2.  above(X,Y)  above(Y,Z)  above(X,Z)

MGU: [X=b2, Z=t]

Resolution result:
6.  above(b2,Y)   above(Y,t)
Then becomes
6.  above(b2,Y1)   above(Y1,t)
 Set of clauses C
1.  on(U,V)  above(U,V)
2.  above(X,Y)  above(Y,Z)  above(X,Z)
3. on(b2,b1)
4. on(b1,t)
5. above(b2,t)
6.  above(b2,Y1)   above(Y1,t)
 Iteration 2
6.  above(b2,Y1)   above(Y1,t)
1.  on(U,V)  above(U,V)

MGU: [Y1=U, V=t]

Resolution result:
7.  above(b2,U)   on(U,t)
Then becomes
7.  above(b2,U1)   on(U1,t)
 Set of clauses C
1.  on(U,V)  above(U,V)
2.  above(X,Y)  above(Y,Z)  above(X,Z)
3. on(b2,b1)
4. on(b1,t)
5. above(b2,t)
6.  above(b2,Y1)   above(Y1,t)
7.  above(b2,U1)   on(U1,t)
 Iteration 3
7.  above(b2,U1)   on(U1,t)
1.  on(U,V)  above(U,V)

MGU: [U=b2, U1=V]

Resolution result:
8.  on(V,t)   on(b2,V)
Then 8. becomes
8.  on(V1,t)   on(b2,V1)
 Set of clauses C
1.  on(U,V)  above(U,V)
2.  above(X,Y)  above(Y,Z)  above(X,Z)
3. on(b2,b1)
4. on(b1,t)
5. above(b2,t)
6.  above(b2,Y1)   above(Y1,t)
7.  above(b2,U1)   on(U1,t)
8.  on(V1,t)   on(b2,V1)
 Iteration 4
8.  on(V1,t)   on(b2,V1)
3. on(b2,b1)

MGU: [V1=b1]
Resolution result:
9.  on(b1,t)
 Set of clauses C
1.  on(U,V)  above(U,V)
2.  above(X,Y)  above(Y,Z)  above(X,Z)
3. on(b2,b1)
4. on(b1,t)
5. above(b2,t)
6.  above(b2,Y1)   above(Y1,t)
7.  above(b2,U1)   on(U1,t)
8.  on(V1,t)   on(b2,V1)
9.  on(b1,t)
 Iteration 5
9.  on(b1,t)
4. on(b1,t)
MGU: [ ]
Resolution result:
10. 
 Set of clauses C
1.  on(U,V)  above(U,V)
2.  above(X,Y)  above(Y,Z)  above(X,Z)
3. on(b2,b1)
4. on(b1,t)
5. above(b2,t)
6.  above(b2,Y1)   above(Y1,t)
7.  above(b2,U1)   on(U1,t)
8.  on(V1,t)   on(b2,V1)
9.  on(b1,t)
10. 