集合代数完整版本

集合论部分10/31/20241DiscreteMath.,YanxiuSheng集合论的起源与发展集合论(SetTheory)是现代数学的基础．它的起源可追溯到16世纪末，主要是对数集进行卓有成效的研究．集合论实际发展是由19世纪70年代德国数学家康托尔(G.Cantor)在无穷序列和分析的有关课题的理论研究中创立的．康托尔对具有任意特性的无穷集合进入了深入的探讨，提出了关于基数、序数、超穷数和良序集等理论，奠定了集合论的深厚基础．因此，康托尔被誉为集合论的创始人．10/31/20242DiscreteMath.,YanxiuSheng集合论的起源与发展（续）随着集合论的发展，以及它与数学哲学密切联系所作的讨论，在本世纪初，出现了许多似是而非、自相矛盾的悖论，如著名的罗素(B.A.W.Russell)悖论，有力冲击了或者说动摇了集合论的发展．许多数学家哲学家为克服这些矛盾而建立了各种公理化集合论体系，其中尤以20世纪初、中期的ZFS(E.Zermelo,A.Fraenkel,T.Skolem)和NBG(Von

Neurnann,P.Bernavs,K.Gödel)公理化体系最为流行.10/31/20243DiscreteMath.,YanxiuSheng集合论的起源与发展（续）到20世纪60年代，P.L.Cohen发明了强制方法而得到了关于连续统与选择公理的独立性成果，尔后的研究结果推陈出新，大量涌现．在同一时代，美国数学家L.A.Zadeh提出了Fuzzy集理论,以及20世纪80年代波兰数学家Z.

Pawlak发表了Rough集理论，这两种理论区别于以往的集合论，是一种新的模糊集理论，受到了学术界的重视和青睐，取得了喜人成果．还有多位著名学者也为集合论的发展作出了重要贡献．10/31/20244DiscreteMath.,YanxiuSheng集合论的起源与发展（续）在此基础上以后就逐步形成了公理化集合论和抽象集合论，使该学科成为在数学中发展最为迅速的一个分支。集合论观点已渗透到古典分析、泛函、概率、函数论以及信息论、排队论等现代数学各个领域。10/31/20245DiscreteMath.,YanxiuSheng康托尔的基本理论康托尔集合论中的许多证明的一切定理均能从三个公理得出．这三个公理是:①外延公理:如果两个集合中各个元都是相同的则它们相等．②抽象公理:任给一个性质，都有一个满足该性质的客体所组成的集合．③选择公理:每个集合都有一个选择函数．但是,毛病却出在抽象公理上.10/31/20246DiscreteMath.,YanxiuSheng罗素悖论罗素悖论：由“不为自身的成员这一性质的所有客体的集合”会导出矛盾.论证把抽象公理符号化为：(

y)(

x)(x∈y

(x))(1)其中,

(x)是不以y为自由变元的公式.把

(x)取为“x不为x的成员”,即

(x)=(x∈x).则罗素悖论符号化为(

y)(

x)(x∈y(x∈x))(2)在(2)中取x＝y，可得(

y)(

y)(y∈y(y∈y))(3)10/31/20247DiscreteMath.,YanxiuSheng本篇的主要内容

集合与关系集合关系集合的基本概念与表示方法子集与集合相等集合的运算及其性质集合的幂集笛卡尔积包含排斥原理关系的定义及表示关系的性质复合关系和逆关系关系的闭包运算集合的划分与覆盖等价关系与等价类相容关系序关系10/31/20248DiscreteMath.,YanxiuSheng集合代数集合的概念和表示集合的基本运算集合的计数——包含排斥原理10/31/20249DiscreteMath.,YanxiuSheng3-1集合的概念和表示法集合的定义与表示集合与元素集合之间的关系空集全集幂集10/31/202410DiscreteMath.,YanxiuSheng集合的定义集合

没有精确的数学定义理解：一些具有共同性质的东西

汇集成的整体如：教室内的桌椅；图书馆的藏书，全国的高等学校、自然数的全体、直线上的点子等。元素组成集合中的事物集合的字符表示集合A、B、C…

元素a,b,c…集合的分类无限集：组成集合的元素个数是无限的有限集：组成集合的元素个数是有限的10/31/202411DiscreteMath.,YanxiuSheng集合的表示方法集合的表示方法列元素法

A={a,b,c,d},B={1,2,3,4},

