Artificial Intelligence

UNIT IV
Knowledge

Prepared By
Mrs. Jayshri Dhere
Assistant Professor
Artificial Intelligence and Data Science
DYPIEMR, Pune
 Syllabus
• Logical Agents,
• Knowledge-Based Agents,
• The Wumpus World,
• Logic,
• Propositional Logic: A Very Simple Logic,
• Propositional Theorem Proving,
• Effective Propositional Model Checking,
• Agents Based on Propositional Logic,
• First-Order Logic,
• Representation Revisited,
• Syntax and Semantics of First-Order Logic,
• Using First-Order Logic,
• Knowledge Engineering in First-Order Logic.
2
Logical Agents

3
 Knowledge-Based Agents
• Intelligent agents need knowledge about the
world in order to reach good decisions.
• Knowledge is contained in agents in the form
of sentences in a knowledge representation
language that are stored in a knowledge base.
• A knowledge-based agent is composed of a
knowledge base and an inference mechanism.
• It operates by storing sentences about the
world in its knowledge base, using the
inference mechanism to infer new sentences,
and using these sentences to decide what
action to take.
 Knowledge-Based Agents
• An intelligent agent needs knowledge about the real
world for taking decisions and reasoning to act
efficiently.
• Knowledge based agents are those agents who have
the capability of maintaining an internal state of
knowledge after observations and take actions.
• These agents can represent the world with some
formal representation and act intelligently.
• Knowledge-based agents are composed of two main
parts:
o Knowledge-base and
o Inference system
 Knowledge-Based Agents
• A Knowledge-Based Agents must be able to do the
following:
• An agent should be able to represents states,
actions etc.
• An agent should be able to incorporate new
percepts
• An agent can update the internal representation
of the world
• An agent can deduce the internal representation
of the world
• An agent can deduce appropriate actions.
Knowledge-Based Agents
Knowledge-Based Agents

9
The Wumpus World

10
 The Wumpus World
PEAS description:
• Performance measure:

By Mrs. Priyadarshani Doke, AI&DS, DYPIEMR,

• +1000 for climbing out of the
cave with the gold,
• –1000 for falling into a pit or
being eaten by the wumpus,

Pune
• –1 for each action taken and
• –10 for using up the arrow.
• The game ends either when the
agent dies or when the agent
climbs out of the cave. 11
 The Wumpus World
