Chapter 7

Logical Agents
CS361 Artificial Intelligence
Dr. Khaled Wassif
Spring 2024

(This is the instructor’s notes, and the student must

read the textbook for complete material.)
 Chapter Outline
◼ Knowledge-based Agents
◼ Wumpus World
◼ Logic in General - Models and Entailment
◼ Propositional (Boolean) Logic
◼ Equivalence, Validity, Satisfiability
◼ Inference Rules and Theorem Proving
– Resolution
– Forward Chaining
– Backward Chaining
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 2
By Dr. Khaled Wassif
 Knowledge-based Agents
◼ Central component of a knowledge-based agent is its
knowledge base (KB).
◼ A knowledge base is a set of sentences:
– Expressed in a formal language (called knowledge
representation language).
– Represent some assertion about the world.
◼ There must be a way to add new sentences to the
knowledge base, and a way to query what is known.
– Standard names for these operations are TELL and ASK.
– Main requirement when ASKs a question, the answer should
follow from what has been TELLed to the KB previously.
◼ Determining what follows from what the KB has been
TELLed is the job of the inference mechanism, the
other main component of a knowledge-based agent.
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 3
By Dr. Khaled Wassif
 Knowledge-based Agents

◼ Declarative approach to building a knowledge-based

agent:
– Tell it what it needs to know (called background knowledge)
– Then it can Ask itself what to do
» Answers should follow from the KB.
» Extensive reasoning may be done.
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 4
By Dr. Khaled Wassif
 Simple Knowledge-based Agent

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 5

By Dr. Khaled Wassif
 Simple Knowledge-based Agent

◼ The agent must be able to:

– Represent states, actions, etc.
– Incorporate new percepts
– Update internal representations of the world
– Deduce hidden properties of the world
– Deduce appropriate actions

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 6

By Dr. Khaled Wassif
 Knowledge-based Agents
◼ A knowledge-based agent can be described at three
levels:
– Knowledge level
» Most abstract level that specify only what the agent knows and
what its goals.
– Logical level
» The level at which the knowledge is encoded into sentences using a
knowledge representation language.
– Implementation level
» The level that runs on the agent architecture.
» At which there are physical representations of the sentences of the
logical level.
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 7
By Dr. Khaled Wassif
 The WUMPUS World

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 8

By Dr. Khaled Wassif
 The WUMPUS World (cont.)
◼ An early computer game:
– Based on an agent who explores a cave consisting of rooms
connected by passageways.
– Lurking somewhere in the cave is the terrible wumpus, a
beast that eats anyone who enters its room.
– The wumpus can be shot by an agent, but the agent has
only one arrow.
– Some rooms contain bottomless pits that will trap anyone
who wanders into these rooms (except the big wumpus).
– The only explanatory feature of living in this environment
is the possibility of finding a heap of gold.
◼ It makes an excellent test bed environment for
intelligent agents.
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 9
By Dr. Khaled Wassif
 Wumpus World PEAS Description
◼ Performance measure:
– +1000 gold, -1000 death
– -1 per step, -10 for using the arrow
◼ Environment:
– A 4×4 grid of rooms and the agent always starts in [1,1]
– Squares adjacent to wumpus are smelly
– Squares adjacent to pit are breezy
– Glitter iff gold is in the same square
– Shooting kills wumpus if you are facing it
– Shooting uses up the only arrow
– Grabbing picks up gold if in same square
– Releasing drops the gold in same square
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 10
By Dr. Khaled Wassif
Wumpus World PEAS Description

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 11

By Dr. Khaled Wassif
 Wumpus World PEAS Description
◼ Sensors:
– In the cell containing the wumpus, and in the directly (not
diagonally) adjacent cells, the agent will perceive a Stench.
– In the cells adjacent to a pit, the agent will perceive a Breeze.
– In the cell containing the gold, the agent will perceive a Glitter.
– If the agent walks into a wall, it perceives a Bump.
– When the wumpus is killed, the agent perceives a Scream.
– The agent cannot perceive its location.
Thus, a percept is a quintuple
< Stench, Breeze, Glitter, Bump, Scream >
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 12
By Dr. Khaled Wassif
 Wumpus World PEAS Description
