Logical Agents

Propositional Logic &

First Order Logic
By
Rashmi K
 Module4 Syllabus:

 Logical Agents: Knowledge-based Agents, The

Wumpus World, Logic, Propositional Logic: A Very
Simple Logic, Reasoning Patterns in Propositional
Logic.

 First-Order Logic: Representation Revisited, Syntax

and Semantics of First-Order Logic, Using First-Order
Logic.
 Why Do We Need Logic?
 Problem solving agents cannot infer unobserved
information.
 A knowledge-based agent can infer the facts and draw
new conclusions.
 It needs a KB and an inference mechanism.
 It operates by storing sentences in its knowledge base,
inferring new sentences with the inference mechanism, and
using them to deduce which actions to take the
interpretation of a sentence is the fact to which it refers.
 Knowledge & Reasoning
To address these issues we will introduce

 A knowledge base (KB): a list of facts that are known to

the agent.

 Rules to infer new facts from old facts using rules of

inference.

 Logic provides the natural language for this.

 Knowledge Bases
 Knowledge base:
 set of sentences in a formal language.
 The central component of a knowledge-based agent is its
knowledge base, or KB.

 A knowledge base is a set of sentences in a formal language

 Each sentence is expressed in a language called a knowledge

representation language

 Declarative approach to building an agent:

 Tell it what it needs to know.

 Ask it what to do  answers should follow from the

KB.
 First, it TELLs the knowledge base what it perceives.

 Second, it ASKs the knowledge base what action it

should perform. In the process of answering this query,
extensive reasoning may be done about the current state
of the world, about the outcomes of possible action
sequences, and so on.

 Third, the agent program TELLs the knowledge base

which action was chosen, and the agent executes the
action.
 Wumpus World PEAS description
Performance measure:
+1000 for climbing out of the cave with the gold,
–1000 for falling into a pit or being eaten by the wumpus,
 –1 for each action taken and –10 for using up the arrow.
The game ends either when the agent dies or when the agent grabs
the gold and moves out of the cave.
• Environment: A 4×4 grid of rooms. The agent always starts in the
square labelled
[1,1], facing to the right. The locations of the gold and the wumpus
are chosen randomly,with a uniform distribution, from the squares
other than the start square.
In addition, each square other than the start can be a pit.
 Actuators:
 The agent can move Forward, TurnLeft by 90◦, or TurnRight by 90◦.
 The agent dies a miserable death if it enters a square containing a pit
or a live wumpus.
 If an agent tries to move forward and bumps into a wall, then the
agent does not move.
 The action Grab can be used to pick up the gold if it is in the same
square as the agent.
 The action Shoot can be used to fire an arrow in a straight line in the
direction the agent is facing. The arrow continues until it either hits
(and hence kills) the wumpus or hits a wall. The agent has only one
arrow, so only the first Shoot action has any effect. Finally, the action
Climb can be used to climb out of the cave, but only from square [1,1].
 Sensors:
 The agent has five sensors, each of which gives a single bit of information:
 In the square containing the wumpus and in the directly (not diagonally) adjacent
squares, the agent will perceive a Stench.
 In the squares directly adjacent to a pit, the agent will perceive a Breeze.
 In the square where the gold is, the agent will perceive a Glitter.
 When an agent walks into a wall, it will perceive a Bump.
 When the wumpus is killed, it emits a woeful Scream that can be perceived
anywhere in the cave.
 The percepts will be given to the agent program in the form of a list of five
symbols; for example, if there is a stench and a breeze, but no glitter, bump, or
scream, the agent program will get
[Stench, Breeze, None, None, None].
Wumpus world
characterization
 Discrete
 Static
 single-agent.
 Sequential,
 Partially observable
Exploring a wumpus world
 Logic

 We used logical reasoning to find the gold.

 Logics are formal languages for representing information such that
conclusions can be drawn
 Syntax defines the sentences in the language
 Semantics define the "meaning" of sentences;
 i.e., define truth of each sentence w.r.t each possible world

 E.g., the language of arithmetic

 x+2 ≥ y is a sentence; x2+y > {} is not a sentence

semantics
 x+2 ≥ y is true in a world where x = 7, y = 1
 x+2 ≥ y is false in a world where x = 0, y = 6
 Entailment
 Entailment means that one thing follows from another:
KB ╞ α
 Knowledge base KB entails sentence α if and only if α
is true in all worlds where KB is true
E.g., x+y = 4 entails x+y <=4
 The formal definition of entailment is this: α |=β if and
only if, in every model in which α is true, β is also true.
Using the notation just introduced, we can write
α |= β if and only if M(α) ⊆ M(β) .
Entailment in the wumpus
world

 Consider possible models for KB assuming only

pits and a reduced Wumpus world

 Situation after detecting

nothing in [1,1], moving right, breeze in [2,1]
Wumpus models

All possible models in this reduced Wumpus world.

Wumpus models

 KB = all possible wumpus-worlds consistent with the observations of the

Wumpus world.
 Wumpus models

α1 = "[1,2] is safe", KB ╞ α1, proved by model checking

 Wumpus models

α2 = "[2,2] is safe", KB ╞ α2
 The inference algorithm is called model checking,
because it enumerates all possible models to check
that α is true in all models in which KB is true, that
is, that M(KB) ⊆ M(α).
 An inference algorithm that derives only entailed
sentences is called sound or preserving.
 It is easy to see that model checking, when it is
applicable, is a sound procedure.
 The property of completeness is also desirable: an
inference algorithm is complete if it can derive any
sentence that is entailed.
PROPOSITIONAL LOGIC:
 Complex Sentences

The proposition symbols P1, P2 etc are atomic

sentences

 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) S1 is premises,s2 is conclusion
 If S1 and S2 are sentences, S1  S2 is a sentence
(biconditional)
A sentence with several operators can be parsed
by the grammar in multiple ways.
To eliminate the ambiguity we define a
precedence for each operator. The “not”
operator (¬) has the highest precedence , which
means that in the sentence ¬A ∧ B the ¬ binds
most tightly, giving us the equivalent of (¬A)∧B
rather than ¬(A∧B).
The notation for ordinary arithmetic is the same:
−2+4 is 2, not –6.
Semantics

 The semantics defines the rules for

determining the truth of a sentence with
respect to a particular TRUTH VALUE
model.
 In propositional logic, a model simply fixes
the truth value—true or false—for every
proposition [Link] model/world
specifies true or false for each proposition
symbol
 Propositional logic: Semantics
Rules for evaluating truth with respect to a model m:
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S2 is true andS2S1 is true

Many of the rules of the wumpus world are best written using ⇔
 For example, if a neighboring square has a pit then it is sensed as breezy, and if
a square is breezy then neighboring square has a pit. So we need a
biconditional,
 B1,1⇔ (P1,2 ∨ P2,1)
Truth tables for connectives

OR: P or Q is true or both are true. Implication is always true

AND: P and Q is true if both are true. when the premises are False!
Wumpus world sentences
 Px,y is true if there is a pit in [x, y].
 Wx,y is true if there is a wumpus in [x, y], dead or
alive.
 Bx,y is true if the agent perceives a breeze in [x, y].
 Sx,y is true if the agent perceives a stench in [x, y].
R1 : ¬P1,1 .
A square is breezy if and only if there is a pit in a
neighbouring square. This has to be stated for each square;
for now, we include just the relevant squares:
R2 : B1,1 ⇔ (P1,2 ∨ P2,1) .
R3 : B2,1 ⇔ (P1,1 ∨ P2,2 ∨ P3,1) .
The preceding sentences are true in all wumpus worlds.
Now we include the breeze percepts for the first two
squares visited in the specific world the agent is in, leading
up to the situation.
R4 : ¬B1,1 .
R5 : B2,1 .
 1.A simple inference procedure(model
checking)
Our goal now is to decide whether KB |= α for some sentence α.
Our first algorithm for inference is a model-checking approach that is
a direct implementation of the definition of entailment:
Enumerate the models, and check that α is true in every model in
which KB is true.
Models are assignments of true or false to every proposition symbol.
Returning to our wumpus-world example, the relevant proposition
symbols are B1,1, B2,1, P1,1, P1,2, P2,1, P2,2, and P3,1. With seven
symbols, there are 2power 7 =128
 128 possible models; in three of these, KB is true. In
those three models, ¬P1,2 is true, hence there is no pit
in [1,2].
 On the other hand, P2,2 is true in two of the three
models and false in one, so we cannot yet tell whether
there is a pit in [2,2].
 Inference algorithm through enumeration for
