Artificial intelligence

​

First Order Logic

KVSM, Dept of CSE , SRKREC

Department of Computer Science and Engineering

S R K R Engineering College,

Bhimavaram-534204

KVSM, Dept of CSE , SRKREC

First Order Logic :

In the topic of Propositional logic, we have seen that how to represent statements using propositional logic.

But unfortunately, in propositional logic, we can only represent the facts, which are either true or false.

Propositional Logic is not sufficient to represent the complex sentences or natural language statements.

The propositional logic has very limited expressive power.

First-Order Logic in Artificial intelligence

KVSM, Dept of CSE , SRKREC

Consider the following sentence, which we cannot represent using Propositional logic.

"Some humans are intelligent", or

"Sachin likes cricket."

To represent the above statements, Propositional logic is not sufficient, so we required some more powerful logic, such as first-order logic.

First-Order Logic in Artificial intelligence

KVSM, Dept of CSE , SRKREC

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.

First-Order Logic in Artificial intelligence

KVSM, Dept of CSE , SRKREC

First-Order logic:

First-order logic (like natural language) does not only assume that the world contains facts like propositional logic but also assumes the following things in the world:

Objects: A, B, people, numbers, colors, wars, theories.

Relations: It can be unary relation such as: red, round, is adjacent, 

or n-any relation such as: the sister of, brother of, has color, comes between

Function: Father of, best friend, third inning of, end of, ......

As a natural language, first-order logic also has two main parts:

Syntax

Semantics

First-Order Logic in Artificial intelligence

KVSM, Dept of CSE , SRKREC

Syntax of First-Order logic:

The syntax of FOL determines which collection of symbols is a logical expression in first-order logic.

The basic syntactic elements of first-order logic are symbols.

We write statements in short-hand notation in FOL.

First-Order Logic in Artificial intelligence

KVSM, Dept of CSE , SRKREC

Basic Elements of First-order logic or predicate logic

​

First-Order Logic in Artificial intelligence

KVSM, Dept of CSE , SRKREC

Atomic sentences:

Atomic sentences are the most basic sentences of first-order logic.

These sentences are formed from a predicate symbol followed by a parenthesis with a sequence of terms.

We can represent atomic sentences as Predicate (term1, term2, ...., term n).

Example: Ravi and Ajay are brothers:

brothers(Ravi, Ajay).�                Chinky is a cat

cat (Chinky).

​

​

First-Order Logic in Artificial intelligence

KVSM, Dept of CSE , SRKREC

Complex Sentences:

Complex sentences are made by combining atomic sentences using connectives.

First-order logic statements can be divided into two parts:

Subject: Subject is the main part of the statement.

Predicate: A predicate can be defined as a relation, which binds two atoms together in a statement.

Consider the statement: "x is an integer.", it consists of two parts, the first part x is the subject of the statement and second part "is an integer," is known as a predicate.

​

​

​

​

First-Order Logic in Artificial intelligence

KVSM, Dept of CSE , SRKREC

Quantifiers in First-order logic:

A quantifier is a language element which generates quantification, and quantification specifies the quantity of specimen in the universe of discourse.

These are the symbols that permit to determine or identify the range and scope of the variable in the logical expression.

There are two types of quantifier:

Universal Quantifier, (for all, everyone, everything)

Existential quantifier, (for some, at least one).

​

First-Order Logic in Artificial intelligence

KVSM, Dept of CSE , SRKREC

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 ∀

For example:

All man drink coffee.

In predicate logic it can be represented as :

∀x : man(x) → drink (x, coffee).

​

First-Order Logic in Artificial intelligence

KVSM, Dept of CSE , SRKREC

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 ∃, When it is used with a predicate variable then it is called as an existential quantifier.

For example:

Some boys are intelligent.

In predicate logic it can be represented as :

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

​

First-Order Logic in Artificial intelligence

KVSM, Dept of CSE , SRKREC

Some Examples of FOL using quantifier:

1. All birds fly.�              ∀x bird(x) →fly(x).

​

2. Every man respects his parent.�              ∀x man(x) → respects (x, parent).

​

3. Some boys play cricket.�              ∃x boys(x) → play(x, cricket).

​

First-Order Logic in Artificial intelligence

KVSM, Dept of CSE , SRKREC

Some Examples of FOL using quantifier:

4. All students like both Mathematics and Science.�              ∀ (x): student(x) → like(x, Mathematics) ∧ like(x, Science).

​

5. Not all students like both Mathematics and Science.�              ¬∀ (x): student(x) → like(x, Mathematics) ∧ like(x, Science).

​