D={桌子，灯泡，自然数，老虎},

C={2,4,6,…,2m},S={a,a2,a3,…,an}

仅适用于有限集合。谓词表示法B={x|P(x)}B由使得P(x)为真的

x

构成如，P(x)表示x是正奇数，则B是所有正奇数的集合.10/31/202412DiscreteMath.,YanxiuSheng集合与元素集合与元素的关系：隶属关系，属于∈，不属于

1、a∈A表示a属于集合A

，亦称A包含a，或a在A之中，或a是A的成员。2、a

A表示元素a不属于A

，亦称A不包含a，或a不在A中，或a不是A的成员。实例，

A={x|x

R

x2-1=0},A={-1,1}，1

A,2A注意：对于任何集合A和元素x(可以是集合)，

x

A和x

A

两者成立其一，且仅成立其一.10/31/202413DiscreteMath.,YanxiuSheng隶属关系的层次结构注意：集合的元素也可以是集合.例1A={a,{b,c},d,{{d}}}{b,c}

Ab

A{{d}}A{d}Ad

A

10/31/202414DiscreteMath.,YanxiuSheng集合之间的关系包含（子集）

A

B

x(x

A

x

B)不包含A⊈B

x(x

A

x

B)相等

A=B

A

B

B

A不相等A

B真包含

A

B

A

B

A

B

(x)(x

A→x

B)∧(x)(x

B∧x

A)不真包含A

B思考：

和

的定义注意

和

是不同层次的问题10/31/202415DiscreteMath.,YanxiuSheng包含关系的性质自反性：A

A传递性：(A

B)∧(B

C)(A

C)证明：(A

B)∧(B

C)

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

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

x((x∈A→x∈C))10/31/202416DiscreteMath.,YanxiuSheng空集空集

不含任何元素的集合，

={x|p(x)∧p(x)}，p(x)是任意谓词。实例{x|x2+1=0xR}就是空集定理空集是任何集合的子集

A

x(x

x

A)TA的平凡子集和A推论空集是惟一的.证

假设存在1和2，则1

2且1

2，因此1=2思考：

≠{

}，

∈{

}，为什么？10/31/202417DiscreteMath.,YanxiuSheng全集全集E

相对性在给定问题中，全集包含任何集合，即A(A

E)注意E={x|p(x)∨

p(x)}，p(x)为任何谓词。全集的概念相当于论域含有n个元素的集合的子集个数为2n个。10/31/202418DiscreteMath.,YanxiuSheng关于集合的说明集合的元素还可以允许是一个集合。如：S={a,{1,2},p,{q}}，q∈{q},但q

S，同理1∈{1,2}，但1

S。{{1,2},4}≠{1,4,2}集合中的元素互异。例如：{1,2,4}={1,2,2,4}集合中的元素无次序和大小之分。如：{1,2,4}={1,4,2}集合中的元素不一定同类。10/31/202419DiscreteMath.,YanxiuSheng幂集定义

(A)={x|x

A

}，或记为

(A),2A实例

(

)={

}，

({

})={

,{

}}

({1,{2,3}})={,{1},{{2,3}},{1,{2,3}}}计数：如果|A|=n，则|

(A)|=2n

证明设A={a1,a2,…,an},把a1a2…an与一个n位二进制数b对应,ai对应于b的第i位。定义二进制数b所对应A的子集B

：与b中的1对应的A中元素组成的集合。这样B与该二进制一一对应，有多少个不同n位二进制就有多少个不同的子集。10/31/202420DiscreteMath.,YanxiuSheng幂集（续）用编码来唯一地表示有限集幂集的元素以S={a,b,c}为例。

(S)={Si|i∈J}，J={i|i是二进制数且00…0≤i≤11…1}例如S3=S011={b,c},S6=S110={a,b}等。一般地10/31/202421DiscreteMath.,YanxiuSheng实例例2

证明对每个集合S，{,{}}(S)成立。证由幂集的定义知，

S

(S)

{}(S){}(S)又(S)(S)所以{,{}}(S){,{}}(S)10/31/202422DiscreteMath.,YanxiuSheng实例（续）例3

假定

(A)=(B)，证明A=B证任意a

a

A{a}A{a}(A){a}(B){a}B

a

B

所以A=B。10/31/202423DiscreteMath.,YanxiuSheng实例（续）例4

证明若B

C，则(B)(C)证任取XX(B)

X

B

X

C

