復(fù)旦大學(xué)-計算機(jī)院-趙一鳴-離散數(shù)學(xué)(中文)1省名師優(yōu)質(zhì)課賽課獲獎?wù)n件市賽課一等獎?wù)n件

離散數(shù)學(xué)是計算機(jī)學(xué)科主要數(shù)學(xué)基礎(chǔ)課之一離散數(shù)學(xué)是以離散(即非連續(xù))對象數(shù)量和空間關(guān)系為研究內(nèi)容數(shù)學(xué)若干個分支總稱。包含數(shù)理邏輯、近世代數(shù)、古典概率、組合學(xué)、圖論、集合論、數(shù)論、自動機(jī)和形式語言、可計算性和可判定性、離散幾何等。1/4318世紀(jì)以前,數(shù)學(xué)基本上是研究離散對象數(shù)量和空間關(guān)系科學(xué),之后,因天文學(xué),物理學(xué)發(fā)展,如行星軌道,牛頓三大力學(xué)定律等研究,極大地推進(jìn)了連續(xù)數(shù)學(xué)(以微積分,數(shù)學(xué)物理方程,實、復(fù)變函數(shù)論為代表)發(fā)展。離散對象研究則處于停滯狀態(tài)2/4320世紀(jì)30年代,圖靈提出計算機(jī)理論模型——圖靈機(jī)。這種模型早于實際制造計算機(jī)十多年,現(xiàn)實計算機(jī)計算能力,本質(zhì)上和圖靈機(jī)計算能力一樣。這是理論指導(dǎo)實際經(jīng)典范例。因為在計算機(jī)內(nèi),機(jī)器字長總是有限,它代表離散數(shù)或其它離散對象。所以伴隨計算機(jī)科學(xué)和技術(shù)迅猛發(fā)展,離散數(shù)學(xué)就顯得主要。3/43離散數(shù)學(xué)是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法、數(shù)據(jù)庫、編譯原理、算法設(shè)計與分析、計算機(jī)網(wǎng)絡(luò)等課程主要基礎(chǔ)對開發(fā)大型軟件、研究信息安全和密碼學(xué)、開展計算機(jī)理論研究以及開發(fā)新型計算機(jī)都提供了不可缺乏基礎(chǔ)知識。本課程是離散數(shù)學(xué)一部分,包含：集合論組合學(xué)圖論4/43Ⅰ集合論初步集合論是當(dāng)代數(shù)學(xué)基礎(chǔ),它已深入到各種科學(xué)和技術(shù)領(lǐng)域中,被廣泛應(yīng)用到數(shù)學(xué)和計算機(jī)科學(xué)各分支中去。在開關(guān)理論、形式語言、數(shù)據(jù)庫等領(lǐng)域得到了卓有成效應(yīng)用。集合論創(chuàng)始人康托爾(Cantor,1845--1918),德國著名數(shù)學(xué)家在1874年,發(fā)表了題為“關(guān)于全部實代數(shù)數(shù)所成集合一個性質(zhì)”論文，開創(chuàng)了當(dāng)代集合論研究，為當(dāng)代數(shù)學(xué)奠定了基礎(chǔ).5/43集合理論中出現(xiàn)了悖論。為了處理集合論悖論,上世紀(jì)初開始了集合論公理學(xué)方向研究,它是數(shù)理邏輯中心問題之一。從集合基本概念和例子著手,對關(guān)系、函數(shù)、基數(shù)等進(jìn)行討論,并簡單介紹集合論悖論。6/43第一章集合基本概念1.1集合表示所謂集合是指含有共同性質(zhì)一些東西(對象)聚集成一個整體。用大寫英文字母表示,比如S,A等。組成一個集合中那些對象稱為該集合元素,用小寫英文字母或數(shù)字等表示。a

A表示a是集合A元素。a

A表示a不是集合A元素。7/43例：全部整數(shù)全體組成集合，記為Z,則3

Z,-8

Z,6.5

