Module 4: Knowledge and

Reasoning
CO: Use knowledge representation language to represent the given facts using prolog..

[Link] Vartak

1
Definition of Knowledge
• Knowledge in AI (Artificial Intelligence) means to have some
information saved in the memory from the prior experience of
something like any skills, objects or facts
• Knowledge can also refer to the capability of understanding or
experiencing a theoretical, logical or practical event. Knowledge can
be formal or informal. It can be systematic or particular. Similarly
knowledge can be some practical skill or expertise as well as it can be
theoretical understanding.

2
• There are many ways to acquire knowledge in AI. There are huge sources
available to acquire knowledge in AI. Some common sources of acquiring
knowledge:
• Perception
• Reason
• scientific inquiry
• Memory
• practice
• testimony
• learning

3
Types of Knowledge in AI

4
1. Declarative Knowledge:
• Declarative knowledge is to know about something.
• It includes concepts, facts, and objects.
• It is also called descriptive knowledge and expressed in declarative
sentences.
• It is simpler than procedural language.
• 2. Procedural Knowledge
• It is also known as imperative knowledge.
• Procedural knowledge is a type of knowledge which is responsible for
knowing how to do something.
• It can be directly applied to any task.
• It includes rules, strategies, procedures, agendas, etc.
• Procedural knowledge depends on the task on which it can be applied.

5
• Meta-knowledge:
• Knowledge about the other types of knowledge is called Meta-knowledge.
• Used to pick other knowledge that is best suited for solving problem.
• 4. Heuristic knowledge:
• Heuristic knowledge is representing knowledge of some experts in a filed or subject.
• Heuristic knowledge is rules of thumb based on previous experiences, awareness of
approaches, and which are good to work but not guaranteed.
• 5. Structural knowledge:
• Structural knowledge is basic knowledge to problem-solving.
• It describes relationships between various concepts such as kind of, part of, and grouping
of something.
• It describes the relationship that exists between concepts or objects.

6
AI knowledge cycle

• An Artificial intelligence system has the following components for

displaying intelligent behavior:
• Perception
• Learning
• Knowledge Representation and Reasoning
• Planning
• Execution

7
AI Knowledge Cycle

Execution

8
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. But how machines do all these things
comes under knowledge representation and reasoning. Hence we can describe
Knowledge representation as following:
• 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.

9
What to Represent:
• Following are the kind of knowledge which needs to be represented in AI
systems:
• Object: All the facts about objects in our world domain. E.g., Guitars
contains strings, trumpets are brass instruments.
• Events: Events are the actions which occur in our world.
• Performance: It describe behavior which involves knowledge about how to
do things.
• Meta-knowledge: It is knowledge about what we know.
• Facts: Facts are the truths about the real world and what we represent.
• Knowledge-Base: The central component of the knowledge-based agents is
the knowledge base. It is represented as KB. knowledge-base is required
for updating knowledge for an agent to learn with experiences and take
action as per the knowledge.

10
Issues in knowledge representation
• We need to consider five critical issues in knowledge
representations.
[Link] attributes
[Link] among attributes
[Link] the granularity of the representation
[Link] a set of objects
[Link] the proper structure as needed

11
Important Attributes
• There are some attributes which may occur in many different types of
problem.
• Consider, there are two instance and isa and each is important
because each supports property inheritance.
• So, this may be an attribute issue.

12
13
Relationship Among Attributes

• The relation among different attributes of an object is independent of

the specific knowledge they encode and hold properties like
• Inverse – We all know that entities in the world have various
relationships with each other. —for example, the relationship
between a chef, cooking, and a recipe.
• Existence in an ISA hierarchy – This refers to the importance of
generalizations and specifications for attributes as they support
inheritance. In other words, some things are more general, and some
things are more specific. This distinction helps the AI understand
things better. Like ‘color’ is a particular type of ‘appearance.’ It’s like
how ‘red’ is a type of ‘color’. .” The appearance attribute includes
physical characteristics such as color, texture, and shape. The color
attribute is a specific aspect of appearance and inherits properties
from the general attribute.
14
• techniques for reasoning about values – Here, we infer
understood values of attributes that we don’t need to state
explicitly. During this process, we use various types of
information. For example, weight must be in a unit of mass, and
a child’s age cannot be greater than the age of their parents. We
specify these values when first establishing a database.
• Single value attributes – This ensures that a particular attribute
has a singular value. For instance, a football player may only
have one specific jersey number and belong to a single
club. Knowledge representation systems use different ways to
deal with information with only one value, like when there’s only
one answer to a question.
15
Choosing the Granularity of
representation
• Now, at what level of depth do we want to go with the
knowledge representation?
• Before we represent knowledge, it is crucial to know the
following:
• High-level facts may not be adequate for inference, meaning
that storing broad facts and figures won’t give you proper
reasoning.
• On the other hand, low-level primitives need a lot of storage
because keeping every nitty gritty detail in the knowledge base
would take a lot of work.
16
• It’s better to plan and decide how much detail we need to remember
about something and the essential parts of that information. This
way, we only need a little memory storage for the AI to use that
information to make good guesses.
• Let’s try to understand this with an example. If we have the
information “Bob is driving a car,” we can represent this as “Bob,
agent, is driving, action, a car, object” this way, we can find out what
Bob is doing he is driving a car. Still, we can’t tell where he is going.
We need to add more information to answer this question, like “Bob
is driving to work.”
• With this extra information, we can infer that Bob is driving a car to
work

