1、Yang JCollege of Computer Science & TechnologyBeijing University of Posts & TelecommunicationsSet Operations（集合的运算）2* College of Computer Science & Technology, BUPTSet Operationsn Propositional calculus （命题演算） and set theory（集合论） are both instances of an algebraic system （代数系统） called aBoolean Algeb
2、ra（布尔代数）n The operators in set theory are defined in terms of the corresponding operator in propositional calculusn As always there must be a universe U. All sets are assumed to be subsets of U3* College of Computer Science & Technology, BUPTEqual（相等）n Definition: Two sets A and B are equal, denoted
3、 A = B, iffxx A x B.n Note: By a previous logical equivalence we haveA = B iff x(x A x B) (x B x A)orA = B iff A B and B A4* College of Computer Science & Technology, BUPTDefinitionsn The union（并集） of A and B, denoted A B, is the setx | xAxBn The intersection （交集） of A and B, denoted A B, is the set
4、x | xAxBn Note: If the intersection is void, A and B are said to be disjoint（不相交） .n The complement （补集） of A, denoted A, is the set x | (xA)n Note: Alternative notation is Ac, and x|xA.5* College of Computer Science & Technology, BUPTThe Addition principle （加法原理）n Theorem n If A and B are finite se
5、ts, then |AB|=|A|+|B|-|AB|n It also called the inclusion-exclusion principle（容斥原理）6* College of Computer Science & Technology, BUPTExamplen Let A=a, b, c, d, e and B=c, e, f, h, k, m. Verify inclusion-exclusion principle.n Solution:n A B=a, b, c, d, e, f, h, k, m and A B= c, en |A|= 5, |B|= 6, | A B
6、 |= 9 and | A B |= 2n |A|+|B|-| A B |= 9=| A B |n Q.E.D7* College of Computer Science & Technology, BUPTThe Addition principle for Disjoint Setsn |AB|=|A|+|B|8* College of Computer Science & Technology, BUPTDefinitionsn The difference（差） of A and B, or the complement of B relative to A(, denoted A -
7、 B, is the setA B n Note: The (absolute) complement of A is U - A.n The symmetric difference（对称差） of A and B, denoted AB, is the set(A B)(B A)9* College of Computer Science & Technology, BUPTVenn Diagramsn A useful geometric visualization tool (for 3 or less sets)n The Universe U is the rectangular boxn Each set is represented by a circle and its interiorn All possible combinations of the sets must be represented10* College of Computer Science & Technology, BUPTVenn Diagramsn Shade the appropriate region to represent the given set operation.
