離散數(shù)學(xué)集合概念表示法

離散數(shù)學(xué)集合概念表示法集合論“一切數(shù)學(xué)成果可建立在集合論基礎(chǔ)上”這一發(fā)現(xiàn)使數(shù)學(xué)家們?yōu)橹兆怼?900年,國(guó)際數(shù)學(xué)家大會(huì)上,法國(guó)著名數(shù)學(xué)家龐加萊就曾興高采烈地宣稱:“………借助集合論概念,我們可以建造整個(gè)數(shù)學(xué)大廈……今天,我們可以說(shuō)絕對(duì)得嚴(yán)格性已經(jīng)達(dá)到了……”可就是,好景不長(zhǎng)。1903年,一個(gè)震驚數(shù)學(xué)界得消息傳出:集合論就是有漏洞得！這就就是英國(guó)數(shù)學(xué)家羅素提出得著名得羅素悖論。

理發(fā)師悖論(羅素悖論)20世紀(jì)英國(guó)著名哲學(xué)家、數(shù)學(xué)家羅素提出一個(gè)著名得悖論——“理發(fā)師難題”,其內(nèi)容如下:

西班牙得塞維利亞有一個(gè)理發(fā)師,這位理發(fā)師有一條極為特殊得規(guī)定:她只給那些“不給自己刮胡子”得人刮胡子。羅素悖論羅素構(gòu)造了一個(gè)集合S:S由一切不就是自身元素得集合所組成。羅素問(wèn):S就是否屬于S呢？如果S屬于S,根據(jù)S得定義,S就不屬于S;反之,如果S不屬于S,同樣根據(jù)定義,S就屬于S。無(wú)論如何都就是矛盾得。G、弗雷格在收到羅素介紹這一悖論得信后傷心地說(shuō):“一個(gè)科學(xué)家所遇到得最不合心意得事莫過(guò)于就是在她得工作即將結(jié)束時(shí),其基礎(chǔ)崩潰了。羅素先生得一封信正好把我置于這個(gè)境地。”可以說(shuō),這一悖論就象在平靜得數(shù)學(xué)水面上投下了一塊巨石,而她所引起得巨大反響則導(dǎo)致了第三次數(shù)學(xué)危機(jī)。危機(jī)產(chǎn)生后,數(shù)學(xué)家紛紛提出自己得解決方案:人們希望能夠通過(guò)對(duì)康托爾得集合論進(jìn)行改造,通過(guò)對(duì)集合定義加以限制來(lái)排除悖論,這就需要建立新得原則?！斑@些原則必須足夠狹窄,以保證排除一切矛盾;另一方面又必須充分廣闊,使康托爾集合論中一切有價(jià)值得內(nèi)容得以保存下來(lái)?！?908年,策梅羅在這一原則基礎(chǔ)上提出第一個(gè)公理化集合論體系,后來(lái)經(jīng)其她數(shù)學(xué)家改進(jìn),稱為ZF系統(tǒng)。這一公理化集合系統(tǒng)很大程度上彌補(bǔ)了康托爾樸素集合論得缺陷。公理化集合系統(tǒng)得建立,成功排除了集合論中出現(xiàn)得悖論,從而比較圓滿地解決了第三次數(shù)學(xué)危機(jī)。集合論第3章集合和關(guān)系第4章函數(shù)第三章集合與關(guān)系

本章主要講授集合論得基本知識(shí),包括集合運(yùn)算、包含排斥原理、笛卡爾積、關(guān)系及其性質(zhì)、關(guān)系得運(yùn)算、特殊關(guān)系(包括等價(jià)關(guān)系、相容關(guān)系、序關(guān)系)等。 重點(diǎn)就是集合得運(yùn)算、關(guān)系及其表示、關(guān)系得性質(zhì)、關(guān)系得閉包、等價(jià)關(guān)系、偏序關(guān)系。難點(diǎn)就是關(guān)系得性質(zhì)、等價(jià)關(guān)系、偏序關(guān)系得證明。3-1集合得概念和表示法

組成集合得對(duì)象稱為集合得成員(member)或元素(element)。

集合就是一些確定得、作為整體識(shí)別得、互相區(qū)別得對(duì)象得總體。一、集合得基本概念

一般用大寫字母表示集合,用小寫字母表示元素。例如A表示一個(gè)集合,a表示元素,如果a就是A得元素,記為:a

A,讀作“a屬于A”、“a就是A得元素”、“a就是A得成員”、“a在A之中”、“A包含a”。如果a不就是A得元素,記為:a

A

,讀作“a不屬于A”?？占椭缓杏邢薅鄠€(gè)元素得集合稱為有限集(finitesets),否則稱為無(wú)限集(infinitesets)。有限集合中元素得個(gè)數(shù)稱為集合得基數(shù)(cardinality)。集合A得基數(shù)表示為

