1

UNIT-2
KNOWLEDGE REPRESENTATION AND REASONING
Logical Agents:
Knowledge-Based Agents:
o An intelligent agent needs knowledge about the real world for taking decisions
and reasoning to act efficiently.
o Knowledge-based agents are those agents who have the capability of maintaining
an internal state of knowledge, reason over that knowledge, update their
knowledge after observations and take actions. These agents can represent
the world with some formal representation and act intelligently.
o Knowledge-based agents are composed of two main parts:
o Knowledge-base and Inference system.
A knowledge-based agent must able to do the following:
o An agent should be able to represent states, actions, etc.
o An agent Should be able to incorporate new percepts
o An agent can update the internal representation of the world
o An agent can deduce the internal representation of the world
o An agent can deduce appropriate actions.
The architecture of knowledge-based agent:

● The above diagram is representing a generalized architecture for a knowledge-

based agent.
 2

● The knowledge-based agent (KBA) take input from the environment by

perceiving the environment.

● The input is taken by the inference engine of the agent and which also

communicate with KB to decide as per the knowledge store in KB.

● The learning element of KBA regularly updates the KB by learning new

knowledge.
Knowledge base:

● Knowledge-base is a central component of a knowledge-based agent, it is also

known as KB.It is a collection of sentences.

● These sentences are expressed in a language which is called a knowledge

representation language.
Inference system:

● Inference means deriving new sentences from old.

● Inference system allows us to add a new sentence to the knowledge base.

● Inference system applies logical rules to the KB to deduce new information.

● Inference system generates new facts so that an agent can update the KB.

● An inference system works mainly in two rules which are given as:

o Forward chaining and Backward chaining.

Operations Performed by KBA
1. TELL: This operation tells the knowledge base what it perceives from the
environment.
2. ASK: This operation asks the knowledge base what action it should perform.
 3

3. Perform: It performs the selected action.

A generic knowledge-based agent:
1. function KB-AGENT(percept):
2. persistent: KB, a knowledge base
3. t, a counter, initially 0, indicating time
4. TELL(KB, MAKE-PERCEPT-SENTENCE(percept, t))
5. Action = ASK(KB, MAKE-ACTION-QUERY(t))
6. TELL(KB, MAKE-ACTION-SENTENCE(action, t))
7. t = t + 1
8. return action

The Wumpus World:

● The Wumpus World’s agent is an example of a knowledge-based agent that

represents Knowledge representation, reasoning and planning.

● Knowledge-Based agent links general knowledge with current percepts to infer

hidden characters of current state before selecting actions.

● Its necessity is vital in partially observable environments.

● The Wumpus world is a 4x4 cave with 16 rooms connected to each other through

passageways. The knowledge-based agent goes forward in this world.

● The cave has a room with a beast which is called Wumpus, who eats anyone who

enters the room.

● The Wumpus can be shot by the agent, but the agent has a single arrow.
 4

● In the Wumpus world, there are some Pits rooms which are bottomless, and if

agent falls in Pits, then he will be stuck there forever.

● The exciting thing with this cave is that in one room there is a possibility of

finding a heap of gold.

● So the agent goal is to find the gold and climb out the cave without fallen into Pits

or eaten by Wumpus.

● The agent will get a reward if he comes out with gold, and he will get a penalty if

eaten by Wumpus or falls in the pit.

There are also some components which can help the agent to navigate the cave.
These components are given as follows:
a) The rooms adjacent to the Wumpus room are smelly, so that it would have some
stench.
b) The room adjacent to PITs has a breeze, so if the agent reaches near to PIT, then
he will perceive the breeze.
c) There will be glitter in the room if and only if the room has gold.
 5

d) The Wumpus can be killed by the agent if the agent is facing to it, and Wumpus
will emit a horrible scream which can be heard anywhere in the cave.
PEAS description of Wumpus world:
Performance measure:
o +1000 reward points if the agent comes out of the cave with the gold.
o -1000 points penalty for being eaten by the Wumpus or falling into the pit.
o -1 for each action, and -10 for using an arrow.
o The game ends if either agent dies or came out of the cave.
Environment:
o A 4*4 grid of rooms.
o The agent initially in room square [1, 1], facing toward the right.
o Location of Wumpus and gold are chosen randomly except the first square [1,1].
o Each square of the cave can be a pit with probability 0.2 except the first square.
Actuators:
o Left turn, Right turn, Move forward, Grab, Release, Shoot.
Sensors:
o The agent will perceive the stench if he is in the room adjacent to the Wumpus.
(Not diagonally).
o The agent will perceive breeze if he is in the room directly adjacent to the Pit.
o The agent will perceive the glitter in the room where the gold is present.

The Wumpus world Properties:

o Partially observable: The Wumpus world is partially observable because the
agent can only perceive the close environment such as an adjacent room.
o Deterministic: It is deterministic, as the result and outcome of the world are
already known.
o Sequential: The order is important, so it is sequential.
o Static: It is static as Wumpus and Pits are not moving.
 6

o Discrete: The environment is discrete.

o One agent: The environment is a single agent as we have one agent only and
Wumpus is not considered as an agent.

Exploring the Wumpus world:

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.

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?

 7

● 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.

● So it is safe, and we will mark it OK, and the agent moves further in [2,2].

Propositional logic:
● Propositional logic (PL) is the simplest form of logic where all the statements are

made by propositions.

● A proposition is a declarative statement which is either true or false.

● It is a technique of knowledge representation in logical and mathematical form.

Example:
a) It is Sunday.
b) The Sun rises from West (False proposition)
c) 5 is a prime number.
Following are some basic facts about propositional logic:
o Propositional logic is also called Boolean logic as it works on 0 and 1.
o In propositional logic, we use symbolic variables to represent the logic, and we
can use any symbol for a representing a proposition, such A, B, C, P, Q, R, etc.
o Propositions can be either true or false, but it cannot be both.
o Propositional logic consists of an object, relations or function, and logical
connectives.
o These connectives are also called logical operators.
o The propositions and connectives are the basic elements of the propositional logic.
o Connectives can be said as a logical operator which connects two sentences.
 8

o A proposition formula which is always true is called tautology, and it is also

called a valid sentence.
o A proposition formula which is always false is called Contradiction.
Syntax of propositional logic:

● The syntax of propositional logic defines the allowable sentences for the

knowledge representation. There are two types of Propositions:

Atomic Propositions and Compound propositions
Atomic Proposition:

● Atomic propositions are the simple propositions. It consists of a single proposition

symbol. These are the sentences which must be either true or false.
Example:
a) 2+2 is 4, it is an atomic proposition as it is a true fact.
b) "The Sun is cold" is also a proposition as it is a false fact.
Compound proposition:

● Compound propositions are constructed by combining simpler or atomic

propositions, using parenthesis and logical connectives.

Example:
a) "It is raining today, and street is wet."
b) "Ankit is a doctor, and his clinic is in Mumbai."
Logical Connectives:
● Logical connectives are used to connect two simpler propositions or representing

a sentence logically.

● We can create compound propositions with the help of logical connectives. There

are mainly five connectives, which are given as follows:

1. Negation: A sentence such as ¬ P is called negation of P. A literal can be either
Positive literal or negative literal.
 9

2. Conjunction: A sentence which has ∧ connective such as, P ∧ Q is called a

conjunction.
Example: Rohan is intelligent and hardworking. It can be written as,
P= Rohan is intelligent,Q= Rohan is hardworking. → P∧ Q.
3. Disjunction: A sentence which has ∨ connective, such as P ∨ Q. is called
disjunction, where P and Q are the propositions.
Example: "Ritika is a doctor or Engineer",
Here P= Ritika is Doctor. Q= Ritika is Doctor, so we can write it as P ∨ Q.
4. Implication: A sentence such as P → Q, is called an implication. Implications are
also known as if-then rules. It can be represented as
If it is raining, then the street is wet.
Let P= It is raining, and Q= Street is wet, so it is represented as P → Q
5. Biconditional: A sentence such as P⇔ Q is a Biconditional sentence, example
If I am breathing, then I am alive
P= I am breathing, Q= I am alive, it can be represented as P ⇔ Q.

First-Order logic:
o First-order logic is another way of knowledge representation in artificial
intelligence. It is an extension to propositional logic.
o First-order logic is also known as Predicate logic or First-order predicate logic.
First-order logic is a powerful language that develops information about the
objects in a more easy way and can also express the relationship between those
objects.
 10

o First-order logic does not only assume that the world contains facts like
propositional logic but also assumes the following things in the world:
o Objects: A, B, people, numbers, colors, wars, theories, squares, pits,….
o Relations: It can be unary relation such as: red, round, is adjacent, or n-
any relation such as: the sister of, brother of, has color, comes between
o Function: Father of, best friend, third inning of, end of, ......
o As a natural language, first-order logic also has two main parts:
o Syntax b.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.

Constant 1, 2, A, John, Mumbai, cat,....

Variables x, y, z, a, b,....

Predicates Brother, Father, >,....

Function sqrt, LeftLegOf, ....

Connectives ∧, ∨, ¬, ⇒, ⇔

Equality ==

Quantifier ∀, ∃

