IFETCE R23 Academic Year 2022-2023

IFET COLLEGE OF ENGINEERING

(An Autonomous Institution)
DEPARTMENT OF CSE

SUBJECT TITLE: Fundamentals of AI UNIT: II

SUBJECT CODE: 23CS4404 YEAR/SEM: II/IV

UNIT-II KNOWLEDGE REPRESENTATION

First-Order Logic: Syntax and Semantics of First-Order Logic - Models for first-order logic -
Symbols and Interpretations – Terms - Atomic sentences - Complex sentences - Quantifiers -
Equality - Using First-Order-Logic - Knowledge Engineering in First- Order Logic - Inference
in First- Order Logic: Inference rules - Unification and Lifting Forward Chaining - Backward
Chaining- Resolution.
3.1 First order predicate logic
FOL is a mode of representation in Artificial Intelligence. It is an extension of PL. FOL
represents natural language statements in a concise way. FOL is also called predicate logic. It
is a powerful language used to develop information about an object and express the relationship
between objects.
FOL not only assumes that does the world contains facts (like PL does), but it also assumes
the following:
o Objects: A, B, people, numbers, colors, wars, theories, squares, pit, etc.
o Relations: It is unary relation such as red, round, sister of, brother of, etc.
o Function: father of, best friend, third inning of, end of, etc.
First order logic is specifying more precisely the way in which the possible worlds of first-
order logic reflect the ontological commitment to objects and relations. Then we introduce the
various elements of the language.
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.
Models for first-order logic are much more interesting.
• The domain of a model is the set of objects or domain elements it contains. The do- main
is required to be nonempty—every possible world must contain at least one object.
• Mathematically speaking, it doesn’t matter what these objects are—all that matters is how
many there are in each particular model—but for pedagogical purposes we’ll use a concrete
example.
• Figure 3.1 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.

1
 IFETCE R23 Academic Year 2022-2023

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

Figure 3.1 A model containing five objects, two binary relations, three unary relations
(indicated by labels on the objects), and one unary function, left-leg.
• Thus, the brotherhood relation in this model is the set
{Richard the Lionheart, King John, King John, Richard the Lionheart} (1)
• 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 . (2)
• Strictly speaking, models in first-order logic require total functions, that is, there must be a
value for every input tuple. Thus, the crown must have a left leg and so must each of the
left legs.
• There is a technical solution to this awkward problem involving an additional “invisible”
object that is the left leg of everything that has no left leg, including itself. Fortunately, as

2
 IFETCE R23 Academic Year 2022-2023

long as one makes no assertions about the left legs of things that have no left legs, these
technicalities are of no import.
Symbols and interpretations
• The impatient reader can obtain a complete description from the formal grammar. 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: constant symbols, which stand for
objects; predicate symbols, which stand for relations; and 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 with proposition symbols, the choice of names is entirely up to the user. Each predicate
and function symbol comes with an arity that fixes the number of arguments.
• 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—which a logician would call the intended
interpretation— is as follows:
✓ Richard refers to Richard the Lionheart and John refers to the evil King John.
✓ Brother refers to the brotherhood relation, that is, the set of tuples of objects given
in Equation (1); OnHead refers to the “on head” relation that holds between the
crown and King John; Person, King, and Crown refer to the sets of objects that
are persons, kings, and crowns.
✓ LeftLeg refers to the “left leg” function, that is, the mapping given in Equation
(2).

3
 IFETCE R23 Academic Year 2022-2023

Figure 3.2 The syntax of first-order logic with equality, specified in Backus–Naur form
• There are many other possible interpretations, of course. For example, one
interpretation maps Richard to the crown and John to King John’s left leg.
• There are five objects in the model, so there are 25 possible interpretations just for the
constant symbols Richard and John.
• Notice that not all the objects need have a name—for example, the intended
interpretation does not name the crown or the legs. It is also possible for an object to
have several names; there is an interpretation under which both Richard and John refer
to the crown.

Figure 3.3 Some members of the set of all models for a language with two constant
symbols, R and J, and one binary relation symbol.
• If you find this possibility confusing, remember that, in propositional logic, it is
perfectly possible to have a model in which Cloudy and Sunny are both true; it is the
job of the knowledge base to rule out models that are inconsistent with our knowledge.
• In summary, a model in first-order logic consists of a set of objects and an interpretation
that maps constant symbols to objects, predicate symbols to relations on those objects,

4
 IFETCE R23 Academic Year 2022-2023

