第2章 集合與序列

第2章集合與序列

1集合論的產(chǎn)生:

1876～1883年間，康托（GeorgeCantor1845～1918年,德國(guó)數(shù)學(xué)家）對(duì)任意元素的集合進(jìn)行了系統(tǒng)的研究?？低斜还J(rèn)為集合理論的創(chuàng)始人。

2.1集合的定義和運(yùn)算22.1.1集合的定義一、集合（sets）的概念

集體

集合

組成集合的事物（也稱(chēng)個(gè)體）叫做該集合的元素（elements）。例如：

計(jì)算機(jī)系2011級(jí)全體同學(xué)；全體自然數(shù)；方程x2-1＝0的解；抽象成數(shù)學(xué)概念3二、集合的表示集合----用大寫(xiě)字母A,B,…等標(biāo)識(shí)。元素----用小寫(xiě)字母a,b,…等標(biāo)識(shí)。記法：若個(gè)體a是集合A的元素,則記為a∈A,讀作“a屬于A”;否則，記為a

A,讀作“a不屬于A”。4【定義】沒(méi)有任何元素的集合叫空集(emptyset),記為

。【定義】當(dāng)我們所討論的集合都是某一集合的子集時(shí),這某一集合就稱(chēng)為全集(universalset),并用E表示。5表示一個(gè)集合的方法通常有以下三種:

1.列舉法。如：

A=｛0,1,2,3｝。自然數(shù)集N用列舉法表示是｛0,1,2,3,…｝。

根據(jù)所列元素,容易判斷N中的其余元素6

2.描述法：說(shuō)明集合A中的元素x應(yīng)滿足的條件。記為：

A＝{x|x滿足的條件}

如:大于0小于1的實(shí)數(shù)集合：{x|(0<x<1)且x∈R};所有正奇數(shù)的集合：{x|x＝2y+1且y∈N}。73.遞歸法(遞推法)數(shù)列常常用遞歸定義。【例】斐波那契數(shù)列:f1=1,f2=1,fn=fn-1+fn-2，n=3,4,…8羅素悖論：Questions在一個(gè)僻靜的孤島上，住著一些人家，島上只有一位理發(fā)師，該理發(fā)師專(zhuān)給那些并且只給那些自己不刮臉的人刮臉。那么，誰(shuí)給這位理發(fā)師刮臉？解：設(shè)C＝{x|x是不給自己刮臉的人}

b是這位理發(fā)師

如果這位理發(fā)師不自己刮臉,即b

C，則

b

C；

如果這位理發(fā)師自己刮臉,即b

C，則

b

C。

b

C或b

C都不能成立9【定義】集合A中元素的個(gè)數(shù)稱(chēng)為A的基（基數(shù),

cardinality），也稱(chēng)為長(zhǎng)度，記作|A|。當(dāng)|A|是有限數(shù)時(shí),集合A稱(chēng)作有限集,否則稱(chēng)為無(wú)限集。顯然,|

|＝0。10定義2.1.1設(shè)A、B是兩個(gè)集合，E是全集，則A和B的并集(union)

A∪B、A和B的交集(intersection)

A∩B、A的補(bǔ)集(complement)分別定義如下：

A∪B＝｛x|x∈A或x∈B｝A∩B＝｛x|x∈A且x∈B｝

＝｛x|x

A且x∈E｝三、集合的運(yùn)算

11直觀地表示集合間關(guān)系的文氏圖：注：文氏(JohnVenn),1834-1923,英國(guó)邏輯學(xué)家。

注意：文氏圖只能幫助我們形象地理解復(fù)雜的集合關(guān)系,一般不作為一種證明方法。

12定義2.1.2設(shè)A、B是兩個(gè)集合，A與B的差集(difference)A－B定義為:

A－B＝｛x|x∈A且x

B｝13設(shè)A＝{a,e,f},B＝{a,f,g,h}則：

A－B＝______B－A＝_______

A－B=B－A。?14由定義或文氏圖都容易得到下面的公式:A－B＝A∩

1542算法2.1.1：求兩個(gè)集合交集的算法。A1645234BC12452364依次掃描A、B中的元素，若相同，則把其添加到C中緊湊存儲(chǔ)方式下的集合運(yùn)算的實(shí)現(xiàn)216算法2.2.1：求兩個(gè)集合交集的算法。FindIntersection(setA,setB)//求出集合A和B的交集{iALength=length(A)//集合A的長(zhǎng)度iBLength=length(B)//集合B的長(zhǎng)度f(wàn)or(i=0;i<iALength;i++){

