《离散数学课件》1-2集合的基本概念

1

集合论2集合论局部第6章集合第7章〔二元〕关系第8章函数3/69康托集合论——公理集合论德国数学家康托(G.Cantor)朴素集合论:十九世纪七十年代悖论公理集合论:在二十世纪初数学思想的最惊人的产物，在纯粹理性的范畴中人类活动的最美的表现。可能是这个时代所能夸耀的最巨大的工作。4/69康托GeorgCantor，1845－19181845年3月3日生于彼得堡。1856年全家迁居法兰克福。先后就学于苏黎世大学、哥廷根大学、法兰克福大学和柏林大学，主要学习哲学、数学和物理。在柏林大学，他受到著名分析学家魏尔斯特拉斯的影响，对纯粹数学产生了兴趣。1867年，他以求不定方程ax2+by2+cz2=0的整数解〔其中，a、b、c为任意整数〕的博士论文获哲学博士学位。5/69罗素〔BertrandArthurWilliamRussell，1872-1970〕著名的英国数学家、逻辑学家。1890年剑挢大学学习数学和哲学。1901年开始与怀特海(Whitehead)合作，经过10年的奋战，写成3卷本巨著《数学原理》。罗素还是2l世纪最有影响的哲学家之一。1920年应邀来中国讲学一年。1950年获诺贝尔文学奖。1964年创设罗素和平基金会。6/69理发师难题西班牙的塞维利亚有一个理发师，这位理发师有一条极为特殊的规定：他只给那些“不给自己刮胡子”的人刮胡子。7/69罗素悖论与第三次数学危机“数学大厦的基石”竟然出现了明显的“裂缝”，那么人类消耗数千年心血建立起来的“数学殿堂”，会不会倒塌呢？一时间，数学界众说纷纭，这就是数学史上著名的“第三次数学危机”。“裱糊匠”:希尔伯特……蔡梅罗:找到摆脱困境的方法8/69ZF公理系统数学家们创造了公理化集合论，明确提出形成集合的原那么，且规定只能按照这些确定的原那么形成集合，以防止的一些集合论的悖论。最著名的一个系统是由蔡梅罗(ErnstZermelo)1908年提出，后经弗兰克尔(AbrahamA.Fraenkel)等人改进而建立的。人们称之为ZF系统。9/69第二次数学危机:关于微积分在牛顿和莱布尼茨发现了微积分的年代里,老是有那么几个敌对分子跟他们作对,其中有一位爱尔兰的大主教贝克莱就讥讽牛顿的“一刹那”是“已死量的幽灵”。还有一位意大利的数学教授格兰蒂把

1/2=1-1+1-1+...=(1-1)+(1-1)+...=0这样的式子看作是"从虚无创造万有"等等不一而足.

10/69第一次数学危机:发现了“无理数”

毕达格拉斯的一个弟子发现边长为1的正方形的对角线是不能用任何比例来表示的。对于毕氏学派来说,这是天大的罪过,结果被扔进海里喂了鲨鱼。11/69第六章集合6.1集合的根本概念6.1.1集合的定义6.1.2集合的表示6.1.3集合的包含关系6.1.4集合的特点12/696.1集合的根本概念集合是最根本的数学概念之一，由于它太根本了，所以不能用更根本的概念来定义它。集合是不能精确定义的数学概念。但是，这并不影响我们去理解它和掌握它。13/69每一个人都知道许多集合逻辑值T,F可以组成一个集合,记为{T,F},真值集。数0，1可以组成一个集合,记为{0,1},真值集。

数0,1,2,3,4,5,6,7,8,9可以组成一个集合,阿拉伯数字集。数0，1,3,

4可以组成一个集合。二十六个英文字母可以组成一个集合,英文字母集例如：14/69一、集合与元素集合：某些确定的、能够区分的对象的聚合。元素：组成一个集合的那些对象称为这一集合的元素和成员。用大写字母代表集合，用小写英文字母代表集合的元素。15/69常用的集合

N代表自然数集,{0,1,2,…}

Z代表整数集,{…,-2,-1,0,1,2,…}

Q代表有理数集

R代表实数集

R+={x│x∈R,x>0}是表示非负的实数集R2={(x,y)│x,y∈R}是XOY坐标平面上点的集合。16/69集合与元素的关系如果a是集合A的一个元素，就叫做a属于集合A，这时记为a∊A

