第2章集合與序列

1集合論的產生:

1876～1883年間，康托（GeorgeCantor1845～1918年,德國數(shù)學家）對任意元素的集合進行了系統(tǒng)的研究。康托被公認為集合理論的創(chuàng)始人。

2.1集合的定義和運算22.1.1集合的定義一、集合（sets）的概念

集體

集合

組成集合的事物（也稱個體）叫做該集合的元素（elements）。例如：

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

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

?！径x】當我們所討論的集合都是某一集合的子集時,這某一集合就稱為全集(universalset),并用E表示。5表示一個集合的方法通常有以下三種:

1.列舉法。如：

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

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

2.描述法：說明集合A中的元素x應滿足的條件。記為：

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

如:大于0小于1的實數(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在一個僻靜的孤島上，住著一些人家，島上只有一位理發(fā)師，該理發(fā)師專給那些并且只給那些自己不刮臉的人刮臉。那么，誰給這位理發(fā)師刮臉？解：設C＝{x|x是不給自己刮臉的人}

b是這位理發(fā)師

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

C，則

b

C；

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

C，則

b

C。

b

C或b

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

cardinality），也稱為長度，記作|A|。當|A|是有限數(shù)時,集合A稱作有限集,否則稱為無限集。顯然,|

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

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

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

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

＝｛x|x

A且x∈E｝三、集合的運算

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

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

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

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

B｝13設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：求兩個集合交集的算法。A1645234BC12452364依次掃描A、B中的元素，若相同，則把其添加到C中緊湊存儲方式下的集合運算的實現(xiàn)216算法2.2.1：求兩個集合交集的算法。FindIntersection(setA,setB)//求出集合A和B的交集{iALength=length(A)//集合A的長度iBLength=length(B)//集合B的長度for(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：求兩個集合并集的算法。A1245234BC152364把A中的元素加到C中，再掃描B，把其不再A中的元素加入C。421563618算法2.1.2：求兩個集合并集的算法：FindUnion(setA,setB)//求出集合A和B的并集{iALength=length(A)//集合A的長度iBLength=length(B)//集合B的長度C=B；//用集合C存儲集合的并集，把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：求兩個集合減法的算法。A1245234B234刪除在B中出現(xiàn)的A的元素。41562620算法2.2.3：集合減法運算算法。FindDeference(setA,setB)//求出集合A-B的差集{iALength=length(A)//集合A的長度iBLength=length(B)//集合B的長度for(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ī)定一個順序，例如d1，d2，…，dn，于是可以用長度為n的位串(布爾型數(shù)組)表示E的子集A：如果di屬于A，則位串中第i位是1；如果di不屬于A，則位串中第i位是0。二、非緊湊存儲方式下的集合運算的實現(xiàn)22例令E={1，2，3，4，5，6，7，8，9，10}，而且E的元素從小到大排序，即di=i。問：表示E中所有奇數(shù)的子集、所有偶數(shù)的子集和不超過5的整數(shù)的子集的位串是什么?解表示E中所有奇數(shù)的子集即{1，3，5，7，9}的位串，其第1、3、5、7、9位為1，其他位為0，即

1010101010

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

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

1111100000

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

0101010101

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

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

1111100000

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

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.結合律

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集合運算的性質

304.德·摩根定律5.

A－B＝A∩

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

A－(B∪C)＝(

A－B

)∩(

A－C

)

A－(B∩C)＝(

A－B

)∪(

A－C

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

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

342.2序列與串一、序列序列：是考慮了元素順序的一個列表，與集合相比，序列中允許元素重復。序列元素：用下標法標注元素在序列中的位置。如序列S：2，4，6，8，…,2n則s1=2，s2=4，s3=6，…序列長度：一個序列中元素的個數(shù)。子序列：從一個序列中去掉一些元素，余下的元素組成了一個新的序列，稱為原序列的子序列。35判定一個序列T是不是另一個序列S的子序列算法：判定原則：T中的元素是否在S中按次序出現(xiàn)。例：S12345678T1139T2173T3137√××36isSubsequence(S,T)//判定序列T是不是序列S的子序列{n=iSLength;//序列S的長度m=iTLength;//序列T的長度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二、字符串長度有限的字符序列又稱字符串，字符串T的長度記作：|T|。兩個字符串可以執(zhí)行連接運算“+”，字符串S和字符T的連接運算如下：S=“abcdefg”T=“hijklmn”S+T=“abcdefghijklmn”。T+S=“hijklmnabcdefg”。38字符串中子串的概念，在計算機編程語言中的概念和數(shù)學中的子序列的概念有所不同。如果字符串的子序列是由原字符串中連續(xù)的元素構成的，則該子序列稱為原字符串的子串。如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|之間的關系是什么?三個集合及以上的情況又如何?Questions容斥原理回答了上述問題。42

【定理】對任意兩個有限集A和