Online Slides
September 10, 2002
These are slides from Computational
Intelligence, A
Logical Approach, Oxford University Press, 1998. Copyright ©David
Poole, Alan
Mackworth, Randy
Goebel and Oxford University Press,
19992002. You may prefer the pdf interface for
which these slides were designed (you can read pdf files using the free acrobat
reader).
A Representation and Reasoning System (RRS) is made up of:
 formal language: specifies the legal sentences
 semantics: specifies the meaning of the symbols
 reasoning theory or proof procedure: nondeterministic
specification of how an answer can be produced.
An implementation of an RRS consists of
 language parser: maps sentences of the language into data
structures.
 reasoning procedure: implementation of reasoning theory + search
strategy.
Note: the semantics aren't reflected in the implementation!
 Begin with a task domain.
 Distinguish those things you want to talk about (the ontology).
 Choose symbols in the computer to denote objects and relations.
 Tell the system knowledge about the domain.
 Ask the system questions.
An agent's knowledge can be usefully described in terms of
individuals and relations among individuals.
An agent's
knowledge base consists of definite and
positive statements.
The environment is static.
There are only a finite number of individuals of interest in the
domain. Each individual can be given a unique name.
=> Datalog
variable starts with uppercase letter.
constant starts with lowercase letter or is a sequence of
digits (numeral).
predicate symbol starts with lowercase letter.
term is either a variable or a constant.
atomic symbol (atom) is of the form p or p(t_{1},...,t_{n})
where p is a predicate symbol and t_{i} are terms.
definite clause is either an atomic symbol (a fact) or of
the form:
where a and b_{i} are atomic symbols.
query is of the form ?b_{1} & ··· & b_{m}.
knowledge base is a set of definite clauses.
in(alan,R) <
teaches(alan,cs322) &
in(cs322,R).
grandfather(william,X) <
father(william,Y) &
parent(Y,X).
slithy(toves) <
mimsy & borogroves &
outgrabe(mome,Raths).
A semantics specifies the meaning of
sentences in the language.
An interpretation specifies:
 what objects (individuals) are in the world
 the correspondence between symbols in the computer and objects
& relations in world
 constants denote individuals
 predicate symbols denote relations
An interpretation
is a triple I=<D,phi,pi>, where
 D, the domain, is a nonempty set.
Elements of D are individuals.
 phi is a
mapping that assigns to each constant an element of D. Constant
c denotes individual phi(c).
 pi is a
mapping that assigns to each nary predicate symbol a relation:
a function
from D^{n} into { TRUE, FALSE}.
Constants: phone, pencil, telephone.
Predicate Symbol: noisy (unary), left_of (binary).
 The domain D can contain real objects. (e.g., a person, a room, a
course). D can't necessarily be stored in a computer.
 pi(p) specifies whether the relation denoted by the nary predicate
symbol p is true or false for each ntuple of individuals.
 If
predicate symbol p has no arguments, then pi(p) is either TRUE
or FALSE.
A constant c denotes in I the individual phi(c) .
Ground (variablefree) atom p(t_{1},...,t_{n}) is
 true in interpretation
I if pi(p)(t_{1}',...,t_{n}')= TRUE, where t_{i} denotes
t_{i}' in interpretation I
and
 false in interpretation I if pi(p)(t_{1}',...,t_{n}')= FALSE.
Ground clause h < b_{1} & ... & b_{m} is false in interpretation I if h
is false in I and each b_{i} is true in
I, and is true in interpretation I otherwise.
In the interpretation given before:
noisy(phone)  true 
noisy(telephone)  true 
noisy(pencil)  false 
left_of(phone,pencil)  true 
left_of(phone,telephone)  false 
noisy(pencil) < left_of(phone,telephone)  true 
noisy(pencil) < left_of(phone,pencil)  false 
noisy(phone) < noisy(telephone) & noisy(pencil)  true 
 A knowledge base, KB, is true in interpretation I
if and only if every clause in KB is true in I.
 A model of a set of clauses is an
interpretation in which all the clauses are
true.
 If KB is a set of clauses and g is a
conjunction of atoms, g is a logical consequence
of KB, written
KBg,
if g is true in every model of KB.
 That is, KBg if
there is no interpretation in which KB is true and g is false.
KB={
}
 pi(p)  pi(q)  pi(r)  pi(s) 
I_{1}  TRUE  TRUE  TRUE  TRUE  is a model of KB 
I_{2}  FALSE  FALSE  FALSE  FALSE  not a model of KB 
I_{3}  TRUE  TRUE  FALSE  FALSE  is a model of KB 
I_{4}  TRUE  TRUE  TRUE  FALSE  is a model of KB 
I_{5}  TRUE  TRUE  FALSE  TRUE  not a model of KB 

