1

AL3391-ARTIFICIAL INTELLIGENCE

UNIT IV
LOGICAL REASONING
SYLLABUS

Knowledge-based agents – propositional logic – propositional theorem proving –

propositional model checking – agents based on propositional logic. First-order logic
– syntax and semantics – knowledge representation and engineering – inferences in
first-order logic – forward chaining – backward chaining – resolution.

INTRODUCTION

Reasoning:
The reasoning is the mental process of deriving logical conclusion and making
predictions from available knowledge, facts, and beliefs. Or we can say,
"Reasoning is a way to infer facts from existing data."
It is a general process of thinking rationally, to find valid conclusions.
In artificial intelligence, the reasoning is essential so that the machine can also
think rationally as a human brain, and can perform like a human.
When a system is required to do something, that it has not been explicitly told how
to do,, it must figure out what it needs to know from what it already knows.
Fact 1 : Robins are Birds
Fact 2 : All birds have wings
Question : Do Robins have wings?

Hence Reasoning system, must find out, what it needs to know from what it
already knows.
Logic is a language of reasoning. It is a collection of rules called logic arguments,
we use when doing logic reasoning.
Logical Reasoning is a process of drawing conclusions from premises using rule of
inference.

S.PRABU Associate Professor. AI&DS Department, KVCET

 2
AL3391-ARTIFICIAL INTELLIGENCE

Topic: 1 : 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
o 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.
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.

S.PRABU Associate Professor. AI&DS Department, KVCET

 3
AL3391-ARTIFICIAL INTELLIGENCE

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 (here 'sentence' is a technical term and it is not
identical to sentence in English).
These sentences are expressed in a language which is called a knowledge
representation language.
The Knowledge-base of KBA stores fact about the world.

Why use a knowledge base?

Knowledge-base is required for updating knowledge for an agent to learn with
experiences and take action as per the knowledge.

Inference system
Inference means deriving new sentences from old.
Inference system allows us to add a new sentence to the knowledge base.
A sentence is a proposition about the world. 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:
• Forward chaining
• Backward chaining

Operations Performed by KBA

Following are three operations which are performed by KBA in order to show the
intelligent behavior:
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. Perform: It performs the selected action.

S.PRABU Associate Professor. AI&DS Department, KVCET

 4
AL3391-ARTIFICIAL INTELLIGENCE

Various levels of knowledge-based agent:

A knowledge-based agent can be viewed at different levels which are given below:

1. Knowledge level
Knowledge level is the first level of knowledge-based agent, and in this level, we
need to specify what the agent knows, and what the agent goals are.
With these specifications, we can fix its behavior.
For example, suppose an automated taxi agent needs to go from a station A to
station B, and he knows the way from A to B, so this comes at the knowledge
level.

2. Logical level:
At this level, we understand that how the knowledge representation of knowledge
is stored.
At this level, sentences are encoded into different logics.
At the logical level, an encoding of knowledge into logical sentences occurs.
At the logical level we can expect to the automated taxi agent to reach to the
destination B.

3. Implementation level:
This is the physical representation of logic and knowledge.
At the implementation level agent perform actions as per logical and knowledge
level.
At this level, an automated taxi agent actually implements his knowledge and logic
so that he can reach to the destination.

Approaches to designing a knowledge-based agent:

There are mainly two approaches to build a knowledge-based agent:

1. Declarative approach:
We can create a knowledge-based agent by initializing with an empty
knowledge base and telling the agent all the sentences with which we want to
start with.
This approach is called Declarative approach.

S.PRABU Associate Professor. AI&DS Department, KVCET

 5
AL3391-ARTIFICIAL INTELLIGENCE

2. Procedural approach:
In the procedural approach, we directly encode desired behavior as a program
code.
Which means we just need to write a program that already encodes the desired
behavior or agent.
However, in the real world, a successful agent can be built by combining both
declarative and procedural approaches, and declarative knowledge can often be
compiled into more efficient procedural code.

Topic: 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) 3+3= 7(False proposition)
d) 5 is a prime number.

