Principles of Artificial Intelligence (21AI54) Module 4

MODULE 4
Chapter 1 – First Order Logic
1. Representation Revisited
2. Syntax and Semantics of First Order Logic
3. Using First Order Logic

Representation Revisited
Difference between Propositional Logic and Predicate / First Order Logic

Department of AI&ML, CIT - Ponnampet Page 1

Principles of Artificial Intelligence (21AI54) Module 2
Combining the best of formal and natural languages
➢ The language of first-order logic, is built around objects and relations.
➢ It has been so important to mathematics, philosophy, and artificial intelligence
precisely because those fields and indeed, much of everyday human existence can
be usefully thought of as dealing with objects and the relations among them.
➢ First-order logic can also express facts about some or all of the objects in the
universe.
➢ When we look at the syntax of natural language, the most obvious elements are
nouns and noun phrases that refer to objects (squares, pits, wumpuses) and verbs
and verb phrases that refer to relations among objects (is breezy, is adjacent to,
shoots).
➢ Some of these relations are functions—relations in which there is only one “value”
for a given “input.”
➢ It is easy to start listing examples of objects, relations, and functions.
1. Objects: people, houses, numbers, theories, Ronald McDonald, colors,
baseball games, wars, centuries ...
2. Relations: these can be unary relations or properties such as red, round,
bogus, prime, multistoried ..., or more general n-ary relations such as
brother of, bigger than, inside, part of, has color, occurred after, owns,
comes between, ...
3. Functions: father of, best friend, third inning of, one more than, beginning
of ...
➢ Examples:
1. “One plus two equals three.”
Objects: one, two, three, one plus two;
Relation: equals;
Function: plus. (“One plus two” is a name for the object that is obtained by
applying the function “plus” to the objects “one” and “two.” “Three” is
another name for this object.)
2. “Squares neighboring the wumpus are smelly.”
Objects: wumpus, squares;
Property: smelly;
Relation: neighboring.
3. “Evil King John ruled England in 1200.”
Objects: John, England, 1200;

Department of AI&ML, CIT - Ponnampet Page 2

Principles of Artificial Intelligence (21AI54) Module 4
Relation: ruled;
Properties: evil, king.

Syntax and Semantics of First Order Logic

Models for First Order Logic
➢ The models of a logical language are the formal structures that constitute the
possible worlds under consideration.
➢ Each model links the vocabulary of the logical sentences to elements of the possible
world, so that the truth of any sentence can be determined.
➢ Thus, models for propositional logic link proposition symbols to predefined truth
values.
➢ The domain of a model is the set of objects or domain elements it contains.
➢ The domain is required to be nonempty—every possible world must contain at least
one object.
➢ Figure 8.2 shows a model with five objects: Richard the Lionheart, King of England
from 1189 to 1199; his younger brother, the evil King John, who ruled from 1199
to 1215; the left legs of Richard and John; and a crown.

➢ The objects in the model may be related in various ways.

➢ In the figure, Richard and John are brothers.
➢ Formally speaking, a relation is just the set of tuples of objects that are related. (A
tuple is a collection of objects arranged in a fixed order and is written with angle
brackets surrounding the objects.)
➢ Thus, the brotherhood relation in this model is the set,
{ < Richard the Lionheart, King John >, < King John, Richard the Lionheart > }

Department of AI&ML, CIT - Ponnampet Page 3

Principles of Artificial Intelligence (21AI54) Module 2
➢ The crown is on King John’s head, so the “on head” relation contains just one tuple,
< the crown, King John >.
➢ The “brother” and “on head” relations are binary relations—that is, they relate pairs
of objects.
➢ The model also contains unary relations, or properties: the “person” property is true
of both Richard and John; the “king” property is true only of John (presumably
because Richard is dead at this point); and the “crown” property is true only of the
crown.
➢ Certain kinds of relationships are best considered as functions, in that a given object
must be related to exactly one object in this way.
➢ For example, each person has one left leg, so the model has a unary “left leg”
function that includes the following mappings:
< Richard the Lionheart > → Richard’s left leg
< King John > → John’s left leg.

Symbols and Interpretations