KB p, KB q, KB r, KB s
 Choose a task domain: intended interpretation.
 Associate constants with individuals you want to
name.
 For each relation you want to represent, associate a predicate
symbol in the language.
 Tell the system clauses that are true in the intended
interpretation: axiomatizing the domain.
 Ask questions about the intended interpretation.
 If KB g, then g must be true in the intended interpretation.
 The computer doesn't have access to the intended interpretation.
 All it knows is the knowledge base.
 The computer can determine if a formula is a logical consequence
of KB.
 If KB g then g must be true in the intended
interpretation.
 If KBg then there is a model of KB in which g
is false. This could be the intended interpretation.
 Variables are universally quantified in the scope of a clause.
 A variable assignment is a function from variables into the
domain.
 Given an interpretation and a variable assignment,
each term denotes an individual and
each clause is either true or false.
 A clause containing variables is true in an interpretation if it is
true for all variable assignments.
A query is a way to ask if a body is a logical consequence of the
knowledge base:
?b_{1} & ··· & b_{m}.
An answer is either
 an instance of the query that is a logical consequence
of the knowledge base KB, or
 no if no instance is a logical consequence of KB.
KB={
in(alan,r123). 
part_of(r123,cs_building). 
in(X,Y) < part_of(Z,Y) & in(X,Z).

}
Query  Answer 
?part_of(r123,B).  part_of(r123,cs_building) 
?part_of(r023,cs_building).  no 
?in(alan,r023).  no 
?in(alan,B).  in(alan,r123) 
 in(alan,cs_building)

Atom g is a logical consequence of KB if and only if:
 g is a fact in KB, or
 there is a rule
g < b_{1} & ... & b_{k}
in KB such that each b_{i} is a logical consequence of KB.
To debug answer g that is false in the intended interpretation:
 If g is a fact in KB, this fact is wrong.
 Otherwise, suppose g was proved using the rule:
g < b_{1} & ... & b_{k}
where each b_{i} is a logical consequence of KB.
 If each b_{i} is true in the intended interpretation, this clause
is false in the intended interpretation.
 If some b_{i} is false in the intended interpretation, debug b_{i}.
%~light(L) is true if L is a light 
light(l_{1}).  light(l_{2}). 
%~down(S) is true if switch S is down 
down(s_{1}).  up(s_{2}).  up(s_{3}). 
%~ok(D) is true if D is not broken 
ok(l_{1}). 
ok(l_{2}).  ok(cb_{1}). 
ok(cb_{2}).

?light(l_{1}).  =>  yes 
?light(l_{6}).  =>  no 
?up(X).  =>  up(s_{2}), up(s_{3})

connected_to(X,Y) is true if component X is connected to Y
connected_to(w_0,w_1) < up(s_2).
connected_to(w_0,w_2) < down(s_2).
connected_to(w_1,w_3) < up(s_1).
connected_to(w_2,w_3) < down(s_1).
connected_to(w_4,w_3) < up(s_3).
connected_to(p_1,w_3).
?connected_to(w_{0},W).  =>  W=w_{1} 
?connected_to(w_{1},W).  =>  no 
?connected_to(Y,w_{3}).  =>  Y=w_{2}, Y=w_{4}, Y=p_{1} 
?connected_to(X,W).  =>  X=w_{0}, W=w_{1}, ... 
% lit(L) is true if the light L is lit
lit(L) < light(L) & ok(L) & live(L).
% live(C) is true if there is power coming into C
live(Y) <
connected_to(Y,Z) &
live(Z).
live(outside).
This is a recursive definition of live.
above(X,Y) < on(X,Y).
above(X,Y) < on(X,Z) & above(Z,Y).
This can be seen as:
 Recursive definition of above:
prove above in terms of a base case (on) or a simpler instance of
itself; or
 Way to prove above by mathematical induction:
the base case is when there are no blocks between X and Y, and if you can prove above when
there are n blocks between them, you can prove it when there are
n+1 blocks.
Suppose you had a database using the relation:
enrolled(S,C)
which is true when student S is enrolled in course C.
You can't define the relation:
empty_course(C)
which is true when course C has no students enrolled in it.
This is because empty_course(C) doesn't logically follow from a set
of enrolled relations. There are always models where someone is
enrolled in a course!
 A proof is a mechanically derivable demonstration that a
