离散数学集合概念表示法

离散数学集合概念表示法集合论“一切数学成果可建立在集合论基础上”这一发现使数学家们为之陶醉。1900年,国际数学家大会上,法国著名数学家庞加莱就曾兴高采烈地宣称:“………借助集合论概念,我们可以建造整个数学大厦……今天,我们可以说绝对得严格性已经达到了……”可就是,好景不长。1903年,一个震惊数学界得消息传出:集合论就是有漏洞得！这就就是英国数学家罗素提出得著名得罗素悖论。

理发师悖论(罗素悖论)20世纪英国著名哲学家、数学家罗素提出一个著名得悖论——“理发师难题”,其内容如下:

西班牙得塞维利亚有一个理发师,这位理发师有一条极为特殊得规定:她只给那些“不给自己刮胡子”得人刮胡子。罗素悖论罗素构造了一个集合S:S由一切不就是自身元素得集合所组成。罗素问:S就是否属于S呢？如果S属于S,根据S得定义,S就不属于S;反之,如果S不属于S,同样根据定义,S就属于S。无论如何都就是矛盾得。G、弗雷格在收到罗素介绍这一悖论得信后伤心地说:“一个科学家所遇到得最不合心意得事莫过于就是在她得工作即将结束时,其基础崩溃了。罗素先生得一封信正好把我置于这个境地。”可以说,这一悖论就象在平静得数学水面上投下了一块巨石,而她所引起得巨大反响则导致了第三次数学危机。危机产生后,数学家纷纷提出自己得解决方案:人们希望能够通过对康托尔得集合论进行改造,通过对集合定义加以限制来排除悖论,这就需要建立新得原则。“这些原则必须足够狭窄,以保证排除一切矛盾;另一方面又必须充分广阔,使康托尔集合论中一切有价值得内容得以保存下来。”1908年,策梅罗在这一原则基础上提出第一个公理化集合论体系,后来经其她数学家改进,称为ZF系统。这一公理化集合系统很大程度上弥补了康托尔朴素集合论得缺陷。公理化集合系统得建立,成功排除了集合论中出现得悖论,从而比较圆满地解决了第三次数学危机。集合论第3章集合和关系第4章函数第三章集合与关系

本章主要讲授集合论得基本知识,包括集合运算、包含排斥原理、笛卡尔积、关系及其性质、关系得运算、特殊关系(包括等价关系、相容关系、序关系)等。 重点就是集合得运算、关系及其表示、关系得性质、关系得闭包、等价关系、偏序关系。难点就是关系得性质、等价关系、偏序关系得证明。3-1集合得概念和表示法

组成集合得对象称为集合得成员(member)或元素(element)。

集合就是一些确定得、作为整体识别得、互相区别得对象得总体。一、集合得基本概念

一般用大写字母表示集合,用小写字母表示元素。例如A表示一个集合,a表示元素,如果a就是A得元素,记为:a

A,读作“a属于A”、“a就是A得元素”、“a就是A得成员”、“a在A之中”、“A包含a”。如果a不就是A得元素,记为:a

A

,读作“a不属于A”。空集和只含有有限多个元素得集合称为有限集(finitesets),否则称为无限集(infinitesets)。有限集合中元素得个数称为集合得基数(cardinality)。集合A得基数表示为

A

。集合得分类大家有疑问的，可以询问和交流可以互相讨论下，但要小声点二、集合得三种表示方式:(l)列举法将集合得元素列举出来。

(2)描述法利用一项规则(一个谓词公式),描述集合中得元素得共同性质,以便决定某一物体就是否属于该集合。(3)归纳法用递归方法定义集合。1、列举法:将集合得元素列举出来例:A={a,b,c,d},A1={1,3,5,7,9,……}使用列举法,须列出足够多得元素以反映集合中成员得特征。如:B={2,4,8,……}若x=2n,则

B={2,4,8,16,32,……}若x=2+n(n-1),则

B={2,4,8,14,22,……}2、描述法:A={x|P(x)}或A={x:P(x)}例:C={x|1

x

5,x

R},

D={(x,y)|x2+y21,x,y

R}F={x|x就是中国得一个省}说明:1、描述法中C={x|1

x

5,x

R}与C={y|1

y

5,x

R}表示同一个集合。2、集合中元素就是无序得。{a,b,c},{b,c,a},{c,a,b}表示同一个集合。3、集合中得元素可能也就是集合,例:A={1,2,{1},{1,2,3}},1

A,{1}

