Name (printed):Student ID #:Section # (or TA’s:name and time)CMSC 250 Exam #1 ANSWERS Thurs., Mar. 11, 2004Write all answers legibly in the space provided. The number of points p os sible for each question is indicatedin square brackets – the total number of points on the exam is 100, and you will have exactly 1 hour and10 minutes to complete this exam. You may not use calculators, textbooks or any other aids during thisexam. If you need more space for any answer, ask for an extra paper - thes e extra papers must be turnedin and you must mark so we can find the answer corresponding to a question. The “cheatsheet” (which isthe last page of the exam) can be ripped off and used during the exam, and the back of the cheat sheetcan be used for scratch paper.1. [15 pnts.] Use a COMPLETE truth table to determine if the following argument is valid or not.Use 1 for “true” and 0 for “false” to create the complete truth table. If it is not valid, indicate allrows/columns indicate that it is not valid; if it is valid, mark all rows/columns which prove that it isvalid.P1 (A → W )∨ ∼ RP2 ∼ A∨ ∼ WP3 R → ATherefore ∼ (W ∨ R)a w r a → w ∼ a ∼ w ∼ r (a → w)∨ ∼ r ∼ a∨ ∼ w r → a w ∨ r ∼ (w ∨ r)1 1 1 1 0 0 0 1 0 1 1 01 1 0 1 0 0 1 1 0 1 1 01 0 1 0 0 1 0 0 1 1 1 01 0 0 0 0 1 1 1 1 1 0 10 1 1 1 1 0 0 1 1 0 1 00 1 0 1 1 0 1 1 1 1 1 00 0 1 1 1 1 0 1 1 0 1 00 0 0 1 1 1 1 1 1 1 0 1NO (Yes or No) These statements do represent a valid argument.Explain why you selected this answer for validity/invalidity - indicate how specific rows/columnsindicated this answer to you.ANSWER: The sixth row is a “critical row because the 8th, 9th and 10th columns (which representthe 3 premises) are all true. This critical row, though, has a false conclusion as can be seen in thefar right column of the 6th row.**** T his area is for grading purposes (points lost per page)- Do not write below this line ****1 2 3 4 5 6 7 8 9 10 Total12. [15 pnts.] Use only those rules given on the “cheatsheet” to prove that the following is a validargument. It is a Valid Argument - you only need to prove that it is.P1 ∀x ∈ D, (∼ P (x) ∧ Q(x)) → R(x)P2 ∃x ∈ D, ∼ P (x) → M (x)P3 ∀x ∈ D, ∼ R(x) ∨ Z(x)P4 ∀x ∈ D, ∼ Z(x) →∼ P (x)Therefore ∃x ∈ D, Z(x) ∨ (∼ Q(x) ∧ M(x))line Statement Reason Line #s1 ∼ P (a) → M (a) ∃ inst. P22 | ∼ Z(a) Assume3 | ∼ P (a) ∀ MP 2,P44 |M(a) MP 1,35 | ∼ R(a) ∨ Z(a) ∀ inst. P36 | ∼ R(a) Disj. Syll 5,27 | ∼ (∼ P (a) ∧ Q(a)) ∀ MT P1,68 |P (a)∨ ∼ Q(a) DeMorg and DN 79 | ∼ Q(a) Disj Syll 8,310 | ∼ Q(a) ∧ M (a) Conj. Add 4,911 ∼ Z(a) → (∼ Q(a) ∧ M(a)) CCW without contra 2-1012 Z(a) ∨ (∼ Q(a) ∧ M (a)) def of Implication 1113 ∃x ∈ D, Z(x) ∨ (∼ Q(x) ∧ M (x)) ∃ gen. 1223. [36 pnts.]For each of the following either give a complete proof to demonstrate that the statement istrue or a counter-example with validation to show that it is false. For these problems you may useany of the formal definitions given in class or the textbook, and you may use the fact that “everyinteger is either even or odd but not both”.a. For all integers (a,b,m,n) greater than 1, if m|n and a ≡mb, then a ≡nb.FALSECOUNTER-EXAMPLE:let a = 3 and b = 5 and m = 2 and n = 4All of these values are integers that are greater than 1It is true that m|n since 2|4and it is true that a ≡mb since 3 ≡25 (because 2|(5 − 3) which is really 2|2).So the antecedent is true.But the consequent is false with these values sincea 6≡nb since 3 6≡45 (because 4 6 |(5 − 3) which is really saying 4 6 |2.3b.∀n ∈ Z, [n ∈ Zodd∧ (n ≡32)] → [12|(n2+ 3) ∨ 12|(n2− 1)]PROOF:Let n be arbitrary in Z| Ass ume n ∈ Zoddand n ≡32| Since n ≡32, 3|(n − 2) by the def. of equiv. in a mod| Then we know that ∃k ∈ Z, n − 2 = 3k by the def. of divides| and then n = 3k + 2 by algebra| Ass ume k ∈ Zeven| ∃s ∈ Z, k = 2s by definition of even| n = 3(2s) + 2 by substitution| n = 2(3s + 1) by algebra| Since 3s + 1 ∈ Z by closure of Z in add and mult| n ∈ Zevenby the definition of even| This is a contradiction to the fact in the outer assumption that n ∈ Zodd| since the previous page says we can assume that any integer is either| even or odd but not both| Since we have found a contradiction, our inner assumption| (that k ∈ Zeven), must be false| so we know for a fact that k ∈ Zoddby CCW w ith contradiction| Since we know that k ∈ Zodd| ∃m ∈ Z, k = 2m + 1 by definition of odd.| n = 3(2m + 1) + 2 by substitution| n = 6m + 5 by algebra| n2= 36m2+ 60m + 25 by squaring both sides| n2− 1 = 36m2+ 60m + 24 by subtracting one from both sides| n2− 1 = 12(3m2+ 5m + 2) by factorring out a 12| Since 3m2+ 5m + 2 ∈ Z by closure of Z in addition and multiplication,| 12|(n2− 1) by definition of divides| 12|(n2+ 3) ∨ 12|(n2− 1) by disjunctive additionNow we can close the outer conditional world by getting to the implication:(n ∈ Zodd∧ n ≡32) → (12|(n2+ 3) ∨ 12|(n2− 1))Since n was arbitrary at the beginning, we can universially generalize:∀n ∈ Z, (n ∈ Zodd∧ n ≡32) → (12|(n2+ 3) ∨ 12|(n2− 1)) by generalizing from the GenericParticular4c.∀a ∈ Zprime, ∀b ∈ Z>1, a|b3→ a|bPROOF:Let a ∈ Zprimeand b ∈ Z>1be arbitrary.Since b ∈ Z>1, it can be prime factorized according to the Unique Prime Factorization Theorem.∃n ∈ Z+, ∃p1, p2, ...pn∈ Zprime, ∃e1, e2, ...en∈ Z+such that b = pe11pe22...pennb3= (pe11pe22...penn)3by cubing both sidesb3= p3e11p3e22...p3ennby carrying out the cubeAssume a|b3The prime, a, must therefore be in the list of primes presented on the right above, in otherwords ∃i ∈ Z+, 1 ≤ i ≤ n ∧ pi= a.Therefore we can factor it out (taking all of the a’s in the righthand side to the front, in otherwords b3= a3ei(b31) where a 6 |b31.Since b3= a3eib31where all of the elements are …
View Full Document
Unlocking...