UNIT-III

First-Order Logic - Syntax and Semantics of First-Order Logic, Using First Order Logic, Knowledge
Engineering in First-Order Logic.
Inference in First-Order Logic: Propositional vs. First-Order Inference, Unification, Forward
Chaining, Backward Chaining, Resolution.

First-Order Logic
In the topic of Propositional logic, we have seen that how to represent statements using propositional
logic. But unfortunately, in propositional logic, we can only represent the facts, which are either true or
false. PL is not sufficient to represent the complex sentences or natural language statements. The
propositional logic has very limited expressive power. Consider the following sentence, which we
cannot represent using PL logic.

o "Some humans are intelligent", or

o "Sachin likes cricket."

To represent the above statements, PL logic is not sufficient, so we required some more powerful logic,
such as first-order logic.

First-Order logic:

o First-order logic is another way of knowledge representation in artificial intelligence. It is an

extension to propositional logic.
o FOL is sufficiently expressive to represent the natural language statements in a concise way.
o First-order logic is also known as Predicate logic or First-order predicate logic. First-order
logic is a powerful language that develops information about the objects in a more easy way and
can also express the relationship between those objects.
o First-order logic (like natural language) does not only assume that the world contains facts like
propositional logic but also assumes the following things in the world:
o Objects: A, B, people, numbers, colors, wars, theories, squares, pits, wumpus, ......
o Relations: It can be unary relation such as: red, round, is adjacent, or n-any relation
such as: the sister of, brother of, has color, comes between
o Function: Father of, best friend, third inning of, end of, ......
o As a natural language, first-order logic also has two main parts:
a. Syntax
b. Semantics
Syntax of First-Order logic:

The syntax of FOL determines which collection of symbols is a logical expression in first-order logic.
The basic syntactic elements of first-order logic are symbols. We write statements in short-hand
notation in FOL.

Basic Elements of First-order logic:

Following are the basic elements of FOL syntax:

Constant 1, 2, A, John, Mumbai, cat,....

Variables x, y, z, a, b,....
Predicates Brother, Father, >,....
Function sqrt, LeftLegOf, ....
Connectives ∧, ∨, ¬, ⇒, ⇔
Equality ==
Quantifier ∀, ∃

Atomic sentences:

o Atomic sentences are the most basic sentences of first-order logic. These sentences are formed
from a predicate symbol followed by a parenthesis with a sequence of terms.
o We can represent atomic sentences as Predicate (term1, term2, ......, term n).

Example: Ravi and Ajay are brothers: => Brothers (Ravi, Ajay).
Chinky is a cat: => cat (Chinky).

Complex Sentences:

o Complex sentences are made by combining atomic sentences using connectives.

First-order logic statements can be divided into two parts:

o Subject: Subject is the main part of the statement.

o Predicate: A predicate can be defined as a relation, which binds two atoms together in a
statement.

Consider the statement: "x is an integer.", it consists of two parts, the first part x is the subject of the
statement and second part "is an integer," is known as a predicate.
Quantifiers in First-order logic:

o A quantifier is a language element which generates quantification, and quantification specifies

the quantity of specimen in the universe of discourse.
o These are the symbols that permit to determine or identify the range and scope of the variable in
the logical expression. There are two types of quantifier:
a. Universal Quantifier, (for all, everyone, everything)
b. Existential quantifier, (for some, at least one).

Universal Quantifier:

Universal quantifier is a symbol of logical representation, which specifies that the statement within its
range is true for everything or every instance of a particular thing.

The Universal quantifier is represented by a symbol ∀, which resembles an inverted A.

Note: In universal quantifier we use implication "→".

If x is a variable, then ∀x is read as:

o For all x
o For each x
o For every x.

Example:

All man drink coffee.

Let a variable x which refers to a cat so all x can be represented in UOD as below:
∀x man(x) → drink (x, coffee).

It will be read as: There are all x where x is a man who drink coffee.

Existential Quantifier:

Existential quantifiers are the type of quantifiers, which express that the statement within its scope is
true for at least one instance of something.

