MODULE 4 ARTIFICIAL INTELLIGENCE(BCS515B)

Syllabus:

First Order Logic: Representation Revisited, Syntax and Semantics of First Order logic, Using First
Order logic, Knowledge Engineering In First-Order Logic
Inference in First Order Logic: Propositional Versus First Order Inference, Unification ,Forward
Chaining
Chapter 8- 8.1, 8.2, 8.3, 8.4
Chapter 9- 9.1, 9.2, 9.3
Text book: Stuart J. Russell and Peter Norvig, Artificial Intelligence, 3rd Edition, Pearson, 2015
• The language of thought
• Combining the best of natural and formal languages.
Objects: people, houses, numbers, theories, Ronald McDonald, colors, baseball games, wars, centuries . .
.
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, . . .
Functions: father of, best friend, third inning of, one more than, beginning of .

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; Relation: ruled; Properties: evil, king

1
Prof. Salma Itagi,Dept. of CSE,SVIT
MODULE 4 ARTIFICIAL INTELLIGENCE(BCS515B)

Syntax and Semantics of First Order Logic

1. Models for First Order Logic
Models for propositional logic link proposition symbols to predefined truth values.
Representation of tuple
2. Symbols and Interpretations
Constant symbols→Objects
Predicate symbols→relations
Function symbols→functions

2
Prof. Salma Itagi,Dept. of CSE,SVIT
MODULE 4 ARTIFICIAL INTELLIGENCE(BCS515B)

3
Prof. Salma Itagi,Dept. of CSE,SVIT
MODULE 4 ARTIFICIAL INTELLIGENCE(BCS515B)

Atomic sentence
Brother(Richard,John)
Complex sentence
￢Brother (LeftLeg(Richard), John)
Brother (Richard , John) ∧ Brother (John,Richard) King(Richard ) ∨ King(John)
￢King(Richard) ⇒ King(John)
1. First-order logic contains two standard quantifiers, called universal and existential
“All kings are persons”
∀ x King(x) ⇒ Person(x) .
Universal quantification makes statements about every object.
A statement about some object in the universe without naming it, by using an existential quantifier.
King John has a crown on his head ∃ x Crown(x) ∧ OnHead(x, John) .
“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.
4
Prof. Salma Itagi,Dept. of CSE,SVIT
MODULE 4 ARTIFICIAL INTELLIGENCE(BCS515B)

• Often want 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 likes somebody” means
that for every person, there is someone that person likes:
∀ x ∃ y Likes(x, y)
• On the other hand, to say “There is someone who is liked by everyone,” we write
∃ y ∀ x Likes(x, y)

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

5
Prof. Salma Itagi,Dept. of CSE,SVIT
MODULE 4 ARTIFICIAL INTELLIGENCE(BCS515B)

• 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.
2. The kinship domain
• It is 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.”
• 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.
• For example, one’s mother is one’s female parent:
∀ m, c Mother (c)=m ⇔ Female(m) ∧ Parent(m, c)
Few more examples:
1. Male and female are disjoint categories:
∀ x Male(x) ⇔ ￢Female(x) .
[Link] and child are inverse relations:
∀ p, c Parent(p, c) ⇔ Child (c, p) .
3. A grandparent is a parent of one’s parent:
∀ g, c Grandparent (g, c) ⇔ ∃p Parent(g, p) ∧ Parent(p, c) .
4. A sibling is another child of one’s parents:
∀ x, y Sibling(x, y) ⇔ x = y ∧ ∃p Parent(p, x) ∧ Parent(p, y) .
[Link],Sets and lists
• The theory of natural numbers or non-negative integers.
• Here we need a predicate NatNum that will be true of natural numbers; we need one constant
symbol, 0; and we need one function symbol, S (successor).
• The Peano axioms define natural numbers and addition.
• Natural numbers are defined recursively:
NatNum(0) . ∀ n NatNum(n) ⇒ NatNum(S(n))
• That is, 0 is a natural number, and for every object n, if n is a natural number, then S(n) is a natural

6
Prof. Salma Itagi,Dept. of CSE,SVIT
MODULE 4 ARTIFICIAL INTELLIGENCE(BCS515B)

