Page 134 - Discrete Mathematics and Its Applications

Supplementary Exercises 113

23. Find a domain for the quantifiers in ∃x∃y(x = y ∧ 33. Express this statement using quantifiers: “Every student
∀z((z = x) ∨ (z = y))) such that this statement is false. in this class has taken some course in every department
24. Use existential and universal quantifiers to express the in the school of mathematical sciences.”
statement “No one has more than three grandmothers” us- 34. Express this statement using quantifiers: “There is a build-
ing the propositional function G(x, y), which represents ing on the campus of some college in the United States in
“x is the grandmother of y.” which every room is painted white.”
25. Use existential and universal quantifiers to express the 35. Express the statement “There is exactly one student in this
statement “Everyone has exactly two biological parents” class who has taken exactly one mathematics class at this
using the propositional function P(x, y), which repre- school” using the uniqueness quantifier. Then express this
sents “x is the biological parent of y.” statement using quantifiers, without using the uniqueness
quantifier.
26. The quantifier ∃ n denotes “there exists exactly n,” so that
∃ n xP(x) means there exist exactly n values in the do- 36. Describe a rule of inference that can be used to prove that
main such that P(x) is true. Determine the true value of there are exactly two elements x and y in a domain such
these statements where the domain consists of all real that P(x) and P(y) are true. Express this rule of inference
numbers. as a statement in English.
2
a) ∃ 0 x(x =−1) b) ∃ 1 x(|x|= 0) 37. Use rules of inference to show that if the premises
2
c) ∃ 2 x(x = 2) d) ∃ 3 x(x =|x|) ∀x(P(x) → Q(x)), ∀x(Q(x) → R(x)), and ¬R(a),
where a is in the domain, are true, then the conclusion
27. Express each of these statements using existential and ¬P(a) is true.
universal quantifiers and propositional logic where ∃ n is 3
defined in Exercise 26. 38. Prove that if x is irrational, then x is irrational.
√
a) ∃ 0 xP(x) b) ∃ 1 xP(x) 39. Prove that if x is irrational and x ≥ 0, then x is irra-
tional.
c) ∃ 2 xP(x) d) ∃ 3 xP(x)
40. Prove that given a nonnegative integer n, there is a unique
28. Let P(x, y) be a propositional function. Show that 2 2
∃x ∀y P (x, y) →∀y ∃x P(x, y) is a tautology. nonnegative integer m such that m ≤ n<(m + 1) .
2
41. Provethatthereexistsanintegermsuchthatm > 10 1000 .
29. Let P(x) and Q(x) be propositional functions. Show Is your proof constructive or nonconstructive?
that∃x(P(x) → Q(x))and∀x P(x) →∃x Q(x)always
42. Prove that there is a positive integer that can be written
have the same truth value.
as the sum of squares of positive integers in two differ-
30. If ∀y ∃x P (x, y) is true, does it necessarily follow that
ent ways. (Use a computer or calculator to speed up your
∃x ∀y P (x, y) is true?
work.)
31. If ∀x ∃y P (x, y) is true, does it necessarily follow that 43. Disprove the statement that every positive integer is the
∃x ∀y P (x, y) is true?
sum of the cubes of eight nonnegative integers.
32. Find the negations of these statements. 44. Disprove the statement that every positive integer is the
a) If it snows today, then I will go skiing tomorrow. sum of at most two squares and a cube of nonnegative
b) Every person in this class understands mathematical integers.
induction. 45. Disprove the statement that every positive integer is the
c) Some students in this class do not like discrete math- sum of 36 fifth powers of nonnegative integers.
ematics. 46. Assuming the truth of the theorem that states that √ n is
d) In every mathematics class there is some student who irrational whenever n is a positive integer that is not a
falls asleep during lectures. perfect square, prove that √ 2 + √ 3 is irrational.

Computer Projects

Write programs with the specified input and output.

1. Given the truth values of the propositions p and q, find the 4. Given the truth values of the propositions p and q in
truth values of the conjunction, disjunction, exclusive or, fuzzy logic, find the truth value of the disjunction and
conditional statement, and biconditional of these proposi- the conjunction of p and q (see Exercises 46 and 47 of
tions. Section 1.1).
∗ 5. Givenpositiveintegersmandn,interactivelyplaythegame
2. Given two bit strings of length n, find the bitwise AND,
bitwise OR, and bitwise XOR of these strings. of Chomp.
∗ 6. Given a portion of a checkerboard, look for tilings of this
∗ 3. Give a compound proposition, determine whether it is sat- checkerboardwithvarioustypesofpolyominoes,including
isfiable by checking its truth value for all positive assign- dominoes, the two types of triominoes, and larger polyomi-
ments of truth values to its propositional variables. noes.