Quiz 11 - Answer Key - Discrete Structures | CMSC 250, Quizzes of Discrete Structures and Graph Theory

Download Quiz 11 - Answer Key - Discrete Structures | CMSC 250 and more Quizzes Discrete Structures and Graph Theory in PDF only on Docsity! CMSC 250 Quiz #11 ANSWERS Wednesday, Nov. 13, 2002 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 quiz is 30, and you will have exactly 15 minutes to complete this quiz. You may not use calculators, textbooks or any other aids during this quiz. 1. [12 pnts.] Prove or give a counter example to the following. For all sets A, B and C. If A ⊆ B and B ∩ C = ∅, then A ∩ C = ∅. Let A,B and C be generic particulars in {Sets} Assume A ⊆ B ∧ B ∩ C = ∅ CASE 1(A = ∅): A ∩ C = ∅ since any set intersected with the empty set is empty CASE 2 (A 6= ∅): Assume ∃x ∈ U, x ∈ A ∩ C Since x ∈ A ∩ C, x ∈ A ∧ x ∈ C by def. of set intersection x ∈ C by conjunctive simplification x ∈ A by conjunctive simplification Since x ∈ A and A ⊆ B, x ∈ B by def. of subset Since x ∈ C and x ∈ B, x ∈ B∩A by def. of set intersection This is a contradiction since B ∩ C = ∅ Our assumption was false, so it must be true that ∼ ∃x ∈ U, x ∈ A ∩ C ∀x ∈ Ux 6∈ A ∩ C by negation of quantified statement A ∩ C = ∅ by definition of empty set A ⊆ B ∧ B ∩ C = ∅ → A ∩ C = ∅ by closing the conditional world without a contradiction ∀A,B,C ∈ {Sets}, A ⊆ B ∧ B ∩ C = ∅ → A ∩ C = ∅ by generalizing from the generic particular Alternative Answer: Goal: A ∩ C = ∅ several rewrites of the goal: ∼ ∃x ∈ U, x ∈ A ∩ C by definition of empty set ∀x ∈ U, x 6∈ (A ∩ C) by negation of quantifier ∀x ∈ U, x ∈ (A ∩ C)′ by definition of complement ∀x ∈ U, x ∈ A′ ∨ x ∈ C ′ by DeMorgan’s ∀x ∈ U, x 6∈ A ∨ x 6∈ C by definition of complement Let A, B, and C be generic particulars in {sets} Assume A ⊆ B ∧ B ∩ C = ∅ A ⊆ B by conjunctive simplification ∀x ∈ U, x ∈ A → x ∈ B by def of subset B ∩ C = ∅ by conjunctive simplification ∼ ∃x ∈ U, x ∈ B ∧ x ∈ C by def. of empty set ∀x ∈ U,∼ (x ∈ B ∧ x ∈ C) by negation of quantification Let x be a generic particular in U x 6∈ B ∨ x 6∈ C by DeMorgan’s Law from above and applying the generic particular x ∈ A → x ∈ B from above applying the generic particular x 6∈ A ∨ x ∈ B by alternative rep of implecation (x 6∈ B ∨ x 6∈ C) ∧ (x 6∈ A ∨ x ∈ B) by conjunctive addition ((x 6∈ A ∨ x ∈ B) ∧ x 6∈ B) ∨ ((x 6∈ A ∨ x ∈ B) ∧ x 6∈ C) by distribution (x ∈ A ∧ x 6∈ B) ∨ (x ∈ B ∧ x 6∈ B) ∨ (x 6∈ A ∧ x 6∈ C) ∨ (x ∈ B ∧ x 6∈ C) by distribution (x ∈ A ∧ x 6∈ B) ∨ (x 6∈ A ∧ x 6∈ C) ∨ (x ∈ B ∧ x 6∈ C) by removing the contradition from the disjunction Call the three parts of this disjunction Case1, Case2 and Case3 and show that the conclusion must be true in all three cases Case1 (x 6∈ A ∧ x 6∈ B): x 6∈ A by conjunctive simplification x 6∈ A ∨ x 6∈ C by disjunctive Addition Case2 (x 6∈ A ∧ x 6∈ C): x 6∈ A by conjunctive simplification x 6∈ A ∨ x 6∈ C by disjunctive Addition Case3 (x ∈ B ∧ x 6∈ C): x 6∈ C by conjunctive simplification x 6∈ A ∨ x 6∈ C by disjunctive Addition Since x is a generic particular in all three cases, it must be true that ∀x ∈ U, x 6∈ A ∨ x 6∈ C by generalizing from the generic particular QED since this is what we said we had as our goal