Chapter 7

Inference and Knowledge

Processing

B. Okuku 1
 1. Reasoning
 Reasoning: The process of drawing
inferences or conclusions; moving from
what is known (fact) to what is unknown
(inference).
 Types of Reasoning:
 Reasoning from signs:
 Cause and effect:
 Reasoning by analogy:
 Reasoning by example:

2
B. Okuku
 Inferencing
 The process of accessing the knowledge stored
in the knowledge base in order to make
conclusions.
 The program for inferencing is typically called the
inference engine or control program.
 In rule based systems it is also called a rule
interpreter.
 Purpose: Direct the search through the
knowledge base. The engine determines
 Which rules to investigate,
 Which to eliminate, and
 Which will attribute to a match.
3
B. Okuku
 Reasoning from signs:
 Assuming that a sign or symbol represents
or indicates something specific.
 Example: making a phone call and receiving a
busy signal. The assumption is that someone
is already on the line.
 The sign, busy signal is used to infer that
someone is on the phone.
 There should be enough information to
relate the sign to the inference
 Beware of stereotypes like: "this author calls
herself a 'feminist;' therefore she hates men".
4
B. Okuku
 Cause and effect:
 Inferring that one event causes another
 “I was late because my alarm didn't go off.”
 or reasoning with the result in mind
 “If I don't study, I will fail the test.”
 Important that there is enough information
to link the events.
 Beware of assuming that things that
happen sequentially are causally related
 “I got a sunburn because it's hot.”
5
B. Okuku
 Reasoning by analogy:
 Drawing a parallel between two similar
events, people, or traits.
 Based on comparisons.
 Example: If all mothers are women, and Ann
is a mother, then Ann must be a woman.
 Care should be taken to always check
analogies for validity, because these don't
always work backwards.
 Example: Because Ann is a woman doesn't
mean she's a mother.
6
B. Okuku
 Reasoning by example:
 Basing conclusions on facts, illustrations,
or cases.
 Example: Conclusions drawn from the results
of polls or surveys.
 When drawing conclusions, always ask,
“Do I have enough facts to support this?”
 Example: "Candidate X has been nominated
with 60% approval rating, therefore he will be
elected in the election" does not provide any
information about the candidate's election
ratings.
7
B. Okuku
 2. Reasoning Methods
 Knowledge Representation allows encoding
or formalization of quantitative facts and
knowledge.
 Reasoning and inference allows generation
of new and useful knowledge, conclusions
and recommendation.
 Inference methods fall into two general
categories.
 Deductive Reasoning.
 Inductive Reasoning.
8
B. Okuku
 Reasoning Methods…
 Inductive reasoning: Specific -> General;
drawing conclusions or making
generalizations based on several examples
or situations (must be based on more than
one example).
 “Plato is mortal, Dr Kingsley is mortal.
Therefore all people are mortal.”
 Deductive reasoning: General -> Specific;
applying a generalization to a particular
case.
 “All people are mortal, therefore I am mortal.”
9
B. Okuku
 Deductive Reasoning
 The method used in propositional and
predicate calculus.
 The inference engine combines the rule (or
predicates) to arrive at the final answer.
 Starts with a set of axioms, or commonly
accepted premises that one cannot derive
from a system itself.
 Using the axioms and proven formulae,
deductive reasoning can deduce new
conclusions.
10
B. Okuku
 Deductive Reasoning
 The Inference process consists of two parts
Single Inference.
 Process of applying inference rules to combine two
pieces of knowledge to derive a new premise.
 May be an intermediate step or the final
recommendation.
Multiple Inference
 The sequence or order of applying the single inference
process to the entire knowledge base in order to
derive final conclusions.
 Together they form the knowledge-processing
capability of an intelligent system.

11
B. Okuku
 Single inference in deductive reasoning
 Inference in Propositional Logic and
Calculus
 There are a number of rules of inference in
propositional logic that allow derivation of
new statements from combining two
previously accepted ones.
 Modus ponens
 Hypothetical syllogism
 Modus tollens

12
B. Okuku
 Single inference in deductive reasoning
 Modus Ponens
 Has the following form: A  B
A
Conclude: B
 Since A is true, A  B has fired and resulted in the conclusion
that B is true
 ((A  B)  A)  B: If A implies B and A is true then
we can conclude B.
 Modus Ponens has to be a tautology for it to be true.
 Tautology: The truth value of a statement form is
always T no matter what the truth values of its
components are.
 Contradiction: Opposite of tautology. Always F.
