Chapter 7

Logical Agents
Knowledge-Based Agents
• The central component of a knowledge-based agent is its knowledge base, or
KB.
• A KB is a set of sentences.
• Each sentence represents some assertion about the world.
• When the sentence is taken without being derived from other sentences, we
call it an axiom.
• TELL : a way to add new sentences to the knowledge base
• ASK: a way to query what is known.
• Inference—deriving new sentences from old
• A knowledge-based agent can be built simply by
• Declarative approach: the agent designer can TELL sentences one by one until the
agent knows how to operate in its environment.
• Procedural approach: encodes desired behaviors directly as program code
2
Dr. Husne Ara Chowdhury
The Wumpus World
o Performance measure:
o +1000 for climbing out of the cave with the gold,
o –1000 for falling into a pit or being eaten by the
wumpus,
o –1 for each action taken, and
o –10 for using up the arrow.
o The game ends either when the agent dies or
when the agent climbs out of the cave
o Environment: A 4×4 grid of rooms
o Actuators: The agent can move Forward,
TurnLeft by 90◦ or TurnRight by 90◦
o Sensors: five sensors
o Stench
o Breeze
o Glitter
o Bump
o Scream
3
Dr. Husne Ara Chowdhury
The Wumpus World

[None,None,None,None,None]. [None,Breeze,None,None,None].

[Stench,None,None,None,None] [Stench,Breeze,Glitter,None,None].
4
Dr. Husne Ara Chowdhury
Logic
• Syntax: Specifies all the sentences that are well formed
• Ex. “x+y = 4” is a well-formed sentence, whereas “x4y+ =” is not.
• Semantics: Meaning of sentences.
• Ex. “x+y=4” is true in a world where x is 2 and y is 2.
• Standard logics: true or false there is no “in between.”
• Model:
• Sentence x+y=4 is true when there are four people in total
• Possible models are just all possible assignments of nonnegative integers to the variables x
and y.
• If a sentence 𝛼 is true in model m, we say that m is a model of 𝛼.
• We use the notation M(𝛼) to mean the set of all models of 𝛼.
• Entailment: A sentence follows logically from another sentence
• Ex. means the sentence 𝛼 entails the sentence β
• means the sentence 𝛼 entails the sentence β, iff, in every model in
which 𝛼 is true, β is also true.
• sentence x = 0 entails the sentence xy = 0.

5
Dr. Husne Ara Chowdhury
Wumpus-world reasoning example from KB
• Possible models for the presence of pits in squares [1,2], [2,2], and [3,1]. There are 23=8
possible models
• The KB corresponding to the observations of nothing in [1,1] and a breeze in [2,1] is shown by
the solid line
• (a) Dotted line shows models of α1 (no pit in [1,2]).
• (b) Dotted line shows models of α2 (no pit in [2,2])

6
Dr. Husne Ara Chowdhury
Logic
• In every model in which KB is true, α1 is also true.
• Hence, KB |= α1: there is no pit in [1,2].
• In some models in which KB is true, α2 is false
• Hence, KB does not entail α2: the agent cannot conclude that there is no pit in [2,2].
• Logical inference
• Model checking: possible models to check that α is true in all models in which
KB is true, that is, that M(KB) ⊆ M(α).

7
Dr. Husne Ara Chowdhury
Logic
• Sentences are physical configurations of the agent
• Reasoning is a process of constructing new physical configurations from old ones.
• Logical reasoning should ensure that the new configurations represent aspects of the
world that actually follow from the aspects that the old configurations represent.

8
Dr. Husne Ara Chowdhury
Propositional Logic: Syntax
• Syntax: The syntax of propositional logic defines the allowable sentences.
• Complex sentences are constructed from simpler sentences, using
parentheses and operators called logical connectives.
• There are five connectives in common use:
• ¬ (not). A sentence such as ¬W1,3 is called the negation of W1,3.
• ∧ (and). A sentence whose main connective is ∧, such as W1,3 ∧P3,1, is called a
conjunction;
• ∨ (or). A sentence whose main connective is ∨, such as (W1,3 ∧P3,1)∨W2,2, is a
disjunction
• ⇒ (implies). A sentence such as (W1,3 ∧P3,1) ⇒ ¬W2,2 is called an implication
Implications are also known as rules or if–then statements.
• ⇔ (if and only if). The sentence W1,3 ⇔ ¬W2,2 is a biconditional.

