Name printed Student ID Section or TA s name and time CMSC 250 Exam 1 ANSWERS Thurs Mar 11 2004 Write all answers legibly in the space provided The number of points possible for each question is indicated in square brackets the total number of points on the exam is 100 and you will have exactly 1 hour and 10 minutes to complete this exam You may not use calculators textbooks or any other aids during this exam If you need more space for any answer ask for an extra paper these extra papers must be turned in and you must mark so we can find the answer corresponding to a question The cheatsheet which is the last page of the exam can be ripped off and used during the exam and the back of the cheat sheet can 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 all rows columns indicate that it is not valid if it is valid mark all rows columns which prove that it is valid P1 A W R P2 A W P3 R A Therefore W R a 1 1 1 1 0 0 0 0 w 1 1 0 0 1 1 0 0 r 1 0 1 0 1 0 1 0 a w 1 1 0 0 1 1 1 1 a 0 0 0 0 1 1 1 1 NO w 0 0 1 1 0 0 1 1 r 0 1 0 1 0 1 0 1 a w r 1 1 0 1 1 1 1 1 a w 0 0 1 1 1 1 1 1 r a 1 1 1 1 0 1 0 1 w r 1 1 1 0 1 1 1 0 w r 0 0 0 1 0 0 0 1 Yes or No These statements do represent a valid argument Explain why you selected this answer for validity invalidity indicate how specific rows columns indicated this answer to you ANSWER The sixth row is a critical row because the 8th 9th and 10th columns which represent the 3 premises are all true This critical row though has a false conclusion as can be seen in the far right column of the 6th row This area is for grading purposes points lost per page Do not write below this line 1 2 3 4 5 6 7 1 8 9 10 Total 2 15 pnts Use only those rules given on the cheatsheet to prove that the following is a valid argument It is a Valid Argument you only need to prove that it is P1 P2 P3 P4 line 1 2 3 4 5 6 7 8 9 10 11 12 13 x D P x Q x R x x D P x M x x D R x Z x x D Z x P x Therefore x D Z x Q x M x Statement P a M a Z a P a M a R a Z a R a P a Q a P a Q a Q a Q a M a Z a Q a M a Z a Q a M a x D Z x Q x M x Reason inst Assume MP MP inst Disj Syll MT DeMorg and DN Disj Syll Conj Add CCW without contra def of Implication gen 2 Line s P2 2 P4 1 3 P3 5 2 P1 6 7 8 3 4 9 2 10 11 12 3 36 pnts For each of the following either give a complete proof to demonstrate that the statement is true or a counter example with validation to show that it is false For these problems you may use any of the formal definitions given in class or the textbook and you may use the fact that every integer is either even or odd but not both a For all integers a b m n greater than 1 if m n and a m b then a n b FALSE COUNTER EXAMPLE let a 3 and b 5 and m 2 and n 4 All of these values are integers that are greater than 1 It is true that m n since 2 4 and it is true that a m b since 3 2 5 because 2 5 3 which is really 2 2 So the antecedent is true But the consequent is false with these values since a 6 n b since 3 6 4 5 because 4 6 5 3 which is really saying 4 6 2 3 b n Z n Z odd n 3 2 12 n2 3 12 n2 1 PROOF Let n be arbitrary in Z Assume n Z odd and n 3 2 Since n 3 2 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 Assume k Z even 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 Z even by the definition of even This is a contradiction to the fact in the outer assumption that n Z odd 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 Z even must be false so we know for a fact that k Z odd by CCW with contradiction Since we know that k Z odd 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 addition Now we can close the outer conditional world by getting to the implication n Z odd n 3 2 12 n2 3 12 n2 1 Since n was arbitrary at the beginning we can universially generalize n Z n Z odd n 3 2 12 n2 3 12 n2 1 by generalizing from the Generic Particular 4 c a Z prime b Z 1 a b3 a b PROOF Let a Z prime and b Z 1 be arbitrary Since b Z 1 it can be prime factorized according to the Unique Prime Factorization Theorem n Z p1 p2 pn Z prime e1 e2 en Z such that b pe11 pe22 penn b3 pe11 pe22 penn 3 by cubing both sides 3en by carrying out the cube 1 3e2 b3 p3e 1 p2 pn Assume a b3 The prime a must therefore …
View Full Document
Unlocking...