离散数学第三章第一节

第三章集合与关系集合的概念是现代数学中最基本的概念之一，集合论是现代数学的重要理论基础，并且深入到各个科学与技术领域之中。对计算机科学而言，它在开关理论，数据结构与形式语言等领域中有着广泛的应用。本章介绍集合论的基础知识，包括集合的运算、性质、序偶、关系、函数、基数等。在方法上尽量采用前两章的符号和推理规则，作出形式的证明。1第三章目录第3-1讲集合的概念和集合的运算第3-2讲笛卡儿积与关系第3-3讲复合关系、逆关系与闭包运算第3-4讲等价关系第3-5讲序关系2第3-1讲集合的概念和运算1.集合的概念2.集合的表示3.集合间的关系4.幂集5.集合的运算6.集合运算的性质7.课堂练习8.第3-1讲作业31、集合的概念集合是数学中最基本的概念之一，如同几何中的点、线等概念一样，不能再用其它有明确定义的词来定义它。

将一些确定的、彼此不同的事物的全体称之为集合。对于给定的集合和事物，应能判断这个特定的事物是否属于给定的集合。集合中的事物称为该集合的元素。通常，用大写的英文字母表示集合，用小写英文字母表示集合的元素。例如，习惯上用Ｎ表示非负整数的集合，用Ｑ表示有理数集合，Ｒ表示实数集合等等。如果ａ是集合Ｓ的元素,记作ａ∈Ｓ,读作“ａ属于Ｓ”。如ｂ不是Ｓ的元素，记作bＳ，读作“ｂ不属于Ｓ”，它等价于（b∈s）。若一个集合的元素个数是有限的，则称为有限集，否则称为无限集。42、集合的表示列举法：列出集合的所有元素，并用花括号括起来，元素之间用逗号隔开。例如：

S={e1,e2,…,en}(具有n个元素的有限集)Ａ＝{a,{b,c},{{d}}}（a,{b,c},{{d}}是该集合的元素）Ｎ＝{0,1,2,3,...}(N是非负整数集)在一个集合中，元素是彼此不同的，相同的元素被认为是一个元素，而且元素之间没有次序关系，例如集合{1,2,3}，{3,1,2}和{3,3,1,2}被视为同一个集合。叙述法（或描述法）

用谓词概括出集合中元素的特性，以确定集合的元素。S＝{x|Ｐ(x)}，如果Ｐ(e)为真，那麽e∈S，否则eS。例如，设A＝{x|x∈Ｎ∧3＜x≤8}，则A＝{4,5,6,7,8}。52、集合的表示（续）空集

定义1不含任何元素的集合叫空集，记作Φ。

Φ＝{x|P(x)∧P(x)}，P(x)是任意谓词。

例如，A={x∈R∧x2＋1＝0}是空集，式中Ｒ表示实数集合。全集定义2在研究某一问题时，如果所有涉及的集合都是某一集合的部分元素组成的（子集），则称该集合为全集，记作Ｅ。即

Ｅ＝{x|P(x)∨P(x)}。（P(x)是任意谓词）显然，全集的概念相当于论域，它是一个相对概念。63、集合间的关系两个集合相等，当且仅当它们有相同的成员。集合Ａ与Ｂ相等，记作Ａ＝Ｂ。集合Ａ与Ｂ不相等，记作Ａ≠Ｂ。定义１

给定集合Ａ和Ｂ，如果Ａ中每个元素都是Ｂ中的元素，则称Ａ为Ｂ的子集，记作ＡＢ或ＢＡ，读作“Ａ包含于Ｂ”或“Ｂ包含Ａ”。如果ＡＢ且Ａ≠Ｂ，则称Ａ为Ｂ的真子集，记作ＡＢ。AB(x)(x∈A→x∈B)AB(x)(x∈A→x∈B)∧(x)(x∈B∧xA)按子集的定义，对于任何集合A、B、C都有AA(自反性)，(AB)∧(BC)(AC)(传递性)73、集合间的关系（续1）定理１

设Ａ、Ｂ为两个集合，Ａ＝Ｂ当且仅当ＡＢ且ＢＡ。即(A＝B)AB∧BA。证明：两个集合相等，则它们有相同的元素。(A＝B)(x)(x∈A→x∈B)∧(x)(x∈B→x∈A)

