Unit 3

Knowledge Representation
- Madhura Vyawahare

Madhura Vyawahare
Syllabus
● Propositional logic
● Theory of first order logic
● Inference in First order logic
● Forward & Backward Chaining
● Resolution

Madhura Vyawahare
Knowledge
Knowledge : knowing something
● Information one gained through learning or experience
● The state of knowing about a particular fact or situation
Reasoning: Use of reasons
● Process of thinking about something and making a judgement or decision
● The drawing of inferences or conclusions through the use of reason
Intelligence:
● Ability to learn something
● The ability to understand, learn and think
Madhura Vyawahare
Types of Knowledge

Madhura Vyawahare
Types of Knowledge
● Declarative or Descriptive knowledge
○ Factual knowledge: capital of a country or the chemical formula for a substance
○ Conceptual knowledge: concepts of crimes, searching, justice or freedom
○ Theoretical knowledge: Newton’s law, laws of physics or the principles of economics

● Procedural Knowledge
○ How to do things
○ Example: How to drive a car, how to register a complaint, how to write a program etc.
● Meta Knowledge
○ Knowledge about knowledge
○ Example: reliability of algorithm, advantages of the procedure
● Structural Knowledge
○ Architecture and design of a software system
● Heuristic Knowledge
Madhura Vyawahare
Knowledge Representation
I saw a man on hill with telescope
A chicken is ready to eat

The dog chased a cat, which ran up a tree. It waited at the bottom.
Who does "it" refer to??

The dog chased a cat, which ran up a tree. It waited at the top.
Who does "it" refer to??
Madhura Vyawahare
Knowledge Representation
● No ambiguity
● No syntax error
● No semantic error

Ways to represent Knowledge

● Logic
○ Propositional
○ Predicate
● Rules
● Semantic net
● Frames
● Scripts

Madhura Vyawahare
Knowledge Representation
What is knowledge representation?
● Humans are best at understanding, reasoning, and interpreting knowledge.
● Human knows things, which is knowledge and as per their knowledge they perform various
actions in the real world.
● Knowledge representation and reasoning (KR, KRR) is the part of Artificial intelligence which
concerned with AI agents thinking and how thinking contributes to intelligent behavior of
agents.
● It is responsible for representing information about the real world so that a computer can
understand and can utilize this knowledge to solve the complex real world problems such as
diagnosis a medical condition or communicating with humans in natural language.
● It is also a way which describes how we can represent knowledge in artificial intelligence.
● Knowledge representation is not just storing data into some database, but it also enables an
intelligent machine to learn from that knowledge and experiences so that it can behave
intelligently like a human.
Madhura Vyawahare
What to Represent:
Following are the kind of knowledge which needs to be represented in AI systems:

o Object: All the facts about objects in our world domain. E.g., Guitars contains strings,
trumpets are brass instruments.

o Events: Events are the actions which occur in our world.

o Performance: It describe behavior which involves knowledge about how to do things.

o Meta-knowledge: It is knowledge about what we know.

o Facts: Facts are the truths about the real world and what we represent.

o Knowledge-Base: The central component of the knowledge-based agents is the knowledge

base. It is represented as KB.
Madhura Vyawahare
Propositional Logic
● PL is the simplest form of logic
● Logic is reasoning or thinking with knowledge
● 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) 3+3= 7(False proposition)
d) 5 is a prime number.
Madhura Vyawahare
Propositional Logic
● Propositional logic is also called Boolean logic as it works on 0 and 1.
● It can have atomic or complex form of propositions
● Parameters of Propositional Logic:
○ Variables: symbolic variables are used to represent the logic such A, B, C, P, Q, R, etc.
○ Local Constants: Propositions can be either true or false, but it cannot be both.
○ Set of logic operators also known as logical connectives
● The propositions and connectives are the basic elements of the propositional logic.
● Connectives can be said as a logical operator which connects two sentences.
● A proposition formula which is always true is called tautology, and it is also called a valid
sentence.
● A proposition formula which is always false is called Contradiction.
Madhura Vyawahare
Madhura Vyawahare
Madhura Vyawahare
Madhura Vyawahare
Madhura Vyawahare
Examples
I have not completed paper checking.
Siya play basketball and siya loves shopping
It is raining or sun is shining
You should study or listen songs at a time