17
Representing Set of Objects

• When we put things together in a group, it’s important to

remember that some things might be valid for the whole group
but not for each item individually.”
• For example, “there are more cows than people in India” and
“Hindi speakers exist throughout the country.”
• We must attach the assertion to the sets representing people,
cows, and Hindi speakers to describe these facts.
• It’s more efficient to associate a property with a whole group
rather than each member. We can show information smartly or
in a way that groups things and makes them easy to understand.
18
Finding the Right Structure

• The question is how to ask for relevant information stored in a

database.
• This process is about figuring out how to organize information in
a way that works well. This method means choosing a good way
to start, adding new information when needed, and knowing
when to make a new system.
• How to find better structure if one chosen is not appropriate.

19
Properties of knowledge representation
system
• Representational adequacy → ability to represent the required knowledge
• Inferential Adequacy →ability to manipulate the knowledge represented
to produce new knowledge corresponding to that inferred from the
original

• Inferential Efficiency → ability to direct the inferential mechanisms into

the most productive directions by storing appropriate guides
• Acquisitional Efficiency → The ability to acquire new knowledge using
automatic methods wherever possible rather than reliance on human
intervention

20
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 but not both. It is a technique
of knowledge representation in logical and mathematical form.
• Logic → provides rules and techniques for determining whether a
given argument is valid.
Example:
a) The Sun rises from West (False proposition)
b)3+3= 7(False proposition)
c) 1+2=3(true proposition).
d) some students are intelligent( true or false)
21
Syntax
• The syntax of propositional logic defines the allowable sentences for
the knowledge representation. There are two types of Propositions:
[Link] Propositions
[Link] propositions/Complex

22
• 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
1. p=2+2 is 4, it is an atomic proposition as it is a true fact.
2. q="The Sun is cold" is also a proposition as it is a false fact.

23
Compound positions
• Compound propositions are constructed by combining simpler or
atomic propositions, using parenthesis and logical connectives.

Example:
•¬p → "It is not raining." (negation)
•p ∧ q → "It is raining AND the sky is cloudy." (conjunction)

24
Semantics
• Semantics define the meaning (truth value) of propositions and how
compound statements get their truth value.
• Truth Values
• Each atomic proposition is assigned either True (T) or False (F).
• The truth value of a compound proposition is determined using truth
tables.
• Examples
• Negation (¬p):
• If p = T → ¬p = F
• If p = F → ¬p = T

25
Formal logic connectives
Logical connectives are used to connect two simpler propositions or representing a
sentence logically.
• Negation: A sentence such as ¬ P is called negation of P. A literal can be either
Positive literal or negative literal. For example: ¬p: The sky is not blue.

• 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.
• 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.
26
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
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.

27
Truth tables
• We can combine all the possible combination with logical
connectives, and the representation of these combinations in a
tabular format is called Truth table.
• The truth table of the proposition depends on the truth value of its
variables

28
29
30
Tautology
• A tautology is a formula which is always true.
• And opposite known as contradiction.(always False)
• A proposition P (p, q, …..) is a tautology if it contains only T in the last
column of its truth table
• A proposition P(p,q…) is a contradiction if it contains only F in the last
column of its truth table

31
• Example: show that (p->q)V(q->p)

p q P->q q->p (p->q)V(q->p)

T T T T T
T F F T T
F T T F T
F F T T T

32
Validity
• An argument is a assertion such that for a given set of propostions P1.
P2….Pn called premises, gives rise to another proposition Q called the
conclusion
• And such an argument is denoted by P1, P2……Pn Q
• Valid → An argument P1, P2….Pn Q is said to be logical or valid if Q is
true whenever all the premises P1, P2…..Pn are true
• Fallacy → An argument which is not valid