A

。集合得分類大家有疑問(wèn)的，可以詢問(wèn)和交流可以互相討論下，但要小聲點(diǎn)二、集合得三種表示方式:(l)列舉法將集合得元素列舉出來(lái)。

(2)描述法利用一項(xiàng)規(guī)則(一個(gè)謂詞公式),描述集合中得元素得共同性質(zhì),以便決定某一物體就是否屬于該集合。(3)歸納法用遞歸方法定義集合。1、列舉法:將集合得元素列舉出來(lái)例: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就是中國(guó)得一個(gè)省}說(shuō)明:1、描述法中C={x|1

x

5,x

R}與C={y|1

y

5,x

R}表示同一個(gè)集合。2、集合中元素就是無(wú)序得。{a,b,c},{b,c,a},{c,a,b}表示同一個(gè)集合。3、集合中得元素可能也就是集合,例:A={1,2,{1},{1,2,3}},1

A,{1}

A。三、集合得關(guān)系1、相等關(guān)系相等(外延性公理):兩個(gè)集合就是相等得,當(dāng)且僅當(dāng)她們有相同得成員。兩個(gè)集合A和B相等,記作A=B,兩個(gè)集合不相等,記作A

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

I}{0,1}

{1,2}

抽象原理

對(duì)任意謂詞公式P(x),均存在集合S,使得

S={x

P(x)}

兩個(gè)集合A和

B相等當(dāng)且僅當(dāng)她們具有相同得元素。即對(duì)任意集合A、B,

A=B

x(x

A

x

B)

外延公理

概括公理

對(duì)任意個(gè)體域,任一謂詞公式都確定一個(gè)以該域中得對(duì)象為元素得集合。即對(duì)給定個(gè)體域U,對(duì)任意謂詞公式P(x),存在集合S,使得

S＝{x

x

U∧P(x)}2、包含關(guān)系(子集)定義3-1、1設(shè)A、B就是任意兩個(gè)集合,如果A得每一個(gè)元素都就是B得元素,則稱集合A就是集合B得子集合(或子集,subsets),或稱A包含在B內(nèi),記為A

B;或稱B包含A,記為B

A

。即

A

B

x(x

A

x

B)

設(shè)A,B,C為任意集合,根據(jù)定義,顯然有:包含關(guān)系具有自反性:A

A

包含關(guān)系具有傳遞性:若A

B且B

C,則A

C。

注:可能A

B或B

A

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

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

D={3}，F(xiàn)={1，4}，則B

A，C

A，D

C，F(xiàn)

A

n元集、m元子集含有n個(gè)元素得集合稱為n元集。她得含有m個(gè)元素得子集稱為她得m元子集。四、特殊得集合1、空集定義3-1、3:不含任何元素得集合稱為空集,記作

。

={x|p(x)

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

R}就是空集。注意:

{

},

{

}定理3-1、2:對(duì)于任意一個(gè)集合A,

A。證明:反證法,假設(shè)存在一個(gè)集合A,使得

A為假。則存在x

且x

A,這與空集得定義矛盾,所以

A,空集就是任意集合得子集。推論:空集就是唯一得。證明:設(shè)

1,

2就是兩個(gè)空集,則

1

2,

2

1,得

1=

2,所以空集就是唯一得。2、全集定義3-1、4:在一定范圍內(nèi),如果所有集合均就是某一集合得子集,則稱該集合為全集。記作E。

E={x|p(x)

p(x)}3、冪集定義3-1、5:給定集合A,由A得所有子集為元素組成得集合稱為A得冪集,記作

(A)或2A。

(A)={u|u

A}例:設(shè)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個(gè),即空集

,1元子集有Cn1個(gè),2元子集有Cn2個(gè),…,n-1元子集有Cnn-1個(gè),n元子集有Cnn個(gè)。所以A得子集個(gè)數(shù)為:Cn0+Cn1+Cn2+…+Cnn=2n。有:定理3-1、3:如果有限集A有n個(gè)元素,其冪集

(A)有2n個(gè)元素。例:A={a,},判斷下列結(jié)論就是否正確。(1)

A,(2)

A,(3){}

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

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

A,結(jié)論(1)、(2)、(3)、(5)、(8)正確。上次課集合得概念集合得表示集合得關(guān)系特殊得集合:空集、全集、冪集3-2集合得運(yùn)算及其性質(zhì)一、集合得運(yùn)算1、交定義3-2、1:設(shè)任意兩個(gè)集合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:設(shè)A就是平面上所有矩形得集合,B就是平面上所有菱形得集合,A