and function symbols to functions on those objects. Just as with propositional logic,
entailment, validity, and so on are defined in terms of all possible models.
• It shows that models vary in how many objects they contain—from one up to infinity—
and in the way the constant symbols map to objects. If there are two constant symbols
and one object, then both symbols must refer to the same object; but this can still happen
even with more objects. When there are more objects than constant symbols, some of
the objects will have no names.
• Because the number of possible models is unbounded, checking entailment by the
enumeration of all possible models is not feasible for first-order logic (unlike
propositional logic). Even if the number of objects is restricted, the number of
combinations can be very large. For the example in Figure 4.9, there are
137,506,194,466 models with six or fewer objects.
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).
• 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. It is important to
remember that a complex term is just a complicated kind of name. It is not a “subroutine
call” that “returns a value.” There is no LeftLeg subroutine that takes a person as input
and returns a leg.
• We can reason about left legs (e.g., stating the general rule that everyone has one and
then deducing that John must have one) without ever providing a definition of LeftLeg.
• This is something that cannot be done with subroutines in programming languages. The
formal semantics of terms is straightforward. Consider a term f(t1, . . . , tn). The function
symbol f refers to some function in the model (call it F); the argument terms refer to
objects in the domain (call them d1, . . . , dn); and the term as a whole refers to the
object that is the value of the function F applied to d1, . . . , dn.
• For example, suppose the LeftLeg function symbol refers to the function shown in
Equation (8.2) and John refers to King John, then LeftLeg(John) refers to King John’s
left leg. In this way, the interpretation fixes the referent of every term.
Atomic sentences
• We have both terms for referring to objects and predicate symbols for referring to
relations, we can put them together to make atomic sentences that state facts. 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).

5
 IFETCE R23 Academic Year 2022-2023