X(C)

所以(B)(C)10/31/202424DiscreteMath.,YanxiuSheng3-2集合的运算集合基本运算的定义

∪∩文氏图集合运算的算律集合包含或恒等式的证明10/31/202425DiscreteMath.,YanxiuSheng集合基本运算的定义并

A∪B={x|x

A

x

B}交

A∩B={x|x

A

x

B}相对补

A

B={x|x

A

x

B}对称差

A

B=(A

B)∪(B

A)=(A∪B)(A∩B)

绝对补

A=E

A

10/31/202426DiscreteMath.,YanxiuSheng文氏图表示10/31/202427DiscreteMath.,YanxiuSheng关于运算的说明运算顺序：和幂集优先，其他由括号确定并和交运算可以推广到有穷个集合上，即

A1∪A2∪…An={x|x

A1

x

A2

…

x

An}

A1∩A2∩…An={x|x

A1

x

A2

…

x

An}10/31/202428DiscreteMath.,YanxiuSheng例1F:一年级大学生的集合S：二年级大学生的集合

R：计算机系学生的集合M：数学系学生的集合

T：选修离散数学的学生的集合L：爱好文学学生的集合

P：爱好体育运动学生的集合只有一、二年级的学生才爱好体育运动T(M∪R)∩SR∩STML∪PPF∪SS(M∪R)P除去数学和计算机系二年级学生外都不

选修离散数学所有计算机系二年级学生都选修离散数学数学系一年级的学生都没有选修离散数学数学系学生或爱好文学或爱好体育运动(M∩F)∩T=10/31/202429DiscreteMath.,YanxiuSheng例2分别对条件(1)到(5)，确定X集合与下述那些集合相等。

S1={1,2,…,8,9},S2={2,4,6,8},S3={1,3,5,7,9},

S4={3,4,5},S5={3,5}若X∩S3=,则X

若X

S4,X∩S2=,则X

若X

S1，XS3,则X

若X

S3=,则X

若

X

S3，XS1,

则X=S2=S5=S1,S2,S4=S3,S5与S1,...,S5都不等10/31/202430DiscreteMath.,YanxiuSheng例3例3

设A

B，求证A∩C

B∩C证任取x，

x∈A∩C

x∈A

x∈C

x∈B

x∈C

x∈B∩C

因此A∩C

B∩C。10/31/202431DiscreteMath.,YanxiuSheng例4例4

设A

B，C

D，则A∪C

B∪D证任取x，

x∈A∪C

x∈A

x∈C

x∈B

x∈D

x∈B∪D

故A∪C

B∪D。10/31/202432DiscreteMath.,YanxiuSheng集合运算的算律∪∩

交换A∪B=B∪AA∩B=B∩AA

B=B

A结合(A∪B)∪C=A∪(B∪C)(A∩B)∩C=A∩(B∩C)(A

B)C=A

(B

C)幂等A∪A=AA∩A=A∪与∩∩与

分配A∪(B∩C)=(A∪B)∩(A∪C)A∩(B∪C)=(A∩B)∪(A∩C)A∩(B

C)=(A∩B)(A∩C)吸收A∪(A∩B)=AA∩(A∪B)=A10/31/202433DiscreteMath.,YanxiuSheng集合运算的算律（续）

D.M律A

(B∪C)=(A

B)∩(A

C)A

(B∩C)=(A

B)∪(A

C)

(B∪C)=B∩

C

(B∩C)=B∪

C双重否定

A=A

E补元律A∩

A=A∪

A=E零律A∩

=

A∪E=E同一律A∪

=AA∩E=A否定

=E

E=10/31/202434DiscreteMath.,YanxiuSheng集合运算的其它性质

A

B

AA

B

A

B=

A∪B=B

A∩B=AA∩B=

A

B=AA

A∪B，B

A∪BA

B~B

~A，A

B(B-A)∪A=BA-B=A∩~B=A-(A∩B)A∩(B-C)=(A∩B)-(A∩C)A

=A，A

A=A

B=(A∩~B)∪(~A∩B)=(A∪B)-(A∩B)10/31/202435DiscreteMath.,YanxiuSheng集合包含或相等的证明方法证明

X

Y命题演算法包含传递法等价条件法反证法并交运算法证明X=Y命题演算法等式代入法反证法运算法以上的X,Y代表集合公式10/31/202436DiscreteMath.,YanxiuSheng命题演算法证X