Atomic sentences:
o Atomic sentences are the most basic sentences of first-order logic. These
sentences are formed from a predicate symbol followed by a parenthesis with a
sequence of terms.
o We can represent atomic sentences as Predicate (term1, term2, ......, term n).
Example: Ravi and Ajay are brothers: => Brothers(Ravi, Ajay).
Chinky is a cat: => cat (Chinky).
 11

Complex Sentences:
o Complex sentences are made by combining atomic sentences using connectives.
First-order logic statements can be divided into two parts:
o Subject: Subject is the main part of the statement.
o 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.

Quantifiers in First-order logic:

o A quantifier is a language element which generates quantification, and
quantification specifies the quantity of specimen in the universe of discourse.
o These are the symbols that permit to determine or identify the range and scope of
the variable in the logical expression. There are two types of quantifier:
1. Universal Quantifier, (for all, everyone, everything)
2. Existential quantifier, (for some, at least one).
Universal Quantifier:
Universal quantifier is a symbol of logical representation, which specifies that the
statement within its range is true for everything or every instance of a particular thing.
The Universal quantifier is represented by a symbol ∀, which resembles an inverted A.
If x is a variable, then ∀x is read as:
o For all x
o For each x
o For every x.
Example:
All man drink coffee.
 12

Let a variable x which refers to a cat so all x can be represented in UOD as below:

Existential Quantifier:
Existential quantifiers are the type of quantifiers, which express that the statement
within its scope is true for at least one instance of something.
It is denoted by the logical operator ∃, which resembles as inverted E. When it is
used with a predicate variable then it is called as an existential quantifier.
If x is a variable, then existential quantifier will be ∃x or ∃(x). And it will be read as:
o There exists a 'x.'
o For some 'x.'
o For at least one 'x.'

Example:
Some boys are intelligent.

∃x: boys(x) ∧ intelligent(x)

It will be read as: There are some x where x is a boy who is intelligent.
 13

Inference in First-Order Logic

● Inference in First-Order Logic is used to deduce new facts or sentences from existing

sentences.

● Before understanding the FOL inference rule, let's understand some basic

terminologies used in FOL.

Substitution:
Substitution is a fundamental operation performed on terms and formulas. It
occurs in all inference systems in first-order logic. The substitution is complex in the
presence of quantifiers in FOL. If we write F[a/x], so it refers to substitute a constant "a"
in place of variable "x".
Equality:
First-Order logic does not only use predicate and terms for making atomic
sentences but also uses another way, which is equality in FOL. For this, we can
use equality symbols which specify that the two terms refer to the same object.
Example: Brother (John) = Smith.
As in the above example, the object referred by the Brother (John) is similar to the
object referred by Smith.
Example: ￢(x=y) which is equivalent to x ≠y.

FOL inference rules for quantifier:

As propositional logic we also have inference rules in first-order logic:
o Universal Generalization/Universal Instantiation
o Existential Instantiation/Existential introduction
1. Universal Generalization:
o Universal generalization is a valid inference rule which states that if premise P(c)
is true for any arbitrary element c in the universe of discourse, then we can have a
conclusion as ∀ x P(x).
 14

o This rule can be used if we want to show that every element has a similar
property.
o In this rule, x must not appear as a free variable.

2. Universal Instantiation:
o Universal instantiation is also called as universal elimination or UI is a valid
inference rule. It can be applied multiple times to add new sentences.
o The new KB is logically equivalent to the previous KB.
o As per UI, we can infer any sentence obtained by substituting a ground term
for the variable.
o The UI rule state that we can infer any sentence P(c) by substituting a ground term
c from ∀ x P(x) for any object in the universe of discourse.

Example:1.
IF "Every person like ice-cream"=> ∀x P(x) so we can infer that
"John likes ice-cream" => P(c)

3. Existential Instantiation:
o Existential instantiation is also called as Existential Elimination, which is a valid
inference rule in first-order logic.
o It can be applied only once to replace the existential sentence.
o The new KB is not logically equivalent to old KB, but it will be satisfiable if old
KB was satisfiable.
o This rule states that one can infer P(c) from the formula given in the form of ∃x
P(x) for a new constant symbol c.
 15

o The restriction with this rule is that c used in the rule must be a new term for
which P(c ) is true.
Example:
From the given sentence: ∃x Crown(x) ∧ OnHead(x, John),
So we can infer: Crown(K) ∧ OnHead( K, John), as long as K does not appear in the
knowledge base.
o The above used K is a constant symbol, which is called Skolem constant.
o The Existential instantiation is a special case of Skolemization process.

4. Existential introduction
o An existential introduction is also known as an existential generalization, which is
a valid inference rule in first-order logic.
o 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 there exists something in the universe
which has the property P.
o Example: Let's say that,
"Priyanka got good marks in English."
"Therefore, someone got good marks in English."