Page 88 - Discrete Mathematics and Its Applications

1.5 Nested Quantifiers 67

2
2
2
2
c) The sum of the squares of two integers is greater than e) ∃n∃m(n + m = 5) f) ∃n∃m(n + m = 6)
or equal to the square of their sum. g) ∃n∃m(n + m = 4 ∧ n − m = 1)
d) The absolute value of the product of two integers is h) ∃n∃m(n + m = 4 ∧ n − m = 2)
the product of their absolute values. i) ∀n∀m∃p(p = (m + n)/2)
20. Express each of these statements using predicates, quan- 28. Determine the truth value of each of these statements if
tifiers, logical connectives, and mathematical operators thedomainofeachvariableconsistsofallrealnumbers.
where the domain consists of all integers. 2 2
a) ∀x∃y(x = y) b) ∀x∃y(x = y )
a) The product of two negative integers is positive. c) ∃x∀y(xy = 0) d) ∃x∃y(x + y = y + x)
b) The average of two positive integers is positive. e) ∀x(x = 0 →∃y(xy = 1))
c) The difference of two negative integers is not neces- f) ∃x∀y(y = 0 → xy = 1)
sarily negative. g) ∀x∃y(x + y = 1)
d) The absolute value of the sum of two integers does h) ∃x∃y(x + 2y = 2 ∧ 2x + 4y = 5)
not exceed the sum of the absolute values of these i) ∀x∃y(x + y = 2 ∧ 2x − y = 1)
integers.
j) ∀x∀y∃z(z = (x + y)/2)
21. Use predicates, quantifiers, logical connectives, and
mathematical operators to express the statement that ev- 29. Suppose the domain of the propositional function P(x, y)
ery positive integer is the sum of the squares of four in- consists of pairs x and y, where x is 1, 2, or 3 and y is
1, 2, or 3. Write out these propositions using disjunctions
tegers.
and conjunctions.
22. Use predicates, quantifiers, logical connectives, and a) ∀x∀yP(x, y) b) ∃x∃yP(x, y)
mathematical operators to express the statement that there
is a positive integer that is not the sum of three squares. c) ∃x∀yP(x, y) d) ∀y∃xP(x, y)
30. Rewrite each of these statements so that negations ap-
23. Express each of these mathematical statements using
predicates, quantifiers, logical connectives, and mathe- pear only within predicates (that is, so that no negation
matical operators. is outside a quantifier or an expression involving logical
connectives).
a) The product of two negative real numbers is positive.
a) ¬Py ∃xP(x, y) b) ¬Hx ∃yP(x, y)
b) The difference of a real number and itself is zero.
c) ¬Py(Q(y) ∧∀x¬R(x, y))
c) Every positive real number has exactly two square
d) ¬Py( ∃xR(x, y) ∨∀xS(x, y))
roots.
d) A negative real number does not have a square root e) ¬Py( ∀x∃zT (x,y,z) ∨∃x∀zU(x,y,z))
that is a real number. 31. Express the negations of each of these statements so that
24. Translate each of these nested quantifications into an En- all negation symbols immediately precede predicates.
glish statement that expresses a mathematical fact. The a) ∀x∃y∀zT (x,y,z)
domain in each case consists of all real numbers. b) ∀x∃yP(x, y) ∨∀x∃yQ(x, y)
a) ∃x∀y(x + y = y) c) ∀x∃y(P(x, y) ∧∃zR(x,y,z))
b) ∀x∀y(((x ≥ 0) ∧ (y < 0)) → (x − y> 0)) d) ∀x∃y(P(x, y) → Q(x, y))
c) ∃x∃y(((x ≤ 0) ∧ (y ≤ 0)) ∧ (x − y> 0)) 32. Express the negations of each of these statements so that
d) ∀x∀y((x = 0) ∧ (y = 0) ↔ (xy = 0)) all negation symbols immediately precede predicates.
25. Translate each of these nested quantifications into an En- a) ∃z∀y∀xT (x,y,z)
glish statement that expresses a mathematical fact. The b) ∃x∃yP(x, y) ∧∀x∀yQ(x, y)
domain in each case consists of all real numbers. c) ∃x∃y(Q(x, y) ↔ Q(y, x))
a) ∃x∀y(xy = y) d) ∀y∃x∃z(T (x, y, z) ∨ Q(x, y))
b) ∀x∀y(((x < 0) ∧ (y < 0)) → (xy > 0)) 33. Rewrite each of these statements so that negations ap-
2
c) ∃x∃y((x >y) ∧ (x < y)) pear only within predicates (that is, so that no negation
d) ∀x∀y∃z(x + y = z) is outside a quantifier or an expression involving logical
26. Let Q(x, y) be the statement “x + y = x − y.” If the do- connectives).
main for both variables consists of all integers, what are a) ¬Hx ∀yP(x, y) b) ¬Hy ∃xP(x, y)
the truth values? c) ¬Hy ∀x(P(x, y) ∨ Q(x, y))
a) Q(1, 1) b) Q(2, 0) d) ¬(∃x∃y¬P(x, y) ∧∀x∀yQ(x, y))
c) ∀yQ(1,y) d) ∃xQ(x, 2) e) ¬Hx( ∃y∀zP(x,y,z) ∧∃z∀yP(x,y,z))
e) ∃x∃yQ(x, y) f) ∀x∃yQ(x, y) 34. Find a common domain for the variables x, y, and z
g) ∃y∀xQ(x, y) h) ∀y∃xQ(x, y)
for which the statement ∀x∀y((x = y) →∀z((z = x) ∨
i) ∀x∀yQ(x, y) (z = y))) is true and another domain for which it is false.
27. Determine the truth value of each of these statements if 35. Find a common domain for the variables x, y, z,
the domain for all variables consists of all integers.
and w for which the statement ∀x∀y∀z∃w((w = x) ∧
2
2
a) ∀n∃m(n <m) b) ∃n∀m(n<m ) (w = y) ∧ (w = z)) is true and another common domain
c) ∀n∃m(n + m = 0) d) ∃n∀m(nm = m) for these variables for which it is false.