北京郵電大學--計算機學院--離散數(shù)學-2.2--set-operations

1、Set Operations（集合的運算）,,2,2024/3/18,College of Computer Science & Technology, BUPT,Set Operations,Propositional calculus （命題演算）and set theory（集合論） are both instances of an algebraic system （代數(shù)系統(tǒng)）called aBoolean A

2、lgebra（布爾代數(shù)）The operators in set theory are defined in terms of the corresponding operator in propositional calculusAs always there must be a universe U. All sets are assumed to be subsets of U,3,2024/3/18,College of

3、Computer Science & Technology, BUPT,Equal（相等）,Definition: Two sets A and B are equal, denoted A = B, iff"x[x ÎA« x ÎB].Note: By a previous logical equivalence we haveA = B iff "x[(x 

4、06;A® x ÎB) Ù (x ÎB® x ÎA)]orA = B iff A Í B and BÍ A,4,2024/3/18,College of Computer Science & Technology, BUPT,Definitions,The union（并集） of A and B, denoted AÈ B, is

5、 the set{x | xÎAÚxÎB}The intersection （交集）of A and B, denoted A Ç B, is the set{x | xÎAÙxÎB}Note: If the intersection is void, A and B are said to be disjoint（不相交）.The compl

6、ement （補集）of A, denoted A, is the set {x | Ø(xÎA)}Note: Alternative notation is Ac, and {x|xÏA}.,,5,2024/3/18,College of Computer Science & Technology, BUPT,The Addition principle （加法原理）

7、,Theorem If A and B are finite sets, then |A?B|=|A|+|B|-|A?B|It also called the inclusion-exclusion principle（容斥原理）,6,2024/3/18,College of Computer Science & Technology, BUPT,Example,Let A={a, b, c,

8、 d, e} and B={c, e, f, h, k, m}. Verify inclusion-exclusion principle.Solution:A? B={a, b, c, d, e, f, h, k, m} and A? B={ c, e}|A|= 5, |B|= 6, | A? B |= 9 and | A? B |= 2|A|+|B|-| A? B |= 9=| A? B |Q.E.D,7,2024/3/1

9、8,College of Computer Science & Technology, BUPT,The Addition principle for Disjoint Sets,|A?B|=|A|+|B|,8,2024/3/18,College of Computer Science & Technology, BUPT,Definitions,The difference（差） of A and B, or the

10、complement of B relative to A(, denoted A - B, is the setA Ç B Note: The (absolute) complement of A is U - A.The symmetric difference（對稱差） of A and B, denoted AÅB, is the set(A - B)È(B - A),,9,2024

11、/3/18,College of Computer Science & Technology, BUPT,Venn Diagrams,A useful geometric visualization tool (for 3 or less sets)The Universe U is the rectangular boxEach set is represented by a circle and its interior

12、All possible combinations of the sets must be represented,10,2024/3/18,College of Computer Science & Technology, BUPT,Venn Diagrams,Shade the appropriate region to represent the given set operation.,,,,,11,2024/3/18

13、,College of Computer Science & Technology, BUPT,Venn Diagrams,12,2024/3/18,College of Computer Science & Technology, BUPT,,,,13,2024/3/18,College of Computer Science & Technology, BUPT,,14,2024/3/18,College o

14、f Computer Science & Technology, BUPT,Examples,U = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}A= {1, 2, 3, 4, 5}, B = {4, 5, 6, 7, 8}. ThenAÈB = {1, 2, 3, 4, 5, 6, 7, 8}AÇB = {4, 5}A = {0, 6, 7, 8, 9, 10}B = {0

15、, 1, 2, 3, 9, 10}A - B = {1, 2, 3}B - A = {6, 7, 8}AÅB = {1, 2, 3, 6, 7, 8},,,15,2024/3/18,College of Computer Science & Technology, BUPT,Algebraic Properties of Set Operations（集合運算的基本定律）,Commutative properti

16、es（交換律）Associative properties（結(jié)合律）Distributive properties（分配律）,16,2024/3/18,College of Computer Science & Technology, BUPT,Algebraic Properties of Set Operations （集合運算的基本定律）,Idempotent properties（等冪律）Properties

17、 of the Complement,17,2024/3/18,College of Computer Science & Technology, BUPT,Algebraic Properties of Set Operations,Properties of a Universal SetProperties of the Empty Set,18,2024/3/18,College of Computer Scienc

