# Computational Intelligence

## 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, 1999-2002. You may prefer the pdf interface for which these slides were designed (you can read pdf files using the free acrobat reader).

# Chapter 7, Lecture 1

## Equality

• 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 t1 equals ground term t2, written t1=t2, is true in interpretation I if t1 and t2 denote the same individual in interpretation I.

## Equality doesn't mean similarity

chair1 != chair2
chair_on_right = chair2
chair_on_right is not similar to chair2, it is chair2.

## Why is equality important?

• 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).

## Allowing Equality Assertions

• Without equality assertions, the only thing that is equal to a ground term is itself.

This can be captured as though you had the assertion X=X. Explicit equality never needs to be used.

• If you allow equality assertions, you need to derive what follows from them. Either:
• axiomatize equality like any other predicate
• build special-purpose inference machinery for equality

## Axiomatizing Equality

X=X.
X=Y <- Y=X.
X=Z <- X=Y & Y=Z.

For each n-ary 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 n-ary 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.

## Special-Purpose Equality Reasoning

paramodulation: if you have t1=t2, then you can replace any occurrence of t1 by t2.

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.

## Unique Names Assumption

The convention that different ground terms denote different individuals is the unique names assumption.

For every pair of distinct ground terms t1 and t2, assume t1 != t2, 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.

## Axiomatizing Inequality for the UNA

• c != c' for any distinct constants c and c'.
• f(X1,...,Xn) != g(Y1,...,Ym) for any distinct function symbols f and g.
• f(X1,...,Xn) != f(Y1,...,Yn) <- Xi != Yi, for any function symbol f. There are n instances of this schema for every n-ary function symbol f (one for each i such that 1 <= i <= n).
• f(X1,...,Xn) != 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).

## Top-down procedure and the UNA

• Inequality isn't just another predicate. There are infinitely many answers to X != f(Y).
• If you have a subgoal t1 != t2, for terms t1 and t2 there are three cases:
• t1 and t2 don't unify. In this case, t1 != t2 succeeds.
• t1 and t2 are identical including having the same variables in the same positions. Here t1 != t2 fails.
• Otherwise, there are instances of t1 != t2 that succeed and instances of t1 != t2 that fail.

## Implementing the UNA

• 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.

## Inequality Example

notin(X,[]).
notin(X,[H|T]) <- 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).

# Chapter 7, Lecture 2

## Complete Knowledge Assumption (CKA)

• 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.

## CKA: propositional case

• Suppose the rules for atom a are
 a <- b1. ... a <- bn.
or equivalently: a <- b1 or ... or bn
• Under the CKA, if a is true, one of the bi must be true:

a -> b_1 or ... or b_n.

• Under the CKA, the clauses for a mean Clark's completion:

a <-> b_1 or ... or b_n

## CKA: Ground Database

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.

## Clark Normal Form

The Clark normal form of the clause:

p(t_1,...,t_k) <- B

is the clause

p(V_1,...,V_k) <-
exist W_1...exist W_m V_1=t_1 & ... & V_k =t_k & B,

where V1,...,Vk are k different variables that did not appear in the original clause.

W1,...,Wm are the original variables in the clause.

## Clark normal form: example

• 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.

## Clark's Completion of a Predicate

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(V1,...,Vk) <- B1 or ... or Bn.

Clark's completion of p is the equivalence

p(V_1,...,V_k) <-> B_1 or ... or B_n,

That is, p(V1,...,Vk) is true if and only if one Bi is true.

## Clark's Completion Example

Given the mem function:

mem(X,[X|T]).
mem(X,[H|T]) <- mem(X,T).

the completion is

mem(X,Y) <-> (exist T Y=[X|T]) or
(exist H exist T Y=[H|T] & mem(X,T))

## Clark's Completion of a KB

• 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.

## Using 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).

## Bottom-up NAF proof procedure

 C:={}; repeat either select "h <- b1 & ... & bm" in KB such that bi in C for all i, and h not in C; C:=C union {h} or select h such that for every rule "h <- b1 & ... & bm" in KB either for some bi, `~` bi in C or some bi= `~` g and g in C C:=C union { `~` h} until no more selections are possible

## Negation as failure example

p <- q & `~` r.
p <- s.
q <- `~` s.
r <- `~` t.
t.
s <- w.

## Top-Down NAF Procedure

• 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 <- b1 ... a <- bn
If each body bi fails, a fails.
If one body, bi 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.

## Free Variables in Negation as Failure

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.

## Floundering Goals

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

?p(X).

# Chapter 7, Lecture 3

## Integrity Constraints

• 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.

## Horn clauses

• An integrity constraint is a clause of the form

false <- a_1 & ... & a_k

where the ai 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.

## Negative Conclusions

• 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.

## Disjunctive Conclusions

• 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.

## Questions and Answers in Horn KBs

• 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.

## Conflict Example

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

## Using Conflicts for Diagnosis

• 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).

• Make ok assumable: assumable(ok(X)).
• Suppose switches s1, s2, and s3 are all up:
up(s1). up(s2). up(s3).

## Electrical Environment

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 l1 and l2 are both dark:
dark(l1).~dark(l2).
• 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 cb1 is broken or there is one of six double faults.

## Diagnoses

• A consistency-based 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(cb1)}, {ok(s1),ok(s3)}, {ok(s1),ok(l2)}, {ok(s2),ok(s3)},...

## Meta-interpreter to find conflicts

dprove(G,D0,D1) is true if list D0 is an ending of list D1 such that assuming the elements of D1 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,[G|D]) <- assumable(G).
dprove(H,D_1,D_2) <-
(H<=B) & dprove(B,D_1,D_2).
conflict(C) <- dprove(false,[],C).

## Example

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.

## Bottom-up Conflict Finding

• 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 <- b1 & ... & bm such that
for each bi there is some Ai such that <bi,Ai> in C, then <h,A1 union ... union Am> can be added to C.
• If <a,A1> and <a,A2> are in C, where A1 strict subset A2, then <a,A2> can be removed from C.
• If <false,A1> and <a,A2> are in C, where A1 subset A2, then <a,A2> can be removed from C.

## Bottom-up Conflict Finding Code

 C:={:a is assumable }; repeat select clause "h <- b1 & ... & bm" in T such that in C for all i and there is no in C or in C such that A' subset A where A=A1 union ... union Am; C:=C union {} Remove any elements of C that can now be pruned; until no more selections are possible

## Integrity Constraints in Databases

• 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 <-