Following are some basic facts about propositional logic:

Propositional logic is also called Boolean logic as it works on 0 and 1.
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.
Propositions can be either true or false, but it cannot be both.
Propositional logic consists of an object, relations or function, and logical
connectives.
These connectives are also called logical operators.
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.

S.PRABU Associate Professor. AI&DS Department, KVCET

 6
AL3391-ARTIFICIAL INTELLIGENCE

Statements which are questions, commands, or opinions are not propositions

such as "Where is Rohini", "How are you", "What is your name", are not
propositions.

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
• 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:

S.PRABU Associate Professor. AI&DS Department, KVCET

 7
AL3391-ARTIFICIAL INTELLIGENCE

Following is the summarized table for Propositional Logic Connectives:

Truth Table:
In propositional logic, we need to know the truth values of propositions in all
possible scenarios.
We can combine all the possible combination with logical connectives, and the
representation of these combinations in a tabular format is called Truth table.
Following are the truth table for all logical connectives:

S.PRABU Associate Professor. AI&DS Department, KVCET

 8
AL3391-ARTIFICIAL INTELLIGENCE

S.PRABU Associate Professor. AI&DS Department, KVCET

 9
AL3391-ARTIFICIAL INTELLIGENCE

Topic: 3 : PROPOSITIONAL THEOREM PROVING

Logical equivalence:
Logical equivalence is one of the features of propositional logic.
Two propositions are said to be logically equivalent if and only if the columns in
the truth table are identical to each other.

S.PRABU Associate Professor. AI&DS Department, KVCET

 10
AL3391-ARTIFICIAL INTELLIGENCE

Let's take two propositions A and B, so for logical equivalence, we can write it as
A⇔B.
In below truth table we can see that column for ¬A∨ B and A→B, are identical
hence A is Equivalent to B

Properties of Operators:
• Commutativity:
o P∧ Q= Q ∧ P, or
o P ∨ Q = Q ∨ P.
• Associativity:
o (P ∧ Q) ∧ R= P ∧ (Q ∧ R),
o (P ∨ Q) ∨ R= P ∨ (Q ∨ R)
• Identity element:
o P ∧ True = P,
o P ∨ True= True.
• Distributive:
o P∧ (Q ∨ R) = (P ∧ Q) ∨ (P ∧ R).
o P ∨ (Q ∧ R) = (P ∨ Q) ∧ (P ∨ R).
• DE Morgan's Law:
o ¬ (P ∧ Q) = (¬P) ∨ (¬Q)
o ¬ (P ∨ Q) = (¬ P) ∧ (¬Q).
• Double-negation elimination:
o ¬ (¬P) = P.

S.PRABU Associate Professor. AI&DS Department, KVCET

 11
AL3391-ARTIFICIAL INTELLIGENCE

Topic: 4 : PROPOSITIONAL MODEL CHECKING

In this section, we describe two families of efficient algorithms for general

propositional inference based on model checking: One approach based on
backtracking search, and one on local hill-climbing search. These algorithms are part
of the “technology” of propositional logic. This section can be skimmed on a first
reading of the chapter

S.PRABU Associate Professor. AI&DS Department, KVCET

 12
AL3391-ARTIFICIAL INTELLIGENCE

Topic: 5 : AGENTS BASED ON PROPOSITIONAL LOGIC

S.PRABU Associate Professor. AI&DS Department, KVCET

 13
AL3391-ARTIFICIAL INTELLIGENCE

7.7.2 A hybrid agent

S.PRABU Associate Professor. AI&DS Department, KVCET

 14
AL3391-ARTIFICIAL INTELLIGENCE

S.PRABU Associate Professor. AI&DS Department, KVCET

 15
AL3391-ARTIFICIAL INTELLIGENCE

Topic: 6 : FIRST-ORDER LOGIC

First-order logic is symbolized reasoning in which each sentence, or statement, is

broken down into a subject and a predicate.
First-order logic can be useful in the creation of computer programs. It is also of
interest to researchers in artificial intelligence.