formula logically follows from a knowledge base.
 Given a proof procedure, KB g means g can be derived
from knowledge base KB.
 Recall KB g means g is true in all models
of KB.
 A proof procedure is sound if KB g implies KB
g.
 A proof procedure is complete if KB g implies KB
g.
One rule of
derivation, a generalized form of modus
ponens:
If "h < b_{1} & ... & b_{m}" is a clause
in the knowledge base, and each b_{i} has been derived,
then h can be derived.
You are forward chaining
on this clause.
(This rule also covers the case when m=0.)
KBg if g in C at the end of this procedure:
C:={}; 
repeat 
 select clause "h < b_{1} & ... & b_{m}" in KB such that 
  b_{i} in C for all i, and 
  h not in C; 
 C:=C union {h} 
until no more clauses can be selected.

 Don'tcare nondeterminism If one selection doesn't
lead to a solution, there is no point trying other alternatives.
select
 Don'tknow nondeterminism If one choice doesn't lead
to a solution, other choices may. choose
a < b & c.
a < e & f.
b < f & k.
c < e.
d < k.
e.
f < j & e.
f < c.
j < c.
If KBg then KBg.
Suppose there is a g such that KBg and KBg.
Let h be the first atom added to C that's not true in
every model of KB. Suppose h isn't
true in model I of KB.
There must be a clause in KB of form
h < b_{1} & ... & b_{m}
Each b_{i} is true in I. h is false in I. So this clause is
false in I. Therefore I isn't a model of KB.
Contradiction: thus
no such g exists.
The C generated at the end of the bottomup algorithm is called a
fixed point.
Let I be the interpretation in which every element of the fixed
point is true and every other atom is false.
I is a model of KB.
Proof: suppose h < b_{1} & ... & b_{m} in KB
is false in I. Then h is false and each b_{i} is true in I. Thus
h can be added to C. Contradiction to C being the fixed point.
I is called a Minimal Model.
If KBg then KBg.
Suppose KBg. Then g is true in all models of KB.
Thus g is true in the minimal model.
Thus g is generated by the bottom up algorithm.
Thus KBg.
Idea: search backward from a query to determine if it is a logical
consequence of KB.
An answer clause is of the form:
yes < a_1 & a_2 & ... & a_m
The SLD Resolution of this answer clause on atom a_{i} with
the clause:
is the answer clause
yes < a_1 & ··· & a_i1 & b_1 & ··· & b_p & a_i+1 & ··· & a_m.
 An answer is an answer clause with m=0. That
is, it is the answer clause yes < .
 A derivation of query "?q_{1} & ... & q_{k}"
from KB is a sequence of answer clauses gamma_{0}, gamma_{1},
..., gamma_{n} such that
 gamma_{0} is the answer clause yes < q_{1} & ... & q_{k},
 gamma_{i} is obtained by resolving gamma_{i1} with a
clause in KB, and
 gamma_{n} is an answer.
To solve the query ?q_{1} & ... & q_{k}:
 ac:= "yes < q_{1} & ... & q_{k}" 
 repeat 
  select a conjunct a_{i} from the body of ac; 
  choose clause C from KB with a_{i} as head; 
  replace a_{i} in the body of ac by the body of C 
 until ac is an answer.

a < b & c. 
a < e & f. 
b < f & k. 
c < e. 
d < k. 
e. 
f < j & e. 
f < c. 
j < c.

Query: ?a
gamma_{0}:  yes < a  gamma_{4}:  yes < e 
gamma_{1}:  yes < e & f  gamma_{5}:  yes < 
gamma_{2}:  yes < f  
gamma_{3}:  yes < c

a < b & c. 
a < e & f. 
b < f & k. 
c < e. 
d < k. 
e. 
f < j & e. 
f < c. 
j < c.

Query: ?a
gamma_{0}:  yes < a  gamma_{4}:  yes < e & k & c 
gamma_{1}:  yes < b & c  gamma_{5}:  yes < k & c 
gamma_{2}:  yes < f & k & c  
gamma_{3}:  yes < c & k & c

 An instance of an atom or a clause is obtained by uniformly
substituting terms for variables.
 A substitution is a finite set of
the form {V_{1}/t_{1},...,V_{n}/t_{n}}, where each V_{i}
is a distinct variable and each t_{i} is a term.
 The application of a
substitution sigma={V_{1}/t_{1},...,V_{n}/t_{n}} to an atom or clause e,
written esigma, is the instance of
e with every occurrence of V_{i} replaced by
t_{i}.
The following are substitutions:
 sigma_{1}={X/A,Y/b,Z/C,D/e}
 sigma_{2}={A/X,Y/b,C/Z,D/e}
 sigma_{3}={A/V,X/V,Y/b,C/W,Z/W,D/e}