If it is raining then road is wet

If it is sunny, then I will go for a walk.

If you study hard, then and only then you will get good grades.
If the team wins the game, then the fans will be happy.
If the team wins the game, then and only then fans will be happy.
Madhura Vyawahare
Examples
I have not completed paper checking. If it is raining then road is wet

completed paper checking = P it is raining = P, road is wet = Q

I have not completed paper checking = ¬P If it is raining then road is wet = P -> Q

Siya play basketball and siya loves shopping If you study hard, then and only then you will
get good grades.
Siya play basketball = P, siya loves shopping = Q
you study hard = P, you will get good grades =
Siya play basketball and siya loves shopping = P ∧ Q Q
P⇔Q

It is raining or sun is shining If the team wins the game, then the fans will be
happy.
It is raining =P, sun is shining = Q
If the team wins the game, then and only then
It is raining or sun is shining = P ∨ Q fans will be happy.
Madhura Vyawahare
“If it is sunny, then I will go for a walk”

Is it equivalent to

“If I go for a walk, then it is sunny”

If the team wins the game, then the fans are happy.

Is it equivalent to

“If fans are happy then, team wins the game”

Or “If fans are happy then team has won the game”

Madhura Vyawahare
● Make a truth table for the statement ¬P ∨ Q
● Prove that the statements ¬( P → Q ) and P ∧ ¬Q are logically equivalent
without using truth tables.
● Are the statements (P∨Q)→R and (P→R)∨(Q→R) logically equivalent?
● You can access the internet from the campus if you are MCA students or you are
not freshman
● Are the statements, “it will not rain or snow” and “it will not rain and it will not
snow” logically equivalent?

Madhura Vyawahare
De Morgan's laws

¬ (P ∧ Q) = (¬P) ∨ (¬Q)

¬ (P ∨ Q) = (¬ P) ∧ (¬Q).

Madhura Vyawahare
Propositional Logic
● It is good start at describing the general principles of logical reasoning but does not give the means to
express a general principle
● Limitations of Propositional Logic
○ We cannot represent relations like ALL, some, or none with propositional logic. Example:
a. All the kids are cute.
b. Axis bank stock goes up on some mondays and goes down on all fridays
○ Propositional logic has limited expressive power.
○ In propositional logic, we cannot describe statements in terms of their properties or logical
relationships.
○ To make sense of inferences like these, we need a logical system that can deal with objects, their
properties, and relations between them.

Madhura Vyawahare
Predicate Logic
● Predicate logic overcomes the limitations of propositional logic

● It is More expressive

● More powerful as it uses quantifiers along with connectives

● Also known as first-order logic, is a formal system for reasoning about statements involving quantifiers

● In predicate logic, we use variables to represent objects or values, and predicates to express relationships
or properties of those objects.

● For example:

○ “The cat is sleeping in the sun.” The clause sleeping in the sun is the predicate and cat is an object

○ “Dog is a mammal who has fur”: The predicate "is a mammal" to describe an object dog, and "has
fur" to describe a property of that object.

● “x + 2 = y” is a predicate and “2+2 = 4” is a proposition

Madhura Vyawahare
First Order Predicate Logic
Atomic sentences and Complex Sentences:
● 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.
● Complex sentences are formed from atomic sentences using connectives
● 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).
○ alexa(intelligent).
○ dimple(beautiful).
○ rahul(smart).
○ owns(sheetal,rose).
○ plays(amit,football).

Madhura Vyawahare
● Example:
○ plays(amit,football).
○ play(amit, rakhi,football).
○ play(amit, rekha, football).
○ play(amit, nitin, football).
● Using variables:
○ plays(amit,X,football).
■ Rakhi;
■ Rekha;
■ nitin;
● Using Connectives
○ likes(shikha,mango) ∧ likes(amit,mango).
Madhura Vyawahare
Basic Elements of First-order logic:

Madhura Vyawahare
Madhura Vyawahare
Madhura Vyawahare
- For all x if x is a dolphin then x is a mammal
- There exist few x such that x is a mammal and x lays eggs
Madhura Vyawahare
Examples
All birds fly

Every man respect his parents

Some boys play cricket

Not all students like maths and science

Madhura Vyawahare
Madhura Vyawahare
Madhura Vyawahare
Examples
1. Predicate Logic Examples

