Artificial Intelligence - Inference Rules in First Order Logic

Quiz

Inference in First-Order Logic

Inference in First-Order Logic (FOL) involves deriving new facts or statements from existing ones. This process is crucial for reasoning, knowledge representation, and automating logical deductions. Before we delve into some inference rules, let's first cover some fundamental concepts of FOL.

Substitution

Substitution is a fundamental operation in first-order logic that involves replacing a variable with a specific constant or phrase within an expression. This process is essential for effectively applying inference rules.

When we write F[b/y], we are substituting the variable y with the constant b in the formula F.
Using quantifiers for substitution needs to be done carefully to maintain logical consistency.
First-Order Logic enables reasoning about specific objects and entire categories within a given domain.

Equality

In first-order logic (FOL), equality is an important aspect that allows us to express that two terms refer to the same object. The equality operator (=) is used to confirm that two expressions point to the same entity.

The expression ¬(a = b) indicates that a and b are not identical objects.

For example, the statement Manager(Alex) = Sophia means that Sophia is the manager of Alex. Combining negation with equality helps to show that two concepts are distinct.

FOL Inference Rules for Quantifier

The inference rules for FOL are an extension of Propositional Logic by adding quantifiers and predicates. The rules below are the key ones:

Universal Generalization

Universal generalization is a valid inference rule that asserts if premise P(c) holds true for any arbitrary element c within the universe of discourse, we can conclude that x P(x) is also true.

If premise P(c) holds true for any arbitrary element c in the discourse universe we can arrive at the conclusion that x P(x).

It can be represented as − P(c), x P(x)

Universal Generalization (UG )is valid only if c represents a general case applicable to all elements in the domain.

Example

Let us say the given statement is like this Loves(John, IceCream), Loves(Mary, IceCream), Loves(Sam, IceCream) the FOL representation using inference rule is as below −

x Loves(x, IceCream) (if John, Mary, and Sam represent all entities).

Universal Instantiation

Universal Instantiation (UI) is an inference rule for First-Order Logic that derives a particular instance from a universally quantified statement. If it is true for all items of a domain, then it has to be the case for any specific element in the domain as well.

According to the UI rule, we can infer any sentence P(c) by replacing every object in the discourse universe with a ground term c (a constant within domain x) from x P(x).

It can be represented as − x P(x), P(c)

According to the UI rule, any sentence P(c) is derivable, replacing a ground word c-for any object belonging to the universe of discourse-as a ground substitution for any x P(x).
UI enables thinking of individual circumstances from universal facts.
This is widely applied in theorem proving and automated reasoning.
UI is the negation of Universal Generalization (UG).

Example

Let us say the given statement be "Everyone who teaches at a university has an advanced degree." x(Teaches(x,University)→ HasAdvancedDegree(x)) [ x P(x)].

By applying Universal Instantiation (UI) inference rule we can infer that for a specific professor, say Dr. Amrit − Teaches(Dr.Amrit,University)→ HasAdvancedDegree(Dr.Amrit).

Existential Instantiation

Existential Instantiation (EI) is a First-Order Logic inference rule that allows for the replacement of an existentially quantified variable with a new, arbitrary constant in order to represent an unknown but existing entity.

This rule indicates that from the formula x P(x), one can deduce P(c) by introducing a new constant symbol c.

It can be represented as − x P(x), P(c)

EI is also known as Existential Elimination.
It can only be used once to replace an existential sentence with a particular instance.
The new knowledge base (KB) is not logically equal to the old KB; yet, if the old KB was satisfactory, the new one is still satisfactory.
According to EI, we can infer P(c) from xP(x) by introducing a new constant c.
The inserted constant c must be new and not previously used in the KB.

Example

Let us say the given statement is "Someone has published a research paper." x (HasPublishedResearch(x)) [ x P(x) ].

By applying the Existential Instantiation (EI) inference rule, we can infer that for a specific researcher, say Dr. Arjun − HasPublishedResearch(Dr.Arjun).

Existential Introduction

Existential Introduction (EI), often referred to as Existential Generalization (EG), is a valid inference rule in First-Order Logic. It allows us to introduce an existential quantifier when we can confirm that a proposition holds true for at least one instance.

It can be represented as − P(c), x P(x)

It lets us move from a specific instance to a more general existential statement.
If P(c) is true for a certain c, we can infer that there exists some x for which P(x) is true.
The new existential statement is logically valid but different from the statement in question.

Example

Let us say the given statement is "Mr. Raj works at Tutorials Point." WorksAt(Mr.Raj, TutorialsPoint) [ P(c) ].

By applying the Existential Introduction (EI) inference rule, we can generalize that "There exists someone who works at Tutorials Point." − x (WorksAt(x, TutorialsPoint)).

Generalized Modus Ponens (GMP) Rule

Generalized Modus Ponens is an extension of the traditional Modus Ponens rule of First-Order Logic. It allows multiple premises, variables, and substitutions. This facilitates logical reasoning by substituting variables in the premises and making replacements to reach conclusions.

Generalized Modus Ponens can be described as "P implies Q and P is asserted to be true, therefore Q must be true.

It can be represented as − P1→Q1,P2→Q2,,Pn→Qn,P1P2Pn, Q1Q2Qn

Combines three steps of natural deduction (Universal Elimination, And Introduction, Modus Ponens) into one.
Provides direction and simplification to the proof process for standard inferences.

Example

Let us say the given rule is "If a person works at Tutorials Point and has expertise in AI, then they are an AI Instructor." x (WorksAt(x, TutorialsPoint) HasExpertise(x, AI) → AIInstructor(x))

Given facts: WorksAt(Ravi, TutorialsPoint)
HasExpertise(Ravi, AI): By applying the Generalized Modus Ponens (GMP) inference rule, we can conclude: AIInstructor(Ravi).

Print Page