◼ Actuators:
– Move Forward.
– Turn Right.
– Turn Left.
– Grab.
– Shoot.
– Climb.
◼ Goals:
– Get gold and return back to the start without entering a pit or
wumpus square.
◼ Can search help the Wumpus world agent?
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 13
By Dr. Khaled Wassif
 Wumpus World Characterization
◼ Fully Observable No – only local perception
◼ Deterministic Yes – outcomes exactly specified
◼ Episodic No – sequential at the level of actions
◼ Static Yes – Wumpus and Pits do not move
◼ Discrete Yes
◼ Single-agent? Yes – Wumpus is essentially a natural
feature

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 14

By Dr. Khaled Wassif
 Exploring Wumpus World

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 15

By Dr. Khaled Wassif
 Exploring Wumpus World

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 16

By Dr. Khaled Wassif
 Exploring Wumpus World

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 17

By Dr. Khaled Wassif
 Exploring Wumpus World

P
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 18
By Dr. Khaled Wassif
 Exploring Wumpus World

P
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 19
By Dr. Khaled Wassif
 Exploring Wumpus World

P
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 20
By Dr. Khaled Wassif
 The WUMPUS World (cont.)
◼ Percepts provide deeper knowledge of the environment.
– For example, sensing no stench while in [1,1], the agent
should know that the wumpus is neither in [1,2] nor in [2,1].
◼ In order to update the state, given a new percept, the
agent needs the following:
1. Background knowledge linking percepts to possible
contents of cells.
2. Some way of representing this knowledge.
3. Some way of mapping percepts to structures of the same
representation.
4. A method that manipulates these structures to update the
agent’s of the state of the environment.
◼ That is, the agent needs full-fledged logical reasoning.
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 21
By Dr. Khaled Wassif
 What is Logic?
◼ There are different uses of the word “logic”.
– But think of “logic” as a language for representing
knowledge such that conclusions can be drawn.
» For example, knowledge of the Wumpus-world agent.
◼ Logic is a formal language and should have precise
syntax and semantics.
– Syntax defines sentences in the representation language.
– Semantics define the "meaning" of sentences.
» Define the truth of each sentence with respect to each possible world.
– E.g., arithmetic language
» “x + y = 4” is a well-formed sentence; but “x4y+ =” is not
» x + 2 ≥ y is true iff the number x + 2 is not less than the number y
– In standard logics, every sentence must be either true or
false in each possible world.
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 22
By Dr. Khaled Wassif
 What is Logic?
◼ Model is a word used instead of “possible world” for
sake of precision.
– If a sentence α is true in model m, we say that m satisfies α (or
m is a model of α).
– We use the notation M(α) to mean the set of all models of α.
◼ Definition:
– Models are mathematical abstractions, each of which simply
fixes the truth or falsehood of every relevant sentence.
– Example:
» x number of men and y number of women sitting at a table playing
bridge.
» x + y = 4 is a sentence which is true when the total number is four.
» Models: all possible assignments of real numbers to the variables x and
y and each assignment fixes the truth of any arithmetic sentence whose
variables are x and y.
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 23
By Dr. Khaled Wassif
 Logical Entailment (Implication)
◼ A sentence α logically follows (implies or entails) a
sentence  if and only if every model in which α is
true,  is also true (written α╞ 𝛽).
– Example
“All men are mortal and Socrates is a man”
logically implies “Socrates is mortal”
◼ Knowledge base KB entails sentence α if and only if α
is true in all models where KB is true (written KB╞ α).
– E.g., the KB containing “Both Ahmed and Gamal came”
entails “Ahmed came”
– E.g., x = 0 entails x . y = 0
◼ Entailment is based only on semantics and does not
depend at all on logical inference.
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 24
By Dr. Khaled Wassif
 Entailment in Wumpus World
◼ A situation after detecting
nothing in [1,1], moving right,
and detecting breeze in [2,1]

◼ Consider possible models for

KB assuming only pits

◼ 3 Boolean choices  23 = 8
possible models

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 25

By Dr. Khaled Wassif
 Wumpus Models