➢ The basic syntactic elements of first-order logic are the symbols that stand for
objects, relations, and functions.
➢ The symbols, therefore, come in three kinds:
1. Constant symbols, which stand for objects;
2. Predicate symbols, which stand for relations; and
3. Function symbols, which stand for functions.
➢ We adopt the convention that these symbols will begin with uppercase letters.
➢ For example, we might use the constant symbols Richard and John; the predicate
symbols Brother, OnHead, Person, King, and Crown; and the function symbol
LeftLeg.
➢ As in propositional logic, every model must provide the information required to
determine if any given sentence is true or false.
➢ Thus, in addition to its objects, relations, and functions, each model includes an
interpretation that specifies exactly which objects, relations and functions are
referred to by the constant, predicate, and function symbols.
➢ One possible interpretation for our example is as follows:
1. Richard refers to Richard the Lionheart and John refers to the evil King John.
2. Brother refers to the brotherhood relation between Richard and John; OnHead
refers to the “on head” relation that holds between the crown and King John;

Department of AI&ML, CIT - Ponnampet Page 4

Principles of Artificial Intelligence (21AI54) Module 4
Person, King, and Crown refer to the sets of objects that are persons, kings,
and crowns.
3. LeftLeg refers to the “left leg” function, that maps to either John’s left leg or
Richard’s left leg.
➢ The below figure shows the Backus – Naur Form (BNF) of First order Logic.

Terms
➢ A term is a logical expression that refers to an object.
➢ Constant symbols are therefore terms, but it is not always convenient to have a
distinct symbol to name every object.
➢ For example, in English we might use the expression “King John’s left leg” rather
than giving a name to his leg.
➢ This is what function symbols are for: instead of using a constant symbol, we use
LeftLeg(John).

Department of AI&ML, CIT - Ponnampet Page 5

Principles of Artificial Intelligence (21AI54) Module 2
➢ In the general case, a complex term is formed by a function symbol followed by a
parenthesized list of terms as arguments to the function symbol.

Atomic Sentences
➢ An atomic sentence (or atom for short) is formed from a predicate symbol
optionally followed by a parenthesized list of terms, such as,
Brother (Richard, John)
This states, that Richard the Lionheart is the brother of King John.
➢ Atomic sentences can have complex terms as arguments.
Married (Father (Richard), Mother (John)) states that Richard the Lionheart’s
father is married to King John’s mother.

Complex Sentences
➢ We can use logical connectives to construct more complex sentences, with the same
syntax and semantics as in propositional calculus.
➢ Here are four sentences that are true in the model of Figure 8.2 under our intended
interpretation:

Quantifiers
First-order logic contains two standard quantifiers, called universal and existential.
Universal quantification (∀)
➢ Rules such as “Squares neighboring the wumpus are smelly” and “All kings are
persons” are the bread and butter of first-order logic.
➢ The second rule, “All kings are persons,” is written in first-order logic as,
∀x King(x) ⇒ Person(x)
∀ is usually pronounced “For all ...”.
➢ Thus, the sentence says, “For all x, if x is a king, then x is a person.”
➢ The symbol x is called a variable.
➢ By convention, variables are lowercase letters.
➢ A variable is a term all by itself, and as such can also serve as the argument of a
function—for example, LeftLeg(x).
➢ A term with no variables is called a ground term.

Department of AI&ML, CIT - Ponnampet Page 6

Principles of Artificial Intelligence (21AI54) Module 4
➢ The sentence ∀x P, where P is any logical expression, says that P is true for every
object x.
➢ More precisely, ∀x P is true in a given model if P is true in all possible extended
interpretations constructed from the interpretation given in the model, where each
extended interpretation specifies a domain element to which x refers to:
x → Richard the Lionheart,
x → King John,
x → Richard’s left leg,
x → John’s left leg,
x → the crown.
➢ The universally quantified sentence ∀ x King(x) ⇒ Person(x) is true in the original
model if the sentence King(x) ⇒ Person(x) is true under each of the five extended
interpretations.
➢ That is, the universally quantified sentence is equivalent to asserting the following
five sentences:
Richard the Lionheart is a king ⇒ Richard the Lionheart is a person.
King John is a king ⇒ King John is a person.
Richard’s left leg is a king ⇒ Richard’s left leg is a person.
John’s left leg is a king ⇒ John’s left leg is a person.
The crown is a king ⇒ the crown is a person.
➢ Since, in our model, King John is the only king, the second sentence asserts that he
is a person.

Existential quantification (∃)

