# Cot 3100h spring Homework #3 Solutions 1 this is what I meant to be question a

Yüklə 25.61 Kb.
 tarix 20.04.2016 ölçüsü 25.61 Kb.
 COT 3100H Spring Homework #3 Solutions 1) THIS IS WHAT I MEANT TO BE QUESTION A... a) (B  C)  (B – A)  (C – A). We must prove the following: (B – A)  (C – A). This means, for an arbitrarily chosen element x, we must show the following: if x(B – A), then x(C – A). We will prove this using the direct proof method. 1) Assume x(B – A). 2) By definition of set difference, this means xB and xA. 3) Since B  C and xB, by definition of subset, we know that xC. 4) By definition of set difference since, xC and xA, x(A – C), as desired. REAL QUESTION A a) ((A  B)  (B  C))  (A  C). This statement is true. This means, we must prove that A  C. We must show that for an arbitrary xA that xC and that there exists some element y such that yA but yC. First, let's consider an arbitrary xA. Since A  B, by the definition of proper subset we can conclude that xB. Similarly, using the given information again, since B  C, we can conclude that xC. This proves the first part of what we need to show. Now, since we know that A  B, in follows that there exists an element y such that yA but yB. But, if yB, since B  C, it follows that yC. Thus, we have shown that there exists an element y such that yA but yC as desired. REAL QUESTION B b) ((A  B)  (A  C))  ((B  C)  (C  B)). This statement is false as well. Consider the following counter example: A = , B = {1}, C={2} Here clearly, (A  B)  (A  C) since the empty set is a proper subset of all non-empty sets. But both of (B  C) and (C  B) are false here. I MEANT FOR THIS TO BE THE QUESTION C... c) ((A  C)  (B  C))  A  B  C. This statement is false. Consider the following counter example: A = {1}, B = {2}, C={1,2}. Clearly we have that (A  C)  (B  C). But, in this example we have that A  B = C, thus it is false that A  B  C. REAL QUESTION C AND D - ANSWERS ARE IN QUESTION #3 because I goofed up!!! 2) Let A, B and C be arbitrary sets taken from the set of positive integers. (a) Show that the sets and are equal, using any method. (b) Prove or disprove: If C  B, then . (a) In this solutions, set laws will be used to show the equivalence: , using DeMorgan's Law , using Law of Double Complement , using Associative Law Another solution uses a Membership Table. (b) We must prove the following: Thus, We must prove that if an arbitrary element , then . We split our work into two cases: (1) , and (2) . Case (1): , by definition of set difference, we have that , and . Since the latter is true, and since C  B, it follows that . Hence, , based on the definition of set complement. Also, since , it naturally follows that , by definition of set union. Since and , by definition of set intersection, we conclude that . Case (2): , by definition of set difference, we have that , and . Hence, , based on the definition of set complement. Also, since , it naturally follows that , by definition of set union. Since and , by definition of set intersection, we conclude that . 3) Let A, B and C be any three sets. Prove or disprove the following propositions: a) If A B C, then either AB or AC. b) (A  C) (C B) =  c) Power(A)Power(B)  Power (A B) d) If AB, then AxCBxC. e) If AxCBxC, then AB. a) If A B C, then either AB or AC. It can be disproved by the following counter example. Take A = {1, 2}, B = {1, 3} and C = {2, 4}. Then A  B  C = {1, 2, 3, 4}, but A is neither a subset of B , nor a subset of C. b) (A  C) (C B) =  Proof by contradiction. Assume that (A  C) (C B)   to show that it results to contradiction. (A  C) (C B)   means that there exists some x  (A  C) (C B). By the definition of intersection we can imply, that there exists x for which the following proposition is true: p = (x A  C)  (x C  B). Using the definition of set difference we can rewrite p as : p = (x A) (x C)  (x C) (x  B). But (x C)  (x C) = False, so p = (x A) [(x C)  (x C)] (x  B) = (x A) False (x  B) = False. So, the assumption that intersection (A  C) (C B)   is not empty results to contradiction which proves that this assumption is false, i.e. intersection is empty. Other solution is to use the membership table. c) Power(A)Power(B)  Power (A B) This is false. To disprove take a counterexample: A = {1, 2}, B = {2, 3}, Power(A) = {, {1}, {2}, {1, 2}}, Power(B) = {, {2}, {3}, {2, 3}}, Power(A)  Power(B) = {{1}, {1, 2}}, A B = {1}, Power (A B )={, {1}}. Thus, {1, 2} Power(A)  Power(B), but {1, 2} Power (A B ), so the proposition Power(A)Power(B)  Power (A B) is disproved. d) If AB, then AxCBxC. This is true. We must show the following: AxCBxC. This means, for an arbitrarily chosen ordered pair (x,y) we must show the following: if (x,y) AxC, then (x,y)BxC. We use direct proof. 1) Assume (x,y) AxC. 2) If this is the case, then we have that xA and yC. 3) We are given that AB and xA. By definition of subset, it follows that xB. 4) By definition of Cartesian Product, we can conclude that (x,y)BxC, as desired. e) If AxCBxC, then AB. This is false, let A = {1}, B = {2}, and C = {}. In this case AxC = {}, BxC = {}, but A is NOT a subset of B.

Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azrefs.org 2016
rəhbərliyinə müraciət