FIRST

ORDER
LOGIC
ARTIFICIAL INTELLIGENCE

PRESENTED BY - ANIKET AND AHMAD KAMRAN

 TOPICS

Limitation of propositional logic Inference in FOL

Why First order logic? Types of Inference rules

First order logic

Basic elements of FOL

Quantifiers
Limitation of proportional logic
Propositional logic is a formal system that is quite straightforward and useful for
representing basic facts and relationships between them. It's declarative, meaning its
syntax directly represents facts. This logic allows for expressing partial, disjunctive,
and negated information, which isn't always easily done in typical data structures or
databases.

However, its expressiveness is limited. While it's great for representing simple
relationships between facts, it falls short when dealing with more complex relationships
or scenarios found in natural language.

For instance, expressing something like "pits cause breezes in adjacent squares" using
propositional logic would require writing a sentence for each square involved, which
becomes cumbersome and inefficient. Additionally, unlike natural language, the
meaning in propositional logic is fixed and context-independent, whereas in natural
language, meaning can heavily depend on the context in which it's used.
 WHY FIRST ORDER
LOGIC?
Propositional logic deals with facts in a more simplistic manner, assuming a world containing
straightforward facts. In contrast, first-order logic, much like natural language, assumes the world
contains:

Objects: These are entities or things, like people, houses, numbers, theories, specific individuals (such
as Ronald McDonald), colors, baseball games, wars, or periods of time (centuries).

Relations: These define properties or relationships between objects. They can be qualities (like "red" or
"round"), or they can describe connections or associations between objects (such as "brother of,"
"bigger than," "inside," "part of," "has color," "occurred after," "owns," "comes between," and so on).

Functions: These denote specific relationships where one object is related to another in a particular way.
They can represent actions or transformations, like "father of," "best friend," "third inning of," "one
more than," "end of," and so forth.

By incorporating these elements, first-order logic becomes more precise and powerful than
propositional logic. It allows for the expression of a wide range of relationships and complexities,
mirroring the way natural language deals with the rich variety of entities, connections, and actions
present in the world.
FIRST ORDER LOGIC
•First-order logic is another way of knowledge representation in
artificial intelligence. It is an extension to propositional logic.

•FOL is sufficiently expressive to represent the natural language

statements in a concise way.

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

•As a natural language, first-order logic also has two main parts:
• Syntax
• Semantics
 Example
"All men are mortal."
"Socrates is a man."
"Therefore, Socrates is mortal."
In first-order logic, we can represent these statements using predicates, quantifiers, and constants. Here's how it can be
written:
Constants:
S represents Socrates.
x represents any individual.
Predicates:
M(x) represents "x is a man."
R(x) represents "x is mortal."
Quantifiers:
∀ means "for all" (universal quantifier).
∃ means "there exists" (existential quantifier).
Using these elements, we can express the given statements:
"All men are mortal": ∀x(M(x)→R(x)) This means "For all x, if x is a man, then x is mortal."
"Socrates is a man": M(S) This represents "Socrates is a man."
Conclusion - "Therefore, Socrates is mortal": R(S) This concludes that "Socrates is mortal."
Basic elements ATOMIC SENTENCE
•Atomic sentences are the most basic sentences of first-order
logic. These sentences are formed from a predicate symbol
Constant 1, 2, A, John, Mumbai, cat,.... followed by a parenthesis with a sequence of terms.
Variables x, y, z, a, b,....
•We can represent atomic sentences as Predicate (term1,
Predicates Brother, Father, >,.... term2, ......, term n)

Function sqrt, LeftLegOf, .... •Example-Ravi and Ajay are brothers: => Brothers(Ravi,
Ajay).
Connectives ∧, ∨, ¬, ⇒, ⇔ Chinky is a cat: => cat (Chinky).
Equality ==
COMPLEX SENTENCE
Quantifier ∀, ∃
•Complex sentences are made by combining atomic
sentences using connectives.

•Example –
∀x(Human(x)∧∃y(Parent(y,x)∧Doctor(y))→∃z(WorksAt(z,
x)∧Hospital(z)))
QUANTIFIERS
•A quantifier is a language element which
generates quantification, and quantification
1.Universal Quantifier, (for all, everyone,
specifies the quantity of specimen in the universe everything)
of discourse.
2.Existential quantifier, (for some, at least
•These are the symbols that permit to determine one).
or identify the range and scope of the variable in
the logical expression.
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:
•For all x
•For each x
•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:
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.

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

read as:

•There exists a 'x.'

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

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

It will be read as: There are some x where x is a boy who is intelligent.
 Inference in FOL
Substitution : Substitution is a basic procedure that is applied Four inference rules in FOL
to terms and formulations. It can be found in all first-order are :
logic inference systems. When there are quantifiers in FOL,
the substitution becomes more complicated. When we •Universal Generalization
write F[a/x], we are referring to the substitution of a
constant "a" for the variable "x." •Universal Instantiation

Equality : In First-Order Logic, atomic sentences are •Existential Instantiation

formed not only via the use of predicate and words,
but also through the application of equality. We can do •Existential introduction
.
this by using equality symbols, which indicate that
the two terms relate to the same thing.
Example: ￢ (x=y) which is equivalent to x ≠y.
 Universal Generalization:

1.Universal generalization is a valid inference rule that states that if premise P(c) is true for any arbitrary
element c in the universe of discourse, we can arrive at the conclusion as for all x P(x).
2.It can be represented as:

3.If we want to prove that every element has a similar property, we can apply this rule.
4.x must not be used as a free variable in this rule.
Example: Let's represent, P(c): "A byte contains 8 bits", so "All bytes contain 8 bits."for ∀ x P(x) , it
will also be true.
 Universal Instantiation:

1.A valid inference rule is universal instantiation, often known as universal elimination or UI. It can be used to add additional
sentences many times.
2.The new knowledge base is logically equal to the existing knowledge base.
3.We can infer any phrase by replacing a ground word for the variable, according to UI
4.The UI rule say 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.
5.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)
 Existential Instantiation:
1.Existential instantiation is also known as Existential Elimination, and it is a legitimate first-order logic inference rule.
2.It can only be used to replace the existential sentence once.
3.Although the new KB is not conceptually identical to the old KB, it will be satisfiable if the old KB was.
4.This rule states that for a new constant symbol c, one can deduce P(c) from the formula given in the form of x P(x).
5.The only constraint with this rule is that c must be a new word for which P(c) is true.
6.It's written like this:

Example: 1

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.

7.The above used K is a constant symbol, which is known as Skolem constant.

2.The Existential instantiation is a special case of Skolemization process
 Existential introduction

1.An existential generalization is a valid inference rule in first-order logic that is also known as an existential introduction.
2.This rule argues that if some element c in the universe of discourse has the property P, we can infer that something in the universe has
the attribute P.
3.It's written like this:

4.Example: Let's say that,

"Priyanka got good marks in English."
"Therefore, someone got good marks in English."
Thank you