Features of First-order Predicate Logic

• More expressive and powerful representation
• Allows us to represent almost any English sentences.
• Generalization of propositional logic.

First-Order logic:
First-order logic is another way of knowledge representation in artificial
intelligence. It is an extension to propositional logic.
FOL is sufficiently expressive to represent the natural language statements in a
concise way.
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.
First-order logic (like natural language) does not only assume that the world
contains facts like propositional logic but also assumes the following things in the
world:
• Objects: A, B, people, numbers, colors, wars, theories, squares, pits,
wumpus, ......

S.PRABU Associate Professor. AI&DS Department, KVCET

 16
AL3391-ARTIFICIAL INTELLIGENCE

• 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
• Function: Father of, best friend, third inning of, end of, ......
As a natural language, first-order logic also has two main parts:
• Syntax
• Semantics

Syntax & Semantics

S.PRABU Associate Professor. AI&DS Department, KVCET

 17
AL3391-ARTIFICIAL INTELLIGENCE

S.PRABU Associate Professor. AI&DS Department, KVCET

 18
AL3391-ARTIFICIAL INTELLIGENCE

Topic: 7 : KNOWLEDGE REPRESENTATION AND ENGINEERING

The preceding section illustrated the use of first-order logic to represent knowledge in
three simple domains. This section describes the general process of knowledge-base
construction— a process called knowledge engineering. A knowledge engineer is
someone who investigates a particular domain, learns what concepts are important in
that domain, and creates a formal representation of the objects and relations in the
domain. We illustrate the knowledge engineering process in an electronic circuit
domain that should already be fairly familiar, so that we can concentrate on the
representational issues involved. The approach we take is suitable for developing

S.PRABU Associate Professor. AI&DS Department, KVCET

 19
AL3391-ARTIFICIAL INTELLIGENCE

special-purpose knowledge bases whose domain is carefully circumscribed and whose

range of queries is known in advance. General-purpose knowledge bases, which cover
a broad range of human knowledge and are intended to support tasks such as natural
language understanding

The knowledge-engineering process

Knowledge engineering projects vary widely in content, scope, and difficulty, but all
such projects include the following steps:

S.PRABU Associate Professor. AI&DS Department, KVCET

 20
AL3391-ARTIFICIAL INTELLIGENCE

S.PRABU Associate Professor. AI&DS Department, KVCET

 21
AL3391-ARTIFICIAL INTELLIGENCE

Topic: 8 : INFERENCES IN FIRST-ORDER LOGIC

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.

S.PRABU Associate Professor. AI&DS Department, KVCET

 22
AL3391-ARTIFICIAL INTELLIGENCE

Example: Brother (John) = Smith.

As in the above example, the object referred by the Brother (John) is similar to the
object referred by Smith. The equality symbol can also be used with negation to
represent that two terms are not the same objects.

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, so
following are some basic inference rules in FOL:
• Universal Generalization
• Universal Instantiation
• Existential Instantiation
• Existential introduction

1. Universal Generalization:
• 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).

• It can be represented as: .

• This rule can be used if we want to show that every element has a similar
property.
• In this rule, x must not appear as a free variable.
Example: Let's represent, P(c): "A byte contains 8 bits", so for ∀ x P(x) "All bytes
contain 8 bits.", it will also be true.

2. Universal Instantiation:
• 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.
• The new KB is logically equivalent to the previous KB.
• As per UI, we can infer any sentence obtained by substituting a ground
term for the variable.
• The UI rule state that we can infer any sentence P(c) by substituting a ground
term c (a constant within domain x) from ∀ x P(x) for any object in the
universe of discourse.

S.PRABU Associate Professor. AI&DS Department, KVCET

 23
AL3391-ARTIFICIAL INTELLIGENCE

• It can be represented as: .

