CS 4 - Knowledge Representation - First Order Logic

BITS Pilani
Pilani Campus
Artificial Intelligence-[SESIZC444]
CS 4 -Knowledge representation &inference
BITS Pilani Dr. Vijayalakshmi Anand

Pilani Campus
DFS algorithm
 The algorithm starts at the root node

 traverses the tree “deepest node first”
 It uses last in- first-out strategy and hence it is
implemented using a stack.
BITS Pilani, Pilani Campus

Example

Depth Limited Search (DLS)
Running DFS with a predetermined depth

limit l
Completeness: No, cannot guarantee a goal

if l < d
Optimal: No
Time complexity:
Space Complexity:

Iterative Deepening Depth First
Search (IDDS)
 Run Depth Limited Search (DLS) by gradually increasing
the limit l
 First with l=1, then l=2, l=3 and so on – until goal is
found
 Its is a combination of Depth First Search + Breadth First

Search

IDDS -example

Informed search
Information about Goal state is present
Efficient algorithm than uninformed search
It is a search which tries to reduce amount of

search that must be done by making intelligent
choices for the nodes that are selected for
expansion
Find optimal solution to reach the goal state.

Informed (Heuristic) Search
Strategies
 Also called heuristic search
 In a heuristic search each state is assigned a

“heuristic value” (h-value) that the search uses in
selecting the “best” next step
1. Greedy Best First Search

2. A* Search

Greedy best first search algorithm
 It is the combination of depth-first search and

breadth-first search algorithms.
At each step of the BFS process, we select the
most promising of the nodes we have generated
so far.
It uses the heuristic function and search.

Contd..
To implement the algorithm we need two list
 ‘Open’ list that keeps track of the current

‘immediate’ nodes available for traversal
 ‘CLOSED’ list that keeps track of the nodes
already traversed.
 Best First Search is complete
 Best First Search is not optimal

Example

A* Search
 Pronounced A-star search

 Most widely used
 Evaluation function f(n) = g(n) + h(n)
• Where g(n) – the cost to reach the
node
• h(n) – the expected cost to go from
node to goal
• Hence, f(n) – estimated cost of
cheapest path through node n

A* Search Example

State-space representation
 In Search Strategies, the states are represented

as
• Atomic representation
• Treated as black box
• Many factors are ignored, e.g., gas in car,
money available for toll, etc.
 To include more factors in our state
representation, we have
• Factored Representation

Factored Representation
Each state will be represented with

 Factors
 Each factor can be a Boolean or real-
valued variable
 E.g., City Arad can now be represented
as
 {“lat”: 46.1866, “lon”: 21.3123,
“has_gas_till_next_station”: yes}

Knowledge-based Agents
Solving problems by
 Representing the knowledge in state-space
 Reasoning about the solution in logical steps

Knowledge-based Agents
 Central Component: Knowledge Base (KB)
 KB – set of sentences, not the English sentences
 Sentence
 representation of knowledge in a language called Knowledge representation
language
 Represents an axiom, when the sentence is taken as given without being derived
from other sentences
 TELL operation: Add new sentences to the knowledge base
 ASK operation: Query what is known
 Each time a knowledge-based agent is called, it does three things

 TELL – the Knowledge Base about the percepts (inputs)
 ASK – the Knowledge Base what action it should perform.
 Extensive reasoning about the outcomes of possible action and current state
 TELL – the Knowledge Base about selected action (to update) and agent executes
the action

Example: Knowledge-based
Agents
Wumpus World

Wumpus World
 Defining the task environment (PEAS)

 Performance Measure:
 +1000 for climbing out with gold,
 -1000 for falling into a pit or being eaten by Wumpus,
 -1 for each action taken and
 -10 for using an arrow
 Environment: 4x4 grid of rooms. Always starts at [1, 1]

facing right. The location of Wumpus and Gold are random.
Agent dies if entered a pit or live Wumpus.

