Discrete Structures Spring 2014 MP Johnson Practice Exercises 1 Due: never, but you should do as many as possible! 1. Verify both de Morgan's rules. (This means: write out their truth tables, and observe that the two things each of de Morgan's rules say are equal indeed have the same truth value in all rows of the truth table.) 2. Translate the following sentences from English to predicate logic. The domain that you are working over is X, the set of people. You may use the functions T(x), meaning that "x has take CMP 232," A(x), meaning that "x has gotten an 'A' in CMP 232," S(x), meaning that "x is a senior," and E(x,y), meaning that "x and y are the same person." a) There are people who have taken CMP 232 and have gotten A's in CMP 232. b) All seniors who have taken CMP 232 got A's in CMP 232 c) Only seniors get A's in CMP 232. 3. The binary logical connectives ∧ (and), ∨ (or), and -> (implies) appear often in not only computer programs, but also everyday speech. In computer chip designs, however, it is considerably easier to construct these out of another operation, nand, which is simpler to represent in a circuit. Here is the truth table for nand: P | Q | P nand Q ------------------------ true | true | false true | false | true false | true | true false | false | true a) For each of the following expressions, find an equivalent expression using only nand and -(not), as well as grouping parentheses to specify the order in which the operations apply. You may use A, B, and the operators any number of times. i) A ∧ B ii) A ∨ B iii) A -> B b) It is actually possible to express each of the above using only nand, without needing to use -. Find an equivalent expression for (-A) using only nand and grouping parentheses. 4. Apply the proof of the irrationality of sqrt(2) to a) sqrt(3) and b) sqrt(4). If the proof breaks down, indicate precisely why. (Do not simply say that the result is false, if it is, explain at what step the attempted proof fails (if it does).) In all induction problems below, clearly state the statement P(n) to be proved, and clearly indicate the base case and the inductive assumption. 5. Prove by induction that for all nonnegative integers n: SUM_{i=1 to n} i^3 = ( n*(n+1)/2 )^2 (This is cumbersome but follows the usual pattern--you just have to be careful at each step. (Being neat helps!)) 6. Prove by induction that, for all integers n>=1 and real numbers r!=1, SUM_{i=0}^n r^i = (r^(n+1) - 1) / (r-1). 7. Prove by induction that, for all integers n>=4, 2^n < n!. 8. Prove by induction that, for all integers n>=6, 2^n > n^2. 9. Prove by induction that, for all integers n>=1, 2 divides n^2 + n. 10. Prove by induction that, for all integers n>=1, 3 divides n^3 + 2n. 11. Prove by strong induction that every amount of postage of 12 cents or more can be formed using just 4-cent and 5-cent stamps. 12. What amounts of money can be formed using just two-dollar bills and five-dollar bills? Prove you answer by strong induction. Exercises from the Rosen textbook (7th edition): Note that there are solutions to all odd-numbered exercises in the back of the book. Here I'm picking out particular exercises doing things we've learned how to do in class, or solving things of a similar flavor to things we've solved in class. For each of these, there are often multiple similar problems nearby it in the text. Practice solving as many of these as you need to become comfortable with them, comparing your solutions to those in the back. LOGIC: section 1.1 exercises: 9,11, 21,23, 29,30,31 section 1.3 exercises: 16,18,19 35 61 section 1.4 exercises: 5,7,9,10 13,14 23,25 33 section 1.5 exercises: 1,3,7,9 45 section 1.7 exercises: 1,2,3,6,11,13 review questions (page 111): 7 supplementary exercises (page 111): 1,21,30,31 SETS: section 2.1 exercises: 1 section 2.2 exercises: 1,3 52,53 section 2.4 exercises: 29,33 INDUCTION: section 5.1 exercises: 1,3,4,6 11,15 21 31,32,33,34 section 5.2 exercises: 3,4,14