集合論-離散數(shù)學(xué)第五章

1第五章集合的基本概念及其運(yùn)算§5.1集合與元素§5.2集合間的相等和包含關(guān)系§5.3冪集§5.4集合的運(yùn)算§5.5有窮集的計(jì)數(shù)原理

§5.6集合的歸納定義法§5.7有序偶和笛卡兒乘積2§5.1集合與元素目標(biāo)要求：會(huì)用抽象法表示集合掌握集合的抽象表示和枚舉表示的互相轉(zhuǎn)換重點(diǎn)難點(diǎn):

集合的抽象表示抽象原則3

集合是人們能夠明確區(qū)分的一些對(duì)象(客體)構(gòu)成的一個(gè)整體。例如：“全體中國(guó)人”，“所有英文字母”都構(gòu)成集合。但“全校高個(gè)子學(xué)生”不能構(gòu)成集合，因?yàn)椤案邆€(gè)子”是一個(gè)模糊概念。集合通常用大寫(xiě)英文字母表示，其中用:N表示自然數(shù)集合(含0)，R表示實(shí)數(shù)集合，

Q表示有理數(shù)集合，I(Z)表示整數(shù)集合。

集合：集合是一個(gè)原始概念,無(wú)精確定義。1875年康托爾給其定義如下：4

如果a是集合A中的元素，就寫(xiě)成aA，讀作:a屬于A。如果b不是A中的元素，就寫(xiě)成bA，讀作:b不屬于A。集合的表示方法:（1）枚舉法（2）抽象法

(3)歸納定義法枚舉法：把集合中的元素全部列舉出來(lái)，用{}括起來(lái)，元素之間用逗號(hào)分開(kāi)。

元素：集合里含有的對(duì)象稱(chēng)為該集合的元素。通常用小寫(xiě)英文字母表示元素。5例如:A={a,e,i,o,u}抽象法:

用謂詞概括集合中元素的屬性.

其描述形式為S={x|P(x)}例:S1={x|x是中國(guó)的省}S2={x|x=2k+1且kN}={x|x是正奇數(shù)}S3={x|x=an,nN}可見(jiàn)，一個(gè)集合的抽象描述形式不唯一。S={a0,a1,a2,…,an,…}，其中n為自然數(shù)。6例:A={x|x是英文元音字母}由抽象原則可知，對(duì)任意x:xAx是英文元音字母其中,表示當(dāng)且僅當(dāng)。

定義5.1(抽象原則):

任給一個(gè)性質(zhì)P，就確定了一個(gè)集合A,A的元素恰好是具有性質(zhì)P的對(duì)象，即:A={x|P(x)}

也就是說(shuō)x(P(x)xA)7抽象原則的限制:(1)謂詞P(x)要明確清楚反例：A={x|p(x)},p(x)：x是公園里美麗的花朵“美麗”是一模糊概念。因此A不能夠成集合。

(2)不能取P(x)為xx

這樣的謂詞來(lái)定義集合，否則就會(huì)產(chǎn)生悖論(羅素悖論,B.Russell)。例：設(shè)T={x|xx},由抽象原則，就有:

x:xTxx，把T代入x得，

TTTT，矛盾!8抽象原則很危險(xiǎn):關(guān)于集合的直觀描述不能作為集合的嚴(yán)格定義。

若C={S|S是集合且SS}，則C不是集合?？低秀Ｕ摚簕S|S是集合}理發(fā)師悖論：理發(fā)師恰給所有不給自己理發(fā)的人理發(fā)。說(shuō)謊者悖論：我說(shuō)的這句話(huà)是假話(huà)。9悖論產(chǎn)生的原因：自引用、自作用集合的公理化：為了解決集合論中的悖論問(wèn)題，人們從二十世紀(jì)初就開(kāi)始了公理化集合論的研究。并提出了集合論的種種公理系統(tǒng)。在本書(shū)中和計(jì)算機(jī)科學(xué)中所涉及的集合，一般都不會(huì)引起悖論。10歸納定義法1)基本項(xiàng)非空集S0

A；2)歸納項(xiàng) 一組規(guī)則，從A中元素出發(fā)，依據(jù)這些規(guī)則所獲得的元素仍然是A中的元素；3)極小化：保證A中每個(gè)元素都可通過(guò)有限次使用1)或2)

