Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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 7.2, 7.3, 7.4, 7.7, and 7.10. 2.1 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 7.2 7.3 7.4 7.7 and 7.10. 2.1 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. 2.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 2.3 IMPLEMENTATION OF SETS 13 s is properly contained in T T properly contains s and is true if s c T and there