33
Well formed formula
• A well-formed formula, abbreviated WFF or wff, often simply formula, is
a finite sequence of symbols from a given alphabet that is part of a formal
language
• Well-Formed Formula(WFF) is an expression consisting of variables(capital
letters), parentheses, and connective symbols.
• An expression is basically a combination of operands & operators and here
operands and operators are the connective symbols.

• Rules of the Well-Formed Formulas

1.A Statement variable standing alone is a Well-Formed Formula(WFF).
For example– Statements like P, ∼P, Q, ∼Q are themselves Well Formed Formulas.
[Link] ‘P’ is a WFF then ∼P is a formula as well.
[Link] P & Q are WFFs, then (P∨Q), (P∧Q), (P⇒Q), (P⇔Q), etc. are also WFFs.
34
35
PROLOG
• Programming in logic
• Declarative language, which means that a program consists of data
based on the facts and rules
• i.e. logical relationship

36
Prolog language basically has three different elements −

Facts − The fact is predicate that is true, for example, if we say, “Tom is the son of Jack”, then this is a fact.

Rules − Rules are extinctions of facts that contain conditional clauses. To satisfy a rule these conditions should
be met. For example, if we define a rule as −
grandfather(X, Y) :- father(X, Z), parent(Z, Y)
This implies that for X to be the grandfather of Y, Z should be a parent of Y and X should be father of Z.

Questions − And to run a prolog program, we need some questions, and those questions can be answered by the
given facts and rules.

37
• Knowledge Base − This is one of the fundamental parts of
Logic Programming.
• Facts, Rules and Queries − These are the building blocks of
logic programming

38
• Facts
• We can define fact as an explicit relationship between objects, and
properties these objects might have. So facts are unconditionally true
in nature. Suppose we have some facts as given below −
• Tom is a cat
• Kunal loves to eat Pasta
• Hair is black
• Nawaz loves to play games

39
Syntax
The syntax for facts is as follows −
relation(object1,object2...).
Example
Following is an example of the above concept −
cat(tom).
loves_to_eat(kunal,pasta).
of_color(hair,black).
loves_to_play_games(nawaz).
lazy(pratyusha).
40
41
• Rules
• We can define rule as an implicit relationship between objects. So facts are
conditionally true. So when one associated condition is true, then the predicate is
also true. Suppose we have some rules as given below −
• Jim is happy if she dances.
• Tom is hungry if he is searching for food.
• Jack and Bili are friends if both of them love to play cricket.
• Ryan will go to play if school is closed, and he is free.
• So these are some rules that are conditionally true, so when the right hand side
is true, then the left hand side is also true.
• Here the symbol ( :- ) will be pronounced as “If”, or “is implied by”. This is also
known as neck symbol, the LHS of this symbol is called the Head, and right
hand side is called Body. Here we can use comma (,) which is known as
conjunction, and we can also use semicolon, that is known as disjunction.

42
Example
• Jim is happy if she dances.
• Tom is hungry if he is searching for food.
• Jack and Bili are friends if both of them love to play cricket.
• Ryan will go to play if school is closed, and he is free.

happy(Jim) :- dances(Jim).

hungry(tom) :- search_for_food(tom).

friends(jack, bili) :- lovesCricket(jack), lovesCricket(bili).

goToPlay(ryan) :- isClosed(school), free(ryan)

43
• Queries
• Queries are some questions on the relationships between
objects and object properties. So question can be anything, as
given below −
• Is tom a cat?
• Does Kunal love to eat pasta?
• Is Lili happy?
• Will Ryan go to play?

44
Predicate Logic: FOPL
• 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.

45
• 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, ......
• 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

46
Syntax
• 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.
• Following are the basic elements of FOL syntax:
Constant 1, 2, A, John, Mumbai, cat,....
Variables x, y, z, a, b,....
Predicates Brother, Father, >,....
Function sqrt, LeftLegOf, ....
Connectives ∧, ∨, ¬, ⇒, ⇔
Equality ==
Quantifier ∀, ∃
47
Atomic 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.
• We can represent atomic sentences as Predicate (term1, term2, ......,
term n).
• Example: Ravi and Ajay are brothers: => Brothers(Ravi, Ajay).
tom is a cat: => cat (tom).

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

49
Quantifiers in First-order logic:

• A quantifier is a language element which generates quantification,

and quantification specifies the quantity of specimen in the universe
of discourse.
• 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:
• Universal Quantifier, (for all, everyone, everything)
• Existential quantifier, (for some, at least one).

