loading1.2.7集合运算的代数性质
Algebraic Properties of Set Operations
Theorem 1. 集合运算满足如下性质：
交换律Commutative Propertie
1.
A?B?B?A 2.. A?B?B?A
结合律 Associative Properties
3. A?(B?C)?(A?B)?C 4. A?(B?C)?(A?B)?C
分配律Distributive Property
5. A?(B?C)?(A?B)?(A?C) 6. A?(B?C)?(A?B)?(A?C)
幂等律Idempotent Properties
7.
A?A?A 8. A?A?A
补余率 Properties of the Complement
9． 11. 13.
A?A 10. A?A??
A?A?U 12.
??U
U??
德·摩根律 De Morgan’s Law
14.
A?B?A?B 15. A?B?A?B
零一律Properties of a universal set and the empty set
16. 18.
A?U?A 17. A?U?U A???? 19. A???A
集合运算性质的证明
Proof (of the property 14) For any x,
x?A?B?x?A?B ?x?A?x?B
?x?A?x?B?x?A?BThus we have A?B?A?B and. A?B?A?B Hence A?B?A?B.
集合运算的另一些算律 Some other properties of set operations
20.A?B?A,A?B?B21.A?A?B,B?A?B22A?B?A23.A?B?A?B24.A?B?A?B?A?A?B?B?A?B?? 25.A?B?B?A26.A?A??27.A???A28.A?(B?C)?A?(B?C)Proof (of the property 23) For any x,
x?A?B
?x?A?x?B?x?A?x?B?x?A?B
Thus we have
Example 1.1 Sow that
A?B?A?B .
A?(B?C)?(A-B)?(A-C)
Proof 1. (用集合相等的定义) For any x,
x?A?(B?C)?x?A?x?B?C?x?A?(x?B?x?C)
?(x?A?x?B)?(x?A?x?C) ?x?(A?B)?x?(A?C)?x?(A?B)?(A?C) Hence
A?(B?C)?(A-B)?(A-C)
Proof 2.（用集合运算的性质）
A?(B?C)?A?B?C
?A?(B?C)?A?B?A?C ?(A?B)?(A?C)Example1.2 Suppose
A?B , prove B?A
Proof Since A?B, with the property 21A?we have
B?A?B?B ,
A?B?B.
So
A?B?B. And with De Morgan’s Law , we obtain
B?A is
A?B?B. Use the property 21 again, A?B?B?B?A,
gotten.
(不交集合的)加法原理The Addition Principle (of disjoint sets)
设A, B是论域U的两个有限子集，A, B不交，即
A?B??，则
|A?B|?|A|?|B|
容斥原理inclusion-exclusion principle
Theorem 2. 设A, B是有限子集，则|A?B|?|A|?|B|?|A?B|.
A B
Theorem3. 设A, B,C是有限子集，则
|A?B?C|?|A|?|B|?|C|?|A?B|?|A?C|?|B?C|?|A?B?C|.
A C B
Example 1.3 Let A={a, b, c, d, e} and B={c, e, f, h, k, m}. Verify theorem 2.
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|-| A? B |=| A? B |