a. John likes all kind of food.

b. Apple and vegetable are food

c. Anything anyone eats and not killed is food.

d. Anil eats peanuts and still alive

e. Harry eats everything that Anil eats.

f. Some humans are intelligent

g. Every child love candy

Madhura Vyawahare
Madhura Vyawahare
Madhura Vyawahare
Madhura Vyawahare
Madhura Vyawahare
Inference in First Order Logic
● Inference in First-Order Logic is used to deduce new facts or sentences from existing
sentences
● Substitution is used for inference
● 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:
○ Brother (John) = Smith.
● Modus Ponens (MP): P → Q If P is true then Q is true
● Modus Tollens: if P→ Q is true and ¬ Q is true, then ¬ P will also true

Madhura Vyawahare
Wumpus World Problem
● The Wumpus world is a cave which has 4/4 rooms connected with passageways.
● There are total 16 rooms which are connected with each other.
● We have a knowledge-based agent who will go 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.
● 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.
● Assumption: Wumpus is static and cannot move Madhura Vyawahare
Madhura Vyawahare
Wumpus world problem
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.
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.

Madhura Vyawahare
PEAS Description of Wumpus World
To explain the Wumpus world we have given PEAS description as below:
Performance measure:
○ +1000 reward points if the agent comes out of the cave with the gold.
○ -1000 points penalty for being eaten by the Wumpus or falling into the pit.
○ -1 for each action, and -10 for using an arrow.
○ The game ends if either agent dies or came out of the cave.
Environment:
○ A 4*4 grid of rooms.
○ The agent initially in room square [1, 1], facing toward the right.
○ Location of Wumpus and gold are chosen randomly except the first square [1,1].
○ Each square of the cave can be a pit with probability 0.2 except the first square.
Madhura Vyawahare
PEAS Description of Wumpus World
Actuators:
○ Left turn
○ Right turn
○ Move forward
○ Grab
○ Shoot.

Madhura Vyawahare
PEAS Description of Wumpus World
Sensors:
○ The agent will perceive the stench if he is in the room adjacent to the Wumpus. (Not
diagonally).
○ The agent will perceive breeze if he is in the room directly adjacent to the Pit.
○ The agent will perceive the glitter in the room where the gold is present.
○ The agent will perceive the bump if he walks into a wall.
○ When the Wumpus is shot, it emits a horrible scream which can be perceived anywhere in
the cave.
○ These precepts can be represented as five element list, in which we will have different
indicators for each sensor.
○ Example if agent perceives stench, breeze, but no glitter, no bump, and no scream then it
can be represented as:
[Stench, Breeze, None, None, None].
Madhura Vyawahare
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.
Madhura Vyawahare
Wumpus World Execution
● If the room is safe we will add symbol OK.

● A is used to represent agent,

● B for the breeze,

● G for Glitter or gold,

● V for the visited room,

● P for pits,

● W for Wumpus.
Madhura Vyawahare
Solving Wumpus World Using Logic
○ Let Pi,j be true if there is a Pit in the room [i, j].
○ Let Bi,j be true if agent perceives breeze in [i, j],
○ Let Wi,j be true if there is wumpus in the square[i, j].
○ Let Si,j be true if agent perceives stench in the square [i, j].
○ Let Vi,j be true if that square[i, j] is visited.
○ Let Gi,j be true if there is gold (and glitter) in the square [i, j].
○ Let OKi,j be true if the room is safe.

Madhura Vyawahare
Madhura Vyawahare
Solving Wumpus World using Propositional Logic
Some Propositional Rules for the wumpus world:

Madhura Vyawahare
Solving Wumpus World using Propositional Logic

Representation of Knowledge Base for Wumpus world:

¬W11 V11 ¬S11 ¬P11 ¬B11 ¬G11 OK11

¬W21
¬W12

Madhura Vyawahare
Madhura Vyawahare
Madhura Vyawahare
S12 and R4 which is S12 → W13 ∨. W12 ∨. W22 ∨.W11, we will get the output as W13∨ W12 ∨ W22
∨.W11.

Madhura Vyawahare
Madhura Vyawahare
Madhura Vyawahare
Forward Chaining and Backward
Chaining in AI

Madhura Vyawahare
 Inference Engine