9
Dr. Husne Ara Chowdhury
A BNF (Backus–Naur Form) in propositional logic

¬A∧B, the ¬ binds most tightly, giving us the equivalent of (¬A)∧B rather than
¬(A∧B).
10
Dr. Husne Ara Chowdhury
Propositional Logic: Semantics
• The semantics defines the rules for determining the truth of a sentence with
respect to a particular model.
• Ex. m1 = {P1,2 =false, P2,2 =false, P3,1 =true}
• With three proposition symbols, there are 23 =8 possible models.

Truth tables for the five logical connectives.

11
Dr. Husne Ara Chowdhury
Propositional Logic: Semantics
• For complex sentences, we have five rules, P and Q (atomic or complex) in
any model m
• ¬P is true iff P is false in m.
• P∧Q is true iff both P and Q are true in m.
• P∨Q is true iff either P or Q is true in m.
• P ⇒ Q is true unless P is true and Q is false in m.
• P ⇔ Q is true iff P and Q are both true or both false in m.
• Ex. means a square is breezy only if a neighboring square has a pit.

12
Dr. Husne Ara Chowdhury
Propositional Logic: A simple knowledge base

• We label each sentence as Ri

13
Dr. Husne Ara Chowdhury
 Propositional Logic: A simple inference procedure
With seven symbols, there are 27 =128 possible models;
Objective: Determine entailment by model checking:
in three of these, KB is true . In those three models, ¬P1,2 is
 showing th enumerating models and
true, hence there is no pit in [1,2]. Again, P2,2 is true in two
 at the sentence must hold in all models.
of the three models and false in one, so we cannot yet tell
whether there is a pit in [2,2].

14
Dr. Husne Ara Chowdhury
Propositional Theorem Proving
• Objective: show how entailment can be done by theorem proving—applying
rules of inference directly to the sentences in our knowledge base to construct
a proof of the desired sentence without consulting models
• If the number of models is large but the length of the proof is short, then
theorem proving can be more efficient than model checking.
• Some additional concepts:
• Logical equivalence: sentences α and β are logically equivalent if they are
true in the same set of models. i.e. α ≡ β.
• Ex. P∧Q and Q∧P are logically equivalent.
• Alternatively, α ≡ β if and only if α |= β and β |= α.
• Monotonicity: set of entailed sentences can only increase as information is added
to the knowledge base
if KB |= α then KB∧β |= α
15
Dr. Husne Ara Chowdhury
Propositional Theorem Proving
• Standard logical equivalences.
• The symbols α, β, and γ stand for arbitrary sentences of propositional logic.

16
Dr. Husne Ara Chowdhury
Propositional Theorem Proving
• Validity: A sentence is valid if it is true in all models.
• For any sentences α and β, α |= β if and only if the sentence (α ⇒ β) is valid.
• Valid sentences are also known as tautologies—they are necessarily true.
• Satisfiability: A sentence is satisfiable if it is true in, or satisfied by, some
model.
• Ex. the KB given earlier, (R1 ∧R2 ∧ R3 ∧ R4 ∧ R5), is satisfiable because these
are true in three models as shown previously.
• Satisfiability can be checked by enumerating the possible models until one is
found that satisfies the sentence.

17
Dr. Husne Ara Chowdhury
Propositional Theorem Proving: Inference and proofs
• Inference rules that can be applied to derive a proof—a chain of conclusions
that leads to the desired goal.
• Modus Ponens:

• Ex. if (WumpusAhead ∧ WumpusAlive) ⇒ Shoot and (WumpusAhead∧ WumpusAlive) are given,

then Shoot inferred.

• And-Elimination:
• Ex. from (WumpusAhead∧WumpusAlive), WumpusAlive can be inferred.
• Biconditional elimination rules work in both directions like this:

• Not all inference rules work in both directions

• For example, we cannot run Modus Ponens in the opposite direction to obtain α ⇒ β
and α from β.
18
Dr. Husne Ara Chowdhury
#Prove ¬P1,2, that is, there is no pit in [1,2]

19
Dr. Husne Ara Chowdhury
Propositional Theorem Proving: Proof by Resolution
• The unit resolution rule can be generalized to the full resolution rule

• where li and mj are complementary literals.

• Resolution takes two clauses and produces a new clause containing all the
literals of the two original clauses except the two complementary literals.
• Ex.

• Resolve only one pair of complementary literals at a time

