Discrete Math Concepts and Set Operations Explained

Slide Note

Explore key concepts in discrete math, including set operations, Venn diagrams, and proofs of set equality. Learn about unions, intersections, differences, complements, and more through visual aids and examples. Enhance your understanding of elements, subsets, and set relationships with comprehensive explanations and illustrations.

ykal Follow

Uploaded on Oct 09, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript

Clicker frequency: CA CSE 20 DISCRETE MATH Prof. Shachar Lovett http://cseweb.ucsd.edu/classes/wi15/cse20-a/

Todays topics Set operations Vs Venn diagrams Sets equality and how to prove it Power set, Cartesian product

Set operations JS p. 47 Union: ? ? = {?:? ? ? ?} Intersection: ? ? = {?:? ? ? ?} Difference: ?\? = ? ??= {? ?: ? ?} ?? = {? ?: ? ?} Complement: (important to know the universe U!) Empty set:

Vs Which one of the following is true? A. 1 {1,2,3} B. 1 {1,2,3} C. {1} {1,2,3} D. {1} 1,2,3 E. None/other/more than one

Vs Recall: x A: x is an element in the set A A B: A is a subset of B (all elements of A are also elements of B) Examples: 1 {1,2,3} {5,7} {5,6,7} Elements can also be set! {1,3} {{2}, 4, {1,3}} We can have set of sets of sets of sets

Vs Which one of the following is true? A. 1 {{1},{2},{3}} B. 1 {{1},{2},{3}} C. {1} {{1},{2},{3}} D. {1} {{1},{2},{3}} E. None/other/more than one

Vs Which one of the following is true? A. { ,{ },{{ }}} B. { ,{ },{{ }}} C. { } { ,{ },{{ }}} D. { } { ,{ },{{ }}} E. None/other/more than one

Venn diagrams An useful way to understand sets intersection & union Generic Venn diagram for 3 sets: U B A C Describes all possible 8=23 combinations for whether an element is in A or not; in B or not; in C or not

Venn diagrams We will use it to prove the following theorem: For any 3 sets A, B, C ?\? ?\? ?\? = U B A C

Venn diagrams Which area(s) represent ?\? ? A. 1,2 B. 2,5,8 C. 1,2,3,4 D. 3,4 E. Other/none/more U B A C

Venn diagrams Which area(s) represent ?\? ? A. 1,4 B. 2,3 C. 8,7 D. 5,6 E. Other/none/more U B A C

Venn diagrams Goal: prove ?\? ?\? ?\? = Which area(s) represent ?\? ? A: 2,3,5,6 B: 3,4,6,7 A\B: 2,5 U B A A\C: 2,3 B\C: 3,4 A\B: 2,5 There is no number that appears in all three lists, so the intersection is empty set C

Algebraic proof of ?\? ?\? ?\? = ?\? ?\? ?\? = (? ??) (? ??) (? ??) (by definition of set difference) = ? ?? ? ?? ? ?? (by associative law removing parentheses) = ? ?? ?? ? (?? ?) (by commutative law, and by associative law adding parentheses) = ? ?? ?? ? (by complement law: any set intersect its complement is empty) = (any set intersect the empty set is the empty set)

Set equality Given sets X and Y X = Y means: ?, ? ? ? ? X Y means: ?, ? ? ? ? Y X means: ?, ? ? ? ? Recall: ? ? is equivalent to ? ? (? ?) So: X=Y is equivalent to X Y and Y X

Proving set equality One way to prove X=Y is in two steps Step 1: prove X Y That is, ?, ? ? ? ? Step 2: prove Y X That is, ?, ? ? ? ?

Proving set equality: simple example X = {n N: n is even} Y = {n N: n+1 is odd} Claim: X=Y Proof that X Y: If n X, then n is even, hence n+1 is odd, hence n+1 Y Proof that Y X: If n Y, then n+1 is odd, hence n is odd, hence n X

Proving set equality: another example Claim: (Ac)c = A Recall definitions: ? ? Equivalently: ? ?? ? ?? ? ? Proof that A (Ac)c: If x A, then x Ac, hence x (Ac)c Proof that (Ac)c A: If x (Ac)c, then x Ac, hence x A

Power Set JS p. 45 Set A P(A) = set of all subsets of A = {?:? ?} What is P({1,2})? A. {1, 2, {1,2}} B. {{1}, {2}, {1,2}, } C. {1, 2, {1,2}, {2,1}} D. None/other/more than one

Power Set Which one of the following is always true? A. A P(A) B. A P(A) C. {A} P(A) D. {A} P(A) E. None/other/more than one

Cartesian product JS p. 48 ? ? = { ?,? :? ?,? ?} What is {1,2} x {1,2,3} ? A. {1, 2, 3} B. {(1,1), (2,2), ( ,3)} C. {(1,1),(1,2),(1,3),(2,1),(2,2),(2,3)} D. {(1),(1,2),(1,3),(2),(2,3)} E. None/other/more than one