Z,今后我們將用I或Z表示整數(shù)集;I+(Z+)表示正整數(shù)集;Q表示有理數(shù)集;Q+表示正有理數(shù)集;Q-表示負(fù)有理數(shù)集;R表示實數(shù)集;R+表示正實數(shù)集。

8/43集合中元素能夠是詳細(xì)事物,也能夠是抽象符號一、集合表示方法(1)列舉法：列出集合中全部元素來表示一個集合。例：集合A元素為1,3,5,7,9,則A可表示為A={1,3,5,7,9}。B={x1,x2,x3}也是采取了列舉法。9/43(2)特征刻畫法(描述法)：描述集合中元素含有共同性質(zhì)方法來表示某個集合。我們用P(A)表示元素a滿足特征P，則A={a|P(a)}就表示集合A是全部使P(a)成立元素所組成集合。例：C={x|x=y3,y

Z+}D={x|-1<x<2}E={x|x為年紀(jì)小于20歲人}列舉法用于元素個數(shù)較少情況,描述法用于元素個數(shù)較多(或無限),且各對象含有共同性質(zhì)情況10/43(3)遞歸定義法：經(jīng)過某規(guī)則計算來定義集合中元素,在此情況下集合常稱為遞歸定義集合。我們將在第四章對此方法作深入介紹。假如一個集合元素個數(shù)有限，則稱該集合為有限集，不然稱為無限集。前面例子中集合C、D是無限集，而A、B、E則是有限集。有限集A元素個數(shù)稱為集合A基數(shù),記為|A|。A={x|x是大于1小于6質(zhì)數(shù)},|A|=3。11/43假如一個集合不含有任何元素,稱為空集,記為

或{}。例：A={x|x2+1=0,x為實數(shù)}是空集

,|A|=|

|=0.但{

}不是空集，它是以

為元素集合在集合中要注意，(1)集合中元素之間次序是無關(guān)緊要例:{a,b,c}與{b,a,c}是完全相同集合。(2)集合中元素是不能重復(fù)出現(xiàn)即{a,b,c,b,d}是不允許出現(xiàn)12/43一個集合能夠是其它集合元素。例:S={{a,b},{a,b,c},{d,e}}{a,b},{a,b,c},{d,e}都是集合S元素。{a,b,c}本身又是集合，其元素是a,b,c。a,b,c都不是集合S元素。象這種以集合作為元素所組成集合稱為集合族。S={

,{

}}元素是

,{

}。13/431.2集合子集用平面上封閉曲線包圍點集圖形來表示集合,該圖形稱為文氏圖(VennDiagrams)。文氏圖還能表示集合之間相互關(guān)系,集合A中元素全部是集合B元素,可用下列圖表示:14/43定義1.1:設(shè)A和B是兩個集合。A每一元素都是B元素,則稱A是B子集,記為A

B或B

A,分別讀作A包含在B中或B包含A。尤其,A

A。若存在元素a

A,但a

B,則A不是B子集.例:{x|-1<x<2},0.5是該集合元素,不是整數(shù)集元素,故集合{x|-1<x<2}不是整數(shù)集Z子集.15/43(1)空集是任何集合子集(2)若A

B,B

C,則A

C證實:(1)假設(shè)不成立。(2)分析：要證實A

C，則要證實A中任意一個元素都是C中元素。即出發(fā)點是對

a

A,而最終目標(biāo)是a

C,怎樣到達(dá)此目標(biāo)，那就是利用條件A

B,B

C證實：對

a

A，因為A

B，所以有a

B。又因為B

C，所以當(dāng)a

B時，必有a

C所以A

C。16/43定義1.2:集合A和B元素全相同,則稱A和B相等,記為A=B,不然稱A和B不相等,記為A

B。定理1.1:設(shè)A和B是兩個集合,則A=B當(dāng)且僅當(dāng)A

B,且B

A。證實：(1)A=B，

A

B,且B

A(2)A

B,且B

A

A=B17/43定義1.3:若A

B,且A

B,則稱集合A是集合B真子集,記為A

B。也能夠說,A是B子集,而且B中最少有一個元素不屬于A。18/43例:{a}