來(lái)獲得。 如果集合SA也滿(mǎn)足1)和2)，則AS。（如果集合SA也滿(mǎn)足1)和2)，則S=A）*極小化保證A是滿(mǎn)足1)和2)的最小集合。11§5.2集合間的相等和包含關(guān)系目標(biāo)要求：掌握集合相等（=）、包含（）的定義。掌握、=、之間的聯(lián)系與區(qū)別。掌握空集的性質(zhì)重點(diǎn)難點(diǎn)：集合間的相等與包含關(guān)系空集的性質(zhì)證明集合相等12一、集合的相等

定義5.2(集合相等)（外延性公理）：設(shè)A,B為任意兩集合，若A和B含有相同的元素，則稱(chēng)A和B相等,記作：A=B

A=Bx(xAxB)或

A=Bx(xAxB)x(xBxA)13例：2.{x|x2-1=0}={-1，1}3.{1，2，3}={3，1，2}——表明集合與其元素排列次序無(wú)關(guān)。{a,b,a}={a,a,b,b,a}={a,b}——表明集合與其元素重復(fù)出現(xiàn)次數(shù)無(wú)關(guān){a,a,b,b,a}稱(chēng)為多重集,也稱(chēng)為bag{x|x≤4且x是正整數(shù)}={1,2,3,4}={x|x<6且x能整除12}14由外延性公理可知，對(duì)于任意集合A,B,C有

1.A=A2.A=BB=A3.A=B∧B=CA=C注意：作為集合的元素，未加任何限制，一個(gè)集合的元素可以是一個(gè)集合。例如：{?，1，2，3，{1，2}}15二、集合的包含關(guān)系

定義5.3(子集或包含)：若集合A的每一個(gè)元素都是集合B的元素，則稱(chēng)A是B的子集，也稱(chēng)A包含于B或B包含A。記作：AB

或BAABx(xAxB)由定義5.3可知：對(duì)任意集合A有:AA

定義5.4（真子集或真包含）：設(shè)A,B是任意集合，若AB且A≠B，則稱(chēng)A為B的真子集，也稱(chēng)A真包含于B，或B真包含A。記作：

AB

或BA16ABA

BA≠Bx(xAxB)x(xBxA)證明：ABA

BA≠Bx(xAxB)(x((xAxB)(xBxA))x(xAxB)(x(xAxB)x(xBxA))x(xAxB)x(xBxA)x(xAxB)x(xBxA)x(xAxB)x(xBxA)17例：若AB，BC，則AC嗎？(或AC嗎？)解：一般不成立。例如：A={1},B={{1},2},C={{{1},2},3},但AC。當(dāng)A={1},B={{1}},C={{{1}},{1}}時(shí),但AC關(guān)系“”和“”的區(qū)別：：構(gòu)成集合A的元素a與A是“”關(guān)系：集合A的子集B與A是“”關(guān)系例：4{{1，3}，4}，{1，3}{{1，3}，4}，

{4}{{1，3}，4}{{1，3}，4，5，7}18定理5.1：設(shè)A,B是兩個(gè)集合，則

A=B當(dāng)且僅當(dāng)AB且BA證：A=Bx(xAxB)(集合相等定義）x(xAxB)x(xBxA)ABBA（子集定義）推論：對(duì)任意集合A，AA定理5.2：設(shè)A，B，C都是集合，若AB且BC，則AC證：對(duì)任意x,xAxB(AB)xC(BC）所以AC成立(注：PQ表示P為真推出Q為真)19定義5.5（全集U）：在對(duì)集合的研究中，如果所討論的集合，都是某一固定集合U的子集，就稱(chēng)集合U為全集，記作：U

U={x|p(x)p(x)}全集U是一個(gè)相對(duì)概念，故全集U不唯一。定義5.6（空集）：不含有任何元素的集合稱(chēng)為空集,記作:={x|p(x)∧p(x)}定理5.3：設(shè)A是任意集合，則A證：Ax(xxA),而x為假,故x(xxA)是永真式,故A成立20定理5.4：空集是唯一的。證：假設(shè)空集不唯一，令1和2都是空集，則有12，同時(shí)21，由定理5.1，1=2

含有一個(gè)元素的集合稱(chēng)為單元集,如：{a},{}

含有n個(gè)元素的集合稱(chēng)為n元集。由有窮個(gè)元素構(gòu)成的集合稱(chēng)為有窮集。由無(wú)窮個(gè)元素構(gòu)成的集合稱(chēng)為無(wú)窮集。如：N,R21§5.3冪集目標(biāo)要求：掌握冪集的定義會(huì)求集合的冪集22例：A={a,b,c}

則A的0元子集：

A的1元子集：{a},,{c}A的2元子集：{a,b},{a,c},{b,c}A的3元子集：{a,b,c}

則A的冪集：

ρ(A)={,{a},,{c},{a,b},{a,c},{b,c},{a,b,c}}可見(jiàn)，若x∈A,則{x}∈ρ(A)，

BAiffB∈ρ(A)定義5.7（冪集）：集合A的全部子集構(gòu)成的集合稱(chēng)為A的冪集，記作ρ（A）。

ρ(A)={X│XA}23證：設(shè)A有n個(gè)元素，即#A=n,則A的m元子集有Cnm個(gè),

所以A共有Cn0+Cn1+……+Cnn

個(gè)子集由二項(xiàng)式定理：（x+y)n=Cn0xn+Cn1xn-1y+……+Cnnyn令x=y=1,則（1+1)n=Cn0+Cn1+……+Cnn=2n

定義5.8（基數(shù)）：有窮集合A中所含有元素的個(gè)數(shù)稱(chēng)為A的基數(shù)。記作#A。若集合S有窮，則S的冪集ρ(S)也有窮。反之亦然。易見(jiàn)，若集A含有n個(gè)元素，則其m元子集有C

nm

個(gè)，其中,C

nm

是從n個(gè)元素中取出m個(gè)元素的組合數(shù)。定理5.5：設(shè)A是有窮集合，則#ρ(A)=2#A24例：（1）求下列集合的冪集

ρ()={}ρ({})={,{}}ρ({a,{a}})={,{a},{{a}},{a,{a}}}ρ(ρ({}))=ρ({,{}})={,{},{{}},{,{}}}

（2）求證：若BC，則ρ(B)ρ(C)證明：對(duì)于任意xx∈ρ（B）xBxC（定理5.2）

x∈ρ（C）所以ρ(B)ρ(C)（的定義）25總結(jié)設(shè)A，B為任意兩個(gè)集合，則有i)