PEAS description:
Environment:
• A 4×4 grid of rooms.
• The agent always starts in the
square labeled [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, with
probability 0.2. 12
 PEAS description: The Wumpus World
Actuators: (Left turn, Right turn,Grab, Release, Move
orward ,Shoot.)
1. The agent can move Forward, TurnLeft by 90◦, or
TurnRight by 90◦.
2. The agent dies a miserable death if it enters a
square containing a pit or a live wumpus. (It is safe,
albeit smelly, to enter a square with a dead
wumpus.)
3. 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.
4. The action Shoot can be used to fire an arrow in a
straight line in the direction the agent is facing.
5. The arrow continues until it either hits (and hence
kills) the wumpus or hits a wall.
6. The agent has only one arrow, so only the first
Shoot action has any effect. 13
7. Finally, the action Climb can be used to climb out of
the cave, but only from square [1,1].
PEAS description:
The Wumpus World
Sensors:

• In the square containing the wumpus and in the

directly (not diagonally) adjacent squares, the
agent will perceive a Stench.

By Mrs. Priyadarshani Doke, AI&DS, DYPIEMR,

• In the squares directly adjacent to a pit, the agent
will perceive a Breeze.

• In the square where the gold is, the agent will

Pune
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 14

cave.
 The Wumpus world Properties:
• Partially observable: The Wumpus world is partially observable because the

agent can only perceive the close environment such as an adjacent room.

• Deterministic: It is deterministic, as the result and outcome of the world are

already known.

• Sequential: The order is important, so it is sequential.

• Static: It is static as Wumpus and Pits are not moving.

• Discrete: The environment is discrete.

• One agent: The environment is a single agent as we have one agent only and

Wumpus is not considered as an agent. 15

 Agent's First step:
• Initially, the agent is in the first room or on the
square [1,1], and we already know that this room
is safe for the agent, so to represent on the below
diagram (a) that room is safe we will add symbol
OK. Symbol A is used to represent agent, symbol B
for the breeze, G for Glitter or gold, V for the
visited room, P for pits, W for Wumpus.
• At Room [1,1] agent does not feel any breeze or
any Stench which means the adjacent squares are
also OK 16
The Wumpus World

17
 Agent's second Step:
• Now agent needs to move forward, so it will either
move to [1, 2], or [2,1]. Let's suppose agent moves to
the room [2, 1], at this room agent perceives some
breeze which means Pit is around this room. The pit
can be in [3, 1], or [2,2], so we will add symbol P? to
say that, is this Pit room?
• Now agent will stop and think and will not make any
harmful move. The agent will go back to the [1, 1]
room. The room [1,1], and [2,1] are visited by the
agent, so we will use symbol V to represent the visited
squares.
18
The Wumpus World

19
 Agent's third step:
• At the third step, now agent will move to the room [1,2] which is
OK. In the room [1,2] agent perceives a stench which means there
must be a Wumpus nearby. But Wumpus cannot be in the room
[1,1] as by rules of the game, and also not in [2,2] (Agent had not
detected any stench when he was at [2,1]). Therefore agent infers
that Wumpus is in the room [1,3], and in current state, there is no
breeze which means in [2,2] there is no Pit and no Wumpus. So it
is safe, and we will mark it OK, and the agent moves further in
[2,2].

20
 Agent's fourth step:
• At room [2,2], here no stench and no breezes present so let's
suppose agent decides to move to [2,3]. At room [2,3] agent
perceives glitter, so it should grab the gold and climb out of
the cave.

21
 Logic
• Knowledge bases consist of sentences.

• These sentences are expressed according to the syntax of the representation language,

which specifies all the sentences that are well formed.

• The notion of syntax is clear enough in ordinary arithmetic: “x +y =4”is a well-formed

sentence, whereas “x4y+=” is not.

• A logic must also define the semantics or meaning of sentences. The semantics defines

the truth of each sentence with respect to each possible world. For example, the

semantics for arithmetic specifies that the sentence “x + y =4” is true in a world where x is

2 and y is 2, but false in a world where x is 1 and y is 1. In standard logics, every sentence

must be either true or false in each possible world—there is no “in between.”1.

• More precisely , we use the term “Model” in place of “possible world.”

•
Logic
Logics are formal languages for representing information such that conclusions
can be drawn
• Syntax defines the sentences in the language(well formed)
• Semantics define the "meaning" of sentences;
• i.e., define truth of a sentence in a world
• E.g., the language of arithmetic
• x+2 ≥ y is a sentence; x2+y > {} is not a sentence
• x+2 ≥ y is true if the number x+2 is not less than the number y
• 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
• The relationship of entailment between sentences is crucial to our
understanding of reasoning.
• A sentence α entails another sentence β if β is true in all worlds where α is true.
• Equivalent definitions include the validity of the sentence α ⇒ β and
• The unsatisfiability of the sentence α ∧ ￢β.
• Logical Representation:

1. Propositional Logic
2. First Order Predicate Logic
 Propositional logic
• Propositional logic cannot predicate, it can say
either true or false.

• Logical constants: true, false

• Propositional symbols: P, Q, S, ... (atomic
sentences)
• Wrapping parentheses: ( … )
• Sentences are combined by connectives:
∧ ...and [conjunction]
∨ ...or [disjunction]
⇒...implies [implication / conditional]
⇔..is equivalent [biconditional]
¬ ...not [negation]
• Literal: atomic sentence or negated atomic
sentence
Examples of Propositional logic
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”
 Propositional logic
• Propositional logic is a simple language
consisting of proposition symbols and logical
connectives.

• It can handle proposition that are known true,

known false, or completely unknown.

• Can be either true or false, but not both.

 Sentence or Well Defined Formula
• A sentence is defined as:
• Each propositional symbol/variable(A,B) is a
sentence.
• Each logical constant (either true or false) is
sentence.
• If A and B are sentences, all of the following are
also sentences.
 Some Examples of Proposition
• Delhi is the capital of India.

• Mumbai is the capital of India.

• 2+2=5

• We can represent these sentences in

Propositional logic.
A Backus normal form (BNF) grammar
of sentences in propositional logic
S := <Sentence> ;
<Sentence> := <AtomicSentence> | <ComplexSentence> ;
<AtomicSentence> := "TRUE" | "FALSE" |
"P" | "Q" | "S" ;
<ComplexSentence> := "(" <Sentence> ")" |
<Sentence> <Connective> <Sentence> |
"NOT" <Sentence> ;
<Connective> := "NOT" | "AND" | "OR" | "IMPLIES" |
"EQUIVALENT" ;
 Propositional Logic Examples
• The statement “the street is wet” is
proposition, as “it is raining”.
• These two propositional can be connected to
form new proposition
If It is raining the street is wet.
Written more formally.
Propositional Logic
Truth tables
 Truth tables

A complex sentence:
Models of complex sentences
 Propositional Logic Examples
1. It is Cold and Dark.

A: It is Cold
B: It is Dark
A B
 Propositional Logic Examples
1. I am breathing if and if I am alive.

A: I am breathing
B: I am alive
A B
 Propositional Logic Examples
1. If I study hard then I get rich.
• Whenever I study hard, I get rich.
• That I study hard implies I get rich.
• I get rich, if I study hard

A: I study hard
B: I get rich
A B
 Propositional Logic Examples
1. Cat chases mice or bird.

A: Cat chases mice

B: Cat chases bird
A B
 Propositional Logic Examples
1. Logic is not easy.

A: Logic is easy.

A
 Propositional Logic Examples
• A -- It is hot
• B-- It is humid
• C-- It is raining

• Conditions:
• If it is humid then it is hot
B A

• If it is hot and humid then it is not raining

• AB C
 Limitation of Propositional Logic
• We can not represent relations like:
All, Some of, None With Propositional Logic.
a. All girls are intelligent
b. Some apples are sweet
Above statements are not declarative statements.
Propositional logic has limited expressive power.
In PL, we can not describe statements, in terms of
their properties of logical relationship.
 Inference rules
• Inference rules are the templates for generating valid arguments.
Inference rules are applied to derive proofs in artificial intelligence, and
the proof is a sequence of the conclusion that leads to the desired goal.

• Logical inference is used to create new sentences that logically follow

from a given set of predicate calculus sentences (KB).

• An inference rule is sound if every sentence X produced by an inference

rule operating on a KB logically follows from the KB. (That is, the
inference rule does not create any contradictions)

• An inference rule is complete if it is able to produce every expression

that logically follows from (is entailed by) the KB. (Note the analogy to
complete search algorithms.)
In inference rules, the implication among all the
connectives plays an important role.
Following are some terminologies related to inference
rules:
Implication: It is one of the logical connectives which can be represented as
P → Q. It is a Boolean expression.

Converse: The converse of implication, which means the right-hand side

proposition goes to the left-hand side and vice-versa. It can be written as Q → P.

Contrapositive: The negation of converse is termed as contrapositive, and it can

be represented as ¬ Q → ¬ P.
Inverse: The negation of implication is called inverse. It can be represented as
¬ P → ¬ Q.

From the above term some of the compound statements are equivalent to each
other, which we can prove using truth table:
 Sound rules of inference
• Here are some examples of sound rules of inference
• A rule is sound if its conclusion is true whenever the
premise is true
• Each can be shown to be sound using a truth table
RULE PREMISE CONCLUSION
Modus Ponens A, A → B B
And Introduction A, B A∧B
And Elimination A ∧ B A
Double Negation ¬¬A A
Unit Resolution A ∨ B, ¬B A
Resolution A ∨ B, ¬B ∨ C A∨C
 1. Modus Ponens:
• The Modus Ponens rule is one of the most important rules of inference,
and it states that if P and P → Q is true, then we can infer that Q will be
true. It can be represented as:

• Example:
• Statement-1: "If I am sleepy then I go to bed" ==> P→ Q
Statement-2: “ I am sleepy" ==> P
Conclusion: "I go to bed." ==> Q.
Hence, we can say that, if P→ Q is true and P is true then Q will be true.
 2. Modus Tollens:
• The Modus Tollens rule state that if P→ Q is true and ¬
Q is true, then ¬ P will also true. It can be represented
as:

• Statement-1: "If I am sleepy then I go to bed" ==> P→

Q
Statement-2: "I do not go to the bed."==> ~Q
Statement-3: Which infers that "I am not sleepy" => ~P
Proof by Truth table:
 3. Hypothetical Syllogism:
• The Hypothetical Syllogism rule state that if
P→R is true whenever P→Q is true, and Q→R is
true. It can be represented as the following
notation:
• Example:
• Statement-1: If you have my home key then you
can unlock my home. P→Q
Statement-2: If you can unlock my home then
you can take my money. Q→R
Conclusion: If you have my home key then you
can take my money. P→R
Proof by Truth table:
 4. Disjunctive Syllogism:

• The Disjunctive syllogism rule state that if P∨Q is true,

and ¬P is true, then Q will be true. It can be represented
as:

• Example:
• Statement-1: Today is Sunday or Monday. ==>P∨Q
Statement-2: Today is not Sunday. ==> ¬P
Conclusion: Today is Monday. ==> Q
Proof by Truth table:
 5. Addition:
• The Addition rule is one the common inference
rule, and it states that If P is true, then P∨Q will
be true.

• Example:
• Statement: I have a vanilla ice-cream. ==> P
Statement-2: I have Chocolate ice-cream.
Conclusion: I have vanilla or chocolate ice-cream.
==> (P∨Q)
Proof by Truth table:
 6. Simplification:
• The simplification rule state that if P∧ Q is true,
then Q or P will also be true. It can be represented as:
 7. Resolution:
• The Resolution rule state that if P∨Q and ¬ P∧R is
true, then Q∨R will also be true. It can be
represented as
 Proving things
• A proof is a sequence of sentences, where each
sentence is either a premise or a sentence derived from
earlier sentences in the proof by one of the rules of
inference.
• The last sentence is the theorem (also called goal or
query) that we want to prove.
• Example for the “weather problem” given above.
1 Humid Premise “It is humid”

2 Humid→Hot Premise “If it is humid, it is hot”

3 Hot Modus Ponens(1,2) “It is hot”

4 (Hot∧Humid)→Rain Premise “If it’s hot & humid, it’s raining”

5 Hot∧Humid And Introduction(1,2) “It is hot and humid”

6 Rain Modus Ponens(4,5) “It is raining”

Horn sentences
Horn clause is clause (a disjunction of literals) with
at most one positive, i.e. unnegated, literal. A clause
with at most one positive (unnegated) literal is called
a Horn Clause.

• A Horn sentence or Horn clause has the form:

P1 ∧ P2 ∧ P3 ... ∧ Pn → Q (P → Q) = (¬P ∨ Q)
or alternatively
¬P1 ∨ ¬ P2 ∨ ¬ P3 ... ∨ ¬ Pn ∨ Q
Where It has only one positive literal Q.
• To get a proof for Horn sentences, apply Modus
Ponens repeatedly until nothing can be done
Propositional logic is a weak language
• Hard to identify “individuals” (e.g., Mary, 3)
• Can’t directly talk about properties of individuals
or relations between individuals (e.g., “Bill is tall”)
• Generalizations, patterns, regularities can’t easily
be represented (e.g., “all triangles have 3 sides”)
• First-Order Logic (abbreviated FOL or FOPC) is
expressive enough to concisely represent this
kind of information
FOL adds relations, variables, and quantifiers, e.g.,
•“Every elephant is gray”: ∀ x (elephant(x) → gray(x))
•“There is a white alligator”: ∃ x (alligator(X) ^ white(X))
Example
• Consider the problem of representing the
following information:
• Every person is mortal.
• Newton is a person.
• Newton is mortal.

• How can these sentences be represented so

that we can infer the third sentence from the
first two?
Example
• In PL we have to create propositional symbols to stand for all
or part of each sentence. For example, we might have:
P = “person”; Q = “mortal”; R = “Newton ”
• so the above 3 sentences are represented as:
P → Q; R → P; R → Q
• Although the third sentence is entailed by the first two, we
needed an explicit symbol, R, to represent an individual,
Newton , who is a member of the classes “person” and
“mortal”
• To represent other individuals we must introduce separate
symbols for each one, with some way to represent the fact
that all individuals who are “people” are also “mortal”
 Forward chaining
• It is a form of reasoning which starts with atomic sentence
with knowledge base and applies inference rules in the
forward direction to extract more data until a goal is
reached.
• It is the process of making a conclusion based on known
facts of data by starting from initial state and reach the goal
node.
• It is also called as data driven.
• It is a bottom up approach.
 Backward chaining
• It is a form of reasoning which starts with goal and
works backward chaining through rules to find
known facts support the goal.

• A goal is broken into sub goal and sub goal to prove

the fact is true.

• It is also called as goal driven.

• It is a bottom up approach.
 Summary
• The process of deriving new sentences from old one is called inference.
• Sound inference processes derives true conclusions given true premises
• Complete inference processes derive all true conclusions from a set of premises
• A valid sentence is true in all worlds under all interpretations
• If an implication sentence can be shown to be valid, then—given its premise—its
consequent can be derived
• Different logics make different commitments about what the world is made of and
what kind of beliefs we can have regarding the facts
• Logics are useful for the commitments they do not make because lack of commitment
gives the knowledge base engineer more freedom
• Propositional logic commits only to the existence of facts that may or may not be
the case in the world being represented
• It has a simple syntax and simple semantics. It suffices to illustrate the process of
inference
• Propositional logic quickly becomes impractical, even for very small worlds
First-Order Logic
Outline
• First-order logic
• Properties, relations, functions, quantifiers, …
• Terms, sentences, axioms, theories, proofs, …
• Extensions to first-order logic
• Logical agents
• Reflex agents
• Representing change: situation calculus, frame
problem
• Preferences on actions
• Goal-based agents
 First-order logic
• First-order logic is another way of knowledge
representation in AI.

• First-order logic is also know as Predicate logic or

First-order Predicate logic.

• Propositional logic assumes the world contains

facts.

• First-order logic assumes the world contains

Objects, relations and function relations.
 First-order logic
• First-order logic (FOL) models the world in terms of
• Objects, which are things with individual identities
• Properties of objects that distinguish them from other objects
• Relations that hold among sets of objects
• Functions, which are a subset of relations where there is only
one “value” for any given “input”
• Examples:
• Objects: Students, lectures, companies, cars ...
• Relations: Brother-of, bigger-than, outside, part-of, has-color,
occurs-after, owns, visits, precedes, ...
• Properties: blue, oval, even, large, ...
• Functions: father-of(), best-friend(), third inning of ()…
 First-order logic
• First-order logic is a powerful language that develops
information about the objects in a world easy way and can
also express the relationship between those objects.

In short,

❑ First-order logic is a logical system for reasoning about

properties of objects.
❑ Augments the logical connectives from propositional logic
with predicates that describe properties of objects,
❑ functions that map objects to one another, and
❑ quantifiers that allow us to reason about multiple objects.
 User provides
• Constant symbols, which represent individuals in the world
• Mary
• 3
• Green
• Function symbols, which map individuals to individuals
• father-of(Mary) = John
• color-of(Sky) = Blue
• Predicate symbols, which map individuals to truth values
• greater(5,3)
• green(Grass)
• color(Grass, Green)
 First-order logic ..
• Variable symbols
• E.g., x, y

• Connectives
• Same as in PL:
not (¬),
and (∧),
or (∨),
implies (→),
if and only if (biconditional ↔)

• Quantifiers
• Universal ∀x or (Ax)
• Existential ∃x or (Ex)
 First-order logic
• First-order logic also has two main parts:
– Syntax
– Semantics
• Syntax of First-Order logic:
• The syntax of FOL determines which collection
of symbols is a logical expression in first-order
logic. The basic syntactic elements of
first-order logic are symbols. We write
statements in short-hand notation in FOL.
 Basic Elements of First-order logic:

• Following are the basic elements of FOL

syntax:
 Sentences are built from terms and
atoms
• A term (denoting a real-world individual) is a constant symbol, a
variable symbol, or an n-place function of n terms.

x and f(x1, ..., xn) are terms, where each xi is a term.

A term with no variables is a ground term

• An atomic sentence (which has value true or false) is an n-place

predicate of n terms. An atomic sentence is an atomic formula
containing no variables.

• It follows that an atomic sentence contains no logical connectives,

variables, or quantifiers.
• let F, G, H be predicate letters;
• let a, b, c be individual constants;
• let x, y, z be variables.

Atomic sentences
An atomic sentence is a simple declarative sentence which can either be true or
false.
We write atomic sentences in the blocks language by combining a predicate (which
always begins with a capital letter), followed by (in parentheses) one or more
individual constants (which always begin with a lower case letter).
Ex:- Cube(a), Larger(b,c)
These well formed formulas are atomic sentences; they contain no free variables or
conjunctions:
• F(a)
• G(a, b)
• H(a, b, c)
 Atomic formula
An atomic formula or atom is simply a predicate applied to a tuple
of terms; that is, an atomic formula is a formula of the
form P (t1 ,…, tn) for P a predicate, and the tn terms.
These wffs are atomic formulae, but are not sentences (atomic or
otherwise) because they include free variables:
• F(x)
• G(a, z)
• H(x, y, z)
Formulas are built from atomic formulas using logical connectives
and quantifiers.
Every atomic formula is a formula.
If A and B are formulas and x is a variable then (A), ¬A, A ∧ B, A
∨ B, A⇒ B, (∀x)A, and (∃x)A are formulas.
 Complex sentences
• Complex sentences are made by combining
atomic sentences using connectives.
• First-order logic statements can be divided into
two parts:
• Subject: Subject is the main part of the
statement.
• Predicate: A predicate can be defined as a
relation, which binds two atoms together in a
statement.
• Consider the statement: "x is an integer.", it
consists of two parts, the first part x is the
subject of the statement and second part "is
an integer," is known as a predicate.
 Sentences are built from terms and atoms (Cont…)

• A complex sentence is formed from atomic sentences

connected by the logical connectives:
¬P, P∨Q, P∧Q, P→Q, P↔Q where P and Q are sentences

• A quantified sentence adds quantifiers ∀ and ∃

• A well-formed formula (wff) is a sentence containing

no “free” variables. That is, all variables are “bound” by
universal or existential quantifiers.
(∀x)P(x,y) has x bound as a universally quantified variable,
but y is free.
Quantifiers

A quantifier is a language element which generates quantification.

These are the symbols that permit to determine of identity the range and Scope of
the variable in the logic expression.

• Universal quantification

• Existential quantification
Quantifiers
Universal quantification (for all, Everyone, Everything)

• It is a symbol of logical representation, which specifies that the statement

within its range is true for everything of every instance of a particular
thing.

• It is represented by a symbol ∀.

• If x is a variable the ∀x is read as:

– For all x

– For each x within range

– For every x
Quantifiers
Existential quantification

• It is a type of quantifier, which express that the statement within its scope
is true for at least one instance of something .

• It is denoted by, ∃.

• ( The Existential quantifier we always use AND conjunction symbol.)

• If x is a variable, then existential quantifier will be ∃(x) is read as

– There exist x

– For some x

– For at least x
Quantifiers
Universal quantification

• (∀x)P(x) means that P holds for all values of x in the domain associated with
that variable

• E.g., (∀x) dolphin(x) → mammal(x)

• Existential quantification

• (∃ x)P(x) means that P holds for some value of x in the domain associated
with that variable

• E.g., (∃ x) mammal(x) ∧ lays-eggs(x)

• Permits one to make a statement about some object without naming it

 Quantifiers
• Universal quantifiers are often used with “implies” to form “rules”:
(∀x) student(x) → smart(x) means “All students are smart”

• Universal quantification is rarely used to make blanket statements about every

individual in the world:
(∀x)student(x)∧smart(x) means “Everyone in the world is a student and is
smart”

• Existential quantifiers are usually used with “and” to specify a list of properties
about an individual:
(∃x) student(x) ∧ smart(x) means “There is a student who is smart”

• A common mistake is to represent this English sentence as the FOL sentence:

(∃x) student(x) → smart(x)

• Q. But what happens when there is a person who is not a student?

1. All birds fly.
predicate is fly(bird)
∀x bird(x) → fly(x)
2. Every man respect his parent
predicate is “respect (x,y) where x=man
y=parent
∀x man(x) →respect(x,parent)
Or
∀x man(x) →respect(x,y)
2 .All man drinks coffee.
3. Some boys are intelligent.
2. All man drinks coffee.
4. Some boys play cricket.
Predicate is "play(x, y),"
where x= boys, and y= game.
Since there are some boys so we will use ∃, and
it will be represented as:
∃x boys(x) → play(x, cricket).
5. Not all students like both Mathematics and
Science.
In this ,
the predicate is "like(x, y),"
where x= student, and y= subject.
Since there are not all students, so we will use ∀
with negation, so
following representation for this:
¬∀ (x) [ student(x) → like(x, Mathematics) ∧ like(x, Science)].
Quantifier Scope
• Switching the order of universal quantifiers does
not change the meaning:
• (∀x)(∀y) P(x,y) ↔ (∀y)(∀x) P(x,y)

• Similarly, you can switch the order of existential

quantifiers:
• (∃x)(∃y)P(x,y) ↔ (∃y)(∃x) P(x,y)

• Switching the order of universals and existentials

does change meaning:
• Everyone likes someone: (∀x)(∃y) likes(x,y)
• Someone is liked by everyone: (∃y)(∀x) likes(x,y)
Connections between All and Exists

The two quantifiers are actually intimately connected with each other, through
negation. As serting that everyone dislikes parsnips is the same as asserting
there does not exist someone who likes them, and vice versa:
Eg.
“Everyone likes ice cream” means that there is no one who does not like ice
cream:
∀x Likes(x, IceCream) is equivalent to ¬∃x ¬Likes (x, IceCream) .
Because ∀ is really a conjunction over the universe of objects and ∃ is a
disjunction, it should not be surprising that they obey De Morgan’s rules. The
De Morgan rules for quantified and unquantified sentences are as follows:

(∀x) ¬P(x) ↔ ¬(∃x) P(x)

¬(∀x) P(x) ↔ (∃x) ¬P(x)
(∀x) P(x) ↔ ¬ (∃x) ¬P(x)
(∃x) P(x) ↔ ¬(∀x) ¬P(x)
• “Students who pass the course either do the
homework or attend lecture;”
• “Bob did not attend every lecture;”
• “Bob passed the course.”
Translate into logic as (with domain being
students in the course):
• ∀x(P(x)→H(x)∨L(x)),
• ¬L(b),
• P(b).
• Proof
– Then we can conclude:
• ∀x(P(x)→H(x)∨L(x)) [hypothesis]
• P(b)→H(b)∨L(b) [Universal instantiation]
• P(b) [hypothesis]
• H(b)∨L(b) [modus ponens using (2) and (3)]
• ¬L(b) [hypothesis]
• H(b) [Disjunctive syllogism using (4) and (5)]
– So, Bob must have done the homework.
•
 USING FIRST-ORDER LOGIC
• In knowledge representation, a domain is just some part of the
world about which we wish to express some knowledge.
• We begin with a brief description of the TELL/ASK interface for
first-order knowledge bases.
• Assertions and queries in first-order logic
• Sentences are added to a knowledge base using TELL, exactly as in
propositional logic. Such sentences are called assertions. For
example, we can assert that John is a king, Richard is a person, and
all kings are persons:
• TELL(KB, King(John)) .
• TELL(KB, Person(Richard)) .
• TELL(KB, ∀x King(x) ⇒ Person(x)) .
• We can ask questions of the knowledge base using ASK. For
example, ASK(KB, King(John)) returns true.
• Questions asked with ASK are called queries or goals.
The kinship domain-
• The first example we consider is the domain of family relationships,
or kinship. This domain includes facts such as “Elizabeth is the
mother of Charles” and “Charles is the father of William” and rules
such as “One’s grandmother is the mother of one’s parent.” Clearly,
the objects in our domain are people. We have two unary
predicates, Male and Female. Kinship relations—parenthood,
brotherhood, marriage, and so on—are represented by binary
predicates: Parent, Sibling, Brother, Sister, Child, Daughter, Son,
Spouse, Wife, Husband, Grandparent, Grandchild, Cousin, Aunt, and
Uncle. We use functions for Mother and Father, because every
person has exactly one of each of these (at least according to
nature’s design).
• For example, one’s mother is one’s female parent:
• ∀m, Mother(c)=m ⇔ Female(m)∧Parent(m,c) .
• One’s husband is one’s male spouse:
• ∀w,h Husband(h,w) ⇔ Male(h)∧Spouse(h,w) .
Quantified inference rules
• Universal instantiation
• ∀x P(x) ∴ P(A)

• Universal generalization
• P(A) ∧ P(B) … ∴ ∀x P(x)

• Existential instantiation
• ∃x P(x) ∴P(F)

• Existential generalization
• P(A) ∴ ∃x P(x)

(Note : A constant that replaces an existentially

quantified variable is called a Skolem constant)
 Universal generalization

• It is a valid inference rule which states that if

premise p(c) is true for any arbitrary element c in
the universe of the discourse, then we can have a
conclusion.
• It can be represented as,
p(c)
∀x
e.g. let’s represent, p(c): “ A byte contains 8 bits”, so
for ∀x p(x). “All byte contains 8 bit:”.
 Universal instantiation
• It is also called Elimination.
• It can be applied multiple times to add new statements.
• If (∀x) P(x) is true, then P(C) is true, where C is any
constant in the domain of x
• The Universal instantiation state that we can infer any
sentence p(c) by substituting a ground term c (a constant
within domain x) for ∀x P(x) for any object in the
universe of discourse.
∀x P(x)
p(x)
If every person likes ice creams -----∀x P(x) so we can infer
that John likes ice cream------- p(x)
 Existential instantiation

• It is also called as Existential elimination.

• It can be applied only once to replace the
Existential sentence.
• This rule state that one can infer p(c) from the
formula given in the form ∃x P(x) for a new
constant symbol c.
∃x P(x)
P(c)
 Existential generalization
P(A) ∃x P(x)

• It is also called as existential generalization.

– This rule states that If there is some element c in
the universe of discourse which has a property p,
then we can infer that their exist something in the
universe which has property p.

P(c)
∃x P(x)
 Example: A simple genealogy KB by FOL
• Build a small genealogy knowledge base using
FOL that
• contains facts of immediate family relations (spouses, parents, etc.)
• contains definitions of more complex relations (ancestors, relatives)
• is able to answer queries about relationships between people
• Predicates:
• parent(x, y), child(x, y), father(x, y), daughter(x, y), etc.
• spouse(x, y), husband(x, y), wife(x,y)
• ancestor(x, y), descendant(x, y)
• male(x), female(y)
• relative(x, y)
• Facts:
• husband(Joe, Mary), son(Fred, Joe)
• spouse(John, Nancy), male(John), son(Mark, Nancy)
• father(Jack, Nancy), daughter(Linda, Jack)
• daughter(Liz, Linda)
• etc.
 Semantics of FOL
• Domain M: the set of all objects in the world (of
interest)
• Interpretation I: includes
• Assign each constant to an object in M
• Define each function of n arguments as a mapping Mn => M
• Define each predicate of n arguments as a mapping Mn => {T, F}
• Therefore, every ground predicate with any instantiation will have
a truth value
• In general there is an infinite number of interpretations because
|M| is infinite
• Define logical connectives: ~, ^, ∨, =>, <=> as
in PL
• Define semantics of (∀x) and (∃x)
• (∀x) P(x) is true if P(x) is true under all interpretations
• (∃x) P(x) is true if P(x) is true under some interpretation
• Model: an interpretation of a set of sentences
such that every sentence is True

• A sentence is
• satisfiable if it is true under some interpretation
• valid if it is true under all possible interpretations
• inconsistent if there does not exist any interpretation under
which the sentence is true

• Logical consequence: S |= X if all models of S

are also models of X
 Translating English to FOL
Every gardener likes the sun.
∀x gardener(x) → likes(x,Sun)
You can fool some of the people all of the time.
∃x ∀t person(x) ∧time(t) → can-fool(x,t)
You can fool all of the people some of the time.
∀x ∃t (person(x) → time(t) ∧can-fool(x,t))
∀x (person(x) → ∃t (time(t) ∧can-fool(x,t)))
All purple mushrooms are poisonous. Equivale
∀x (mushroom(x) ∧ purple(x)) → poisonous(x)
nt
No purple mushroom is poisonous.
¬∃x purple(x) ∧ mushroom(x) ∧ poisonous(x)
∀x (mushroom(x) ∧ purple(x)) → ¬poisonous(x)
There are exactly two purple mushrooms. Equivale
∃x ∃y mushroom(x) ∧ purple(x) ∧ mushroom(y) ∧ purple(y) ^ ¬(x=y)nt
∧ ∀z
(mushroom(z) ∧ purple(z)) → ((x=z) ∨ (y=z))
Clinton is not tall.
¬tall(Clinton)
X is above Y iff X is on directly on top of Y or there is a pile of one or more other objects
directly on top of one another starting with X and ending with Y.
∀x ∀y above(x,y) ↔ (on(x,y) ∨ ∃z (on(x,z) ∧ above(z,y)))
 Summary of FOL Semantics

• A well-formed formula (“wff”) FOL is true or false

with respect to a world and an interpretation (a
model). The world has objects, relations,
functions, and predicates. The interpretation
maps symbols in the logic to the world.
 A Backus–Naur form(BNF) for FOL
S := <Sentence> ;
<Quantifier> := "EXISTS" |
<Sentence> := <AtomicSentence> | "FORALL" ;
<Sentence> <Connective>
<Sentence> |
<Quantifier> <Variable>,... <Constant> := "A" | "X1" | "John
<Sentence> | | ... ;

"NOT" <Sentence> | "("

<Sentence> ")";
<Variable> := "a" | "x" | "s" |
... ;

<AtomicSentence> := <Predicate>
"(" <Term>, ... ")" | <Term> "=" <Predicate> := "Before" |
<Term>; "HasColor" | "Raining" | ...

<Function> := "Mother" |
<Term> := <Function> "(" <Term>, ... "LeftLegOf" | ... ;
")" | <Constant> | <Variable>;

<Connective> := "AND" | "OR" |

 Knowledge Engineering in First Order
Logic
• The process of constructing a knowledge-base in first order logic is called
Knowledge Engineering.
• In Knowledge Engineering, someone who investigates a particular domain,
learns important concept of that domain, and generates a formal
representation of the objects, is known as Knowledge Engineering.

• Following are the steps of Knowledge Engineering steps:

1. Identify the task.

2. Assemble the relevant knowledge.
3. Decide on a vocabulary of predicates, functions and constants.
4. Encode general knowledge about the domain.
5. Encode a description of the specific problem instance.
6. Pose queries to the inference procedure and get answers.
7. Debug the knowledge base.
Logical agents for the Wumpus World

Three (non-exclusive) agent architectures:

• Reflex agents
• Have rules that classify situations, specifying how to
react to each possible situation
• Model-based agents
• Construct an internal model of their world
• Goal-based agents
• Form goals and try to achieve them
 Goal-based agents
• Once the gold is found, it is necessary to change
strategies. So now we need a new set of action
values.
• We could encode this as a rule:
• (∀s) Holding(Gold,s) → GoalLocation([1,1]),s)
• We must now decide how the agent will work out
a sequence of actions to accomplish the goal.
• Three possible approaches are:
• Inference: good versus wasteful solutions
• Search: make a problem with operators and set of
states.
 Reference
• Text Books:
• Stuart Russell and Peter Norvig, “Artificial
Intelligence: A Modern Approach”, Third edition,
Pearson, 2003, ISBN :10: 0136042597
Thank You !