B就是所有正方形得集合。例3:設(shè)A就是所有能被K整除得整數(shù)得集合,B就是所有能被L整除得整數(shù)得集合,A

B就是所有能被K與L最小公倍數(shù)整除得整數(shù)得集合。舉例性質(zhì):a)AA=Ab)A=c)AE=Ad)AB=BAe)(AB)C=A(BC)f)ABA,ABB例題4:設(shè)AB,求證ACBC。證明:對(duì)任一個(gè)x

AC,則x

A且x

C,因?yàn)橛蠥B,若x

A,則x

B,所以x

B且x

C,故x

BC。因此ACBC。舉例2、并集定義3-2、2:設(shè)任意兩個(gè)集合A和B,所有屬于A或?qū)儆贐得元素組成得集合,稱為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:設(shè)A就是奇數(shù)集合,B就是偶數(shù)集合,A

B就是整數(shù)集合,AB=。舉例性質(zhì):a)AA=Ab)AE=Ec)A=Ad)AB=BAe)(AB)C=A(BC)f)AAB,BAB例題3:設(shè)AB,CD,求證ACBD。證明:對(duì)任一x

AC,則x

A或x

C,(1)若x

A,則x

B,故x

BD;(2)若x

C,則x

D,故x

BD。因此ACBD。舉例定理3-2、1設(shè)A,B,C為三個(gè)集合,則下列分配律成立。a)A(BC)=(AB)(AC)b)A(BC)=(AB)(AC)證明:a)設(shè)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設(shè)A,B為任意兩個(gè)集合,則下列吸收律成立。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,當(dāng)且僅當(dāng)AB=B或AB=A。證明:若AB,對(duì)任意xA必有xB,(1)對(duì)任意xAB,則xA或xB,即xB,所以ABB。(2)又BAB,因此得到AB=B。反之,若AB=B,因?yàn)锳AB,所以AB。同理可證得AB=A3、差集、補(bǔ)集定義3-2、3:設(shè)A、B就是任意兩個(gè)集合,所有屬于A而不屬于B得元素組成得集合稱為B對(duì)A得補(bǔ)集,或相對(duì)補(bǔ),(或A和B差集)記作A-B。

A-B={x|xA∧xB}文氏圖定義3-2、4:設(shè)E為全集,任一集合A關(guān)于E得補(bǔ),稱為A得絕對(duì)補(bǔ),記作

A。

A=E-A={x|xE∧xA}文氏圖性質(zhì):a)(A)=Ab)E=c)=Ed)AA=Ee)AA=定理3-2、4設(shè)A,B為任意兩個(gè)集合,則下列關(guān)系式成立。a)(AB)=ABb)(AB)=AB定理3-2、5設(shè)A,B為任意兩個(gè)集合,則下列關(guān)系式成立。a)A-B=ABb)A-B=A-(AB)定理3-2、6設(shè)A,B,C為三個(gè)集合,則A

(B-C)=(A

B)-(A

C)定理3-2、7設(shè)A,B為任意兩個(gè)集合,若AB,則a)

B

Ab)(B-A)A=B4、對(duì)稱差定義3-2、5:設(shè)A、B就是任意兩個(gè)集合,集合A和B得對(duì)稱差,其元素或?qū)儆贏,或?qū)儆贐,但不能既屬于A又屬于B,記作A

B。

A

B=(A-B)(B-A)文氏圖性質(zhì):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:設(shè)A1,A2為有限集合,其元素個(gè)數(shù)分別為|A1|,|A2|,則|A1

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

A2|,此定理被稱作包含排斥原理。證明:a)當(dāng)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|解:設(shè)A為從1到500得整數(shù)中,能被3除盡得數(shù)得集合。

B為從1到500得整數(shù)中,能被5除盡得數(shù)得集合。則

A

=[500/3]=166([x]表示不超過(guò)x得最大整數(shù))

B

=[500/5]=100

A

B

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

A

B

=

A

+

B

-

A

B

=166+100-33=233即從1到500得整數(shù)中,能被3或5除盡得數(shù)有233個(gè)。

例1:求從1到500得整數(shù)中,能被3或5除盡得數(shù)得個(gè)數(shù)。解:設(shè)職員和學(xué)生得集合分別就是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名青年既不就是職員又不就是學(xué)生。例2:在20名青年中有10名就是公司職員,12名就是學(xué)生,其中5名既就是職員又就是學(xué)生,問(wèn)有幾名既不就是職員,又不就是學(xué)生。例題3假設(shè)在10名青年中有5名就是工人,7名就是學(xué)生,其中兼具工人和學(xué)生雙重身份得青年有3名,問(wèn)有幾名既不就是工人又不就是學(xué)生。解:設(shè)工人得集合為W,學(xué)生得集合為S。則根據(jù)題設(shè)有|E|=1