• This states, under the intended interpretation given earlier, that Richard the Lionheart
is the brother of King John. Atomic sentences can have complex terms as arguments.
Thus,
Married(Father (Richard),Mother (John))
states that Richard the Lionheart’s father is married to King John’s mother.
• An atomic sentence is true in a given model if the relation referred to by the predicate
symbol holds among the objects referred to by the arguments.
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:
￢Brother (LeftLeg(Richard), John)
Brother (Richard, John) ∧ Brother (John,Richard)
King(Richard) ∨ King(John)
￢King(Richard) ⇒ King(John) .
Quantifiers
Once we have a logic that allows objects, it is only natural to want to express properties
of entire collections of objects, instead of enumerating the objects by name. Quantifiers let us
do this. First-order logic contains two standard quantifiers, called universal and existential.
Universal quantification (∀)
• The expression of general rules in propositional logic. 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 . . .”. (Remember that the upside-down A stands 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.
• Intuitively, 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.
• This sounds complicated, but it is really just a careful way of stating the intuitive
meaning of universal quantification.
Existential quantification (∃)

6
 IFETCE R23 Academic Year 2022-2023

• 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 . . .”.
• Intuitively, 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;
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. Notice that, by our definition, the sentence would also be true in a
model in which King John was wearing two crowns. This is entirely consistent with the
original sentence “King John has a crown on his head.”
Nested quantifiers
• To express more complex sentences using multiple 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.
• On the other hand, ∃ y (∀ x Loves(x, y)) says that someone in the world has a particular
property, namely the property of being loved by everybody.
Equality

7
 IFETCE R23 Academic Year 2022-2023

• 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. Because an interpretation fixes the referent of any term, determining the truth
of an equality sentence is simply a matter of seeing that the referents of the two terms
are the same object.
• The equality symbol can be used to state facts about a given function, as we just did for the
Father symbol. It can also be used with negation to insist that two terms are not the same
object.
• To say that Richard has at least two brothers, we would write
∃ x, y Brother (x,Richard) ∧ Brother (y,Richard) ∧ ￢(x=y) .
• The sentence
∃ x, y Brother (x,Richard) ∧ Brother (y,Richard)
does not have the intended meaning. In particular, it is true in the model of Figure 4.10,
where Richard has only one brother. To see this, consider the extended interpretation
in which both x and y are assigned to King John. The addition of ￢(x=y) rules out such
models. The notation x 6= y is sometimes used as an abbreviation for ￢(x=y).
USING FIRST-ORDER LOGIC
First-order logic (FOL), also known as predicate logic, is a powerful representation language
that extends propositional logic by including quantifiers, predicates, and variables.
i. Assertions and Queries in First-Order Logic
First-Order Logic (FOL) is a formal language for representing facts about the world. It is
more expressive than propositional logic because it includes objects, relations, and quantifiers.
Assertions in FOL
• Definition: Assertions in FOL are statements about the world, expressed using
constants, predicates, and quantifiers.
• Structure:
o Constants: Represent specific objects (e.g., John, Paris).
o Predicates: Represent properties or relationships (e.g., Loves(John, Mary)
means "John loves Mary").
o Quantifiers:
▪ Universal (∀): "For all"
▪ Existential (∃): "There exists"
• Example:
o "All humans are mortal" can be written as:
∀x (Human(x) → Mortal(x))
Queries in FOL

8
 IFETCE R23 Academic Year 2022-2023

• Queries ask whether certain statements (formulas) can be logically inferred from the
given set of assertions (knowledge base).
• Example:
o Knowledge Base (KB):
Human(Socrates)
∀x (Human(x) → Mortal(x))
o Query: Mortal(Socrates)?
o Answer: Yes (based on the KB and inference rules).
ii. The Kinship Domain
The kinship domain represents relationships between family members, using FOL to capture
complex relational knowledge.
Key Concepts
• Family Relations: Represented as predicates like Parent(x, y), Sibling(x, y), Cousin(x,
y), etc.
• Rules and Assertions: Define relationships using logical expressions.
• Example Assertions:
o Parent(John, Mary) (John is a parent of Mary)
o ∀x ∀y (Parent(x, y) → Ancestor(x, y)) (A parent is an ancestor)
o ∀x ∀y ∀z ((Parent(x, y) ∧ Parent(y, z)) → Grandparent(x, z)) (A parent's parent
is a grandparent)
Query Example
• Query: "Is John an ancestor of Sarah?"
• Knowledge Base:
o Parent(John, Mary)
o Parent(Mary, Sarah)
o ∀x ∀y (Parent(x, y) → Ancestor(x, y))
o ∀x ∀y ∀z ((Parent(x, y) ∧ Ancestor(y, z)) → Ancestor(x, z))
• Answer: Yes, based on the inference rules.
iii. Numbers, Sets, and Lists
Numbers in FOL
• Numbers can be represented with functions and predicates. For example:
o Plus(x, y, z) means x + y = z.
o GreaterThan(x, y) means x > y.
Sets in FOL
• Sets are represented using membership and subset relations:
o Member(x, S) means x is a member of set S.
o Subset(S1, S2) means S1 is a subset of S2.
• Example:
o "All humans belong to the set of mortals" can be expressed as:
∀x (Human(x) → Member(x, Mortals))
Lists in FOL

9
 IFETCE R23 Academic Year 2022-2023

• Lists are handled using recursive definitions.

• Example:
o A list [1, 2, 3] can be represented as:
▪ Cons(1, Cons(2, Cons(3, Nil)))
iv. The Wumpus World
The Wumpus World is a simple AI environment used to demonstrate reasoning with
incomplete and uncertain information.
Environment
• Goal: The agent needs to find gold in a grid while avoiding pits and a wumpus (a
monster).
• Rules:
o Breeze: Indicates a pit is adjacent.
o Stench: Indicates the wumpus is adjacent.
o Glitter: Indicates gold is in the current square.
FOL Representation
1. Percepts:
o Breeze(x, y) means there is a breeze at square (x, y).
o Stench(x, y) means there is a stench at square (x, y).
2. Rules:
o ∀x ∀y (Breeze(x, y) → ∃a ∃b (Pit(a, b) ∧ Adjacent(a, b, x, y)))
(If there's a breeze at (x, y), then there’s a pit in an adjacent square).
o ∀x ∀y (Stench(x, y) → ∃a ∃b (Wumpus(a, b) ∧ Adjacent(a, b, x, y)))
(If there's a stench at (x, y), then the wumpus is adjacent).
3. Example Query:
o Query: "Is there a pit at (2, 2)?"
o KB:
▪ Breeze(1, 1)
▪ Adjacent(1, 1, 2, 2)
▪ Rule: ∀x ∀y (Breeze(x, y) → ∃a ∃b (Pit(a, b) ∧ Adjacent(a, b, x, y)))
o Answer: Yes, inferred from the rules and assertions.
Examples in Practical Applications
These logical frameworks are crucial in AI systems for tasks like:
1. Expert Systems: Medical diagnosis using logical rules (e.g., kinship reasoning in
genetics).
2. Robotics: Wumpus-like reasoning for navigation in uncertain environments.
3. Data Handling: Using set and list representations in programming languages like
Prolog.
KNOWLEDGE ENGINEERING IN FIRST ORDER LOGIC
Knowledge Engineering involves building a knowledge base (KB) to represent and reason
about a domain. Using FOL, which allows for quantifiers, predicates, and

10
 IFETCE R23 Academic Year 2022-2023

relationships, makes it possible to handle complex, structured knowledge beyond

simple true/false facts.
Steps in Knowledge Engineering
1. Identify the Task
This involves determining what problem needs solving and what knowledge is necessary to
solve it.
• Example: Build a diagnostic system for diseases.
o Task: Diagnose diseases based on symptoms.
o Knowledge Needed: Symptoms of diseases, causal relationships, and medical
tests.
2. Assemble the Relevant Knowledge
Gather all the facts, rules, and relationships about the domain.
• Example: For disease diagnosis:
o Fact: Fever is a symptom of the flu.
o Rule: If a person has a fever and body aches, they may have the flu.
3. Decide on a Vocabulary
Define the constants, predicates, and functions to represent objects, relations, and properties
in the domain.
• Example for Disease Diagnosis:
o Constants: John, Fever, Flu
o Predicates:
▪ HasSymptom(Patient, Symptom) (e.g., HasSymptom(John, Fever))
▪ HasDisease(Patient, Disease) (e.g., HasDisease(John, Flu))
o Functions: TestFor(Disease) (e.g., a function to test for a disease)
4. Encode General Knowledge about the Domain
Represent general truths about the domain using FOL axioms.
• Example:
o If a person has a fever and body aches, they might have the flu:
∀p (HasSymptom(p, Fever) ∧ HasSymptom(p, BodyAches) → HasDisease(p,
Flu))
o Fever is caused by an infection:
∀p (HasSymptom(p, Fever) → ∃d (HasDisease(p, d) ∧ DiseaseCauses(d,
Fever)))
5. Encode Specific Problem Instances
Add facts about a particular situation to the knowledge base.
• Example:
o Specific facts about a patient:
▪ HasSymptom(John, Fever)
▪ HasSymptom(John, BodyAches)
6. Pose Queries to the Inference System
Query the KB to infer answers or make decisions.

11
 IFETCE R23 Academic Year 2022-2023

• Example:
o Query: "Does John have the flu?"
▪ HasDisease(John, Flu)?
▪ Answer: Yes, based on the KB and rules.
7. Debug and Improve the Knowledge Base
Test the knowledge base with different cases, identify inconsistencies, and refine the rules
and facts.
Examples of Domains
1. The Kinship Domain
The kinship domain models family relationships.
• Vocabulary:
o Constants: John, Mary, Sue
o Predicates:
▪ Parent(x, y) (x is a parent of y)
▪ Sibling(x, y) (x and y are siblings)
▪ Ancestor(x, y) (x is an ancestor of y)
• General Rules:
o A parent is an ancestor:
∀x ∀y (Parent(x, y) → Ancestor(x, y))
o A parent's ancestor is also an ancestor:
∀x ∀y ∀z ((Parent(x, y) ∧ Ancestor(y, z)) → Ancestor(x, z))
• Specific Facts:
o Parent(John, Mary)
o Parent(Mary, Sue)
• Query:
"Is John an ancestor of Sue?"
o Answer: Yes, derived using the rules.
2. Numbers, Sets, and Lists
FOL can represent mathematical objects like numbers, sets, and lists.
• Numbers:
o Vocabulary:
▪ Plus(x, y, z) means x + y = z.
▪ GreaterThan(x, y) means x > y.
o Example Rule: Addition is commutative:
∀x ∀y ∀z (Plus(x, y, z) → Plus(y, x, z))
• Sets:
o Vocabulary:
▪ Member(x, S) means x is a member of set S.
▪ Subset(S1, S2) means S1 is a subset of S2.
o Example Rule: If x is in S1 and S1 is a subset of S2, then x is in S2:
∀x ∀S1 ∀S2 ((Member(x, S1) ∧ Subset(S1, S2)) → Member(x, S2))

12
 IFETCE R23 Academic Year 2022-2023

• Lists:
o Vocabulary:
▪ Cons(h, t) represents a list with head h and tail t.
▪ Nil is the empty list.
o Example Rule: A list is empty if and only if it is Nil:
∀x (List(x) ↔ (x = Nil ∨ ∃h ∃t (Cons(h, t) = x)))
3. The Wumpus World
The Wumpus World is a classic domain used to demonstrate reasoning in an uncertain
environment.
• Vocabulary:
o Constants: Grid locations (x, y)
o Predicates:
▪ Breeze(x, y) (breeze at location (x, y))
▪ Pit(x, y) (pit at location (x, y))
▪ Stench(x, y) (stench at location (x, y))
▪ Wumpus(x, y) (Wumpus at location (x, y))
• General Rules:
o If there is a breeze at (x, y), a pit is adjacent:
∀x ∀y (Breeze(x, y) → ∃a ∃b (Pit(a, b) ∧ Adjacent(a, b, x, y)))
o If there is a stench at (x, y), the Wumpus is adjacent:
∀x ∀y (Stench(x, y) → ∃a ∃b (Wumpus(a, b) ∧ Adjacent(a, b, x, y)))
• Specific Facts:
o Breeze(2, 2)
o Adjacent(2, 2, 1, 2)
• Query: "Is there a pit at (1, 2)?"
o Answer: Yes, derived using the rules.
Inference in FOL
1. Universal Elimination:
Replace universal quantifiers with specific instances.
Example:
∀x (Human(x) → Mortal(x)) → Human(Socrates) → Mortal(Socrates)
2. Existential Instantiation:
Replace existential quantifiers with specific constants.
Example:
∃x Loves(x, Mary) → Loves(John, Mary)
3. Resolution:
The primary method for inference, combining clauses to resolve queries.
Challenges in Knowledge Engineering
1. Choosing the Right Representation: Ensuring the vocabulary and rules fully capture
the domain.
2. Handling Ambiguity: Avoiding conflicts or incomplete information.

13
 IFETCE R23 Academic Year 2022-2023

3. Scalability: Large KBs can become computationally expensive.

3.2 INFERENCE IN FIRST-ORDER LOGIC
• Inference in First-Order Logic (FOL) refers to the process of deriving new information or
conclusions from existing knowledge using logical reasoning.
• Inference in First-Order Logic (FOL) is the process of deriving new facts or conclusions
based on a given set of facts (knowledge base) and rules. FOL extends propositional logic
by including quantifiers (like ∀\forall∀ and ∃\exists∃) and predicates with variables,
making it more expressive for reasoning about objects and their relationships.
Example:
Knowledge base:
1. ∀x(Person(x)∧Loves(x,Chocolate)→Happy(x))\forall x (Person(x) \land Loves(x,
Chocolate) \rightarrow Happy(x))∀x(Person(x)∧Loves(x,Chocolate)→Happy(x))
(All people who love chocolate are happy.)
2. Person(John)Person(John)Person(John) (John is a person.)
3. Loves(John,Chocolate)Loves(John, Chocolate)Loves(John,Chocolate) (John loves
chocolate.)
Inference:
Happy(John)Happy(John)Happy(John) (John is happy).
2. Inference Rules:
Inference in FOL uses specific logical rules to deduce new statements from existing ones.
Example Rules:
o Modus Ponens: If P→QP \rightarrow QP→Q (if PPP, then QQQ) and PPP is true, infer
QQQ.
▪ P(x)→Q(x)P(x) \rightarrow Q(x)P(x)→Q(x)
▪ P(John)P(John)P(John)
▪ Infer Q(John)Q(John)Q(John).
o Universal Elimination: If ∀xP(x)\forall x P(x)∀xP(x) is true, then P(A)P(A)P(A) is true
for any specific AAA.
▪ ∀x(Person(x)→Mortal(x))\forall x (Person(x) \rightarrow
Mortal(x))∀x(Person(x)→Mortal(x))
▪ Person(Socrates)Person(Socrates)Person(Socrates)
▪ Infer Mortal(Socrates)Mortal(Socrates)Mortal(Socrates).
3. Unification:
FOL often requires matching variables to constants or other variables to perform
inference, a process called unification.
Example:
Knowledge base:
1. Parent(x,y)∧Ancestor(y,z)→Ancestor(x,z)Parent(x, y) \land Ancestor(y, z) \rightarrow
Ancestor(x, z)Parent(x,y)∧Ancestor(y,z)→Ancestor(x,z)
2. Parent(Alice,Bob)Parent(Alice, Bob)Parent(Alice,Bob)
3. Ancestor(Bob,Charlie)Ancestor(Bob, Charlie)Ancestor(Bob,Charlie)
Unification:
o Match Parent(x,y)Parent(x, y)Parent(x,y) with Parent(Alice,Bob)Parent(Alice,
Bob)Parent(Alice,Bob): x=Alice,y=Bobx = Alice, y = Bobx=Alice,y=Bob.
o Match Ancestor(y,z)Ancestor(y, z)Ancestor(y,z) with
Ancestor(Bob,Charlie)Ancestor(Bob, Charlie)Ancestor(Bob,Charlie): y=Bob,z=Charliey =
Bob, z = Charliey=Bob,z=Charlie.

14
 IFETCE R23 Academic Year 2022-2023

Inference: Ancestor(Alice,Charlie)Ancestor(Alice, Charlie)Ancestor(Alice,Charlie).

4. Completeness and Soundness:
o Soundness: If the inference system derives a conclusion, it is guaranteed to be logically
correct if the premises are true.
Example: From P(A)∧(P(A)→Q(A))P(A) \land (P(A) \rightarrow
Q(A))P(A)∧(P(A)→Q(A)), the system infers Q(A)Q(A)Q(A). This inference is sound
because it adheres to the logical rules.
o Completeness: The system can derive all logically valid conclusions from the premises.
Example: If ∀x(P(x)→Q(x))\forall x (P(x) \rightarrow Q(x))∀x(P(x)→Q(x)) and
P(A)P(A)P(A) are true, the system should be able to infer Q(A)Q(A)Q(A).
5. Techniques for Inference:
Two main approaches are used to apply inference rules in FOL:
a. Forward Chaining:
Starts with known facts and applies rules to derive new facts until the goal is reached.
Example:
o ∀x(Bird(x)→CanFly(x))\forall x (Bird(x) \rightarrow CanFly(x))∀x(Bird(x)→CanFly(x))
o Bird(Sparrow)Bird(Sparrow)Bird(Sparrow)
Inference: CanFly(Sparrow)CanFly(Sparrow)CanFly(Sparrow).
b. Backward Chaining:
Starts with a goal and works backward to check if the known facts can support it.
Example:
Goal: Prove CanFly(Sparrow)CanFly(Sparrow)CanFly(Sparrow).
o Rule: Bird(x)→CanFly(x)Bird(x) \rightarrow CanFly(x)Bird(x)→CanFly(x).
o Fact: Bird(Sparrow)Bird(Sparrow)Bird(Sparrow).
Inference: CanFly(Sparrow)CanFly(Sparrow)CanFly(Sparrow).
PROPOSITIONAL INFERENCE VS. FIRST-ORDER INFERENCE
Propositional and First-Order Inference are reasoning processes used in logic, but they differ
significantly in their expressiveness, structure, and complexity.
1. Expressiveness
• Propositional Inference:
Deals with propositions—statements that are either true or false. It does not handle
variables or quantifiers.
o Example:
PPP, QQQ, and P∧QP \land QP∧Q (logical AND of PPP and QQQ) are
propositions.
▪ Rule: If P→QP \rightarrow QP→Q and PPP are true, infer QQQ.
• First-Order Inference:
Extends propositional logic by adding predicates, variables, and quantifiers
(∀\forall∀, ∃\exists∃). It allows reasoning about objects and their relationships.
o Example:
∀x(Human(x)→Mortal(x))\forall x (Human(x) \rightarrow
Mortal(x))∀x(Human(x)→Mortal(x))
(All humans are mortal.)
2. Structure
• Propositional Logic:
o Propositions are atomic and indivisible (e.g., PPP, QQQ).
o Statements do not include internal structure (e.g., subjects or objects).
Example:
15
 IFETCE R23 Academic Year 2022-2023

o Rule: Rain→WetRain \rightarrow WetRain→Wet

(If it rains, the ground is wet.)
o Facts: RainRainRain
o Inference: WetWetWet.
• First-Order Logic (FOL):
o Sentences include relations, functions, and quantifiers, enabling more
complex and detailed expressions.
o Variables can take on values from a domain, making FOL more expressive.
Example:
o Rule: ∀x(Student(x)∧Studies(x,Math)→Passes(x,Exam))\forall x (Student(x)
\land Studies(x, Math) \rightarrow Passes(x,
Exam))∀x(Student(x)∧Studies(x,Math)→Passes(x,Exam))
(All students studying Math will pass the exam.)
o Facts: Student(John)Student(John)Student(John),
Studies(John,Math)Studies(John, Math)Studies(John,Math).
o Inference: Passes(John,Exam)Passes(John, Exam)Passes(John,Exam).
3. Inference Techniques
• Propositional Logic:
Inference relies on truth tables, resolution, and simplification of propositional
formulas.
o Example:
P→QP \rightarrow QP→Q, PPP are true, infer QQQ.
• First-Order Logic:
Uses additional techniques like unification and substitution to handle variables and
quantifiers.
o Example:
▪ Rule: ∀x(Animal(x)→NeedsFood(x))\forall x (Animal(x) \rightarrow
NeedsFood(x))∀x(Animal(x)→NeedsFood(x)).
▪ Fact: Animal(Lion)Animal(Lion)Animal(Lion).
▪ Unification: x=Lionx = Lionx=Lion.
▪ Inference: NeedsFood(Lion)NeedsFood(Lion)NeedsFood(Lion).
4. Efficiency and Complexity
• Propositional Logic:
Simpler and computationally less expensive since it deals with a finite set of
propositions. It does not involve variable matching or complex rules.
• First-Order Logic:
More computationally expensive because it handles infinite domains and requires
variable substitutions, unification, and quantifier reasoning.
5. Applications
• Propositional Logic:
o Best for domains with fixed, finite facts.
o Common in simple rule-based systems or decision-making tasks.
Example: Circuit analysis, basic AI systems.
• First-Order Logic:
o Suitable for domains with rich structures and relationships.
o Common in advanced AI, knowledge representation, and databases.
Example: Expert systems, natural language processing.

16
IFETCE R23 Academic Year 2022-2023

UNIFICATION
Unification:
✓ Unification is a process of making two different logical atomic expressions identical
by finding a substitution. Unification depends on the substitution process.
✓ It takes two literals as input and makes them identical using substitution.
✓ Let Ψ1 and Ψ2 be two atomic sentences and 𝜎 be a unifier such that, Ψ1𝜎 = Ψ2𝜎,
then it can be expressed as UNIFY(Ψ1, Ψ2).
Example: Find the MGU for Unify{King(x), King(John)}
Let Ψ1 = King(x), Ψ2 = King(John),
Substitution θ = {John/x} is a unifier for these atoms and applying this substitution,
and both expressions will be identical.
✓ The UNIFY algorithm is used for unification, which takes two atomic sentences and
returns a unifier for those sentences (If any exist).
✓ Unification is a key component of all first-order inference algorithms. It returns fail if
the expressions do not match with each other.
✓ The substitution variables are called Most General Unifier or MGU.
Example. Let's say there are two different expressions, P(x, y), and P(a, f(z)).
In this example, need to make both above statements identical to each other. For this,will
perform the substitution.
P(x, y) .......... (i)
P(a, f(z)) ......... (ii)
✓ Substitute x with a, and y with f(z) in the first expression, and it will be represented as
a/x and f(z)/y.
✓ With both the substitutions, the first expression will be identical to the second
expression and the substitution set will be: [a/x, f(z)/y].
Conditions for Unification:
Following are some basic conditions for unification:
• Predicate symbol must be same, atoms or expression with different predicate
symbol can never be unified.
• Number of Arguments in both expressions must be identical.
• Unification will fail if there are two similar variables present in the same expression.
Unification Algorithm:
Algorithm: Unify(Ψ1, Ψ2)
Step. 1: If Ψ1 or Ψ2 is a variable or constant, then:
a) If Ψ1 or Ψ2 are identical, then return NIL.
b) Else if Ψ1is a variable,
a. then if Ψ1 occurs in Ψ2, then return FAILURE
b. Else return { (Ψ2/ Ψ1)}.
c) Else if Ψ2 is a variable,
a. If Ψ2 occurs in Ψ1 then return FAILURE,
b. Else return {( Ψ1/ Ψ2)}.

