Online Slides
October 29, 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).
 Sometimes two terms denote the same individual.
 Example: Clark Kent & superman. 4×4 & 11+5.
The projector we used last Friday & this projector.
 Ground term t_{1} equals ground term t_{2}, written t_{1}=t_{2},
is true in interpretation I if t_{1} and t_{2} denote the same
individual in interpretation I.
chair1 != chair2
chair_on_right = chair2
chair_on_right is not similar to chair2, it is chair2.
 In a doctor's office, the doctor wants to know if a patient is the same
patient that she saw last week (or is his twin sister).
 In a criminal investigation, the police want to determine if
someone is the same person as the person who committed some crime.
 When buying a replacement switch, an electrician may want
to know if it was built in the same factory as the switches that were
unreliable. (And if it is a different switch to the one that was
replaced the previous time).
X=X.
X=Y < Y=X.
X=Z < X=Y & Y=Z.
For each nary function symbol f there is a rule of
the form
f(X_1,...,X_n)=f(Y_1,..., Y_n) <
X_1=Y_1 & ··· & X_n=Y_n.
For each nary predicate symbol p, there is a rule of the form
p(X_1,...,X_n) <
p(Y_1,..., Y_n) & X_1=Y_1 & ··· & X_n=Y_n.
paramodulation: if you have t_{1}=t_{2}, then you can replace
any occurrence of t_{1} by t_{2}.
Treat equality as a rewrite rule, substituting equals for equals.
You select a canonical representation for each
individual and rewrite all other representations into that
representation.
Example: treat the sequence of digits as the canonical representation of the
number.
Example: use the student number as the canonical representation for students.
The convention that
different ground terms denote different individuals is the
unique names assumption.
For every pair of distinct ground
terms t_{1} and
t_{2}, assume t_{1} != t_{2}, where " != " means "not equal to."
Example: For each pair of courses, you don't want to have to
state, math302 != psyc303, ...
Example: Sometimes the unique names assumption is
inappropriate, for example 3+7 != 2×5 is wrong.
 c != c' for any distinct constants c and c'.
 f(X_{1},...,X_{n}) != g(Y_{1},...,Y_{m}) for any distinct
function symbols f and g.
 f(X_{1},...,X_{n}) != f(Y_{1},...,Y_{n}) < X_{i} != Y_{i},
for any function symbol f. There are n instances of this schema
for every nary function symbol f (one for each i such that
1 <= i <= n).
 f(X_{1},...,X_{n}) != c for any function symbol f and
constant c.
 t != X for any term t in which X appears (where t is
not the term X).
 Inequality isn't just another predicate. There are infinitely many
answers to X != f(Y).
 If you have a subgoal t_{1} != t_{2}, for terms t_{1} and t_{2} there are three cases:
 t_{1} and t_{2} don't unify. In this case, t_{1} != t_{2} succeeds.
 t_{1} and t_{2} are identical including having the same variables in
the same positions. Here t_{1} != t_{2} fails.
 Otherwise, there are instances of t_{1} != t_{2} that succeed
and instances of t_{1} != t_{2} that fail.
 Recall: in SLD resolution you can select any subgoal
in the body of an answer clause to solve next.
 Idea: only select inequality when it will either
succeed or fail, otherwise select another subgoal. Thus you are
delaying inequality goals.
 If only inequality subgoals remain, and none fail, the query succeeds.
notin(X,[]).
notin(X,[HT]) < X != H & notin(X,T).
good_course(C) < course(C) & passes_analysis(C).
course(cs312).
course(cs444).
course(cs322).
passes_analysis(C) < something_complicated(C).
? notin(C,[cs312,cs322,cs422,cs310,cs402])
& good_course(C).
 Sometimes you want to assume that a database of facts is complete.
Any fact not listed is false.
 Example: Assuming a database of enrolled(S,C) relations is
complete, you can define empty_course(C).
 The definite clause RRS is monotonic: adding clauses doesn't
invalidate a previous conclusion.
 With the complete knowledge assumption, the system is
nonmonotonic: a conclusion can be invalidated by adding more clauses.
 Suppose the rules for atom
a are
a < b_{1}. 
... 
a < b_{n}.

or equivalently: a < b_{1} or ... or b_{n}
 Under the CKA, if
a is true, one of the b_{i} must be true:
 Under the CKA, the clauses for a mean Clark's completion:
Example: Consider the relation defined by:
student(mary).
student(john).
student(ying).
The CKA specifies these three are
the only students:
student(X) <> X=mary or X=john or X=ying.
To conclude ¬student(alan), you have to be able to prove
alan != mary & alan != john & alan != ying
This needs the unique names assumption.
The Clark normal form
of the clause:
is the clause
p(V_1,...,V_k) <
exist W_1...exist W_m
V_1=t_1 & ... & V_k
=t_k & B,
where V_{1},...,V_{k} are k different variables that did not appear in the original
clause.
W_{1},...,W_{m} are the original variables in the clause.
 The Clark normal form of:
room(C,room208) <
cs_course(C) & enrollment(C,E) & E<120.
is
room(X,Y) < exist C exist E X=C & Y=room208 &
cs_course(C) & enrollment(C,E) & E<120.
Put all of the clauses for
p into Clark normal form, with the
same set of introduced variables:
p(V_1,...,V_k) < B_1
...
p(V_1,...,V_k) < B_n
This is the same as: ~~
p(V_{1},...,V_{k}) < B_{1} or ... or B_{n}.
Clark's completion of
p is the equivalence
p(V_1,...,V_k)
<> B_1 or ... or B_n,
That is, p(V_{1},...,V_{k}) is true if and only if one
B_{i} is true.
Given the mem function:
mem(X,[XT]).
mem(X,[HT]) < mem(X,T).
the completion is
mem(X,Y) <> (exist T Y=[XT]) or
(exist H exist T Y=[HT] & mem(X,T))
 Clark's completion of a knowledge base consists of the
completion of every predicate symbol, along with
the axioms for equality and
inequality.
 If you have a predicate p defined by no
clauses in the knowledge base, the completion is p <> false. That
is, ¬p.
 You can interpret negations in the
bodies of clauses.
~
p means that p is false under the Complete
Knowledge Assumption. This is called negation as
failure.
Previously we couldn't define empty_course(C) from a database of
enrolled(S,C).
This can be defined using negation as failure:
empty_course(C) <
course(C) &
~
has_Enrollment(C).
has_Enrollment(C) <
enrolled(S,C).
C:={}; 
repeat 
 either select "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} 
 or select h such that 
   for every rule "h < b_{1} & ... & b_{m}" in KB 
    either for some b_{i}, ~ b_{i} in C 
    or some b_{i}= ~ g and g in C 
  C:=C union { ~ h} 
until no more selections are possible

p < q & ~
r.
p < s.
q < ~
s.
r < ~
t.
t.
s < w.
 If the proof for a fails, you can conclude
~
a.
 Failure and success can be defined recursively:
 Suppose you have rules for atom a:
a < b_{1} 
... 
a < b_{n}

If each body b_{i} fails, a fails.
If one body, b_{i} succeeds, a succeeds.
 A
body fails if one of the conjuncts in the body
fails.
A body succeeds if all of the conjuncts succeed.
 If a fails,
~
a succeeds. If a succeeds ~
a
fails.
Example:
p(X) < ~
q(X) & r(X).
q(a).
q(b).
r(a).
r(c).
There is only one answer to the query
?p(X), namely
X=c.
For calls to negation as failure with free variables,
you need to delay negation as failure goals that contain free
variables until the variables become
bound.
If the variables never become bound, a negated goal flounders.
In this case you can't conclude
anything about the goal.
Example:
Consider the clauses:
p(X) < ~
q(X)
q(X) < ~
r(X)
r(a)
and the query
 In the electrical domain, what if we predict that a light should
be on, but observe that
it isn't?
What can we conclude?
 We will expand the definite clause language to include
integrity constraints which are rules that imply
false, where false is
an atom that is false in all interpretations.
 This will allow us to make conclusions from a contradiction.
 A definite clause knowledge base is always consistent. This won't be true with the
rules that imply false.
 An integrity constraint is a clause of the form
where the a_{i} are atoms and false is a special atom that is false
in all interpretations.
 A Horn clause is either a definite
clause or an integrity
constraint.
 Negations can follow from a Horn clause KB.
 The negation of alpha, written ¬alpha is a formula that
 is true in interpretation I if alpha is false in I, and
 is false in interpretation I if alpha is true in I.
 Example:
KB={
false < a & b. 
a < c. 
b < c.

}
KB ¬c.
 Disjunctions can follow from a Horn clause KB.
 The disjunction of alpha and beta, written
alpha or beta, is
 true in interpretation I if alpha is true in I or beta
is true in I (or both are true in I).
 false in interpretation I if alpha and beta are both false in I.
 Example:
KB={
false < a & b. 
a < c. 
b < d.

}
KB ¬c or ¬d.
 An assumable is an
atom whose negation you are prepared to accept as part of a (disjunctive)
answer.
 A conflict of KB is a set of