➢ Universal quantification makes statements about every object.
➢ Similarly, we can make a statement about some object in the universe without
naming it, by using an existential quantifier.
➢ To say, for example, that King John has a crown on his head, we write
Ǝx Crown(x) ∧ OnHead(x, John)
∃x is pronounced “There exists an x such that ...” or “For some x...”.
➢ The sentence ∃x P says that P is true for at least one object x.
➢ More precisely, ∃x P is true in a given model if P is true in at least one extended
interpretation that assigns x to a domain element. That is, at least one of the
following is true:
Richard the Lionheart is a crown ∧ Richard the Lionheart is on John’s head;
King John is a crown ∧ King John is on John’s head;

Department of AI&ML, CIT - Ponnampet Page 7

Principles of Artificial Intelligence (21AI54) Module 2
Richard’s left leg is a crown ∧ Richard’s left leg is on John’s head;
John’s left leg is a crown ∧ John’s left leg is on John’s head;
The crown is a crown ∧ the crown is on John’s head.
➢ The fifth assertion is true in the model, so the original existentially quantified
sentence is true in the model.
➢ Just as ⇒ appears to be the natural connective to use with ∀, ∧ is the natural
connective to use with ∃.

Nested Quantifiers
➢ The simplest case is where the quantifiers are of the same type.
➢ For example, “Brothers are siblings” can be written as,
∀x ∀y Brother(x, y) ⇒ Sibling(x, y)
➢ Consecutive quantifiers of the same type can be written as one quantifier with
several variables.
➢ For example, to say that siblinghood is a symmetric relationship, we can write,
∀x,y Sibling(x, y) ⇔ Sibling(y, x)
➢ In other cases we will have mixtures. “Everybody loves somebody” means that for
every person, there is someone that person loves:
∀x Ǝy Loves(x, y).
➢ On the other hand, to say “There is someone who is loved by everyone,” we write
Ǝy ∀x Loves(x, y).
➢ The order of quantification is therefore very important.
➢ It becomes clearer if we insert parentheses.
➢ ∀ x (Ǝy Loves(x, y)) says that everyone has a particular property, namely, the
property that they love someone.

Connections between ∀ and ∃

➢ The two quantifiers are actually intimately connected with each other, through
negation.
➢ Asserting that “everyone dislikes parsnips” is the same as asserting “there does not
exist someone who likes them”, and vice versa:
∀ x ¬Likes (x, Parsnips) is equivalent to ¬∃ x Likes (x, Parsnips)
➢ “Everyone likes ice cream” means that there is no one who does not like ice cream:
∀ x Likes(x, IceCream) is equivalent to ¬∃ x ¬Likes(x, IceCream)
➢ The De Morgan rules for quantified and unquantified sentences are as follows:

Department of AI&ML, CIT - Ponnampet Page 8

Principles of Artificial Intelligence (21AI54) Module 4

Equality
➢ First-order logic includes one more way to make atomic sentences, other than using
a predicate and terms as described earlier.
➢ We can use the equality symbol to signify that two terms refer to the same object.
For example, Father (John) = Henry
says that the object referred to by Father (John) and the object referred to by Henry
are the same.
➢ One proposal that is very popular in database systems works as follows.
➢ First, we insist that every constant symbol refer to a distinct object—the so called
unique-names assumption.
➢ Second, we assume that atomic sentences not known to be true are in fact false the
closed-world assumption.
➢ To say that Richard has at least two brothers, we would write
∃ x,y Brother (x, Richard) ∧ Brother (y, Richard) ∧ ¬(x = y)

Using First Order Logic

Assertions and queries in first-order logic
➢ Sentences are added to a knowledge base using TELL, exactly as in propositional
logic. Such sentences are called assertions.
➢ For example, we can assert that John is a king, Richard is a person, and all kings
are persons:
TELL(KB, King(John))
TELL(KB, Person(Richard))
TELL(KB, ∀ x King(x) ⇒ Person(x)).
➢ We can ask questions of the knowledge base using ASK. For example,
ASK(KB, King(John)) returns true.
➢ Questions asked with ASK are called queries or goals.
➢ Given the two preceding assertions, the query ASK(KB, Person(John)) should also
return true.
➢ We can ask quantified queries, such as ASK(KB, ∃x Person(x)) . The answer is
true.

Department of AI&ML, CIT - Ponnampet Page 9

Principles of Artificial Intelligence (21AI54) Module 2
➢ If we want to know what value of x makes the sentence true, we will need a different
function, ASKVARS, which we call with,
ASKVARS(KB, Person(x)) and which yields a stream of answers.
➢ In this case there will be two answers: {x/John} and {x/Richard}.
➢ Such an answer is called a substitution or binding list.