It is denoted by the logical operator ∃, which resembles as inverted E. When it is used with a predicate
variable then it is called as an existential quantifier.

Note: In Existential quantifier we always use AND or Conjunction symbol (∧).

If x is a variable, then existential quantifier will be ∃x or ∃(x). And it will be read as:

o There exists a 'x.'

o For some 'x.'
o For at least one 'x.'

Example:

Some boys are intelligent.

∃x: boys(x) ∧ intelligent(x)

It will be read as: There are some x where x is a boy who is intelligent.

Points to remember:

o The main connective for universal quantifier ∀ is implication →.

o The main connective for existential quantifier ∃ is and ∧.

Properties of Quantifiers:

o In universal quantifier, ∀x∀y is similar to ∀y∀x.

o In Existential quantifier, ∃x∃y is similar to ∃y∃x.
o ∃x∀y is not similar to ∀y∃x.

Some Examples of FOL using quantifier:

1. All birds fly.

In this question the predicate is "fly(bird)."
And since there are all birds who fly so it will be represented as follows.
∀x bird(x) →fly(x).

2. Every man respects his parent.

In this question, the predicate is "respect(x, y)," where x=man, and y= parent.
Since there is every man so will use ∀, and it will be represented as follows:
∀x man(x) → respects (x, parent).

3. Some boys play cricket.

In this question, the predicate is "play(x, y)," where x= boys, and y= game. Since there are some boys
so we will use ∃, and it will be represented as:
∃x boys(x) → play(x, cricket).

4. Not all students like both Mathematics and Science.

In this question, the predicate is "like(x, y)," where x= student, and y= subject.
Since there are not all students, so we will use ∀ with negation, so following representation for this:
¬∀ (x) [ student(x) → like(x, Mathematics) ∧ like(x, Science)].

5. Only one student failed in Mathematics.