assumables that, given KB imply false.
 A minimal conflict is a conflict such that no strict
subset is also a conflict.
Example: If {c,d,e,f,g,h} are the assumables
KB={
false < a & b. 
a < c. 
b < d. 
b < e.

}
 {c,d} is a conflict
 {c,e} is a conflict
 {c,d,e,h} is a conflict
 Assume that the user is able to observe
whether a light is lit or dark and whether a power outlet is dead or
live.
 A light can't be both lit and dark. An outlet can't be both live
and dead:
false <=dark(L) &lit(L).
false <=dead(L) &live(L).
 Make ok assumable:
assumable(ok(X)).
 Suppose switches s_{1}, s_{2}, and s_{3}
are all up:
up(s_{1}). up(s_{2}). up(s_{3}).
lit(L) <=light(L)&ok(L)&live(L).
live(W) <=connected_to(W,W_1)&live(W_1).
live(outside)<=true.
light(l_1)<=true.
light(l_2)<=true.
connected_to(l_1,w_0)<=true.
connected_to(w_0,w_1) <=up(s_2)&ok(s_2).
connected_to(w_1,w_3) <=up(s_1)&ok(s_1).
connected_to(w_3,w_5) <=ok(cb_1).
connected_to(w_5,outside)<=true.
 If the user has observed l_{1} and l_{2} are both dark:
dark(l_{1}).~dark(l_{2}).
 There are two minimal conflicts:
{ok(cb_1),ok(s_1),ok(s_2),ok(l_1)} and
{ok(cb_1),ok(s_3),ok(l_2)}.
 You can derive:
¬ok(cb_1) or ¬ok(s_1) or ¬ok(s_2) or ¬ok(l_1)
¬ok(cb_1) or ¬ok(s_3) or ¬ok(l_2).
 Either cb_{1} is broken or there is one of six double faults.
 A consistencybased diagnosis is a
set of assumables that has at least one element in each conflict.
 A minimal diagnosis is a diagnosis such that no
subset is also a diagnosis.
 Intuitively, one of the minimal diagnoses must hold. A diagnosis
holds if all of its elements are false.
 Example: For the proceeding example there are seven
minimal diagnoses: {ok(cb_{1})}, {ok(s_{1}),ok(s_{3})},
{ok(s_{1}),ok(l_{2})}, {ok(s_{2}),ok(s_{3})},...
dprove(G,D_{0},D_{1}) is true if list D_{0} is an ending of list D_{1} such
that assuming the elements of D_{1} lets you derive G.
dprove(true,D,D).
dprove((A&B),D_1,D_3) <
dprove(A,D_1,D_2) & dprove(B,D_2,D_3).
dprove(G,D,[GD]) < assumable(G).
dprove(H,D_1,D_2) <
(H<=B) & dprove(B,D_1,D_2).
conflict(C) < dprove(false,[],C).
false <=a.
a <=b &c.
b <=d.
b <=e.
c <=f.
c <=g.
e <=h &w.
e <=g.
w <=f.
assumable d,f,g,h.
 Conclusions are pairs <a,A>, where a is an atom
and A is a set of assumables that
imply a.
 Initially, conclusion set C={<a,{a}>:a is assumable}.
 If there is a rule h < b_{1} & ... & b_{m}
such that
for each
b_{i} there is some
A_{i} such that <b_{i},A_{i}>
in C, then <h,A_{1} union ... union A_{m}> can be added to C.
 If <a,A_{1}> and <a,A_{2}>
are in C, where A_{1} strict subset A_{2}, then
<a,A_{2}> can be removed from C.
 If <false,A_{1}> and <a,A_{2}> are in
C, where A_{1} subset A_{2}, then
<a,A_{2}> can be removed from C.
C:={<a,{a}>:a is assumable }; 
repeat 
 select clause "h < b_{1} & ... & b_{m}" in T such that 
  <b_{i},A_{i}> in C for all i and 
  there is no <h,A'> in C or <false,A'> in C 
   such that A' subset A where A=A_{1} union ... union A_{m}; 
 C:=C union {<h,A>} 
 Remove any elements of C that can now be pruned; 
until no more selections are possible

 Database designers can use integrity constraints to specify
constraints that should never be violated.
 Example: A student can't have two different grades for the same course.
false <
grade(St,Course,Gr_1) &
grade(St,Course,Gr_2) &
Gr_1 != Gr_2.
 When false is derived, how can be used to debug the KB.
©David
Poole, Alan
Mackworth, Randy
Goebel and Oxford University Press,
19982002