The Kinship domain

➢ Consider the domain of family relationships, or kinship.
➢ This domain includes facts such as “Elizabeth is the mother of Charles” and
“Charles is the father of William” and rules such as “One’s grandmother is the
mother of one’s parent.”
➢ Clearly, the objects in our domain are people.
➢ We have two unary predicates, Male and Female.
➢ Kinship relations—parenthood, brotherhood, marriage, and so on—are represented
by binary predicates: Parent, Sibling, Brother, Sister, Child, Daughter, Son, Spouse,
Wife, Husband, Grandparent, Grandchild, Cousin, Aunt, and Uncle.
➢ We use functions for Mother and Father, because every person has exactly one of
each of these.

Department of AI&ML, CIT - Ponnampet Page 10

Principles of Artificial Intelligence (21AI54) Module 4
The Wumpus World
➢ The wumpus agent receives a percept vector with five elements.
➢ The corresponding first-order sentence stored in the knowledge base must include
both the percept and the time at which it occurred; otherwise, the agent will get
confused about when it saw what.
➢ We use integers for time steps.
➢ A typical percept sentence would be
Percept ([Stench, Breeze, Glitter, None, None], 5).
Here, Percept is a binary predicate, and Stench and so on are constants placed in a
list.
➢ The actions in the wumpus world can be represented by logical terms: Turn(Right),
Turn(Left), Forward, Shoot, Grab, Climb.
➢ To determine which is best, the agent program executes the query,
ASKVARS (∃ a BestAction(a, 5))
which returns a binding list such as {a/Grab}.
➢ The agent program can then return Grab as the action to take.

Department of AI&ML, CIT - Ponnampet Page 11

Principles of Artificial Intelligence (21AI54) Module 4

MODULE 4
Chapter 2 – Inference in First Order Logic
1. Propositional versus First Order Inference
2. Unification
3. Forward Chaining
4. Backward Chaining
5. Resolution

Unification
➢ Lifted inference rules require finding substitutions that make different logical
expressions look identical.
➢ This process is called unification and is a key component of all first-order inference
algorithms.
➢ The UNIFY algorithm takes two sentences and returns a unifier for them if one
exists,
UNIFY(p, q) = θ where SUBST(θ, p) = SUBST(θ, q)
Example:
➢ Suppose we have a query AskVars(Knows(John, x)) and answers to this query can
be found by finding all sentences in the knowledge base that unify with
Knows(John, x).
➢ Here are the results of unification with four different sentences that might be in the
knowledge base: (Find MGU of the following)
UNIFY(Knows(John, x), Knows(John, Jane)) = {x/Jane}
UNIFY(Knows(John, x), Knows(y, Bill)) = {x/Bill, y/John}
UNIFY(Knows(John, x), Knows(y, Mother (y))) = {y/John, x/Mother(John)}
UNIFY(Knows(John, x), Knows(x, Elizabeth)) = fail.
➢ The last unification fails because x cannot take on the values John and Elizabeth at
the same time.
➢ Knows(x,Elizabeth) means “Everyone knows Elizabeth,” so we should be able to
infer that John knows Elizabeth.
➢ The problem arises only because the two sentences happen to use the same variable
name, x.
➢ The problem can be avoided by standardizing apart one of the two sentences being
unified, which means renaming its variables to avoid name clashes.

Department of AI&ML, CIT - Ponnampet Page 1

Principles of Artificial Intelligence (21AI54) Module 2
➢ For example, we can rename x in Knows(x,Elizabeth) to x17 (a new variable name)
without changing its meaning. Now the unification will work:
UNIFY(Knows(John, x), Knows(x17,Elizabeth)) = {x/Elizabeth, x17/John}
➢ There is one more complication: we said that UNIFY should return a substitution
that makes the two arguments look the same.
➢ But there could be more than one such unifier.
➢ For example, UNIFY(Knows(John, x), Knows(y, z)) could return {y/John, x/z} or
{y/John, x/John, z/John}.
➢ The first unifier gives Knows(John, z) as the result of unification, whereas the
second gives Knows(John, John).
➢ The second result could be obtained from the first by an additional substitution
{z/John}; we say that the first unifier is more general than the second, because it
places fewer restrictions on the values of the variables.
➢ It turns out that, for every unifiable pair of expressions, there is a single Most
General Unifier (or MGU) that is unique up to renaming and substitution of
variables. (For example, {x/John} and {y/John} are considered equivalent, as are
{x/John, y/John} and {x/John, y/x}.) In this case it is {y/John, x/z}.
➢ An algorithm for computing most general unifiers is shown in Figure 9.1.