8 possible models
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 26
By Dr. Khaled Wassif
 Wumpus Models

◼ KB = Wumpus-world rules + observations

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 27
By Dr. Khaled Wassif
 Wumpus Models

◼ KB = Wumpus-world rules + observations

◼ α1 = "[1,2] is safe", KB ╞ α1, proved by model checking
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 28
By Dr. Khaled Wassif
 Wumpus Models

◼ KB = Wumpus-world rules + observations

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 29
By Dr. Khaled Wassif
 Wumpus Models

◼ KB = Wumpus-world rules + observations

◼ α2 = "[2,2] is safe", KB ╞ α2
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 30
By Dr. Khaled Wassif
 Logical Inference
◼ KB├i α = sentence α can be derived from KB by an
inference procedure i.
◼ Soundness: i is sound if it derives only sentences that
are entailed by KB. KB├i α KB╞ α
– It is easy to see that model checking is a sound procedure.
◼ Completeness: i is complete if it derives all sentences
that are entailed by KB. KB╞ α KB├i α
◼ There are sound and complete inference procedures
for logics (first-order logic) that are sufficiently
expressive to handle many knowledge bases.
◼ If KB is true in the real world, then any sentence α
derived from KB by a sound inference procedure is
also true in the real world.
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 31
By Dr. Khaled Wassif
 Logical Inference
Sentences Inference Sentence
Logical
KB 
Representation

Semantics
Semantics
Aspects of the Entail Aspect of the
World real world real world

Logical reasoning should ensure that the new configurations

represent aspects of the world that actually follow from the
aspects that the old configurations represent.
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 32
By Dr. Khaled Wassif
 Propositional Logic
◼ Propositional logic is the simplest logic.

– Syntax

– Semantic

– Entailment and Inference

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 33

By Dr. Khaled Wassif
 Propositional Logic: Syntax
◼ Syntax defines the allowable sentences.
◼ Atomic sentence:
– Single proposition symbol.
» Uppercase names for symbols must have some mnemonic value.

» Example: W1,3 to say the Wumpus is in [1,3].

– True and False: two proposition symbols with fixed meaning.

◼ Complex sentences:
– Constructed from simpler sentences using logical connectives.

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 34

By Dr. Khaled Wassif
 Propositional Logic: Syntax
◼ Logical connectives:
1.  (not) negation.
2.  (and) conjunction, its operands are conjuncts.
3.  (or) disjunction, its operands are disjuncts.
4. ⇒ (implies) implication or conditional.
» As A ⇒ B, A is the premise or antecedent and B is
the conclusion or consequent.
» It is also known as rule or if-then statement.
5.  (if and only if) equivalent or biconditional.
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 35
By Dr. Khaled Wassif
 Propositional Logic: Syntax
◼ Logical constants True and False are sentences.
◼ Proposition symbols P1, P2 etc. are sentences.
– Symbols P1 and negated symbols  P1 are called literals.
◼ If S is a sentence,  S is a sentence (negation).
◼ If S1 and S2 are sentences, S1  S2 is a sentence
(conjunction).
◼ If S1 and S2 are sentences, S1  S2 is a sentence
(disjunction).
◼ If S1 and S2 are sentences, S1  S2 is a sentence
(implication).
◼ If S1 and S2 are sentences, S1  S2 is a sentence
(biconditional).
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 36
By Dr. Khaled Wassif
 Propositional Logic: Syntax
◼ Order of precedence
From highest to lowest:
– Parenthesis ( Sentence ) or [ Sentence ]
– Not 
– And 
– Or 
– Implies 
– Equivalent 

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 37

By Dr. Khaled Wassif
 Propositional Logic: Syntax
A BNF (Backus-Naur Form) grammar of sentences in
propositional Logic is defined by the following rules:

Sentence → AtomicSentence │ComplexSentence

AtomicSentence → True │ False │ Symbol
Symbol → P │ Q │ R …
ComplexSentence → ( Sentence ) │ [ Sentence ]
│  Sentence
│ Sentence  Sentence
│ Sentence  Sentence
│ Sentence  Sentence
│ Sentence  Sentence
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 38
By Dr. Khaled Wassif
 Propositional Logic: Syntax
