CMSC 175 Discrete MathematicsFinal Exam Study GuideThe final exam is comprehensive. It will include - writing definitions – you should know all definitions given in the lessons.- multiple choice questions – review the multiple choice questions in the unit tests.- problems to solve – review all problems in the homework assignments and theunit testsThe final exam will not include Boolean AlgebraA. LogicYou should know: truth tables, logical equivalences, de Morgan’s laws, conditionals (contrapositive, converse, inverse, disjunctive representation, negation of a conditional, representation of “unless” and “only if”, necessary and sufficient conditions), negation of quantifies expressions, arguments in propositional and predicate logic. See all problems in the homework assignments and Test 1Sample problem: Show how t can be derived:Premises:1. p V q2. q  r3. p  s  t4. ~r5. ~q  u  s6. Conclusion: tB. ProofsSee all proof problems in the homework assignments and tests. Sample problems:Choose and apply a method of proof or disproof (direct proof, proof by contraposition, proof by contradiction, disproof by counterexample, proof by mathematical induction) to prove or disprove the following statements:1. For all integers n, n2 is even if and only if n is even. Note: if and only if means: a) if n2 is even then n is even, b) if n is even then n2 is even2. For all integers k, k3 is odd if and only if k is odd3. 2 + 4 + 6 + …. + 2n = n(n+1) , for all n ≥14. 12 + 32 + 52 + …. + (2n-1) 2 = n(2n+1)(2n-1)/3, n ≥115. 1 + a + a2 + a3 + …. + a(n-1) = (an – 1)/(a-1), n ≥1, a  16. For all integers n, if n is even then (n-1)(n+1) is odd7. For all integers n, if (n+1)(n-1) is odd then n is even8. Consider the sequence a1, a2, …, an …. defined recursively: a1 = aan+1 = an + dProve that an = a1 + (n-1)d9. The square of any integer can be written in one of the following forms: 4k or 4k+110. Let n be an odd integer. Then n3 + 2n2 is also odd.11. 2 + 6 + 18 + …. + 2*3(n-1) = 3n – 1, n ≥112. 1*2 + 2*3 + 3*4 + …. + n(n+1) = n(n+1)(n+2)/313. 32n + 7 is divisible by 8 for all n ≥1 14. 11n – 6 is divisible by 5 for all n ≥115. 6*7n – 2*3n is divisible by 4 for all n ≥1Prove (A  B) – B = A – B(A – B)  B = A  BA – (A – B ) = A  BA – B = A  ~BA  (~A  B) = A  B(A – B)  (B – A) = (A  B) – (A  B)A – (A  B) = A ~B(A  B )  (A  ~B ) = A2C. RelationsSee all problems on relations in the homework assignments and in the tests. Sample problems:1. Let X = {1,2,3,4,…, 10}. Define a relation R on X x X : R = { ((a, b), (c, d)) | a + d = b + c}Show that R is an equivalence relation on X x X 2. Let X = {1,2,3,4,…, 10}. Define a relation R on X x X : R = { ((a, b), (c, d)) | ad = bc}Show that R is an equivalence relation on X x X3. Let R and S be two relations on a set A. Given the properties of R and S, determinethe corresponding properties of R S, R  S, ~R.D. Recurrence RelationsSolve the recurrence relations below with initial condition T(1) = 1:1. T(N) = T(N-1) + 12. T(N) = T(N-1) + N3. T(N) = 2T(N-1) + 14. T(N) = T(N/2) + 15. T(N) = T(N/2) + N6. T(N) = 2T(N/2) + 17. T(N) = 2T(N/2) + NE. CountingSee the problems in Lesson 21: Counting. Some more problems:1. A select committee of three persons is to be formed from five Conservative, three Labor and four Liberal Democrat members.a. In how many ways can the committee be formed?3b. In how many ways can the committee be formed if at least one Liberal Democrat must be included?c. In how many ways can the committee be formed if it cannot include both Labor and Conservative members?d. In how many ways can the committee be formed if it must include at least one conservative and one Labor member?2. A palindrome is a string that reads the same backwards as forwards. Consider palindromes of digits only (decimal digits 0, 1, 2, …, 9). How many different palindromes are there of length 6? Of length 7?3. How many 4-digit numbers less than 6000 (decimal number system) can be built using only odd digits? Assume that numbers do not start with leading zeros.4. How many 3-digit hexadecimal numbers are there less than F00, but greater than 999? How many of them end in 1?5. A computer password consists of 8 characters. Allowed characters are: Letters in the English alphabet - lower and upper case, decimal digits 0, 1, .., 9, and the underscore symbol. The first two characters must be lower case letters. a. How many different passwords are possible?b. How many passwords with no repeated characters are