In this question, the predicate is "failed(x, y)," where x= student, and y= subject.
Since there is only one student who failed in Mathematics, so we will use following representation for
this:
∃(x) [ student(x) → failed (x, Mathematics) ∧∀ (y) [¬(x==y) ∧ student(y) → ¬failed (x,
Mathematics)].

Free and Bound Variables:

The quantifiers interact with variables which appear in a suitable way. There are two types of variables
in First-order logic which are given below:

Free Variable: A variable is said to be a free variable in a formula if it occurs outside the scope of the
quantifier.

Example: ∀x ∃(y)[P (x, y, z)], where z is a free variable.

Bound Variable: A variable is said to be a bound variable in a formula if it occurs within the scope of
the quantifier.

Example: ∀x [A (x) B( y)], here x and y are the bound variables.

USING FIRST-ORDER LOGIC

• Now that we have defined an expressive logical language, it is time to learn how to use it.
• In knowledge representation, a domain is just some part of the world about which we wish to
express some knowledge.
• We begin with a brief description of the TELL/ASK interface for first-order knowledge bases.
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, ASSERTION 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.
• Generally speaking, any query that is logically entailed by the knowledge base should be
answered affirmatively.
• For example, 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, but this is perhaps not as helpful as we would like. It is rather like answering
“Can you tell me the time?” with “Yes.”
• 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.
• ASKVARS is usually reserved for knowledge bases consisting solely of Horn clauses, because in
such knowledge bases every way of making the query true will bind the variables to specific
values. That is not the case with first-order logic;
• if KB has been told King(John) ∨ King(Richard ), then there is no binding to x for the query ∃ x
King(x), even though the query is true.

The kinship domain

• we consider 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.”
• Clearly, the objects in our domain are people. We have two unary predicates, Male andFemale.
• 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.
We can go through each function and predicate, writing down what we know in terms of the other
symbols.

For example, one’s mother is one’s female parent:

∀ m, c Mother (c)=m ⇔ Female(m) ∧ Parent(m, c) .
One’s husband is one’s male spouse:
∀ w, h Husband(h,w) ⇔ Male(h) ∧ Spouse(h,w) .
Male and female are disjoint categories:
∀ x Male(x) ⇔ ￢Female(x) .
Parent and child are inverse relations:
∀ p, c Parent(p, c) ⇔ Child (c, p) .
A grandparent is a parent of one’s parent:
∀ g, c Grandparent (g, c) ⇔ ∃p Parent(g, p) ∧ Parent(p, c) .
A sibling is another child of one’s parents:
∀ x, y Sibling(x, y) ⇔ x _= y ∧ ∃p Parent(p, x) ∧ Parent(p, y) .
• Axioms are commonly associated with purely mathematical domains—we will see some axioms
for numbers shortly—but they are needed in all domains.
• They provide the basic factual information from which useful conclusions can be derived.
• Our kinship axioms are also definitions; they have the DEFINITION form ∀ x, y P(x, y) ⇔ . . ..
• The axioms define the Mother function and the Husband, Male, Parent, Grandparent, and Sibling
predicates in terms of other predicate

Numbers, sets, and lists

• Numbers are perhaps the most vivid example of how a large theory can be built up from a tiny
kernel of axioms.
• We describe here NATURAL NUMBERS the theory of natural numbers or non-negative
integers. We need a predicate Nat_Num 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.9 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
number. So the natural numbers are 0, S(0), S(S(0)), and so on We also need axioms to constrain the
successor function:
∀ n 0 != S(n) .
∀ m, n m!= n ⇒ S(m)!= S(n) .
Now we can define addition in terms of the successor function:
∀m NatNum(m) ⇒ + (0,m) = m .
∀ m, n NatNum(m) ∧ NatNum(n) ⇒ + (S(m), n) = S(+(m, n)) .
• The first of these axioms says that adding 0 to any natural number m gives m itself.
• Notice the use of the binary function symbol “+” in the term +(m, 0); in ordinary mathematics,
the term would be written m + 0 using infix notation.
• The domain of sets is also fundamental to mathematics as well as to commonsense reasoning. (In
fact, it is possible to define number theory in terms of set theory.)
• We want to be able to represent individual sets, including the empty set.
• We need a way to build up sets by adding an element to a set or taking the union or intersection
of two sets.
• We will want to know whether an element is a member of a set and we will want to distinguish
sets from objects that are not sets.
• 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
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 LIST 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. As with sets, it is common to use syntactic sugar in logical
sentences involving 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))).

KNOWLEDGE ENGINEERING IN FIRST-ORDER LOGIC

• The general process of knowledge-base construction—a process called knowledge engineering.

 • A knowledge engineer is someone who investigates a particular domain, learns what concepts are
important in that domain, and creates a formal representation of the objects and relations in the
domain.

The knowledge-engineering process:

Knowledge engineering projects vary widely in content, scope, and difficulty, but all such projects
include the following steps:
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. For
example, does the Wumpus knowledge base need to be able to choose actions or is it required to answer
questions only about the contents of the environment? Will the sensor facts include the current location?
The task will determine what knowledge must be represented in order to connect problem instances to
answers.
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. 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.
For the wumpus world, which is defined by an artificial set of rules, the relevant knowledge is easy to
identify. (Notice, however, that the definition of adjacency was not supplied explicitly in the wumpus-
world rules.) For real domains, the issue of relevance can be quite difficult—for example, a system for
simulating VLSI designs might or might not need to take into account stray capacitances and skin
effects.
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 ONTOLOGY 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 thoughtout, 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. Thus, we avoid the need for writing an application-specific solution algorithm.
7. Debug the knowledge base. Alas, 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. For example, if an axiom is
missing, some queries will not be answerable from the knowledge base. A considerable debugging
process could ensue. Missing axioms or axioms that are too weak can be easily identified by noticing
places where the chain of reasoning stops unexpectedly.

The electronic circuits domain

In this topic, we will understand the Knowledge engineering process in an electronic circuit domain,
develop a knowledge base which will allow us to reason about digital circuit (One-bit full adder)
which is given below.
1. Identify the task:

The first step of the process is to identify the task, and for the digital circuit, there are various reasoning
tasks. At the first level or highest level, we will examine the functionality of the circuit:

o Does the circuit add properly?

o What will be the output of gate A2, if all the inputs are high?

At the second level, we will examine the circuit structure details such as:

o Which gate is connected to the first input terminal?

o Does the circuit have feedback loops?

2. Assemble the relevant knowledge:

In the second step, we will assemble the relevant knowledge which is required for digital circuits. So for
digital circuits, we have the following required knowledge:

o Logic circuits are made up of wires and gates.

o Signal flows through wires to the input terminal of the gate, and each gate produces the
corresponding output which flows further.

o In this logic circuit, there are four types of gates used: AND, OR, XOR, and NOT.
o All these gates have one output terminal and two input terminals (except NOT gate, it has one
input terminal).
3. Decide on vocabulary:

The next step of the process is to select functions, predicate, and constants to represent the circuits,
terminals, signals, and gates. Firstly we will distinguish the gates from each other and from other
objects. Each gate is represented as an object which is named by a constant, such as, Gate(X1). The
functionality of each gate is determined by its type, which is taken as constants such as AND, OR,
XOR, or NOT. Circuits will be identified by a predicate: Circuit (C1).

For the terminal, we will use predicate: Terminal(x).

For gate input, we will use the function In(1, X1) for denoting the first input terminal of the gate, and
for output terminal we will use Out (1, X1).

The function Arity(c, i, j) is used to denote that circuit c has i input, j output.

The connectivity between gates can be represented by predicate Connect(Out(1, X1), In(1, X1)).

We use a unary predicate On (t), which is true if the signal at a terminal is on.

4. Encode general knowledge about the domain:

To encode the general knowledge about the logic circuit, we need some following rules:

o If two terminals are connected then they have the same input signal, it can be represented as:

∀ t1, t2 Terminal (t1) ∧ Terminal (t2) ∧ Connect (t1, t2) → Signal (t1) = Signal (2).

o Signal at every terminal will have either value 0 or 1, it will be represented as:

∀ t Terminal (t) →Signal (t) = 1 ∨Signal (t) = 0.

o Connect predicates are commutative:

∀ t1, t2 Connect(t1, t2) → Connect (t2, t1).

o Representation of types of gates:

∀ g Gate(g) ∧ r = Type(g) → r = OR ∨r = AND ∨r = XOR ∨r = NOT.

 o Output of AND gate will be zero if and only if any of its input is zero.

∀ g Gate(g) ∧ Type(g) = AND →Signal (Out(1, g))= 0 ⇔ ∃n Signal (In(n, g))= 0.

o Output of OR gate is 1 if and only if any of its input is 1:

∀ g Gate(g) ∧ Type(g) = OR → Signal (Out(1, g))= 1 ⇔ ∃n Signal (In(n, g))= 1

o Output of XOR gate is 1 if and only if its inputs are different:

∀ g Gate(g) ∧ Type(g) = XOR → Signal (Out(1, g)) = 1 ⇔ Signal (In(1, g)) ≠ Signal (In(2, g)).

o Output of NOT gate is invert of its input:

∀ g Gate(g) ∧ Type(g) = NOT → Signal (In(1, g)) ≠ Signal (Out(1, g)).

o All the gates in the above circuit have two inputs and one output (except NOT gate).

∀ g Gate(g) ∧ Type(g) = NOT → Arity(g, 1, 1)

∀ g Gate(g) ∧ r =Type(g) ∧ (r= AND ∨r= OR ∨r= XOR) → Arity (g, 2, 1).

o All gates are logic circuits:

∀ g Gate(g) → Circuit (g).

5. Encode a description of the problem instance:

Now we encode problem of circuit C1, firstly we categorize the circuit and its gate components. This
step is easy if ontology about the problem is already thought. This step involves the writing simple
atomics sentences of instances of concepts, which is known as ontology.

For the given circuit C1, we can encode the problem instance in atomic sentences as below:

For XOR gate: Type(x1)= XOR, Type(X2) = XOR

For AND gate: Type(A1) = AND, Type(A2)= AND
For OR gate: Type (O1) = OR.
Since in the circuit there are two XOR, two AND, and one OR gate so atomic sentences for these gates
will be: And then represent the connections between all the gates.

6. Pose queries to the inference procedure and get answers:

In this step, we will find all the possible set of values of all the terminal for the adder circuit. The first
query will be:

What should be the combination of input which would generate the first output of circuit C1, as 0 and a
second output 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

7. Debug the knowledge base:

Now we will debug the knowledge base, and this is the last step of the complete process. In this step, we
will try to debug the issues of knowledge base.

INFERENCE IN FIRST-ORDER LOGIC

In which we define effective procedures for answering questions posed in first order logic.
Inference in First-Order Logic is used to deduce new facts or sentences from existing sentences. Before
understanding the FOL inference rule, let's understand some basic terminologies used in FOL.

Substitution:

Substitution is a fundamental operation performed on terms and formulas. It occurs in all inference
systems in first-order logic. The substitution is complex in the presence of quantifiers in FOL. If we
write F[a/x], so it refers to substitute a constant "a" in place of variable "x".

Equality:

First-Order logic does not only use predicate and terms for making atomic sentences but also uses
another way, which is equality in FOL. For this, we can use equality symbols which specify that the
two terms refer to the same object.
Example: Brother (John) = Smith.

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

Example: ￢(x=y) which is equivalent to x ≠y.

FOL inference rules for quantifier:

As propositional logic we also have inference rules in first-order logic, so following are some basic
inference rules in FOL:

Universal Instantiation:

o Universal instantiation is also called as universal elimination or UI is a valid inference rule. It can
be applied multiple times to add new sentences.

o The new KB is logically equivalent to the previous KB.

o As per UI, we can infer any sentence obtained by substituting a ground term for the
variable.

o The UI rule state that we can infer any sentence P(c) by substituting a ground term c (a constant
within domain x) from ∀ x P(x) for any object in the universe of discourse.

o It can be represented as: .

Example:1.

IF "Every person like ice-cream"=> ∀x P(x) so we can infer that

"John likes ice-cream" => P(c)

Example: 2.Let's take a famous example,

"All kings who are greedy are Evil." So let our knowledge base contains this detail as in the form of
FOL: ∀x king(x) ∧ greedy (x) → Evil (x),
So from this information, we can infer any of the following statements using Universal Instantiation:

o King(John) ∧ Greedy (John) → Evil (John),

o King(Richard) ∧ Greedy (Richard) → Evil (Richard),

o King(Father(John)) ∧ Greedy (Father(John)) → Evil (Father(John)),

Existential Instantiation:

o Existential instantiation is also called as Existential Elimination, which is a valid inference rule in
first-order logic.
o It can be applied only once to replace the existential sentence.

o The new KB is not logically equivalent to old KB, but it will be satisfiable if old KB was
satisfiable.

o This rule states that one can infer P(c) from the formula given in the form of ∃x P(x) for a new
constant symbol c.

o The restriction with this rule is that c used in the rule must be a new term for which P(c ) is true.

o It can be represented as:

o Example:
o From the given sentence: ∃x Crown(x) ∧ OnHead(x, John),

So we can infer: Crown(K) ∧ OnHead( K, John), as long as K does not appear in the knowledge base.

o The above used K is a constant symbol, which is called Skolem constant.

o The Existential instantiation is a special case of Skolemization process.

Generalized Modus Ponens Rule:

For the inference process in FOL, we have a single inference rule which is called Generalized Modus
Ponens. It is lifted version of Modus ponens.