ρ(A)；ii)Aρ(A)；iii)若AB，則ρ(A)

ρ(B)；iv)若AB，則ρ(A)

ρ(B)。26思考題ρ(B)ρ(C)的充分必要條件?2)ρ(B)=ρ(C)的充分必要條件?27§5.4集合的運(yùn)算重點(diǎn)：集合運(yùn)算及運(yùn)算性質(zhì)難點(diǎn)：證明兩個(gè)集合相等28集合的運(yùn)算有：∩、∪、－（差，也稱(chēng)相對(duì)補(bǔ)）、

~（補(bǔ)，也稱(chēng)絕對(duì)補(bǔ)）、（對(duì)稱(chēng)差）n個(gè)集合的∩和∪，集合的聚合上的∩和∪。定義5.9：設(shè)A和B是任意兩個(gè)集合⑴A∩B={x|x∈A∧x∈B}⑵A∪B={x|x∈A∨x∈B}⑶A－B={x|x∈A∧xB}定義5.10：若A和B沒(méi)有公共元素，即A∩B=，則稱(chēng)A和B不相交。29例：設(shè)A={1，2，3，4}，B={3，4，5，6}，求A∪B，A∩B，A－B和B－A。解：A∪B={1，2，3，4，5，6},A∩B={3，4}A－B={1，2},B－A={5，6}定義5.11(補(bǔ)集):設(shè)A是全集U的子集，A相對(duì)于U的補(bǔ)集U－A稱(chēng)為A的絕對(duì)補(bǔ)集，簡(jiǎn)稱(chēng)A的補(bǔ)集。記作~A。即:~A=U－A={x|x∈U∧xA}={x|x

A}顯然,x

Aiffx∈~A30證：根據(jù)抽象原則，對(duì)于任意xx∈A－Bx∈A∧xB（－定義）

x∈A∧x∈~B（~定義）

x∈A∩~B（∩定義）定義5.12（對(duì)稱(chēng)差集）:設(shè)A和B是任意兩個(gè)集合，A和B的對(duì)稱(chēng)差集，記為AB，則

AB=（A－B）∪（B－A）例：若U={1，2，3，4}且A={1，2}，B={2，3，4}，則~A={3，4}，AB={1，3，4}。若U=N且A={x|x>0}，則~A={0}例：證明A－B=A∩~B31證：對(duì)任意xx∈A－（A∩B）