Wumpus World
Actuators –
 Forward,
 TurnLeft by 90,
 TurnRight by 90,
 Grab – pick gold if present,
 Shoot – fire an arrow, it either hits a
wall or kills wumpus. Agent has only
one arrow.
 Climb – Used to climb out of cave, only
from [1, 1]

Wumpus World
 Sensors. The agent has five sensors

 Stench: In all adjacent (but not diagonal) squares of
Wumpus
 Breeze: In all adjacent (but not diagonal) squares of a pit
 Glitter: In the square where gold is
 Bump: If agent walks into a wall
 Scream: When Wumpus is killed, it can be perceived
everywhere
 Percept Format: [Stench?, Breeze?, Glitter?, Bump?,

Scream?]
E.g., [Stench, Breeze, None, None, None]

Wumpus World
Goal: Discover the location of Wumpus, Pits and

Gold so that the agent can navigate to Gold
without falling prey to Wumpus or Pits
This would be agent’s knowledge for transition

Requires a configuration of the environment to do
logical reasoning

Wumpus World
Symbolic Notation
A = Agent
B = Breeze
G = Glitter, Gold
OK = Safe Square
P = Pit
S = Stench
V = Visited
W = Wumpus

Wumpus World
Percept 1: [None, None, None, None, None]
Action: Forward

Wumpus World
Percept 2: [None, Breeze, None, None, None]
Action: Move to 1, 2 (the other non-visited OK state)

Wumpus World
Percept 3: [Stench, None, None, None,

None]
Action: Move to [2, 2]

Wumpus World
Logical Agents: combine the current percept with the

existing knowledge (percept history) and do logical
reasoning in identifying state information

Logic
Reasoning conducted or assessed according to

available knowledge about the domain
Syntax: Every sentence in our knowledge base

are expressed according to a syntax of the
representing language.
E.g., in Arithmetic, “x + y = 4” is a well-formed
sentence, “xy+4=“ is not

Logic – Semantics
Semantics: Meaning of sentence. They

define the truth of a sentence according to a
possible world.
E.g., in a world where x=2, y=2, “x + y =
4” is a true sentence, whereas in a world where
x=1, y=1, the same sentence is not true
In standard Logic, every sentence has to be

either True or False but cannot be in between

Logic – Model
Model: Any possible world. Not necessarily the

reality. Any combination of assignment of truth
values to sentences in our KB.
E.g., Two sentences S1 and S2 in our KB.

Possible models: m1: {S1: True, S2: True}, m2:
{S1: False, S2: True}, m3: {S1:True, S2: False},
m4: {S1:False, S2:False}
S1 is true in m1, m3  m1 satisfies S1 or m3
satisfies S1
M(S1) is set of models that satisfy S1, i.e., [m1, m3]

Logic – Entailment
Logical Reasoning: Logical entailment between

sentences, i.e., a sentence follows from
another sentence
X Y , it means that sentence X entails the

sentence Y
 In every model where X is true, Y is also true
X Y if and only if M(X) M(Y)

 Example: In Wumpus World, the agent is in [2,1]

and detected a breeze
 The agent is interested in squares [1, 2], [2, 2], [3,
1] for next move.
 Now, each square might or might not contain a pit
(total 23 = 8 possible models)
 Our KB tells us that in [1, 1] we didn’t receive a
breeze and hence [2, 1] doesn’t have a pit

Define = “There is no pit in [1, 2]”

In every model, where KB is true,
is also true
Hence, KB
M(KB) M()
Model Checking: This

enumeration of all models to
verify logical inference
(entailment) is called Model
Checking

Define = “There is no pit in

[2, 2]”
Here, is true in models

where KB is not true
Hence, KB

Sound – An inference algorithm that derives

only entailed sentences
E.g., Model Checking is a sound inference
procedure
Completeness – An inference algorithm is

complete if it can derive any sentence that is
entailed
If KB is true, any sentence derived using Sound