Generalized Modus Ponens can be summarized as, " P implies Q and P is asserted to be true, therefore
Q must be True."
According to Modus Ponens, for atomic sentences pi, pi', q. Where there is a substitution θ such that
SUBST (θ, pi',) = SUBST(θ, pi), it can be represented as:

Example:

We will use this rule for Kings are evil, so we will find some x such that x is king, and x is greedy
so we can infer that x is evil.

1. Here let say, p1' is king(John) p1 is king(x)

2. p2' is Greedy(y) p2 is Greedy(x)
3. θ is {x/John, y/John} q is evil(x)
4. SUBST(θ,q).

UNIFICATION:

o Unification is a process of making two different logical atomic expressions identical by finding a
substitution. Unification depends on the substitution process.

o It takes two literals as input and makes them identical using substitution.

o Let A1 and A2 be two atomic sentences and 𝜎 be a unifier such that, A1𝜎 = A2𝜎, then it can be
expressed as UNIFY(A1, A2).

o Example: Find the MGU for Unify{King(x), King(John)}

Let A1 = King(x), A2 = King(John),

Substitution θ = {John/x} is a unifier for these atoms and applying this substitution, and both
expressions will be identical.

o The UNIFY algorithm is used for unification, which takes two atomic sentences and returns a
unifier for those sentences (If any exist).
o Unification is a key component of all first-order inference algorithms.
 o It returns fail if the expressions do not match with each other.

o The substitution variables are called Most General Unifier or MGU.

E.g. Let's say there are two different expressions, P(x, y), and P(a, f(z)).

In this example, we need to make both above statements identical to each other. For this, we will
perform the substitution.

P(x, y)......... (i)

P(a, f(z))......... (ii)

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

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

o Predicate symbol must be same, atoms or expression with different predicate symbol can never
be unified.

o Number of Arguments in both expressions must be identical.

o Unification will fail if there are two similar variables present in the same expression.

Algorithm: Unify(A1, A2)

Step. 1: If A1 or A2 is a variable or constant, then:

a) If A1 or A2 are identical, then return NIL.

b) Else if A1is a variable,

a. then if A1 occurs in A2, then return FAILURE

 b. Else return { (A2/ A1)}.

c) Else if A2 is a variable,

a. If A2 occurs in A1 then return FAILURE,

b. Else return {( A1/ A2)}.

d) Else return FAILURE.

Step.2: If the initial Predicate symbol in A1 and A2 are not same, then return FAILURE.

Step. 3: IF A1 and A2 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 A1.

a) Call Unify function with the ith element of A1 and ith element of A2, 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.

Forward Chaining and backward chaining

Inference engine:

The inference engine is the component of the intelligent system in artificial intelligence, which applies
logical rules to the knowledge base to infer new information from known facts. The first inference
engine was part of the expert system. Inference engine commonly proceeds in two modes, which are:
a. Forward chaining

b. Backward chaining

Horn Clause and Definite clause:

Horn clause and definite clause are the forms of sentences, which enables knowledge base to use a more
restricted and efficient inference algorithm. Logical inference algorithms use forward and backward
chaining approaches, which require KB in the form of the first-order definite clause.

Definite clause: A clause which is a disjunction of literals with exactly one positive literal is known as
a definite clause or strict horn clause.

Horn clause: A clause which is a disjunction of literals with at most one positive literal is known as
horn clause. Hence all the definite clauses are horn clauses.

Example: (¬ p V ¬ q V k). It has only one positive literal k.

It is equivalent to p ∧ q → k.

A. 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:

o It is a down-up approach, as it moves from bottom to top.

 o 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.
o Forward-chaining approach is also called as data-driven as we reach to the goal using available
data.
o Forward -chaining approach is commonly used in the expert system, such as CLIPS, business,
and production rule systems.

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, we will convert all the above facts into first-order definite clauses,
and then we will use a forward-chaining algorithm to reach the goal.

Facts Conversion into FOL:

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

o Country A has some missiles. ?p Owns(A, p) ∧ Missile(p). It can be written in two definite
clauses by using Existential Instantiation, introducing new Constant T1.
Owns(A, T1) ......(2)
Missile(T1) .......(3)

o All of the missiles were sold to country A by Robert.