x∈A∧xA∩B

x∈A∧┐（x∈A∧x∈B）

x∈A∧（x

A∨

x

B）

（x∈A∧x

A）∨（x∈A∧x

B）

x∈A∧x

B

x∈A－B

所以A－（A∩B）=A－B根據(jù)外延性公理A－B=A∩~B。因此有：

AB=（A∩~B）∪（B∩

~A）例：試證A－（A∩B）=A－B32可把兩個(gè)集合的∩，∪運(yùn)算推廣到n個(gè)集合上：設(shè)A1,A2,···,An為集合，則:A1∩A2∩···∩An={x|x∈A1∧x∈A2∧···∧x∈An}A1∪A2∪···∪An={x|x∈A1∨x∈A2∨···∨x∈An}∪i=1n∩i=1n∩i=1∪i=1也可將上述n個(gè)集合的∩，∪分別記作Ai

和Ai

同理可把無(wú)窮多個(gè)集合的∩，∪分別記為：

Ai=A1∩A2∩·······∩An∩

·······Ai=A1∪A2∪·······∪An∪·······33設(shè)集合的聚合：

A=｛AS1,AS2,AS3,······｝

J=｛S1,S2,S3，······｝則A可以簡(jiǎn)寫(xiě)成：

A=｛Ai|i∈J｝其中，稱(chēng)A為加標(biāo)集合，J為標(biāo)碼集合。定義5.13(集合族或集合的聚合):

如果一個(gè)集合的所有元素都是集合，則稱(chēng)該集合為集合族或集合的聚合。34定義5.14(集合的聚合上的∩、∪運(yùn)算)

設(shè)A是全集U的子集的聚合，即：

A=｛Ai|i∈J｝,其中J為標(biāo)碼（下標(biāo)）集合（1）A的元素的并集表示為∪A或∪i∈JAi∪A={x|S（S∈A∧x∈S

）}（2）若A≠,A的元素的交集表示為∩A或∩i∈JAi

∩A={x|S（S∈Ax∈S

）}

因?yàn)?，若A=,則蘊(yùn)涵式S∈Ax∈S的前件為假，S（S∈Ax∈S）為真，這就定義了全集U。因此，要求A≠。35例：設(shè)C=｛｛0｝,｛0,1｝,｛0,1,2｝｝則∪C=｛0｝∪｛0,1｝∪｛0,1,2｝=｛0,1,2｝∩C=｛0｝∩｛0,1｝∩｛0,1,2｝=｛0｝例：設(shè)A=｛Ai|i∈J｝,J=｛a,b,c｝,Aa=｛0,1,2｝,Ab=｛4,5,6｝,Ac=｛2｝則∪i∈JAi=Aa∪Ab∪Ac=｛0,1,2,4,5,6}∩i∈JAi=Aa∩Ab∩Ac=36思考題∩ρ

(Ａ)=?∪ρ

(Ａ)=?xAB iff（xA且xB）或（xB且xA）xAB iff（xA且xB）或（xA且xB）A－B=iff?A∪B=iff?AB=iff?AB=ACiff?ρ

(Ａ)∪ρ

(B)=ρ

(Ａ∪B)iff?

證明:對(duì)于任意集合A,B,C,均有AB=(A∪B)－(A∩

B)

ρ

(Ａ)∩ρ

(B)=ρ

(Ａ∩

B)(AB)C=A(BC)37集合恒等式冪等律：A∪A=A交換律：A∪B=B∪AA∩A=AA∩B=B∩A結(jié)合律：（A∪B）∪C=A∪（B∪C）（A∩B）∩C=A∩（B∩C）分配律：A∪（B∩C）=（A∪B）∩（A∪C）

A∩（B∪C）=（A∩B）∪（A∩C）同一律：A∪=AA∩U=A38零律：

A∪U=UA∩=否定律：A∪~A=UA∩~A=吸收律：A∪（A∩B）=AA∩（A∪B）=A德摩根律：~（A∪B）=~A∩~B~（A∩B）=~A∪~B對(duì)合律：~（~A）=A~=U~U=39對(duì)集合恒等式的說(shuō)明

在不含和的集合恒等式中，將和互換，和U

互換，得到的仍是集合恒等式?！獙?duì)偶原理

吸收律：A∪（A∩B）=AA∩（A∪B）=A

將不含、和的命題邏輯等值式中的換為，換為，換為，0換為，1換為U，換為=，就得到集合恒等式。