The following shows some applications:
 p(A,b,C,D) sigma_{1} = p(A,b,C,e)
 p(X,Y,Z,e) sigma_{1} = p(A,b,C,e)
 p(A,b,C,D) sigma_{2} = p(X,b,Z,e)
 p(X,Y,Z,e) sigma_{2} = p(X,b,Z,e)
 p(A,b,C,D) sigma_{3} = p(V,b,W,e)
 p(X,Y,Z,e) sigma_{3} = p(V,b,W,e)
 Substitution sigma is a unifier
of e_{1} and e_{2}
if e_{1}sigma=e_{2}sigma.
 Substitution sigma is a most general unifier (mgu)
of e_{1} and e_{2} if
 sigma is a unifier of e_{1} and e_{2}; and
 if
substitution sigma' also
unifies e_{1} and e_{2}, then esigma' is an instance of e
sigma for all atoms e.
 If two atoms have a unifier, they have a most
general unifier.
p(A,b,C,D) and p(X,Y,Z,e) have as unifiers:
 sigma_{1}={X/A,Y/b,Z/C,D/e}
 sigma_{2}={A/X,Y/b,C/Z,D/e}
 sigma_{3}={A/V,X/V,Y/b,C/W,Z/W,D/e}
 sigma_{4}={A/a,X/a,Y/b,C/c,Z/c,D/e}
 sigma_{5}={X/A,Y/b,Z/A,C/A,D/e}
 sigma_{6}={X/A,Y/b,Z/C,D/e,W/a}
The first three are most general unifiers.
The following substitutions are not unifiers:
 sigma_{7}={Y/b,D/e}
 sigma_{8}={X/a,Y/b,Z/c,D/e}
A generalized answer clause is of the form
yes(t_1,...,t_k) < a_1 & a_2 & ... & a_m,
where t_{1},...,t_{k} are terms and a_{1},...,a_{m} are atoms.
The
SLD resolution
of this generalized answer clause on a_{i} with the clause
where a_{i} and a have most general unifier theta, is
(yes(t_1,...,t_k) <
a_1 & ... & a_i1 & b_1 & ... & b_p & a_i+1 & ... & a_m)theta.
To solve query ?B with variables V_{1},...,V_{k}:
Set ac to generalized answer clause yes(V_{1},...,V_{k}) < B; 
While ac is not an answer do 
 Suppose ac is yes(t_{1},...,t_{k}) < a_{1} & a_{2} & ... & a_{m} 
 Select atom a_{i} in the body of ac; 
 Choose clause a < b_{1} & ... & b_{p} in KB; 
 Rename all variables in a < b_{1} & ... & b_{p}; 
 Let theta be the most general unifier of a_{i} and a. 
  Fail if they don't unify; 
 Set ac to (yes(t_{1},...,t_{k}) < a_{1} & ... & a_{i1} & 
     b_{1} & ... & b_{p} & a_{i+1} & ... & a_{m})theta 
end while.

live(Y) < connected_to(Y,Z) & live(Z).live(outside).
connected_to(w_6,w_5).connected_to(w_5,outside).
?live(A).
yes(A) < live(A).
yes(A) < connected_to(A,Z_1) & live(Z_1).
yes(w_6) < live(w_5).
yes(w_6) < connected_to(w_5,Z_2) & live(Z_2).
yes(w_6) < live(outside).
yes(w_6) < .
Often we want to refer to individuals in terms of components.
Examples: 4:55 p.m. English sentences. A classlist.
We extend the notion of term. So that a term can be f(t_{1},...,t_{n})
where f is a function symbol and the t_{i} are terms.
In an interpretation and with a variable assignment,
term f(t_{1},...,t_{n}) denotes an individual in
the domain.
With one function symbol and one constant we can refer to infinitely
many individuals.
A list is an ordered sequence of elements.
Let's use the constant nil to denote the empty list, and
the function cons(H,T) to denote the list with first
element H and restoflist T. These are not builtin.
The list containing david, alan and randy is
cons(david,cons(alan,cons(randy,nil)))
append(X,Y,Z) is true if list Z contains the elements of X
followed by
the elements of Y
append(nil,Z,Z).
append(cons(A,X),Y,cons(A,Z)) < append(X,Y,Z).
©David
Poole, Alan
Mackworth, Randy
Goebel and Oxford University Press,
19982002