01-离散数学基本原理-离散数学讲义-海南大学（共十一讲）

1.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 |