DOC PREVIEW
GSU CSC 2510 - ch03s1

This preview shows page 1-2-3-4-5-6 out of 19 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Set, Combinatorics, Probability & Number TheorySet theorySlide 3Set Theory ExamplesSet Theory BasicsOpen and closed intervalRelationship between SetsSlide 8ExerciseSet of SetsSet operationsBinary or unary operationsOperations on SetsDisjoint, Universal and Difference SetsClass ExerciseCartesian ProductBasic Set IdentitiesMore set identitiesSlide 19Set, Combinatorics, Probability & Number TheoryMathematical Structures for Computer ScienceChapter 3Copyright © 2006 W.H. Freeman & Co. MSCS Slides Set, Combinatorics, Probability & Number TheorySection 3.1 Sets 2Set theorySets: Powerful tool in computer science to solve real world problems.The concepts of set and element have no clear-cut definition, except as they relate to each other. A set is a collection of elements or objects, and an element is a member of a set. Traditionally, sets are described by capital letters, and elements by lower case letters.The symbol  means “belongs to” and is used to represent the fact that an element belongs to a particular set. Hence, aA means that element a belongs to set A.bA implies that b is not an element of A.Braces {} are used to indicate a set.A = {2, 4, 6, 8, 10} 3A and 2ASection 3.1 Sets 3Set theoryOrdering is not imposed on the set elements and listing elements twice or more is redundant.Two sets are equal if and only if they contain the same elements.Hence, A = B means (x)[(x  A  x  B) Λ (x  B  x  A)] Finite and infinite set: described by number of elements in a setMembers of infinite sets cannot be listed, but a pattern for listing elements could be indicated. e.g. S = {x  x is a positive even integer} or using predicate notation.S = {x  P(x)} means (x)[(x  S  P(x)) Λ (P(x) x  S)] where P is the unary predicate.Hence, every element of S has the property P and everything that has a property P is an element of S.Section 3.1 Sets 4Set Theory ExamplesDescribe each of the following sets by listing the elements:{x | x is a month with exactly thirty days}{April, June, September, November}{x | x is an integer and 4 < x < 9}{5, 6, 7, 8}What is the predicate for each of the following sets?{1, 4, 9, 16}{x | x is one of the first four perfect squares}{2, 3, 5, 7, 11, 13, 17, ….}{x | x is a prime number}Section 3.1 Sets 5Set Theory BasicsA set that has no members is called a null or empty set and is represented by  or {}.Note that  is different from {}. The latter is a set with 1 element, which is the empty set.Some notations used for convenience of defining setsN = set of all nonnegative integers (note that 0  N)Z = set of all integersQ = set of all rational numbersR = set of all real numbersC = set of all complex numbersUsing the above notations and predicate symbols, one can describe sets quite easilyA = {x | (y)(y {0,1,2} and x = y2}Hence, A = {0,1, 4}A = {x | x  N and (y)(y  {2, 3, 4, 5}  x  y)}B = {x | (y)(z)(y  {1,2} and z  {2,3} and x = z – y) }Section 3.1 Sets 6Open and closed interval{x  R | -2 < x < 3}Denotes the set containing all real numbers between -2 and 3. This is an open interval, meaning that the endpoints -2 and 3 are not included. By all real numbers, we mean everything such as 1.05, -3/4, and every other real number within that interval. {x  R | -2  x  3}Similar set but on a closed interval It includes all the numbers in the open interval described above, plus the endpoints.Section 3.1 Sets 7Relationship between SetsSay S is the set of all people, M is the set of all male humans, and C is the set of all computer science students.M and C are both subsets of S, because all elements of M and C are also elements of S.M is not a subset of C, however, since there are elements of M that are not in C (specifically, all males who are not studying computer science). For sets S and M, M is a subset of S if, and only if, every element in M is also an element of S.Symbolically: M  S  (x), if x  M, then x  S.If M  S and M  S, then there is at least one element of S that is not an element of M, then M is a proper subset of S.Symbolically, denoted by M  SSection 3.1 Sets 8Relationship between SetsA superset is the opposite of subset. If M is a subset of S, then S is a superset of M. Symbolically, denoted S  M. Likewise, if M is a proper subset of S, then S is a proper superset of M.Symbolically, denoted S  M.Cardinality of a set is simply the number of elements within the set.The cardinality of S is denoted by |S|. By the above definition of subset, it is clear that set M must have fewer members than S, which yields the following symbolic representation: M  S  |M| < |S|Section 3.1 Sets 9ExerciseA = {x | x  N and x  5}  {5, 6, 7, 8, 9, …… }B = {10, 12, 16, 20}C = {x | (y)(y  N and x = 2y)}  {0, 2, 4, 6, 8, 10, …….} What statements are true?B  C  B  A A  C 26  C {11, 12, 13}  A  {11, 12, 13}  C{12}  B {12}  B {x | x  N and x < 20} B  5  A{}  B   A Section 3.1 Sets 10Set of SetsFor the following sets, prove A  B.A = { x | x  R such that x2 – 4x + 3 = 0}A = {1, 3}B = { x | x  N and 1 x  4}B = {1, 2, 3, 4}All elements of A exist in B, hence A  B.From every set, many subsets can be generated. A set whose elements are all such subsets is called the power set.For a set S, (S) is termed as the power set.For a set S = {1, 2, 3} ; (S) = { ,{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}For a set with n elements, the power set has 2n elements.Section 3.1 Sets 11Set operationsBinary and unary operatorsBinary acts on two elements, say x-y or y-x.Unary acts on a single element, say negation of an element x is –x.Example: +, - and * are all binary operators on Z.An ordered pair of elements is written as (x,y) and is different from (y,x).Two ordered pairs (a,b) and (c,d) are equal if and only if a = c and b = d.If S = {2,3}, the ordered pairs of this set are (2,2), (2,3), (3,2), (3,3).Binary operation (represented by ) on a set defined as follows: If for every ordered pair (x,y) of elements of S, x  y exists, and is unique, and is a


View Full Document

GSU CSC 2510 - ch03s1

Documents in this Course
ch02s2

ch02s2

5 pages

ch04s2

ch04s2

8 pages

ch01s6

ch01s6

10 pages

ch01s1

ch01s1

21 pages

ch02s4

ch02s4

10 pages

ch08s2

ch08s2

21 pages

ch08s3

ch08s3

15 pages

ch07s3

ch07s3

21 pages

ch04s3

ch04s3

23 pages

ch06s3

ch06s3

16 pages

ch01s3

ch01s3

15 pages

ch03s4

ch03s4

11 pages

ch03s6

ch03s6

6 pages

ch03s5

ch03s5

9 pages

ch06s2

ch06s2

9 pages

ch07s1

ch07s1

11 pages

ch02s1

ch02s1

14 pages

ch08s1

ch08s1

15 pages

ch02s5

ch02s5

9 pages

ch01s4

ch01s4

13 pages

Load more
Download ch03s1
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view ch03s1 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view ch03s1 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?