COMP 1805 Discrete Functions

NO NEED FOR EXPLANATION!

I need this within 60 minutes please!

Q1)

Consider the following claim and attempted proof: Claim. Let 72 and 72 be integers. If nm72 is not divisible by 9, then neither ? nor m is divisible by 9. Proof. We will prove the claim by proving the equivalent contrapositive statement that if either 72 or 72 is divisible by 9 then nm2 is divisible by 9. Suppose either 12 or 172 is divisible by 9. We want to show that 72172 is divisible by 9. There are two cases based on whether it is 12 or 712 that is divisible by 9. case 1:9 n: Then n = 9c for some c E Z = nm = 9cm for some c E Z - nm = 96 for some l E Z # nm is divisible by 9 case 2:9 m: This is symmetric to the previous case (i.e. replace 7 by m and everything flows.) Since we know at least one of 12 or 72 is divisible by 9, our two cases are exhaustive. Therefore we have proven the claim of the contrapositive, and thus the original claim is true. O a) The proof is valid to prove the claim. O b) The proof is not valid but the claim is true. O c) The proof is not valid and the claim is not true.Consider the claim Claim. If x and y are rational numbers then x-y is also a rational number. A proof might look like this: (1) To prove the claim we will assume x and y are rational, then show that x-y is also rational. (2)= = nI ny = dy , where ne, dI, ny, dy E Z and de, dy * 0 - ny (3) = x- y = d, dy nr dy-ny-di (4)=0 - 4= di dy n (5)=*-y= dr dy where n E Z (6)=x- y =2 where d E Z and d * 0 (7) = - y is rational. For each of the steps below, match it to the reason that explains why that step is valid. (Remember that the reason attached to reason (x)-(x+1) would be the reason on line (x+1) in our column-format proof.)1. by substitution 2. by factoring 3. by cross-multiplying 4. by dividing both sides (4)-(5) 5. because the product and difference of integers is integer (6)-(7) 6. because the product of two non- zero integers is a non-zero integer (5)-(6) 7. because the difference of an integer and a non-integer is non- (2)-(3) integer, and the difference of two integers is integer (3)-(4) 8. because the two quantities are equal (1)-(2) 9. by the definition of an odd integer 10. by the definition of divisible by (or equivalently, because __ divides 11. by the definition of rational 12. by how we write numbersConsider the following proof that {8n : nez}n {21 : ne Z} C {24n : ne Z} Proof. (0) Suppose a E {8n : n e Z} n {21n : ne Z} (1) = a E {8n : ne Z} and a c {21n : ne Z} (2) = a = 86 and a = 21j, where 6, j E Z (3) 8/ = 21j (4) 21j is divisible by 8 (5) j is divisible by 8 (6) j = 8k where k E Z (7) a = 21(8k) (8) a = 24(7k), (9) a = 24n, where n E Z (10) a E {24n : n EZ} For each of the steps below, match it to the reason that explains why that step is valid. (Remember that the reason attached to reason (x)-(x+1) would be the reason on line (x+1) in our column-format proof.)1. by substitution 2. by factoring / refactoring 3. by multiplying (7)-(8) 4. by dividing both sides (3)-(4) 5. because the sum and product of integers is integer (8)-(9) 6. by the definition of (0)-(1) 7. by the definition of U (4)-(5) 8. by the definition of 9. by the definition of set (1)-(2) complement 10. since 8 and 21 have no common factors 11. by the definition of divisible by (or equivalently, because __ dividesConsider the following claim: Claim. There is no integer 2 such that [= mod 30 = 13] and [= mod 55 = 2]. (where we're using (2 mod n = ] to represent the proposition that 2 has a remainder of 7" when divided by n.) The following are steps to prove the result. Put them in the correct order such that each step follows from the previous and the result is a correct proof by contradiction of the result. 13 + 30c = 2 + 55d 5 | 11 z = 13 + 30cand > = 2 + 55d, for c, de Z 5(11d - 6c) = 11 Suppose Ez E Z such that > mod 30 = 13 and z mod 55 = 2. 19 (0.0001 points) Saved it! That's it, you're done! Way to keep up right through the end, that's