propositional logic has a worst-case complexity that is
exponential in the size of the input.
 For n symbols, time complexity is O(2n)...
[Link] Theorem Proving:

 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.
 Two sentences are logically equivalent iff they
are true in same models: α ≡ ß iff α╞ β and β╞ α
Logical equivalence

You need to
know these !
 Validity
 The second concept we will need is validity. A sentence is
valid if it is true in all models.
 For example, the sentence P ∨¬P is valid. Valid sentences
are also known as tautologies—they are necessarily true.
 Because the sentence True is true in all models, every valid
sentence is logically equivalent to True.
 For any sentences α and β, α |= β if and only if the
sentence (α ⇒β) is valid.
 Hence, we can decide if α |= β by checking that (α ⇒β) is
true in every model
 Satisfiability
 The final concept we will need is satisfiability. A sentence
is satisfiable if it is true in, or satisfied by, some model.
 Satisfiability
can be checked by enumerating the possible
models until one is found that satisfies the sentence.
 Validity and satisfiability are of course connected:
α is valid iff ¬α is unsatisfiable; contrapositively,
 We also have the following useful result:
α |= β if and only if the sentence (α ∧¬β) is
unsatisfiable.
 Validity and satisfiability
A sentence is valid 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 false in all models
e.g., AA
Satisfiability is connected to inference via the following:
KB ╞ α if and only if (KB α) is unsatisfiable
(there is no model for which KB=true and  is false)
 Inference and proofs
 This section covers inference rules that can be applied
to derive a proof—a chain of conclusions that leads to
the desired goal.
 Thebest-known rule is called Modus Ponens (Latin for
mode that affirms) and is written
α⇒β, α / β
 The notation means that, whenever any sentences of the
form α⇒β and α are given, then the sentence β can be
inferred.
 Forexample, if
(WumpusAhead∧WumpusAlive) ⇒ Shoot
and (WumpusAhead∧WumpusAlive) are
given, then Shoot can be inferred.
 Another useful inference rule is And-
Elimination, which says that, from a
conjunction, any of the conjuncts can be
inferred:
α∧β/ α
R1 : ¬P1,1 .
• A square is breezy if and only if there is a pit in a
neighbouring square. This has to be stated for each
square; for now, we include just the relevant squares:
R2 : B1,1 ⇔ (P1,2 ∨ P2,1) .
R3 : B2,1 ⇔ (P1,1 ∨ P2,2 ∨ P3,1) .
The preceding sentences are true in all wumpus
worlds. Now we include the breeze percepts for the first
two squares visited in the specific world the agent is in,
leading up to the situation.
R4 : ¬B1,1 . R5 : B2,1 .
 We start with the knowledge base containing R1
through R5 and show how to prove ¬P1,2, that is,
there is no pit in [1,2]. First,
 we apply biconditional elimination to R2 to obtain
 R6 : (B1,1 ⇒ (P1,2 ∨ P2,1)) ∧ ((P1,2 ∨ P2,1) ⇒
B1,1) .
Then we apply And-Elimination to R6 to obtain
 R7 : ((P1,2 ∨ P2,1) ⇒ B1,1) .
Logical equivalence for contrapositives gives
 R8 : (¬B1,1 ⇒¬(P1,2 ∨ P2,1)) .
 Now we can apply Modus Ponens with R8
and the percept R4 (i.e., ¬B1,1), to obtain
 R9 : ¬(P1,2 ∨ P2,1) .
 Finally,we apply De Morgan’s rule, giving
the conclusion
 R10 : ¬P1,2 ∧ ¬P2,1 .
 That is, neither [1,2] nor [2,1] contains a
pit.
 We can apply any of the search algorithms to find a
sequence of steps that constitutes a proof. We just need to
define a proof problem as follows:
• INITIAL STATE: the initial knowledge base.
• ACTIONS: the set of actions consists of all the
inference rules applied to all the sentences that match the
top half of the inference rule.
• RESULT: the result of an action is to add the sentence in
the bottom half of the inference rule.
•GOAL: the goal is a state that contains the sentence we
are trying to prove.
 Thus, searching for proofs is an alternative to
enumerating models. In many practical cases,
one final property of logical systems is
monotonicity, which says that the set of
entailed sentences can only increase as
information is added to the knowledge base, it
may not always lead to required valid
conclusions.