➢ The process is simple: recursively explore the two expressions simultaneously “side
by side,” building up a unifier along the way, but failing if two corresponding points
in the structures do not match.
➢ There is one expensive step: when matching a variable against a complex term, one
must check whether the variable itself occurs inside the term; if it does, the match
fails because no consistent unifier can be constructed.

Department of AI&ML, CIT - Ponnampet Page 2

Principles of Artificial Intelligence (21AI54) Module 4

Forward Chaining
➢ The idea is simple start with the atomic sentences in the knowledge base and apply
Modus Ponens in the forward direction, adding new atomic sentences, until no
further inferences can be made.
➢ Here, we explain how the algorithm is applied to first-order definite clauses.

First - order definite clauses

➢ A definite clause either is atomic or is an implication whose antecedent is a
conjunction of positive literals and whose consequent is a single positive literal.
➢ The following are first-order definite clauses:
King(x) ^ Greedy(x) ⇒ Evil(x)
King(John)
Greedy(y)
➢ Unlike propositional literals, first-order literals can include variables, in which case
those variables are assumed to be universally quantified.
➢ The below algorithm illustrates the working of Forward chaining algorithm.

Problem:
The law says that it is a crime for an American to sell weapons to hostile nations. The
country Nono, an enemy of America, has some missiles, and all of its missiles were
sold to it by Colonel West, who is American. Prove that “West is a criminal” using
Forward chaining algorithm.
Solution:
Step 1: First, we will represent these facts as first - order definite clauses.
1. “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) ---------→ (1)

Department of AI&ML, CIT - Ponnampet Page 3

Principles of Artificial Intelligence (21AI54) Module 2
2. “Nono ... has some missiles.”
The sentence ∃ x Owns(Nono, x) ∧ Missile(x) is transformed into two definite
clauses by Existential Instantiation, introducing a new constant M1:
Owns(Nono, M1) ---------→ (2)
Missile(M1) --------------→ (3)
3. “All of its missiles were sold to it by Colonel West”:
Missile(x) ∧ Owns(Nono, x) ⇒ Sells(West, x, Nono) -------------------→ (4)
4. We will also need to know that missiles are weapons:
Missile(x) ⇒ Weapon(x) -------------------→ (5)
5. And we must know that an enemy of America counts as “hostile”:
Enemy(x, America) ⇒ Hostile(x) -------------------→ (6)
6. “West, who is American ...”:
American(West) -------------------→ (7)
7. “The country Nono, an enemy of America ...”:
Enemy(Nono, America) -------------------→ (8)
Step 2: Construct AND – OR graph using Forward chaining algorithm.
➢ Starting from the known facts, it triggers all the rules whose premises are satisfied,
adding their conclusions to the known facts.
➢ The process repeats until the query is answered (assuming that just one answer is
required) or no new facts are added.
➢ Consider the premises (2), (3), (7) and (8) i.e., the premises that does not contain
any implication symbols.
➢ Forward chaining algorithm uses bottom-up approach. Hence draw the following
tree.

➢ On the first iteration, Rule (1) has unsatisfied premises.

Rule (4) is satisfied with {x/M1}, and Sells(West,M1, Nono) is added.
Rule (5) is satisfied with {x/M1}, and Weapon(M1) is added.
Rule (6) is satisfied with {x/Nono}, and Hostile(Nono) is added.

Department of AI&ML, CIT - Ponnampet Page 4

Principles of Artificial Intelligence (21AI54) Module 4
➢ On the second iteration, Rule (1) is satisfied with {x/West, y/M1, z/Nono}, and
Criminal (West) is added.

Backward Chaining
➢ These algorithms work backward from the goal, chaining through rules to find
known facts that support the proof.
➢ Follows top-down approach.
➢ The below algorithm illustrates the working of Backward chaining algorithm.

➢ In backward-chaining algorithm for definite clauses, FOL-BC-ASK(KB, goal ) will