{a,b}。例:S1={a},S2={{a}},S3={a,{a}}定義1.4:在取定一個集合U以后,對于U任意子集而言,稱U為全集。全集是一個相正確概念.實數(shù)集對于整數(shù)集、有理數(shù)集而言是全集,而整數(shù)集對于偶數(shù)集、奇數(shù)集而言也是全集。19/43定理1.2:對于任何集合A,必有(1)

A,(2)A

A,(3)A

U。對于集合A={1,2,3},

,{1},{2},{3},{1,2},{1,3},{2,3}和{1,2,3}都是集合A子集。這些子集全體也可組成集合，這個集合稱為{1,2,3}冪集。定義1.5：設(shè)A是任意集合,A全部子集所組成集合,稱為集合A冪集,記為P(A),或記為2A,即P(A)={B|B

A}。有限集合S，|S|=k，則|P(S)|=?定理1.3:設(shè)A是有限集,則|P(A)|=2|A|。20/431.4集合運算一、運算定義定義1.10：設(shè)A和B是兩個集合,U是全集,(1)A和B并,記為A∪B,它是由A和B中全部元素所組成集合,即A∪B={x|x

A或x

B}。21/43(2)A和B交,記為A∩B,它是由A和B中公共元素所組成集合,即A∩B={x|x

A且x

B}。(3)A和B差,記為A-B,它是由在A中而不在B中元素所組成集合,即A-B={x|x

A且x

B}。22/43集合并,交,差,補也分別稱為集合并運算,交運算,差運算,補運算。例:A={1,2,3,4,5},B={1,2,4,6},C={7,8},U={1,2,3,4,5,6,7,8,9,10}。23/43定義1.11：設(shè)集合A1,A2,…,An,定義:A1∪A2∪…∪An={x|最少有某個i,1≤i≤n,x

Ai},稱為A1,A2,…,An并,記為A1∩A2∩…∩An={x|對每個i,1≤i≤n,x

Ai},稱為A1,A2,…,An交,記為24/43二、運算基本性質(zhì)定理1.4：設(shè)A,B,C是任意集合,U為全集,以下等式成立:(1)A∪A=A； A∩A=A (冪等律)(2)A∪B=B∪A;A∩B=B∩A (交換律)(3)A∪(B∪C)=(A∪B)∪C;A∩(B∩C)=(A∩B)∩C(結(jié)合律)(4)A∪(B∩C)=(A∪B)∩(A∪C)(分配律)

A∩(B∪C)=(A∩B)∪(A∩C)(5)A∪U=U;A∩U=A;A∪

=A;A∩

=

(恒等律)25/4326/43例：設(shè)A和B為兩個集合，則P(A)∩P(B)=P(A∩B)證實：先證P(A)∩P(B)

P(A∩B)再證P(A∩B)

P(A)∩P(B)證實集合相等，除了用定理1.3外，還可利用定理1.4給出基本等式來證實。27/43例：(A∪B)-C=(A-C)∪(B-C)28/43在集合并、交、差運算都是不滿足消去律。即A∪B=A∪C不能得到B=C例:A={1,2,3},B={3,4,5},C={4,5},A∩B=A∩C不能得到B=C例:A={1,2,3},B={3,4,5},C={3},一樣A-B=A-C不能得到B=C29/43下面引進(jìn)運算則含有消去律性質(zhì).A和B對稱差,記為A

B,A

B=(A-B)∪(B-A)。30/43實際上有(A∪B)-(A∩B)=(A-B)∪(B-A)31/43對稱差運算則是滿足消去律，即有定理：若A

B=A