(AB)∧(BA)。反之，若(AB)∧(BA)，如果A≠B，则A与B的元素不完全相同。设x∈A但xB，这与AB矛盾；或x∈B但xA，这与BA矛盾，故A与B的元素必相同，即A＝B。

定理２

空集是任意集合的子集。证明：任给集合Ａ，Φ是空集。则（x)(x∈Φ→x∈A)永真，这是因为条件式的前件(x∈Φ)永假，所以该条件式对一切ｘ皆为真。按子集的定义，ΦA为真。83、集合间的关系（续2）例1证明对于任何集合A、B、C都有(AB)∧(BC)(AC)证：(AB)∧(BC)(x)(x∈A→x∈B)∧(x)(x∈B→x∈C)

(x)（(x∈A→x∈B)∧(x∈B→x∈C)）

(x)(x∈A→x∈C)AC例2

确定下列命题的真值⑴ΦΦ；⑵Φ∈Φ；⑶Φ{Φ}；⑷Φ∈{Φ}。解：⑴、⑶、⑷为真；（因为空集是任何集合的子集，所以⑴、⑶为真。）⑵为假。（因为空集不含任何元素。）93、集合间的关系（续3）例3

证明空集是唯一的证：假定Φ1和Φ2为二空集。由定理2，Φ1Φ2，Φ2Φ1。再根据定理1，Φ1＝Φ2。例4设集合Ｅ＝{a,b,c}，写出它的所有可能的子集。解：集合Ｅ＝{a,b,c}的所有可能的子集是：

S0=Φ，S1={a}，S2={b}，S3={c}，S4={a,b}，S5={a,c}，S6={b,c}，S7={a,b,c}。104、幂集定义４集合Ａ的所有子集构成的集合叫Ａ的幂集，记作ρ(A)。

根据定义，ρ(A)={X|XA}。例如,设Ａ＝{a,b,c},则

ρ(A)＝{Φ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}例5

设B＝{Φ,{Φ}}求ρ(B)。解：ρ(B)＝{Φ，{Φ}，{{Φ}}，{Φ,{Φ}}}114、幂集（续）定理３设A有ｎ个元素，则ρ(A)有2n个元素。

证明：A的所有由ｋ个元素组成的子集个数为从ｎ个元素中取ｋ个元素的组合数：在(x+y)2的展开式中令x=y=1得：另外，因ΦA，故ρ(A)中元素的个数Ｎ可表示为：125、集合的运算定义1

设Ａ、Ｂ为两个集合，则Ａ与Ｂ的交集Ａ∩Ｂ、并集Ａ∪Ｂ、差集Ａ－Ｂ（也称Ｂ对Ａ的相对补集）和对称差AB分别定义如下：A∩B＝{x│x∈A∧x∈B}A∪B＝{x│x∈A∨x∈B}A－B＝{x│x∈A∧xB}AB＝（A－B）∪（B－A）＝{x│x∈Ax∈B}用文氏图可将集合表示如下：135、集合的运算（续）定义2设Ｅ为全集，Ａ为任一集合，称Ｅ－Ａ为Ａ的绝对补，记作A。A＝E－A＝{x│x∈E∧xA}例6设Ｅ＝{a,b,c,d},A＝{a,c},B＝{a,b,c,d},c＝Φ,求A,B,C。解：A＝{b,d}，B＝Φ，C＝{a,b,c,d}＝E。例7设A＝{1,2,3}，B＝{1,4}，C＝{3}。求A∪B,B∪AA∩B,B∩A,A－B,AB,C∩A,B∩C。解:A∪B＝{1,2,3,4}＝B∪AA∩B＝{1}＝B∩AA－B＝{2,3}AB＝{2,3,4}C∩A＝Φ,B∩C＝Φ146、集合运算的性质(1)交运算的性质A∩A=AA∩Ф=ФA∩E=AA∩B=B∩A(A∩B)∩C=A∩(B∩C)156、集合运算的性质(续1)(2)并运算的性质A∪A=AA∪E=EA∪B=B∪A(A∪B)∪C=A∪(B∪C)AA∪B，BA∪B166、集合运算的性质(续2)(3)绝对补运算的性质（A）=AE=ΦΦ=EA=EA∩A=Φ（A∪B）=A∩B176、集合运算的性质(续3)(4)差运算的性质A-B=A∩BA-B=A-(A∩B)A∩(B-C)=(A∩B)-(