6. Only one student failed in Mathematics.�              ∃(x) [ student(x) → failed (x, Mathematics) ∧∀ (y) [¬(x==y) ∧ student(y) → ¬failed (x, Mathematics)].

First-Order Logic in Artificial intelligence

KVSM, Dept of CSE , SRKREC

Some Examples of FOL using quantifier:

7. Some one likes cakes.�              ∃ (x): person (x) → like(x, cakes ).

​

8. No one likes cakes.

      ¬ ∃ (x): person (x) → like(x, cakes ).

or

∃ (x): person (x) → ¬ like(x, cakes ).

​

​

First-Order Logic in Artificial intelligence

KVSM, Dept of CSE , SRKREC

A well-formed formula (wff) is a predicate logic representation of the sentence.

Well Formed formula ( W F F)

The following are some facts and their wff representation:

​

Marcus was a man.

man(Marcus)

​

Marcus was a Pompeian.

Pompeian(Marcus)

​

All Pompeians were Romans.

∀x: Pompeian(x) → Roman(x)

​

Caesar was a ruler.

ruler(Caesar)

KVSM, Dept of CSE , SRKREC

Well Formed formula ( W F F)

All romans were either loyal to Caesar or hated him.

​

∀x: Roman(x) → loyalto(x, Caesar) ∨ hate(x, Caesar)

� Everyone is loyal to someone.

​

∀x: ∃y: loyalto (x, y)

​

People only try to assassinate rulers they are not loyal to.

​

∀x: ∀y: person(x) ∧ ruler(y) ∧ tryassassinate(x, y) → ¬loyalto(x, y)

​

Marcus tried to assassinate Caesar.

​

tryassassinate(Marcus, Caesar)

​

KVSM, Dept of CSE , SRKREC

Well Formed formula ( W F F)

Now suppose if we want to use these statements to answer the question:

Was Marcus loyal to Caesar?

Also, Now let’s try to produce a formal proof, reasoning using reasoning backward from the desired goal: ¬ Ioyalto(Marcus, Caesar)

​

In order to prove the goal, we need to use the rules of inference to transform it into another goal (or possibly a set of goals) that can, in turn, transformed, and so on, until there are no unsatisfied goals remaining.

​

KVSM, Dept of CSE , SRKREC

Well Formed formula ( W F F)

Now We need to add the representation of another fact to our system, namely:

∀ man(x) → person(x)

Now we can satisfy the last goal and produce a proof that Marcus was not loyal to Caesar.

KVSM, Dept of CSE , SRKREC

Representing Instance and ISA Relationships

 Specific attributes instance and isa play an important role particularly in reasoning using property inheritance.

​

The predicates instance is used to express class membership

​

The predicate isa is used to express class inclusion.

KVSM, Dept of CSE , SRKREC

Representing Instance and ISA Relationships

 In the following table shows the first five sentences of the last section represented in logic in three different ways.

​

The first part of the figure contains the representations we have already discussed. In these representations, class membership represented with unary predicates (such as Roman), each of which corresponds to a class.

Asserting that P(x) is true is equivalent to asserting that x is an instance (or element) of P.

The second part of the figure contains representations that use the instance predicate explicitly.

The third part contains representations that use both the instance and isa predicates explicitly.

KVSM, Dept of CSE , SRKREC

Representing Instance and ISA Relationships

KVSM, Dept of CSE , SRKREC

Computable Functions and Predicates

To express simple facts, such as the following greater-than and less-than relationships:

gt(1,O) lt(0,1) gt(2,1) lt(1,2) gt(3,2) lt( 2,3)

It is often also useful to have computable functions as well as computable predicates.

Thus we might want to be able to evaluate the truth of gt(2 + 3,1)

To do so requires that we first compute the value of the plus function given the arguments 2 and 3, and then send the arguments 5 and 1 to gt.

​

KVSM, Dept of CSE , SRKREC

Natural deduction

Marcus was a man.

man(Marcus)

Marcus was a Pompeian.

Pompeian(Marcus)

Marcus was born in 40 A.D.

born(Marcus, 40)

All men are mortal.

∀ x: man(x) → mortal(x)

All Pompeians died when the volcano erupted in 79 A.D. erupted(volcano, 79) ∧ ∀ x : [Pompeian(x) → died(x, 79)]

No mortal lives longer than 150 years.

∀ x: t1: At2: mortal(x) born(x, t1) gt(t2 – t1,150) → died(x, t2)

It is now 2021.

now = 2021

Alive means not dead.

∀ x: t: [alive(x, t) → ¬ dead(x, t)] [¬ dead(x, t) → alive(x, t)]

If someone dies, then he is dead at all later times.

∀ x: t1: At2: died(x, t1) gt(t2, t1) → dead(x, t2)

KVSM, Dept of CSE , SRKREC

Natural deduction

So, Now let’s attempt to answer the question “Is Marcus alive?” by proving: ¬ alive(Marcus, now)

KVSM, Dept of CSE , SRKREC

First-Order Logic in Artificial intelligence

KVSM, Dept of CSE , SRKREC

First-Order Logic in Artificial intelligence

KVSM, Dept of CSE , SRKREC

28

​

Thank you

​

KVS MURTHY

Assistant Professor

Department of CSE

SRKR Engineering College

9848290433

kvssrmurthy75@gmail.com

kvssr.murthy@srkrec.edu.in