Introduction to Predicate Logic and Quantifiers in Discrete Mathematics
Discrete Mathematics
Lecture 4 & 5:
Predicate and Quantifier
By:
Nur Uddin, Ph.D
1
Motivation
•
Propositional logic cannot adequately express the meaning of all
statements in mathematics and in natural language.
•
W
e
w
i
l
l
i
n
t
r
o
d
u
c
e
a
m
o
r
e
p
o
w
e
r
f
u
l
t
y
p
e
o
f
l
o
g
i
c
c
a
l
l
e
d
p
r
e
d
i
c
a
t
e
l
o
g
i
c
.
•
How predicate logic can be used to express the meaning of a wide
range of statements in mathematics and computer science in
ways that permit us to reason and explore relationships
between
objects.
2
Predicate
•
The statement “
x
is greater than 3” has two parts:
•
The first part, the variable
x
, is the subject of the statement.
•
T
h
e
s
e
c
o
n
d
p
a
r
t
—
t
h
e
p
r
e
d
i
c
a
t
e
,
“
i
s
g
r
e
a
t
e
r
t
h
a
n
3
”
—
r
e
f
e
r
s
t
o
a
p
r
o
p
e
r
t
y
t
h
a
t
t
h
e
s
u
b
j
e
c
t
o
f
t
h
e
s
t
a
t
e
m
e
n
t
c
a
n
h
a
v
e
.
•
We can denote the statement “
x
is greater than 3” by
P(x)
, where
P
denotes the predicate “is greater than 3” and
x
is the variable.
•
T
h
e
s
t
a
t
e
m
e
n
t
P
(
x
)
i
s
a
l
s
o
s
a
i
d
t
o
b
e
t
h
e
v
a
l
u
e
o
f
t
h
e
p
r
o
p
o
s
i
t
i
o
n
a
l
f
u
n
c
t
i
o
n
P
a
t
x
.
•
Once a value has been assigned to the variable
x
, the statement
P(x)
becomes a proposition and has a truth value
3
Examples
1.
Let
P(x)
denote the statement “
x >
3.” What are the truth values
of
P(
4
)
and
P(
2
)
?
2.
Let
Q(x, y)
denote the statement “
x
=
y
+ 3.” What are the truth
values of the propositions
Q(
1
,
2
)
and
Q(
3
,
0
)
?
4
Quantifiers
•
When the variables in a propositional function are assigned
values, the resulting statement becomes a proposition with a
certain truth value.
•
H
o
w
e
v
e
r
,
t
h
e
r
e
i
s
a
n
o
t
h
e
r
i
m
p
o
r
t
a
n
t
w
a
y
,
c
a
l
l
e
d
q
u
a
n
t
i
f
i
c
a
t
i
o
n
,
t
o
c
r
e
a
t
e
a
p
r
o
p
o
s
i
t
i
o
n
f
r
o
m
a
p
r
o
p
o
s
i
t
i
o
n
a
l
f
u
n
c
t
i
o
n
.
Q
u
a
n
t
i
f
i
c
a
t
i
o
n
e
x
p
r
e
s
s
e
s
t
h
e
e
x
t
e
n
t
t
o
w
h
i
c
h
a
p
r
e
d
i
c
a
t
e
i
s
t
r
u
e
o
v
e
r
a
r
a
n
g
e
o
f
e
l
e
m
e
n
t
s
.
•
In English, the words
all
,
some
,
many
,
none
, and
few
are used in
quantifications.
5
Quantification types
•
Two types of quantification:
1.
U
n
i
v
e
r
s
a
l
q
u
a
n
t
i
f
i
c
a
t
i
o
n
t
e
l
l
u
s
t
h
a
t
a
p
r
e
d
i
c
a
t
e
i
s
t
r
u
e
f
o
r
e
v
e
r
y
e
l
e
m
e
n
t
u
n
d
e
r
c
o
n
s
i
d
e
r
a
t
i
o
n
2.
e
x
i
s
t
e
n
t
i
a
l
q
u
a
n
t
i
f
i
c
a
t
i
o
n
t
e
l
l
s
u
s
t
h
a
t
t
h
e
r
e
i
s
o
n
e
o
r
m
o
r
e
e
l
e
m
e
n
t
u
n
d
e
r
c
o
n
s
i
d
e
r
a
t
i
o
n
f
o
r
w
h
i
c
h
t
h
e
p
r
e
d
i
c
a
t
e
i
s
t
r
u
e
.
•
T
h
e
a
r
e
a
o
f
l
o
g
i
c
t
h
a
t
d
e
a
l
s
w
i
t
h
p
r
e
d
i
c
a
t
e
s
a
n
d
q
u
a
n
t
i
f
i
e
r
s
i
s
c
a
l
l
e
d
t
h
e
p
r
e
d
i
c
a
t
e
c
a
l
c
u
l
u
s
.
6
Universal Quantifier
•
M
a
n
y
m
a
t
h
e
m
a
t
i
c
a
l
s
t
a
t
e
m
e
n
t
s
a
s
s
e
r
t
t
h
a
t
a
p
r
o
p
e
r
t
y
i
s
t
r
u
e
f
o
r
a
l
l
v
a
l
u
e
s
o
f
a
v
a
r
i
a
b
l
e
i
n
a
p
a
r
t
i
c
u
l
a
r
d
o
m
a
i
n
,
c
a
l
l
e
d
t
h
e
d
o
m
a
i
n
o
f
d
i
s
c
o
u
r
s
e
(
o
r
t
h
e
u
n
i
v
e
r
s
e
o
f
d
i
s
c
o
u
r
s
e
)
,
o
f
t
e
n
j
u
s
t
r
e
f
e
r
r
e
d
t
o
a
s
t
h
e
d
o
m
a
i
n
.
7
Universal Quantifier
8
Example:
Universal Quantifier
9
Example:
Example:
Existensial Quantifier
10
Besides the phrase “there exists,”we can also express existential quantification in
many otherways, such as by using the words “for some,” “for at least one,” or “there
is.” The existential quantification
∃
xP(x)
is read as:
“There is an
x
such that
P(x)
,”
“There is at least one
x
such that
P(x)
,”
“For some
xP(x)
.”
Existensial Quantifier
11
Example 1:
Example 2:
The Uniqueness Quantifier
•
T
h
e
u
n
i
q
u
e
n
e
s
s
q
u
a
n
t
i
f
i
e
r
,
d
e
n
o
t
e
d
b
y
∃
!
o
r
∃
1
.
•
The notation
∃
!
xP(x) or
[
∃
1
xP(x)
] states “There exists a unique
x
such that
P(x)
is true.”
•
For example,
∃
!
x(x
− 1 = 0
)
, where the domain is the set of real
numbers, states that there is a unique real number
x
such that
x
−1=0. This is a true statement, as
x
= 1 is the unique real number
such that
x
− 1 = 0.
12
Homework 1
13
In this lecture series by Dr. Nur Uddin, we delve into the limitations of propositional logic and the introduction of predicate logic as a more powerful tool for expressing statements in mathematics and computer science. Learn about predicates, quantifiers, and how to reason and explore relationships between objects using predicate calculus.
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
Discrete Mathematics Lecture 4 & 5: Predicate and Quantifier By: Nur Uddin, Ph.D 1
Motivation Propositional logic cannot adequately express the meaning of all statements in mathematics and in natural language. We will introduce a more powerful type of logic called predicate logic. How predicate logic can be used to express the meaning of a wide range of statements in mathematics and computer science in ways that permit us to reason and explore relationships between objects. 2
Predicate The statement x is greater than 3 has two parts: The first part, the variable x, is the subject of the statement. The second part the predicate, is greater than 3 refers to a property that the subject of the statement can have. We can denote the statement x is greater than 3 by P(x), where P denotes the predicate is greater than 3 and x is the variable. The statement P(x) is also said to be the value of the propositional function P at x. Once a value has been assigned to the variable x, the statement P(x) becomes a proposition and has a truth value 3
Examples 1. Let P(x) denote the statement x > 3. What are the truth values of P(4) and P(2)? 2. Let Q(x, y) denote the statement x = y + 3. What are the truth values of the propositions Q(1, 2) and Q(3, 0)? 4
Quantifiers When the variables in a propositional function are assigned values, the resulting statement becomes a proposition with a certain truth value. However, there is another important way, called quantification, to create a proposition from a propositional function. Quantification expresses the extent to which a predicate is true over a range of elements. In English, the words all, some, many, none, and few are used in quantifications. 5
Quantification types Two types of quantification: 1. Universal quantification every element under consideration 2. existential quantification element under consideration for which the predicate is true. tell us that a predicate is true for tells us that there is one or more The area of logic that deals with predicates and quantifiers is called the predicate calculus. 6
Universal Quantifier Many mathematical statements assert that a property is true for all values of a variable in a particular domain, called the domain of discourse (or the universe of discourse), often just referred to as the domain. 7
Universal Quantifier Example: 8
Universal Quantifier Example: Example: 9
Existensial Quantifier Besides the phrase there exists, we can also express existential quantification in many otherways, such as by using the words for some, for at least one, or there is. The existential quantification xP(x) is read as: There is an x such that P(x), There is at least one x such that P(x), For some xP(x). 10
Existensial Quantifier Example 1: Example 2: 11
The Uniqueness Quantifier The uniqueness quantifier, denoted by ! or 1. The notation !xP(x) or [ 1xP(x)] states There exists a unique x such that P(x) is true. For example, !x(x 1 = 0), where the domain is the set of real numbers, states that there is a unique real number x such that x 1=0. This is a true statement, as x = 1 is the unique real number such that x 1 = 0. 12
Homework 1 1. 2. 13