17
 IFETCE R23 Academic Year 2022-2023

d) Else return FAILURE.

Step.2: If the initial Predicate symbol in Ψ1 and Ψ2 are not same, then
return FAILURE.
Step. 3: IF Ψ1 and Ψ2 have a different number of arguments, then
return FAILURE.
Step. 4: Set Substitution set(SUBST) to NIL.
Step. 5: For i=1 to the number of elements in Ψ1.
a) Call Unify function with the ith element of Ψ1 and ith element of Ψ2, and put the
result into S.
b) If S = failure then returns Failure
c) If S ≠ NIL then do,
a. Apply S to the remainder of both L1 and L2.
b. SUBST= APPEND(S, SUBST).
Step.6: Return SUBST.
Implementation of the Algorithm
Step.1: Initialize the substitution set to be empty.
Step.2: Recursively unify atomic sentences:
a) Check for Identical expression match.
b) If one expression is a variable vi, and the other is a term ti which does not contain
variable vi, then:
a. Substitute ti / vi in the existing substitutions
b. Add ti /vi to the substitution setlist.
c. If both the expressions are functions, then function name must be similar, and
the number of arguments must be the same in both the expression.
For each pair of the following atomic sentences find the Most General Unifier.
1. Find the MGU of {p(f(a), g(Y)) and p(X, X)}
Sol: S0 => Here, Ψ1 = p(f(a), g(Y)),
and Ψ2 = p(X, X)
SUBST θ= {f(a) / X}
S1 => Ψ1 = p(f(a), g(Y)), and
Ψ2 = p(f(a), f(a)) SUBST θ=
{f(a) / g(y)}, Unification
failed.
Unification is not possible for these expressions.
2. Find the MGU of {p(b, X, f(g(Z))) and p(Z, f(Y), f(Y))}
Here, Ψ1 = p(b, X, f(g(Z))) , and Ψ2 = p(Z, f(Y), f(Y))
S0 =>{ p(b, X, f(g(Z))); p(Z, f(Y), f(Y))}
SUBST θ={b/Z}
S1 =>{ p(b, X,
f(g(b))); p(b, f(Y),
f(Y))} SUBST