。如果a不是集合A中的一个元素，就叫做a不属于A，这时记为a∉A。对于任给的一个对象a和任给的一个集合A，或者a属于A，或者a不属于A，二者必居其一，不可得兼。

隶属关系的层次结构例A={a,{b,c},d,{{d}}}{b,c}

Ab,c

A{{d}}A{d}Ad

A

18/69二、集合的表示(1)列举出这个集合中的所有元素。 ♦A={a,b,c}

♦B={1,3,5}(2)利用元素所具有的性质来表示。 ♦D={x│x2-3x+2=0,x∈R}

♦E={x│x是南京理工大学学生}一般地，S={a│a具有性质ξ}表示

a∊

S当且仅当a具有性质ξ

。描述法枚举法19/69罗素(B.Russell)悖论S={A│A是不以自身为元素的集合,即A∉A}S是集合吗？如果我们假定S是集合，那么S是自己的元素，

S不是自己的元素，二者居其一且只居其一。容易说明我们假定S是集合是错误的。如果S∊S，那么与性质矛盾；如果S∉S，那么S满足性质，矛盾。20/69定义1：A,B是二个集合，对于任意的x，假设x∊A，那么x∊B，我们说集合A是集合B的子集，也说集合B包含集合A，记为A⊆B。假设A不是B的子集,记为A⊄B。也说B不包含A。三、集合的包含关系21/69例{1，2}⊆{1，2，3}{1，3}⊆{1，3，2，4}{1}⊆{1，2}1⊄{1，2}1∈{1，2}22/69例：是否存在这样两个集合，其中一个既是另一个的子集，又是它的元素？{1}∈{1，{1}}

{1}⊆{1，{1}}23/69空集Ø设K是一个集合，K={x∊R│x2+1=0}

。我们都知道集合K中什么元素也没有。这样没有一个元素的集合称为空集。我们用Ø来表示空集合。24/69命题1(p76)A是任意集合，Ø是空集，那么

①A⊆A

②Ø⊆A证明：①对于任意的x，假设x∊A,那么显然有x∊A，所以A⊆A.用反证法：假设Ø不包含于A，那么存在x，x∊Ø，但x∉A。显然这与Ø是空集矛盾。故Ø⊆A。25/69定义2(p76)A,B是两个集合，假设A⊆B，且B⊆A,那么说A与B是相等的两个集合，记为A=B。假设A⊆B且A≠B，说A是B的真子集，记为A⊂B。26/69命题2：空集是唯一的。证明：设Ø1，Ø2

是两个空集合。由命题1，Ø1⊆Ø2

且Ø2⊆Ø1故Ø1=Ø2

27集合之间的关系包含〔子集〕ABx(xAxB)不包含A⊈Bx(xAxB)相等A=BABBA不相等AB真包含ABABAB不真包含AB注意和是不同层次的问题28/69四、集合的特点仅考虑集合所包含的不同的元素，也就是说集合中元素重复出现没有意义。例如：

{a,a,b,c,c},

{a,b,c}

是相等的两个集合。互异性29/69集合的特点集合中的元素没有任何方式的顺序。例如：

{a,b,c}{c,a,b}

是相等的两个集合。无序性30/69集合的特点对集合中的元素没有任何的限制，也就是一个集合中的元素之间彼此独立，可以毫不相干；一个集合也可以是另一个集合的元素。例如：

{a,2,华盛顿,中国人}

{a,{a},Ø}

都是两个确定的集合。确定性集合的表示方法集合的特性集合与元素的关系集合与集合的关系3132/696.2集合的根本运算6.2.1集合的并、交、差6.2.2集合的对称差6.2.3文氏图6.2.4集合的幂集合6.2.5多个集合的并与交33/69并运算：A∪BA∪B={x│x∊A或x∊B}其元素是所有的或者属于集合A，或者属于集合B的元素组成。

A∪B34/69交运算：A∩BA∩B={x│x∊A且x∊B}其元素是所有的既属于集合A，又属于集合B的元素组成。

A∩B35/69差运算：A–BA–B={x│x∊A且x∉B}其元素是所有的属于集合A，但不属于集合B的元素组成。