• Removal of multiple copies of literals is called factoring.
• Ex. Resolve (A∨B) with (A∨ ¬B), we obtain (A∨A), which is reduced to just A by factoring.

20
Dr. Husne Ara Chowdhury
Conjunctive normal form (CNF)
• A sentence expressed as a conjunction of clauses is said to be in CNF

21
Dr. Husne Ara Chowdhury
Converting the sentence B1,1 ⇔ (P1,2 ∨P2,1) into CNF.
• The steps are as follows:

22
Dr. Husne Ara Chowdhury
A resolution algorithm

23
Dr. Husne Ara Chowdhury
Resolution algorithm
• To show that KB |= α, we show that (KB∧ ¬α) is unsatisfiable.
• We do this by proving a contradiction.
• A resolution algorithm is shown in previous slide.
• First, (KB∧ ¬α) is converted into CNF.
• Then, the resolution rule is applied to the resulting clauses.
• Each pair that contains complementary literals is resolved to produce a new
clause,
• 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 α; or,
• two clauses resolve to yield the empty clause, in which case KB entails α.

24
Dr. Husne Ara Chowdhury
Resolution algorithm: Example
• Humidity is high or sky is cloudy
1: P V Q
• If the sky is cloudy, then it will rain 2: Q →R
• If the humidity is high, then it is hot. 3: P →S
• It is not hot. 4: ┐S
• Goal: It will rain
• Steps: CNF
• Convert all sentences to CNF 1: P V Q
• Negate the desired conclusion 2: ┐ Q V R
3: ┐ P V S
4: ┐S

25
Dr. Husne Ara Chowdhury
 26
Dr. Husne Ara Chowdhury
Resolution algorithm: Example (wumpus world)
• When the agent is in [1,1], there is no breeze, so there can be no pits in neighboring
squares.
• The relevant knowledge base is
• KB = R2 ∧R4 = (B1,1 ⇔ (P1,2 ∨P2,1))∧ ¬B1,1
• We wish to prove α, which is, say, ¬P1,2.
• When we convert (KB ∧ ¬α) into CNF, we obtain the clauses as:
• (¬B1,1 ∨ P1,2 ∨ P2,1)∧(¬P1,2 ∨ B1,1)∧(¬P2,1 ∨ B1,1) ∧ ¬B1,1 ∧ P1,2.
• We see that the third and fourth clauses yield the clause ¬P1,2, which is then resolved with P1,2
to yield the empty clause, meaning that the query is proven.

27
Dr. Husne Ara Chowdhury
Horn clauses and definite clauses
• Definite clause: which is a disjunction of literals of which exactly one is
positive.
• For example, the clause (¬L1,1 ∨ ¬Breeze∨B1,1) is a definite clause, whereas (¬B1,1 ∨
P1,2 ∨ P2,1) is not, because it has two positive clauses.
• Horn clauses: which is a disjunction of literals of which at most one is positive.
• All definite clauses are Horn clauses.
• Goal clauses: clauses with no positive literals are called goal clauses.
• Horn clauses are closed under resolution: if you resolve two Horn clauses,
you get back a Horn clause.
• One more class is the k-CNF sentence, which is a CNF sentence where each
clause has at most k literals

28
Dr. Husne Ara Chowdhury
• KB containing only definite clauses are interesting for three reasons
1. 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.
 Ex. the definite clause (¬L1,1 ∨¬Breeze∨B1,1) can be written as (L1,1∧Breeze) ⇒ B1,1. it says.....
2. Inference with Horn clauses can be done through the forward-chaining and
backward-chaining algorithms. This is the basis for logic programming.
3. Deciding entailment with Horn clauses can be done in time that is linear in the
size of the knowledge base—a pleasant surprise.

29
Dr. Husne Ara Chowdhury
Forward and backward chaining
• The forward-chaining algorithm
determines if a single proposition
symbol q—the query—is entailed by a
knowledge base of definite clauses.
• For example, if L1,1 and Breeze are
known and (L1,1 ∧Breeze) ⇒ B1,1 is
in the knowledge base, then B1,1
can be added.
 Forward chaining is an example of the
general concept of data-driven
reasoning
 Backward chaining is a form of goal-
directed reasoning
(a) A set of Horn clauses. (b) The corresponding AND–OR graph

30
Dr. Husne Ara Chowdhury
End of the Chapter

31
Dr. Husne Ara Chowdhury