U.C. Berkeley – CS70: Discrete Mathematics and Probability Problem Set 2Lecturers: Umesh Vazirani & Christos H. Papadimitriou Due September 8, 2006 at 4:00pmProblem Set 21. Exclusive OR The exclusive OR (written as XOR or ⊕ ) is just what it sounds like: P ⊕ Q is tr uewhen exactly one of P, Q is true.Show, using a tr uth table, that P ⊕ Q is equivalent to (P ∨ Q) ∧ ¬(P ∧ Q).2. Which of the following conditional sentences is true?(a) If triangles have three sides, then squares have four sides.(b) If a hexagon has six sides, then the moon is made of cheese.(c) If 7 + 6 = 14, then 5 + 5 = 10.(d) If 5 < 2, then 10 < 7.Write the converse and co ntrapositive of each of the conditional sentences listed above.3. Translate the following English sentence into a symbolic sentence with quantifiers (use the predicatefo ol(x,t) to denote the fact that you foo l person x at some time t): ”You can fool some of the peopleall the time and all of the people some of the time, but you cannot fool a ll of the people all of the time.(Interpret ’some’ as ’at least one’).Write an e nglish s entence that expresses the negation of the above se ntence.4. Prove that if a2is even then a is even. What style of proof did you use?5. Suppose P (n) is a predicate on the natural numbers, and suppose ∀k ∈ N P (k) =⇒ P (k + 2).For each of the following ass e rtions below, state whether (A) it must always hold, or (N) it can neverhold, or (C) it can hold but need not always.Give a very brief (one or two sentence) justification for your answers. T he domain of all quantifiers isthe natural numb e rs.(a) ∀n ≥ 0 P (n)(b) P (0) =⇒ ∀n P (n + 2)(c) P (0) =⇒ ∀n P (n + 1)(d) ∀n ¬P (n)(e) (∀n ≤ 10 P(n)) ∧(∀n > 10 ¬P(n))(f) (∀n ≤ 10 ¬P (n)) ∧ (∀n > 10 P (n))1(g) P (0) ∧ P (1) =⇒ ∀n P (n)(h) P (n) =⇒ [∃m > n P (m)](i) ¬P (m) ∨ ¬P (m + 1) ∨(∀n ≥ m P (n))6. (a) Prove by induction thatQni=2(1 −1/i) = 1/n.(b) Prove that 13+ 23+ 33+ ··· + n3= (1 + 2 + 3 + ··· + n)2for all integers n > 0.(c) Tower of Brahma T his g ame is also known as the Towers of Hanoi or the End of the World Puzzle.It was invented by the French mathematician, Edouard Lucas, in 1883. Accompanying the puzzleis a story:In the great temple at Benares beneath the dome which marks the center of the world, rests abrass plate in which are fixed three diamond needles, ea ch a cubit high and as thick as the bodyof a bee. On one of these needles, at the creation, God placed sixty-four disks of pure gold, thelargest disk resting on the brass plate and the others getting smaller and smaller up to the topone. This is the Tower of Brahma. Day and Night unceasingly, the priests transfer the disksfrom one diamond needle to another acco rding to the fixe d and immutable laws of Brahma, whichrequire that the priest on duty must not move more than one disk at a time and that he mustplace this disk on a needle so that there is no smaller disk below it. When all the sixty-four disksshall have been thus trans ferred from the needle on which at the creation God plac e d them toone of the other needles, tower, temple and Brahmins alike will c rumble into dust, and with athunderclap the world will vanish.Prove by induction the exact number of moves required to carry out this task in gener al, if thereare n disks on the original needle. Assuming that the priests can move a disk each second, roughlyhow many centuries does the prophecy predict befor e the destruction of the World?7. Proofs to Grade Assign a gra de of A (excellent) if the claim and pr oof are correct, F (failure) if theclaim is incorrect, if the main idea in the proof is incorrect, or if most of the statements in it areincorrect. Assign a grade of C (par tial credit) for a proo f that is largely correct, but contains one ortwo incorrect statements or justifications. Whenever a proof is incorrect, explain your grade. Say whatis incorrect and why.(a) Suppose m is an integerClaim: If m2is odd then m is odd.Proof: Assume m is odd. Then m = 2k + 1 for some integer k. Therefore m2= (2k + 1)2=4k2+ 4k + 1 = 2(2k2+ 2k) + 1, which is odd. Therefore if m2is odd, then m is odd.(b) Suppose m is an integerClaim: If m2is odd then m is odd.Proof: Assume that m2is not odd. Then m2is even, and m2= 2k for some integer k. Thus 2 kis a perfect square; that is,√2k is an integer. If√2k is odd, then√2k = 2n + 1 for some integern, which means m2= 2k = (2n + 1)2= 4n2+ 4n + 1 = 2(2n2+ 2n) + 1. Thus m2is odd, contraryto our assumption. Therefore√2k = m must be even. Thus if m2is not odd, then m is not odd.Hence if m2is odd, then m is odd.(c) Supp ose t is a real number .Claim: If t is irrational, then 5t is irrational.Proof: Suppose 5t is rational. Then 5t = p/q wher e p and q are integers and q 6= 0. Thereforet = p/5q where p and 5 q are integers and 5q 6= 0, so t is rational. Therefore if t is irrational, then5t is irrational.2(d) Suppose x and y are integers.Claim: If x and y ar e even, then x + y is even.Proof: Suppose x and y are even but x + y is odd. Then, for some integer k, x + y = 2k + 1.Therefore x + y + (−2)k = 1. The left side of the equation is even because it is the sum of evennumbers. However the right side, 1, is odd. Since and even cannot equal an odd, we have acontradiction. Therefore x + y is even. ♠(e) Claim: For every n ∈ N, n2+ n is odd. Proof: The number n = 1 is odd. Suppose k ∈ N andk2+ k is odd. Then,(k + 1)2+ (k + 1) = k2+ 2k + 1 + k + 1 = (k2+ k) + (2k + 2)is the sum of an odd and an even integer. Therefore, (k + 1)2+ (k + 1) is odd. By the Principleof Mathematical Induction, the property that n2+ n is odd is true for all na tur al numbers n.
View Full Document
Unlocking...