inference procedure is also true in real world.

Logic - Grounding
Grounding – connection between logical reasoning

and real environment in which agent exists
How do we know that KB is true in the real world?

Propositional Logic
 A simple representation language for building knowledge-

based agents
 Proposition Symbol – A symbol that stands for a proposition.
E.g., W1,3 – “Wumpus in [1,3]” is a proposition and W1,3 is
the symbol
 Proposition can be true or false
 Usually represented with uppercase letter and may contain
other letters or subscripts. E.g., P, Q, R, W1,3, North
 Two proposition symbols have fixed meaning
• True – always true proposition
• False – always false proposition

Propositional Logic – Syntax
 Syntax – Defines the language for allowable

sentences
 Atomic proposition – consist of a single
propositional symbol
 Complex proposition– Constructed from atomic
sentences using parenthesis and logical
connectives

Propositional Logic –
Connectivites
(not) – A sentence like W1,3 is the negation of W1,3 .

(and) – Used in AND combination of sentences, i.e., W1,3 P3,1 . It is
called a conjunction and its parts are called conjuncts
(or) – Used in OR combination of sentences, i.e., W1,3 P3,1 . It is called
a disjunction and its parts are called disjuncts
(implies) – A sentence such as (W1,3 P3,1) W2,2 is called an implication
(or conditional). Its premise (antecedent) is LHS and its conclusion
(consequent) is RHS
(if and only if) – A sentence like W1,3 W2,2 is a biconditional

Propositional Logic – Syntax
Operator Precedence: , , , ,
In ambiguous sentences like , resolution is
done using precedence, such that rather than

Semantics
 Semantics defines the rules for determining the

truth of a sentence w.r.t a particular model
 E.g., sentences in knowledge base are {P1, P2,
P3}, a possible model
m1 = {P1 = false, P2 = true, P3 = false}, a model
provides truth values for proposition symbols

Semantics
 Semantics must specify how to compute the truth

value of any sentence, given a model
 Compute the truth of atomic sentences and
 Compute the truth of sentences formed with five
connectives
 The truth of atomic sentences is given by the

model

Semantics
 For complex sentences, we can do
recursive evaluation using truth
table
 E.g., evaluated in m1 gives true (false

true) = true (true) = true

Propositional Logic – Example
KB
A simple KB for wumpus world.

 For each [x, y] location
 Px,y is true if there is a pit in [x, y]
 Wx,y is true if there is a wumpus in [x, y]
 Bx,y is true if agent perceives a breeze in [x, y]
 Sx,y is true if agent perceives a stench in [x, y]

Propositional Logic – Example
KB
Each sentence will be denoted as

Ri so that we can refer to them
R1 : P1,1
R2 : B1,1 (P1,2 P2,1)
R3 : B2,1 (P1,1 P2,2 P3,1 )
R4 : B1,1
R5 : B2,1

Propositional Logic (PL) –
Inference
Given our example KB, can we infer a

sentence
E.g., P1,2 entailed by our KB?

PL Inference - Model Checking
Step 1: Get relevant Propositional symbols from our

KB, B1,1, B2,1, P1,1, P1,2, P2,1, P2,2, P3,1 . With 7
symbols, we would have 27 = 128 possible models.
Step 2: Enumerate all models with combination of
truth values to propositional symbols
Step 3: In all the models, find those models where
KB is true, i.e., every sentence R1, R2, R3, R4, R5
are true
Step 4: In those models where KB is true, find if
query sentence P1,2 is true
Step 5: If query sentence P1,2 is true in all models
where KB is true, then it entails, otherwise it won’t


In three models, KB is true

P1,2 is true in all three of those
models,hence, P1,2 is entailed from
KB, i.e., P1,2 is true
There is no pit in [1, 2]
P2,2 is true in two of the three models

and false in one, so we cannot infer if
there is a pit in [2,2] based on our
simple KB

Model checking algorithm

 If KB and contain n symbols, then
