Discrete Mathematics - Practice Midterm (Solutions) K. Subramani LCSEE, West Virginia University, Morgantown, WV [email protected]} 1 Problems 1. Propositional Logic. Show that the following arguments are valid. (a) A0 ∧ (B → A) → B 0 . (b) (A ∧ B) → (A → B 0 )0 . Solution: (a) Consider the following proof sequence: (i) (ii) (iii) (iv) (v) (vi) B → A hypothesis. B 0 ∨ A (i), implication. A ∨ B 0 (ii), commutativity. A0 → B 0 (iii), implication. A0 hypothesis. B 0 (iv), (v), Modus Ponens. (b) We use an intuitive argument. Consider the following two cases: (i) A is true - In this case, the given argument boils down to B → B which is trivially true. (ii) A is false - In this case, the antecedent is false and hence the argument itself is true. 2 2. Predicate Logic. (a) Show that the argument (∀x)[P (x) ∨ Q(x)] → [[(∃x)P (x)]0 → (∀x)Q(x)] is valid. (b) Consider the verbal argument:Some plants are flowers. All flowers smell sweet. Therefore, some plants smell sweet. Is it valid? Solution: (a) Using the deduction method, we can rewrite the given argument as: [(∀x)[P (x) ∨ Q(x)] ∧ [(∃x)P (x)]0 ] → (∀x)Q(x) Consider the following proof sequence: (i) [(∃x)P (x)]0 hypothesis. (ii) P (a)0 (i), e.i. (iii) (∀x)[P (x) ∨ Q(x)] hypothesis. 1 (iv) (v) (vi) (vii) P (a) ∨ Q(a) (iii), u.i. P (a)0 ∨ Q(a) (iv), implication. Q(a) (ii), (v), Modus Ponens. (∀x)Q(x) u.g. The last step is justified, since Q(a) was not deduced from a hypothesis in which a is a free variable nor has Q(a) been deduced by existential instantiation from a formula in which a is a free variable. (b) Let P (x) ≡ “x is a plant”, F (x) ≡ “x is a flower” and S(x) ≡ “x smells sweet.” Accordingly, the verbal argument can be symbolized as follows: (∃x)[P (x) ∧ F (x)] ∧ (∀x)[F (x) → S(x)] → (∃x)[P (x) ∧ S(x)] Consider the following proof sequence: (i) (ii) (iii) (iv) (v) (vi) (vii) (viii) (ix) (∃x)[P (x) ∧ F (x)] hypothesis. P (a) ∧ F (a) (i), ei. (∀x)[F (x) → S(x)] hypothesis. F (a) → S(a) (iii), ui. F (a) (ii), simplification. S(a) (iv), (v) Modus Ponens. P (a) (ii), simplification. P (a) ∧ S(a) (vi), (vii), Conjunction. (∃x)[P (x) ∧ S(x)] (viii), eg. 2 3. Non-Inductive Proof. Prove the following two conjectures. Pn (a) Let A = n1 · i=1 xi . Is it necessarily true that at least one of the xi s is greater than or equal to A? (b) Prove that log2 5 is not rational. Solution: (a) Yes, it is necessarily Pn true. Assume the contrary and let xi < A, ∀i = 1, 2 . . . , n. Then, hence, A > n1 i=1 xi , thereby contradicting the hypothesis. Pn i=1 xi < n · A and (b) Assume that log2 5 is rational. Then, we can write log2 5 = pq , where p and q are integers, q 6= 0 and gcd(p, q) = 1. Observe that, log2 5 = p q ⇒5 = 2q ⇒ 5q = 2p p Since 2 | 2p , 2 must divide 5q . However, 5 is a prime number, therefore 2 must divide 5, which is a contradiction. 2 4. Inductive Proof. Prove that Pn 1 i=1 i2 < 2 − n1 , n ≥ 2. 2 Solution: BASIS : n = 2. LHS = = = < = = 2 X 1 2 i i=1 1 1 + 1 4 5 4 3 2 1 2− 2 RHS Thus the basis is proven. I NDUCTIVE S TEP : Assume that k+1 X i=1 1 i2 Pk 1 i=1 i2 = < = = = = < = = < 2 − k1 , for some k ≥ 2. Observe that, k X 1 1 + 2 i (k + 1)2 i=1 1 1 )+ , by inductive hypothesis k (k + 1)2 1 1 2−( − ) k (k + 1)2 (k + 1)2 − k 2−( ) k(k + 1)2 k 2 + 2k + 1 − k 2−( ) k(k + 1)2 k2 + k + 1 2−( ) k(k + 1)2 k2 + k 2−( ), subtracting a smaller number k(k + 1)2 k(k + 1) 2− k(k + 1)2 1 2− k+1 (2 − We have thus shown that, if the conjecture is true for any k ≥ 2, then it must also be true for (k + 1). Using the first principle of mathematical induction, we conclude that the presented conjecture is true for all n ≥ 2. 2 5. Recurrences. (a) Solve the recurrence: S(1) = 1 S(n) = S(n − 1) + n, n ≥ 2 (b) Show that [F (n + 1)]2 = [F (n)]2 + F (n − 1) · F (n + 2), ∀n ≥ 2. 3 Solution: (a) The given recurrence is a first-order, linear recurrence. The parameters of the recurrence are: k0 = 1, c = 1 and g(i) = i. As per the formula discussed in class, S(n) = 1n−1 · 1 + n X 1n−i · i i=2 = 1+ n X i i=2 = n X i i=1 = n · (n + 1) , as proved in class 2 (b) Observe that, [F (n + 1)]2 = [F (n) + F (n − 1)]2 , by definition = [F (n)]2 + [F (n − 1)]2 + 2 · F (n) · F (n − 1) = [F (n)]2 + F (n − 1) · [F (n − 1) + 2 · F (n)] = [F (n)]2 + F (n − 1) · [F (n − 1) + F (n) + F (n)] = [F (n)]2 + F (n − 1) · [F (n + 1) + F (n)], by definition = [F (n)]2 + F (n − 1) · F (n + 2), by definition 2 4

© Copyright 2017 ExploreDoc