——？？原理

40布爾代數(shù)

布爾代數(shù)是有補(bǔ)分配格，記為〈B，*，，′，0，1〉，其中〈B，*，〉是格，′是求補(bǔ)運(yùn)算，0和1為最小元和最大元。設(shè)S是非空集，則〈ρ(S)，∩，∪，～，，S〉是布爾代數(shù),習(xí)慣上稱(chēng)為集合代數(shù)。布爾代數(shù)是同構(gòu)于集合冪集的格的代數(shù)系統(tǒng)，許多代數(shù)系統(tǒng)（諸如命題代數(shù)、開(kāi)關(guān)代數(shù)和集合代數(shù)）都是布爾代數(shù)的特例。用W表示包含n個(gè)原子的合式公式的集合，則代數(shù)系統(tǒng)〈W，∧，∨，，F(xiàn)，T〉是布爾代數(shù)，稱(chēng)為命題代數(shù)。41

除了上述性質(zhì)外，常用性質(zhì)還有A－B=AB

和下面兩個(gè)性質(zhì)定理定理：設(shè)A和B是全集U的子集，B=A

當(dāng)且僅當(dāng)

AB=U

和AB=

。證明：必要性若B=A，則AB=AA=U，

AB=A

A=

充分性

若AB=U和AB=，則

B=UB=(A

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

A)

(AB)=A(AB)=AU=A42定理：設(shè)A和B是全集U的子集，則下列命題等價(jià)：（1）AB（2）AB=B（3）AB=A（4）A–B=證明：（1）（2）（3）（4）（1）43（1）（2）：對(duì)于任意x，由“”定義可知

x∈B，x∈AB，因此BAB對(duì)于任意x，x∈ABx∈Ax∈Bx∈Bx∈Bx∈B所以AB=B（2）（3）:AB=A（AB）=A

（吸收律）（3）（4）:A-B=(AB)–B=ABB=（4）（1）:反證法，假設(shè)AB不成立，則存在x，

x∈A但xB，因此x∈A-B，即A-B，與已知條件（4）矛盾。故必有AB

該定理常用于證明兩個(gè)集合的包含關(guān)系。44例：設(shè)A，B，C是任意集合，試證：若AB且CD，則ACBD證明：因?yàn)锳B且CD，則

AB=B且CD=D（四個(gè)等價(jià)命題）

(AB)(CD)=BD即（AC）（BD）=BD

所以ACBD（四個(gè)等價(jià)命題）45證明兩個(gè)集合相等常用以下兩種方法：（1）集合相等定義(元素分析法）（2）集合恒等式（等式推理）46例：試證：A－(B∪C)＝(A－B)∩(A－C)。證明：方法一，對(duì)任意x,x∈A－(BC)x∈A∧x(BC)x∈A∧┐(x∈BC)

x∈A∧┐(x∈B∨x∈C)

x∈A∧(xB∧xC)

(x∈A∧xB)∧(x∈A∧xC)

x∈A－B∧x∈A－Cx∈(A－B)∩(A－C)所以，A－(B∪C)＝(A－B)∩(A－C)。

47例：試證：A－(B∪C)＝(A－B)∩(A－C)。證明：方法二

A－(B∪C)

＝A∩～(B∪C) ＝A∩(～B∩～C) 德·摩根律＝(A∩A)∩(～B∩～C) 冪等律＝(A∩～B)∩(A∩～C) 結(jié)合律，交換律＝(A－B)∩(A－C)

48例設(shè)A,B,C是任意集合,試證：

(A-B)

B=(A-B)B(=AB)證明：（A-B）

B=((A-B)-B)(B-(A-B))(

的定義)=（A~B~B)(B~(A~B))=(A~B)(B(B~A))=（A-B）B（吸收律）

49§5.5有窮集的計(jì)數(shù)原理

引理5.1：若A和B是有窮集合，且A∩B＝，則＃(A∪B)=

＃A＋＃B

定理5.12：若A和B是有窮集合，則

＃(A∪B)=

＃A＋＃B

－＃(A∩B)證明：顯然A∪B和A∩B是有窮集。

A∪B=B∪A=（B∪A）∩（B∪～B)=B∪(A∩～B)（分配律）50由于B∩(A∩～B)＝，根據(jù)引理5.1得＃（A∪B)＝＃B＋＃（A∩～B)(1)又A＝A∩(B∪～B)

