First-Order Logic in Artificial Intelligence
A
r
t
i
f
i
c
i
a
l
I
n
t
e
l
l
i
g
e
n
c
e
Lecture 8
First Order Logic
College of Engineering & Technology
Computer Techniques Engineering Department
Artificial Intelligence – Stage 3
F
i
r
s
t
O
r
d
e
r
L
o
g
i
c
•
Knowledge-based agent could represent the world in which it operates
and
deduce
what action to take.
•
Propositional Logic are used as our
representation language
.
•
Propositional logic is sufficient to illustrate the
basic concepts
of logic
and Knowledge-base agents.
Unfortunately
Propositional logic is too puny language to represent knowledge of
complex environments in concise way
F
i
r
s
t
O
r
d
e
r
L
o
g
i
c
•
Propositional logic
lacks the expressive power
to concisely describe an
environment with many objects.
First-order logic
Is sufficiently expressive to represent a good deal of our commonsense
knowledge.
S
y
n
t
a
x
a
n
d
S
e
m
a
n
t
i
c
s
o
f
F
i
r
s
t
O
r
d
e
r
L
o
g
i
c
•
The model of a logical language are the formal structures that
constitute
the possible worlds under consideration.
•
Each model
links the vocabulary
of the logical sentences to elements
of the possible world, so the truth of any sentence can be determined.
•
Thus,
Model for propositional logic link proposition symbols to predefined truth
values
S
y
n
t
a
x
a
n
d
S
e
m
a
n
t
i
c
s
o
f
F
i
r
s
t
O
r
d
e
r
L
o
g
i
c
•
Model for first-order logic are much more interesting.
•
First, they have
objects
The domain of a model is the set of objects or domain elements it
contains
•
The domain is required to be non-empty, every possible world must
contain at least
one object
.
S
y
n
t
a
x
a
n
d
S
e
m
a
n
t
i
c
s
o
f
F
i
r
s
t
O
r
d
e
r
L
o
g
i
c
•
Figure below shows a model with five objects.
S
y
n
t
a
x
a
n
d
S
e
m
a
n
t
i
c
s
o
f
F
i
r
s
t
O
r
d
e
r
L
o
g
i
c
•
Figure below shows a model with five objects.
•
1. Richard
•
2.King John
•
3.The left leg of Richard
•
4.The left leg of John
•
5.Crown
S
y
n
t
a
x
a
n
d
S
e
m
a
n
t
i
c
s
o
f
F
i
r
s
t
O
r
d
e
r
L
o
g
i
c
•
The objects in the model may be
related
in various ways.
Richard and John are brothers
S
y
n
t
a
x
a
n
d
S
e
m
a
n
t
i
c
s
o
f
F
i
r
s
t
O
r
d
e
r
L
o
g
i
c
•
The crown is on King Johns head, so “
on head
” relation contain just
one tuple
S
y
n
t
a
x
a
n
d
S
e
m
a
n
t
i
c
s
o
f
F
i
r
s
t
O
r
d
e
r
L
o
g
i
c
•
The “
brother
” and “
on head
” relations are
binary relation,
that is they
relates
pairs of objects
S
y
n
t
a
x
a
n
d
S
e
m
a
n
t
i
c
s
o
f
F
i
r
s
t
O
r
d
e
r
L
o
g
i
c
•
The model also contains
unary relation
. Or
Properties.
•
the “
person
”
property
is true of
both
Richard and John.
•
The
king property
is true on of
John
.
•
And the
crown property
is true only of the crown
S
y
n
t
a
x
a
n
d
S
e
m
a
n
t
i
c
s
o
f
F
i
r
s
t
O
r
d
e
r
L
o
g
i
c
•
Certain kinds of relationships are best considers as
functions.
•
That a given object must be related to exactly one object in this way
for example
•
each person has one left leg, so the model has a
unary “left leg”
function that includes the following mappings
S
y
m
b
o
l
s
a
n
d
I
n
t
e
r
p
r
e
t
a
t
i
o
n
s
•
We turn now to the syntax of first-order logic.
•
The basic syntactic elements of first-order logic are:
•
Symbols that stand for objects, relations and functions.
•
The symbols therefore come in three kinds:
•
Constant
symbols which stand for object.
•
Predicate
symbols which stand for relations
•
Function
symbols which stand for functions.
S
y
m
b
o
l
s
a
n
d
I
n
t
e
r
p
r
e
t
a
t
i
o
n
s
•
These symbols will begin with uppercase letter, for
example:
•
Constant
Richard , John.
•
Predicate
Brother, OnHead, Person, King, Crown.
•
Function
lefLeg.
•
Each
predicate
and
function
comes with
arity
that fixes the
number of arguments.
S
y
m
b
o
l
s
a
n
d
I
n
t
e
r
p
r
e
t
a
t
i
o
n
s
•
As in propositional logic, every model must provide the
information required to determine if any given sentence is
true or false
.
•
Thus, in addition to its objects, relations and functions,
each model includes an
interpretation
.
•
The complete description of the formal grammar for the
first order logic are explained in
figure below
S
y
m
b
o
l
s
a
n
d
I
n
t
e
r
p
r
e
t
a
t
i
o
n
s
T
e
r
m
•
Term
is a logical expression that refers to an object.
Constant symbols are therefore terms
•
It is not always convenient to have distinct symbol to name every object
.
•
This is wat function symbols are for, instead of using a constant symbol, we use
function. For example
leftLeg(john).
•
Term is formed by a
function symbol
followed by a
parenthesized list of terms as
arguments
to the function symbol.
f
(
t
1
,
…
…
,
t
n
)
•
T
h
e
f
u
n
c
t
i
o
n
s
y
m
b
o
l
f
r
e
f
e
r
s
t
o
s
o
m
e
f
u
n
c
t
i
o
n
i
n
t
h
e
m
o
d
e
l
c
a
l
l
i
t
f
.
•
T
h
e
a
r
g
u
m
e
n
t
t
e
r
m
s
r
e
f
e
r
t
o
o
b
j
e
c
t
i
n
t
h
e
d
o
m
a
i
n
(
c
a
l
l
t
h
e
m
d
1
,
…
.
.
,
d
n
)
A
t
o
m
i
c
S
e
n
t
e
n
c
e
s
•
Now that we have both:
•
Terms for referring to objects
.
•
Predicate for referring to relations.
•
We can put them together to make
atomic sentences
that state facts.
•
Atomic sentence is formed from a
predicate
symbol optionally followed by an
parenthesized list of terms
, such as.
•
Atomic sentence can have
complex terms as arguments
, for example:
•
State that Richard father is married of king johns mother.
C
o
m
p
l
e
x
S
e
n
t
e
n
c
e
s
•
We can use
logical connective to construct more complex sentences.
Q
u
a
n
t
i
f
i
e
r
s
Q
u
a
n
t
i
f
i
e
r
s
Q
u
a
n
t
i
f
i
e
r
s
N
e
s
t
e
d
Q
u
a
n
t
i
f
i
e
r
s
•
We will often want to express
more complex sentences using multiple quantifiers
.
•
The simplest case is where the
quantifiers are of the same type
.
•
For example
“
Brother are Siblings
”
•
Consecutive quantifiers of the same type can be written as
one quantifier with several
variables
.
•
For example, to say that
siblinghood is a symmetric relationship
, we can write.
N
e
s
t
e
d
Q
u
a
n
t
i
f
i
e
r
s
•
In other cases, we will have mixtures. “
Everybody loves somebody
”.
•
On the other hand, to say “
There is someone who loved by everyone
”.
•
The two quantifiers are actually
connected
with each other throw
negations
.
•
For example, asserting that:
“
e
v
e
r
y
o
n
e
d
i
s
l
i
k
e
s
p
a
r
s
n
i
p
s
”
•
I
s
t
h
e
s
a
m
e
a
s
s
e
r
t
i
n
g
t
h
e
r
e
:
“
t
h
e
r
e
d
o
e
s
n
o
t
e
x
i
s
t
s
o
m
e
o
n
e
w
h
o
l
i
k
e
s
t
h
e
m
”
E
q
u
a
l
i
t
y
•
F
i
r
s
t
o
r
d
e
r
l
o
g
i
c
i
n
c
l
u
d
e
s
o
n
e
m
o
r
e
w
a
y
t
o
m
a
k
e
a
t
o
m
i
c
s
e
n
t
e
n
c
e
s
.
•
W
e
c
a
n
u
s
e
t
h
e
e
q
u
a
l
i
t
y
s
y
m
b
o
l
t
o
s
i
g
n
i
f
y
t
h
o
s
e
t
w
o
t
e
r
m
s
r
e
f
e
r
t
o
t
h
e
s
a
m
e
o
b
j
e
c
t
.
F
o
r
e
x
a
m
p
l
e
:
•
S
a
y
s
t
h
a
t
t
h
e
o
b
j
e
c
t
r
e
f
e
r
r
e
d
b
y
F
a
t
h
e
r
(
J
o
h
n
)
a
n
d
t
h
e
o
b
j
e
c
t
r
e
f
e
r
r
e
d
t
o
b
y
H
e
n
r
y
a
r
e
t
h
e
s
a
m
e
.
•
T
h
e
e
q
u
a
l
i
t
y
s
y
m
b
o
l
c
a
n
b
e
u
s
e
d
t
o
s
t
a
t
e
f
a
c
t
s
a
b
o
u
t
a
g
i
v
e
n
f
u
n
c
t
i
o
n
.
•
I
t
c
a
n
b
e
u
s
e
d
w
i
t
h
n
e
g
a
t
i
o
n
t
o
i
n
s
i
s
t
t
w
o
t
e
r
m
s
a
r
e
n
o
t
t
h
e
s
a
m
e
o
b
j
e
c
t
.
•
T
o
s
a
y
t
h
a
t
R
i
c
h
a
r
d
h
a
s
a
t
l
e
a
s
t
t
w
o
b
r
o
t
h
e
r
s
.
Delve into the realm of first-order logic in artificial intelligence as a knowledge-based agent represents and deduces actions in its operating world. Explore the limitations of propositional logic and the expressive power of first-order logic, along with syntax, semantics, and models in logical languages, shedding light on representing complex environments and common sense knowledge.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
College of Engineering & Technology Computer Techniques Engineering Department Artificial Intelligence Stage 3 Artificial Intelligence Artificial Intelligence Lecture 8 First Order Logic
First Order Logic First Order Logic Knowledge-based agent could represent the world in which it operates and deduce what action to take. Propositional Logic are used as our representation language. Propositional logic is sufficient to illustrate the basic concepts of logic and Knowledge-base agents. Unfortunately Propositional logic is too puny language to represent knowledge of complex environments in concise way
First Order Logic First Order Logic Propositional logic lacks the expressive power to concisely describe an environment with many objects. First-order logic Is sufficiently expressive to represent a good deal of our commonsense knowledge.
Syntax and Semantics of First Order Logic Syntax and Semantics of First Order Logic The model of a logical language are the formal structures that constitute the possible worlds under consideration. Each model links the vocabulary of the logical sentences to elements of the possible world, so the truth of any sentence can be determined. Thus, Model for propositional logic link proposition symbols to predefined truth values
Syntax and Semantics of First Order Logic Syntax and Semantics of First Order Logic Model for first-order logic are much more interesting. First, they have objects The domain of a model is the set of objects or domain elements it contains The domain is required to be non-empty, every possible world must contain at least one object.
Syntax and Semantics of First Order Logic Syntax and Semantics of First Order Logic Figure below shows a model with five objects.
Syntax and Semantics of First Order Logic Syntax and Semantics of First Order Logic Figure below shows a model with five objects. 1. Richard 2.King John 3.The left leg of Richard 4.The left leg of John 5.Crown
Syntax and Semantics of First Order Logic Syntax and Semantics of First Order Logic The objects in the model may be related in various ways. Richard and John are brothers
Syntax and Semantics of First Order Logic Syntax and Semantics of First Order Logic The crown is on King Johns head, so on head relation contain just one tuple
Syntax and Semantics of First Order Logic Syntax and Semantics of First Order Logic The brother and on head relations are binary relation, that is they relates pairs of objects
Syntax and Semantics of First Order Logic Syntax and Semantics of First Order Logic The model also contains unary relation. Or Properties. the person property is true of both Richard and John. The king property is true on of John. And the crown property is true only of the crown
Syntax and Semantics of First Order Logic Syntax and Semantics of First Order Logic Certain kinds of relationships are best considers as functions. That a given object must be related to exactly one object in this way for example each person has one left leg, so the model has a unary leftleg function that includes the following mappings
Symbols and Interpretations Symbols and Interpretations We turn now to the syntax of first-order logic. The basic syntactic elements of first-order logic are: Symbols that stand for objects, relations and functions. The symbols therefore come in three kinds: Constant symbols which stand for object. Predicate symbols which stand for relations Function symbols which stand for functions.
Symbols and Interpretations Symbols and Interpretations These symbols will begin with uppercase letter, for example: Constant Richard , John. Predicate Brother, OnHead, Person, King, Crown. Function lefLeg. Each predicate and function comes with arity that fixes the number of arguments.
Symbols and Interpretations Symbols and Interpretations As in propositional logic, every model must provide the information required to determine if any given sentence is true or false. Thus, in addition to its objects, relations and functions, each model includes an interpretation. The complete description of the formal grammar for the first order logic are explained in figure below
Symbols and Interpretations Symbols and Interpretations
Term Term Term is a logical expression that refers to an object. Constant symbols are therefore terms It is not always convenient to have distinct symbol to name every object. This is wat function symbols are for, instead of using a constant symbol, we use function. For example leftLeg(john). Term is formed by a function symbol followed by a parenthesized list of terms as arguments to the function symbol. f(t1, , tn) The function symbol f refers to some function in the model call it f. The argument terms refer to object in the domain (call them d1, ..,dn)
Atomic Sentences Atomic Sentences Now that we have both: Terms for referring to objects. Predicate for referring to relations. We can put them together to make atomic sentences that state facts. Atomic sentence is formed from a predicate symbol optionally followed by an parenthesized list of terms, such as. Atomic sentence can have complex terms as arguments, for example: State that Richard father is married of king johns mother.
Complex Sentences Complex Sentences We can use logical connective to construct more complex sentences.
Quantifiers Quantifiers In first order logic it is natural to express properties of entire collection of objects, in stead of enumerating the objects by name. Quantifiers let us do this First-order logic contains two standard quantifiers called universal and existential. Universal quantification ( ) All Kings are Person is usually pronounced For all . The sentence says, For all x, if x is a king, then x is a person .
Quantifiers Quantifiers The symbol x is called variable. Variables are lowercase letters. A variable is a term all by itself, and as such can also serve as the argument of a function. the sentence x P, where P is any logical expression, says that P is true for every object x. x P is true in a give model if P is true in all possible extended interpretations constructed from the interpretation given in the model
Quantifiers Quantifiers Existential quantification Make statement about some object in the universe with naming it. For example, to say King John has a crown on his head ? is pronounced There exists an x such that .. or For some x . . The sentence ? ? is true for at least one object x. Precisely, ? ? is true in a given model if P is true in at least one extended interpretation that assigns x to a domain element.
Nested Quantifiers Nested Quantifiers We will often want to express more complex sentences using multiple quantifiers. The simplest case is where the quantifiers are of the same type. For example Brother are Siblings Consecutive quantifiers of the same type can be written as one quantifier with several variables. For example, to say that siblinghood is a symmetric relationship, we can write.
Nested Quantifiers Nested Quantifiers In other cases, we will have mixtures. Everybody loves somebody . On the other hand, to say There is someone who loved by everyone . The order of quantification is therefore very important. It becomes clearer if we insert parentheses. ? ( ? ????? ?,? ) -- > everyone loves someone. ? ( ? ????? ?,? ) someone is being loved by everybody.
Connections between and The two quantifiers are actually connected with each other throw negations. For example, asserting that: everyone dislikes parsnips Is the same asserting there: there does not exist someone who likes them
Connections between and Because is really a conjunction over the universe of objects and is a disjunction. De Morgan s rules can be applied. De Morgan rules for quantified and unquantified sentences are as follows.
Equality First order logic includes one more way to make atomic sentences. We can use the equality symbol to signify those two terms refer to the same object. For example: Says that the object referred by Father(John) and the object referred to by Henry are the same. The equality symbol can be used to state facts about a given function. It can be used with negation to insist two terms are not the same object. To say that Richard has at least two brothers.
