Set-Theory集合.ppt

1、Sets集合,演讲人：陈思维,2,Agenda 目录,Concepts 概念 Representations 表示 Properties of sets 性质 Operations 运算,3,Sets,A Set is an unordered collection of objects Members of a set are called elements How to determine a set Listing（列举法）: Example: A = 1,3,5,7 = 7, 5, 3, 1, 3 Description（描述法）： Example: B = x | x=2k+1, 0

2、 k 30,4,Set Theory,xA “x is an element of A” “x is a member of A” xA “x is not an element of A” A = x1, x2, , xn “A contains” Order of elements is meaningless. It does not matter how often the same element is listed.,5,Set Equality,Sets A and B are equal if and only if they contain exactly the same

3、elements. Examples: A = 9, 2, 7, -3, B = 7, 9, -3, 2 : A = B A = dog, cat, horse, B = cat, horse, squirrel, dog : A B A = dog, cat, horse, B = cat, horse, dog, dog : A = B,6,Some important sets,The empty set = has no elements. Universal set: the set of all elements about which we make assertions. Ex

4、amples: U = all natural numbers U = all real numbers U = x| x is a natural number and 1 x10,7,Subsets,A is a subset of B if every element of A is also contained in B (in symbols A B) Equality: A = B if A B and B A, i.e., A = B whenever x A, then x B, and whenever x B, then x A A is a proper subset o

5、f B if A B but B A,8,Subsets,A B “A is a subset of B” A B if every element of A is also an element of B. Examples: A = 3, 9, B = 5, 9, 1, 3, A B ? True A = 3, 3, 3, 9, B = 5, 9, 1, 3, A B ? True A = 1, 2, 3, B = 2, 3, 4, A B ? false,Venn diagrams,A Venn diagram provides a graphic view of sets Venn d

6、iagrams are useful in representing sets and set operations which can be easily and visually identified. Various sets are represented by circles inside a big rectangle representing the universal set.,9,10,Subsets,Useful rules: A = B (A B) (B A) (A B) (B C) A C (next Venn Diagram),11,Subsets,Useful ru

7、les: A for any set A A A for any set A Proper subsets（真子集）: A B “A is a proper subset of B” A B x (xA xB) x (xB xA),12,Power set,The power set of A is the set of all subsets of A, in symbols P(A), P(A)= X | X A Example: if A = 1, 2, 3, then P(A) = , 1, 2, 3, 1,2, 1,3, 2,3, 1,2,3 Theorem: If |A| = n,

8、 then |P(A)| = 2n.,13,The Power Set,P(A) “power set of A” P(A) = X | X A (contains all subsets of A) Examples: A = x, y, z P(A) = , x, y, z, x,y, x,z, y,z, x,y,z A = P(A) = Note: |A| = 0, |P(A)| = 1,14,Set Operations,Union: Elements in at least one of the two sets. AB = x | xA xB Example: A = a, b,

9、B = b, c, d AB = a, b, c, d,A,B,U,AB,Set Operations,Intersection: Elements in exactly one of the two sets. AB = x | xA xB Example: A = a, b, B = b, c, d AB = b,15,A,B,U,AB,Set Operations,Difference: Elements in first set but not second. Difference is also called the relative complement of B in A. A-

10、B = x | xA xB Example A = a, b, B = b, c, d A-B = a,16,A,B,U,A-B,Set Operations,Symmetric Difference: Elements in exactly one of the two sets. AB = x | xA xB = (AB) (AB) Example: A = a, b, B = b, c, d AB = a,c,d,17,A,B,U,AB,Set Operations,Complement(补集): Elements not in the set (unary operator). Ac

11、= x | x A Example: U = N, A = 250, 251, 252, Ac = 0, 1, 2, , 248, 249,Copyright 2007 by Xu Dezhi,18,A,U,Ac,19,Disjoint Sets,Disjoint: If A and B have no common elements, they are said to be disjoint. A B = ,A,B,U,20,Examples for set operations,If A=1, 4, 7, 10, B=1, 2, 3, 4, 5 A B =? A B =? A B =? B

12、 A =? A B =?,21,Example for set operations,If A=1, 4, 7, 10, B=1, 2, 3, 4, 5 A B = 1, 2, 3, 4, 5, 7, 10 A B = 1, 4 A B = 7, 10 B A = 2, 3, 5 A B = (AB) (AB) = 2, 3, 5, 7, 10,22,Properties of set operations (1),Theorem: Let U be a universal set, and A, B and C subsets of U. The following properties h

13、old: a) Associativity（结合律）: (A B) C = A (B C) (A B) C = A (B C) b) Commutativity（交换律）: A B = B A A B = B A,23,Properties of set operations (2),c) Distributive laws（分配律）: A(BC) = (AB)(AC) A(BC) = (AB)(AC) d) Identity laws（恒等律）: AU=A A = A e) Complement laws: AAc = U AAc = ,24,Properties of set operations (3),f) Idempotent laws(幂等律): AA = A AA = A g) Bound laws（支配律）: AU = U A = h) Absorption laws（吸收律）: A(AB) = A A(AB) = A,25,Properties of set operations (4),i) complementation laws（补集律）: (Ac)c = A j) De Morgans laws（德摩根定律）: (AB)c = AcBc (AB)c =