＝(A∩B)∪(A∩～B)

（分配律）同樣(A∩B)∩(A∩～B)＝，根據(jù)引理5.1得＃A＝＃(A∩B)＋＃(A∩～B)

＃(A∩～B)＝＃A－＃(A∩B)代入(1)式得＃(A∪B)＝

＃A+＃B－＃(A∩B)51推論：若A，B和C是有窮集合，則＃(A∪B∪C)＝＃A＋＃B＋＃C

－＃(A∩B)－＃(A∩C)－＃(B∩C)

＋＃（A∩B∩C)有窮集合計(jì)數(shù)問(wèn)題的求解，可利用上述定理或推論，還可利用文氏圖和代數(shù)相結(jié)合的方法。舉例如下：52例：外語(yǔ)系120名學(xué)生中，其中有100名學(xué)生至少學(xué)習(xí)英語(yǔ)、德語(yǔ)、法語(yǔ)這三門(mén)外語(yǔ)中的一種，有65人學(xué)英語(yǔ)，45人學(xué)德語(yǔ)，42人學(xué)法語(yǔ)，20人既學(xué)英語(yǔ)又學(xué)德語(yǔ)，25人既學(xué)英語(yǔ)又學(xué)法語(yǔ)，15人既學(xué)德語(yǔ)又學(xué)法語(yǔ)。求同時(shí)學(xué)這三種外語(yǔ)的人數(shù)和僅學(xué)其中一門(mén)外語(yǔ)的人數(shù)。解1：＃(E∪G∪F)＝＃E＋＃G＋＃F－＃(E∩G)－＃(E∩F)＃(G∩F)＋＃（E∩G∩F),其中＃(E∪G∪F)=100,＃E=65,＃G=45,＃F=42,＃(E∩G)=20,＃(E∩F)=25,＃(G∩F)=15，因此得:＃

(E∩G∩F)=8,即同時(shí)學(xué)三種外語(yǔ)有8人僅學(xué)英語(yǔ)和德語(yǔ)的人數(shù)為20－8=12，僅學(xué)英語(yǔ)和法語(yǔ)的人數(shù)為25－8=17，僅學(xué)德語(yǔ)和法語(yǔ)的人數(shù)為15－8=7，因此，僅學(xué)其中一門(mén)外語(yǔ)的人數(shù)為：100–12–17–7–8=5653解2：設(shè)同時(shí)學(xué)這三種外語(yǔ)的人數(shù)為x，僅學(xué)英語(yǔ)、德語(yǔ)、法語(yǔ)的學(xué)生人數(shù)分別為y1,y2,y3

。故僅學(xué)英語(yǔ)和德語(yǔ)的人數(shù)為20－x僅學(xué)英語(yǔ)和法語(yǔ)的人數(shù)為25－x僅學(xué)德語(yǔ)和法語(yǔ)的人數(shù)為15－x由學(xué)英語(yǔ)的有65人得y1＋20－x＋x＋25－x＝65,由學(xué)德語(yǔ)的有45人得y2＋20－x＋x＋15－x＝45,由學(xué)法語(yǔ)的有42人得y3＋25－x＋x＋15－x＝42,y1＋20－x＋x＋25－x＋y2＋15－x＋y3＝10054

解方程組得：x＝8，y1＝28,y2＝18,y3＝10

因此，同時(shí)學(xué)這三門(mén)外語(yǔ)的有8人，僅學(xué)這三門(mén)外語(yǔ)中一門(mén)的有28＋18＋10＝56人。55§5.6集合的歸納定義法前面介紹了集合的表示方法有1.枚舉法：常用于有窮集合的表示。2.抽象法：用于有窮集或無(wú)窮集的表示。

但用抽象法表示集合時(shí)，有時(shí)不可能清楚地表示某些集合。例如算術(shù)表達(dá)式集合，某高級(jí)語(yǔ)言程序集合等等，這時(shí)可用集合的歸納定義法來(lái)描述。56歸納定義法1)基本項(xiàng)

非空集S0

A；(規(guī)定A的一些生成元）2)歸納項(xiàng)

一組規(guī)則，從A中元素出發(fā)，依據(jù)這些規(guī)則所獲得的元素仍然是A中的元素；3)極小化

(a)A中的每個(gè)元素都是通過(guò)有限次使用1)或2)獲得的。

(b)如果集合SA也滿(mǎn)足1)和2)，則AS。

