离散数学第13讲

第二部分集合论

对于从事计算机科学工作的人们来说，集合论是必不可少的基础知识。例如有限状态机、形式语言等都离不开子集、幂集、集合的分类等概念。集合成员表和范式在逻辑设计、定理证明中也都有重要应用。本部分从集合的直观概念出发，介绍了集合论中的一些基本概念和基本理论，其中包括集合、关系、函数等。离散数学第13讲本讲基本知识点：1、集合的基本概念2、集合的运算3、集合基本恒等式2第六章集合代数6.1集合的基本概念直观定义：一些事物汇集到一起组成的一个整体称为集合，而这些事物就是这个集合的元素或成员。集合通常用大写字母来标记，如N、Z、Q、R、C。集合表示方法：列元素法A={1,2,3,4,5}谓词表示法B={x|x∈N∧1≤x≤5}3第六章集合代数集合的特征互异性{1,2,3,2,4}={1,2,3,4}无序性{4,2,1,3}={1,2,3,4}元素和集合之间的关系属于（∈）或不属于（

）

如：对于A={1,{2,3},{{4}}}，1∈A,{2,3}∈A,3

A.可以用树形图表示这种关系。考虑：4,{4},{{4}}呢?4第六章集合代数如：A1{2,3}{{4}}

23{4}4本书规定：对于任何集合A，都有A

A。5第六章集合代数定义6.1设A，B为集合，如果B中的每个元素都是A中的元素，则称B是A的子集合，简称子集。也称B被A包含，或B包含于A，或A包含B，记作B

A。如果B不被A包含，则记作B

A。包含的符号化表示为：B

A

x(x∈Bx∈A)例如：N

Z

Q

R

C,而CR.显然：对于任何集合A，都有A

A。6第六章集合代数定义6.2设A，B为集合，如果A

B且B

A，则称A与B相等，记作A=B。如果A与B不相等，则记作A≠B。相等的符号化表示为：A=B

A

B

∧B

A7第六章集合代数定义6.3设A，B为集合，如果B

A且B≠A，则称B是A的真子集,也称B被A真包含，或B真包含于A，或A真包含B，记作B

A。如果B不被A真包含，则记作A

B。真子集的符号化表示为：B

A

A≠B∧B

A例如：N

Z

Q

R

C,而CC.显然：对于任何集合A，都有A

A。8第六章集合代数定义6.4不含任何元素的集合叫做空集，记作φ。空集的符号化表示为：φ

{x|x≠x}如：C={x|x∈Z+∧x<0}.定理6.1空集是一切集合的子集。证明：对于任何集合A，有子集定义有φ

A

x(x∈φx∈A)右边的蕴涵式为真，所以φ

A也为真。推论：空集是唯一的。证明：如不唯一，设存在空集φ1和φ2，由定理6.1得

φ1

φ2和φ2

φ1根据集合相等的定义得，φ1=φ2。9第六章集合代数含有n个元素的集合简称为n元集，它的含有m(m≤n)个元素的子集叫做它的m元子集。任给一个n元集，它的0元子集的个数为：Cn0,即φ；它的1元子集的个数为：Cn1,即单元集；它的2元子集的个数为：Cn2；……它的n元子集的个数为：Cnn.显然：任一n元集A的子集总数为：

Cn0+Cn1+Cn2…+Cnn=2n请通过列出集合S={a,b,c}的所有子集来验证此结论。10第六章集合代数定义6.5设A为集合，把A的全部子集构成的集合叫做A的幂集，记作P(A)或2A。幂集的符号化表示为P(A)＝｛x|x

A｝例如：若B={1，2，c,d}，则P(B)=???定义6.6在一个具体问题中，若所涉及的集合都是某个集合的子集，则称这个集合为全集，记作E。11第六章集合代数6.2集合的运算定义6.7设A，B集合，A与B的并集A∪B，交集A∩B，B对A的相对补集A-B，分别定义如下：A∪B={x|x∈A∨

x∈B}A∩B={x|x∈A∧

x∈B}A-B={x|x∈A∧

x

B}如：A={1,2,3},B={3,4,5}，C={6,7}则A∪B、A∩B、A-B、C∩B、C-B、C-C分别为？？？两个集合的并交运算可推广至n个集合：A1∪A2∪…∪An={x|x∈A1∨x∈A2∨…∨

x∈An

}A1∩A2∩

…∩An={x|x∈A1∧x∈A2∧

…∧

x∈An

}文氏图是用来描述集合关系与运算的很好的工具，请参见课本P96。12第六章集合代数定义6.8设A，B集合，A与B的对称差集A○B，分别定义如下：A○B=(A–B)∪(B-A)或A○B=(A∪B)-(A∩B)+++定义6.9设A集合，E为全集，A的绝对补集定义为：~A=E–A={x|x∈E∨

x

A}13第六章集合代数利用文氏图可以解决一些有限集的计数问题参见例6.2、6.3练习：某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。已知会打网球的6个人都会打篮球或排球。求不会打球的人数。14假设只会打篮球和排球的人数为x，只会打篮球和网球的人数为y，只会打网球和排球的人数为z：x+2=6x=4z+2=5z=3y+2+z=6y=1不会打球的人数为：25-14-12+x+2=5

排球12网球6篮球14人2xyzx15练习2：对60个人的调查表明有25人阅读《每周新闻》杂志，26人阅读《时代》杂志，26人阅读《财富》杂志，9人阅读《每周新闻》和《财富》，11人阅读《每周新闻》和《时代》，8人阅读《时代》和《财富》，还有8人什么杂志也不读。（1）求阅读全部三种杂志的人数（2）分别求只阅读《每周新闻》、《时代》和《财富》杂志的人数。16解：(1)(5+x)+(7+x)+(9+x)+(9-x)+(11-x)+(8-x)+x+8=60解得x=3(2)分别是8，10，12人x8-x8人9-x

11-x25-(11-x)-(9-x)-x=5+x时代26财富26每周新闻25人26-(11-x)-(8-x)-x=7+x26-(9-x)-(8-x)-x=9+x17第六章集合代数6.3集合恒等式P99-100列出的23条恒等式是这部分进行运算、证明的重要依据，望注意掌握。集合代数中恒等式证明的两种思路：(1)设A1、A2为集合公式，欲证A1=A2，只须证A1

A2∧A2

A1为真。也即证

x∈A1=>x∈A2和

x∈A2=>x∈A1

(2)利用已知的恒等式代入。

总体上还是采用命题逻辑中的等值式，在叙述上采用半形式化的方法，其中

表示当且仅当，意即“等价”。18第六章集合代数例6.6证明A-(B∪C)=(A-B)∩(A-C).证明：对于

xx∈A-(B∪C)

x∈A∧x

(B∪C)

x∈A∧

(x∈B∨x∈C)

x∈A∧(

x∈B∧

x∈C)