◼ Example sentences:
– P means “It is hot.”
– Q means “It is humid.”
– R means “It is raining.”
– (P  Q)  R
“If it is hot and humid, then it is raining”
– QP
“If it is humid, then it is hot”
– A better way:
Hot = “It is hot”
Humid = “It is humid”
Raining = “It is raining”
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 39
By Dr. Khaled Wassif
 Propositional logic: Semantics
◼ Semantics define the rules for determining the truth
of a sentence with respect to a particular model.
– Each model specifies the truth value (true or false) for each
proposition symbol.
– E.g. P1,2 P2,2 P3,1
false false true
– With these three symbols, 8 possible models, can be
enumerated automatically.
◼ Rules:
 S is true iff S is false
S1  S2 is true iff S1 is true and S2 is true
S1  S2 is true iff S1is true or S2 is true
S1  S2 is true iff S1 is false or S2 is true
i.e., is false iff S1 is true and S2 is false
S1  S2 is true iff S1 and S2 are both true or both false
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 40
By Dr. Khaled Wassif
 Truth Tables for Connectives

◼ Most sentences are sometimes true.

PQ
◼ Some sentences are always true (valid).
PP
◼ Some sentences are never true (unsatisfiable).
PP
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 41
By Dr. Khaled Wassif
 Simple Inference Procedure
◼ Model-checking (or Enumeration) is an inference
approach that implement directly the definition of
entailment:
– Enumerate all possible models by assigning true or false to
every proposition symbol.
– Check that α is true in every model in which KB is true.
◼ This procedure is sound and complete.
◼ Example:
– Let  =    and KB = (  C)  (B  C)
– Is it the case that KB ╞  ?
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 42
By Dr. Khaled Wassif
 Simple Inference Procedure
KB 
A B C
(  C)  (B  C) 
False False False False False
False False True False False
False True False False True
False True True True True
True False False True True
True False True False True
True True False True True
True True True True True

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 43

By Dr. Khaled Wassif
 Simple Inference Procedure
KB 
A B C
(  C)  (B  C) 
False False False False False
False False True False False
False True False False True
False True True True True
True False False True True
True False True False True
True True False True True
True True True True True

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 44

By Dr. Khaled Wassif
 Simple Inference Procedure
KB 
A B C
(  C)  (B  C) 
False False False False False
False False True False False
False True False False True
False True True True True KB╞ α
True False False True True
True False True False True
True True False True True
True True True True True

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 45

By Dr. Khaled Wassif
 Wumpus World Sentences
◼ Let Pi,j be true if there is a pit in [i,j] and Bi,j be true if
there is a breeze in [i,j].
– There is no pit in [1,1]:
R1: P1,1
– “Pits cause breezes in adjacent squares”. But, we include
just the relevant squares:
R2: B1,1  (P1,2  P2,1)
R3: B2,1  (P1,1  P2,2  P3,1)
– Now we include the breeze percepts for the first two
squares visited by the agent:
R4: B1,1
R5: B2,1
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 47
By Dr. Khaled Wassif
 Inference by Enumeration

1 = P1,2 2 = P2,2 3 = P3,1

KB = R1  R2  R3
 R4  R5 KB╞ α1 KB ╞ α2 KB ╞ α3
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 48
By Dr. Khaled Wassif
 Propositional Theorem Proving
◼ Proof methods are divided (roughly) into two kinds:
– Model checking
» Truth table enumeration (sound and complete for propositional
logic).
» Suitable only in case of small numbers of propositional symboles.
» For n symbols, the time complexity is O(2n).
– Application of inference rules
» More efficient than model checking.
» Proof without consulting models by applying set of inference rules.
» Legal (sound) generation of new sentences from current sentences.
» Can use inference rules as operators in a standard search algorithm.
» Typically require transformation of sentences into a normal form.
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 49
By Dr. Khaled Wassif
 Additional Entailment Concepts
◼ Two sentences α and ß are logically equivalent α ≡ ß
iff each of them entails the other: α╞ β and β╞ α

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 50