• Example:1.
• IF "Every person like ice-cream"=> ∀x P(x) so we can infer that
"John likes ice-cream" => P(c)
• Example: 2.
• Let's take a famous example,
• "All kings who are greedy are Evil." So let our knowledge base contains this
detail as in the form of FOL:
∀x king(x) ∧ greedy (x) → Evil (x),
So from this information, we can infer any of the following statements using
Universal Instantiation:
• King(John) ∧ Greedy (John) → Evil (John),
• King(Richard) ∧ Greedy (Richard) → Evil (Richard),
• King(Father(John)) ∧ Greedy (Father(John)) → Evil (Father(John)),

3. Existential Instantiation:
• Existential instantiation is also called as Existential Elimination, which is a
valid inference rule in first-order logic.
• It can be applied only once to replace the existential sentence.
• The new KB is not logically equivalent to old KB, but it will be satisfiable if
old KB was satisfiable.
• 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.
• The restriction with this rule is that c used in the rule must be a new term for
which P(c ) is true.

• It can be represented as:

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.
• The above used K is a constant symbol, which is called Skolem constant.
• The Existential instantiation is a special case of Skolemization process.

S.PRABU Associate Professor. AI&DS Department, KVCET

 24
AL3391-ARTIFICIAL INTELLIGENCE

4. Existential introduction
• An existential introduction is also known as an existential generalization,
which is a valid inference rule in first-order logic.
• 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.

• It can be represented as:

• Example: Let's say that,
"Priyanka got good marks in English."
"Therefore, someone got good marks in English."

Topic: 9 : FORWARD AND BACKWARD CHAINING

Forward and Backward Chaining in Artificial Intelligence

Backward and forward chaining are methods of reasoning that exist in the Expert
System Domain of artificial intelligence.
These techniques are used in expert systems such as MYCIN and DENDRAL to
generate solutions to real life problems.
This article provides an overview of these techniques, and how they work. By the
end of the article, readers will have learned real life examples of how backward
and forward chaining are applied in artificial intelligence.

Introduction to the Expert System

A brief overview of an expert system can help us gain more insights on the origin
of backward and forward chaining in artificial intelligence.
An expert system is a computer application that uses rules, approaches, and facts
to provide solutions to complex problems.
Examples of expert systems include MYCIN and DENDRAL.
MYCIN uses the backward chaining technique to diagnose bacterial infections.
DENDRAL employs forward chaining to establish the structure of chemicals.

S.PRABU Associate Professor. AI&DS Department, KVCET

 25
AL3391-ARTIFICIAL INTELLIGENCE

There are three components in an expert system:

• user interface,
• inference engine, and
• knowledge base.
The user interface enables users of the system to interact with the expert system.
High-quality and domain-specific knowledge is stored in the knowledge base.
Backward and forward chaining stem from the inference engine component.
This is a component in which logical rules are applied to the knowledge base to get
new information or make a decision.
The backward and forward chaining techniques are used by the inference engine as
strategies for proposing solutions or deducing information in the expert system.

Forward chaining
Forward chaining is a method of reasoning in artificial intelligence in which inference
rules are applied to existing data to extract additional data until an endpoint (goal) is
achieved.
In this type of chaining, the inference engine starts by evaluating existing facts,
derivations, and conditions before deducing new information. An endpoint (goal) is
achieved through the manipulation of knowledge that exists in the knowledge base.

S.PRABU Associate Professor. AI&DS Department, KVCET

 26
AL3391-ARTIFICIAL INTELLIGENCE

forward chaining can be used in planning, monitoring, controlling, and interpreting

applications.

Properties of forward chaining

• The process uses a down-up approach (bottom to top).
• It starts from an initial state and uses facts to make a conclusion.
• This approach is data-driven.
• It’s employed in expert systems and production rule system.

Examples of forward chaining

A simple example of forward chaining can be explained in the following sequence.
A
A->B
B
A is the starting point. A->B represents a fact.
This fact is used to achieve a decision B.

A practical example will go as follows;

Tom is running (A)
If a person is running, he will sweat (A->B)
Therefore, Tom is sweating. (B)
A DENDRAL expert system is a good example of how forward chaining is used in
artificial intelligence.
DENDRAL is used in the prediction of the molecular structure of substances.
Deducing the chemical structure starts by finding the number of atoms in every
molecule.