number. So the natural numbers are 0, S(0), S(S(0)), and so on.

• The empty set is a constant written as {}.

• There is one unary predicate, Set, which is true of sets.
• The binary predicates are x∈ s (x is a member of set s) and s1 ⊆ s2 (set s1 is a subset, not
necessarily proper, of set s2).
• The binary functions are s1 ∩ s2 (the intersection of two sets), s1 ∪ s2 (the union of two sets),
and {x|s} (the set resulting from adjoining element x to set s). One possible set of axioms is as
follows:
1. The only sets are the empty set and those made by adjoining something to a set:
∀ s Set(s) ⇔ (s={}) ∨ (∃ x, s2 Set(s2) ∧ s={x|s2}) .
2. The empty set has no elements adjoined into it. In other words, there is no way to decompose {}
into a smaller set and an element:
￢∃ x, s {x|s}={} .
3. Adjoining an element already in the set has no effect: ∀ x, s x∈ s ⇔ s={x|s} .
4. The only members of a set are the elements that were adjoined into it.
We express this recursively, saying that x is a member of s if and only if s is equal to some set s2 adjoined
with some element y, where either y is the same as x or x is a member of s2: ∀ x, s x∈ s ⇔ ∃y, s2 (s={y|s2}
∧ (x=y ∨ x∈ s2))
5. A set is a subset of another set if and only if all of the first set’s members are members of the second
7
Prof. Salma Itagi,Dept. of CSE,SVIT
MODULE 4 ARTIFICIAL INTELLIGENCE(BCS515B)

