First-Order Logic in Artificial Intelligence

Pre-requisites

1. Propositional Logic

Introduction to First-Order Logic in AI

First Order Logic in Artificial Intelligence is a technique used for knowledge representation. It is an extension of propositional logic and unlike propositional logic, it is sufficiently expressive in representing any natural language construct. First Order Logic in AI is also known as Predicate Logic or First Order Predicate Logic. It is a robust technique to represent objects as well as their relationships. Unlike propositional logic, First Order Logic in Artificial Intelligence doesn't only include facts but also different other entities as listed below.

1. Objects:
   Objects can denote any real-world entity or any variable. E.g., A, B, colours, theories, circles etc.
2. Relations:
   Relations represent the links between different objects. Relations can be unary(relations defined for a single term) and n-ary(relations defined for n terms). E.g., blue, round (unary); friends, siblings (binary); etc.
3. Functions:
   Functions map their input object to the output object using their underlying relation. Eg: father_of(), mother_of() etc.

In the subsequent sections, we present the parts of First Order Logic in AI, i.e., the syntax and the semantics.

Parts of First Order Logic

First-order logic in Artificial Intelligence comprises two main components, which are as follows.

1. Syntax:
   Syntax represents the rules to write expressions in First Order Logic in Artificial Intelligence.
2. Semantics:
   Semantics refers to the techniques that we use to evaluate an expression of First Order Logic in AI. These techniques use various known relations and facts of the respective environment to deduce the boolean value of the given First Order Logic expression.

We elaborate on the syntax of First Order Logic in AI in the following sections.

Syntax of First Order Logic

Syntax of First Order Logic in Artificial Intelligence represents the rules of representing any natural language construct in terms of First Order Logic in AI. This involves the rules to describe any object and the relationships between different objects. These rules comprise rules for writing constants, variables, predicates, quantifiers, etc. In the following sections, we present various examples of the syntax of first-order logic in AI. These rules are further illustrated in the following sections.

Basic Elements of First-Order Logic

The following table furnishes the basic elements of First Order Logic in Artificial Intelligence.

Atomic Sentences

Atomic sentences are the most basic expressions of First Order Logic in AI. These sentences comprise a predicate followed by a set of terms inside a parenthesis. Formally stating, the structure of an atomic sentence looks like the following.

One example of an atomic sentence in First Order Logic in Artificial Intelligence can be $\text { Sisters } ( \text { Geeta } , \text { Seeta } )$. Another example involving a unary predicate can be $\text { Polygon } ( \text { Rectangle } )$.

Complex Sentences

Complex sentences can be constructed by combining atomic sentences using connectives like AND (∧), OR (∨), NOT (¬), IMPLIES (⇒), IF AND ONLY IF (⇔) etc. Formally stating, if $c_1, c_2, ...$ represent connectives, a complex sentence in First Order Logic in AI can be defined as follows.

An example of a complex sentence in First Order Logic in Artificial Intelligence can be $Sisters$ ( $Geeta, Seeta$) $∧ Sisters$ ( $Geeta , Leela$ ). Another example using just one predicate can be ¬$Sisters (Geeta , Seeta )$

Any expression of First Order Logic in AI can be broken into two main components, namely subject and predicate. The subject is the main entity about which the expression describes. Predicate depicts the relation between different subjects. For example, in the expression, $Polygon (Rectangle)$, which is a translation of "Rectangle is a polygon." in First Order Logic in Artificial Intelligence, "Rectangle" is the subject, and "Polygon" represents a predicate.

Quantifiers in First-Order Logic

Quantifiers in First Order Logic in AI, as the name suggests, are used to quantify any entity in a given environment. Quantification refers to the identification of the total number of an entity that is present in the environment and satisfies a given expression in First Order Logic in Artificial Intelligence. Quantifiers enable us to determine the range and scope of a variable in a logical expression. Two types of quantifiers are stated as follows.

1. Universal Quantifier
2. Existential Quantifier

Universal Quantifier

Universal Quantifier in First Order Logic in AI is a symbol in a logical expression that signifies that the given expression is true in its range for all instances of the concerned entity. It is represented by the symbol $\forall$ (an inverted A). If $x$ is a variable, then $\forall x$ is read as "For all x" or "For every x" or "For each x".

For example, let us take the sentence, "All cats like fish". Let us take a variable $x$ which can take the value of "cat". Let us take a predicate $\text { cat } ( x )$ which is true if $x$ is a cat. Similarly, let us take another predicate $\text { likes } ( x, y )$ which is true if $x$ likes $y$. Therefore, using the universal quantifier $\forall$, we can write

This expression is read as "For all $x$, if $x$ is a cat, then $x$ likes to fish".

Existential Quantifier

An existential Quantifier in First Order Logic in Artificial Intelligence is a symbol in a logical expression that signifies that the given expression is true in its range for at least one of the instances of the concerned entity. It is represented by the symbol $\exists$ (an inverted E). If $x$ is a variable, then $\exists x$ is read as "There exists x" or "For some x" or "For at least one x".

For example, let us take the sentence, "Some students like ice cream". Let us take a variable $x$ which can take the value of "student". Let us take a predicate $\text { student } ( x )$, which is true if $x$ is a student. Similarly, let us take another predicate $\text { likes } ( x, y )$, which is true if $x$ likes $y$. Therefore, using the existential quantifier $\exists$, we can write

This expression reads, "There exists some $x$ such that $x$ is a student and also likes ice cream".

Properties of Quantifiers

Quantifiers in First Order Logic in AI follow some properties as stated below.

1. In the universal quantifier, $\forall x \forall y$ is equivalent to $\forall y \forall x$.
2. In the existential quantifier, $\exists x \exists y$ is equivalent to $\exists y \exists x$.
3. $\exists x \forall y$ is not equivalent to $\forall y \exists x$.
4. Quantifier Duality:
   Each quantifier can be expressed using the other. E.g., $\forall$ x $\quad$ Predicate( x ) $\quad$ is same as $\quad$ ¬ $\exists$ x $\quad$ ¬ Predicate(x).

Points to Remember About Quantifiers in First-Order Logic

While using quantifiers in writing expressions for First Order Logic in Artificial Intelligence, we need to keep the following points in mind.

1. The main connective for the universal quantifier $\forall$ is the implication ($\implies$).
2. The main connective for existential quantifier $\exists$ is and (∧).

Free and Bound Variables

There are two types of variables based upon their interaction with the quantifiers in a First Order Logic in AI, namely free and bound variables.

1. Free Variables:
   Free variables are those variables that do not come under the scope of the quantifier. For instance, in an expression $\forall x \exists y P ( x, y, z )$, $z$ is a free variable because it doesn't come under the scope of any quantifier.
2. Bound Variables:
   Bound variables are those variables that occur inside the scope of the quantifier. For instance, in an expression $\forall x \exists y P ( x, y, z )$, $x \text { and } y$ are bound variables because they occur inside the scope of the quantifiers.