CMSC 250 Quiz #10 Answers Wed., April 7, 2004Write all answers legibly in the space provided. The number of points possible for each question is indicatedin square brackets – the total number of p oints on the quiz is 30, and you will have exactly 15 minutes tocomplete this quiz. You may not use calculators, textbooks or any other aids during this quiz.1. [12 pnts.] Assuming Σ is the set {a, b, c} do each of the following:a. Give the value of Σ2.Σ2= {aa, ab, ac, ba, bb, bc, ca, cb, cc}b. Give the power set of Σ.P (Σ) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}c. Assuming A = {1, 2} - give A × Σ.A × Σ = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}2. [8 pnts.] Give the lists of elements in each of the sets (A and B) assuming A − B = {1, 5, 7, 8},B − A = {2, 10} and A ∩ B = {3, 6, 9}.A = {1, 5, 7, 8, 3, 6, 9}B = {2, 10, 3, 6, 9}3. [10 pnts.] Prove or give a counter example to the following. For all sets A, B and C. If A ⊆ B andB ∩ C = ∅, then A ∩ C = ∅.Suppose A, B and C are arbitrary sets.———————-DIRECT METHOD —————Assume A ⊆ B and B ∩ C = ∅and an arbitrary x such that x ∈ ASince x ∈ A and A ⊆ B, by the definition of subset x ∈ B.Since B ∩ C = ∅, B and C are disjoint sets.Since B and C are disjoint sets and x ∈ B, then x 6∈ C.This means that ∀x ∈ U, x ∈ A → x 6∈ C.By the definition of complement, this is the same as: ∀x ∈ U, x ∈ A → x ∈ CcBy the definition of subset, this means: A ⊆ CcTherefore every member of A would need to be in Cc.Since C and Ccare disjoint, A and C would also be disjoint.Therefore, A ∩ C = ∅. QED—————- USING CONTRADICTION ——————Assume x ∈ (A ∩ C)This means that x ∈ A and x ∈ C by the definition of intersection.x ∈ A by conjunctive simplification.x ∈ C by conjunctive simplification.Since x ∈ A and A ⊆ B, then x ∈ B.x ∈ B ∧ x ∈ C by conjunctive addition.x ∈ (B ∩ C) by definition of intersection.contradiction because x can’t be in B ∩ C if B ∩ C = ∅.Therefore our assumption that x ∈ (A ∩ C) must be false.Since x was arbitrarily chosen, it must be true that ∀x ∈ U, x 6∈ (A ∩ C).Therefore A ∩ C =
View Full Document
Unlocking...