离散数学(18)

离散数学

关于集合运算的基本规律，列举如下：

(1)幂等律

A∪A＝AA∩A＝A 

(2)结合律

(A∪B)∪C＝A∪(B∪C) (A∩B)∩C＝A∩(B∩C) 

(3交换律

A∪B＝B∪A A∩B＝B∩A 

(4)分配律

A∪(B∩C)＝(A∪B)∩(A∪C) A∩(B∪C)＝(A∩B)∪(A∩C) 

(5)同一律 

A∪＝A A∩U＝A 

(6)零律 

A∪U＝U A∩＝ 

(7)互补律 

A∪A＝U A∩A＝ 

(8)吸收律 

A∪(A∩B)＝A A∩(A∪B)＝A 

(9)德．摩尔根(DeMorgan)律

(A∪B)＝A∩B (A∩B)＝A∪B 

(10)对合律 

(A)＝A 

(11)U＝ 

＝U

这些定律的证明并不难。下面仅以对合律、分配律和德．摩尔根律为例来说明一般的证明方法。先证明对合律。对任意的x∈U，则x∈A当且仅当x A。但x .A当且仅当x∈

(A)。因此，x∈A当且仅当x∈(A)。这表明(A)＝A。

再证德．摩尔根律。对任意的x∈U，因为x∈(A∪B)当且仅当x A∪B，但x A∪B当且仅当x A且x B，即x∈A且x∈B。所以x∈(A∪B)当且仅当x∈A∩B。这表明(A∪B)＝A∩B。

 当用A和B分别代替刚证明的(A∪B)＝A∩B中的A和B时，就得到 

(A∪B)＝(A)∩(B)

但由对合律得知A∩B＝(A)∩(B)，所以

(A∩B)＝((A∪B))＝A∪B

最后我们来证明分配律。

因为AA∪B且AA∪C，所以A(A∪B)∩(A∪C)。又因为B∩CBA∪B且B∩CCA∪C，所以B∩C(A∪B)∩(A∪C)。因此得到

A∪(B∩C)(A∪B)∩(A∪C) 

另一方面，任取x∈(A∪B)∩(A∪C)，则x∈A∪B且x∈A∪C。如果x∈A，则由x∈A∪B知x∈B，由x∈A∪C知x∈C，所以x∈B∩C。从而知道，总有x∈A或x∈B∩C，即x∈A∪(B∩C)。这表明(A∪B)

∩(A∪C)A∪(B∩C)。

总结以上的结果，就得到

A∪(B∩C)＝(A∪B)∩(A∪C)

若用A，B和C分别代替上式的A，B和C即可得到

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库离散数学(18)在线全文阅读。