be proved if the knowledge base contains a clause of the form lhs ⇒ goal, where
lhs (left-hand side) is a list of conjuncts.
➢ An atomic fact like American(West) is considered as a clause whose lhs is the
empty list.
➢ Now a query that contains variables might be proved in multiple ways.

Department of AI&ML, CIT - Ponnampet Page 5

Principles of Artificial Intelligence (21AI54) Module 2
➢ For example, the query Person(x) could be proved with the substitution {x/John}
as well as with {x/Richard}.
➢ So, we implement FOL-BC-ASK as a generator— a function that returns multiple
times, each time giving one possible result.
➢ Backward chaining is a kind of AND/OR search—the OR part because the goal
query can be proved by any rule in the knowledge base, and the AND part because
all the conjuncts in the lhs of a clause must be proved.
➢ FOL-BC-OR works by fetching all clauses that might unify with the goal,
standardizing the variables in the clause to be brand-new variables, and then, if the
rhs of the clause does indeed unify with the goal, proving every conjunct in the lhs,
using FOL-BC-AND.
Problem:
The law says that it is a crime for an American to sell weapons to hostile nations. The
country Nono, an enemy of America, has some missiles, and all of its missiles were
sold to it by Colonel West, who is American. Prove that “West is a criminal” using
Backward chaining algorithm.
Solution:
Step 1: First, we will represent these facts as first - order definite clauses.
1. “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) ---------→ (1)
2. “Nono ... has some missiles.”
The sentence ∃ x Owns(Nono, x) ∧ Missile(x) is transformed into two definite
clauses by Existential Instantiation, introducing a new constant M1:
Owns(Nono, M1) ---------→ (2)
Missile(M1) --------------→ (3)
3. “All of its missiles were sold to it by Colonel West”:
Missile(x) ∧ Owns(Nono, x) ⇒ Sells(West, x, Nono) -------------------→ (4)
4. We will also need to know that missiles are weapons:
Missile(x) ⇒ Weapon(x) -------------------→ (5)
5. And we must know that an enemy of America counts as “hostile”:
Enemy(x, America) ⇒ Hostile(x) -------------------→ (6)
6. “West, who is American ...”:
American(West) -------------------→ (7)
7. “The country Nono, an enemy of America ...”:
Enemy(Nono, America) -------------------→ (8)

Department of AI&ML, CIT - Ponnampet Page 6

Principles of Artificial Intelligence (21AI54) Module 4
Step 2: Construct AND – OR graph using Backward chaining algorithm.
➢ Start with the conclusion i.e., Criminal(West).

➢ Rule (1) is satisfied by substituting {x/West}, we get the following tree.

➢ Rule (5) is satisfied by{x/y}, and Missile(y) is added.

Rule (4) is satisfied by {M1/x} and {z/Nono}; Missile(M1) and Owns(Nono, M1)
is added.
Rule (6) is satisfied by {x/Nono} and Enemy(Nono, America) is added.

Resolution
Conjunctive normal form for first-order logic
First-order resolution requires that sentences be in conjunctive normal form (CNF)—that
is, a conjunction of clauses, where each clause is a disjunction of literals.

Problem:
Convert the sentence “Everyone who loves all animals is loved by someone” into CNF.
Solution:
Step 1: Convert the given sentence into FOL.
∀ x [∀ y Animal(y) ⇒ Loves(x, y)] ⇒ [∃ y Loves(y, x)]
Step 2: Eliminate implications.
∀ x [¬∀ y ¬Animal(y) ∨ Loves(x, y)] ∨ [∃ y Loves(y, x)]

Department of AI&ML, CIT - Ponnampet Page 7

