集合论与图论

集合论与图论第1页，共22页，2023年，2月20日，星期四2第三章目录第3-1讲集合的概念和集合的运算第3-2讲笛卡儿积与关系第3-3讲复合关系、逆关系与闭包运算第3-4讲等价关系第3-5讲序关系第2页，共22页，2023年，2月20日，星期四3第3-1讲集合的概念和运算1.集合的概念2.集合的表示3.集合间的关系4.幂集5.集合的运算6.集合运算的性质7.课堂练习8.第3-1讲作业第3页，共22页，2023年，2月20日，星期四41、集合的概念将一些确定的、彼此不同的事物的全体称之为集合。对于给定的集合和事物，应能判断这个特定的事物是否属于给定的集合。集合中的事物称为该集合的元素。

通常，用大写的英文字母表示集合，用小写英文字母表示集合的元素。例如，习惯上用Ｎ表示非负整数的集合，用Ｑ表示有理数集合，Ｒ表示实数集合等等。如果ａ是集合Ｓ的元素,记作ａ∈Ｓ,读作“ａ属于Ｓ”。如ｂ不是Ｓ的元素，记作bＳ，读作“ｂ不属于Ｓ”，它等价于（b∈s）。若一个集合的元素个数是有限的，则称为有限集，否则称为无限集。第4页，共22页，2023年，2月20日，星期四52、集合的表示列举法：列出集合的所有元素，并用花括号括起来，元素之间用逗号隔开。例如：

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}。第5页，共22页，2023年，2月20日，星期四62、集合的表示（续）空集

定义1

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

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

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

Ｅ＝{x|P(x)∨P(x)}。（P(x)是任意谓词）显然，全集的概念相当于论域，它是一个相对概念。第6页，共22页，2023年，2月20日，星期四73、集合间的关系两个集合相等，当且仅当它们有相同的成员。集合Ａ与Ｂ相等，记作Ａ＝Ｂ。集合Ａ与Ｂ不相等，记作Ａ≠Ｂ。定义１

给定集合Ａ和Ｂ，如果Ａ中每个元素都是Ｂ中的元素，则称Ａ为Ｂ的子集，记作ＡＢ或ＢＡ，读作“Ａ包含于Ｂ”或“Ｂ包含Ａ”。如果ＡＢ且Ａ≠Ｂ，则称Ａ为Ｂ的真子集，记作ＡＢ。

AB(x)(x∈A→x∈B)AB(x)(x∈A→x∈B)∧(x)(x∈B∧xA)

按子集的定义，对于任何集合A、B、C都有AA(自反性)，(AB)∧(BC)(AC)(传递性)第7页，共22页，2023年，2月20日，星期四83、集合间的关系（续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为真。第8页，共22页，2023年，2月20日，星期四93、集合间的关系（续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

确定下列命题的真值⑴ΦΦ；⑵Φ∈Φ；⑶Φ{Φ}；⑷Φ∈{Φ}。解：⑴、⑶、⑷为真；（因为空集是任何集合的子集，所以⑴、⑶为真。）⑵为假。（因为空集不含任何元素。）第9页，共22页，2023年，2月20日，星期四103、集合间的关系（续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}。第10页，共22页，2023年，2月20日，星期四114、幂集定义４集合Ａ的所有子集构成的集合叫Ａ的幂集，记作ρ(A)。

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

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

设B＝{Φ,{Φ}}求ρ(B)。解：ρ(B)＝{Φ，{Φ}，{{Φ}}，{Φ,{Φ}}}第11页，共22页，2023年，2月20日，星期四124、幂集（续）定理３设A有ｎ个元素，则ρ(A)有2n个元素。

证明：A的所有由ｋ个元素组成的子集个数为从ｎ个元素中取ｋ个元素的组合数：在(x+y)2的展开式中令x=y=1得：另外，因ΦA，故ρ(A)中元素的个数Ｎ可表示为：第12页，共22页，2023年，2月20日，星期四135、集合的运算定义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}用文氏图可将集合表示如下：第13页，共22页，2023年，2月20日，星期四145、集合的运算（续）定义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∪A，A∩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＝Φ第14页，共22页，2023年，2月20日，星期四156、集合运算的性质(1)交运算的性质A∩A=AA∩Ф=ФA∩E=AA∩B=B∩A(A∩B)∩C=A∩(B∩C)例8

证明(A∩B)∩C=A∩(B∩C)证：(A∩B)∩C={x|x∈(A∩B)x∈C}={x|x∈Ax∈Bx∈C}={x|x∈A(x∈Bx∈C)}={x|x∈Ax∈B∩C)}=A∩(B∩C)第15页，共22页，2023年，2月20日，星期四166、集合运算的性质(续1)(2)并运算的性质A∪A=AA∪E=EA∪B=B∪A(A∪B)∪C=A∪(B∪C)AA∪B，BA∪B例9设AB，CD，则A∪CB∪D。证:对任意x∈A∪C，则x∈A或x∈C。若x∈A，因AB，x∈B，故x∈B∪D；若x∈C，因CD，所以x∈D亦有x∈B∪D。按子集的定义可知原式成立。第16页，共22页，2023年，2月20日，星期四176、集合运算的性质(续2)(3)绝对补运算的性质（A）=AE=ΦΦ=EA=EA∩A=Φ（A∪B）=A∩B例10

证明(A∩B)=A∪B证:（A∩B）={x|x∈(A∩B)}={x|xA∩B}={x|x∈A∩B}={x|(x∈A∧x∈B)}={x|x∈A∨x∈B}={x|xA∨xB}={x|x∈A∨x∈B}=A∪B第17页，共22页，2023年，2月20日，星期四186、集合运算的性质(续3)(4)差运算的性质A-B=A∩BA-B=A-(A∩B)A∩(B-C)=(A∩B)-(A∩C)例11

证明A-B=A-(A∩B)证:因为x∈A-Bx∈AxB

x∈Ax(A∩B)x∈A-(A∩B)

所以，A-BA-(A∩B)。反之，x∈A-(A∩B)x∈Ax(A∩B)x∈Ax∈(A∩B)x∈Ax∈ABx∈A(x∈Ax∈B))(x∈Ax∈A)(x∈Ax∈B)）F(x∈Ax∈B))x∈Ax∈Bx∈AxBx∈A-B所以，A-(A∩B)A-B。纵上所述，原式成立。第18页，共22页，2023年，2月20日，星期四196、集合运算的性质(续4)(5)对称差运算的性质AB=BAAΦ=AAA=ΦAB=（A∩B）∪（A∩B）(AB)C=A(BC)对结合律，用文氏图说明如下：第19页，共22页，2023年，2月20日，星期四207、课堂练习练习1

证明A∩(B-C)=(A∩B)-(A∩C)证法1：(A∩B)-(A∩C)=(A∩B)∩(A∩C)=(A∩B)∩(A∪C)=(A∩B∩A)∪(A∩B∩C)=Φ∪(A∩B∩C)（从左往右的关键步骤）

=A∩B∩C=A∩(B-C)证法2:按集合相等的定义证明。任取x∈A∩(B-C),有x∈A∩(B-C)x∈Ax∈(B-C)(x∈Ax∈BxC)(x∈Ax∈BxA)(x∈Ax∈BxC)(x∈Ax∈B)(xAxC)x∈(A∩B)(x∈Ax∈C)x∈(A∩B)(x∈Ax∈C)x∈(A∩B)(x∈A∩C)x∈(A∩B)xA∩Cx∈(A∩B)-(A∩C)所以，A∩(B-C)=