Page 89 - Discrete Mathematics and Its Applications

68 1 / The Foundations: Logic and Proofs

36. Express each of these statements using quantifiers. Then 45. Determine the truth value of the statement ∀x∃y(xy = 1)
form the negation of the statement so that no negation is if the domain for the variables consists of
to the left of a quantifier. Next, express the negation in a) the nonzero real numbers.
simple English. (Do not simply use the phrase “It is not b) the nonzero integers.
the case that.”)
c) the positive real numbers.
a) No one has lost more than one thousand dollars play- 46. Determine the truth value of the statement ∃x∀y(x ≤ y )
2
ing the lottery. if the domain for the variables consists of
b) There is a student in this class who has chatted with
exactly one other student. a) the positive real numbers.
c) No student in this class has sent e-mail to exactly two b) the integers.
other students in this class. c) the nonzero real numbers.
d) Some student has solved every exercise in this book. 47. Show that the two statements ¬Px ∀yP(x, y) and
e) No student has solved at least one exercise in every
section of this book. ∀x∃y¬P(x, y), where both quantifiers over the first vari-
able in P(x, y) have the same domain, and both quanti-
37. Express each of these statements using quantifiers. Then fiers over the second variable in P(x, y) have the same
form the negation of the statement so that no negation is domain, are logically equivalent.
to the left of a quantifier. Next, express the negation in
∗ 48. Show that ∀xP(x) ∨∀xQ(x) and ∀x∀y(P (x) ∨ Q(y)),
simple English. (Do not simply use the phrase “It is not
the case that.”) where all quantifiers have the same nonempty domain,
are logically equivalent. (The new variable y is used to
a) Every student in this class has taken exactly two math- combine the quantifications correctly.)
ematics classes at this school.
b) Someone has visited every country in the world except ∗ 49. a) Show that ∀xP(x) ∧∃xQ(x) is logically equivalent
Libya. to ∀x∃y(P(x) ∧ Q(y)), where all quantifiers have
c) No one has climbed every mountain in the Himalayas. the same nonempty domain.
d) Every movie actor has either been in a movie with b) Show that ∀xP(x) ∨∃xQ(x) is equivalent to ∀x∃y
Kevin Bacon or has been in a movie with someone (P(x) ∨ Q(y)), where all quantifiers have the same
who has been in a movie with Kevin Bacon.
nonempty domain.
38. Express the negations of these propositions using quan-
A statement is in prenex normal form (PNF) if and only if it
tifiers, and in English.
is of the form
a) Every student in this class likes mathematics.
b) There is a student in this class who has never seen a
computer. Q 1 x 1 Q 2 x 2 ··· Q k x k P(x 1 ,x 2 ,...,x k ),
c) There is a student in this class who has taken every
mathematics course offered at this school. where each Q i ,i = 1, 2,...,k, is either the existential quan-
d) There is a student in this class who has been in at least tifier or the universal quantifier, and P(x 1 ,...,x k ) is a pred-
one room of every building on campus.
icate involving no quantifiers. For example, ∃x∀y(P (x, y) ∧
39. Find a counterexample, if possible, to these universally Q(y)) is in prenex normal form, whereas ∃xP(x) ∨∀xQ(x)
quantified statements, where the domain for all variables is not (because the quantifiers do not all occur first).
consists of all integers. Every statement formed from propositional variables,
2
2
a) ∀x∀y(x = y → x = y) predicates, T, and F using logical connectives and quan-
2
b) ∀x∃y(y = x) tifiers is equivalent to a statement in prenex normal form.
c) ∀x∀y(xy ≥ x) Exercise 51 asks for a proof of this fact.
40. Find a counterexample, if possible, to these universally ∗ 50. Put these statements in prenex normal form. [Hint: Use
quantified statements, where the domain for all variables logical equivalence from Tables 6 and 7 in Section 1.3,
consists of all integers. Table 2 in Section 1.4, Example 19 in Section 1.4,
a) ∀x∃y(x = 1/y) Exercises 45 and 46 in Section 1.4, and Exercises 48 and
2
b) ∀x∃y(y − x< 100) 49.]
2
3
c) ∀x∀y(x = y )
a) ∃xP(x) ∨∃xQ(x) ∨ A, where A is a proposition not
41. Use quantifiers to express the associative law for multi- involving any quantifiers.
plication of real numbers.
b) ¬(∀xP(x) ∨∀xQ(x))
42. Use quantifiers to express the distributive laws of multi-
c) ∃xP(x) →∃xQ(x)
plication over addition for real numbers.
∗∗ 51. Show how to transform an arbitrary statement to a state-
43. Use quantifiers and logical connectives to express the fact
that every linear polynomial (that is, polynomial of de- ment in prenex normal form that is equivalent to the given
gree 1) with real coefficients and where the coefficient of statement. (Note: A formal solution of this exercise re-
x is nonzero, has exactly one real root. quires use of structural induction, covered in Section 5.3.)
44. Use quantifiers and logical connectives to express the fact ∗ 52. Express the quantification ∃!xP(x), introduced in Sec-
that a quadratic polynomial with real number coefficients tion 1.4, using universal quantifications, existential quan-
has at most two real roots. tifications, and logical operators.