there will be 2n models
 Time Complexity: O(2n)
 Space Complexity: O(n) because
enumeration is depth-first

PL Inference - Theorem
Proving
Theorem Proving – applying rules of inference
directly to sentences in our KB to prove query
sentence without consulting models
Logical Equivalence: two sentences and are

logically equivalent if they are true in the same set
of models denoted as
E.g., (P1,2 B2,1) and (B2,1 P1,2 )are logically equivalent

PL Inference - Theorem
Proving

PL Inference - Theorem Proving
Validity: A sentence is valid if it is true in all models. E.g., P1,2
P1,2 is always true
Deduction Theorem: For any sentences and , if and only if
the sentence is valid
If we prove is equivalent to True, then entailment is proved
Satisfiability: A sentence is satisfiable if it is true in some

model. E.g., our simple KB is satisfied only by three models
Unsatisfiable: If a sentence is false in all models. E.g., P1,2 P1,2
is always false

PL Inference – Theorem
Proving
 For any sentences and , if and only if the

sentence is unsatisfiable
 This is Proof by Refutation or Proof by
Contradiction

Proving
Inference Rules
Modus Ponens (Latin for Mode that affirms) :
Whenever any sentence of the form () and are
given, then can be inferred
E.g., ((WumpusAhead WumpusAlive) Shoot
If (WumpusAhead WumpusAlive) is given, then
Shoot can be inferred

Proving
Inference Rules
And-Elimination: Given a conjecture, any of
the conjuncts can be inferred: or
E.g., If (WumpusAhead WumpusAlive) is
given, then WumpusAhead can be inferred

Proving
Inference Rules
All Logical Equivalence
rules can be used as
inference rules

Proving
Example: Given our simple KB of Wumpus World

R1 : P1,1
R2 : B1,1 (P1,2 P2,1)
R3 : B2,1 (P1,1 P2,2 P3,1 )
R4 : B1,1
R5 : B2,1
Query: P1,2 . Can we prove if this sentence be

entailed from KB using inference rules?

Proving
• R2 : B1,1 (P1,2 P2,1)

• Apply Biconditional Elimination
• R6 : (B1,1 (P1,2 P2,1)) ((P1,2 P2,1) B1,1)
• 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))
• Apply Modus Ponens with R8 and R4 to obtain
• R9 : (P1,2 P2,1)
• Finally, using De Morgan’s rule
• R10 : P1,2 P2,1
Proving
 This proof can be efficiently computed using
search algorithms we discussed earlier. We need
to define the proof problem as
 Initial State: the initial knowledge base

 Actions: all inference rules that could match the
sentences with the top half of inference rule
 Result: the bottom half of inference rule
 Goal: The state containing the query sentence
 In many practical cases, searching a proof can be

more efficient because the proof can ignore
irrelevant propositions

example

solution

Exercise
Solving a murder case

Limitations of Propositional
Logic
Less expressive
Proposition is a declarative that either true
or false not both
All and some cannot be represented using
propositional logic

Complexity of Representation
What my actions do?
Search Strategies Propositional Logic First Order Logic

Structured Representation
Has three elements

 Objects – entities that can be represented as individual
states. E.g., people, houses, numbers, etc.
 Relations – they can be unary relations or properties of
objects such as adjectives, red, round, multistoried, etc.
They can be n-ary relations between objects such as
brother of, bigger than, inside, part of, etc.
 Functions – these are relations where there is only one
value for a given input. E.g., father of, best friend, king of.
The output of a function is always an object.

Structured Representation
 Squares neighboring the wumpus are smelly

• Objects: squares, wumpus
• Unary Relation (properties of an object): smelly
• N-ary Relation (between objects): neighboring
• Function: -
 One plus two equals three

• Objects: One, two, three, one plus two
• Unary Relation (properties of an object): -
• N-ary Relation (between objects): equals
• Function: plus (“plus” when applied to objects “one”
and two” gave another object “one plus two”)