Y例5

证明A

B

~B

~A

任取x

x~B

x

B

x

A

x

~A任取x，

x

X…x

Y

10/31/202437DiscreteMath.,YanxiuSheng包含传递法证X

Y例6

A

B

A

B证

A

B

A

A

A

B

所以A

B

A

B找到集合T

满足X

T

且T

Y，从而有X

Y10/31/202438DiscreteMath.,YanxiuSheng利用包含的等价条件证X

Y例7A

C

B

C

A

B

C

证A

C

A

C=C

B

C

B

C=C(A

B)C=A(B

C)=A

C=C(A

B)C=C

A

B

C

命题得证10/31/202439DiscreteMath.,YanxiuSheng反证法证X

Y例8证明A

C

B

C

A

B

C证假设A

B

C不成立，则

x(x

A

B

x

C)

因此

x

A

或

x

B，且x

C

若x

A,则与A

C矛盾；

若x

B,则与B

C矛盾.欲证X

Y,假设命题不成立，必存在x使得

x

X

且x

Y.然后推出矛盾.

10/31/202440DiscreteMath.,YanxiuSheng利用已知包含式并交运算例9证明A

C

B

C

A

C

B

C

A

B证A

C

B

C，A

C

B

C

上式两边求并，得

(A

C)(A

C)(B

C)(B

C)

(A

C)(A

C)(B

C)(B

C)

A(C

C)

B(C

C)

A

E

B

E

A

B由已知包含式通过运算产生新的包含式

X

Y

X

Z

Y

Z,X

Z

Y

Z10/31/202441DiscreteMath.,YanxiuSheng命题演算法证明X=Y例10证明A(A

B)=A

（吸收律）证任取x,

x

A(A

B)x

A

x

A

B

x

A(x

A

x

B)x

A

任取x

，

x

X

…x

Y

x

Y…x

X

或者

x

X

…

x

Y

10/31/202442DiscreteMath.,YanxiuSheng等式替换证明X=Y例11证明A

(A

B)=A

（吸收律）

A∪(A∩B)=(A∩E)∪(A∩B)=A∩(E∪B)=A∩E=A不断进行代入化简，最终得到两边相等10/31/202443DiscreteMath.,YanxiuSheng反证法证明X=Y例12证明以下等价条件

A

B

A

B=B

A

B=A

A

B=

(1)(2)(3)(4)证明顺序：

(1)(2),(2)(3),(3)(4),(4)(1)假设X=Y不成立，则存在x使得x

X且x

Y，或者存在x使得x

Y且x

X，然后推出矛盾.10/31/202444DiscreteMath.,YanxiuSheng例12（续）(1)(2)：A

B

A

B=B显然B

A

B，下面证明A

B

B.任取x，

x

A

B

x

A

x

B

x

B

x

B

x

B因此有A

B

B.综合上述（2）得证.(2)(3)：A

B=B

A

B=A

A=A

(A

B)

A=A

B

（将A

B用B代入)10/31/202445DiscreteMath.,YanxiuSheng例12（续）(3)(4)：A

B=A

A

B=

假设A

B

,即

x

A

B，那么x

A且x

B.而

x

B

x

A

B.从而与A

B=A矛盾.(4)(1)：A

B=

A

B

假设A

B不成立，那么

x(x

A

x

B)

x

A

B

A

B

与条件A

B=矛盾.10/31/202446DiscreteMath.,YanxiuSheng集合运算法证明X=Y例13

证明A

C=B

C

A

C=B

C

A=B证由A

C=B

C

和

A

C=B

C

得到

(A

C)-(A

C)=(B

C)-(B

C)

从而有A

C=B

C由已知等式通过运算产生新的等式

X=Y

X

Z=Y

Z,X

Z=Y

Z，X-Z=Y-Z(A

C)C=(B

C)C

A(C

C)=B(C

C)

A=B

A=B10/31/202447DiscreteMath.,YanxiuSheng实例例14

证明

~(A∪B)=~A∩~B~(A∩B)=~A∪~B（德摩根律）证