13
B. Okuku
 Single inference in deductive reasoning
Hypothetical Syllogism
 Has the form AB
BC
Conclude: A  C

 Makes it possible to combine two rules and

derive a new rule. Also (A  B)  (B  C)
 (A C)
 It is also be a tautology.

14
B. Okuku
 Single inference in deductive reasoning
Modus Tollens
 The rule of inference used when the

negation of a fact is established.

 It has the form: A  B

B
Conclude:  A

 If the consequent is not true, then the

antecedent is not true.
 It is also a tautology.
15
B. Okuku
 Single inference in deductive reasoning
Inference in Predicate Calculus
 Predicate calculus uses rules of inference in

propositional calculus.
 Modus ponens and hypothetical syllogism are used.
 Predicate calculus has predicates and quantifiers
(Existential and Universal) that do not exist in
propositional calculus.
 Quantifiers: Provide more power for the system
because the content of propositions can be broken
into predicates - unification and resolution.

16
B. Okuku
Rules of Inference
Law of Detachment: p -> q
p
therefore, q

Law of the Contrapositive: p -> q

therefore, ~q -> ~p
If something is a bird, then it is an animal
If something is not an animal, then it is not a bird
Chain rule (Law of the Syllogism): p -> q
q -> r
therefore, p -> r

Law of Disjunctive Inference: pvq pvq

~p ~q
therefore, q p
Either Sylvia is going to make brownies or she's going to make a pizza. Sylvia is
not going to make brownies

Law of Double Negation: ~(~p)

17
therefore, p
B. Okuku
 Rules of Inference

DeMorgan’s Law: ~(p ^ q) ~(p v q)

therefore, ~p v ~q ~p ^ ~q

Law of Conjunction: p
q
therefore, p ^ q

Law of Disjunctive Addition: p

therefore, p v q
We can add absolutely any statement to a given true statement, even if there does not
seem to be a connection between the statements
Law of Conjunctive Argument: ~(p ^ q) ~(p ^ q)
p q
therefore, ~q ~p
It is not the case that Sylvia will go to the bank and the grocery store. Sylvia went to the
bank
=> Sylvia will not go to the grocery store
18
B. Okuku
 Multiple inference in deductive reasoning
 Applying rules of inference to the entire
knowledge base requires tools for analysis and
heuristics that could improve the speed of
system response is known as Multiple Inference
 Multiple Inference (MI)- Involves testing rules or
predicates to find the one which must fire next.
 The commonly used methods of multiple
inference are:
 Graphs, Trees, and the And/Or Graph.
 Backward Chaining.
 Forward Chaining.
19
B. Okuku
 Graphs
 Uses graph theory.
 Easily understandable.
 Consists of nodes connected by arcs
 Directed Graph: The direction of an arc
connecting two nodes is important.
 Path: The sequence of nodes and arcs
connecting the beginning node of the path to
the end node of the path
 Cycle: The ending node of the path is the
same as the beginning node.

20
B. Okuku
 Graph
A A

A. Graph

B C B C C

D E E F

B. Directed graph, with paths, A - B - E etc.

A

B C

D C. Graph with cycle, A - B - C 21

B. Okuku
 Tree
 A directed graph with no
cycles which starts with a
beginning node (root) and Root
ends with ending nodes A
(leaves).
 Paths start from the root
and end with leaves in a B C
tree
Leaves
 There is only one path
from the root to each E F G H
leaf.
 Used extensively in A.I. Directed graph, with branches,
And Expert Systems e.g. A - B - E etc.
and/or graph and decision
tree.
22
B. Okuku
 And/Or Graph
 Rules and predicates are shown with nodes and
arcs.
 Examples
A A

B C B C

BCA B CA

 The two arcs in the AND diagram are connected by

another arc signifying that both A and B must be true
to reach conclusion C from this rule.

23
B. Okuku
 Backward and Forward Chaining.
 Two well known and commonly used
methods of multiple inference in expert
systems are
 Backward Chaining.
 Forward Chaining.

24
B. Okuku
 Backward Chaining
 The multiple inference starts with a question or
goal.
 The inference engine starts from the
consequent of a rule and goes backward to the
antecedent or IF part of the rule.
 The Backward Chaining algorithm
1. State a specific goal (question)
2. Find rules which resolve the goal
3. At runtime, answer questions to satisfy the
antecedents of the rules as required
4. Obtain a result (goal resolved or not)
25
B. Okuku
The Backward Chaining algorithm

State primary
goal to source Source
sub goals
Fire backward
2 3
chaining rules