A–B36/69例设A、B是两个任意集合，那么以下两条件等价A∪B=AB⊆A证明：①②对于任意的x∊B,有x∊A∪B=A， 即x(xBxA) 于是B⊆A。②①显然，A⊆A∪B。 对于任意的x∊A∪B,那么x∊A或x∊B，由于B⊆A，故总有x∊A，即证得A∪B⊆A。因此A∪B=A。37/69例设A、B是两个任意集合，那么以下两条件等价A∩B=BB⊆A证明：①②对于任意的x∊B,有 x∊B=A∩B， 于是x∊A,因此证得B⊆A。②① 显然，A∩B⊆B。 对于任意的x∊B,那么由于B⊆A，故x∊A，从而x∊A∩B，即证得B⊆A∩B。因此A∩B=B。38/69集合运算性质定理：设A、B、C是三个任意集合，那么：幂等律A∪A=AA∩A=A交换律A∪B=B∪AA∩B=B∩A结合律A∪〔B∪C〕=〔A∪B〕∪CA∩〔B∩C〕=〔A∩B〕∩C分配律A∪〔B∩C〕=〔A∪B〕∩〔A∪C〕A∩〔B∪C〕=〔A∩B〕∪〔A∩C〕39/69例试证：A∪(B∩C)=(A∪B)∩(A∪C)证明：1、对于任意的x，假设x∊A∪(B∩C)，那么x∊A，或x∊B∩C。当x∊A，那么 x∊A∪B且x∊A∪C， 于是 x∊(A∪B)∩(A∪C)； 当x∊B∩C，那么x∊B且x∊C，就有 x∊A∪B,且x∊A∪C， 于是 x∊(A∪B)∩(A∪C)。 故A∪(B∩C)⊆(A∪B)∩(A∪C)2、再证明：(A∪B)∩(A∪C)⊆A∪(B∩C)假设x∊(A∪B)∩(A∪C)，那么x∊A∪B,且x∊A∪C由x∊A∪B得 x∊A或x∊B；〔1〕由x∊A∪C得 x∊A或x∊C。〔2〕于是，当x∊A，有 x∊A∪(B∩C)；当x∉A，由(1)和(2)，x∊B且x∊C，有 x∊B∩C，所以x∊A∪(B∩C)。故(A∪B)∩(A∪C)⊆A∪(B∩C)综上知，A∪〔B∩C〕=〔A∪B〕∩〔A∪C〕。41/69证明：对于任意的x，x∊A∪(B∩C)，x∊Ax∊B∩Cx∊A〔x∊Bx∊C〕〔x∊Ax∊B〕〔x∊Ax∊C〕x∊A∪Bx∊A∪Cx∊〔A∪B∩x∊A∪C〕

例试证：A∪(B∩C)=(A∪B)∩(A∪C)42/69例1(p78)(A-B)∪(A-C)=A在何条件下成立？

解：根据分析当且仅当A∩(B∩C)=Ø时,等式成立。首先，假假设(A-B)∪(A-C)=A,要证明A∩(B∩C)=Ø。用反证法。假设A∩B∩C≠Ø,那么∃x∊A∩B∩C,所以x∊A，x∊B，x∊C。由x∊A，x∊B,有x∉A-B,又由x∊A，x∊C,有x∉A-C,所以有x∉(A-B)∪(A-C)=A。矛盾说明A∩B∩C=Ø。分析：A的元素a既是B的元素、也是C的元素，那么等式不成立。43/69再证，假设A∩(B∩C)=Ø,那么(A-B)∪(A-C)=A成立。1、对于任意的x∊(A-B)∪(A-C),那么有x∊A-B或x∊A-C,即有x∊A且x∉B,或x∊A且x∉C,于是有x∊A,所以(A-B)∪(A-C)⊆A。2、对于任意的x∊A,假设x∉B，那么有x∊A-B,进而x∊(A-B)；假设x∊B,那么x∊A∩B，由于A∩(B∩C)=Ø,那么x∉C,即有x∊A-C,进而x∊(A-B)∪(A-C)；所以有A⊆(A-B)∪(A-C)。综合得到(A-B)∪(A-C)=A成立。44/69二、对称差：A⊕B

A⊕B={x│x∊A且x∉B,或x∊B且x∉A}其元素是所有的或者属于A不属于B，或者属于B不属于A。