By Dr. Khaled Wassif
 Additional Entailment Concepts
◼A sentence is valid (or tautology) if it is true in all
models:
e.g., True, A  A, A  A, (A  (A  B))  B
◼ Validity
is connected to inference via the Deduction
Theorem:
KB╞ α if and only if (KB  α) is valid
◼A sentence is satisfiable if it is true in some model:
e.g., A  B, C
◼A sentence is unsatisfiable if it is true in no models:
e.g., A  A
◼ Satisfiability is connected to inference via the contradiction:
KB╞ α if and only if (KB  α) is unsatisfiable
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 51
By Dr. Khaled Wassif
 Inference Rules
◼ An inference rule is sound if the conclusion is true in
all cases where the premises are true:
 Premise
 Conclusion
– Modus Ponens
» From an implication and the premise of the implication, you can
infer the conclusion:
    Premise
 Conclusion
– Modus Tollens
» From an implication and the conclusion negation of the implication,
you can infer the premise negation.
    ¬ Premise
¬ Conclusion
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 52
By Dr. Khaled Wassif
 Inference Rules
– And-Elimination
» From a conjunction, you can infer any of the conjuncts.
1  2  …  n Premise
i Conclusion

– And-Introduction
» From a list of sentences, you can infer their conjunction.
1, 2, …, n Premise
1  2 …  n Conclusion

– Or-Introduction
» From a sentence, you can infer its disjunction with anything else at all.
i Premise
1  2  …  n Conclusion
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 53
By Dr. Khaled Wassif
 Inference Rules
– Unit Resolution
» From a disjunction, if one of the disjuncts is false, then you can
infer the other one is true.
     Premise
 Conclusion

– Resolution
      Premise
  Conclusion
or equivalently
      Premise
   Conclusion

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 54

By Dr. Khaled Wassif
 Inference in Wumpus World
◼ Let Si,j be true if there is
a stench in cell [i,j].

◼ Let Bi,j be true if there is

a breeze in cell [i,j]. W
◼ Let Wi,j be true if there is
a Wumpus in cell [i,j].

◼ Let Pi,j be true if there is P

a Pit in cell [i,j].
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 55
By Dr. Khaled Wassif
 Inference in Wumpus World
◼ Given:
R2: B1,1 ⇔ (P1,2  P2,1)
R4: ¬B1,1
◼ Let’s make some inferences:
1. (B1,1 ⇒ (P1,2  P2,1))  ((P1,2  P2,1) ⇒ B1,1 )
(By definition of the biconditional)
2. (P1,2  P2,1) ⇒ B1,1 (And-elimination)
3. ¬B1,1 ⇒ ¬(P1,2  P2,1) (equivalence with contrapositive)
4. ¬(P1,2  P2,1) (modus ponens)
5. ¬P1,2  ¬P2,1 (DeMorgan’s rule)
6. ¬P1,2 (And Elimination)
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 56
By Dr. Khaled Wassif
 Inference in Wumpus World
Initial KB
Percept Sentences Some inferences:
S1,1 B1,1 Apply Modus Ponens to R11
S2,1 B2,1 Add to KB
S1,2 B1,2
…
W1,1  W2,1  W1,2

Environment Knowledge Apply to this And-Elimination

R11: S1,1 W1,1 W2,1 W1,2
R12: S1,2 W1,2  W1,1  W2,2  W1,3
Add to KB
R13: B1,1  P1,1  P2,1  P1,2 W1,1
R14: B1,2  P1,1  P1,2  P2,2  P1,3 W2,1
... W1,2

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 57

By Dr. Khaled Wassif
 Inference in Wumpus World
◼ Recall that when we were at [2,1] we could not
decide on a safe move, so we backtracked, and
explored [1,2], which yielded ¬B1,2.

¬B1,2 ⇔ ¬P1,1  ¬P1,3  ¬P2,2

this yields to ¬P1,1  ¬P1,3  ¬P2,2
and consequently ¬P1,1 , ¬P1,3 , ¬P2,2

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 58

By Dr. Khaled Wassif
 Inference in Wumpus World
