CHAPTER 2

KNOWLEDGE REPRESENTATION
Aims
To introduce and compare the main knowledge
representation methods used in AI.

Objective
You should be able to :
use the different methods to represent knowledge.
Show how new facts can be inferred.
Discuss advantages and disadvantages of different methods.
Introduction

 Representation is a set of conventions about how to describe

a class of things.
 Finding the appropriate representation is a major part of
problem-solving.
 Use diagram to replace sentences.
 Knowledge representation languages, i.e., PROLOG, LISP.
Example :
A farmer wants to move himself, a silver fox, a fat goose, and
some tasty grain across a river. Unfortunately, his boat is so
tiny he can take only one of his possessions across any trip.
Worse yet, an unattended fox will eat a goose, and an
unattended goose will eat grains, so the farmer must not leave
the fox alone with the goose or the goose alone with the
grains.
 
What is he to do ?

Solution
Representation methods
 Semantic networks and frames
 Predicate calculus/ logic
 Rule-based system/ production rule.
Semantic networks and frames
 Both provide a simple and intuitively way of representing
facts about objects.
 Both represent classes (or categories) of objects and
relations.
 Simple inference can be drawn based on this
representation.
 Both different in used of notation to represent
knowledge.
Example: Representing some knowledge about animals.

Animal

subclass subclass
Reptile Mammal head
has-part
subclass
Africa Elephant large
livesin size
instance instance

Clyde Nellie apples

likes
From the network we can draw some facts/simple inferences:
 Mammals and reptiles are animal.
 Mammals have head.
 An elephant is a large grey mammals.
 Clyde and Nellie are both elephant, and that Nellie likes
apple.
 Concept of inherit properties :
Clyde & Nellie both have a head, and are large and grey.
• Exercise: Represent the following facts as a semantic network

1) “The aorta is a particular kind of artery which has a diameter of 2.5cm. An

artery is a kind of blood vessel. An artery always has a muscular wall, and
generally has a diameter of 0.4 cm. A vein is a kind of blood vessel, but
has a fibrous wall. Blood vessels all have tubular form and contain blood”

2) “Herbert is a small hippopotamus who lives in Edinburgh zoo. Like all

hippopotamuses he eats and likes swimming”

• Based on the semantic network, give two new facts

Representational Adequacy
 Semantic networks and frames – simple and clear.
 But not to express negation (i.e., NOT), disjunction
(i.e, OR) or certain types of quantification(i.e.,
some/all).
Predicate Calculus/ Logic
 It is a formal language which can be described as its :
 Syntax (What the allowable expression are).
 Semantic (What they means).
 Proof theory/rules of inference.
 How to draw conclusion?

Advantages:
 well defined formal sentences.
 sound and complete inference rules.
 
Review of Propositional Calculus
 Propositional Calculus and Predicate Logic are languages. 
 Using their words, phrases and sentences we can represent
and reason about properties and relationship –
inference/generate a new fact
 The first step to describe a language is its set of symbols.
 Symbols are used to represent facts about the world.
i.e., “Ali likes cakes” represented symbol P
P is known as atomic symbol.
 Other symbols truth symbols: true, false
 Complex statement is a combination of atomic proposition
with the following connectives :
 (and),  (or),  (not), = (equivalent),  (implications)

 Examples
 P Q where Q is another fact “Ali eats cakes”.
 PQ
 Q “Ali doesn’t eats cakes”.
 PQ “if Ali likes cakes then
 P=Q “if Ali likes cakes then …, and vice versa
The Predicate Logic(PreL)
• In Propositional, i.e., “it is rained on Tuesday” denoted by P.
In PreL, is denoted as weather(tuesday, rain)
where it contains predicate name and arguments.
• Other example: “Ali likes chocolate” is written as
likes(ali, chocolate).
• Expression can contain variables, example
weather(X, rain) X representing any day
It allows to create general assertions.
Syntax of PredL
  uses symbols to denote objects, properties or relation.
  Symbol is a string of letters followed by digits/underscore.
  Symbols in i(g,k) and likes(john, kate) are equivalent but
