Discrete structures ch 1 sets PDF

Preview

Summary

an introduction to discrete structures which you learn about sets and the elements of what make up a set and attributes of a set...

Description

Discrete structures = Chapter 1.1 set and subsets. 

A set is a collection of objects



Objects are various types such as titles of books, rational numbers



Objects in a set are elements



A set can contain elements with different varieties



A set is defined by indicating



A roster notation definition of a set is a list of elements enclosed in curly braces with individual elements separated by commas o Ex) A = {2,4,6,10} o The order is unimportant o Repeating an element does not change the set

More notations related to sets 

∈ is used to show that an element is an a set o Ex) 2 ∈ A



∉ shows that the element is not in a set o Ex) 5 ∉ A



Lower case will be used to represent elements in a set



Upper case will be used to represent variable detonating sets

Common mathematical sets 

N = represents a set of natural numbers which include all integers greater than or equal to 0 o Ex) 0,1,2



Z = set of all integers o



Ex) -2, -1,0, 1,2

Q = set of rational numbers which includes all real numbers that are expressed as a/b , where a and b are integers and b ≠ 0. o Ex) 0, ½, 5.23, -5.3



R is the set of real numbers o Ex) = 0, 1/2, 5.23, -5/3, π,

Universal set o The universal set is represented by the variable U, which is a set that contains all elements mentioned o Sets are represented usually with the Venn diagrams o A rectangle represents the universal set o Oval shapes represent sets within U o An element drawn inside the rectangle indicate it is inside the set o If every element in a set (EX) A) is in another set then that set is a subset of another and represented as A ⊆ B. if not the case then it is shown as A ⊈ B. o If A ⊆ B and an in element of B is not in the set of A then A is a proper subset of B and shown as A ⊂ B.

Discrete structures chapter 1.2 Notes: Set of sets 

The elements of set can be a set themselves



Ex) A = {{ 1, 2 }, ∅, { 1, 2, 3 }, { 1 } }



Set A has 4 elements = {1, 2 }, ∅, { 1, 2, 3 }, and { 1 }.



The empty set is not the same as {∅ }



{ ∅ } is one since it has only one element which is an empty set

The power sets 

The power set of a set is shown as P(A) and is the set of all subsets of A.



The cardinality of the power set of A is 2n, or |P(A)|=2n.



Ex) A = { 1, 2, 3 } = P(A) = { ∅, { 1 }, { 2 }, { 3 }, { 1, 2 }, { 1, 3 }, { 2, 3 }, { 1, 2, 3 } }

Chapter 1.3 Union and intersection 

The intersection of two sets is represented with the symbol ∩ o Ex) A ∩ B o It is read as A intersect b



For example A and B can share two elements and the intersection is represented as = A ∩ B = {e, f}.



Intersection can also apply to infinite sets o Ex) A ∩ B = {x ∈ Z: x is an integer multiple of 6}

The set union operation 

The union of 2 sets is shown as A ∪ B and read as A union B



It is the set of all elements that are elements of A or B



Set operations can be combined to define even more sets



For example A ∪ ( B ∩ C ) = means that the union of the set A and set B ∩ C



Using parentheses is important because ( A ∪ B ) ∩ C is different from the set A ∪ ( B ∩ C ).

Chapter 1.4 = More set operations

Set difference and symmetric difference 

The differences between two sets A and B is shown as A –B



This describes the set of elements in A but not in B



Ex) A - B = {a, b, c}.



The symmetric difference between two sets is shown as A ⊕ B,



The symmetric difference is the set of elements that are a member of exactly one of A and b but not both



an alternative of the symmetric difference operation is = A ⊕ B = ( A - B ) ∪ ( B - A )

The set complement operation 

The complement of a set A is shown as “A” with a horizontal line on top



The complement of a set is the set of all elements in U that are not elements of A



An alternative definition is U - A.

Chapter 1.5 Cartesian products 

An ordered pair of items is written as (x,y).



Using parentheses () shows that the order is significant unlike with {}, the order doesn't matter



For example (x,y) does not equal (y ,x) unless x = y



The Cartesian product of A and B is represented as A x B, is the set of all in which the first entry is in A and the second entry is in B



Cartesian product: A x B = { (a, b) : a ∈ A and b ∈ B }



If A and B are finite sets, then |A x B| = |A|⋅|B|.



An ordered list of three items is called an ordered triple and is shown as (x,y,z)



The Cartesian of a set A can be represented as A × A or A2



Or in other words = Ak

Strings 

If A is a set of symbols or characters, the elements in An can be written without punctuation



Ex) if A = {x,y} the set A2 would be {xx, xy , yx, yy}



A sequence of characters is known as a string



A set of characters used in a string is called the alphabet



The length of a string is the number of characters in a string



A binary string is a string with an alphabet of {0,1}



The input and output of every program is described by a binary string



Every program is stored in computers as binary strings



An empty string with a length of 0 is represented by the symbol λ

Chapter 1.6 Partitions 

Two sets A and B are disjoint if their intersection is empty = (A ∩ B = ∅)



A partition of a non-empty set A is a collection of non-empty subsets of A given that each element of A is in exactly one of the subsets...