MTH 207 Final, Fall 2011

Lebanese American University Fall 2011 Byblos Discrete Structure I Final Exam Name: Date: 25/01/2012 Duration: 2h 15 ID: Part I: Problems (70 pts) 1. [10 pts] Find a resolution proof and a formal proof for the following proposi- tional logic formula: {C −! (A _ D) ; ¬D −! (B _ ¬C) ; C ; ¬D} ` ¬(A −! ¬B) (Hint: For the formal proof, assume A −! ¬B and prove a contradiction) 1 2 2. [15 pts] Prove, by induction, the following: (a) 8n − 3n is divisible by 5 for all n 2 N. (b) n X k=1 k (k + 1)! = 1 − 1 (n + 1)!. (c) 52n+1 · 2n+2 + 3n+2 · 22n+1 is divisible by 19 for all n 2 N. 3 4 5 3. [10 pts] Solve using pigeonhole principle the following two independent ques- tions: (a) There are 25 students in a class. While doing a keyboarding test, each student made fewer than 12 mistakes. Show that at least 3 students made the same number of mistakes. (b) Five points are chosen from inside an equilateral triangle of side 2. Prove that two points must be within a distance of 1 of each other. 6 4. [10 pts] We consider the following program (input is n and output is r): if n > 0 then begin r := 0; i := 1; while i <= n do begin r := r + 2*i; i := i + 1; end; end; (a) Find the output of the program for n = 1, n = 2, n = 3 and n = 4. 7 (b) Which function computes the program? 8 5. [13 pts] Verify, in the following cases, if the binary relation R defined over the set X is reflexive, symmetric and transitive. If R is an equivalence relation then find the set of classes ⇡R. (a) X = Z and x R y i↵ x + y is even. (b) X = Z and x R y i↵ xy is even 9 10 6. [12 pts] Find for the following two ordered sets the maximal, minimal, greatest and least elements (if any): (a) X = {2, 6, 12, 18, 24, 36} and the order is x R y i↵ x divides y. (b) X = {[0, 1], [−1, 2], [−1, 3], [2, 3], [−1, 5]} and the order is x R y i↵ x ✓ y. (c) X = {2, 3, 4, 8, 9, 16} and the order is x R y i↵ 9 n 2 N⇤ such that y = xn. 11