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], it means
to substitute a constant
"a" in place of variable
"x".
Note: First-order logic is
capable of expressing
facts about some or all
objects in the universe.
Equality:
First-Order logic does
not only use predicates
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.
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], it means
to substitute a constant "a" in place of variable "x".
Note: First-order logic is capable of expressing facts about some or all objects in the universe.
Equality:
First-Order logic does not only use predicates 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.
●The above used K is a constant symbol, which is called Skolem constant.
●Existential instantiation is a special case of the Skolemization process.
4. Existential introduction
●An existential introduction is also known as an existential generalization, which is a valid
inference rule
in first-order logic.
●This rule states that if there is some element c in the universe of discourse which has a
property P, then
we can infer that there exists something in the universe which has the property P.
●It can be represented as:
●Example: Let's say that,
"Priyanka got good marks in English."
"Therefore, someone got good marks in English."
Generalized Modus Ponens Rule:
For the inference process in FOL, we have a single inference rule which is called Generalized
Modus Ponens. It
is a 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).
What is 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 Ψ1and Ψ2be 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, both
expressions will be
identical