北京邮电大学计算机学院离散数学22-Setoperationsppt课件.ppt

《北京邮电大学计算机学院离散数学22-Setoperationsppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、SetOperations（集合的运算）22021/8/31CollegeofComputerScience&Technology,BUPTSetOperationsPropositionalcalculus（命题演算）andsettheory（集合论）arebothinstancesofanalgebraicsystem（代数系统）calledaBooleanAlgebra（布尔代数）Theoperatorsinsettheoryaredefinedintermsofthecorrespondingoperatorinpropositionalcal

2、culusAsalwaystheremustbeauniverseU.AllsetsareassumedtobesubsetsofU32021/8/31CollegeofComputerScience&Technology,BUPTEqual（相等）Definition:TwosetsAandBareequal,denotedA=B,iff"x[xÎA«xÎB].Note:ByapreviouslogicalequivalencewehaveA=Biff"x[(xÎA®xÎB)Ù(xÎB®xÎA)]orA=BiffAÍBandBÍA42021/8/31

3、CollegeofComputerScience&Technology,BUPTDefinitionsTheunion（并集）ofAandB,denotedAÈB,istheset{x

4、xÎAÚxÎB}Theintersection（交集）ofAandB,denotedAÇB,istheset{x

5、xÎAÙxÎB}Note:Iftheintersectionisvoid,AandBaresaidtobedisjoint（不相交）.Thecomplement（补集）ofA,denotedA,istheset{x

6、Ø(xÎA)}Note:Alternati

7、venotationisAc,and{x

8、xÏA}.52021/8/31CollegeofComputerScience&Technology,BUPTTheAdditionprinciple（加法原理）TheoremIfAandBarefinitesets,then

9、AB

10、=

11、A

12、+

13、B

14、-

15、AB

16、Italsocalledtheinclusion-exclusionprinciple（容斥原理）62021/8/31CollegeofComputerScience&Technology,BUPTExampleLetA={a,b,c,d,e}andB

17、={c,e,f,h,k,m}.Verifyinclusion-exclusionprinciple.Solution:AB={a,b,c,d,e,f,h,k,m}andAB={c,e}

18、A

19、=5,

20、B

21、=6,

22、AB

23、=9and

24、AB

25、=2

26、A

27、+

28、B

29、-

30、AB

31、=9=

32、AB

33、Q.E.D72021/8/31CollegeofComputerScience&Technology,BUPTTheAdditionprincipleforDisjointSets

34、AB

35、=

36、A

37、+

38、B

39、82021/8/31CollegeofComputerScien

40、ce&Technology,BUPTDefinitionsThedifference（差）ofAandB,orthecomplementofBrelativetoA(,denotedA-B,isthesetAÇBNote:The(absolute)complementofAisU-A.Thesymmetricdifference（对称差）ofAandB,denotedAÅB,istheset(A-B)È(B-A)92021/8/31CollegeofComputerScience&Technology,BUPTVennDiagramsAusefulge

41、ometricvisualizationtool(for3orlesssets)TheUniverseUistherectangularboxEachsetisrepresentedbyacircleanditsinteriorAllpossiblecombinationsofthesetsmustberepresented102021/8/31CollegeofComputerScience&Technology,BUPTVennDiagramsShadetheappropriateregiontorepresentthegivensetoperat

42、ion.112021/8/31CollegeofComputerScience&Technol