SOLUTIONS TO THE EXAM FOR G51MCS, 2011-2012 Problem 1 consists in exercises that are identical to or small variations on ones that have been treated during the lectures. Each of problems 2-5 is divided into 3 parts. Part (a) is bookwork: a trivial exercise to test if the student studied the lecture notes; Part (b) is an exercise of moderate difficulty similar to some that have been treated in class and in the lecture notes; Part (c) is a more challenging exercise that requires some more advanced skills from the student. QUESTION 1 (a) (i) B => ~C (ii) ~A /\ C => ~B (iii) NO (iv) A B (B\/A) ~(B\/A) A/\~(B\/A) t t t f f t f t f f f t t f f f f f t f (v) NO (b) (i) 5 (ii) 2 (iii) 1 (iv) false (v) false (c) (i) true (ii) false (iii) true (iv) false (v) true (d) (i) daisy,cyclamen,tulip,orchid (all of B) (ii) {}, {tulip}, {daisy}, {tulip,daisy} (iii) true (iv) false (v) true (e) (i) 0 (ii) 8 (iii) 10 (iv) 4960 (v) 4 QUESTION 2 (a) A B C A=>B (A=>B)=>C A\/B ~C A\/B\/~C ((A=>B)=>C)=>A\/B\/~C t t t t t t f t t t t f t f t t t t t f t f t t f t t t f f f t t t t t f t t t t t f t t f t f t f t t t t f f t t t f f f f f f f t f f t t t NOT a tautology (b) 1. ~A /\ B 2. A \/ ~B -------- 3. ~A /\E,1 4. B /\E,1 ------------- 5. A Assumption 6. False ~E,3,5 ------------- 7. ~B Assumption 8. False ~E,7,4 ------------- 9. False \/E,2,5-6,7-8 (c) (C=>B)=>A = ~(~C\/B)\/A Definition of implication, twice = (~~C/\~B)\/A Second De Morgan law = A\/(~~C/\~B) Commutativity of disjunction = (A\/~~C)/\(A\/~B) Distributivity of disj. over conj. = (~~C\/A)/\(~B\/A) Comm. of disj., twice = (~C=>A)/\(B=>A) Definition of implication, twice QUESTION 3 (a) strangeFun(1) = 2 strangeFun(2) = 6 strangeFun(3) = 12 strangeFun(4) = 20 (b) Base case, P(0) : strangeFun(0) = 0 by definition 0*(0+1) = 0 by arithmetic so P(0) is trivially true Inductive step Induction hypothesis: Assume P(k) is true strangeFun(k) = k*(k+1) We must prove P(k+1) : strangeFun(k+1) = (k+1)*(k+2) In fact we have: strangeFun(k+1) = 2*(k+1)^2 - strangeFun(k) by definition of strangeFun = 2*(k+1)^2 - k*(k+1) by induction hypothesis = (k+1)(2*(k+1) - k) common factor (k+1) = (k+1)(k+2) arithmetic Since we proved P(0) and P(k)=>P(k+1) for every k, by induction P(n) is true for all n. (c) The two coefficients are 5 and -3. QUESTION 4 (a) (A\(BuC)) u (B\(CuA)) u (C\(AuB)) (b) Numbers in A: 5, 7, 11, 13, 19, 23 Numbers in B: 7, 11, 12, 13, 15, 19, 22 Numbers in C: 11, 22, 33 The numbers in the set from part (a) are: 5, 12, 15, 23, 33 (c) The values of the function are: f(0)=1, f(1)=0, f(2)=3, f(3)=0 (i) It is not a bijection. (ii) f has the same value on 1 and 3 (and never produces the value 2) QUESTION 5 (a) f(0) = 2 0^2 = 0 f(1) = 4 1^2 = 1 f(2) = 3 2^2 = 4 f(3) = 1 3^2 = 4 f(4) = 0 4^2 = 1 (b) The function f is bijective. Its inverse "finv" has the values: finv(0)=4 finv(1)=3 finv(2)=0 finv(3)=2 finv(4)=1 (c) f has a single orbit: 0 -> 2 -> 3 -> 1 -> 4 -> 0. Therefore the least n such that f^n=id is 5.