离散第6章第二部分 集合论课件

第二部分集合论离散第6章第二部分集合论第六章集合代数离散第6章第二部分集合论第一节集合的基本概念离散第6章第二部分集合论

d

A,aA

图1说明隶属关系可以看作是处在不同层次上的集合之间的关系。规定：对任何集合A都有A

A。离散第6章第二部分集合论离散第6章第二部分集合论离散第6章第二部分集合论离散第6章第二部分集合论离散第6章第二部分集合论第二节集合的运算举例设A＝{a，b，c}，B＝{a}，C＝{b，d}则有

A∪B＝{a，b，c}，A∩B＝{a}，

A－B＝{b，c}，

B－A＝

，B∩C＝

说明如果两个集合的交集为

，则称这两个集合是不相交的。例如B和C是不相交的。离散第6章第二部分集合论

两个集合的并和交运算可以推广成n个集合的并和交：

A1∪A2∪…∪An＝{x|x∈A1∨x∈A2∨…∨x∈An}A1∩A2∩…∩An＝{x|x∈A1∧x∈A2∧…∧x∈An}

可简记为：

＝A1∪A2∪…∪An

＝A1∩A2∩…∩An

并和交运算还可以推广到无穷多个集合的情况：离散第6章第二部分集合论

＝A1∪A2∪…

＝A1∩A2∩…定义6.8

设A，B为集合，A与B的对称差集A

B定义为：

A

B＝(A－B)∪(B－A)

例如A＝{a，b，c}，B＝{b，d}，则

A

B＝{a，c，d}。

对称差运算的另一种定义是

A

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

可以证明这两种定义是等价的。

在给定全集E以后，A

E，A的绝对补集～A定义如下：离散第6章第二部分集合论定义6.9

～A＝E－A＝{x|x∈E∧x

A}

因为E是全集，x∈E是真命题，所以～A可以定义为

～A＝{x|xA}

例如E＝{a，b，c，d}，A＝{a，b，c}，则～A＝{d}。以上集合之间的关系和运算可以用文氏图(VennDiagram)给予形象的描述。文氏图的构造方法如下：

离散第6章第二部分集合论文氏图的构造方法如下：画一个大矩形表示全集E(有时为简单起见可将全集省略)。在矩形内画一些圆(或任何其它的适当的闭曲线)，用圆的内部表示集合。不同的圆代表不同的集合。如果没有关于集合不交的说明，任何两个圆彼此相交。图中阴影的区域表示新组成的集合。可以用实心点代表集合中的元素。离散第6章第二部分集合论文氏图的实例离散第6章第二部分集合论有穷集的计数问题使用文氏图可以很方便地解决有穷集的计数问题。首先根据已知条件把对应的文氏图画出来。一般地说，每一条性质决定一个集合。有多少条性质，就有多少个集合。如果没有特殊说明，任何两个集合都画成相交的然后将已知集合的元素数填入表示该集合的区域内。通常从n个集合的交集填起，根据计算的结果将数字逐步填入所有的空白区域。如果交集的数字是未知的，可以设为x。根据题目中的条件，列出一次方程或方程组，就可以求得所需要的结果。离散第6章第二部分集合论例6.2

对24名会外语的科技人员进行掌握外语情况的调查。其统计结果如下：会英、日、德和法语的人分别为13，5，10和9人，其中同时会英语和日语的有2人，会英、德和法语中任两种语言的都是4人。已知会日语的人既不懂法语也不懂德语，分别求只会一种语言(英、德、法、日)的人数和会三种语言的人数。解：令A，B，C，D分别表示会英、法、德、日语的人的集合。根据题意画出文氏图。设同时会三种语言的有x人，只会英、法或德语一种语言的分别为y1，y2和y3人。将x和y1，y2，y3填入图中相应的区域，然后依次填入其它区域的人数。