Primary goal
sourced

26
B. Okuku
 Backward Chaining example
 A knowledge base consists of the
following rules G

1. AC
2. DE E F

3. BCF
4. EFG D B C

 The and/or graph is as shown

A

27
B. Okuku
 Backward Chaining example
 The goal is to establish whether G is true.
 The inference engine checks to see which
rule has G as its consequent.
 Rule 4 fires
 To conclude from this that G is true, E or
F must be shown to be true.
 E becomes the current goal of the system
 The inference engine checks to see which
rule has E as its consequent
 Rule 2 fires
28
B. Okuku
 Backward Chaining example
 The current goal becomes D
 The inference engine checks to see which
rule has D as its consequent
 There is none.
 It asks the user to provide information
about D
 D is True
 The inference engine concludes that E is true and
G is also true.
 D is False
 The system fails to establish the truth of E
29
B. Okuku
 Backward Chaining example
 In this case, it backtracks and picks up F
to get at the goal G.
 B and C become the current goal.
 B is not the consequent of any rule and
the system asks the user if it is true.
 B is False
 No matter what C is, the conditional part of rule 3
is false and the inference engine fails to establish
whether G is true.
 B is True
 The inference engine pursues C etc
30
B. Okuku
 Reasons for Backward Chaining
 There is a clear set of statements which
must be confirmed or denied.
 A large number of questions could be
asked of the user, but typically only a few
are necessary to resolve a situation.
 It is desirable to have interactive dialogue
with the user.
 Rule execution depends on data gathering
which may be expensive or difficult.
31
B. Okuku
 Characteristics of backward chaining:
 Good for Diagnosis.
 Looks from present to past.
 Works from consequent to antecedent.
 Is goal-driven, top-down reasoning.
 Works backward to find facts that support
the hypothesis.
 It facilitates a depth-first search.
 The consequents determine the search.
 Facilitates explanation.
32
B. Okuku
 Forward Chaining
 The system requires the user to provide facts
pertaining to the problem.
 The inference engine tries to match each fact
with the antecedent or if part of a rule.
 If the match succeeds, the rule fires and the
consequent of that rule is established and is
added to the known facts of the case.
 The process continues until the inference engine
has drawn all possible conclusions by matching
facts to antecedents of rules in the knowledge
base.
 Among these could be goals of the system.
33
B. Okuku
 The Forward Chaining algorithm
1. Enter new data
2. Fire forward chaining
1
rules Add new data values
Get some
3. Rule actions infer new data to knowledge base

new data values 4

Fire forward
4. Go to step 2 2
chaining rules Infer new data values
5. Repeat until no new from rule actions

data can be inferred 3

6. If no solution, rule
base is insufficient
34
B. Okuku
 Forward Chaining example
 Forward Chaining using the same knowledge
base consisting of the following rules G
1. AC
2. DE
E F
3. BCF
4. EFG
 A and B are the known facts D B C

 Using rule 1 inference engine concludes that C is

true.
A
 Using rule 3 it concludes that F is true.
 Using rule 4 it then concludes that G is true.
35
B. Okuku
 Reasons for forward chaining
 When everything that can possibly be
concluded about a set of data needs to be
known.
 Many conclusions are possible from a
single data item.
 It is important to communicate new
conclusions to the user immediately.

36
B. Okuku
 Characteristics of forward chaining:
 Good for monitoring, planning, and control
 Looks from present to future.
 Works from antecedent to consequent.
 Is data-driven, bottom-up reasoning.
 Works forward to find what solutions
follow from the facts.
 It facilitates a breadth-first search.
 The antecedents determine the search.
 It does not facilitate explanation.
37
B. Okuku
 Criteria for choosing inferences
 The logical reasoning process.
 Design features of the system.
 The inputs and where they come from.
 The outputs and where they go.
 How the inputs and outputs map to
forward or backward chaining.

38
B. Okuku
 Backward vs. Forward chaining
Backward Chaining
 Useful when the number of goals is small and

the and/or graph does not have numerous levels.

 In some systems, the user has the choice of
telling the inference engine which goal it must
pursue - Goal selection by the user.
Forward Chaining
 Performs well when the number of goals is large,

the user has a given set of facts at the start and

wants to find the implications of these facts.

39
B. Okuku
 Backward vs. Forward chaining
 Useful when the number of goals is small
and the and/or graph does not have
numerous levels.
 In some systems, the user has the choice
of telling the inference engine which goal it
must pursue - Goal selection by the user.
Next Lecture
 Search Methods

40
B. Okuku