18、e & Technology, BUPT,Proving Set Identities,To prove statements about sets, of the form E1 = E2 (where the Es are set expressions), here are three useful techniques:1. Prove E1 ? E2 and E2 ? E1 separately.2. Use s

19、et builder notation & logical equivalences.3. Use a membership table.,19,2024/3/18,College of Computer Science & Technology, BUPT,Method 1: Mutual subsets,Example: Show A?(B?C)=(A?B)?(A?C).Part 1: Show A?(B?C)

20、?(A?B)?(A?C).Assume x?A?(B?C), & show x?(A?B)?(A?C).We know that x?A, and either x?B or x?C.Case 1: x?B. Then x?A?B, so x?(A?B)?(A?C).Case 2: x?C. Then x?A?C , so x?(A?B)?(A?C).Therefore, x?(A?B)?(A?C).Therefo

21、re, A?(B?C)?(A?B)?(A?C).Part 2: Show (A?B)?(A?C) ? A?(B?C). …,20,2024/3/18,College of Computer Science & Technology, BUPT,Method 2: Use set builder notation,EXAMPLE 10 Proof that,21,2024/3/18,College of Computer Sc

22、ience & Technology, BUPT,Method 3: Membership Tables,Just like truth tables for propositional logic.Columns for different set expressions.Rows for all combinations of memberships in constituent sets.Use “1” to ind

23、icate membership in the derived set, “0” for non-membership.Prove equivalence with identical columns.,22,2024/3/18,College of Computer Science & Technology, BUPT,Membership Table Example,Prove (A?B)?B = A?B.,,,23,20

24、24/3/18,College of Computer Science & Technology, BUPT,Membership Table Exercise,Prove (A?B)?C = (A?C)?(B?C).,24,2024/3/18,College of Computer Science & Technology, BUPT,Generalized Unions & Intersections,Sin

25、ce union & intersection are commutative and associative, we can extend them from operating on ordered pairs of sets (A,B) to operating on sequences of sets (A1,…,An), or even on unordered sets of sets,X={A | P(A)}.,

26、25,2024/3/18,College of Computer Science & Technology, BUPT,Generalized Union,Binary union operator: A?Bn-ary union:A?A2?…?An :? ((…((A1? A2) ?…)? An)(grouping & order is irrelevant)“Big U” notation:Or for

27、infinite sets of sets:,26,2024/3/18,College of Computer Science & Technology, BUPT,Generalized Intersection,Binary intersection operator: A?Bn-ary intersection:A1?A2?…?An?((…((A1?A2)?…)?An)(grouping & order is

28、 irrelevant)“Big Arch” notation:Or for infinite sets of sets:,27,2024/3/18,College of Computer Science & Technology, BUPT,Notation,AÈBÈC= {x | xÎAÚxÎBÚxÎC}A1ÈA2È?An=A

29、ÇBÇC= {x | xÎAÙxÎBÙxÎC}A1ÇA2Ç?An=,28,2024/3/18,College of Computer Science & Technology, BUPT,Union and Intersection of Indexed Collections,Let A1,A2 ,..., An be an index

30、ed collection of sets.Union and intersection are associative (because 'and' and 'or' are) we have:Ai = A1È A2È...ÈAnandAi = A1 Ç A2 Ç...Ç An,29,2024/3/18,College of

31、 Computer Science & Technology, BUPT,Examples,LetAi = [i,¥),1 £ i < ¥thenAi = [1,¥)Ai = [n,¥),30,2024/3/18,College of Computer Science & Technology, BUPT,Representations,A fre

32、quent theme of this course will be methods of representing one discrete structure using another discrete structure of a different type. E.g., one can represent natural numbers asSets: 0:??, 1:?{0}, 2:?{0,1}, 3:?{0,1,2

33、}, …Bit strings: 0:?0, 1:?1, 2:?10, 3:?11, 4:?100, …,31,2024/3/18,College of Computer Science & Technology, BUPT,Representing Sets with Bit Strings,For an enumerable u.d. U with ordering x1, x2, …, represent a fin

34、ite set S?U as the finite bit string B=b1b2…bn where?i: xi?S ? (i<n ? bi=1).E.g. U=N, S={2,3,5,7,11}, B=001101010001.In this representation, the set operators“?”, “?”, “?” are implemented directly by bitwise OR, A

35、ND, NOT!,32,2024/3/18,College of Computer Science & Technology, BUPT,Computer representation of sets,Example 18Example 19Example 20,33,2024/3/18,College of Computer Science & Technology, BUPT,Review of 2.2,Oper