# 《离散数学》杨争锋ch01-3_图文

§1.4 Nested Quantifiers 1. Introduction nested quantifiers -------occur within the scope of other quantifiers ?x ?y(x+y=0)

2. Translating statements involving nested quantifiers (1) Example 1 (page 44) universe discourse for x and y --------all real numbers ?x ?y (x+y=y+x)------commutative law -------true ?x ?y (x+y=0)------true ?x ?y ?z (x+(y+z)=(x+y)+z)------true -------associative law

(2) Example 2 (page 51) ?x ?y ( (x>0) /\ (y<0)→(xy<0)) universe discourse----all real numbers -----English meaning

-----value…….true

3. The order of Quantifiers (1) Example 3 (page 52) P(x,y)-----”x+y=y+x” universe of discourse---all real numbers How about
?x ?y P(x,y)----------true ?y ?x P(x,y)---------true We have: ?x ?y P(x,y) ≡ ?y ?x P(x,y)

(2) Example 4 (page 52) Q(x,y)------”x+y=0”
universe of discourse----all real numbers

?y ?x Q(x,y) and? x ?y Q(x,y)?

Solution: (a) ?y ?x Q(x,y)----There is a real number y such that for every real number x, Q(x,y). ----false (b) ? x ?y Q(x,y)----For every real number x there is a real number y such that Q(x,y). -----true (c) ?y ? x Q(x,y)-----? x ?y Q(x,y) ( not equivalent)

(4) Example 5(page 53) Q(x,y)-----”x+y=z” universe of discourse -----all real numbers How about ?x ?y ?z Q(x,y,z) and ?z ?x ?y Q(x,y,z) Solution: ?x ?y ?z Q(x,y,z) is true. ?z ?x ?y Q(x,y,z) is false.

Translating Mathematical Statements into Statements Involving Nested Quantifiers

? Example 6(page 54): ? Example 7:

4. Translating from Nested Quantifiers into English (3) Example 9 (page 55)

?x ( C(x) \/ ?y (C(y) /\ F(x,y)) )
C(x)----”x has a computer” F(x,y)----”x,y are friends” universe of discourse for both x and y -----------all students in the school ??? What does the formula mean?

(4) Example 4 (page 45)

?x ?y ?z (
(F(x,y) /\ F(x,z) /\ (y≠z)) →?F(y,z) ) F(a,b)----a and b are friends universe of discourse for x, y and z ----- all students in your school
What does this formula mean? (These is a student none of whose friends are also friends with each other.)

5. Translating Sentences Into Logical Expression (1) Example 11 (page 56) “If a person is female and is parent, then this person is someone’s mother.” universe of discourse ------all people

Solution: also can be expressed as “For every person, if person x is a female and person x is a parent, then there exists a person y such that person x is the mother of person x.” F(x)-----x is female; P(x)-----x is a parent Then, the formula is:
?x ( (F(x) /\ P(x)) →?y M(x,y)) ?x ?y ( (F(x) /\ P(x)) →M(x,y)) or

(2) Example 12 (page 56) “Everyone has exactly one best friend” Universe of discourse --------all people Solution: “For every person x, person x has exactly one best friend”
B(x,y) -----y is the best friend of x

?y ( B(x,y) /\ ?z ( (z≠y)→?B(x,z) ) )
?x(………the above formula…………….)

6. Negating Nested Quantifiers (1) Example 14 (page 57)
Express the negation of ?x?y (xy=1) so that no negation precedes a quantifier. Solution:

??x?y (xy=1) ≡ ?x ? ?y (xy=1) ≡ ?x ?y ? (xy=1)
≡ ?x ?y (xy≠1)

(3) Summary (page 53, Table 1) Statement When true? When false?
?x ?y P(x,y) ?y ?x P(x,y) ---------------------------------------------------------------

?x ?y Q(x,y)
--------------------------------------------------------------

?x?y Q(x,y) --------------------------------------------------------? x ? y P(x,y) ? y ? x P(x,y)

Further, (a) If ?y?x Q(x,y) is true, then ? x?y Q(x,y) is true. (b) If ? x?y Q(x,y) is true, then it is not necessary for ?y?x Q(x,y) to be true. Example 5(Page 53) Read it by yourself

Homework
Page 59: 26、28、30、32、38

《离散数学》杨争锋ch01-1
《离散数学》杨争锋ch01-2
《离散数学》杨争锋ch01-4
《离散数学》杨争锋ch04-3
《离散数学》杨争锋ch04-1
《离散数学》杨争锋ch06-1
《离散数学》杨争锋ch07-1
《离散数学》杨争锋ch02-4
《离散数学》杨争锋ch08-1
《离散数学》杨争锋ch04-4