Statements with Multiple Quantifiers
Statements with Multiple Quantifiers
When a statement contains more than one quantifier, we
imagine the actions suggested by the quantifiers as being
performed in the order in which the quantifiers occur.
For instance, consider a statement of the form
∀
x
in set
D
,
∃
y
in set
E
such that
x
and
y
satisfy property
P
(
x
,
y
).
Statements with Multiple Quantifiers
∀
people
x
,
∃
a person
y
such that
x
loves
y
.
∃
a person
y
such that
∀
people
x
,
x
loves
y
.
Informally,
∀
…
∃
…such that
…
is similar to
“everyone has something”
∃
…
∀
…such that
…
is similar to
“someone has everything”
Statements with Multiple Quantifiers
Interestingly, however, if one quantifier immediately follows
another quantifier
of the same type
, then the order of the
quantifiers does not affect the meaning.
∀
real numbers
x
and
∀
real numbers
y
,
x
+
y
=
y
+
x.
∀
real numbers
y
and
∀
real numbers
x
,
x
+
y
=
y
+
x.
Usually, this is expressed more briefly as
∀
real numbers
x
and
y
,
x
+
y
=
y
+
x.
Example 1 –
Truth of a
∀∃
Statement in a Tarski World
Consider the Tarski world shown below.
Show that the following statement is true in this world:
For all triangles
x
,
there is a square
y
such that
x
and
y
have the same color.
Example 1 –
Truth of a
∀∃
Statement in a Tarski World
Consider the Tarski world shown below.
Show that the following statement is true in this world:
There exists a triangle
x
such that for all circles
y
,
x
and
y
have different color.
You can use the same rules to negate multiply-quantified
statements that you used to negate simpler quantified
statements.
We already know that
∼
(
∀
x
in
D
,
P
(
x
)) ≡
∃
x
in
D
such that
∼
P
(
x
).
and
∼
(
∃
x
in
D
such that
P
(
x
)) ≡
∀
x
in
D
,
∼
P
(
x
).
Negations of Multiply-Quantified Statements
We apply these laws to find
∼
(
∀
x
in
D
,
∃
y
in
E
such that
P
(
x
,
y
))
by moving in stages from left to right along the sentence.
First version of negation
:
∃
x
in
D
such that
∼
(
∃
y
in
E
such that
P
(
x
,
y
)).
Final version of negation
:
∃
x
in
D
such that
∀
y
in
E
,
∼
P
(
x
,
y
).
Negations of Multiply-Quantified Statements
Similarly, to find
∼
(
∃
x
in
D
such that
∀
y
in
E
,
P
(
x
,
y
)),
we have
First version of negation
:
∀
x
in
D
,
∼
(
∀
y
in
E
,
P
(
x
,
y
)).
Final version of negation
:
∀
x
in
D
,
∃
y
in
E
such that
∼
P
(
x
,
y
).
Negations of Multiply-Quantified Statements
These facts can be summarized as follows:
Negations of Multiply-Quantified Statements
Write a negation for each of the
following statements, and determine
which is true, the given statement or
its negation.
a
.
F
o
r
a
l
l
s
q
u
a
r
e
s
x
,
t
h
e
r
e
i
s
a
c
i
r
c
l
e
y
s
u
c
h
t
h
a
t
x
a
n
d
y
h
a
v
e
t
h
e
s
a
m
e
c
o
l
o
r
.
Example 8 –
Negating Statements in a Tarski World
Negation
:
∃
a square
x
such that
∀
circles
y
,
x
and
y
do not have the same color.
The negation is true. Square
e
is black and no circle is
black, so there is a square that does not have the same
color as any circle.
Write a negation for each of the
following statements, and determine
which is true, the given statement or
its negation.
b
.
T
h
e
r
e
i
s
a
t
r
i
a
n
g
l
e
x
s
u
c
h
t
h
a
t
f
o
r
a
l
l
s
q
u
a
r
e
s
y
,
x
i
s
t
o
t
h
e
r
i
g
h
t
o
f
y
.
Example 8 –
Negating Statements in a Tarski World
Negation
:
∀
triangles
x
,
∃
a square
y
such that
x
is not to the right of
y
.
The negation is true because no matter what triangle is
chosen, it is not to the right of square
g
(or square
j
).
In some areas of computer science, logical statements are
expressed in purely symbolic notation.
The notation involves using predicates to describe all
properties of variables and omitting the words
such that
in
existential statements.
The formalism also depends on the following facts:
“
∀
x
in
D
,
P
(
x
)” can be written as “
∀
x
(
x
in
D
→
P
(
x
)),” and
“
∃
x
in
D
such that
P
(
x
)” can be written as
“
∃
x
(
x
in
D
∧
P
(
x
)).”
Formal Logical Notation
Formal logical notation is used in branches of computer
science such as artificial intelligence, program verification,
and automata theory and formal languages.
T
a
k
e
n
t
o
g
e
t
h
e
r
,
t
h
e
s
y
m
b
o
l
s
f
o
r
q
u
a
n
t
i
f
i
e
r
s
,
v
a
r
i
a
b
l
e
s
,
p
r
e
d
i
c
a
t
e
s
,
a
n
d
l
o
g
i
c
a
l
c
o
n
n
e
c
t
i
v
e
s
m
a
k
e
u
p
w
h
a
t
i
s
k
n
o
w
n
a
s
t
h
e
l
a
n
g
u
a
g
e
o
f
f
i
r
s
t
-
o
r
d
e
r
l
o
g
i
c
.
Formal Logical Notation
When a statement involves multiple quantifiers, the actions are visualized in the order they appear. The relative position of quantifiers can impact the statement's meaning. This concept is illustrated through examples in a Tarski world, demonstrating the truth of statements with various quantifiers. The process of negating multiply-quantified statements is also explained, emphasizing the importance of the order of quantifiers in such cases.
Uploaded on Nov 28, 2024 | 0 Views
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
Statements with Multiple Quantifiers When a statement contains more than one quantifier, we imagine the actions suggested by the quantifiers as being performed in the order in which the quantifiers occur. For instance, consider a statement of the form x in set D, y in set E such that x and y satisfy property P(x, y). 1
Statements with Multiple Quantifiers people x, a person y such that x loves y. a person y such that people x, x loves y. Informally, such that is similar to everyone has something such that is similar to someone has everything 2
Statements with Multiple Quantifiers Interestingly, however, if one quantifier immediately follows another quantifier of the same type, then the order of the quantifiers does not affect the meaning. real numbers x and real numbers y, x+y=y+x. real numbers y and real numbers x, x+y=y+x. Usually, this is expressed more briefly as real numbers x and y, x+y = y+x. 3
Example 1 Truth of a Statement in a Tarski World Consider the Tarski world shown below. Show that the following statement is true in this world: For all triangles x, there is a square y such that x and y have the same color. 4
Example 1 Truth of a Statement in a Tarski World Consider the Tarski world shown below. Show that the following statement is true in this world: There exists a triangle x such that for all circles y, x and y have different color. 5
Negations of Multiply-Quantified Statements You can use the same rules to negate multiply-quantified statements that you used to negate simpler quantified statements. We already know that ( x in D, P(x)) x in D such that P(x). and ( x in D such that P(x)) x in D, P(x). 6
Negations of Multiply-Quantified Statements We apply these laws to find ( x in D, y in E such that P(x, y)) by moving in stages from left to right along the sentence. First version of negation: x in D such that ( y in E such that P(x, y)). Final version of negation: x in D such that y in E, P(x, y). 7
Negations of Multiply-Quantified Statements Similarly, to find ( x in D such that y in E, P(x, y)), we have First version of negation: x in D, ( y in E, P(x, y)). Final version of negation: x in D, y in E such that P(x, y). 8
Negations of Multiply-Quantified Statements These facts can be summarized as follows: 9
Example 8 Negating Statements in a Tarski World Write a negation for each of the following statements, and determine which is true, the given statement or its negation. a. For all squares x, there is a circle y such that x and y have the same color. Negation: a square x such that circles y, x and y do not have the same color. The negation is true. Square e is black and no circle is black, so there is a square that does not have the same color as any circle. 10
Example 8 Negating Statements in a Tarski World Write a negation for each of the following statements, and determine which is true, the given statement or its negation. b.There is a triangle x such that for all squares y, x is to the right of y. Negation: triangles x, a square y such that x is not to the right of y. The negation is true because no matter what triangle is chosen, it is not to the right of square g (or square j). 11
Formal Logical Notation In some areas of computer science, logical statements are expressed in purely symbolic notation. The notation involves using predicates to describe all properties of variables and omitting the words such that in existential statements. The formalism also depends on the following facts: x in D, P(x) can be written as x(x in D P(x)), and x in D such that P(x) can be written as x(x in D P(x)). 12
Formal Logical Notation Formal logical notation is used in branches of computer science such as artificial intelligence, program verification, and automata theory and formal languages. Taken together, the symbols for quantifiers, variables, predicates, and logical connectives make up what is known as the language of first-order logic. 13