● Inference is extracting conclusion or decision
● The inference engine is the component of the intelligent system in artificial
intelligence, which applies logical rules to the knowledge base to infer
new information from known facts.
● The first inference engine was part of the expert system.
● Inference engine commonly proceeds in two modes, which are:
○ Forward Chaining
○ Backward Chaining

Madhura Vyawahare
Forward Chaining
● Also known as a forward deduction or forward reasoning method when it uses an
inference engine.
● The Forward-chaining algorithm
○ Starts from known facts,
○ Triggers all rules whose premises are satisfied,
○ Add their conclusion to the known facts.
● Forward chaining is a form of reasoning which start with atomic sentences in
the knowledge base and applies inference rules in the forward direction to
extract more data until a goal is reached.
● Initial state to goal state
● Initial data is given and it finds out solution or conclusion
● It is based on available data hence is Data driven approach
● This process repeats until the problem is solved
Madhura Vyawahare
Forward Chaining/Reasoning
● It starts by finding all the rules whose left side matches with the initial / root node
● For example,
○ While diagnosing a patient the doctor first check the symptoms and medical condition of
the body such as temperature, blood pressure, pulse, eye colour, blood, etc..
○ After that, the patient symptoms are analysed and compared against the predetermined
symptoms.
○ Then the doctor is able to provide the medicines according to the symptoms of the
patient.
● So, when a solution employs this manner of reasoning, it is known as forward
chaining/reasoning.

Madhura Vyawahare
Forward Chaining

● Example:
○ It is raining- A
○ Road is wet - B
○ If it is raining road is wet A-> B
○ A is true is given fact, find if the road is wet or not
● Example: x=1, y=2,
○ if (x==1 and y==2) then z=3)
○ if z==3 then a=10
○ Find what is the value of a

Left side is given find right side

Madhura Vyawahare
Backward Chaining:
● Backward-chaining is also known as a backward deduction or backward
reasoning method when using an inference engine.
● A backward chaining algorithm is a form of reasoning, which starts with
the goal and works backward, chaining through rules to find known facts
that support the goal.
● Goal Driven approach
● Goal state to initial data requirement
● Conclusion is given and find out required facts from which the conclusion
can be reached
Madhura Vyawahare
Backward Chaining

● Example:
○ It is raining - A
○ Road is wet - B
○ If it is raining road is wet A-> B
○ Road is wet is fact
● Example: x=1, y=2,
○ if (x==1 and y==2) then z=3
○ if z==3 then a=10
○ Value of a=10 is given find the values for a and b

Right side is given find left side

Madhura Vyawahare
Properties of Forward-Chaining:
● It is a bottom-up approach, as it moves from bottom to top.
● It is a process of making a conclusion based on known facts or
data, by starting from the initial state and reaches the goal state.
● Forward-chaining approach is also called as data-driven as we
reach to the goal using available data.
● Forward-chaining approach is commonly used in the expert
system, such as CLIPS, business, and production rule systems.

Madhura Vyawahare
Steps that are followed in the forward chaining
The inference engine explores the knowledge base with the provided
information for constraints whose precedence matches the given current
state.
● In the first step, the system is given with one or more than one constraints.
● Then the rules are searched in the knowledge base for each constraint. The
rules that fulfil the condition are selected (i.e., IF part).
● Now each rule is able to produce new conditions from the conclusion of
the invoked one. As a result, THEN part is again included in the existing
one.
● The added conditions are processed again by repeating step 2. The process
will end if there is no new conditions exist.
Madhura Vyawahare
Example of Forward Chaining
Encouraged students are always motivated. Along with motivation if student is healthy then
only students can work hard. Hard-working students with goal are excellent students who
succeed. If a Ram is encouraged, healthy and has goal find if Ram will succeed or not!

encouraged(student) -> motivated(Student)

motivated(student) AND healthy(student) -> work-hard(student)

work-hard(student) AND has(student, goal) -> Excellent(student)

Excellent(student) -> succeed(student)

encouraged(Ram), healthy(Ram), has(Ram, goal)