◼ Now we can consider the implications of B2,1
and prove by resolution:
1. B2,1 ⇔ (P1,1  P2,2  P3,1)
2. B2,1 ⇒ (P1,1  P2,2  P3,1)
(biconditional Elimination)
3. P1,1  P2,2  P3,1 (modus ponens)
4. P1,1  P3,1 (resolution rule because no pit in [2,2])
5. P3,1 (resolution rule because no pit in [1,1])

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 59

By Dr. Khaled Wassif
 Conversion to CNF
◼ The resolution rule applies only to knowledge bases and
queries consisting of clauses (disjunctions of literals).
◼ A sentence expressed as a conjunction of clauses is
said to be in Conjunctive Normal Form (CNF).
– E.g., (A  B)  (B  C  D)
◼ Every sentence of propositional logic is logically
equivalent to a conjunction of clauses.
◼ Converting the propositional sentences into CNF
allows using the resolution rule as part of a complete
inference procedure for all of propositional logic.
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 60
By Dr. Khaled Wassif
 Conversion to CNF: Example
◼ Converting B1,1  (P1,2  P2,1) into CNF:
1. Eliminate  by replacing α  β with (α  β)  (β  α):
(B1,1  (P1,2  P2,1))  ((P1,2  P2,1)  B1,1)
2. Eliminate , replacing α  β with α  β:
(B1,1  P1,2  P2,1)  ((P1,2  P2,1)  B1,1)
3. Move  inwards using De Morgan's and double-negation
rules, replacing ¬(α  β) with (¬α  ¬β) and ¬(¬α) with α:
(B1,1  P1,2  P2,1)  ((P1,2  P2,1)  B1,1)
4. Apply distributivity law (distributing  over ) and flatten,
replacing (α  (β  γ)) with ((α  β)  (α  γ)):
(B1,1  P1,2  P2,1)  (P1,2  B1,1)  (P2,1  B1,1)
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 61
By Dr. Khaled Wassif
 Proof by Contradiction
◼ Inference procedures based on resolution work by
using the principle of proof by contradiction.
– Show that KB ╞ α by showing that (KB ∧ ¬α) is unsatisfiable.
1. First, convert (KB ∧ ¬α) into CNF.
2. Then, apply the resolution rule to the resulting clauses.
» Each pair that contains complementary literals is resolved to produce
a new clause, which is added to the set if it is not already present.
3. The process continues until one of two things happens:
» There are no new clauses that can be added
In which case KB does not entail α.
» Two clauses resolve to yield the empty clause
In which case KB entails α.
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 62
By Dr. Khaled Wassif
 Proof by Contradiction: Example
◼ KB = R2  R4
(B1,1  (P1,2 P2,1))  B1,1
◼ α = P1,2

◼ Then KB╞ α (or R2  R4  P1,2)

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 64
By Dr. Khaled Wassif
Definite Clauses and Horn Clauses
◼ Some real-world knowledge bases satisfy certain
restrictions on the form of sentences they contain:
– Definite clauses are clauses with exactly one positive literal.
» E.g., the clause      is a definite clause.
– Horn clauses are clauses with at most one positive literal.
◼ All definite clauses are Horn clauses.
– Clauses with no positive literals are called goal clauses.
◼ Horn clauses are closed under resolution:
– If two Horn clauses are resolved, we get back a Horn
clause.
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 65
By Dr. Khaled Wassif
Definite Clauses and Horn Clauses
◼ Knowledge bases containing only definite clauses are
interesting for three reasons:
– Every definite clause can be written as an implication whose
premise is a conjunction of positive literals and whose
conclusion is a single positive literal.
» E.g., the clause      can be written as      .
» In Horn form, the premise is called the body and the conclusion is
called the head – like Prolog.
» A sentence consisting of a single positive literal only is called a fact.
– Inference with Horn clauses can be done through the
forward-chaining and backward chaining algorithms.
– Deciding entailment with Horn clauses can be done in time
that is linear in the size of the knowledge base.
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 66
By Dr. Khaled Wassif
CNF & Definite and Horn Clauses Grammar

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 67

By Dr. Khaled Wassif
 Forward Chaining