set:
∀ s1, s2 s1 ⊆ s2 ⇔ (∀x x∈ s1 ⇒ x∈ s2)
6. Two sets are equal if and only if each is a subset of the other:
∀ s1, s2 (s1 =s2) ⇔ (s1 ⊆ s2 ∧ s2 ⊆ s1)
7. An object is in the intersection of two sets if and only if it is a member of both sets:
∀ x, s1, s2 x∈ (s1 ∩ s2) ⇔ (x∈ s1 ∧ x∈s2) .
8. An object is in the union of two sets if and only if it is a member of either set:
∀ x, s1, s2 x∈ (s1 ∪ s2) ⇔ (x∈ s1 ∨ x∈s2) .
• Lists are similar to sets.
• The differences are that lists are ordered and the same element can appear more than once in a list.
• We can use the vocabulary of Lisp for lists: Nil is the constant list with no elements; Cons, Append,
First, and Rest are functions; and Find is the predicate that does for lists what Member does for
sets. List? is a predicate that is true only of lists.
• The empty list is [ ]. The term Cons(x, y), where y is a nonempty list, is written [x|y].
• The term Cons(x, Nil) (i.e., the list containing the element x) is written as [x].
• A list of several elements, such as [A,B,C], corresponds to the nested term Cons(A, Cons(B,
Cons(C, Nil))).
3. The WUMPUS WORLD
The wumpus agent receives a percept vector with five elements.
Percept ([Stench, Breeze, Glitter , None, None]
• The actions in the wumpus world can be represented by logical terms:
• Turn(Right ), Turn(Left ), Forward , Shoot , Grab, Climb .
• If the agent is at a square and perceives a breeze, then that square is breezy:
∀ s, t At(Agent, s, t) ∧ Breeze(t) ⇒ Breezy(s)
∀ s Breezy(s) ⇔ ∃r Adjacent (r, s) ∧ Pit(r) .
• STEPS in Knowledge Engineering Process
1. Identify the task. The knowledge engineer must delineate the range of questions that the
knowledge base will support and the kinds of facts that will be available for each specific problem
instance.
2. Assemble the relevant knowledge. The knowledge engineer might already be an expert in the domain,
or might need to work with real experts to extract what they know—a process called knowledge
acquisition.
8
Prof. Salma Itagi,Dept. of CSE,SVIT
MODULE 4 ARTIFICIAL INTELLIGENCE(BCS515B)

At this stage, the knowledge is not represented formally.

The idea is to understand the scope of the knowledge base, as determined by the task, and to understand
how the domain actually works.
3. Decide on a vocabulary of predicates, functions, and constants. That is, translate the important
domain-level concepts into logic-level names.
This involves many questions of knowledge-engineering style.
Like programming style, this can have a significant impact on the eventual success of the project.
• For example, should pits be represented by objects or by a unary predicate on squares?
• Should the agent’s orientation be a function or a predicate?
• Should the wumpus’s location depend on time?
• Once the choices have been made, the result is a vocabulary that is known as the ontology of the
domain.
• The word ontology means a particular theory of the nature of being or existence.
• The ontology determines what kinds of things exist, but does not determine their specific properties
and interrelationships.
4. Encode general knowledge about the domain.
• The knowledge engineer writes down the axioms for all the vocabulary terms.
• This pins down (to the extent possible) the meaning of the terms, enabling the expert to check the
content.
• Often, this step reveals misconceptions or gaps in the vocabulary that must be fixed by returning
to step 3 and iterating through the process.
5. Encode a description of the specific problem instance.
• If the ontology is well thought out, this step will be easy.
• It will involve writing simple atomic sentences about instances of concepts that are already part of
the ontology.
• For a logical agent, problem instances are supplied by the sensors, whereas a “disembodied”
knowledge base is supplied with additional sentences in the same way that traditional programs are
supplied with input data.
6. Pose queries to the inference procedure and get answers.
This is where the reward is:
• we can let the inference procedure operate on the axioms and problem-specific facts to derive the
facts we are interested in knowing.
9
Prof. Salma Itagi,Dept. of CSE,SVIT
MODULE 4 ARTIFICIAL INTELLIGENCE(BCS515B)

• Thus, we avoid the need for writing an application-specific solution algorithm.

7. Debug the knowledge base.
The answers to queries will seldom be correct on the first try. More precisely, the answers will be correct
for the knowledge base as written, assuming that the inference procedure is sound, but they will not be the
ones that the user is expecting.

•
Identify the TASK

• There are many reasoning tasks associated with digital circuits.

• At the highest level, one analyzes the circuit’s functionality. For example, does the circuit in Figure
8.6 actually add properly?
• If all the inputs are high, what is the output of gate A2?
• Questions about the circuit’s structure are also interesting.
• For example, what are all the gates connected to the first input terminal?
• Does the circuit contain feedback loops?
• These will be our tasks in this section.
• There are more detailed levels of analysis, including those related to timing delays, circuit area,
power consumption, production cost, and so on.
• Each of these levels would require additional knowledge.

10
Prof. Salma Itagi,Dept. of CSE,SVIT
MODULE 4 ARTIFICIAL INTELLIGENCE(BCS515B)

Assemble the relevant knowledge

• What do we know about digital circuits? For our purposes, they are composed of wires and gates.
• Signals flow along wires to the input terminals of gates, and each gate produces a signal on the
output terminal that flows along another wire.
• To determine what these signals will be, we need to know how the gates transform their input
signals.
• There are four types of gates: AND, OR, and XOR gates have two input terminals, and NOT gates
have one.
• All gates have one output terminal.
• Circuits, like gates, have input and output terminals.
Decide on Vocabulary

• The next step is to choose functions, predicates, and constants to represent them.
• First, we need to be able to distinguish gates from each other and from other objects.
• Each gate is represented as an object named by a constant, about which we assert that it is a gate
with, say, Gate(X1).
• The behavior of each gate is determined by its type: one of the constants AND,OR, XOR, or NOT.
• Because a gate has exactly one type, a function is appropriate: Type(X1)=XOR.
• Circuits, like gates, are identified by a predicate: Circuit(C1).
• Next we consider terminals, which are identified by the predicate Terminal (x).
• A gate or circuit can have one or more input terminals and one or more output terminals.
• We use the function In(1,X1) to denote the first input terminal for gate X1.
• A similar function Out is used for output terminals.
• The function Arity(c, i, j) says that circuit c has i input and j output terminals.
• The connectivity between gates can be represented by a predicate, Connected, which takes two
terminals as arguments, as in Connected(Out(1,X1), In(1,X2)).
• Finally, we need to know whether a signal is on or off.
• One possibility is to use a unary predicate, On(t), which is true when the signal at a terminal is on.
• This makes it a little difficult, however, to pose questions such as “What are all the possible values
of the signals at the output terminals of circuit C1 ?”
• We therefore introduce as objects two signal values, 1 and 0, and a function Signal (t) that denotes
11
Prof. Salma Itagi,Dept. of CSE,SVIT
MODULE 4 ARTIFICIAL INTELLIGENCE(BCS515B)

the signal value for the terminal t.

• If two terminals are connected, then they have the same signal:
∀ t1, t2 Terminal (t1) ∧ Terminal (t2) ∧ Connected(t1, t2) ⇒ Signal (t1)=Signal (t2) .

Encode the specific problem instance

• First, we categorize the circuit and its component gates:
• Circuit(C1) ∧ Arity(C1, 3, 2)
• Gate(X1) ∧ Type(X1)=XOR
• Gate(X2) ∧ Type(X2)=XOR
12
Prof. Salma Itagi,Dept. of CSE,SVIT
MODULE 4 ARTIFICIAL INTELLIGENCE(BCS515B)

• Gate(A1) ∧ Type(A1)=AND
• Gate(A2) ∧ Type(A2)=AND
• Gate(O1) ∧ Type(O1)=OR .
• X1 (XOR): Computes A ⊕ B.
• X2 (XOR): Computes (A ⊕ B) ⊕ C_in to produce the Sum output.
• A1 (AND): Computes A ∧ B.
• A2 (AND): Computes C_in ∧ (A ⊕ B).
• O1 (OR): Computes the Carry-out (C_out) as the OR of the two AND gates' outputs.
• Then, we show the connections between them:
• Connected(Out(1,X1), In(1,X2)) Connected(In(1,C1), In(1,X1))
• Connected(Out(1,X1), In(2,A2)) Connected(In(1,C1), In(1,A1))
• Connected(Out(1,A2), In(1,O1)) Connected(In(2,C1), In(2,X1))
• Connected(Out(1,A1), In(2,O1)) Connected(In(2,C1), In(2,A1))
• Connected(Out(1,X2), Out(1,C1)) Connected(In(3,C1), In(2,X2))
• Connected(Out(1,O1), Out(2,C1)) Connected(In(3,C1), In(1,A2)) .
• 1. Connected(Out(1,X1), In(1,X2))
• Out(1, X1): The output of the first XOR gate X1.
• In(1, X2): The first input of the second XOR gate X2.
• This statement means that the output of X1 is connected to the first input of X2. In the full adder,
X1 calculates A ⊕ B, and this output is used as an input to X2, which calculates (A ⊕ B) ⊕ C_in
to produce the Sum.
• 2. Connected(In(1,C1), In(1,X1))
• In(1, C1): The first input of the circuit C1 (which has 3 inputs and 2 outputs, representing the 1-
bit full adder).
• In(1, X1): The first input of XOR gate X1.
• This connection means that A (from the inputs of the full adder) is connected to the first input of
XOR gate X1.
• 3. Connected(Out(1, X1), In(2, A2))
• Out(1, X1): The output of XOR gate X1.
• In(2, A2): The second input of AND gate A2.
• This means the output of X1 (which is A ⊕ B) is connected to the second input of the AND gate

13
Prof. Salma Itagi,Dept. of CSE,SVIT
MODULE 4 ARTIFICIAL INTELLIGENCE(BCS515B)

A2, where it is used as (A ⊕ B) in the carry calculation.

• 4. Connected(In(1, C1), In(1, A1))
• In(1, C1): The first input of the carry input C1.
• In(1, A1): The first input of AND gate A1.
• This means C_in (the carry input) is connected to the first input of A1, which calculates A ∧ B.
• 5. Connected(Out(1, A2), In(1, O1))
• Out(1, A2): The output of AND gate A2.
• In(1, O1): The first input of OR gate O1.
• The output of A2 (which is C_in ∧ (A ⊕ B)) is connected to the first input of OR gate O1, which
is part of the final carry-out calculation.
• 6. Connected(In(2, C1), In(2, X1))
• In(2, C1): The second input of the carry input C1.
• In(2, X1): The second input of XOR gate X1.
• This indicates that B is connected to the second input of X1 (to calculate A ⊕ B).
• 7. Connected(Out(1, A1), In(2, O1))
• Out(1, A1): The output of AND gate A1.
• In(2, O1): The second input of OR gate O1.
• The output of A1 (which is A ∧ B) is connected to the second input of OR gate O1, which combines
the results of the AND gates to calculate Carry-out.
• 8. Connected(In(2, C1), In(2, A1))
• In(2, C1): The second input of the carry input C1.
• In(2, A1): The second input of AND gate A1.
• This connection suggests that C_in (the carry input) is connected to the second input of AND gate
A1, participating in the calculation of Carry-out through the AND gates.
• 9. Connected(Out(1, X2), Out(1, C1))
• Out(1, X2): The output of XOR gate X2 (which is the final Sum output).
• Out(1, C1): The output of the full adder circuit C1 (the final result of the adder).
• This means that the Sum output of the full adder (Out(1, X2)) is connected to the final output of
the circuit C1.
• 10. Connected(In(3, C1), In(2, X2))
• In(3, C1): The third input of the full adder circuit C1.
• In(2, X2): The second input of XOR gate X2.
14
Prof. Salma Itagi,Dept. of CSE,SVIT
MODULE 4 ARTIFICIAL INTELLIGENCE(BCS515B)

• This means that C_in is connected to the second input of X2, as it is used to compute (A ⊕ B) ⊕
C_in for the Sum output.
• 11. Connected(Out(1, O1), Out(2, C1))
• Out(1, O1): The output of OR gate O1 (the Carry-out).
• Out(2, C1): The second output of the full adder circuit C1.
• This means that the Carry-out from O1 is connected to the Carry-out output of the full adder
circuit.
• 12. Connected(In(3, C1), In(1, A2))
• In(3, C1): The third input of the full adder circuit C1.
• In(1, A2): The first input of AND gate A2.
• This means that C_in is connected to the first input of AND gate A2, which is used in the
calculation of C_in ∧ (A ⊕ B) for the carry computation.
Summary:
• The 1-bit full adder circuit involves three types of gates: XOR, AND, and OR.
• The inputs are A, B, and C_in (carry input), and the outputs are Sum and Carry-out.
• The various Connected statements describe how these gates interact with each other, ensuring the
proper calculation of the Sum and Carry-out.
• The Sum is calculated by XORing A, B, and C_in, and the Carry-out is calculated using AND
and OR gates, based on the inputs.
• The connections reflect the standard logic for a 1-bit full adder where:
• Sum = (A ⊕ B) ⊕ C_in.
• Carry-out = (A ∧ B) ∨ (C_in ∧ (A ⊕ B)).
Pose queries to the inference procedure
• What combinations of inputs would cause the first output of C1 (the sum bit) to be 0 and the second
output of C1 (the carry bit) to be 1?
• ∃ i1, i2, i3 Signal (In(1, C1))=i1 ∧ Signal (In(2, C1))=i2 ∧ Signal (In(3, C1))=i3∧ Signal (Out(1,
C1))=0 ∧ Signal (Out(2, C1))=1 .
• The answers are substitutions for the variables i1, i2, and i3 such that the resulting sentence is
entailed by the knowledge base.
• ASKVARS will give us three such substitutions:
• {i1/1, i2/1, i3/0} {i1/1, i2/0, i3/1} {i1/0, i2/1, i3/1} .

15
Prof. Salma Itagi,Dept. of CSE,SVIT
MODULE 4 ARTIFICIAL INTELLIGENCE(BCS515B)

• What are the possible sets of values of all the terminals for the adder circuit?
• ∃ i1, i2, i3, o1, o2 Signal (In(1, C1))=i1 ∧ Signal (In(2, C1))=i2
• ∧ Signal (In(3, C1))=i3 ∧ Signal (Out(1, C1))=o1 ∧ Signal (Out(2, C1))=o2 .
• {i1/1, i2/1, i3/0}: Sum = 1 ⊕ 1 ⊕ 0 = 0 (sum is 0) and carry-out = (1 ∧ 1) ∨ (1 ∧ 0) ∨ (1 ∧ 0) = 1
(carry-out is 1).
• Cout=(A∧B)∨(B∧Cin)∨(A∧Cin)

For example:
{i1=0, i2=0, i3=0, o1=0, o2=0}
Debug the knowledge base

16
Prof. Salma Itagi,Dept. of CSE,SVIT
MODULE 4 ARTIFICIAL INTELLIGENCE(BCS515B)

• The system is unable to infer the correct behavior of the XOR gate for certain input combinations,
like 1 and 0.
• This failure to infer is due to the lack of knowledge about the relationship between those inputs
(i.e., that 1 and 0 are different).
• By examining the axiom for the XOR gate and testing for the output at each gate, it becomes clear
that the system needs to be explicitly told about the condition 1 ≠ 0 in order to deduce the correct
output.
• Once this information is provided, the system can correctly infer that Signal (Out(1, X1)) = 1 when
the inputs are 1 and 0.
In essence, the problem is a missing or forgotten assertion that would allow the system to properly deduce
the XOR gate's output.
INFERENCE IN FIRST ORDER LOGIC
• Propositional vs First order inference
• Inference Rules for Quantifiers
All greedy kings are evil
• ∀ x King(x) ∧ Greedy(x) ⇒ Evil(x) .
• Then it seems quite permissible to infer any of the following sentences:
• King(John) ∧ Greedy(John) ⇒ Evil(John)
• King(Richard ) ∧ Greedy(Richard) ⇒ Evil(Richard)
• King(Father (John)) ∧ Greedy(Father (John)) ⇒ Evil(Father (John)) .
• The rule of Universal Instantiation (UI for short) says that we can infer any sentence obtained by
substituting a ground term (a term without variables) for the variable.

17
Prof. Salma Itagi,Dept. of CSE,SVIT
MODULE 4 ARTIFICIAL INTELLIGENCE(BCS515B)

Reduction to propositional Inference

• Let’s consider an example:
• PredicateLogicStatement:
∀x (Person(x) → ∃y (FriendOf(y, x)))
• This statement says: "For all x, if x is a person, there exists a y such that y is a friend of x."
Step 1: Eliminate quantifiers by replacing them with specific constants.
• "Person(x)" becomes propositional variables like Person(a), Person(b).
• "FriendOf(y, x)" becomes FriendOf(a, b), FriendOf(b, a), and so on.
Step 2: Convert the logical operations (→ and ∃) into simpler logical connectives.
• "Person(x) → ∃y (FriendOf(y, x))" becomes "¬Person(x) ∨ ∃y FriendOf(y, x)"
• (implication is replaced by disjunction and negation).
Step 3: Replace existential quantifiers with propositional variables, e.g., FriendOf(a, b).
• Thus, the original statement can be reduced to a set of propositional logic clauses.
UNIFICATION AND LIFTING

18
Prof. Salma Itagi,Dept. of CSE,SVIT
MODULE 4 ARTIFICIAL INTELLIGENCE(BCS515B)

Premises
We have a series of n atomic sentences (propositions), denoted by:
• p1,p2,…, pn
• P1is: King(x)
• p2 is: Greedy(x)
Additionally, there is one implication involving these premises:
• (p1∧ p2 ∧⋯∧ p2n⇒q)
• This implication states that if all the premises p1,p2,…, pn are true, then the conclusion q must also
be true.
• (P1∧P2⇒q) where q is: Evil(x)
So, the implication says:
• "If P1 (King(x)) and P1 (Greedy(x)) are true, then q(Evil(x)) must also be true."
Substitution (θ)
The substitution θ is given as:
• θ={x/John,y/John}
This substitution says:
• Replace x with John in all occurrences of x.
• Replace y with John in all occurrences of y.
Thus, when you apply this substitution to a formula, you replace the variables x and y with the constant
"John."
Substitution Applied to the Conclusion (q)
The final part of the rule is applying the substitution θ to the consequent q, which is Evil(x) q is Evil(x)
meaning "x is evil."
19
Prof. Salma Itagi,Dept. of CSE,SVIT
MODULE 4 ARTIFICIAL INTELLIGENCE(BCS515B)

• After applying the substitution θ={x/John,y/John}, you replace the variable x with "John".
Therefore:
• SUBST(θ,q) becomes Evil(John)
So, after substitution, the conclusion becomes Evil(John), which asserts that John is evil.
Here’s a complete breakdown of how this rule works in the context of the given example:
1. Premises:
1. p1:King(x) (John is a King)
2. p2:Greedy (John is Greedy)
3. The rule: If p1and p2 are true, then q (Evil(x)) is true.
2. Implication (Rule):
1. (p1∧p2⇒q) which reads: "If John is a King and greedy, then John is evil."
3. Substitution:
1. θ={x/John,y/John}, meaning replace all instances of x and y with "John."
4. Conclusion after applying the substitution:
1. q=Evil(x), and after applying θ , it becomes Evil(John).
Thus, the result of applying the substitution θ to q is that John is evil.
UNIFICATION
• UNIFY(Knows(John, x), Knows(John, Jane)) = {x/Jane}
• Substitution: x→Jane
• UNIFY(Knows(John, x), Knows(y, Bill )) = {x/Bill, y/John}
• Substitution: x→Bill,y→John
• UNIFY(Knows(John, x), Knows(y,Mother (y))) = {y/John, x/Mother (John)}
• Substitution: y→John,x→Mother(John)
• UNIFY(Knows(John, x), Knows(x, Elizabeth)) = fail .
• Fail: The unification fails because of a contradiction in the substitution for x.

20
Prof. Salma Itagi,Dept. of CSE,SVIT
MODULE 4 ARTIFICIAL INTELLIGENCE(BCS515B)

•
Example 1:
We want to unify the terms
Knows(John, x) and Knows(John, Jane).
• The operator Knows is the same for both terms.
• The first argument is John in both cases, so they are already unified.
• The second argument is x in the first term and Jane in the second term. We need to unify x with
Jane.
The unification is possible, and the substitution becomes {x → Jane}.
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.
21
Prof. Salma Itagi,Dept. of CSE,SVIT
MODULE 4 ARTIFICIAL INTELLIGENCE(BCS515B)

• Here, we explain how the algorithm is applied to first-order definite clauses.

• Definite clauses such as Situation ⇒ Response are especially useful for systems that make
inferences in response to newly arrived information.
• Forward Chaining is a method of reasoning used in rule-based systems and expert systems. It is a
form of data-driven reasoning where the inference engine starts with the available facts and applies
inference rules to extract new facts, progressively working forward through the knowledge base.

Eg:
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 ColonelWest, who is
American.
American(x) ∧Weapon(y) ∧ Sells(x, y, z) ∧ Hostile(z) ⇒ Criminal (x) .

22
Prof. Salma Itagi,Dept. of CSE,SVIT
MODULE 4 ARTIFICIAL INTELLIGENCE(BCS515B)

Algorithm Steps Explained:

1. Initialize:
• The algorithm starts by initializing the new set to empty. This set will collect all newly inferred
facts on each iteration.
2. Repeat Until New Facts Are Inferred:
• The loop continues until no new facts are inferred, i.e., when the new set is empty. This ensures
that the algorithm will keep applying the rules to infer facts until no further progress can be made.
3. Standardizing Variables in Rules:
• For each rule in the knowledge base, the algorithm applies standardization. The function
STANDARDIZE-VARIABLES(rule) ensures that all variables in the rule are renamed so that no
two rules share the same variable names. This prevents variable conflicts during unification.
• Example: If two rules have variables x and y, STANDARDIZE-VARIABLES will rename
them (e.g., x1 and y1 ) to avoid confusion when performing unification.
4. Try to Match Rules with Known Facts:
• For each rule in the KB, it looks for substitutions θ that match the left-hand side (the premises)
of the rule with some existing facts in the KB.
• It checks all combinations of the premises p1 ,p2 ,…, pn from the KB (i.e., the left side of the rule).
• The algorithm compares the premises of the rule against the existing facts (which could be in KB
or new facts) to see if any of them unify with the premises. If a match is found, the rule’s conclusion
q is derived using the unification of those facts.
23
Prof. Salma Itagi,Dept. of CSE,SVIT
MODULE 4 ARTIFICIAL INTELLIGENCE(BCS515B)

5. Apply Substitution to the Conclusion:

• If a match is found (i.e., a valid substitution θ is found), the algorithm applies the substitution to
the conclusion q of the rule:
• q' = SUBST(θ, q): This means the right-hand side (conclusion) of the rule is modified using
the substitution θ.
6. Check for Redundant Conclusions:
• After obtaining q′, the algorithm checks if q′already exists in the KB or in the set of newly inferred
facts (new).
• If q′is already present, it is not added again.
• If q′ is new, it is added to the new set. This ensures that only new, unique facts are added
to the knowledge base.
7. Unify with the Query:
• After the fact q′ has been added to the new set, the algorithm checks if this fact unifies with the
query α.
• φ = UNIFY(q', α): The function UNIFY tries to find a substitution φ that makes q′and α
identical.
• If UNIFY succeeds (i.e., returns a non-failing substitution φ), then the query is provable
from the knowledge base, and the algorithm returns φ, the substitution that makes the query
true.
8. Add New Facts to KB:
• If no valid unification is found for any q′, the new facts are added to the knowledge base KB.
• This is done so that these newly inferred facts can be used in the next iteration to infer
further facts.
9. Return False if Query is Not Provable:
• If, after all iterations, no unification is found for α, meaning no substitution makes the query true,
the algorithm returns false. This means that the query α cannot be derived from the knowledge
base.

24
Prof. Salma Itagi,Dept. of CSE,SVIT
MODULE 4 ARTIFICIAL INTELLIGENCE(BCS515B)

•
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.
• This method uses First Order Definite clause .
• 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.
For example
• King(x) ∧ Greedy(x) ⇒ Evil(x) .
• King(John) .
• Greedy(y) .
• The law says that it is a crime for an American to sell weapons to hostile nations. The country
25
Prof. Salma Itagi,Dept. of CSE,SVIT
MODULE 4 ARTIFICIAL INTELLIGENCE(BCS515B)

Nono, an enemy of America, has some missiles, and all of its missiles were sold to it by
ColonelWest, who is American.
• We will prove that West is a criminal.
• Representation of this by using first order definite clauses.
• So 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
• “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
• “All of its missiles were sold to it by Colonel West”:
Missile(x) ∧ Owns(Nono, x) ⇒ Sells(West, x, Nono) ---4
• We will also need to know that missiles are weapons:
Missile(x) ⇒ Weapon(x) ----5
• An enemy of America counts as “hostile”:
• Enemy(x,America) ⇒ Hostile(x) ----6
• “West, who is American . . .”:
• American(West) -----7
• “The country Nono, an enemy of America . . .”:
• Enemy(Nono,America) .
• This knowledge base contains no function symbols and is therefore an instance of the class
of Datalog knowledge bases.
• Datalog is a language that is restricted to first-order definite clauses with no function symbols.
• 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 or no new facts are
added.
• 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.
• On the second iteration, rule 1 is satisfied with {x/West, y/M1, z/Nono}, and Criminal (West) is
26
Prof. Salma Itagi,Dept. of CSE,SVIT
MODULE 4 ARTIFICIAL INTELLIGENCE(BCS515B)

added.

Steps:
1. Initialization
2. Loop until new is empty
3. Processing each rule
4. Finding applicable premises
5. Checking for duplicates
6. Unifying with the query
7. Adding new facts to KB
8. Termination

27
Prof. Salma Itagi,Dept. of CSE,SVIT
MODULE 4 ARTIFICIAL INTELLIGENCE(BCS515B)

Efficient Forward Chaining

• There are three possible sources of inefficiency.
• First, the “inner loop” of the algorithm involves finding all possible unifiers such that the premise
of a rule unifies with a suitable set of facts in the knowledge base. This is often called pattern
matching and can be very expensive.
• Second, the algorithm rechecks every rule on every iteration to see whether its premises are
satisfied, even if very few additions are made to the knowledge base on each iteration.
• Finally, the algorithm might generate many facts that are irrelevant to the goal.

28
Prof. Salma Itagi,Dept. of CSE,SVIT