CSC 28 - Discrete Structures - Sets ----------------------------------- ** These notes are not intended as a replacement to lecture. There sole purpose ** is to remind me what I want to say, and remind you what I thought was ** important ** Sets are collections of objects. ** Membership is the basic operation on sets If x is in the set S, we write x \in S (and say x is an element of) If x is *not* in the set S, we write x \not\in S All other operations and relations are defined based on membership ** Sets can be specified in several ways... famous sets: Z = integers ..., -2, -1, 0, 1, 2, ... N = natural integers 1, 2, 3, 4, ... Q = rational numbers a/b, a and b are integers, b != 0 R = real numbers all numbers on the number line U = Universal set all values of potential interest (U depends on context) [empty set symbol] = empty set = set with nothing in it explicitly: { apple, banana } by pattern: { 0, 1, 2, ..., 9 } by characteristic: { x | a true/false statement about x } Everything is in this set that makes the statement true. { x | x is an even integer } = { ..., -4, -2, 0, 2, 4, ... } { x | x \in Z and x mod 2 = 0 } by characteristic with restriction: { x \in S | a true/false statement about x } = { x | x\in S and a true/false statement about x } { x \in Z | 0 < x < 5 } = {1,2,3,4} by characteristic with structure { expression about x | a true/false statement about x } essentially means { y | y=f(x) and a true/false statement about x } { 2x | x \in Z } = { ..., -4, -2, 0, 2, 4, ... } To evaluate: 1. Identify which variables make rhs true 2. Plug them into lhs. These values are in the set. Ex: Evaluate { 2x+1 | x \in Z } { x \in Z | sqrt(x) \in Z } Write in set notation by characteristic "Negative even integers" "even numbers that are multiples of 3" ** Free vs Bound variables We have seen two type of variables: free and bound. A variable is *free* if we must specify a value for it to evaluate the expression. Otherwise the variable is bound. Ex: { x | z in Z and x > c } c is free because we cannot evaluate the set until a value for c is supplied. x is bound because we do not need to supply a value for it to evaluate the set. Relations on sets ----------------- ** Subset Set A is a subset of B iff For every x \in A it is also the case that x \in B { 1, 4 } \subseteq { 1, 3, 4, 5 } { 3, 5 } \not\subseteq { 3, 7 } { } \subseteq { 2, 3 } // The empty set is a subset of every set ** Equality Sets A and B are equal iff For every x \in A it is also true that x \in B, and For every x \in B it is also true that x \in A By this definition, are { 1, 2, 3 } and { 2, 1, 3 } equal? How about { 1, 1, 2, 3, 3} and { 3, 2, 1 }? Yes! Because neither the order in which a set is written nor multiple occurrence change the membership of an element. Operations on sets ------------------ New sets can be made from old sets using set operators. Just like new numbers can be created from old numbers: 1+2=3. Let U be the universe, and let A and B be sets. A \union B = { x | x \in A or x \in B } A \intersect B = { x | x \in A and x \in B } A\B = { x | x \in A and x \not\in B } ** Often written A-B A^c = { x | x \notin A } ** Often A' or \overbar{A} Cardinality of set: |A| = number of elements distinct in A. Undefined if A is infinite. Product A x B = set of all ordered pairs ex: A = {1,2} B = {x,y} A x B = {(1,x), (2,x), (1,y), (2,y)} A x B = { (x,y) | x \in A and y \in B } Venn Diagrams ------------- Venn diagrams give a way to visually represent the relation between sets. [Draw general venn diagram for two sets] The diagram has four regions in which every object from U will be placed into one of the four regions: A\B, B\A, B \intersection A and (A \union B)^c Given some sets X = {a,b,c} Y = {b,c,d,e} coming from some universal context U = {a,b,c,d,e,f}, We can help visualize the relationship between elements and sets using a Venn diagram. [Draw diagram] This diagram has four regions, and each object from the universe belongs to exactly one of these regions - In X but not in Y: {a} - In Y but not in X: {d,e} - In both X and Y: {b,c} - In neither X nor Y: {f} Also, it helps visualize the basic operators shade in turn: intersection, union, subtraction, complement, symmetric diff Venn diagrams are useful for visualizing sets created with the operators: union, intersection, difference and complement. [Draw them all] For sets A and B, shade A in red and B in blue A \union B is the area shaded red or blue A \intersection B is the region shaded both red and blue A \ B is the area shaded red but not blue A^c is the area not shaded red. Bigger example: Find: S \union (T \intersection V) Find: (S \union T) \intersect (S \union V) The shaded areas are the same, so the two sets are equal S \union (T \intersection V) = (S \union T) \intersect (S \union V) Ex: Show A \ (A \intersect B) == A \ B Ex: Show (A \union B) \ C == (A \ C) \union (B \ C) Reasoning with Venn diagrams ---------------------------- Say 100 people receive a questionnaire with two questions (1) do you speak spanish, (2) do you speak chinese? Say 44 say 'yes' to chinese and 40 say 'yes' to neither. How many speak just spanish? What is n( A \union B )? n(A) + n(B) counts those objects in A \intersect B twice, so n( A \union B ) = n(A) + n(B) \ n(A \intersect B) ---- Application of sets: Functions ------------------------------ Sets give a way to document "types" in mathematical functions. A function from set X to set Y is a mapping from each element in X to elements in Y. The notation f: X --> Y tells us the function is named f, and it maps each element of X to an element in Y. X is the domain (or source) set of f. Y is the codomain (or target) set of f. f(x) is the value that x maps to under f. The key rules for f: X --> Y are: - f(x) is defined for every x \in X. - f(x) \in Y for every x \in X. Functions are usually defined using a formula f: Z --> Z // tells us f maps every integer into an integer f(x) = x^2 // tells us f(x) and x^2 are the same thing. Ex: Let g: R --> R be defined as g(x) = sqrt(x). Is g a function? No. Not every element of R maps to something in R. g(-1) \notin R. ---- Application of sets: Abstract Data Types ---------------------------------------- An abstract data type is a set of values and operations on those values. int is an ADT. When you declare a variable int x; You are declaring that x represents a value from int's set of values. x can be manipulated via +, *, /, -, ==. Set of values: { -2^31, -2^31+1, ..., 2^31-2, 2^31-1 } -- float x x is represented as 32 bits 1 sign bit s = 0 or 1 8 exponent bits e = (8 bits binary number) - 127 "excess 127 notation" 23 significand bits f = b10/2 + b11/4 + b12/8 + ... + b32/2^23 x = (-1)^s x (1+f) x 2^e <== a kind of binary scientific notation [Do example: 1 00100100 0101010000...000] What set of values can be represented? S = {0,1} E = {-127, -126, ..., 128} F = { 0/2^23, 1/2^23, 2/2^23, ..., (2^23-1)/2^23 } = { x/2^23 | x \in { 0, 1, 2, ..., 2^23 - 1 } } Values = { (-1)^s x (1+f) x 2^e | s \in S, f \in F, and e \in E } Operations: +, *, -, /, ==. This a the formal way that data types are modeled.