*88*

# Inference 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**“.

#### 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 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 Generalization****Universal Instantiation****Existential Instantiation****Existential introduction**

**1. Universal Generalization:**

- Universal generalization is a valid inference rule which states that if premise P(c) is true for any arbitrary element c in the universe of discourse, then we can have a conclusion as ∀ x P(x).
- It can be represented as: .
- This rule can be used if we want to show that every element has a similar property.
- In this rule, x must not appear as a free variable.

**Example:** Let’s represent, P(c): “**A byte contains 8 bits**“, so for **∀ x P(x)** “**All bytes contain 8 bits**.”, it will also be true.

**2. Universal Instantiation: **

- 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.
- The new KB is logically equivalent to the previous KB.
- As per UI,
**we can infer any sentence obtained by substituting a ground term for the variable**. - 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**. - 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:

**King(John) ∧ Greedy (John) → Evil (John),****King(Richard) ∧ Greedy (Richard) → Evil (Richard),****King(Father(John)) ∧ Greedy (Father(John)) → Evil (Father(John)),**

**3. Existential Instantiation: **

- Existential instantiation is also called as Existential Elimination, which is a valid inference rule in first-order logic.
- It can be applied only once to replace the existential sentence.
- The new KB is not logically equivalent to old KB, but it will be satisfiable if old KB was satisfiable.
- 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.
- The restriction with this rule is that c used in the rule must be a new term for which P(c ) is true.
- It can be represented as:

**Example:**

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.

- The above used K is a constant symbol, which is called
**Skolem constant**. - The Existential instantiation is a special case of
**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 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. **