50
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.
• Note: In universal quantifier we use implication "→".
• If x is a variable, then ∀x is read as:
• For all x
• For each x
• For every x.
• Example: All man drink coffee.
∀x man(x) → drink (x, coffee).

51
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.
• Note: In Existential quantifier we always use AND or Conjunction symbol
(∧).
• If x is a variable, then existential quantifier will be ∃x or ∃(x). And it will be read
as:
• There exists a 'x.'
• For some 'x.'
• For at least one 'x.'
• Example:
Some boys are intelligent.
∃x: boys(x) ∧ intelligent(x)

52
Some Examples of FOL
1. All birds fly.
∀x bird(x) →fly(x).

2. Some boys play cricket.

∃x boys(x) → play(x, cricket).

3. Not all students like both Mathematics and Science.

¬∀ (x) [ student(x) → like(x, Mathematics) ∧ like(x, Science)].

53
Inference
• Inference in FOPL is used to deduce new facts or sentences from
existing sentences
• Terminology
• Substitution → Fundamental operation performed on terms and
formulas
• It occurs in all inference systems in first order logic
• Eg: F[a/x] means in place of x we substitute a
• Equality → specify that two terms refer to the same subject
• Eg: Brother (Ramesh) = Ashok
54
 Inference Rules
1) Universal generalization → valid inference rule which states that if
premise P(c) is true for any arbitary element c, then we can have conclusion
as
For all x, P(x)
EG: P(c): A byte contains 8 bits
Means ∀x p(x): all bytes contain 8 bits
2) Universal Instantiation → universal elimination or UI
It can be applied multiple times to add new sentences
We can infer any sentence P(C) obtained by substituting a ground term c for
the variable
EG:
Every person like Ice-cream- ∀x p(x)
Means John like ice-cream- P(C)

55
3) Existential Instantiation
Existential elimination, applied only once to replace the existential sentence.
Eg. Someone has published a research paper.
Dr. Arjun has Published Research paper

4) Existential introduction
Existential generalization
IF there is some element c in the universe of discourse which has property P,
then we can infer that there exists something in the universe which has the
property P.
Eg. Pinky got good marks
Therefore , someone got good marks.

56
Forward chaining
• The system starts from a set of rules, a set of facts and tries to find a
way of using those rules and facts to deduce a conclusion or come up
with a suitable course of action
• Known as data driven reasoning because the reasoning starts from a
set of data and ends at the goal, which is the conclusion

57
Properties of Forward-Chaining:
• It is a down-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.

58
Steps
• 1) Take the facts in fact database and see if any combination of these
matches all the antecedents of one of the rules in the rule db
• 2) When all the antecedents of rule are matched by facts, then this
rule is triggered
• 3) Usually when a rule is triggered, it is fired, which means its
conclusion is added to the facts database

59
Example
• Example:
• it is a crime for an American to sell weapons to hostile nations. The
country Nono, an enemy America, has some missiles, and all of its
missiles were sold to it by Col. West, who is an American.

• Prove that Col. West is a criminal.

60
Solution
• Facts Conversion into FOL:
• …it is a crime for an American to sell weapons to hostile
nations
American(x) Weapon(y) Sells(x,y,z) Hostile(z)  Criminal(x)
• The country Nono, an enemy of America
Enemy(Nono, America)
• Nono…has some missiles
x Owns(Nono, x)  Missiles(x)
Owns(Nono, M1) and Missle(M1)
• …all of its missiles were sold to it by Col. West
x Missle(x)  Owns(Nono, x)  Sells( West, x, Nono)
• Missiles are weapons
Missle(x)  Weapon(x) 61
• An enemy of America counts as “hostile”
Enemy( x, America )  Hostile(x)

• Col. West who is an American

American( Col. West )

62
Proof

Step-1:
In the first step we will start with the known facts and will choose the sentences which do not have
implications, All facts will be represented as below.

63
Step-2:
At the second step, we will see those facts which infer from
available facts and with satisfied premises.

64
Step-3:

Hence it is proved that west col. is Criminal using forward

chaining approach
65
Backward chaining
• We start from a conclusion which is the hypothesis and we aim to
show how that conclusion can be reached from the rules and facts in
the database
• Called goal driven reasoning
• Based on modus ponens inference rule

66
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 used a depth-first search strategy
for proof.

67
Example same as forward chaining
Step-1:
At the first step, we will take the goal fact.

68
69
70
71
72
Semantic Networks
• Alternative to predicate logic as a form of knowledge representation
• Idea is that we can store our knowledge in the form of graphs, with
nodes representing objects in the world and arcs representing
relationship between those objects