Madhura Vyawahare
Definition of Backward Chaining
● The backward reasoning is inverse of forward reasoning
● It starts by finding all the rules whose right side matches with the goal node
● Goal is analyzed in order to deduce the rules, initial facts and data.
● We can understand the concept by the similar example,
● In forward reasoning the doctor is trying to diagnose the patient with the help
of the inceptive data such as symptoms.
● However, in this case, the patient comes up with the name of disease, on the
basis of which the doctor is going to prove and verify the symptoms.
● This kind of reasoning comes under backward reasoning.

Madhura Vyawahare
Properties of backward chaining:
● It is known as a top-down approach.
● Backward-chaining is based on modus ponens inference rule.
● In backward chaining, the goal is broken into sub-goal or sub-goals to prove
the facts true.
● It is called a goal-driven approach, as a list of goals decides which rules are
selected and used.
● Backward -chaining algorithm is used in game theory, automated theorem
proving tools, inference engines, proof assistants, and various AI applications.
● The backward-chaining method mostly uses a depth-first search strategy for
proof.

Madhura Vyawahare
Steps that are followed in the backward reasoning:
In this type of reasoning, the system chooses a goal state and reasons in the
backward direction. Now, let’s understand how does it happens and what steps
are followed.
● Firstly, the goal state and the rules are selected where the goal state reside
in the THEN part as the conclusion.
● From the IF part of the selected rule the sub goals are made to be satisfied
for the goal state to be true.
● Set initial conditions important to satisfy all the sub goals.
● Verify whether the provided initial state matches with the established
states. If it fulfils the condition then the goal is the solution otherwise
other goal state is selected.
Madhura Vyawahare
Example of Backward Reasoning
encouraged(student) -> motivated(Student)
motivated(student) AND healthy(student) -> work-hard(student)
work-hard(student) AND has(student, goal) -> Excellent(student)
Excellent(student) -> succeed(student)

Ram succeeded, find facts about Ram.

to be excellent, subgoals are: student should be able to work hard and has goal
Student can work hard if he is healthy and motivated
Student is motivated if he is encouraged!
Madhura Vyawahare
Madhura Vyawahare
 BASIS FOR FORWARD BACKWARD
COMPARISON CHAINING CHAINING
Basic Data-driven Goal driven

Begins with New Data Uncertain conclusion

Objective is to find the Conclusion that must Facts to support the

follow conclusions
Type of approach Opportunistic Conservative

Flow Incipient to Consequence to

consequence incipient

Madhura Vyawahare
Example:
"As per the law, it is a crime for an American to sell weapons to
hostile nations. Country A, an enemy of America, has some
missiles, and all the missiles were sold to it by Robert, who is an
American citizen."
Prove that "Robert is criminal."
To solve the above problem, first, we will convert all the above facts
into first-order definite clauses, and then we will use a
forward-chaining algorithm to reach the goal.

Madhura Vyawahare
Madhura Vyawahare
Madhura Vyawahare
Forward chaining proof:
Step-1:
In the first step we will start with the known facts and will choose the
sentences which do not have implications, such as: American(Robert),
Enemy(A, America), Owns(A, T1), and Missile(T1). All these facts will
be represented as below.

Madhura Vyawahare
Step-2:
At the second step, we will see those facts which infer from available facts
and with satisfied premises.
Rule-(1) does not satisfy premises, so it will not be added in the first
iteration.
Rule-(2) and (3) are already added.
Rule-(4) satisfy with the substitution {p/T1}, so Sells (Robert, T1, A) is
added, which infers from the conjunction of Rule (2) and (3).
Rule-(6) is satisfied with the substitution(p/A), so Hostile(A) is added
and which infers from Rule-(7).

Madhura Vyawahare
Madhura Vyawahare
Madhura Vyawahare
Example:
In backward-chaining, we will use the same above example, and will rewrite all
the rules.

Madhura Vyawahare
Backward-Chaining proof:
In Backward chaining, we will start with our goal predicate, which
is Criminal(Robert), and then infer further rules.
Step-1:
At the first step, we will take the goal fact. And from the goal fact, we will
infer other facts, and at last, we will prove those facts true. So our goal
fact is "Robert is Criminal," so following is the predicate of it.

Madhura Vyawahare
Step-2: At the second step, we will infer other facts form goal fact which
satisfies the rules. So as we can see in Rule-1, the goal predicate Criminal
(Robert) is present with substitution {Robert/P}. So we will add all the
conjunctive facts below the first level and will replace p with Robert.
Here we can see American (Robert) is a fact, so it is proved here.