the second is more readable.
 Constant symbol begin with lower case, ali, chocolate, rain
 Variable symbol - begin with capital letter, i.e., X
 Function likes predicate yields value, i.e., sum(X,Y)
 Truth values/constant: true and false are reserved.
 An atomic sentence is a predicate name followed by n terms
enclosed in ( ) and separated by commas and delimited by a
period. Examples:
friends(ali, azhar).
friends(father(razak), father(jamal) ).
likes(X, azhar).

 Complex sentences – combination of atomic sentences with

logical connectives, i.e.,
friends(ali, azhar)  likes(ali, azhar)
likes (ali, azhar)  likes (ali, chocolate)
(likes(ali, timah)  likes(ali, apple))  likes(ali, limau)
A Semantic of PredL – referring truth values
• From well-formed expression to its truth value/ meaning.
• It provides a formal basis for determining the truth value.
• It maps symbols into objects and relations in the domain of
definition, i.e., given objects/ true facts
friends(ali, bakar).
friends(ali, ismail).
• Asking expression :
? friends(ali, bakar) return True
? friends(ali, ali) return False
? friends(ali, X) return X as bakar or ismail.
? friends(bakar, X) return False
Quantification
 
  universal quantification.
means true for all objects in the domain, i.e.,
   X likes (X, apple) is true by checking all likes(…).

 existentially quantification.
True for at least one substitution from the domain.
“There exist bird that doesn’t flies.”
 X (bird(X)  flies(X))
 Examples :
“Ali eats everything that he likes.” X(likes(ali, X) eats(ali, X)).
 
“Every person has something that they love”.
X (person(X) Y loves(X, Y) )
 
“If it doesn’t rain tomorrow, ahmad will go fishing.”
weather(rain, tomorrow)  go(ahmad, fishing).

“All basketball players are tall.”  X( basketball_players(X)  tall(X) ).

 
“Nobody likes taxes.”  X likes(X, taxes).
• Exercises:

• Represent the following facts in the Predicate Logic:

– Every apple is either green or yellow
– No apple is blue
– If an apple is green then it is tasty
– Every man likes a tasty apple
– “Herbert is a small hippopotamus who lives in Edinburgh zoo. Like all
hippopotamuses he eats and likes swimming”
 Given the facts and rules about simple Family relationships
mother (timah, abu).
mother (timah, mas).
father (ali, abu).
father (ali, mas).
XY (father (X, Y)  mother (X, Y)  parent(X,Y)).
XYZ (parent (X, Y)  parent (X, Z)  sibling(Y, Z)).

Note: The last two rules or implication give general descriptions of other relationships,
i.e., parent and sibling.
 Therefore we can infer such as:
? sibling(mas, abu)
How to prove: mas and abu are sibling?
 Notes:
In the language, universally and existentially quantified
variables may refer to objects (constants) in the domain of
discourse. Predicate and function names may not be replaced
by quantified variables. This language is called the First-Order
Predicate Logic.

Example of higher-order Predicate Logic is

 (Likes) Likes(ali, timah)
• Examples 2: Blocks World with its predicate logic description

c b
 
a d

on(c,a)
on(b,d)
ontable(a)
ontable(d)
clear(b)
clear(c)
hand_empty
 To design a control algorithm for a robot arm  
 We need to represent knowledge based on :
• Does a given block have a clear top surface ?
• Can we pick up block a ? etc.
 We need to know : (operations of the system)
• location of each block and the arm.
• The initial knowledge are shown the figure.
 The arm can move blocks, change the state, and clear.
For example: to pick-up block-a
• Is block-a clear ?
• remove block-c.
• delete the knowledge of on(c,a).
• pick-up block-a.

 Rule to describe block is cleared:

 X( Y on (Y, X)  clear (X) ).
“For all X, X is cleared if there does not exist a Y such that Y is on X.”
 Rule to describe stacking :
Example to stack X on Y:
• first empty the hand,
• clear X
• clear Y
• pick_up X
• put_down X on Y
XY((hand_empty  clear(X)  clear(Y)  pick_up(X)  put_down(X, Y) )
 stack(X,Y) ).
 Notes:
• Initial predicate expressions give a semantic interpretation of the current status of
the system.
• Knowledge bases are always updated after each operation.
 Full program/codes:

