离散数学英文DMAv7-2.1-6.ppt

1、Module #2:The Theory of SetsRosen 7th ed., 2.1-2.22 Basic Structures: Sets, Functions, Sequences , Sums and Matrices2.1 Sets 2.2 Set Operations 2.3 Functions 2.4 Sequences and Summations 2.5 Cardinality of Sets 2.6 MatricesIntroduction to Set Theory集合论 (2.1) A set is a new type of structure, represe

2、nting an unordered collection (group, plurality) of zero or more distinct (different) objects. Set theory deals with operations between, relations among, and statements about sets. Sets are ubiquitous in computer software systems. All of mathematics can be defined in terms of some form of set theory

3、 (using predicate logic).Nave set theory Basic premise: Any collection or class of objects (elements) that we can describe (by any means whatsoever) constitutes a set. But, the resulting theory turns out to be logically inconsistent! This means, there exist nave set theory propositions p such that y

4、ou can prove that both p and p follow logically from the axioms of the theory! The conjunction of the axioms is a contradiction! This theory is fundamentally uninteresting, because any possible statement in it can be (very trivially) “proved” by contradiction! More sophisticated set theories fix thi

5、s problem.Basic notations for sets For sets, well use variables S, T, U, We can denote a set S in writing by listing all of its elements in curly braces: a, b, c is the set of whatever 3 objects are denoted by a, b, c. Set builder notation: For any proposition P(x) over any universe of discourse, x|

6、P(x) is the set of all x such that P(x).Basic properties of sets Sets are inherently unordered:No matter what objects a, b, and c denote, a, b, c = a, c, b = b, a, c =b, c, a = c, a, b = c, b, a. All elements are distinct (unequal);multiple listings make no difference!If a=b, then a, b, c = a, c = b

7、, c = a, a, b, a, b, c, c, c, c. This set contains (at most) 2 elements!Definition of Set Equality集合相等 Two sets are declared to be equal if and only if they contain exactly the same elements. In particular, it does not matter how the set is defined or denoted. For example: The set 1, 2, 3, 4 = x | x

8、 is an integer where x0 and x0 and 25Infinite Sets无限集 Conceptually, sets may be infinite (i.e., not finite, without end, unending). Symbols for some special infinite sets:N = 0, 1, 2, The Natural numbers.Z = , -2, -1, 0, 1, 2, The Zntegers.R = The “Real” numbers, such as 374.182847192949818191728194

9、3125 “Blackboard Bold” or double-struck font (,) is also often used for these special number sets. Infinite sets come in different sizes!Venn Diagrams文氏图John Venn1834-1923Basic Set Relations:Member of成员 xS (“x is in S”) is the proposition that object x is an lement or member of set S. e.g. 3N, “a”x | x is a letter of the alphabetCan define set equality in terms of relation:S,T: S=T (x: xS xT)“Two sets are equal iff they have all the same members.” xS : (xS) “x is not in S”