1M. HauskrechtCS 441 Discrete mathematics for CSCS 441 Discrete Mathematics for CSLecture 8Milos [email protected] Sennott SquareSets and set operations: cont.Functions. M. HauskrechtCS 441 Discrete mathematics for CSSet• Definition: A set is a (unordered) collection of objects. These objects are sometimes called elements or members of the set. (Cantor's naive definition)• Examples:– Vowels in the English alphabetV = { a, e, i, o, u }– First seven prime numbers.X = { 2, 3, 5, 7, 11, 13, 17 }2M. HauskrechtCS 441 Discrete mathematics for CSSets - review• A subset of B:– A is a subset of B if all elements in A are also in B.• Proper subset: – A is a proper subset of B, if A is a subset of B and A  B• A power set:– The power set of A is a set of all subsets of AM. HauskrechtCS 441 Discrete mathematics for CSSets - review• Cardinality of a set A:– The number of elements of in the set• An n-tuple– An ordered collection of n elements• Cartesian product of A and B– A set of all pairs such that the first element is in A and the second in B3M. HauskrechtCS 441 Discrete mathematics for CSSet operationsSet union:• A = {1,2,3,6} B = { 2,4,6,9}• A B = { 1,2,3,4,6,9 }Set intersection:• A = {1,2,3,6} B = { 2, 4, 6, 9}• A B = { 2, 6 }Set difference: • A = {1,2,3,6} B = { 2, 4, 6, 9}• A - B = { 1, 3}• B – A = {4, 9}M. HauskrechtCS 441 Discrete mathematics for CSComplement of a setDefinition: Let U be the universal set: the set of all objects under the consideration.Definition: The complement of the set A, denoted by A, is the complement of A with respect to U.• Alternate: A = { x | x  A }Example: U={1,2,3,4,5,6,7,8} A ={1,3,5,7}• A = {2,4,6,8}UA4M. HauskrechtCS 441 Discrete mathematics for CSSet identitiesSet Identities (analogous to logical equivalences)• Identity– A  = A– A U = A• Domination– A U = U– A  = • Idempotent– A A = A– A A = AM. HauskrechtCS 441 Discrete mathematics for CSSet identities• Double complement–A = A• Commutative– A B = B A– A B = B A• Associative– A (B C) = (A B) C– A (B C) = (A B) C• Distributive– A (B C) = (A B) (A C)– A (B C) = (A B) (A C) 5M. HauskrechtCS 441 Discrete mathematics for CSSet identities• DeMorgan– (A B) = A B – (A B) = A B• Absorbtion Laws– A (A B) = A– A (A B) = A • Complement Laws–A A = U–A A =  M. HauskrechtCS 441 Discrete mathematics for CSSet identities• Set identities can be proved using membership tables. • List each combination of sets that an element can belong to. Then show that for each such a combination the element either belongs or does not belong to both sets in the identity. • Prove: (A B) = A BAB_A_B____A B_ _A B1100001001000110000011116M. HauskrechtCS 441 Discrete mathematics for CSGeneralized unions and itersectionsDefinition: The union of a collection of sets is the set that contains those elements that are members of at least one set in the collection.Example:•Let Ai= {1,2,...,i} i =1,2,...,n•}...{211nniiAAAA },...,2,1{1nAniiM. HauskrechtCS 441 Discrete mathematics for CSGeneralized unions and intersectionsDefinition: The intersection of a collection of sets is the set that contains those elements that are members of all sets in the collection.Example:•Let Ai= {1,2,...,i} i =1,2,...,n}...{211nniiAAAA }1{1niiA7M. HauskrechtCS 441 Discrete mathematics for CSComputer representation of sets• How to represent sets in the computer? • One solution: Data structures like a list• A better solution: • Assign a bit in a bit string to each element in the universal set and set the bit to 1 if the element is present otherwise use 0Example:All possible elements: U={1 2 3 4 5}• Assume A={2,5}– Computer representation: A = 01001• Assume B={1,5}– Computer representation: B = 10001M. HauskrechtCS 441 Discrete mathematics for CSComputer representation of setsExample:• A = 01001• B = 10001• The union is modeled with a bitwise or•A  B = 11001• The intersection is modeled with a bitwise and•A  B = 00001• The complement is modeled with a bitwise negation• A =101108M. HauskrechtCS 441 Discrete mathematics for CSFunctionsM. HauskrechtFunctions• Definition: Let A and B be two sets. A function from A to B, denoted f : A  B , is an assignment of exactly one element of B to each element of A. We write f(a) = b to denote the assignment of b to an element a of A by the function f. ABf: A  B9M. HauskrechtFunctions• Definition: Let A and B be two sets. A function from A to B, denoted f : A  B , is an assignment of exactly one element of B to each element of A. We write f(a) = b to denote the assignment of b to an element a of A by the function f. ABf: A  BNot allowed !!!M. HauskrechtRepresenting functionsRepresentations of functions:1. Explicitly state the assignments in between elements of the two sets2. Compactly by a formula. (using ‘standard’ functions)Example1:• Let A = {1,2,3} and B = {a,b,c}• Assume f is defined as:•1  c•2  a•3  c• Is f a function ? • Yes. since f(1)=c, f(2)=a, f(3)=c. each element of A is assigned an element from B10M. HauskrechtRepresenting functionsRepresentations of functions:1. Explicitly state the assignments in between elements of the two sets2. Compactly by a formula. (using ‘standard’ functions)Example 2:• Let A = {1,2,3} and B = {a,b,c}• Assume g is defined as•1  c•1  b•2  a•3  c• Is g a function? • No. g(1) = is assigned both c and b.M. HauskrechtRepresenting functionsRepresentations of functions:1. Explicitly state the assignments in between elements of the two sets2. Compactly by a formula. (using ‘standard’ functions)Example 3:• A = {0,1,2,3,4,5,6,7,8,9}, B = {0,1,2}• Define h: A  B as:• h(x) = x mod 3. • (the result is the remainder after the division by 3)• Assignments:•0  03  0•1 14  1•2  2 …11M. HauskrechtImportant setsDefinitions: Let f be a function from A to B. • We say that A is the domain of f and B is the codomain of f. • If f(a) = b, b is the image of a and a is a