Madhura Vyawahare
Step-3:t At step-3, we will extract further fact Missile(q) which infer from
Weapon(q), as it satisfies Rule-(5). Weapon (q) is also true with the
substitution of a constant T1 at q.

Madhura Vyawahare
Step-4: At step-4, we can infer facts Missile(T1) and Owns(A, T1) form Sells(Robert,
T1, r) which satisfies the Rule- 4, with the substitution of A in place of r. So these two
statements are proved here.

Madhura Vyawahare
Madhura Vyawahare
Madhura Vyawahare
S. No. Forward Chaining Backward Chaining

1 Forward chaining starts from known facts and applies Backward chaining starts from the goal and works backward through
inference rule to extract more data unit it reaches to the goal. inference rules to find the required facts that support the goal.

2 It is a bottom-up approach It is a top-down approach

3 Forward chaining is known as data-driven inference technique Backward chaining is known as goal-driven technique as we start
as we reach to the goal using the available data. from the goal and divide into sub-goal to extract the facts.

4 Forward chaining reasoning applies a breadth-first search Backward chaining reasoning applies a depth-first search strategy.
strategy.

5 Forward chaining tests for all the available rules Backward chaining only tests for few required rules.
6 Forward chaining is suitable for the planning, monitoring, Backward chaining is suitable for diagnostic, prescription, and
control, and interpretation application. debugging application.
7 Forward chaining can generate an infinite number of possible Backward chaining generates a finite number of possible conclusions.
conclusions.
8 It operates in the forward direction. It operates in the backward direction.
9 Forward chaining is aimed for any conclusion. Backward chaining is only aimed for the required data.
Madhura Vyawahare
Resolution
● Resolution is a theorem proving technique that proceeds by building refutation proofs, i.e., proofs by
contradictions.

● Resolution is used, if there are various statements are given, and we need to prove a conclusion of those
statements.

● Resolution is a single inference rule which can efficiently operate on the conjunctive normal form or clausal
form.

● Clause: Disjunction of literals (an atomic sentence) is called a clause. It is also known as a unit clause.

● Conjunctive Normal Form: A sentence represented as a conjunction of clauses is said to be conjunctive

normal form or CNF.

● The resolution rule for first-order logic is simply a lifted version of the propositional rule. Resolution can
resolve two clauses if they contain complementary literals, which are assumed to be standardized apart so that
they share no variables.

Madhura Vyawahare
Steps for Resolution
Steps for Resolution:

1. Conversion of facts into first-order logic.

2. Convert FOL statements into CNF
3. Negate the statement which needs to prove (proof by contradiction)
4. Draw resolution graph.

Madhura Vyawahare
Example

1. All people who are graduating are happy

2. All happy people smile
3. Someone is graduating

Prove someone is smiling = true using resolution

Draw resolution tree

Madhura Vyawahare
1. All people who are graduating are happy
2. All happy people smile
3. Someone is graduating
someone is smiling

Step 1. Conversion of facts into first-order logic.

1. ∀x: graduating(x) → happy(x)

2. ∀x: happy(x) → smile(x)
3. ∃x: graduating(x)

∃x: smile(x)

We take negation of the final statement and prove with contradiction

Hence, ¬ (∃x: smile(x))

Madhura Vyawahare
Rules for Converting FOL to CNF
● Elimination of implications (→ )
○ a→ b is equal to ¬ aVb
● Move ¬ inwards
○ ¬ (a V b) = ¬a Λ ¬b
○ ¬ (a Λ b) = ¬a V ¬b
○ ¬¬a=a
● Standardize variables
● Drop universal quantifiers

Madhura Vyawahare
 Remove implications:

1. ∀x: graduating(x) → happy(x) 1. ∀x: ¬ graduating(x) V happy(x)

2. ∀x: happy(x) → smile(x) 2. ∀x: ¬ happy(x) V smile(x)
3. ∃x: graduating(x) 3. ∃x: graduating(x)
4. ¬ (∃x: smile(x)) 4. ¬ (∃x: smile(x))