S.PRABU Associate Professor. AI&DS Department, KVCET

 27
AL3391-ARTIFICIAL INTELLIGENCE

The mass spectrum of the sample is then used to establish the arrangement of the
atoms.
We can summarize these steps as follows.
• The chemical formula is determined ( the number of atoms in every
molecule).
• The spectrum machine is used to form mass spectrums of the sample.
• The isomer and structure of the chemical are identified.
In this example, the identification of the chemical structure is the endpoint.
In the DENDRAL expert system, a generate and test technique is employed.
There are two elements in the generator:
• a synthesizer and
• structural enumerator.
The synthesizer plays the role of producing the mass spectrum.
The structural enumerator identifies the structure of substances and prevents
redundancy in the generator.

Advantages
• It can be used to draw multiple conclusions.
• It provides a good basis for arriving at conclusions.
• It’s more flexible than backward chaining because it does not have a limitation
on the data derived from it.

Disadvantages
• The process of forward chaining may be time-consuming. It may take a lot of
time to eliminate and synchronize available data.
• Unlike backward chaining, the explanation of facts or observations for this type
of chaining is not very clear. The former uses a goal-driven method that arrives
at conclusions efficiently.

Backward chaining
Backward chaining is a concept in artificial intelligence that involves backtracking
from the endpoint or goal to steps that led to the endpoint.

S.PRABU Associate Professor. AI&DS Department, KVCET

 28
AL3391-ARTIFICIAL INTELLIGENCE

This type of chaining starts from the goal and moves backward to comprehend the
steps that were taken to attain this goal.
The backtracking process can also enable a person establish logical steps that can
be used to find other important solutions.

Backward chaining can be used in debugging, diagnostics, and prescription

applications.

Properties of backward chaining

• The process uses an up-down approach (top to bottom).
• It’s a goal-driven method of reasoning.
• The endpoint (goal) is subdivided into sub-goals to prove the truth of facts.
• A backward chaining algorithm is employed in inference engines, game
theories, and complex database systems.
• The modus ponens inference rule is used as the basis for the backward chaining
process. This rule states that if both the conditional statement (p->q) and the
antecedent (p) are true, then we can infer the subsequent (q).

Example of backward chaining

The information provided in the previous example (forward chaining) can be used to
provide a simple explanation of backward chaining. Backward chaining can be
explained in the following sequence.

B
A->B
A

S.PRABU Associate Professor. AI&DS Department, KVCET

 29
AL3391-ARTIFICIAL INTELLIGENCE

B is the goal or endpoint, that is used as the starting point for backward tracking.
A is the initial state. A->B is a fact that must be asserted to arrive at the endpoint
B.
A practical example of backward chaining will go as follows:
Tom is sweating (B).
If a person is running, he will sweat (A->B).
Tom is running (A).
The MYCIN expert system is a real life example of how backward chaining works.
This is a system that’s used in the diagnosis of bacterial infections.
It also recommends suitable treatments for this type of infections.
The knowledge base of a MYCIN comprises many antecedent-consequent rules,
that enable the system to recognize various causes of (bacterial) infections.
This system is suitable for patients who have a bacterial infection, but don’t know
the specific infection.
The system will gather information relating to symptoms and history of the patient.
It will then analyze this information to establish the bacterial infection.
A suitable sequence can be as follows:
• The patient has a bacterial infection.
• The patient is vomiting.
• He/she is also experiencing diarrhea and severe stomach upset.
• Therefore, the patient has typhoid (salmonella bacterial infection).
The MYCIN expert system uses the information collected from the patient to
recommend suitable treatment.
The recommended treatment corresponds to the identified bacterial infection. In
the case above, the system may recommend the use of ciprofloxacin.

Advantages
• The result is already known, which makes it easy to deduce inferences.
• It’s a quicker method of reasoning than forward chaining because the endpoint
is available.
• In this type of chaining, correct solutions can be derived effectively if pre-
determined rules are met by the inference engine.
Disadvantages
• The process of reasoning can only start if the endpoint is known.
• It doesn’t deduce multiple solutions or answers.

