北京邮电大学计算机学院离散数学22-Setoperations

[e-mail]ce&TechnologyBeijingUniversityofPosts&TelecommunicationsSetOperations（集合的运算）22020/1/5CollegeofComputerScience&Technology,BUPTSetOperationsPropositionalcalculus（命题演算）andsettheory（集合论）arebothinstancesofanalgebraicsystem（代数系统）calledaBooleanAlgebra（布尔代数）TheoperatorsinsettheoryaredefinedintermsofthecorrespondingoperatorinpropositionalcalculusAsalwaystheremustbeauniverseU.AllsetsareassumedtobesubsetsofU32020/1/5CollegeofComputerScience&Technology,BUPTEqual（相等）Definition:TwosetsAandBareequal,denotedA=B,iffx[xAxB].Note:ByapreviouslogicalequivalencewehaveA=Biffx[(xAxB)(xBxA)]orA=BiffABandBA42020/1/5CollegeofComputerScience&Technology,BUPTDefinitionsTheunion（并集）ofAandB,denotedAB,istheset{x|xAxB}Theintersection（交集）ofAandB,denotedAB,istheset{x|xAxB}Note:Iftheintersectionisvoid,AandBaresaidtobedisjoint（不相交）.Thecomplement（补集）ofA,denotedA,istheset{x|(xA)}Note:AlternativenotationisAc,and{x|xA}.52020/1/5CollegeofComputerScience&Technology,BUPTTheAdditionprinciple（加法原理）TheoremIfAandBarefinitesets,then|AB|=|A|+|B|-|AB|Italsocalledtheinclusion-exclusionprinciple（容斥原理）62020/1/5CollegeofComputerScience&Technology,BUPTExampleLetA={a,b,c,d,e}andB={c,e,f,h,k,m}.Verifyinclusion-exclusionprinciple.Solution:AB={a,b,c,d,e,f,h,k,m}andAB={c,e}|A|=5,|B|=6,|AB|=9and|AB|=2|A|+|B|-|AB|=9=|AB|Q.E.D72020/1/5CollegeofComputerScience&Technology,BUPTTheAdditionprincipleforDisjointSets|AB|=|A|+|B|82020/1/5CollegeofComputerScience&Technology,BUPTDefinitionsThedifference（差）ofAandB,orthecomplementofBrelativetoA(,denotedA-B,isthesetABNote:The(absolute)complementofAisU-A.Thesymmetricdifference（对称差）ofAandB,denotedAB,istheset(A-B)(B-A)92020/1/5CollegeofComputerScience&Technology,BUPTVennDiagramsAusefulgeometricvisualizationtool(for3orlesssets)TheUniverseUistherectangularboxEachsetisrepresentedbyacircleanditsinteriorAllpossiblecombinationsofthesetsmustberepresented102020/1/5CollegeofComputerScience&Technology,BUPTVennDiagramsShadetheappropriateregiontorepresentthegivensetoperation.112020/1/5CollegeofComputerScience&Technology,BUPTVennDiagrams122020/1/5CollegeofComputerScience&Technology,BUPT132020/1/5CollegeofComputerScience&Technology,BUPT142020/1/5CollegeofComputerScience&Technology,BUPTExamplesU={0,1,2,3,4,5,6,7,8,9,10}A={1,2,3,4,5},B={4,5,6,7,8}.ThenAB={1,2,3,4,5,6,7,8}AB={4,5}A={0,6,7,8,9,10}B={0,1,2,3,9,10}A-B={1,2,3}B-A={6,7,8}AB={1,2,3,6,7,8}152020/1/5CollegeofComputerScience&Technology,BUPTAlgebraicPropertiesofSetOperations（集合运算的基本定律）Commutativeproperties（交换律）Associativeproperties（结合律）Distributiveproperties（分配律）ABBAABBA()()()()ABCABCABCABC()()()()()()ABCABACABCABAC162020/1/5CollegeofComputerScience&Technology,BUPTAlgebraicPropertiesofSetOperations（集合运算的基本定律）Idempotentproperties（等幂律）PropertiesoftheComplementAAAAAAAAAAUAAUUABABABAB172020/1/5CollegeofComputerScience&Technology,BUPTAlgebraicPropertiesofSetOperationsPropertiesofaUniversalSetPropertiesoftheEmptySetAUUAUAAAA182020/1/5CollegeofComputerScience&Technology,BUPTProvingSetIdentitiesToprovestatementsaboutsets,oftheformE1=E2(wheretheEsaresetexpressions),herearethreeusefultechniques:1.ProveE1E2andE2E1separately.2.Usesetbuildernotation&logicalequivalences.3.Useamembershiptable.192020/1/5CollegeofComputerScience&Technology,BUPTMethod1:MutualsubsetsExample:ShowA(BC)=(AB)(AC).Part1:ShowA(BC)(AB)(AC).AssumexA(BC),&showx(AB)(AC).WeknowthatxA,andeitherxBorxC.Case1:xB.ThenxAB,sox(AB)(AC).Case2:xC.ThenxAC,sox(AB)(AC).Therefore,x(AB)(AC).Therefore,A(BC)(AB)(AC).Part2:Show(AB)(AC)A(BC).…202020/1/5CollegeofComputerScience&Technology,BUPTMethod2:UsesetbuildernotationEXAMPLE10ProofthatAB={x|xAB}bydefinitionofcomplement={x|{x(AB)}bydefinitionofdoesnotbelongsymbol={x|(xAxB)}bydefinitionofintersection={x|(xA)(xB)}bythefirstDeMorganlawforlogicalequivalences={x|xAxB}bydefinitionofdoesnotbelongsymbol={x|xAxB}bydefinitionofcomplement={x|xAB}bydefinitionofunion=ABbymeaningofsetbuildernotationABAB212020/1/5CollegeofComputerScience&Technology,BUPTMethod3:MembershipTablesJustliketruthtablesforpropositionallogic.Columnsfordifferentsetexpressions.Rowsforallcombinationsofmembershipsinconstituentsets.Use“1”toindicatemembershipinthederivedset,“0”fornon-membership.Proveequivalencewithidenticalcolumns.222020/1/5CollegeofComputerScience&Technology,BUPTMembershipTableExampleProve(AB)-B=A-B.AABBAABB((AABB))--BBAA--BB00000011001011111100232020/1/5CollegeofComputerScience&Technology,BUPTMembershipTableExerciseProve(AB)-C=(A-C)(B-C).ABCAABB((AABB))--CCAA--CCBB--CC((AA--CC))((BB--CC))000001010011100101110111242020/1/5CollegeofComputerScience&Technology,BUPTGeneralizedUnions&IntersectionsSinceunion&intersectionarecommutativeandassociative,wecanextendthemfromoperatingonorderedpairsofsets(A,B)tooperatingonsequencesofsets(A1,…,An),orevenonunord