73
Advantages
• They can represent default values of different categories
• Simple and easy to understand
• Easy to translate
• Represent relationships between nodes

• Limitations
• Lack of link names standards
• Node naming is not standard
• Answering negative query takes long time

74
Resolution and Unification
• IF various statements are given and we are required to state a
conclusion of those statements, then this process is called Resolution
• Resolution is a single inference rule which can efficiently operate on
the CNF
• Unification → key concept in proofs

75
Resolution Algorithm
• 1. Convert all the steps of F to clause form
• 2. Negate P and convert the result to clause form
• Add it to the set of clauses obtained in 1
• 3. Repeat until either a contradiction is found, no progress can be
made, or a predetermined amount of effort has been expected
• i. Select two clauses: call these the parent clause
• Ii. Resolve them together : Resolvent will be the disjunction of all
literal of both parent clauses with appropriate substitution performed
and with the following exception

76
• If there is one pair of literals T1 and –T2 such that one of parent
clauses contains T1, and other contains T2
• And if T1 and T2 are unifiable, then neither T1 nor T2 should appear
in the resolvent
• Use the substitution produced by the unification to create the
resolvent
• IF the resolvent is the empty clause, then a contradiction has been
found
• If it is not, then add it to the set of clauses available to the procedure

77
Unification
• Process of finding substitutions for lifted inference rules, which can
make different logical expressions to look similar
• Procedure for determining substitutions needed to make two first
order logic expression match

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

79
• Steps for Resolution:
[Link] of facts into first-order logic.
[Link] FOL statements into CNF
[Link] the statement which needs to prove (proof by contradiction)
[Link] resolution graph (unification).

80
Example:

[Link] likes all kind of food.

[Link] and vegetable are food
[Link] anyone eats and not killed is food.
[Link] eats peanuts and still alive
[Link] eats everything that Anil eats.
Prove by resolution that:
[Link] likes peanuts.

81
Step-1: Conversion of Facts
into FOL
In the first step we will
convert all the given
statements into its first
order logic.

82
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.
Rules:
i) Eliminate all implication (→) and rewrite
Example: a → b write ¬ a V b
a <-> b write a →b ∧ b →a
ii) Move negation (¬)inwards and rewrite
Example: ¬( ∀x P)= ∃x ¬P
¬( ∃ x P)= ∀x ¬P
¬(a Vb)=¬a ∧¬b
¬(a ∧ b)=¬a V¬b
¬¬a=a
iii)Rename variables or standardize variables
iv)Eliminate existential instantiation quantifier by elimination
Example: ∃x Rich(x)=Rich(G1)
v)Drop Universal quantifiers.
vi)Distribute conjunction ∧ over disjunction ¬.
83
i) 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)
e) alive(Anil)
f)∀x ¬ eats(Anil, x) V eats(Harry, x)
g)∀x¬ [¬ killed(x) ] V alive(x)
h)∀x ¬ alive(x) V ¬ killed(x)
i)likes(John, Peanuts).

84
ii) Move negation (¬)inwards and rewrite
a. ∀x ¬ food(x) V likes(John, x)
b. food(Apple) Λ food(vegetables)
c. ∀x ∀y ¬ eats(x, y) V killed(x) V food(y)
d. eats (Anil, Peanuts)
e. alive(Anil)
f. ∀x ¬ eats(Anil, x) V eats(Harry, x)
g. ∀x ¬[killed(x) ] V alive(x)
h. ∀x ¬ alive(x) V ¬ killed(x)
i. likes(John, Peanuts).

85
iii) Rename variables or standardize variables
a. ∀x ¬ food(x) V likes(John, x)
b. food(Apple) Λ food(vegetables)
c. ∀y ∀z ¬ eats(y, z) V killed(y) V food(z)
d. eats (Anil, Peanuts)
e. alive(Anil)
f. ∀w¬ eats(Anil, w) V eats(Harry, w)
g. ∀g ¬killed(g) ] V alive(g)
h. ∀k ¬ alive(k) V ¬ killed(k)
i. likes(John, Peanuts).

86
iv) Eliminate existential instantiation quantifier by elimination.
In this step, we will eliminate existential quantifier ∃, and this process is
known as Skolemization. But in this example problem since there is no
existential quantifier so all the statements will remain same in this step.

87
v) Drop Universal quantifiers.
In this step we will drop all universal quantifier since all the statements
are not implicitly quantified so we don't need it.
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).

88
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)

89
• Step-4: Draw Resolution graph:

90
Thank You

91