S.PRABU Associate Professor. AI&DS Department, KVCET

 30
AL3391-ARTIFICIAL INTELLIGENCE

• It only derives data that is needed, which makes it less flexible than forward
chaining.

Thus,
Backward and forward chaining are important methods of reasoning in artificial
intelligence.
These concepts differ mainly in terms of approach, strategy, technique, speed, and
operational direction.
Forward chaining is important to developers that want to use data-driven
algorithms to develop effective computer-based systems.
Backward chaining is important to developers that are interested in using goal-
driven algorithms to design effective solutions in complex database systems.

Topic: 10 : RESOLUTION

Resolution is a theorem proving technique that proceeds by building refutation

proofs, i.e., proofs by contradictions.
It was invented by a Mathematician John Alan Robinson in the year 1965.
Resolution is used, if there are various statements are given, and we need to prove
a conclusion of those statements.
Unification is a key concept in proofs by resolutions. 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.

S.PRABU Associate Professor. AI&DS Department, KVCET

 31
AL3391-ARTIFICIAL INTELLIGENCE

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 (unification).
To better understand all the above steps, we will take an example in which we will
apply resolution.
Example:
• John likes all kind of food.
• Apple and vegetable are food
• Anything anyone eats and not killed is food.
• Anil eats peanuts and still alive
• Harry eats everything that Anil eats.

Prove by resolution that:

• John likes peanuts.

Step-1: Conversion of Facts into FOL

In the first step we will convert all the given statements into its first order logic.

Step-2: Conversion of FOL into CNF

In First order logic resolution, it is required to convert the FOL into CNF as CNF form
makes easier for resolution proofs.

S.PRABU Associate Professor. AI&DS Department, KVCET

 32
AL3391-ARTIFICIAL INTELLIGENCE

Eliminate all implication (→) and rewrite

a. ∀x ¬ food(x) V likes(John, x)
b. food(Apple) Λ food(vegetables)
c. ∀x ∀y ¬ [eats(x, y) Λ ¬ killed(x)] V food(y)
d. eats (Anil, Peanuts) Λ alive(Anil)
e. ∀x ¬ eats(Anil, x) V eats(Harry, x)
f. ∀x¬ [¬ killed(x) ] V alive(x)
g. ∀ x ¬ alive(x) V ¬ killed(x)
h. likes(John, Peanuts).

Move negation (¬)inwards and rewrite

• ∀ x ¬ food(x) V likes(John, x)
• food(Apple) Λ food(vegetables)
• ∀ x ∀ y ¬ eats(x, y) V killed(x) V food(y)
• eats (Anil, Peanuts) Λ alive(Anil)
• ∀ x ¬ eats(Anil, x) V eats(Harry, x)
• ∀ x ¬killed(x) ] V alive(x)
• ∀ x ¬ alive(x) V ¬ killed(x)
• likes(John, Peanuts).
Rename variables or standardize variables
• ∀ x ¬ food(x) V likes(John, x)
• food(Apple) Λ food(vegetables)
• ∀ y ∀ z ¬ eats(y, z) V killed(y) V food(z)
• eats (Anil, Peanuts) Λ alive(Anil)
• ∀ w¬ eats(Anil, w) V eats(Harry, w)
• ∀ g ¬killed(g) ] V alive(g)
• ∀ k ¬ alive(k) V ¬ killed(k)
• likes(John, Peanuts).

Step-3: Negate the statement to be proved

In this statement, we will apply negation to the conclusion statements, which will be
written as ¬likes(John, Peanuts)

Step-4: Draw Resolution graph:

S.PRABU Associate Professor. AI&DS Department, KVCET

 33
AL3391-ARTIFICIAL INTELLIGENCE

Now in this step, we will solve the problem by resolution tree using substitution. For
the above problem, it will be given as follows:

Hence the negation of the conclusion has been proved as a complete contradiction
with the given set of statements.

S.PRABU Associate Professor. AI&DS Department, KVCET