Set Operations PDF

1.2 Operations on Sets  Operation on Sets An operation on a set is where two sets are combined to produce a third  Union A  B = {x | x  A or x  B} Example: Let A = {a, b, c, e, f} and B = {b, d, r, s} A  B = {a, b, c, d, e, f, r, s} Venn diagram ...

1.2 Operations on Sets  Operation on Sets An operation on a set is where two sets are combined to produce a third  Union A  B = {x | x  A or x  B} Example: Let A = {a, b, c, e, f} and B = {b, d, r, s} A  B = {a, b, c, d, e, f, r, s} Venn diagram  Intersection A  B = {x | x  A and x  B} Example: Let A = {a, b, c, e, f}, B = {b, e, f, r, s}, and C = {a, t, u, v}. A  B = {b, e, f} A  C = {a} BC={} Venn diagram  Disjoint Sets Disjoint sets are sets where the intersection results in the empty set Not disjoint Disjoint Unions and Intersections Across Multiple Sets Both intersection and union can be performed on multiple sets – A  B  C = {x | x  A or x  B or x  C} – A  B  C = {x | x  A and x  B and x  C} – Example: A = {1, 2, 3, 4, 5, 7}, B = {1, 3, 8, 9}, and C = {1, 3, 6, 8}. A  B  C = {1, 2, 3, 4, 5, 6, 7, 8, 9} A  B  C = {1, 3}  Complement The complement of A (with respect to the universal set U) – all elements of the universal set U that are not a member of A. Denoted A Example: If A = {x | x is an integer and x < 4} and U = Z, then A = {x | x is an integer and x > 4} Venn diagram  Complement “With Respect to…” The complement of B with respect to A – all elements belonging to A, but not to B. It’s as if U is in the complement is replaced with A. Denoted A – B = {x | x  A and x  B} Example: Assume A = {a, b, c} and B = {b, c, d, e} A – B = {a} B – A = {d, e} Venn diagram B–A A–B  Symmetric difference Symmetric difference – If A and B are two sets, the symmetric difference is the set of elements belonging to A or B, but not both A and B. Denoted A  B = {x | (x  A and x  B) or (x  B and x  A)} A  B = (A – B)  (B – A) Venn diagram Symmetric difference Algebraic Properties of Set Operations Commutative properties AB=BA AB=BA Associative properties A  (B  C) = (A  B)  C A  (B  C) = (A  B)  C Distributive properties A  (B  C) = (A  B)  (A  C) A  (B  C) = (A  B)  (A  C)  More Algebraic Properties of Set Operations Idempotent properties AA=A AA=A Properties of the complement (A) = A AA=U AA= =U U= A  B = A  B -- De Morgan’s law A  B = A  B -- De Morgan’s law  More Algebraic Properties of Set Operations Properties of a Universal Set AU=U A U =A Properties of the Empty Set A   = A or A  { } = A A   =  or A  { } = { }  The Addition Principle The Addition Principle associates the cardinality of sets with the cardinality of their union If A and B are finite sets, then |A  B| = |A| + |B| – |A  B| Let’s use a Venn diagram to prove this: AB 1 2 1 The Roman Numerals indicate how many times each segment is included for the expression |A| + |B| Therefore, we need to remove one |A  B| since it is counted twice.  Addition Principle Example Let A = {a, b, c, d, e} and B = {c, e, f, h, k, m} |A| = 5, |B| = 6, and |A  B| = |{c, e}| = 2 |A  B| = |{a, b, c, d, e, f, h, k, m}| |A  B| = 9 = 5 + 6 – 2 If A  B = , i.e., A and B are disjoint sets, then the |A  B| term drops out leaving |A| + |B|