Madhura Vyawahare
1. ∀x: graduating(x) → happy(x) Standardize variables:
2. ∀x: happy(x) → smile(x) 1. ∀x: ¬ graduating(x) V happy(x)
3. ∃x: graduating(x) 2. ∀y: ¬ happy(y) V smile(y)
4. ¬ (∃x: smile(x)) 3. ∃z: graduating(z)

Remove implications: 4. ¬ (∃w: smile(w))

1. ∀x: ¬ graduating(x) V happy(x)

2. ∀x: ¬ happy(x) V smile(x)

3. ∃x: graduating(x)
4. ¬ (∃x: smile(x))

Madhura Vyawahare
1. ∀x: graduating(x) → happy(x) Standardize variables:
2. ∀x: happy(x) → smile(x) 1. ∀x: ¬ graduating(x) V happy(x)
3. ∃x: graduating(x) 2. ∀y: ¬ happy(y) V smile(y)
4. ¬ (∃x: smile(x)) 3. ∃z: graduating(z)

Remove implications: 4. ¬ (∃w: smile(w))

1. ∀x: ¬ graduating(x) V happy(x) Move negation inverds and remove
2. ∀x: ¬ happy(x) V smile(x) quantifiers :
3. ∃x: graduating(x) 1. ¬ graduating(x) V happy(x)
4. ¬ (∃x: smile(x)) 2. ¬ happy(y) V smile(y)

3. graduating(z)
4. ¬ smile(w)
Madhura Vyawahare
Negate the statement which needs to prove (proof by contradiction)

In this statement, we will apply negation to the conclusion statements,

which will be written as
¬ smile(w)
1. Start with negation
2. Find contradicting rules
3. Contradiction is proved when it returns NULL

Madhura Vyawahare
Example

a. John likes all kind of food.

b. Apple and vegetable are food
c. Anything anyone eats and not killed is
food.
d. Anil eats peanuts and still alive
e. Harry eats everything that Anil eats.
f. John likes peanuts.

Madhura Vyawahare
Example Step 1. Conversion of facts into first-order
logic.

a. John likes all kind of food. a. ∀x: food(x) → likes(John, x)

b. Apple and vegetable are food b. food(Apple) Λ food(vegetables)
c. Anything anyone eats and not killed is c. ∀x ∀y : eats(x, y) Λ ¬ killed(x) →
food. food(y)
d. Anil eats peanuts and still alive d. eats (Anil, Peanuts) Λ alive(Anil)
e. Harry eats everything that Anil eats. e. ∀x eats(Anil, x) → eats(Harry, x)
f. John likes peanuts. f. likes(John,peanuts)

Madhura Vyawahare
FOL to CNF Conversion
Step 1. Conversion of facts into first-order logic. Step 2. Eliminate all implication (→) and rewrite

a. ∀x: food(x) → likes(John, x) a. ∀x ¬ food(x) V likes(John, x)

b. food(Apple) Λ food(vegetables) b. food(Apple) Λ food(vegetables)

c. ∀x ∀y : eats(x, y) Λ ¬ killed(x) → food(y) c. ∀x ∀y ¬ [eats(x, y) Λ ¬ killed(x)] V food(y)

d. eats (Anil, Peanuts) Λ alive(Anil) d. eats (Anil, Peanuts) Λ alive(Anil)

e. ∀x: eats(Anil, x) → eats(Harry, x) e. ∀x ¬ eats(Anil, x) V eats(Harry, x)

f. ∀x : ¬ killed(x) → alive(x) f. ∀x¬ [¬ killed(x) ] V alive(x)

g. ∀x: alive(x) → ¬ killed(x) g. ∀x ¬ alive(x) V ¬ killed(x)

h. likes(John,peanuts) h. likes(John, Peanuts).

Madhura Vyawahare
Move negation inwards
Step 3. Move negation (¬)inwards and rewrite
Step 2. Eliminate all implication (→) and rewrite

a. ∀x ¬ food(x) V likes(John, x) a. ∀x ¬ food(x) V likes(John, x)

b. food(Apple) Λ food(vegetables) b. food(Apple) Λ food(vegetables)

c. ∀x ∀y ¬ [eats(x, y) Λ ¬ killed(x)] V food(y) c. ∀x ∀y ¬ eats(x, y) V killed(x) V food(y)

d. eats (Anil, Peanuts) Λ alive(Anil) d. eats (Anil, Peanuts) Λ alive(Anil)