on(c,a).
on(b,d)
ontable(a).
ontable(d).
clear(b).
clear(c).
hand_empty.
 X( Y on (Y, X)  clear (X) ).
XY((hand_empty  clear(X)  clear(Y)  pick_up(X) put_down(X, Y) ) 
stack(X,Y) ).
• Exercise?
(1) You can translate semantic network examples, eg.
Animal relations into Predicate Logic. (Refer pg
dirt dirt
(0,2) (1,2) (2,2)

(0,1) (1,1) (2,1)

(0,0) (1,0) (2,0)

Figure 1: Vacuum world.

• The figure above shows a robotic with a function to clean up a house. The
robot is equipped with a sensor that can receive a percept dirt (signifying
that there is dirt beneath it), or null (indicating no special information).
The robot always has a definite orientation (one of north, south, east or
west). In addition to being able to suck up dirt, the robot can move
forward one ‘step’ or turn right 90o. The robot moves round a room,
which is divided grid-like into a number of equally sized squares of 3 x 3,
and it always start in grid square (0,0) facing north. The goal is to traverse
the room continually searching for and removing dirt.

• Given an initial environment.

In(x, y) robot is at (x, y)
Dirt(x, y) there is dirt at (x, y)
Facing(d) robot is facing direction d
• Write all possible rules starting from (0,0) until (3,3) to indicate the
actions performed by the robot. The rules dealing with the traversal up to
(0,2) are given below
Formal basis for PreC Inference Rules (proof theory)

 We need rules to draw conclusion.

 You unconsciously use Inference Rules all the times, i.e., you
conclude that your friend is home from the fact that her car is
in the driveway.
  The important feature of PreL is the ability to infer a new
correct expression from a set of true assertions (existing
expression). Or creating new expressions from existing.
 The semantics provide a basis for a formal theory of logical
inference. Before conclusion, we do interpretation on the
expressions.
 Two ways of proof theories :
 “modus ponens” and
 resolutions.

 Modus ponens is a sound rule of inference for the logic.

 IF (premise) is true THEN conclusions are guaranteed true.

 Definition: An expression Q logically follows (LFs) from a set of

PreC expression S if every interpretation that satisfies S also
satisfies Q.
LFs mean that Q is true for every interpretation that satisfies S.
 In general:
Given S : P =>Q and P. Under interpretation I, both are true then Q is also
true where Q is the conclusion.
 Example 1: Given two observations :
PQ “if it is raining then the ground is wet.”
P “it is raining.”
 How to proof Q is true?
Now is raining (P is true) and P  Q generally true, then Q is true.

 Example 2: expression containing variables:

“All men are mortal and Socrates is a man
S: X (man(X)  mortal(X) ). I: True “on everyman”
P: man(socrates). I: True “he is the man”
Therefore Q: “Socrates is mortal.”

By substituting socrates with X, then we can infer :

man(socrates)  mortal(socrates). (conclusion)
Unification (likes assignment statement)
  To apply modus, two expression must match/the same.
  In ProC , they match if and only if they are syntactically
identical.
 In PreC is more complicated because the expression contains
variables may be replaced from the domain by any terms of
arbitrary complexity.
  Unification is the algorithm for determining the substitution
needed to make two PreC expressions match.
  Example of simple substitution:
Substituting socrates with X to infer Q: mortal(socrates).
 Example: foo(X, a, goo(Y) )
1. foo(fred,a, goo(z) )
2. foo(W, a, goo(jack) )
3. foo(Z, a, goo(moo(z) ) )

 The substitution instances or unifications are :

1. {fred/X, z/Y} X=fred and Y=z
2. {W/X, jack/Y} X=W and Y = jack
3. {Z/X, moo(z)/Y} X=Z and Y=moo(z)
 
 The notation X/Y, … indicates that X is substituted for the
variable Y in the original expression.
Application : A Logic-Based Financial Advisor
 To help a user decide whether to invest in a savings account
or the stock market or both.
 Criteria depend on income and the saving such as:
 Inadequate savings account should – saving is the priority, regardless
of their income
 adequate savings and adequate income should consider investment in
stock market.
 lower income + adequate saving – may consider splitting their surplus
between savings and stock.
 The adequacy of both is determined by dependents.
 At least RM5000 in the bank for each dependent.
 An adequate income must be steady income and supply at least
RM15,000 per year plus an additional RM4000 for each dependent.
 To automate this advice - change to PreC:
1. The first task is to determine the major features that must be considered. Here,
they are the adequacy of the savings and the income. They are represented by:
 Atomic sentences/ facts
savings_account(adequate).
savings_account(inadequate).
income(adequate).
income(inadequate).

2. Rules for investment strategies where the conclusions are stock, savings or
combination (investment should be split)

Savings_account(inadequate)  investment(savings).
Savings_account(adequate)  income(adequate)  investment(stocks).
Savings_account(adequate)  income(inadequate)  investment(combination).
3. The advisor must determines when savings are adequate or inadequate:
 
X amount_saved(X)  Y(dependents(Y)  greater(X, minsavings(Y)))
savings_account(adequate).
X amount_saved(X)  Y(dependents(Y)  greater(X, minsavings(Y) ) ) 
savings_account(inadequate).
  where minsavings(Y) is a function : minsavings(Y) = 5000*Y;

4. And when income are adequate or inadequate:

X earnings(X,steady)  Y(dependents(Y)  greater(X, minincome(Y) ) ) 

income(adequate).
X earnings(X,steady)  Y(dependents(Y)  greater(X, minincome(Y) ) ) 
income(inadequate).
X earnings(X,unsteady)  income(inadequate).
 
where minincome(Y) = 15000+(4000*Y)
 Run the system:
 Start to give advice:
 In order to perform a consultation, a description of a particular
investor is added to this set of sentences using:

amount_saved(22000).
earnings(25000, steady).
dependents(3).
 
What is the advise?
 This yield a logical system consisting:
1. savings_account(inadequate)  investment(savings).
2. savings_account(adequate)income(adequate)  investment(stocks).
3. savings_account(adequate)  income(inadequate)  investment(combination).
4. X amount_saved(X)Y(dependents(Y)greater(X,minsavings(Y)))
 savings_account(adequate).
5. X amount_saved(X)Y(dependents(Y)greater(X,minsavings(Y)))
 savings_account(inadequate).
6. X earnings(X,steady)Y(dependents(Y)greater(X, minincome(Y)))
 income(adequate).
7. X earnings(X,steady)Y(dependents(Y)greater(X,minincome(Y)))
 income(inadequate).
8. X earnings(X,unsteady)  income(inadequate).
9. amount_saved(22000).
10. earnings(25000, steady).
11. dependents(3).

 
 Unification process:
 Unify sentence 10 and 11 with sentence 7 under substitution
{25000/X, 3/Y} yielding the new implication

earnings(25000,steady) (dependents(3)  greater(25000, 27000 )  income(inadequate).

 
 Since premises are true by applying modus ponent, the conclusion is
true. This is added as:
 
12. income(inadequate).
 Similarly, unify sentence 9 and 11 with sentence 4, under the substitution
{22000/X, 3/Y}, yielding the implication

amount_saved(22000)(dependents(3) greater(22000, 15000) 

savings_account(adequate).

  Since premises are true by applying modus ponens, the conclusion is true.
This is added as:

13. savings_account(adequate).

 As an examination of 3, 12, and 13 indicates, the premise of implication 3

is also true. When we apply modus ponens yet again, the conclusion is
investment(combination).
Rule-Based Systems (RBS)
 Previous methods representing knowledge in a relatively
declarative, static way (as a set of things that are true).
  RBS representing knowledge in terms of a set of rules – what
you should do and what you can conclude.
  Consist of :
 a set of IF-THEN rules.
 a set of facts representing things- currently to be true.
 some interpreter controlling the application of the rules, given the
facts.
Figure below shows the Rule-Based System Architecture

Control Scheme (Interpreter)

Condition-Action Rules
Database of Facts
R1: IF hot AND smoky THEN ADD fire
alarm_beeps
R2: IF alarm_beeps THEN ADD smoky hot
R3 IF fire THEN ADD switch_on_sprinklers
 IF-THEN is not similar constructs in Java/C++ – not as part of a
sequence of instructions but treats each rule as an
independent chunk of knowledge.
  The rules are more like implications in logic, i.e.,
raining  carry_umbrella
 Interpreter :
 forward chaining
 backward chaining
 Forward chaining systems – start with some initial facts, and keep using
the rules to draw new conclusions.
 Backward chaining systems – start with some hyphotesis (or goal) you are
trying to prove. 
 Forward chaining systems are primarily data driven, while backward
chaining systems are goal-driven.
Forward chaining systems
 Facts are held in working memory – continually updated as
rules are invoked.
 Rules represent possible actions to take when specified facts
occur in the working memory – referred as condition-action
rules.
 Actions involve – adding or deleting item from working
memory or printing a message.
 The interpreter control the system’s activity – based on a
cycle of activity – known as – a recognize-act-cycle.
 It selects the rule and performs the actions in the action part
of it - is refered as firing the rule.
 Algorithm of the interpreter (forward chaining) :

Repeat :
1. Find all rules which have conditions satisfied.
2. Select one, using conflict resolution strategies.
3. Perform actions in conclusion – possibly modify current
working memory.
Until no rules can fire or halt is added in memory.
 Simple fire fighting example – only switch the sprinklers on if
smoke alarm on and hot :
R1 : IF hot AND smoky THEN ADD fire
R2 : IF alarm_beeps THEN ADD smoky
R3 : IF fire THEN ADD switch_on_sprinklers
F1 : alarm_beeps
F2 : hot

 Start ?
 Notice that the order in which rules fires depends on what is
in working memory.
 What happens if, in some cycle, more than one rule has its
condition satisfied, i.e.,
R1 : IF hot AND smoky THEN ADD fire
R2 : IF alarm_beeps THEN ADD smoky
R3 : IF fire THEN ADD switch_on_sprinklers
R4 : IF dry THEN ADD switch_on_humidifier
R5 : IF switch_on_sprinklers THEN DELETE dry
F1 : alarm_beeps
F2 : hot
F3 : dry
 In the 1st. cycle – R2 and R4 – conflict ?
If R4 is chosen, the humidifier is switched on and then things proceed as before.
If R2 is chosen, followed by R1, R3 and R5, then dry is deleted from working
memory and the humidifier never switch on.
 Common conflict resolution strategies:
 Rules that involve facts have been recently added, i.e., if R2 fires, the
next rule to be fired will be R1.
 Rules with more specific condition, i.e., R1, it contains, hot and
smoky.
 Allow user to prioritize rules. Eg. R4 could have very low priority. Only
fire if nothing else can fire.
 Fire all applicable rules at once.
 A language may provide a range of different strategies.
 The CLIPS Expert System tool is based on forward chaining.
Backward Chaining System
 Forward allow draws new conclusion from existing data.
 Useful - know all the initial facts but do not know ….
 If we know conclusions/goals/hypothesis without knowing all
initial facts then use backward chaining.
 Avoid irrelevant inferences and focus just on the hypothesis
in question.
 It does not need to update the working memory.
 Algorithm :
 To prove goal G:
 If G is in the initial facts it is proven.
 Otherwise, find a rule which can be used to conclude G, and try to prove each of
that rule’s preconditions.
 If all preconditions true then G is proven.
 Example (Given rules and some initial facts) :

R1 : IF hot AND smoky THEN ADD fire

R2 : IF alarm_beeps THEN ADD smoky
R3 : IF alarm_beeps THEN ADD ear_plugs
R4 : IF fire THEN ADD switch_on_sprinklers
R5 : IF smoky THEN ADD poor_visibility
F1 : alarm_beeps
F2 : hot

 Start to prove :
G1 : switch_on_sprinklers
 Conflict strategies :
If there is more than one rules for the same conclusions. Try them all. See
which one can be proved. Search techniques may be used to try all posibilities.
  Prolog uses backward chaining system.
Forward vs Backward Reasoning
 Suitable applications such as on expert systems.
 Medical diagnosis, i.e., MYCIN, use backward chaining since
hypotheses of the diseases are known.
 Computer configuration, i.e., XCON – since there are an
enormous number of possible configurations and it would not
be sensible to go through all. Forward chaining is a better
idea. It starts with the specifications and gradually building up
(in working memory) a possible configurations.