A⊕B由定义，不难知：A⊕B=(A–B)∪(B–A)A⊕A=ØA⊕Ø=A45/69命题1(p79)A⊕B=(A∪B)–(A∩B)

证明：对于任何一个x,x∊A⊕Bx∊A–Bx∊B–A。〔x∊Ax∉B〕〔x∊Bx∉A〕〔x∊Ax∊B〕〔x∊Ax∉A〕〔x∉Bx∊B〕〔x∉Bx∉A〕〔x∊Ax∊B〕〔x∊Bx∊A〕〔x∊Ax∊B〕〔x∊Bx∊A〕〔x∊A∪B〕〔x∊A∩B〕〔x∊A∪B〕x∉A∩Bx∊(A∪B)–(A∩B)46/69命题3(p79)〔A⊕B〕⊕C=A⊕〔B⊕C〕

47/69命题3(p79)〔A⊕B〕⊕C=A⊕〔B⊕C〕

证：记 P={x∊A且x∉B且x∉C}, Q={x∊B且x∉A且x∉C}, S={x∊C且x∉A且x∉B}, T={x∊A且x∊B且x∊C},那么容易验证：(A⊕B)⊕C=P∪Q∪S∪T A⊕(B⊕C)=P∪Q∪S∪T 所以结论得证： (A⊕B)⊕C=A⊕(B⊕C)PQST48/69例2(p80)A⊕B=A⊕C，证明B=C。证明：因为A⊕B=A⊕C所以A⊕(A⊕B)=A⊕(A⊕C)从而有〔A⊕A〕⊕B=〔A⊕A〕⊕C即Ø⊕B=Ø⊕C故B=C49/69三、幂集定义3：A是一个集合，存在一个集合，它是由A的所有子集为元素构成的集合，称它为集合A的幂集合，记为ρ(A)

，也记为P(A)、2A

。即ρ(A)

={x|x

A}例设A={0,1}，那么ρ(A)={Ø,{0},{1},{0,1}}设B={a,b,c}，那么ρ(B)={Ø,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}50/69例P(

)={

}，

P({

})={

,{

}}

P({1,{2,3}})={,{1},{{2,3}},{1,{2,3}}}计数如果|A|=n，那么|P(A)|=2n51/69四、有限并与交设Pi(1≤i≤k)是k个任意集合,A1

A2

…Ak=={x|x

A1

x

A2

…

x

Ak}A1

A2

…Ak=={x|x

A1

x

A2

…

x

Ak}52/69推论(p67)设A,Pi(1≤i≤k)是k+1个集合,那么〔分配率对有限并、有限交都成立。〕集合根本运算的定义并

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)

53幂集ρ(A)

={x|x

A}集合的运算小结54/696.3全集和集合的补6.3.1全集、集合的补集6.3.2根本运算定理55/69

一、全集定义:

我们在研究某一个具体问题时，往往规定一个集合，使所涉及的集合都是它的子集合，称这个集合为全集，记为U(或E)。全集是个有相对性的概念，不同的问题，可以规定不同的全集。56/69

二、补运算：Ā、

A

定义：设A是一个集合,U是全集合，我们称集合U–A为A的补集，记为Ā或

A

，即有：

Ā={x│x∉A且x∊U}UAĀ57/69定理1A是一个任意集合，那么

A∪Ø

=AA∩U=A58/69定理2A是一个任意集合，那么A∪Ā=UA∩Ā

=Ø59/69定理3Ā=B当且仅当A∪B=U且A∩B=Ø证明： “”由定理1结论成立。 “”设A∪B=U且A∩B=Ø，那么B=B∩U=B∩(A∪Ā)=(B∩A)∪(B∩Ā)=Ø∪(B∩Ā)=(A∩Ā)∪(B∩Ā)=(A∪B)∩Ā=U∩Ā=Ā任一集合的补集合是唯一的。60/69推论：设A是任意一个集合，那么61/69定理4

德·摩根定律三、运算定律

(A

B)=A

B

(A

B)=A

B62证明：

(A∩B)=A∪

B对任意的x，x∊(A∩B)x∊Ux∉A∩B。x∊U〔x∊Ax∊B〕x∊U〔x∊Ax∊B〕x∊U