First Order Logic
 First-order logic is another way of knowledge

representation in artificial intelligence.
 Its Syntax and Semantics are built around
Objects, Relations and Functions
 Primary difference between propositional and
first-order logic lies in “ontological commitment”
– the assumption about the nature of reality.

First Order Logic – Example
Domain – Domain of a model is the set of objects or

domain elements it contains.
Objects: Richard the Lionheart, Evil King John, Richard’s

left leg, John’s left leg, Crown
Relation: A set of tuples of objects that are related
E.g., Brotherhood: {<Richard, John>, <John,
Richard>}
OnHead: { <crown, John>}
These are binary relations, relate two objects
Unary relations: “Person”, “King” properties, “King” is
True for John but False for Richard
Function: A relation where a given object is related to
exactly one object
E.g., LeftLeg(Richard) => Richard’s left leg
LeftLeg(John) => John’s left leg

First Order Logic – Syntax
Symbols: Basic syntactic elements

• Constant Symbols: represent objects
• Predicate Symbols: represent relations
• Function Symbols: stand for functions
All begin with uppercase, E.g., Brother, OnHead,Person,King,
Crown, Left Leg
• Connectives : (, , , , )
• Equality :=
• Quantifiers: , ()

Atomic Sentence:
 Formed by a predicate symbol optionally
followed by a parenthesized list of terms.
E.g., Brother(Richard, John) – which means that
Richard is the brother of John.
 Atomic sentences can have complex terms as
arguments.
E.g., Married(Father(Richard), Mother(John))
 Atomic sentence is true if the Predicate relation
holds between the objects in the arguments