(c)如果集合SA也滿(mǎn)足1)和2)，則S=A。*極小化保證：A是同時(shí)滿(mǎn)足1)和2)

的最小集合。572.歸納語(yǔ)句：規(guī)定由已知元素構(gòu)成集合中新元素的規(guī)則（集合生成算法）一般表述為:“若x,y,z…,是集合中的元素，則根據(jù)某些規(guī)則進(jìn)行有限次的組合，其結(jié)果也是集合中的元素”。3.極小化語(yǔ)句：限定集合的范圍。（是滿(mǎn)足1和2的最小集合，注：這步有時(shí)省略）一般表述為“只有有限次應(yīng)用基礎(chǔ)語(yǔ)句和歸納語(yǔ)句得到的元素才是該集合中的元素”。集合的歸納定義由三部分組成

1.基礎(chǔ)語(yǔ)句：規(guī)定集合生成元（集合的原子元素），表明集合非空。58例：非負(fù)偶數(shù)集合

E={xy(yNx=2y)}E的歸納定義如下：⑴.0E⑵.若nE，則(n+2)E⑶.只有有限次應(yīng)用⑴、⑵得到的數(shù)才是E中的元素。例：求下列歸納定義的集合P⑴.3P⑵.若x,yP,則(x+y)P⑶.只有有限次應(yīng)用⑴、⑵得到的元素才在P中。顯然，P是由3的倍數(shù)的正整數(shù)組成。59用歸納定義法給出下列集合:允許有前0的十進(jìn)制無(wú)符號(hào)整數(shù)的集合；不允許有前0的十進(jìn)制無(wú)符號(hào)整數(shù)的集合；不允許有前0的二進(jìn)制無(wú)符號(hào)偶數(shù)的集合；不允許有前0的被3整除的二進(jìn)制無(wú)符號(hào)整數(shù)的集合。

思考題60允許有前0的十進(jìn)制無(wú)符號(hào)整數(shù)的集合；解法一：1)令S0=

{0,1,2,3,4,5,6,7,8,9}A1

；2)若aS0且A1

，則aA1

；3)極小化。解法二：1)令S0

=

{0,1,2,3,4,5,6,7,8,9}A1

；若,A1，則A1

；3)極小化。

解法612.

不允許有前0的十進(jìn)制無(wú)符號(hào)整數(shù)的集合；解法一：1)令S0

=

{0,1,2,3,4,5,6,7,8,9}A2

；若aS0

–{0}

且A2

，則aA2

；3)極小化。???解法二：1)令S0

=

{0,1,2,3,4,5,6,7,8,9}A2

；若,A2

且0，則A2

；3)極小化。

解法623.不允許有前0的二進(jìn)制無(wú)符號(hào)偶數(shù)的集合；解法一：1)令S0

=

{0}A3

；若A3

，則1A3;

若,A3

且0，則A3;4)極小化。

解法63中秋節(jié)快樂(lè)!給你10個(gè)月餅，每天至少吃一個(gè)，多吃不限，連續(xù)幾天把月餅吃完，有多少種不同的吃法？

月餅的吃法：64字符串在計(jì)算機(jī)科學(xué)中有重要作用，下面引入有關(guān)術(shù)語(yǔ)字母表是字母(或稱(chēng)符號(hào))的非空有限集合,通常記作∑。字母表∑上的字符串是由∑中的字母所組成的有窮序列例：a，ab，cba，aabbac是={a，b，c}上的字符串字符串的長(zhǎng)度：字符串x所含字母的個(gè)數(shù)，稱(chēng)為字符串x的長(zhǎng)度，記作|x|，例如：|ab|=2,|an|=n。若|x|=0，則稱(chēng)x為空串，記做。65字符串相等：設(shè)x

和y是任意兩個(gè)字符串，則x=y當(dāng)且僅當(dāng)|x|=|y|，并且組成x的諸字符與組成y的諸字符依次相同。例：若x=ab,y=ab,則x=y；若x=ab,y=ba,則x

y。字符串的連接：設(shè)是一字母表，x，y是上字符串，x=a1a2…an，

y=b1b2…bn，x和y的連接記作xy，xy=a1a2…anb1b2…bn特別地：x

=

x=x，

n個(gè)x的連接記作xn，x0=，xn+1=xnx顯然|xy

|=|x|+|y|，字符串的連接運(yùn)算滿(mǎn)足結(jié)合律66

設(shè)x,y,z是任意字符串，則稱(chēng)x是字符串xy的前綴,