离散第6章第二部分集合论例6.24-x4-x4-xxy2y1y325-2英13法9德10日5y1+2(4-x)+x+2＝13y2+2(4-x)+x＝9y3+2(4-x)+x＝10y1+y2+y3+3(4-x)+x＝24-5离散第6章第二部分集合论离散第6章第二部分集合论33离散第6章第二部分集合论离散第6章第二部分集合论离散第6章第二部分集合论离散第6章第二部分集合论离散第6章第二部分集合论离散第6章第二部分集合论离散第6章第二部分集合论第三节集合恒等式下面的恒等式给出了集合运算的主要算律，其中A，B，C代表任意集合。 幂等律A∪A＝A (6.1)

A∩A＝A (6.2)

结合律(A∪B)∪C＝A∪(B∪C)(6.3)

(A∩B)∩C＝A∩(B∩C)(6.4)

交换律A∪B＝B∪A (6.5)

A∩B＝B∩A (6.6)

分配律A∪(B∩C)＝(A∪B)∩(A∪C)(6.7)

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

同一律A∪

＝A (6.9)

A∩E＝A (6.10)

离散第6章第二部分集合论零律 A∪E＝E(6.11)

A∩

＝

(6.12)排中律 A∪～A＝E(6.13)矛盾律A∩～A＝

(6.14)吸收律A∪(A∩B)＝A (6.15)

A∩(A∪B)＝A (6.16)德摩根律A－(B∪C)＝(A－B)∩(A－C)(6.17)

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

～(B∪C)＝～B∩～C(6.19)

～(B∩C)＝～B∪～C(6.20)

～

＝E(6.21)

～E＝

(6.22)双重否定律 ～(～A)＝A(6.23)离散第6章第二部分集合论集合运算性质的一些重要结果A∩B

A，A∩B

B (6.24)A

A∪B，B

A∪B (6.25)A－B

A (6.26)A－B＝A∩～B (6.27)A∪B＝B

A

B

A∩B＝A

A－B＝

(6.28)A

B＝B

A (6.29)(A

B)

C＝A

(B

C) (6.30)A

＝A (6.31)A

A＝

(6.32)A

B＝A

C

B＝C (6.33)离散第6章第二部分集合论集合恒等式的证明方法逻辑演算法 利用逻辑等值式和推理规则集合演算法 利用集合恒等式和已知结论离散第6章第二部分集合论逻辑演算法的格式题目：A＝B证明：

x，

x∈A …… x∈B

所以A＝B或证P

Q∧Q

P

题目：A

B证明：

x，

x∈A

……

x∈B

所以A

B离散第6章第二部分集合论集合演算法的格式题目：A＝B证明：A

＝……

＝B

所以A＝B题目：A

B证明：A

…

…

B

所以A

B离散第6章第二部分集合论例6.6

证明式6.17，即A－(B∪C)＝(A－B)∩(A－C)

证明:对任意的x，有

x∈A－(B∪C)

x∈A∧x

B∪C

x∈A∧┐(x∈B∨x∈C)

x∈A∧(┐x∈B∧┐x∈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)

所以A－(B∪C)＝(A－B)∩(A－C)离散第6章第二部分集合论例6.7证明式6.10，即A∩E＝A证明对任意的x，有

x∈A∩E

x∈A∧x∈E

x∈A(因为x∈E是恒真命题)

所以A∩E＝A离散第6章第二部分集合论例6.8假设已知等式6.1～6.14，试证等式6.15，

即A∪(A∩B)＝A。证明A∪(A∩B)

＝(A∩E)∪(A∩B)(由等式6.10)

＝A∩(E∪B)(由等式6.8)

＝A∩(B∪E)(由等式6.5)

＝A∩E(由等式6.11)

＝A(由等式6.10)离散第6章第二部分集合论例6.9证明等式6.27，即A－B＝A∩～B证明对于任意的x，有

x∈A－B

x∈A∧x

B

x∈A∧x∈～B

x∈A∩～B

所以A－B＝A∩～B。说明等式6.27把相对补运算转换成交运算，这在证明有关相对补的恒等式中是很有用的。离散第6章第二部分集合论例6.10证明(A－B)∪B＝A∪B证明(A－B)∪B

＝(A∩～B)∪B

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

＝(A∪B)∩E

＝A∪B离散第6章第二部分集合论离散第6章第二部分集合论离散第6章第二部分集合论离散第6章第二部分集合论离散第6章第二部分集合论第六章习题课离散第6章第二部分