Complex Sentences –
 use Logical connectives (, , , , to
construct complex sentences
Brother(LeftLeg(Richard), John)
Brother(Richard, John)Brother(John, Richard)
King(Richard) King(John)
King(Richard) King(John)

Quantifiers – to represent a collection of objects

in a single sentence
Two standard quantifiers
1. Universal quantification (): A fact to apply for all
objects. E.g., ”All Kings are persons”, “Squares
neighboring the wumpus are smelly” written as

Universal quantification ()
x – refers to an object, can take values as

x  [“Richard the Lionheart”, “King John”, “Richard’s left leg”, “John’s left
leg”, “the crown”]
The above universal quantified sentence is equivalent to

Richard the Lionheart is a king Richard the Lionheart is a person
King John is a king King John is a person
Richard’s left leg is a king Richard’s left leg is a person
John’s left leg is a king John’s left leg is a person
The crown is a king The crown is a person
- True for King John
- While using universal quantifier (), (implies) is preferred

Existential Quantification () – statement about some of the objects

without naming it. E.g., “King John has a crown on his head” can be
written as
Richard the Lionheart is a crown Richard the Lionheart is on John’s

head
King John is a crown King John is on John’s head
Richard’s Left Leg is a crown Richard’s Left Leg is on John’s head
John’s Left Leg is a crown John’s Left Leg is on John’s head
The crown is a crown The crown is on John’s head
- True for last statement and hence existential is satisfied

- While using existential quantifier (), (and) is preferred

Nested quantifiers – can use multiple quantifiers to

express complex sentences
means “Brothers are siblings”
Consecutive quantifiers of same type can be written as one
quantifier

Mixtures of quantifiers, “Everybody loves somebody”

meaning for every person there is someone that person
loves
If you reverse the order of quantifiers

which means “There is someone who is loved by
everyone”
Order of quantifiers is important

Equality – signify two terms refer to the same

object
E.g., Father(John) = Henry
The equality symbol can be used to state facts

about a function.
E.g., to say Richard has atleast two brother

First Order Logic – Knowledge
Base Usage
First order knowledge base can be interacted with three interfaces
TELL – Sentences that need to be added to the knowledge base.
Such sentences are assertions.
E.g., TELL(KB, King(John))
TELL(KB, Person(Richard))
TELL(KB,
ASK – Ask questions about the Knowledge base. Questions asked
with ASK are called queries or goals. It would give a Boolean
result.
ASK(KB, Person(John)) , results in True
ASKVARS – Ask questions with variables to extract. It yields a
stream of answers
ASKVARS(KB, Person(x)) , gives two answers {x/John} and
{x/Richard}
Such an answer is called substitution or binding list

First Order Logic – Inference
First order logic has sentences with quantifiers

which makes it hard for inference
First order inference can be done by
reducing the knowledge base to propositional
logic and
use propositional inference techniques

First Order Logic - Inference
Inference rules for quantifiers

Universal Instantiation (UI) – we can infer any sentence
obtained by substituting the ground term (a term without
variable) for the variable.
SUBST will replace variable v in sentence with all ground
terms g
will be converted to below variants and then inferred
Richard the Lionheart is a king Richard the Lionheart is a
person
King John is a king King John is a person
.
.

First Order Logic - Inference
Existential Instantiation – variable is replace by

a single new constant
E.g.,
We will infer the sentence - Crown(C1)
OnHead(C1, John)
C1 does not appear in KB

Example

Contd..

Thank you

CS 4 - Knowledge Representation - First Order Logic

Uploaded by

Copyright:

Available Formats

CS 4 - Knowledge Representation - First Order Logic

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

CS 4 - Knowledge Representation - First Order Logic

Uploaded by

Copyright:

Available Formats

BITS Pilani

BITS Pilani Dr. Vijayalakshmi Anand

 The algorithm starts at the root node

BITS Pilani, Pilani Campus

BITS Pilani, Pilani Campus

Running DFS with a predetermined depth

Completeness: No, cannot guarantee a goal

BITS Pilani, Pilani Campus

 Its is a combination of Depth First Search + Breadth First

BITS Pilani, Pilani Campus

BITS Pilani, Pilani Campus

Information about Goal state is present

Efficient algorithm than uninformed search

It is a search which tries to reduce amount of

Find optimal solution to reach the goal state.

BITS Pilani, Pilani Campus

 Also called heuristic search

 In a heuristic search each state is assigned a

1. Greedy Best First Search

BITS Pilani, Pilani Campus

 It is the combination of depth-first search and

BITS Pilani, Pilani Campus

To implement the algorithm we need two list

 ‘Open’ list that keeps track of the current

BITS Pilani, Pilani Campus

BITS Pilani, Pilani Campus

 Pronounced A-star search

BITS Pilani, Pilani Campus

BITS Pilani, Pilani Campus

 In Search Strategies, the states are represented

BITS Pilani, Pilani Campus

Each state will be represented with

BITS Pilani, Pilani Campus

BITS Pilani, Pilani Campus

 KB – set of sentences, not the English sentences

 Each time a knowledge-based agent is called, it does three things

BITS Pilani, Pilani Campus

BITS Pilani, Pilani Campus

 Defining the task environment (PEAS)

 Environment: 4x4 grid of rooms. Always starts at [1, 1]

BITS Pilani, Pilani Campus

BITS Pilani, Pilani Campus

 Sensors. The agent has five sensors

 Percept Format: [Stench?, Breeze?, Glitter?, Bump?,

BITS Pilani, Pilani Campus

Goal: Discover the location of Wumpus, Pits and

This would be agent’s knowledge for transition

BITS Pilani, Pilani Campus

BITS Pilani, Pilani Campus

Percept 1: [None, None, None, None, None]

BITS Pilani, Pilani Campus

Percept 2: [None, Breeze, None, None, None]

Action: Move to 1, 2 (the other non-visited OK state)

BITS Pilani, Pilani Campus

Percept 3: [Stench, None, None, None,

Action: Move to [2, 2]

BITS Pilani, Pilani Campus

Logical Agents: combine the current percept with the

BITS Pilani, Pilani Campus