y是字符串xy的后綴。例如:ε,a,ab,abc,abcc等都是字符串a(chǎn)bccba的前綴

ε,a,ba,cba,ccba等都是字符串a(chǎn)bccba的后綴稱(chēng)x

，y，z分別是字符串xyz的子串。

ε是每個(gè)字符串的前綴、后綴、子串。若x

是y的子串（前綴，后綴）并且xy,則稱(chēng)x是y的真子串（真前綴，真后綴）

上的所有字符串構(gòu)成的集合記做*，給出*的歸納定義?67*

的歸納定義如下：1）

*2）若x

*和a

，則xa

*(或ax

*)3）*中的每一個(gè)元素都可通過(guò)有限次應(yīng)用上述1)、2)規(guī)則得到。上的所有非空字符串的集合記做

+

，

+

的歸納定義如下???1）

+

2）若x

+

和a

，則xa

+(或ax

+)3）+中的每一個(gè)元素都可通過(guò)有限次應(yīng)用上述1)、2)規(guī)則得到。68上的語(yǔ)言：*的子集例如：{a，ab，cba，bba}是={a，b，c}上的語(yǔ)言。語(yǔ)言的運(yùn)算如下：語(yǔ)言的乘積(連接)：設(shè)A和B是上的語(yǔ)言，A和B的乘積記作AB，AB={xyxAyB}例：A={，a，ab}，B={a，bb}，則

AB={a，bb，aa，abb，aba，abbb}語(yǔ)言的冪運(yùn)算An：

(1)A0={},(2)An+1=AnA,nN語(yǔ)言的閉包運(yùn)算A*

：

A*

={}AA2……A的正閉包A+

：A+

=AA2……例：令B={a，bb}，則B2

={aa，abb，bba，bbbb}B*

={，a，bb，aa，abb，bba，bbbb，…}69定理：設(shè)A、B、C、D是上的任意語(yǔ)言，則下列關(guān)系成立A=A=A{}={}A=A(AB)C=A(BC)若AB和CD,則ACBDA(BC)=ABAC(BC)A=BACAA(BC)ABAC(BC)ABACA70試證：若AB和CD,則ACBD證明：對(duì)于任意zzACxy(z=xyxAyC)xy(z=xyxByD)(AB和CD)

zBD所以，ACBD71證明A(BC)=ABAC證明：對(duì)于任意zzA(BC)xy(z=xyxAy(BC))xy(z=xyxA(yByC))xy((z=xyxAyB)(z=xyxAyC))

xy((z=xyxAyB)xy(z=xyxAyC))

zABzAC

zABAC72定理：設(shè)A、B是上的任意語(yǔ)言，m、n是任意自然數(shù),則下列關(guān)系成立：（1）Am

An

=Am+n（2）（Am

）

n=Amn（3）若AB，則AnBn

定理：設(shè)A、B是上的任意語(yǔ)言，nN，則下列關(guān)系成立：（1）A*

={}A+

（2）AnA*

，n0（3）An

A+

，n173（4）AAB*（5）AB*A（6）若AB，則A*B*（7）若AB，則A+

B+（8）AA*

=A*A

=A+

（9）若A，則

A*

=A+

（10）(A*

)*

=A*

A*=A*

（11）（A*

）*

=(A+

)

*=A*

（12）（

A+）+

=A+

證明略。74

§5.7有序偶和笛卡兒乘積·

掌握有序偶和笛卡兒乘積的定義和性質(zhì)·

熟練掌握求兩個(gè)集合的笛卡兒乘積75定義5.22：（有序偶）任給兩個(gè)對(duì)象x和y，將它們按規(guī)定的順序構(gòu)成的序列，稱(chēng)之為有序偶，記為〈x，y〉。其中，x稱(chēng)為有序偶的第一元，y稱(chēng)為第二元。

顯然有序偶與二元集在概念和性質(zhì)上都有根本的不同。如：

〈a，b〉≠〈b，a〉〈a，a〉≠〈a〉

而{a，b}={b，a}{a，a}={a}76

1921年波蘭數(shù)學(xué)家?guī)炖蟹蛩够↘uratovski）給出了一種有序偶的集合表示：

〈x，y〉={{x}，{x，y}}。

定理5.16

有序偶的唯一性定理：〈u，v〉=〈x，y〉當(dāng)且僅當(dāng)u=x和v=y。證：充分性當(dāng)u