tailieunhanh - INTRODUCTION TO COMPUTER SCIENCE - PART 2

INTRODUCTION TO COMPUTER SCIENCE HANDOUT #2. SET THEORY K5 & K6, Computer Science Department, Vaên Lang University Second semester -- Feb, 2002 Instructor: Traàn Ñöùc Quang Major themes: 1. The Set Data Model 2. Set Algebra 3. Implementation of Sets Reading: Sections , , , , and . THE SET DATA MODEL The set is the most fundamental concept in mathematics, and this is true in computer science. The term "set" is not defined explicitly; at a basic level, we can think of a set as a collection of objects. Basic notation • x ∈ S "element x is a member of. | INTRODUCTION TO COMPUTER SCIENCE HANDOUT 2. SET THEORY K5 K6 Computer Science Department Văn Lang University Second semester -- Feb 2002 Instructor Trăn Đức Quang Major themes 1. The Set Data Model 2. Set Algebra 3. Implementation of Sets Reading Sections and . THE SET DATA MODEL The set is the most fundamental concept in mathematics and this is true in computer science. The term set is not defined explicitly at a basic level we can think of a set as a collection of objects. Basic notation x e S element x is a member of set S S x1 x2 . . . xn elements X1 x2 . . . xn are members of set S each xi must be distinct sets contain unique objects in any order 0 the empty set the set with no members Defining Sets S 1 4 5 3 4 9 definition by enumeration T x x e S x is odd definition by abstraction. The latter means the set of elements x such that x is an odd element of S. set former notation general form We write x x e X and P x and read the set of elements x in X such that x has property P. 12 INTRODUCTION TO COMPUTER SCIENCE HANDOUT 2. SET THEORY Equality of Sets Two sets are equal if they have exactly the same members. This doesn t necessarily mean their representations must be identical. For example the set 1 2 is equal to the set 2 1 because they both have exactly the elements 1 and 2. SET ALGEBRA We introduce the three basic operations on sets. Union s È T the set containing the elements that are in s or T or both Intersection s n T the set containing the elements that are in both s and T Difference s T the set containing the elements that are in s but not in T A Venn Diagram illustrating these relationships See algebraic laws for those operations in the text page 343 . Subsets 1. s c T means s is a subset of T T is a superset of s s is contained in T T contains s 2. s Ì T means s is a proper subset of T T is a proper superset of s IMPLEMENTATION OF SETS 13 s is properly contained in T T properly contains s and is true if s c T and there