?p Missiles(p) ∧ Owns (A, p) → Sells (Robert, p, A) ......(4)

o Missiles are weapons.

Missile(p) → Weapons (p) .......(5)
o Enemy of America is known as hostile.
Enemy(p, America) →Hostile(p) ........(6)
 o Country A is an enemy of America.
Enemy (A, America) .........(7)
o Robert is American
American(Robert). ..........(8)

Forward chaining proof:

Step-1:

In the first step we will start with 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, we will 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).

Step-3:
At step-3, as we can check Rule-(1) is satisfied with the substitution {p/Robert, q/T1, r/A}, so we can
add Criminal(Robert) which infers all the available facts. And hence we reached our goal statement.

B. 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:

o It is known as a top-down approach.

o Backward-chaining is based on modus ponens inference rule.

o In backward chaining, the goal is broken into sub-goal or sub-goals to prove the facts true.
o It is called a goal-driven approach, as a list of goals decides which rules are selected and used.

o Backward -chaining algorithm is used in game theory, automated theorem proving tools,
inference engines, proof assistants, and various AI applications.
o The backward-chaining method mostly used a depth-first search strategy for proof.

Example:

In backward-chaining, we will use the same above example, and will rewrite all the rules.
 o American (p) ∧ weapon(q) ∧ sells (p, q, r) ∧ hostile(r) → Criminal(p) ...(1)
Owns(A, T1) ........(2)
o Missile(T1)

o ?p Missiles(p) ∧ Owns (A, p) → Sells (Robert, p, A) ......(4)

o Missile(p) → Weapons (p) .......(5)

o Enemy(p, America) →Hostile(p) ........(6)

o Enemy (A, America) .........(7)

o American(Robert). ..........(8)

Backward-Chaining proof:

In Backward chaining, we will start with our goal predicate, which is Criminal(Robert), and then infer
further rules.

Step-1:

At the first step, we will take the goal fact. And from the goal fact, we will infer other facts, and at last,
we will prove those facts true. So our goal fact is "Robert is Criminal," so following is the predicate of
it.

Step-2:

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

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

Step-3:t At step-3, we 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, we 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.
Step-5:

At step-5, we 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.

Resolution

• Resolution is a theorem proving technique that proceeds by building refutation proofs, i.e., proofs
by contradictions.
 • Resolution is used, if there are various statements are given, and we need to prove a conclusion
of those statements.
• Unification is a key concept in proofs by resolutions.
• Resolution is a single inference rule which can efficiently operate on the conjunctive normal
form or clausal form.

Clause: Disjunction of literals (an atomic sentence) is called a clause. It is also known as a unit clause.

Conjunctive Normal Form: A sentence represented as a conjunction of clauses is said to

be conjunctive normal form or CNF.

Example:

We can resolve two clauses which are given below:

[Animal (g(x) V Loves (f(x), x)] and [￢ Loves(a, b) V ￢Kills(a, b)]

Where two complimentary literals are: Loves (f(x), x) and ￢ Loves (a, b)

These literals can be unified with unifier θ= [a/f(x), and b/x] , and it will generate a resolvent clause:

[Animal (g(x) V ￢ Kills(f(x), x)].

Steps for Resolution:

1. Conversion of facts into first-order logic.

2. Convert FOL statements into CNF

3. Negate the statement which needs to prove (proof by contradiction)

4. Draw resolution graph (unification).

To better understand all the above steps, we will take an example in which we will apply resolution.

Example:

a. John likes all kind of food.

b. Apple and vegetable are food

 c. Anything anyone eats and not killed is food.

d. Anil eats peanuts and still alive

e. Harry eats everything that Anil eats.

Prove by resolution that:
f. John likes peanuts.

Step-1: Conversion of Facts into FOL

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

Step-2: Conversion of FOL into CNF

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

o Eliminate all implication (→) and rewrite

a. ∀x ¬ food(x) V likes(John, x)

b. food(Apple) Λ food(vegetables)

c. ∀x ∀y ¬ [eats(x, y) Λ ¬ killed(x)] V food(y)

d. eats (Anil, Peanuts) Λ alive(Anil)

e. ∀x ¬ eats(Anil, x) V eats(Harry, x)
f. ∀x¬ [¬ killed(x) ] V alive(x)

g. ∀x ¬ alive(x) V ¬ killed(x)

h. likes(John, Peanuts).
Move negation (¬)inwards and rewrite

. ∀x ¬ food(x) V likes(John, x)

a. food(Apple) Λ food(vegetables)

b. ∀x ∀y ¬ eats(x, y) V killed(x) V food(y)

c. eats (Anil, Peanuts) Λ alive(Anil)

d. ∀x ¬ eats(Anil, x) V eats(Harry, x)

e. ∀x ¬killed(x) ] V alive(x)

f. ∀x ¬ alive(x) V ¬ killed(x)

g. likes(John, Peanuts).
Rename variables or standardize variables

. ∀x ¬ food(x) V likes(John, x)

a. food(Apple) Λ food(vegetables)

b. ∀y ∀z ¬ eats(y, z) V killed(y) V food(z)

c. eats (Anil, Peanuts) Λ alive(Anil)

d. ∀w¬ eats(Anil, w) V eats(Harry, w)

e. ∀g ¬killed(g) ] V alive(g)

f. ∀k ¬ alive(k) V ¬ killed(k)

g. likes(John, Peanuts).

Eliminate existential instantiation quantifier by elimination.

In this step, we will eliminate existential quantifier ∃, and this process is known as Skolemization. But
in this example problem since there is no existential quantifier so all the statements will remain same in
this step.
Drop Universal quantifiers.
In this step we will drop all universal quantifier since all the statements are not implicitly quantified so
we don't need it.
. ¬ food(x) V likes(John, x)

a. food(Apple)

b. food(vegetables)

c. ¬ eats(y, z) V killed(y) V food(z)

d. eats (Anil, Peanuts)

e. alive(Anil)
f. ¬ eats(Anil, w) V eats(Harry, w)

g. killed(g) V alive(g)
h. ¬ alive(k) V ¬ killed(k)

i. likes(John, Peanuts).

Distribute conjunction ∧ over disjunction ¬.

This step will not make any change in this problem.

Step-3: Negate the statement to be proved

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

Step-4: Draw Resolution graph:

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

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

o 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) .

o In the third step of the resolution graph, ¬ eats(y, Peanuts) and eats (Anil, Peanuts) get resolved
by substitution {Anil/y}, and we are left with Killed(Anil) .
o 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) .
o In the last step of the resolution graph ¬ alive(Anil) and alive(Anil) get resolved.

Ex2:
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?

First, we express the original sentences, some background knowledge, and the negated goal G in first-
order logic:
A. ∀ x [∀ y Animal (y) ⇒ Loves(x, y)] ⇒ [∃ y Loves(y, x)]
B. ∀ x [∃ z Animal (z) ∧ Kills(x, z)] ⇒ [∀ y ￢Loves(y, x)]
C. ∀ x Animal(x) ⇒ Loves(Jack, x)
D. Kills(Jack, Tuna) ∨ Kills(Curiosity, Tuna)
E. Cat(Tuna)
F. ∀ x Cat(x) ⇒ Animal (x)
￢G. ￢Kills(Curiosity, Tuna)
Now we apply the conversion procedure to convert each sentence to CNF:
A1. Animal(F(x)) ∨ Loves(G(x), x)
A2. ￢Loves(x, F(x)) ∨ Loves(G(x), x)
B. ￢Loves(y, x) ∨ ￢Animal (z) ∨ ￢Kills(x, z)
C. ￢Animal(x) ∨ Loves(Jack, x)
D. Kills(Jack, Tuna) ∨ Kills(Curiosity, Tuna)
E. Cat(Tuna)
F. ￢Cat(x) ∨ Animal (x)
￢G. ￢Kills(Curiosity, Tuna)

• time. The identity is between the subevents of each object that are defined by the period 1790.