Computational Intelligence

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, 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 2, Lecture 1

Representation and Reasoning System

A Representation and Reasoning System (RRS) is made up of:

Implementation of an RRS

An implementation of an RRS consists of Note: the semantics aren't reflected in the implementation!

Using an RRS

  1. Begin with a task domain.
  2. Distinguish those things you want to talk about (the ontology).
  3. Choose symbols in the computer to denote objects and relations.
  4. Tell the system knowledge about the domain.
  5. Ask the system questions.

Role of Semantics in an RRS

Simplifying Assumptions of Initial RRS

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

Syntax of Datalog

variable starts with upper-case letter.

constant starts with lower-case letter or is a sequence of digits (numeral).

predicate symbol starts with lower-case letter.

term is either a variable or a constant.

atomic symbol (atom) is of the form p or p(t1,...,tn) where p is a predicate symbol and ti are terms.

Syntax of Datalog (cont)

definite clause is either an atomic symbol (a fact) or of the form: where a and bi are atomic symbols.

query is of the form ?b1 & ··· & bm.

knowledge base is a set of definite clauses.

Example Knowledge Base

in(alan,R) <-
     teaches(alan,cs322) &
grandfather(william,X) <-
      father(william,Y) &
slithy(toves) <-
      mimsy & borogroves &

Chapter 2, Lecture 2

Semantics: General Idea

A semantics specifies the meaning of sentences in the language.

An interpretation specifies:

Formal Semantics

An interpretation is a triple I=<D,phi,pi>, where

Example Interpretation

Constants: phone, pencil, telephone.
Predicate Symbol: noisy (unary), left_of (binary).

Important points to note

Truth in an interpretation

A constant c denotes in I the individual phi(c) .

Ground (variable-free) atom p(t1,...,tn) is

Ground clause h <- b1 & ... & bm is false in interpretation I if h is false in I and each bi is true in I, and is true in interpretation I otherwise.

Example Truths

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

Models and logical consequences

Simple Example

p <- q.
r <- s.
pi(p) pi(q) pi(r) pi(s)
I1   TRUE   TRUE   TRUE   TRUEis a model of KB
I2   FALSE   FALSE   FALSE   FALSEnot a model of KB
I3   TRUE   TRUE   FALSE   FALSEis a model of KB
I4   TRUE   TRUE   TRUE   FALSEis a model of KB
I5   TRUE   TRUE   FALSE   TRUEnot a model of KB

KB p, KB q, KB r, KB s

User's view of Semantics

  1. Choose a task domain: intended interpretation.
  2. Associate constants with individuals you want to name.
  3. For each relation you want to represent, associate a predicate symbol in the language.
  4. Tell the system clauses that are true in the intended interpretation: axiomatizing the domain.
  5. Ask questions about the intended interpretation.
  6. If KB g, then g must be true in the intended interpretation.

Computer's view of semantics

Chapter 2, Lecture 3


Queries and Answers

A query is a way to ask if a body is a logical consequence of the knowledge base:
?b1 & ··· & bm.
An answer is either

Example Queries

in(X,Y) <- part_of(Z,Y) & in(X,Z).
?part_of(r123,B). part_of(r123,cs_building)
?in(alan,B). in(alan,r123)

Logical Consequence

Atom g is a logical consequence of KB if and only if:

Debugging false conclusions

To debug answer g that is false in the intended interpretation:

Electrical Environment

Axiomatizing the Electrical Environment

%~light(L) is true if L is a light
light(l1). light(l2).
%~down(S) is true if switch S is down
down(s1). up(s2). up(s3).
%~ok(D) is true if D is not broken
ok(l1). ok(l2). ok(cb1). ok(cb2).
?light(l1). => yes
?light(l6). =>no
?up(X). =>up(s2), up(s3)

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(w0,W). => W=w1
?connected_to(w1,W). => no
?connected_to(Y,w3). => Y=w2, Y=w4, Y=p1
?connected_to(X,W). => X=w0, W=w1, ...

% 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) &

This is a recursive definition of live.

Recursion and Mathematical Induction

above(X,Y) <- on(X,Y).
above(X,Y) <- on(X,Z) & above(Z,Y).

This can be seen as:


Suppose you had a database using the relation:
which is true when student S is enrolled in course C.

You can't define the relation:

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!

Chapter 2, Lecture 4


Bottom-up Ground Proof Procedure

One rule of derivation, a generalized form of modus ponens:

If "h <- b1 & ... & bm" is a clause in the knowledge base, and each bi has been derived, then h can be derived.

You are forward chaining on this clause.

(This rule also covers the case when m=0.)

Bottom-up proof procedure

KBg if g in C at the end of this procedure:
select clause "h <- b1 & ... & bm" in KB such that
bi in C for all i, and
h not in C;
C:=C union {h}
until no more clauses can be selected.

Nondeterministic Choice


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

Soundness of bottom-up proof procedure

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 <- b1 & ... & bm
Each bi 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.

Fixed Point

The C generated at the end of the bottom-up 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 <- b1 & ... & bm in KB is false in I. Then h is false and each bi 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.

Chapter 2, Lecture 5

Top-down Ground Proof Procedure

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 ai with the clause:

a_i <- b_1 & ... & b_ p

is the answer clause

yes <- a_1 & ··· & a_i-1 & b_1 & ··· & b_p & a_i+1 & ··· & a_m.


Top-down definite clause interpreter

To solve the query ?q1 & ... & qk:

ac:= "yes <- q1 & ... & qk"
select a conjunct ai from the body of ac;
choose clause C from KB with ai as head;
replace ai in the body of ac by the body of C
until ac is an answer.

Example: successful derivation

a <- b & c. a <- e & f. b <- f & k.
c <- e. d <- k. e.
f <- j & e. f <- c. j <- c.
Query: ?a
gamma0: yes <- a gamma4: yes <- e
gamma1: yes <- e & f gamma5: yes <-
gamma2: yes <- f
gamma3: yes <- c

Example: failing derivation

a <- b & c. a <- e & f. b <- f & k.
c <- e. d <- k. e.
f <- j & e. f <- c. j <- c.
Query: ?a
gamma0: yes <- a gamma4: yes <- e & k & c
gamma1: yes <- b & c gamma5: yes <- k & c
gamma2: yes <- f & k & c
gamma3: yes <- c & k & c

Chapter 2, Lecture 6

Reasoning with Variables

Application Examples

The following are substitutions: The following shows some applications:


Unification Example

p(A,b,C,D) and p(X,Y,Z,e) have as unifiers: The first three are most general unifiers.

The following substitutions are not unifiers:

Bottom-up procedure

Definite Resolution with Variables

A generalized answer clause is of the form

yes(t_1,...,t_k) <- a_1 & a_2 & ... & a_m,

where t1,...,tk are terms and a1,...,am are atoms.

The SLD resolution of this generalized answer clause on ai with the clause

a <- b_1 & ... & b_p,

where ai and a have most general unifier theta, is

(yes(t_1,...,t_k) <-
     a_1 & ... & a_i-1 & b_1 & ... & b_p & a_i+1 & ... & a_m)theta.

To solve query ?B with variables V1,...,Vk:
Set ac to generalized answer clause yes(V1,...,Vk) <- B;
While ac is not an answer do
Suppose ac is yes(t1,...,tk) <- a1 & a2 & ... & am
Select atom ai in the body of ac;
Choose clause a <- b1 & ... & bp in KB;
Rename all variables in a <- b1 & ... & bp;
Let theta be the most general unifier of ai and a.
Fail if they don't unify;
Set ac to (yes(t1,...,tk) <- a1 & ... & ai-1 &
b1 & ... & bp & ai+1 & ... & am)theta
end while.


live(Y) <- connected_to(Y,Z) & live(Z).live(outside).
     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) <- .

Function Symbols

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(t1,...,tn) where f is a function symbol and the ti are terms.

In an interpretation and with a variable assignment, term f(t1,...,tn) 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 rest-of-list T. These are not built-in.

The list containing david, alan and randy is

append(X,Y,Z) is true if list Z contains the elements of X followed by the elements of Y

append(cons(A,X),Y,cons(A,Z)) <- append(X,Y,Z).

©David Poole, Alan Mackworth, Randy Goebel and Oxford University Press, 1998-2002