C，則B=C證實留作習(xí)題對于多個集合運算,除了并和交含有結(jié)合律和交換律外,還有分配律和狄·摩根律:B∩(A1∪A2∪…∪An)=(B∩A1)∪(B∩A2)∪…∪(B∩An)B∪(A1∩A2∩…∩An)=(B∪A1)∩(B∪A2)∩…∩(B∪An)32/43伴隨數(shù)學(xué)發(fā)展，人們發(fā)覺單憑直觀經(jīng)驗建立起來集合概念是靠不住。在1895年康托爾本人舉例說明樸素集合論將造成矛盾,其中最有名例子是英國哲學(xué)家和數(shù)學(xué)家羅素(1872--1970)在19給出,在數(shù)學(xué)史上稱為羅素悖論33/431.5羅素悖論命題：能區(qū)分真假陳說語句。例：我是學(xué)生。今天不下雨。上述兩個都是命題。它們都能判別真假。祝你一帆風(fēng)順！你明天下午出去嗎？上述兩個都不是命題。34/43所謂悖論,是指對于命題Q,假如從Q為真,能夠推導(dǎo)出Q為假,又從Q為非真推導(dǎo)出Q為真,我們就說命題Q是一個悖論。顯然假如從命題P可引出一個命題Q,而Q是一個悖論,那么P也是一個悖論。說謊悖論有一個人斷言:“我正在說謊”。我們要問:這個人是在說謊還是在講真話?假如他在說謊,這表明他斷言“我正在說謊”是謊話,也就是說他在講真話。即他說謊,推出他是講真話(即沒有說謊)。另首先,假如他講真話,這表明他斷言“我正在說謊”是真話,也就是說他正說謊話,即他講真話,推出他在說謊(即沒有講真話)。35/43斷言“我正在說謊”就是一個悖論,因為我們無法斷言它真?zhèn)巍＜舭l(fā)師悖論一個村上,有一個剪發(fā)師公開宣告他給而且只給村子中全部自己不替自己剪發(fā)人剪發(fā)?，F(xiàn)在要問:誰給這個剪發(fā)師剪發(fā)?假如剪發(fā)師頭由他人給他理,也就是說剪發(fā)師自己不替自己剪發(fā),那么按照要求,這位剪發(fā)師應(yīng)該給自己剪發(fā)。另首先,假如剪發(fā)師頭由自己理,那么按照要求,剪發(fā)師不能給自己剪發(fā)。也是一個悖論：剪發(fā)師頭由他人來理,不行；剪發(fā)師頭由自己理,也不行。36/43羅素悖論將集合分成兩類,一類是集合A本身是A一個元素,即A

A,另一類是集合A本身不是A一個元素,即A

A。現(xiàn)結(jié)構(gòu)一個集合S:S={A|A

A}}也就是說S是由滿足條件A

A那些A組成一個新集合。我們要問:S是不是它自己一個元素?即S

S,還是S

S。即既不是S

S,也不是S

S,這個悖論就是著名羅素悖論。37/43集合{全部課程全體}和集合{全部教室}這兩個集合之間就存在著某種聯(lián)絡(luò)。實際上，在計算機(jī)中，離散對象之間總存在著各種各樣聯(lián)絡(luò)，這就是我們下面要介紹關(guān)系。首先將引進(jìn)笛卡兒積概念38/431.3笛卡爾積定義1.6：兩個對象a,b依一定次序組成一對,稱為有序?qū)?記為(a,b)。兩個有序?qū)ο嗟?a,b)=(c,d),當(dāng)且僅當(dāng)a=c和b=d同時成立。對于集合有{a,b}={b,a}，而對于有序?qū)t在a

b時，(a,b)

(b,a)。(a,a)是有意義39/43定義1.7：對n>0,n個對象序列形如a1,a2,…,an組成一組稱為有序n元組,記為(a1,a2,…,an),其中ai稱為第i個分量。兩個有序n元組相等當(dāng)且僅當(dāng)它們每個對應(yīng)分量相等。定義1.8：設(shè)A和B是兩個集合,定義A與B笛卡爾積為A×B={(a,b)|a

A且b

B},又稱A×B為A與B直積。例:設(shè)A={1,2},B={x,y},C={a,b,c},則A×B={(1,x),(1,y),(2,x),(2,y)};B×A={(x,1),(x,2),(y,1),(y,2)};B×A

A×B由此可知A與B直積是不滿足交換律。40/43A×C={(1,a),(1,b),(1,c),(2,a),(2,b),(2,c)};A×A={(1,1),(1,2),(2,1),(2,2)}。A×

=

×A=

定義1.9:設(shè)A1,