for(j=0;j<iBLength;j++)if(A[i]==B[j]){

C[k]=A[i];//添加交集元素到交集C中k++;break；}}ReturnC;//集合C就是A與B的交集}1742算法2.2.2：求兩個(gè)集合并集的算法。A1245234BC152364把A中的元素加到C中，再掃描B，把其不再A中的元素加入C。421563618算法2.1.2：求兩個(gè)集合并集的算法：FindUnion(setA,setB)//求出集合A和B的并集{iALength=length(A)//集合A的長(zhǎng)度iBLength=length(B)//集合B的長(zhǎng)度C=B；//用集合C存儲(chǔ)集合的并集，把B中的元素賦值到C中iCLength=iBLengthfor(i=0;i<iALength;i++){bFind=false;for(j=0;j<iBLength;j++)//循環(huán)1if(A[i]==B[j]){bFind=true;//A[i]為公共元素；break；//跳出循環(huán)1}ifnotbFind//A[i]不是公共元素；{C[iClength+1]=A[i];//把A[i]加入到集合C中；iClength=iClength+1;}}ReturnC;//集合C就是A與B的并集}19算法2.2.2：求兩個(gè)集合減法的算法。A1245234B234刪除在B中出現(xiàn)的A的元素。41562620算法2.2.3：集合減法運(yùn)算算法。FindDeference(setA,setB)//求出集合A-B的差集{iALength=length(A)//集合A的長(zhǎng)度iBLength=length(B)//集合B的長(zhǎng)度f(wàn)or(i=0;i<iBLength;i++){for(j=0;j<iALength;j++)if(A[j]==B[i]){A=A-A[j]；//從集合A中去掉元素A[j]Break；}}ReturnA;//集合A就是A與B的差集}21假定全集E是有限的。首先為E的元素任意規(guī)定一個(gè)順序，例如d1，d2，…，dn，于是可以用長(zhǎng)度為n的位串(布爾型數(shù)組)表示E的子集A：如果di屬于A，則位串中第i位是1；如果di不屬于A，則位串中第i位是0。二、非緊湊存儲(chǔ)方式下的集合運(yùn)算的實(shí)現(xiàn)22例令E={1，2，3，4，5，6，7，8，9，10}，而且E的元素從小到大排序，即di=i。問(wèn)：表示E中所有奇數(shù)的子集、所有偶數(shù)的子集和不超過(guò)5的整數(shù)的子集的位串是什么?解表示E中所有奇數(shù)的子集即{1，3，5，7，9}的位串，其第1、3、5、7、9位為1，其他位為0，即

1010101010

(位串分成長(zhǎng)度為5的兩段以便閱讀)23類(lèi)似地，E中所有偶數(shù)的子集即{2，4，6，8，10}，由位串

0101010101表示。E中不超過(guò)5的所有整數(shù)的集合即{1，2，3，4，5}，由位串

1111100000

表示。24用位串表示集合便于計(jì)算集合的補(bǔ)集、并集、交集和差集。1）要從表示集合的位串計(jì)算它的補(bǔ)集的位串，只須簡(jiǎn)單地把每個(gè)1改為0，每個(gè)0改為1。即按位取反。25例我們已經(jīng)知道集合{1，3，5，7，9}的位串是1010101010它的補(bǔ)集的位串是什么?解用0取代1，用1取代0，即可得到此集合的補(bǔ)集的位串

0101010101

這對(duì)應(yīng)著集合{2，4，6，8，10}。26要得到兩個(gè)集合的并集和交集的位串，我們可以對(duì)表示這兩個(gè)集合的位串按位做布爾運(yùn)算：2）并集的位串是兩個(gè)集合位串的按位或：只要兩個(gè)位串的第i字位有一個(gè)是1，則并集的位串的第i位是1，當(dāng)兩個(gè)字位都是0時(shí)為0。3）交集的位串是兩個(gè)集合位串的按位與：當(dāng)兩個(gè)位串的第i字位均為1時(shí)，交集的位串第i位為1，否則為0。27

例集合{1，2，3，4，5}和{1，3，5，7，9}的位串分別是1111100000和1010101010。用位串找出它們的并集和交集。解這兩個(gè)集合的并集的位串是

1111100000

1010101010=1111101010它表示的集合是{1，2，3，4，5，7，9}。這兩個(gè)集合的交集的位串是

1111100000

1010101010=1010100000它表示的集合是{1，3，5}。28

例集合A={1，2，3，4，5}和B={1，3，5，7，9}的位串分別是1111100000和1010101010。試用位串求差集A－B

。解利用公式A－B＝A∩

292.結(jié)合律

A∪(B∪C)＝(A∪B)∪C

A∩(B∩C)＝(A∩B)∩C1.交換律

A∪B＝B∪A

A∩B＝B∩A3.分配律

A∩(B∪C)＝(A∩B)∪(A∩C)

A∪(B∩C)＝(A∪B)∩(A∪C)2.1.3集合運(yùn)算的性質(zhì)

304.德·摩根定律5.

A－B＝A∩

德·摩根(DeMorgan,1806-1871)生于印度,英國(guó)數(shù)學(xué)家。主要貢獻(xiàn):數(shù)學(xué)歸納法,極限的定義,符號(hào)邏輯由4和5可得：6.

A－(B∪C)＝(

A－B

)∩(

A－C

)

A－(B∩C)＝(

A－B

)∪(

A－C

)通過(guò)這些性質(zhì)，可以看出實(shí)現(xiàn)同一集合運(yùn)算有不同算法。31例2.1.1：集合A表示班級(jí)男生集合，B是離散數(shù)學(xué)考試及格的同學(xué)，C是數(shù)據(jù)結(jié)構(gòu)考試及格的同學(xué)。求出至少有一門(mén)考試不及格的男同學(xué)。分析：(A-B)表示離散數(shù)學(xué)考試不及格的男同學(xué);(A-C)表示數(shù)據(jù)結(jié)構(gòu)考試不及格的男同學(xué);至少有一門(mén)考試不及格的男同學(xué)可以表示為：(A-C)∪(A-B)根據(jù)摩根定律可知：(A-C)∪(A-B)=A-(B∩C)32//找出至少有一門(mén)考試不及格的男同學(xué)//A表示班級(jí)男生集合//B是離散數(shù)學(xué)考試及格的同學(xué)//C是數(shù)據(jù)結(jié)構(gòu)考試及格的同學(xué)FindMaleNotPass（setA，setB，setC）{//求出B與C的交集 setD=FindIntersection(B,C)；//A-(B∩C)FindDeference(setA,setD)//求出集合A-D}33利用前面公式,可以證明集合恒等式。

【例】對(duì)任意集合A,B,C,證明:(A－B)－C＝A－(B∪C)

342.2序列與串一、序列序列：是考慮了元素順序的一個(gè)列表，與集合相比，序列中允許元素重復(fù)。序列元素：用下標(biāo)法標(biāo)注元素在序列中的位置。如序列S：2，4，6，8，…,2n則s1=2，s2=4，s3=6，…序列長(zhǎng)度：一個(gè)序列中元素的個(gè)數(shù)。子序列：從一個(gè)序列中去掉一些元素，余下的元素組成了一個(gè)新的序列，稱(chēng)為原序列的子序列。35判定一個(gè)序列T是不是另一個(gè)序列S的子序列算法：判定原則：T中的元素是否在S中按次序出現(xiàn)。例：S12345678T1139T2173T3137√××36isSubsequence(S,T)//判定序列T是不是序列S的子序列{n=iSLength;//序列S的長(zhǎng)度m=iTLength;//序列T的長(zhǎng)度ifm>nreturnfalse;i=1;j=1;while((i<=m)and(j<=n)){if(ti=sj)//字符匹配i=i+1;j=j+1；}ifi=m+1returntrue;//T是S的子序列returnfalse;}S246783T473j=1i=1j=2i=2j=3j=4i=3j=5j=6i=4>mj=737二、字符串長(zhǎng)度有限的字符序列又稱(chēng)字符串，字符串T的長(zhǎng)度記作：|T|。兩個(gè)字符串可以執(zhí)行連接運(yùn)算“+”，字符串S和字符T的連接運(yùn)算如下：S=“abcdefg”T=“hijklmn”S+T=“abcdefghijklmn”。T+S=“hijklmnabcdefg”。38字符串中子串的概念，在計(jì)算機(jī)編程語(yǔ)言中的概念和數(shù)學(xué)中的子序列的概念有所不同。如果字符串的子序列是由原字符串中連續(xù)的元素構(gòu)成的，則該子序列稱(chēng)為原字符串的子串。如S=“abcdefg”,則子串為：“abc”，“cde”，“efg”等“bdf”雖然是S的子序列，但不是S的子串。思考：子串判定的算法392.3矩陣一、矩陣相加的算法MatrixSum(MatrixA,MatrixB){for(i=0;i<m;i++)for(j=0;j<n;j++)aij=aij+bijreturnA;}40二、矩陣相乘的算法MatrixMulti(MatrixA,MatrixB){for(i=0;i<m;i++)for(j=0;j<l;j++){cij=0;for(k=0;k<n;k++)cij=cij+aik×bkj}returnC;}41容斥原理如果已知|A|和|B|,能否求出|A∪B|和|A∩B|?|A∪B|、|A∩B|和|A|、|B|之間的關(guān)系是什么?三個(gè)集合及以上的情況又如何?Questions容斥原理回答了上述問(wèn)題。42

【定理】對(duì)任意兩個(gè)有限集A和