◼ To determine if a query is entailed by a knowledge
base (KB) of definite clauses (implications):
– Begin from known facts (positive literals) in KB.
– If all premises of an implication (rule) are known, then its
conclusion is added to the set of known facts.
– This process continues until the query is added or no further
inferences can be made.
◼ An exampleP ofQ the general concept of data-driven
LMP
reasoning: B  L  M
– The focus Aof attention
PL starts with the known data.
ABL
– It can be used
A within an agent to derive conclusions from
incoming percepts,
B often without a specific query in mind.
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 68
By Dr. Khaled Wassif
 Forward Chaining Example

PQ
LMP
BLM
APL
ABL
A
B

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 69

By Dr. Khaled Wassif
 Forward Chaining Example

PQ
LMP
BLM
APL
ABL
A
B

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 70

By Dr. Khaled Wassif
 Forward Chaining Example

PQ
LMP
BLM
APL
ABL
A
B

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 71

By Dr. Khaled Wassif
 Forward Chaining Example

PQ
LMP
BLM
APL
ABL
A
B

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 72

By Dr. Khaled Wassif
 Forward Chaining Example

PQ
LMP
BLM
APL
ABL
A
B

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 73

By Dr. Khaled Wassif
 Forward Chaining Example

PQ
LMP
BLM
APL
ABL
A
B

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 74

By Dr. Khaled Wassif
 Forward Chaining Example

PQ
LMP
BLM
APL
ABL
A
B

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 75

By Dr. Khaled Wassif
 Forward Chaining Example

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 76

By Dr. Khaled Wassif
 Backward chaining
◼ As its name suggests, work backward from the query:
– If the query is known to be true, then no work is needed.
– Otherwise, find those implications in the knowledge base
whose conclusion is the query.
– If all the premises of one of those implications can be
proved true (by backward chaining), then the query is true.
– It works backward until it reaches a set of known facts.
◼ PQ
A form of goal-directed reasoning.
LMP
◼ Often, the costB  Lof
 Mbackward chaining is much less
APL
than linear in Athe
 B size
 L of the knowledge base, because
the process touches
A only relevant facts.
B
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 78
By Dr. Khaled Wassif
 Backward Chaining Example

PQ
LMP
BLM
APL
ABL
A
B

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 79

By Dr. Khaled Wassif
 Backward Chaining Example

PQ
LMP
BLM
APL
ABL
A
B

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 80

By Dr. Khaled Wassif
 Backward Chaining Example

PQ
LMP
BLM
APL
ABL
A
B

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 81

By Dr. Khaled Wassif
 Backward Chaining Example

PQ
LMP
BLM
APL
ABL
A
B

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 82

By Dr. Khaled Wassif
 Backward Chaining Example

PQ
LMP
BLM
APL
ABL
A
B

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 83

By Dr. Khaled Wassif
 Backward Chaining Example

PQ
LMP
BLM
APL
ABL
A
B

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 84

By Dr. Khaled Wassif
 Backward Chaining Example

PQ
LMP
BLM
APL
ABL
A
B

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 85

By Dr. Khaled Wassif
 Backward Chaining Example

PQ
LMP
BLM
APL
ABL
A
B

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 86

By Dr. Khaled Wassif
 Backward Chaining Example

PQ
LMP
BLM
APL
ABL
A
B

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 87

By Dr. Khaled Wassif
 Backward Chaining Example

AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 88

By Dr. Khaled Wassif
 SUMMARY
◼ Logical agents apply inference to a knowledge base to
derive new information and make decisions.
◼ Basic concepts of logic:
– syntax: formal structure of sentence.
– semantics: truth of sentences models.
– entailment: necessary truth of one sentence given another.
– inference: deriving sentences from other sentences.
– soundness: derivations produce only entailed sentences.
– completeness: derivations can produce all entailed sentences.
◼ Wumpus world requires the ability to represent partial
and negated information, reason by cases, etc.
◼ Resolution is complete inference for propositional logic.
◼ Inference can be done through forward or backward
chaining algorithms.
AI: A modern Approach © 2010 S. Russell and P. Norving Slide 7- 89
By Dr. Khaled Wassif