Principles of Artificial Intelligence (21AI54) Module 2
Step 3: Move ¬ inwards.
➢ In addition to the usual rules for negated connectives, we need rules for negated
quantifiers. Thus, we have,
¬∀ x p becomes ∃ x ¬p
¬∃ x p becomes ∀ x ¬p .
➢ Our sentence goes through the following transformations:
∀ x [∃ y ¬(¬Animal(y) ∨ Loves(x, y))] ∨ [∃ y Loves(y, x)]
∀ x [∃ y ¬¬Animal(y) ∧ ¬Loves(x, y)] ∨ [∃ y Loves(y, x)]
∀ x [∃ y Animal(y) ∧ ¬Loves(x, y)] ∨ [∃ y Loves(y, x)]
Step 4: Standardize variables.
➢ For sentences like (∃ x P(x))∨(∃ x Q(x)) which use the same variable name twice,
change the name of one of the variables.
➢ This avoids confusion later when we drop the quantifiers.
➢ Thus, we have,
∀ x [∃ y Animal(y) ∧ ¬Loves(x, y)] ∨ [∃ z Loves(z, x)]
Step 5: Skolemize.
➢ Skolemization is the process of removing existential quantifiers by elimination.
➢ In the simple case, translate ∃ x P(x) into P(A), where A is a new constant.
➢ Thus, we get,
∀ x [Animal(F(x)) ∧ ¬Loves(x, F(x))] ∨ Loves(G(z), x)
where F and G are Skolem functions.
Step 6: Drop universal quantifiers.
➢ We can drop the universal quantifiers.
[Animal(F(x)) ∧ ¬Loves(x, F(x))] ∨ Loves(G(z), x)
Step 7: Distribute ∨ over ∧
[Animal(F(x)) ∨ Loves(G(z), x)] ∧ [¬Loves(x, F(x)) ∨ Loves(G(z), x)] .
The sentence is now in CNF and consists of two clauses.

Department of AI&ML, CIT - Ponnampet Page 8

Principles of Artificial Intelligence (21AI54) Module 4
Example Proofs
Problem 1:
The law says that it is a crime for an American to sell weapons to hostile nations. The
country Nono, an enemy of America, has some missiles, and all of its missiles were sold
to it by Colonel West, who is American. Prove that “West is a criminal” using Resolution.
Solution:
Step 1: Convert the given sentences into FOL.
i. “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) ---------→ (1)
ii. “Nono ... has some missiles.”
The sentence ∃ x Owns(Nono, x) ∧ Missile(x) is transformed into two definite
clauses by Existential Instantiation, introducing a new constant M1:
Owns(Nono, M1) ---------→ (2)
Missile(M1) --------------→ (3)
iii. “All of its missiles were sold to it by Colonel West”:
Missile(x) ∧ Owns(Nono, x) ⇒ Sells(West, x, Nono) -------------------→ (4)
iv. We will also need to know that missiles are weapons:
Missile(x) ⇒ Weapon(x) -------------------→ (5)
v. And we must know that an enemy of America counts as “hostile”:
Enemy(x, America) ⇒ Hostile(x) -------------------→ (6)
vi. “West, who is American ...”:
American(West) -------------------→ (7)
vii. “The country Nono, an enemy of America ...”:
Enemy(Nono, America) -------------------→ (8)
Step 2: Convert all the converted FOL sentences into CNF.
1. Convert (1) i.e., American(x) ∧ Weapon(y) ∧ Sells(x, y, z) ∧ Hostile(z) ⇒
Criminal(x) into CNF,
Removing implications,
¬[American(x) ∧ Weapon(y) ∧ Sells(x, y, z) ∧ Hostile(z)] ∨ Criminal(x)
¬American(x) ∨ ¬Weapon(y) ∨ ¬Sells(x, y, z) ∨ ¬Hostile(z) ∨ Criminal(x)
Therefore, the sentence has been converted into CNF.
2. (2) and (3) are in CNF.
3. Convert (4) i.e., Missile(x) ∧ Owns(Nono, x) ⇒ Sells(West, x, Nono) into CNF.
Removing implications,
¬[Missile(x) ∧ Owns(Nono, x)] ∨ Sells(West, x, Nono)

Department of AI&ML, CIT - Ponnampet Page 9

Principles of Artificial Intelligence (21AI54) Module 2
¬Missile(x) ∨ ¬Owns(Nono, x) ∨ Sells(West, x, Nono)
Therefore, the sentence has been converted into CNF.
4. Convert (5) i.e., Missile(x) ⇒ Weapon(x) into CNF.
Removing implications,
¬Missile(x) ∨ Weapon(x)
Therefore, the sentence has been converted into CNF.
5. Convert (6) i.e., Enemy(x, America) ⇒ Hostile(x) into CNF.
¬Enemy(x, America) ∨ Hostile(x)
Therefore, the sentence has been converted into CNF.
6. (7) and (8) are already in CNF.

Step 3: Negate the conclusion.

➢ Conclusion is “West is Criminal”.
➢ Convert to FOL, it becomes, Criminal(West).
➢ Therefore, Negated form is ¬Criminal(West).

Step 4: Construct Resolution Tree.

Department of AI&ML, CIT - Ponnampet Page 10