e. ∀x ¬ eats(Anil, x) V eats(Harry, x) e. ∀x ¬ eats(Anil, x) V eats(Harry, x)

f. ∀x¬ [¬ killed(x) ] V alive(x) f. ∀x killed(x) V alive(x)

g. ∀x ¬ alive(x) V ¬ killed(x) g. ∀x ¬ alive(x) V ¬ killed(x)

h. likes(John, Peanuts). h. likes(John, Peanuts).

Madhura Vyawahare
Rename/ standardize Variables
Step 3. Move negation (¬)inwards and rewrite Step 4. Rename variables or standardize variables

a. ∀x ¬ food(x) V likes(John, x) a. ∀x ¬ food(x) V likes(John, x)

b. food(Apple) Λ food(vegetables) b. food(Apple) Λ food(vegetables)
c. ∀x ∀y ¬ eats(x, y) V killed(x) V food(y) c. ∀y ∀z ¬ eats(y, z) V killed(y) V
d. eats (Anil, Peanuts) Λ alive(Anil) food(z)
e. ∀x ¬ eats(Anil, x) V eats(Harry, x) d. eats (Anil, Peanuts) Λ alive(Anil)
f. ∀x killed(x) V alive(x) e. ∀w¬ eats(Anil, w) V eats(Harry, w)
g. ∀x ¬ alive(x) V ¬ killed(x) f. ∀g killed(g) V alive(g)
h. likes(John, Peanuts). g. ∀k ¬ alive(k) V ¬ killed(k)
h. likes(John, Peanuts).
Madhura Vyawahare
Drop Universal Quantifiers
Step 4. Rename variables or standardize variables Step 5. Drop Universal quantifiers

a. ¬ food(x) V likes(John, x)
a. ∀x ¬ food(x) V likes(John, x)
b. food(Apple)
b. food(Apple) Λ food(vegetables) c. food(vegetables)

c. ∀y ∀z ¬ eats(y, z) V killed(y) V d. ¬ eats(y, z) V killed(y) V food(z)

e. eats (Anil, Peanuts)
food(z)
f. alive(Anil)
d. eats (Anil, Peanuts) Λ alive(Anil)
g. ¬ eats(Anil, w) V eats(Harry, w)
e. ∀w¬ eats(Anil, w) V eats(Harry, w) h. killed(g) V alive(g)
f. ∀g killed(g) V alive(g) i. ¬ alive(k) V ¬ killed(k)

g. ∀k ¬ alive(k) V ¬ killed(k) j. likes(John, Peanuts).

h. likes(John, Peanuts).
Madhura Vyawahare
Negate the statement which needs to prove (proof by contradiction)

In this statement, we will apply negation to the conclusion statements,

which will be written as
¬likes(John, Peanuts)
1. Start with negation
2. Find contradicting rules
3. Contradiction is proved when it returns NULL

Madhura Vyawahare
a. ¬ food(x) V likes(John, x)

b. food(Apple)

c. food(vegetables)

d. ¬ eats(y, z) V killed(y) V food(z)

e. eats (Anil, Peanuts)

f. alive(Anil)

g. ¬ eats(Anil, w) V eats(Harry, w)

h. killed(g) V alive(g)

i. ¬ alive(k) V ¬ killed(k)

j. likes(John, Peanuts).
Madhura Vyawahare
Explanation of Resolution Graph
○ In the first step of resolution graph, ¬likes(John, Peanuts) , and likes(John, x) get
resolved(canceled) by substitution of {Peanuts/x}, and we are left with ¬ food(Peanuts)
○ In the second step of the resolution graph, ¬ food(Peanuts) , and food(z) get resolved
(canceled) by substitution of { Peanuts/z}, and we are left with ¬ eats(y, Peanuts) V killed(y) .
○ In the third step of the resolution graph, ¬ eats(y, Peanuts) and eats (Anil, Peanuts) get
resolved by substitution {Anil/y}, and we are left with Killed(Anil) .
○ In the fourth step of the resolution graph, Killed(Anil) and ¬ killed(k) get resolve by
substitution {Anil/k}, and we are left with ¬ alive(Anil) .
○ In the last step of the resolution graph ¬ alive(Anil) and alive(Anil) get resolved.
Madhura Vyawahare
THE END

Madhura Vyawahare