A。三、集合得关系1、相等关系相等(外延性公理):两个集合就是相等得,当且仅当她们有相同得成员。两个集合A和B相等,记作A=B,两个集合不相等,记作A

B。{0,1}={x|x(x2-2x+1)=0,x

I}{0,1}

{1,2}

抽象原理

对任意谓词公式P(x),均存在集合S,使得

S={x

P(x)}

两个集合A和

B相等当且仅当她们具有相同得元素。即对任意集合A、B,

A=B

x(x

A

x

B)

外延公理

概括公理

对任意个体域,任一谓词公式都确定一个以该域中得对象为元素得集合。即对给定个体域U,对任意谓词公式P(x),存在集合S,使得

S＝{x

x

U∧P(x)}2、包含关系(子集)定义3-1、1设A、B就是任意两个集合,如果A得每一个元素都就是B得元素,则称集合A就是集合B得子集合(或子集,subsets),或称A包含在B内,记为A

B;或称B包含A,记为B

A

。即

A

B

x(x

A

x

B)

设A,B,C为任意集合,根据定义,显然有:包含关系具有自反性:A

A

包含关系具有传递性:若A

B且B

C,则A

C。

注:可能A

B或B

A

,也可能两者均不成立,不就是两者必居其一。

例：A={1，2，3}，B={1，2}，C={1，3}，

D={3}，F={1，4}，则B

A，C

A，D

C，F

A

n元集、m元子集含有n个元素得集合称为n元集。她得含有m个元素得子集称为她得m元子集。四、特殊得集合1、空集定义3-1、3:不含任何元素得集合称为空集,记作

。

={x|p(x)

p(x)}例如:X={x|x2+1=0,x

R}就是空集。注意:

{

},

{

}定理3-1、2:对于任意一个集合A,

A。证明:反证法,假设存在一个集合A,使得

A为假。则存在x

且x

A,这与空集得定义矛盾,所以

A,空集就是任意集合得子集。推论:空集就是唯一得。证明:设

1,

2就是两个空集,则

1

2,

2

1,得

1=

2,所以空集就是唯一得。2、全集定义3-1、4:在一定范围内,如果所有集合均就是某一集合得子集,则称该集合为全集。记作E。

E={x|p(x)

p(x)}3、幂集定义3-1、5:给定集合A,由A得所有子集为元素组成得集合称为A得幂集,记作

(A)或2A。

(A)={u|u

A}例:设A={1,2,3},写出A得幂集

(A)。解:

(A)={

,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}

一般地如果|A|=n,则:A得0元子集有Cn0=1个,即空集

,1元子集有Cn1个,2元子集有Cn2个,…,n-1元子集有Cnn-1个,n元子集有Cnn个。所以A得子集个数为:Cn0+Cn1+Cn2+…+Cnn=2n。有:定理3-1、3:如果有限集A有n个元素,其幂集

(A)有2n个元素。例:A={a,},判断下列结论就是否正确。(1)

A,(2)

A,(3){}

A(4){}A,(5)aA,(6)a

A,(7){a}A,(8){a}

A,结论(1)、(2)、(3)、(5)、(8)正确。上次课集合得概念集合得表示集合得关系特殊得集合:空集、全集、幂集3-2集合得运算及其性质一、集合得运算1、交定义3-2、1:设任意两个集合A和B,由A和B得所有共同元素组成得集合,称为A和B得交集,记为A

B。

A

B={x|x

A

x

B}文氏图例1:A={0,2,4,6,8,10,12},B={1,2,3,4,5,6},A

B={2,4,6}例2:设A就是平面上所有矩形得集合,B就是平面上所有菱形得集合,A

B就是所有正方形得集合。例3:设A就是所有能被K整除得整数得集合,B就是所有能被L整除得整数得集合,A

B就是所有能被K与L最小公倍数整除得整数得集合。举例性质:a)AA=Ab)A=c)AE=Ad)AB=BAe)(AB)C=A(BC)f)ABA,ABB例题4:设AB,求证ACBC。证明:对任一个x

AC,则x

A且x

C,因为有AB,若x

A,则x

B,所以x

B且x

C,故x

BC。因此ACBC。举例2、并集定义3-2、2:设任意两个集合A和B,所有属于A或属于B得元素组成得集合,称为A和B得并集,记作A

B。

A

B={x|x

A

x

B}文氏图例1:A={1,2,3,4},B={2,4,5},A

B={1,2,3,4,5}例2:设A就是奇数集合,B就是偶数集合,A