Principles of Artificial Intelligence (21AI54) Module 4
Problem 2:
Everyone who loves all animals is loved by someone.
Anyone who kills an animal is loved by no one.
Jack loves all animals.
Either Jack or Curiosity killed the cat, who is named Tuna.
Did Curiosity kill the cat?
Prove by Resolution.
Solution:
Step 1: Convert the given sentences into FOL.
1. Everyone who loves all animals is loved by someone.
∀ x [∀ y Animal(y) ⇒ Loves(x, y)] ⇒ [∃ y Loves(y, x)] -----→ (1)
2. Anyone who kills an animal is loved by no one.
∀ x [∃ z Animal(z) ∧ Kills(x, z)] ⇒ [∀ y ¬Loves(y, x)] -----→ (2)
3. Jack loves all animals.
∀ x Animal(x) ⇒ Loves(Jack, x) -----→ (3)
4. Either Jack or Curiosity killed the cat, who is named Tuna.
Kills(Jack, Tuna) ∨ Kills(Curiosity, Tuna) -----→ (4)
5. Cat name is Tuna.
Cat(Tuna) -----→ (5)
6. We derive the following fact, Cats are animals.
∀ x Cat(x) ⇒ Animal(x) -----→ (6)
Step 2: Convert all the converted FOL sentences into CNF.
1. Convert (1) i.e., ∀ x [∀ y Animal(y) ⇒ Loves(x, y)] ⇒ [∃ y Loves(y, x)] into CNF,
i. Removing implications,
∀ x [¬∀ y ¬Animal(y) ∨ Loves(x, y)] ∨ [∃ y Loves(y, x)]
ii. Move ¬ inwards.
∀ x [∃ y ¬(¬Animal(y) ∨ Loves(x, y))] ∨ [∃ y Loves(y, x)]
∀ x [∃ y ¬¬Animal(y) ∧ ¬Loves(x, y)] ∨ [∃ y Loves(y, x)]
∀ x [∃ y Animal(y) ∧ ¬Loves(x, y)] ∨ [∃ y Loves(y, x)]
iii. Standardize variables.
∀ x [∃ y Animal(y) ∧ ¬Loves(x, y)] ∨ [∃ z Loves(z, x)]
iv. Skolemize
∀ x [Animal(F(x)) ∧ ¬Loves(x, F(x))] ∨ Loves(G(z), x)
v. Drop universal quantifiers
[Animal(F(x)) ∧ ¬Loves(x, F(x))] ∨ Loves(G(z), x)

Department of AI&ML, CIT - Ponnampet Page 11

Principles of Artificial Intelligence (21AI54) Module 2
vi. Distribute ∨ over ∧
[Animal(F(x)) ∨ Loves(G(z), x)] ∧ [¬Loves(x, F(x)) ∨ Loves(G(z), x)]
Therefore, the sentence has been converted into CNF.
2. Convert (2) i.e., ∀ x [∃ z Animal(z) ∧ Kills(x, z)] ⇒ [∀ y ¬Loves(y, x)] into CNF.
i. Removing implications,
∀ x ¬[∃ z Animal(z) ∧ Kills(x, z)] ∨ [∀ y ¬Loves(y, x)]
ii. Move ¬ inwards,
∀ x [∀ z ¬Animal(z) ∨ ¬Kills(x, z)] ∨ [∀ y ¬Loves(y, x)]
iii. Drop Universal quantifiers,
¬Loves(y, x) ∨ ¬Animal(z) ∨ ¬Kills(x, z)
Therefore, the sentence has been converted into CNF.
3. Convert (3) i.e., ∀ x Animal(x) ⇒ Loves(Jack, x) into CNF.
Removing implications,
¬Animal(x) ∨ Loves(Jack, x)
Therefore, the sentence has been converted into CNF.
4. (4), (5) and (6) are in CNF.

Step 3: Negate the conclusion.

➢ Conclusion is “Curiosity killed the cat”.
➢ Convert to FOL, it becomes, Kills(Curiosity, Tuna).
➢ Therefore, Negated form is ¬ Kills(Curiosity, Tuna).

Step 4: Construct Resolution Tree.

Department of AI&ML, CIT - Ponnampet Page 12

Principles of Artificial Intelligence (21AI54) Module 4
Difference between Forward Chaining and Backward Chaining

Department of AI&ML, CIT - Ponnampet Page 13