18
 IFETCE R23 Academic Year 2022-2023

θ={f(Y) /X}
S2 =>{ p(b, f(Y), f(g(b))); p(b,
f(Y), f(Y))} SUBST θ= {g(b)
/Y}
S2 =>{ p(b, f(g(b)), f(g(b)); p(b, f(g(b)), f(g(b))}
Unified Successfully. And Unifier = { b/Z, f(Y) /X
, g(b) /Y}.
3. Find the MGU of {p (X, X),
and p (Z, f(Z))} Here,
Ψ1 = {p (X, X), and Ψ2
= p (Z, f(Z)) S0 => {p
(X, X), p (Z, f(Z))}
SUBST θ= {X/Z}
S1 => {p (Z, Z), p (Z, f(Z))}
SUBST θ= {f(Z) / Z}, Unification Failed.
Hence, unification is not possible for these expressions.
3.4 FORWARD CHAINING
Forward chaining is also known as a forward deduction or forward reasoning method
when using an inference engine. Forward chaining is a form of reasoning which start with
atomic sentences in the knowledge base and applies inference rules (Modus Ponens) in the
forward direction to extract more data until a goal is reached.
The Forward-chaining algorithm starts from known facts, triggers all rules whose
premises are satisfied, and add their conclusion to the known facts. This process repeats until
the problem is solved.
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 reach to the goal
using available data.
Example:
"As per the law, it is a crime for an American to sell weapons to hostile nations. Country
A, an enemy of America, has some missiles, and all the missiles were sold to it by Robert,
who is an American citizen." Prove that "Robert is criminal."
To solve the above problem, first, convert all the above facts into first-order definite
clauses, and then use a forward-chaining algorithm to reach the goal.
Facts Conversion into FOL:
It is a crime for an American to sell weapons to hostile nations. (Let's say p, q,
and r are variables) American (p) ∧ weapon(q) ∧ sells (p, q, r) ∧ hostile(r) →
Criminal(p) ...(1)
Country A has some missiles. p Owns(A, p) ∧ Missile(p). It can be written in two

19
 IFETCE R23 Academic Year 2022-2023

definite clauses by using Existential Instantiation, introducing new Constant T1.

Owns(A, T1) .................. (2)
Missile(T1) ................... (3)
All of the missiles were sold to country A by Robert.
p Missiles(p) ∧ Owns (A, p) → Sells (Robert, p, A) ............. (4)
Missiles are weapons.
Missile(p) → Weapons (p) ................... (5)
Enemy of America is known as hostile.
Enemy(p, America)
→Hostile(p) .................................................... (6)
Country A is an enemy of America.
Enemy (A, America) (7)
Robert is
American
American(Rober
t) .................................................. (8)
Forward chaining proof:
Step-1:
In the first step the known facts and will choose the sentences which do not have
implications, such as: American(Robert), Enemy(A, America), Owns(A, T1), and
Missile(T1). All these facts will be represented as below.

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

20
 IFETCE R23 Academic Year 2022-2023

Step-3:

At step-3, as we can check Rule-(1) is satisfied with the substitution {p/Robert,

q/T1, r/A}, so add Criminal(Robert) which infers all the available facts. And
hence reached goal statement.
Hence it is proved that Robert is Criminal using forward chaining approach.
3.5 BACKWARD CHAINING
Backward-chaining is also known as a backward deduction or backward reasoning
method when using an inference engine. A backward chaining algorithm is a form of
reasoning, which starts with the goal and works backward, chaining through rules to
find known facts that support the goal.
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.
Example:
In backward-chaining, use the same above example, and will rewrite all the rules.
American (p) ∧ weapon(q) ∧ sells (p, q, r) ∧ hostile(r) → Criminal(p) ...(1)
Owns(A, T1)........................ (2)
Missile(T1)………………….(3)
p Missiles(p) ∧ Owns (A, p) → Sells (Robert, p, A) .................. (4)
Missile(p) → Weapons (p) ....................... (5)
Enemy(p, America) →Hostile(p) ........................ (6)
Enemy (A, America) ......................... (7)
American(Robert) ........................... (8)
Backward-Chaining proof:
In Backward chaining, start with our goal predicate, which is Criminal(Robert), and then
infer further rules.
Step-1:
At the first step, take the goal fact. And from the goal fact, infer other facts, and
at last, prove those facts true. So goal fact is "Robert is Criminal," so following is
the predicate of it.

21
 IFETCE R23 Academic Year 2022-2023

Step-2: At the second step, infer other facts form goal fact which satisfies the rules. So as in
Rule-1, the goal predicate Criminal (Robert) is present with substitution {Robert/P}. So add all
the conjunctive facts below the first level and will replace p with Robert.

Here can see American (Robert) is a fact, so it is proved here.

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

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

22
IFETCE R23 Academic Year 2022-2023

Step-5: At step-5, can infer the fact Enemy(A, America) from Hostile(A) which satisfies
Rule- 6. And hence all the statements are proved true using backward chaining.

S. Forward Chaining Backward Chaining

No.

1. Forward chaining starts from known Backward chaining starts from the goal and
facts and applies inference rule to works backward through inference rules to
extract more data unit it reaches to find the required facts that support the goal.
the goal.
2. It is a bottom-up approach It is a top-down approach

3. Forward chaining is known as data- Backward chaining is known as goal-

driven inference technique as we reach driven technique as we start from the goal
to the goal using the available data. and divide into sub-goal to extract the facts.
4. Forward chaining reasoning Backward chaining reasoning applies a
applies a breadth-first search depth- first search strategy.
strategy.

23
 IFETCE R23 Academic Year 2022-2023

5. Forward chaining tests for all the Backward chaining only tests for few
available rules required rules.
6. Forward chaining is suitable Backward chaining is suitable for
for the planning, monitoring, diagnostic, prescription, and debugging
control, and interpretation application.
application.
7. Forward chaining can generate an Backward chaining generates a finite
infinite number of possible number of possible conclusions.
conclusions.
8. It operates in the forward direction. It operates in the backward direction.

9. Forward chaining is aimed for Backward chaining is only aimed for the
any conclusion. required data.

3.5 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 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.
Steps for Resolution:
• Conversion of facts into first-order logic.
• Convert FOL statements into CNF
• Negate the statement which needs to prove (proof by contradiction)
• Draw resolution graph (unification).
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 convert all the given statements into its first order logic.

24
 IFETCE R23 Academic Year 2022-2023

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.
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
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) Λ 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).
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) Λ alive(Anil)
e. ∀w¬ eats(Anil, w) V eats(Harry, w)
f. ∀g ¬killed(g) ] V alive(g)
g. ∀k ¬ alive(k) V ¬ killed(k)
h. likes(John, Peanuts).
Drop Universal quantifiers.
In this step will drop all universal quantifier since all the statements are not implicitly

25
 IFETCE R23 Academic Year 2022-2023

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).
Step-3: Negate the statement to be proved
In this statement, apply negation to the conclusion statements, which will be written as
¬likes(John, Peanuts).
Step-4: Draw Resolution graph:Now in this step, 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.
Explanation of Resolution graph
• In the first step of resolution graph, ¬likes(John, Peanuts) , and likes(John,
x) get resolved(canceled) by substitution of {Peanuts/x}, and we are left with ¬
food(Peanuts)
• In the second step of the resolution graph, ¬ food(Peanuts) , and food(z) get
resolved (canceled) by substitution of { Peanuts/z}, and we are left with ¬ eats(y,
Peanuts) V killed(y) .
• In the third step of the resolution graph, ¬ eats(y, Peanuts) and eats (Anil,

26
 IFETCE R23 Academic Year 2022-2023

Peanuts) get resolved by substitution {Anil/y}, and we are left with Killed(Anil)
.
• In the fourth step of the resolution graph, Killed(Anil) and ¬ killed(k) get resolve
by substitution
{Anil/k}, and we are left with ¬ alive(Anil) .
In the last step of the resolution graph ¬ alive(Anil) and alive(Anil) get resolved.

27