B就是整数集合,AB=。举例性质:a)AA=Ab)AE=Ec)A=Ad)AB=BAe)(AB)C=A(BC)f)AAB,BAB例题3:设AB,CD,求证ACBD。证明:对任一x

AC,则x

A或x

C,(1)若x

A,则x

B,故x

BD;(2)若x

C,则x

D,故x

BD。因此ACBD。举例定理3-2、1设A,B,C为三个集合,则下列分配律成立。a)A(BC)=(AB)(AC)b)A(BC)=(AB)(AC)证明:a)设S=A(BC),T=(AB)(AC),若xS,则xA且xBC,即xA且xB或xA且xC,xAB或x

AC即xT,所以ST。反之,若xT,则xAB或x

AC,xA且xB或xA且xC,即xA且xBC,于就是xS,所以TS。因此,S=T。b)证明完全与a)类似。定理3-2、2设A,B为任意两个集合,则下列吸收律成立。a)A(AB)=Ab)A(AB)=A证明:a)A(AB)=(AE)(AB)=A(EB)=AE=Ab)A(AB)=(AA)(AB)=A(AB)=A定理3-2、3AB,当且仅当AB=B或AB=A。证明:若AB,对任意xA必有xB,(1)对任意xAB,则xA或xB,即xB,所以ABB。(2)又BAB,因此得到AB=B。反之,若AB=B,因为AAB,所以AB。同理可证得AB=A3、差集、补集定义3-2、3:设A、B就是任意两个集合,所有属于A而不属于B得元素组成得集合称为B对A得补集,或相对补,(或A和B差集)记作A-B。

A-B={x|xA∧xB}文氏图定义3-2、4:设E为全集,任一集合A关于E得补,称为A得绝对补,记作

A。

A=E-A={x|xE∧xA}文氏图性质:a)(A)=Ab)E=c)=Ed)AA=Ee)AA=定理3-2、4设A,B为任意两个集合,则下列关系式成立。a)(AB)=ABb)(AB)=AB定理3-2、5设A,B为任意两个集合,则下列关系式成立。a)A-B=ABb)A-B=A-(AB)定理3-2、6设A,B,C为三个集合,则A

(B-C)=(A

B)-(A

C)定理3-2、7设A,B为任意两个集合,若AB,则a)

B

Ab)(B-A)A=B4、对称差定义3-2、5:设A、B就是任意两个集合,集合A和B得对称差,其元素或属于A,或属于B,但不能既属于A又属于B,记作A

B。

A

B=(A-B)(B-A)文氏图性质:a)A

B=BAb)A=Ac)A

A=

d)A

B=(AB)(AB)e)(A

B)C=A(BC)3-3包含排斥原理(容斥原理)包含排斥原理1、定理3-3、1:设A1,A2为有限集合,其元素个数分别为|A1|,|A2|,则|A1

A2|=|A1|+|A2|-|A1

A2|,此定理被称作包含排斥原理。证明:a)当A1

A2=

,则|A1

A2|=|A1|+|A2|b)若A1

A2

,则|A1|=|A1

～A2|+|A1

A2|,|A2|=|～A1

A2|+|A1

A2|所以|A1|+|A2|=|A1

～A2|+|A1

A2|+|～A1

A2|+|A1

A2|=|A1

～A2|+|～A1

A2|+2|A1

A2|而|A1

～A2|+|～A1

A2|+|A1

A2|=|A1

A2|故|A1

A2|=|A1|+|A2|-|A1

A2|解:设A为从1到500得整数中,能被3除尽得数得集合。

B为从1到500得整数中,能被5除尽得数得集合。则

A

=[500/3]=166([x]表示不超过x得最大整数)

B

=[500/5]=100

A

B

=[500/(3*5)]=33由包含排斥原理:

A

B

=

A

+

B

-

A

B

=166+100-33=233即从1到500得整数中,能被3或5除尽得数有233个。

例1:求从1到500得整数中,能被3或5除尽得数得个数。解:设职员和学生得集合分别就是A和B。由已知条件

A

=10,

B

=12,

A

B

=5,有

A

B

=

A

+

B

-

A

B

=10+12-5=17,则

(A

B)

=

E

-

A

B

=20-17=3。有3名青年既不就是职员又不就是学生。例2:在20名青年中有10名就是公司职员,12名就是学生,其中5名既就是职员又就是学生,问有几名既不就是职员,又不就是学生。例题3假设在10名青年中有5名就是工人,7名就是学生,其中兼具工人和学生双重身份得青年有3名,问有几名既不就是工人又不就是学生。解:设工人得集合为W,学生得集合为S。则根据题设有|E|=1