Page 133 - Discrete Mathematics and Its Applications

112 1 / The Foundations: Logic and Proofs

2. Find the truth table of the compound proposition (p ∨ 13. Suppose that you meet three people Aaron, Bohan, and
q) → (p ∧¬r). Crystal.CanyoudeterminewhatAaron,Bohan,andCrys-
3. Show that these compound propositions are tautologies. tal are ifAaron says “All of us are knaves” and Bohan says
“Exactly one of us is a knave.”?
a) (¬q ∧ (p → q)) →¬p
b) ((p ∨ q) ∧¬p) → q 14. Suppose that you meet three people, Anita, Boris, and
Carmen. What are Anita, Boris, and Carmen if Anita says
4. Give the converse, the contrapositive, and the inverse of
“I am a knave and Boris is a knight” and Boris says “Ex-
these conditional statements.
actly one of the three of us is a knight”?
a) If it rains today, then I will drive to work.
15. (Adapted from [Sm78]) Suppose that on an island there
b) If |x|= x, then x ≥ 0.
2
c) If n is greater than 3, then n is greater than 9. are three types of people, knights, knaves, and normals
(also known as spies). Knights always tell the truth,
5. Given a conditional statement p → q, find the converse knaves always lie, and normals sometimes lie and some-
of its inverse, the converse of its converse, and the con- times tell the truth. Detectives questioned three inhabi-
verse of its contrapositive.
tants of the island—Amy, Brenda, and Claire—as part
6. Given a conditional statement p → q, find the inverse of of the investigation of a crime. The detectives knew that
its inverse, the inverse of its converse, and the inverse of one of the three committed the crime, but not which one.
its contrapositive. They also knew that the criminal was a knight, and that the
7. Find a compound proposition involving the propositional other two were not. Additionally, the detectives recorded
variables p, q, r, and s that is true when exactly three of these statements: Amy: “I am innocent.” Brenda: “What
these propositional variables are true and is false other- Amy says is true.” Claire: “Brenda is not a normal.” Af-
wise. ter analyzing their information, the detectives positively
8. Show that these statements are inconsistent: “If Sergei identified the guilty party. Who was it?
takes the job offer then he will get a signing bonus.” “If 16. Show that if S is a proposition, where S is the conditional
Sergei takes the job offer, then he will receive a higher statement “If S is true, then unicorns live,” then “Uni-
salary.” “If Sergei gets a signing bonus, then he will not corns live” is true. Show that it follows that S cannot be a
receive a higher salary.” “Sergei takes the job offer.” proposition. (This paradox is known as Löb’s paradox.)
9. Show that these statements are inconsistent: “If Miranda 17. Showthattheargumentwithpremises“Thetoothfairyisa
does not take a course in discrete mathematics, then she real person” and “The tooth fairy is not a real person” and
will not graduate.” “If Miranda does not graduate, then conclusion “You can find gold at the end of the rainbow”
she is not qualified for the job.” “If Miranda reads this is a valid argument. Does this show that the conclusion is
book, then she is qualified for the job.” “Miranda does true?
not take a course in discrete mathematics but she reads 18. Suppose that the truth value of the proposition p i is T
this book.”
whenever i is an odd positive integer and is F when-
Teachers in the Middle Ages supposedly tested the realtime ever i is an even positive integer. Find the truth values
propositional logic ability of a student via a technique known of 100 (p i ∧ p i+1 ) and 100 (p i ∨ p i+1 ).
as an obligato game. In an obligato game, a number of rounds i=1 i=1
∗ 19. Model 16 × 16 Sudoku puzzles (with 4 × 4 blocks) as
is set and in each round the teacher gives the student succes- satisfiability problems.
sive assertions that the student must either accept or reject as
they are given. When the student accepts an assertion, it is 20. Let P(x) be the statement “Student x knows calculus” and
added as a commitment; when the student rejects an assertion let Q(y) be the statement “Class y contains a student who
its negation is added as a commitment. The student passes knows calculus.” Express each of these as quantifications
the test if the consistency of all commitments is maintained of P(x) and Q(y).
throughout the test. a) Some students know calculus.
10. Suppose that in a three-round obligato game, the teacher b) Not every student knows calculus.
first gives the student the proposition p → q, then the c) Every class has a student in it who knows calculus.
proposition ¬(p ∨ r) ∨ q, and finally the proposition q. d) Every student in every class knows calculus.
Forwhichoftheeightpossiblesequencesofthreeanswers e) There is at least one class with no students who know
will the student pass the test? calculus.
11. Suppose that in a four-round obligato game, the teacher 21. Let P(m, n) be the statement “m divides n,” where the do-
first gives the student the proposition ¬(p → (q ∧ r)), main for both variables consists of all positive integers.
then the proposition p ∨¬q, then the proposition ¬r, and (By “m divides n” we mean that n = km for some integer
finally, the proposition (p ∧ r) ∨ (q → p). For which of k.) Determine the truth values of each of these statements.
the 16 possible sequences of four answers will the student a) P(4, 5) b) P(2, 4)
pass the test? c) ∀m ∀n P(m, n) d) ∃m ∀n P (m, n)
12. Explain why every obligato game has a winning strategy. e) ∃n ∀m P (m, n) f) ∀nP(1,n)
Exercises 13 and 14 are set on the island of knights and knaves 22. Find a domain for the quantifiers in ∃x∃y(x = y ∧
described in Example 7 in Section 1.2. ∀z((z = x) ∨ (z = y))) such that this statement is true.