~(A∪B)=E-(A∪B)=(E-A)∩(E-B)=~A∩~B~(A∩B)=E-(A∩B)=(E-A)∪(E-B)=~A∩~B10/31/202448DiscreteMath.,YanxiuSheng广义并/子集簇成员的并定义设A为集合，A的元素的元素构成的集合称为A的广义并，记为∪A。∪A={x|

S(S

∈A∧x∈S}定义设A为非空集合，A的所有元素的公共元素的集合称为A的广义交，记为∩A。∩A={x|

S(S

∈A→x∈S}例设A={{a,b,c},{a,c,d},{a,e,f}},B={{a}},C={a,{c,d}}∪A={a,b,c,d,e,f},∪B={a},∪C=a∪{c,d}∩A={a},∩B={a},∩C=a∩{c,d}10/31/202449DiscreteMath.,YanxiuSheng几点说明规定集合的元素都是集合。若A={A1,A2,…,An}，则∪A=A1∪A2∪…∪

An∪=空集不可以进行广义交，因为∩不是集合，在集合论中是没有意义的。若A={A1,A2,…,An}，则∩A=A1∩A2∩…∩An10/31/202450DiscreteMath.,YanxiuSheng集合运算的优先级一元运算：广义交、广义并、幂集、绝对补二元运算：并、交、相对补、对称差优先级：先一元运算再二元运算。结合顺序一元运算之间由右到左二元运算之间由括号决定10/31/202451DiscreteMath.,YanxiuSheng例题例15

设A,B,C是集合，求下列各式成立的充分必要条件。

a)(A-B)∪(A-C)=

b)(A-C)∪B=A∪B解

a)(A-B)∪(A-C)

A-(B∩C)=

A

B∩C故a)成立的充分必要条件是A

B∩C.b)(A-C)∪B=(A∩~C)∪B=(A∪B)∩(B∪~C）=A∪BA∪BB∪~C故b)成立的充分必要条件是A∪BB∪~C.思考题：A

~C

是b)成立的充分必要条件是吗？10/31/202452DiscreteMath.,YanxiuSheng例题例16

设A,B,C是任意集合，若A∩B

~C和A∪C

B,

则A∩C=.证法1

假设A∩C

，即

x(x∈A∩C)

x(x∈A

x∈C)

x(x∈A

x∈A∪C)

x(x∈A

x∈B)

x(x∈A∩B)

x∈~C证法2

C

A∪C

A∩C

A∩(A∪C)

A∩C

A∩B

A∩C~C

A∩C=10/31/202453DiscreteMath.,YanxiuSheng包含排斥原理包含排斥原理——有限个元素的计数问题。定理设S为有穷集，P1,P2,…,Pm

是m种性质，Ai是S

中具有性质Pi

的元素构成的子集，i=1,2,…,m.则S

中不具有性质P1,P2,…,Pm的元素数为10/31/202454DiscreteMath.,YanxiuSheng证明证设x不具有性质P1,P2,…,Pm

,

x

Ai

,i=1,2,…,m

x

Ai

Aj

,1i<j

m

…

x

A1

A2…Am

,x对右边计数贡献为

10+00+…+(1)m·0=1证明要点：任何元素x，如果不具有任何性质，则对等式右边计数贡献为１，否则为０10/31/202455DiscreteMath.,YanxiuSheng证明（续）设x具有n条性质，1n

m

x

对|S|贡献为1

x

对贡献为

x

对贡献为

….

x

对|A1

A2…Am|贡献为

x对右边计数贡献为10/31/202456DiscreteMath.,YanxiuSheng推论推论S中至少具有一条性质的元素数为证明将定理1代入即可10/31/202457DiscreteMath.,YanxiuSheng实例例1

假设在10名青年中有5名是工人，7名是学生，其中兼具有工人与学生双重身份的青年有3名，问既不是工人又不是学生的青年有几名？解：设工人的集合为W，学生的集合为S，则根据题设有：|W|=5，|S|=7，|W∩S|=3。则|~W∩~S|=10-(|W|+|S|)+|W∩S|=10-(5+7)+3=1所以既不是工人又不是学生的青年有1名。10/31/202458DiscreteMath.,YanxiuSheng实例例2

求1到1000之间（包含1和1000在内）既不能被5和6整除，也不能被8整除的数有多少个？解：S={x|x

Z,1x1000},

如下定义S

的3个子集A,B,C：

A={x|x

S,5|x}，

B={x|x

S,6|x}，

C={x|x

S,8|x}10/31/202459DiscreteMath.,YanxiuSheng例2（续）对上述子集计数：

|S|=1000,|A|=

1000/5

=200,|B|=1000/6=133，

|C|=1000/8

=125,|AB|=1000/30

=33,|BC|=1000/40