“什么是教育？教育就是當你把所學(xué)的東西都忘掉后，最終剩下的東西！”

“最終剩下的東西就是一個人的創(chuàng)新意識和學(xué)習(xí)能力J

把教學(xué)的著眼點集中在掌握科學(xué)基礎(chǔ)知識和訓(xùn)練創(chuàng)新能力上，著重培養(yǎng)科學(xué)的思維方

法，把知識傳授與科學(xué)探索融為一體，激發(fā)學(xué)生的好奇心和創(chuàng)造性。

教學(xué)質(zhì)量是“教育水平高低和效果優(yōu)劣的程度”(教育大詞典)

前言

0』集合論與圖論是數(shù)學(xué)的一部分

“對于大自然這本奧秘無窮的書，我讀不懂”。

——莎士比亞：《安東尼和克里奧帕特拉》(1564-1616)

“如果不理解它的語言，沒有人能讀懂宇宙這本偉大的書，它的語言就是數(shù)學(xué)工

——伽里略(1564—1642)

“在任何特定的理論中，只有其中包含數(shù)學(xué)的部分才是真正的科學(xué)”。

——康德(1724—1804)

數(shù)學(xué)不專屬自然科學(xué)，也不專屬社會科學(xué)，更不專屬于文學(xué)藝術(shù)。它是一種宇宙語言，為

一切文明生物共有、共享，

0.2主要內(nèi)容

“我想知道上帝是如何創(chuàng)造這個世界的。對這個或那個現(xiàn)象、這個或那個元素的譜我

并不感興趣。我想知道的是他的思想，其他的都是細節(jié)問題”。

——愛因斯坦(1879—1955)

本課主要講述集合論(SetTheory)：集合及其運算、映射及其合成、關(guān)系及其運算、

無窮集合及其基數(shù)。圖論(GraphTheory)：圖的一些基本概念、一些特殊的圖、樹及其性

質(zhì)、割點和橋、連通度、平面圖、圖的著色、有向圖。

基本思想和意義

我們從“集合”這個基本概念開始建立集合理論。就某種觀點來看，“集合”與“性

質(zhì)”是同義詞，是基本概念之一。這樣，

集合用來描述事物的性質(zhì)一一我們的研究對象，映時用來描述事物之間的聯(lián)系一一運

算、關(guān)系，從而為集合建立了結(jié)構(gòu)。于是，為建立系統(tǒng)的數(shù)學(xué)模型提供了數(shù)學(xué)描述語言一

-工具，代數(shù)系統(tǒng)就是在集合上引入運算。集合論又提供了研究數(shù)學(xué)模型的性質(zhì)，發(fā)現(xiàn)新

聯(lián)系的推理方法，從而找出事物的運動規(guī)律。而圖論是上述思想的一個具體應(yīng)用，事實上,

圖論為任何一個包含了一種二元關(guān)系的系統(tǒng)提供了一個數(shù)學(xué)模型；部分地，也因為使用了

圖解式表示方法，圖就具有一種直觀的和符合美學(xué)的外形。

在圖論中，許多結(jié)果是初等的，但也有大量的十分復(fù)雜的問題可以難倒最老練的數(shù)學(xué)

家。

0.3在計算機科學(xué)/技術(shù)/工程中的意義

能形式化就能自動化。

對計算機科學(xué)/技術(shù)/工程而言，形式化尤為重要。利用形式化描述給程序設(shè)計提供了

方便，從而實現(xiàn)了自動化，

集合論可以看成一種通用語言，一切必要的數(shù)據(jù)結(jié)構(gòu)都可以由集合這個原始的數(shù)據(jù)結(jié)

構(gòu)而構(gòu)造出來。實際上，數(shù)學(xué)發(fā)展的歷史可以看成是?個煞費苦心或精心制成的數(shù)據(jù)結(jié)構(gòu)。

首先，我們有整數(shù)，然后有有理數(shù)、代數(shù)數(shù)，在經(jīng)過一陣斗爭以后，我們有實數(shù)、復(fù)數(shù)、

函數(shù)的一般概念等等。最后，人們終于明白開頭所說的思想，計算機科學(xué)家或許可以利用

這個經(jīng)歷。其次，19世紀后半期，數(shù)學(xué)家把函數(shù)定義為笛兒乘積的子集，從而把函數(shù)視為

集合，這是嚴格的。但對計算機科學(xué)家是不合適宜的，他們更喜歡用規(guī)則來定義函數(shù)。

集合論是數(shù)學(xué)的基礎(chǔ)，也是計算機科學(xué)的基礎(chǔ)。集合論和圖論是算法與數(shù)據(jù)結(jié)構(gòu)、形

式語言與自動機、數(shù)據(jù)庫原理、計算的復(fù)雜性理論等課的先修課。而圖論的基本知識則將

始終陪伴我們，直到……，

數(shù)學(xué)要教會人如何進行邏輯推理，如何進行止確的抽象思維，如何在紛繁的事物中抓

住主要的聯(lián)系，并如何使!IJ明確的概念，等等。這對計算機技術(shù)及應(yīng)用也是至關(guān)重要的，

在其他任何領(lǐng)域同樣重要，

本課程的特點

1自給自足，不需要預(yù)先的知識準備。學(xué)習(xí)本課的前提實在僅僅是不可捉摸的所謂“數(shù)

學(xué)上的成熟”。

2概念多，但都有實在的具體的實物背景，最后要落實到抽象的定義上，概念是第一

位的。

3作為一門數(shù)學(xué)課，與以往不同的是以證明為主而不是以計算為主。因此，要學(xué)會證

明技術(shù)，學(xué)會分析問題和解決問題的思想方法。它能培養(yǎng)你誠實！

4與計算機科學(xué)/技術(shù)聯(lián)系緊密，是最常用、最有用的數(shù)學(xué)內(nèi)容之一。

5沒有什么公式要你背。需要的僅是智力上的成熟并樂意進行獨立思考！

0.5怎么教

?“只有學(xué)生能理解的定義才是令人滿意的?！薄狿oincare于1909年

但數(shù)學(xué)教師并沒有十分注意這一點。講清概念的背景，最好先從具體的實例出發(fā)，直

觀地給出實在的東西，然后推廣或抽出本質(zhì)得到抽象概念。沒有抽象就沒有科學(xué)！

“從具體到抽象是數(shù)學(xué)發(fā)展的一條重要大道，因此具體例子往往是抽象概念的源泉，

而所用的方法也往往是高深數(shù)學(xué)里所用的方法的依據(jù)。僅僅熟讀了抽象的定義和方法而不

知道他們具體來源的數(shù)學(xué)工作者是沒有發(fā)展前途的，這樣的人要搞深刻研究是可能會遇到

無法克服的難關(guān)的"。一一華羅庚：《數(shù)論導(dǎo)引》

“難處不在于有公式去證明，而在于沒公式之前，怎樣去找出公式二一一華羅庚

總之，教育的目的或重點是理解概念、理塔方法、理解定理。而今應(yīng)多一個就是怎樣

分析、處理這眾多的信息以達到思考它、理解信息,從中獲取知識，增長智慧，創(chuàng)造生活。

?證明、解題：發(fā)現(xiàn)解法

已知的事物和要求的事，已知量和未知量，假設(shè)和結(jié)論，在原先開始時隔開的事物和

想法，我們就是要在這原先是隔開的事物或想法之間找出聯(lián)系。被聯(lián)系的事物原來離得越

遠，聯(lián)系的發(fā)現(xiàn)者的功績也就越大。有時我們發(fā)現(xiàn)這種聯(lián)系就象一座橋：一個偉大的發(fā)現(xiàn)

使我們強烈地覺得象是在兩個離得很遠的想法的鴻溝間架上了橋。我們常常看到這種聯(lián)系

是由一條鏈來貫穿的：一個證明象是一串論據(jù)，象是一條由一系列結(jié)論組成的鏈，也許是

一條長鏈。這條鏈的強度是由它最弱的一環(huán)來代表的。因為哪怕是只少了一環(huán)，就不會有

連續(xù)推理的鏈，也就不會芍有效的證明。對于思維上的聯(lián)系，我們更經(jīng)常使用線索這個詞。

事實上，那種創(chuàng)造發(fā)明的要素，那種起指導(dǎo)和推動作用的直觀要素，雖然常常不能用

簡單的哲學(xué)公式來表達，但是它們都是任何數(shù)學(xué)成就的核心，即使在最抽象的領(lǐng)域里也是

如此。

一個證明或算法常常取決于一個中心思想，而這個思想本身是直觀的、簡單的。一個

好的報告人（教師）應(yīng)當能從證明（算法）中提取出關(guān)犍思想,并且設(shè)法把它講得直觀而

明顯,使得每?位聽眾都能夠懂得它，體會它，并記住它以作今后可能的應(yīng)用。嚴格的邏

輯證明或計算有時無非是直覺（觀）的一種數(shù)學(xué)加工和精確化而已。

?瞻前顧后

站在新的概念、理論、方法和觀點看已學(xué)過的知識（在這里是微積分、線性代數(shù)、概

率論、C程序設(shè)計語言等）有時會更清楚，顯得簡單，理解會更深刻；我們也將隨時指出

本課的內(nèi)容在計算機科學(xué)/技術(shù)/工程中的應(yīng)用，特別是在后繼課一數(shù)據(jù)結(jié)構(gòu)與算法、形

式語言與自動機、編譯、數(shù)據(jù)庫原理、計算復(fù)雜性理論等中的應(yīng)用。但不能詳述，目的是

告訴你現(xiàn)在值得花點精力學(xué)它。

?基本概念必須抽象化

要問當作實體的這些.時象是什么，這是沒有意義的，即使是有的話也不可能在數(shù)學(xué)范

圍內(nèi)得到解決。所有適合它們的論斷都不涉及到這些實體的現(xiàn)實，而只說明數(shù)學(xué)上“不加

定義的對象”之間的相互關(guān)系以及它們所遵循的運算法?！翱沈炞C”的事實只是結(jié)構(gòu)和關(guān)系。

?不要期望百分之百地聽懂每個細節(jié)，某些細節(jié)應(yīng)獨立思考自己弄懂，這才會使你

愉快。

0.6怎么學(xué)

?一般的學(xué)習(xí)只是一種模仿，而沒有任何的創(chuàng)用。學(xué)習(xí)應(yīng)該以思考為基礎(chǔ)。思考由

懷疑和答案所組成。學(xué)習(xí)便是經(jīng)常懷疑，經(jīng)常隨時發(fā)問。懷疑是智慧的大門，知道的越多，

就越會發(fā)懷疑，而問題就越多。所以，發(fā)問使人進步，發(fā)問和答案一樣重要。

?在獨立思考之前，務(wù)必先有基本知識?；A(chǔ)知識是研究的工具，所謂“獲得基礎(chǔ)

知識”，并不足形式上讀過某一課程，而足將學(xué)過的東西完全弄懂。有如吃東西，必須完全

消化，變成自己的細胞，才能長成肌肉。在大學(xué)階段，最重要的是獲得一個廣而深的基礎(chǔ)。

所謂獨立思考，適宜用在學(xué)習(xí)時對課題從各個不同觀點,層次的了解上，而不是不屑學(xué)習(xí)

課程而思考。

學(xué)習(xí)中，概念是第一位的，概念的背景（直觀原型）、抽象定義的內(nèi)涵和外延要準確，

應(yīng)用時才能自如。

-學(xué)習(xí)的一種方法，經(jīng)常還是唯一的方法，就在于首先犯錯誤。我們在學(xué)習(xí),多數(shù)

時間在通過犯錯誤來學(xué)習(xí)，這是事實。這個事實在我們克服事與愿違一據(jù)哥德爾說“世

界的意義”在此一的努力中占據(jù)很大的分量。如果我們從不犯錯誤，生命的意義會喪失

殆盡。

?教學(xué)、學(xué)習(xí)是?個過程，是毛毛雨，不斷地滋潤。在傳授知識和技術(shù)的過程中,

偶爾傳授教訓(xùn)，但這種教訓(xùn)對你們沒有親身體驗，不會變成有用的經(jīng)驗。對「知識來說，

沒有教訓(xùn)作為根基，知識只能是紙上談兵。因此,上課、讀書、復(fù)習(xí)、討論、做實驗、自

己編程序、上機調(diào)試排錯，…，是絕對必要的。那種抄別人作業(yè)、考試作弊、不上課不看

書，……是沒有希望的。

?個作弊的民族怎么可能進步和強大呢？

提倡學(xué)習(xí)中互相討論、辯論、提出不同的方法。

?記住，數(shù)學(xué)以及其他理論學(xué)科的書，不能讀得太快，也不能期望讀一遍就全弄懂。

?生活的根基不僅包括我們得到的所有的答案，而且還應(yīng)該包括我們提出的所有問

題。

?輔導(dǎo)答疑

這是任課教師與學(xué)生直接交流、溝通思想的時間。對學(xué)生一視同仁應(yīng)當是教師的基本

心理，而善待每個學(xué)生是教師應(yīng)當堅持的教育原則。而學(xué)生應(yīng)充分利用好這段時間，在這

時

?教師為你解答經(jīng)你努力但尚未弄懂的問題。沒有經(jīng)你思考的習(xí)題、問題最好暫不

問，否則收獲不大。對教師而言，

不要立即披露你的全部秘密一一讓學(xué)生在你說出來之前先去猜一一盡量讓他們自己去

第1部分集合論

第1章集合及其運算

內(nèi)容提要:

I.集合(set)、屬于關(guān)系￡、集合的表示方法、空集

2.子集(subset)、兩個集合相等，鼎集(powerset)、集族(以集為元素的集)、證明兩個

集相等的方法

3.集合的運算：并(union)l」、交(intersection)G、差(subraction)對稱差(symmetric

difference)△，各自的性質(zhì)及相互聯(lián)系

4.求補(complement)運算。(二一,CJ及DeMorgan律

5.迪卡爾積(Cartesianproduct)及其性質(zhì)

6.有限集合的基數(shù)(cardinalnumber)、基本的計數(shù)法則、容斥原理

本章重點：

概念:集合、差、對稱差、笛卡兒乘積、有窮集基數(shù)。

方法:證明兩個集合相等的方法必考，必須掌握；

基本的計數(shù)法則及容斥原理在占典概率論中的應(yīng)用。

應(yīng)用:古典概率模型、跳舞問題的數(shù)學(xué)模型。

§1集合(set)的概念

本課講授撲素(直觀)集合論

1.1集合

集合是數(shù)學(xué)的基本(初始)概念之一，基本概念是不能定義的，因為沒有比它更基本

的概念。

一個集合就是一些互不相同的東西(事物、對象)構(gòu)成的整體。

東西或事物，以后稱為對象或元素，可以是具體的，也可以是思想上的抽象的思維。

重要的是這些對象是可以區(qū)分的，而集合則是一些這樣的對象的整體。構(gòu)成這個整體的那

些對象叫做它的元素。一個對象相對于一個集合而言是在這個整體里還是不在這個整體

里，前者稱為該對象屬于給定集合一一是它的一個元素，后者稱為不屬于該集。

在數(shù)學(xué)里，我們常用一個符號，例如A,來稱呼一個集合。在語言上，A是集合的名

字。在這里實際上是它的縮寫。例如，由1，2,3構(gòu)成的整體記為人=｛1,2,3｝。設(shè)A為

一個集合，若元素a在A中，則記為a"讀成“a屬于A”；若。不在A中，則記為aGA

或并且讀成“。不屬于A”。

于是，我們引出三個基本概念：集合、元素、屬于關(guān)系￡一謂詞七反映了元素與

集合間的屬于或不屬于關(guān)系，它是二值的。

1.2集合的描述方法

枚舉(列出)集中的所有元素，在左右加上花號1與1,｛與｝表示其間的元素構(gòu)成一個

整體。例如

A=｛1,2,3,4｝

是由1,2,3,4構(gòu)成的集。注意，集合中的元素沒有次序關(guān)系，因此A可寫成

A=(1,3,4,2｝

由1到100的整數(shù)構(gòu)成的集合記為

B二｛1,2,…，100｝。

其中“…”不是集合的元素，它用來代表那些未列出的但已為我們所知的那些整數(shù)。用這

種方法，借助于有關(guān)知識，還可描述無窮多個元素構(gòu)成的集。例如，全體正整數(shù)的集可記

為

N=｛1,2,3,…｝。

描述集合的另?種十分重要的方法是給出其元素所應(yīng)具有的性質(zhì)，其一般形式為

C=｛x\P(x)｝三｛x:P(x)｝

即具有性質(zhì)戶的那些元素構(gòu)成的集。P(x)是關(guān)于變元X的命題，P(x)為真時的X之集。

例如

B=\x\x是正偶數(shù)｝三｛x|x￡N且21X]o

以后，我們常用這種方式描述或定義具體的集合。

在此我們并沒有使集的定義更明確，因為“性質(zhì)”和“集”從某種觀點看來是同義詞。

二十世紀最偉大的邏輯學(xué)家、數(shù)學(xué)家、科學(xué)家和哲學(xué)家、思想家?guī)鞝柼?哥德爾(Kun

Godel,1906.4.28—1978.1.14)本體論的兩大基本范疇——也就是“東西”或全體存在物的

兩大基本類型一一是客體與概念?？腕w由數(shù)學(xué)客體及其他客體組成。數(shù)學(xué)客體即是“純粹”

集合。集合在某種意義上包括在概念中，因為哥德爾猜想每個集合都是某個概念的外延。

集合是外延，概念則是內(nèi)涵。

顯然，在這里討論集合論中的哲學(xué)問題是不合適的，也為時過早。在第四章末將略作

窺探并引出公理化集合論，但不作探討。

L3空集

沒有元素的集稱為空集，空集記為6。于是，e=｛｝。

我們假定空集是存在的，方便的。

§2子集、一集、兩個集合相等

我們利用基本概念來定義其他概念，并稱為導(dǎo)出概念。

2.1子集(subset)

定義2.1設(shè)A與B是兩個集合，如果對A的每一個元素X都有了￡8,則稱A是B

的一個子集，記為人三8,并讀成“A包含在B里或B包含著A”。

于是當且僅BreA有顯然，B當且僅當不屬B的元素必也不屬

于A。因此，我們有

定理2.1空集是任一集合的子集。

定理2.2設(shè)A,B,C是集合且BqC,則AqC,AqA。

定義2.2設(shè)A=8且使人至A,則稱A是B的一個真子集,記為AuB。

易見，①uAoAw中。

if4<=4且4匚。，則AuC。

子集的概念使我們可以由已知集產(chǎn)生新集合。

2.2集合的相等

定義2.3如果集合X與Y有相同的元素，則稱X與Y相等，并記成X=Y。形式地，

如果XqY且YqX則說X與Y相等，并記為X=Y。

X=Y并不意味著X與Y的定義方式一樣。

由定義2.3,我們得到證明兩個集合X與Y相等的方法是：證明XqY,同時再證

Y^X.在下節(jié)我們將作出一些示范。

我們發(fā)現(xiàn)集合之間的包含關(guān)系“q”與數(shù)間的小于或等于關(guān)系有類似的性質(zhì)：

10對每個集A,AqA；a<a；

2°if且8口4,則人=13；ifa<b^<aMa=b；

3°if4口8且87。，則AqC。if4W匕且h?c,貝以《c。

但也有不同之處：對任兩個數(shù)以。，

a<h,a=b,h<a

有且僅有一個成立。對集合而言則不成立，可找到A,B使AqB,A=B,BqA都不成

立。例如A={1},B={2},>

注意，Au3oAqBjBLA=3。

A工304qB或B生Ao

A^B<^3aeA使。GB

這是在訓(xùn)練學(xué)生的邏輯思維，對程序設(shè)計至關(guān)重要。

2.3募集(powerset)

定義2.4設(shè)X是一個集合，X的所有子集(包括力和X在內(nèi))的集合稱為X的累集,

并記為2*或虱x)或P(x),即2X=Q：)=P(x)={A|AqX)。

例如，若X=［1,2,3),則

2X=仲,{1},{2},{3},{1,2},{1,3},{2,3},{123}}。

一般地，以集合為元素的集稱為集族。這并不是新概念，集族也是集合，只是提醒讀

者，其元素又是集合。這沒有什么不好理解的，因為集合也是東西一一對象，一些集合也

可構(gòu)成一個整體，即集合，

設(shè)/為一個集合，對/的每個元i對應(yīng)一個集4,這些凡構(gòu)成的整體一一集族，

/稱為標號集。例如，/={123}則

/={A,A2,Ay}={4}間］2,3}

注意，這些兒未必不同。

若集X中只有有限個元素，則X稱為有限集，其元素的個數(shù)記為1X1。例如I①1=0；

若力={123},則|X|=3。

設(shè)X是一個集，4cXo若|A|=K,則A是X的一個K?子集。如果|X|=〃，X的

所有K-子集共有(2)個。

定理2.3設(shè)X是一個集合且|X|=〃，則

|2-|二|P(X)|=2岡=2"。

［迪］應(yīng)用數(shù)學(xué)歸納法，施歸納于〃即可。#

定理2.3表明塞集的名稱與記號的來歷。

注意，①H{中}，①e{0}且①1{6}。

作業(yè)：P8—3,4；P9—5,6,7；P33—5*。

§3集合的運算

“在許多精確的科學(xué)領(lǐng)域中，常常采用各種各樣的符號運算.這些運算服從熟知的規(guī)

律，它們不僅能使所獲得的公式簡單化，而且在許多重要場合中，也往往簡化科學(xué)結(jié)論的

邏輯結(jié)構(gòu)”。另外，由已知的對象通過運算后可以得到新對象。

在集合論中，給定集合X和匕有各種方法把X和丫聯(lián)合成一個新集合。集運算大多

都反映某種邏輯運算。用直觀的文氏圖描述這些運算及性質(zhì)富有啟發(fā)性，但不能作邏輯證

明的依據(jù)。因為我們認為：

直觀是真理的源泉，而不是檢驗真理的最終標準。一一無名氏

本節(jié)的內(nèi)容在中學(xué)學(xué)過一些，理解這些內(nèi)容不困難.因此，本節(jié)的重點在于：

1°使用明確的概念，學(xué)會從概念開始進行正確的邏輯推理。

2。學(xué)會如何證明兩個集合相等的方法。

3.1并(union)運算U

定義3.1設(shè)A與B為集合，屬于A或?qū)儆?的所有元素構(gòu)成的集合稱為4與3的并

集，并記為AUB。亦即AU3={x|xcA物￡3}。

在這里，邏輯聯(lián)接詞“或”是可兼的，即如果xeAUB，則有以下三種情況：(1)

xeA,x'eB；(2)(3)xeA,xe13

注意，X'G4JLVBo

定理3.1(并運算本身的運算規(guī)律)設(shè)4,B,C是任意三個集合，則

1°交換律成立：ALB=3UA；

2°結(jié)合律成立：(AU8)UC=AU(8UC);

3°塞等律成立：AUA-/A；

4°空集中是并運算U的單位元：WA=A；

5°AU4=4oA=8。

［證］1°、3°、4°、5°是顯然的。以證明2°為示范，說明如何證明兩個集合相等。

證明可用一棵樹表示如下：

證(4U磯CNAUIUO

xe(AUB)UC

XGA{JBXGC

xeAxeBxeB\JC

XGALK5UOxeBUCXGAU(BUC)

AG^U(BUC)

再證AU(8UC)q(AUB)UC

XGAU(BUC)

XEAxeZ?UC

XGA\JBxeBXGC

ze(AU8)UCXWAUBxe(4UB)UC

X€(AUB)UC#

由結(jié)合律，(AU8)UC，AU(BUC)口J記為AU5UC。

若A，&，…，4為集合，則它們的并記為

41141>,24=04={刈對某個〃4區(qū)〃，164}。

/=!

集4,4,…的并記為

AU4U…=0d=U4={x|于eN使A-GAJ,其中N={1,2,…}。集族{A,}“/口各

*=1；sN?'

集之并為

U4={#巧/使得XW4}。

3.2交（intersection）運算D

定義3.2設(shè)x和丫為集合，由x與丫的公共元素組成的集合稱為x與y的交集，記

為xnv，即

XHY=｛x\xeX.^xeY｝。

若xnv=①，則稱x與Y不相交。

XEXC\Y<^xeX^xeY.

定理3.2（交運算的運算規(guī)律）設(shè)4B,C為三個任意集合，則

6°交換律成立:4r8=8C|A

2二結(jié)合律成立：（AnB）nc=An（8nc）

亡某等律成立：ACA=A

9°空集為零元素:GfM=a）

10°4nB=

定理3.3（分配律一一并、交運算之間的聯(lián)系）設(shè)4B,C為任意三個集，則

ii°/in（BUc）=Mng）u（/inc）：

12°AU（gne）=MUB）n（AUC）o

其次還有11°式成立當且僅當12°式成立。

定理3.4（吸收律）設(shè)A和B為任意集,則

13°AC\（AUB）=A：

14°AU（AlB）=A°

集A，A〃的交記為

4PIA?n…CIA“=nA=｛%ixeA」=I,2,…,〃｝。

r>l

集序列A，&,…,A〃…的交記為

CIA,=nA：=｛刈A”,〃=1,2,3,…｝。

Z=lieN

集族｛2｝國的集之交為

PlAz=｛x|xe4e,e/｝o

兵/

3.3差運算\

定義3.3設(shè)A與3為集，屬于A但不屬于B的?切元素構(gòu)成的集稱為A與8的差集,

記為讀作“A差8”，即A\8=｛x|x￡A且/至B｝。

于是，x~eA\Bx~eA^xGBo

差運算不滿足交換律，也不滿足結(jié)合律。但交運算對差運算滿足分配律。

定理3.5設(shè)A,B,。為集合，則

15°、40（8\。）=（408）\（400。

［證］設(shè)XG/\n（B\C）,則xe4iLreB\C從而xe^KxeC,故

xe目/至AflCxe右邊。類似J也，若％w右邊推出xe左邊，故左=右。

3.4對稱差（symmetricdifference）運算A

定義3.4設(shè)A,4為任意集合，集合（A金）U（小A）為A與笈的對稱差，記為AA8。

顯然，

4A8=(A\8)U(8\A)={x|x￡AU砥x至An8}=(AU8)\(Ar)8)。

例如,若4={123,4},8={23,5},則

AAB=(A\3)U(3\A)={1,4}U{5}

={1,4,5}=(4UB)\(AnB)={1,2,3,4,5}\{2,3}={1,4,5}

定理3.4(對稱差運算的規(guī)律)設(shè)A,B,。為三個任意的集合，則

160交換律成立:AM3=B\A；

17。結(jié)合律成立:(AAB)^C=AA(BAC)；

鱉①是單位元：①A4=A

12二人的逆元為A：AAA=中；

20°交運算對對稱差滿足分配律:

An(BAC)=(AC|B)A(AnC)o

[證]160,18°,19°顯然。17。留為作業(yè)。對20°WAn(BAQ=An[(C\B)U(B\C)]

=[An(c\B)]U[AnB\c)]=[(Anc)\(/in^)]U[AnB)\(Anc)]=(AnB)A(/ino

3.5補(complement)

定義3.5設(shè)AqS,集S\A稱為A對S的補，記為八°(八',彳,。5八)。

設(shè)4=S；貝IJ

21°CSO=S；

22°G$S=①；

23°A\JAC=S；

24°Ar\AC=<D；

25°4C=：

26°A\B=4A?Co

實際上，令S=4U及則ACIB。=4D(S\B)=(AnS)14nB=A\(4D8)=A\B

定理3.7(DeMorgan公式)ABqS，

27°=ACQBC

28°(AAB)C=ACU5C

一般地

(uA,尸=n屋,(。尸=nA；

氣/-4e/-ielgu

用日常語言描述為

集的并之補等于各集之補的交。

各集之交的補等于每個集的補之并。

最后，顯然有

29°(Ac)c=Ao

ccc

習(xí)題1、證明：Au(/tn?)=(AnB)o

習(xí)題2、證明：(ACn8)U(An8C)U(ACn8C)=(4nB)c。

作業(yè)：PI6—17,1-8；10-11；15,16o

P20—21,1-5,其中4題較難。

習(xí)題4、證明：若(zl\A)U(A\Q=「，則

4q(B\C)U(C\A)=4n8nC=6O

§4笛卡兒乘積運算

§3中介紹的五種集合運算有個共同特點：

如果A,8qS,則AIJ氏ACl8,A\8,AA8,A。qS。

本節(jié)將要定義的笛卡兒乘積運算則不具有此特點，其思想來源于笛卡兒發(fā)明解析幾何

的思想。當在平面上建立了坐標系后，平面上的點就可用實數(shù)對表示了，幾何圖形就對應(yīng)

于存對的集合，從而開創(chuàng)了用代數(shù)方法研究幾何的先河。解折幾何的發(fā)明足數(shù)學(xué)史上最為

偉大的發(fā)明之一，應(yīng)該大書而特書。解析幾何的發(fā)明，在數(shù)學(xué)概念思維領(lǐng)域?qū)崿F(xiàn)了遢差

系的溝通。這是笛卡兒(Descartes,Rend：1596-1659,法國哲學(xué)家、物理學(xué)家、數(shù)學(xué)家、

生理學(xué)家)留給我們的寶貴思想和科學(xué)遺產(chǎn)。

要知道，從這個世界得到點什么比留下點什么容易得多。

4.1序?qū)Α撝辛硪粋€基本概念

一個集合由其元素確定，而與元素的次序無關(guān)。但有時我們需要注意次序。在這里，

“次序”是直觀的，并未給出形式定義，這對我們而言已足夠了。

兩個元素a和b組成的序?qū)τ洺?a,b),a在b的前面，或第1個位置為a,b在第2

個位置。在這里(a,b)與(b,a)不問，除非a=b。

注意，序?qū)?a,b)不是集合(含2個元)，因為在這里a與b可相同且有次序。當把

序?qū)σ暈閷ο髸r，如何區(qū)分序?qū)δ?？我們?/p>

(a,b)=(c,d)當且僅當a=c,b=do

4.2集合的笛卡兒乘積運算X

定義4.1設(shè)X和Y是集合，X與Y的笛卡兒乘積是一切形如",)，)的序?qū)χ?/p>

為Xxy,其中亦即

Xxy={(x,y)UeXo'er}o

如果R為全體實數(shù)之集，則當在平面上建立了坐標系后，平面.上的點之集就表示外R。

這也是我們?yōu)槭裁窗堰@個運算叫做笛R爾乘積的原因。

例如,若乂={1,2},丫=佃向,則

Xxy={(l,a),("),(2,a),(2,L)}

yxX={(a,1),3,2),(6,1)02))

XxX={(l,l),(l,2),(2,l),(2,2))

YXY=((6Z,(a,b),(b,a),(b,b)}。

由此可見，一般說來，Xxr^rxx,即交換律不成立。但我們有

定理定1設(shè)A,B,c為集合，則

30°AX(BUC)=(4XB)U(4XC)

31°AxMC）=（Ax4）n（AxC）

320人x（8\C）=（人xB）\（八xC）

4.3有序〃元組

推廣有序?qū)Φ母拍?，我們有有序〃元組（簡稱〃元組）（巧心,….〃），其中修為第1

個，叼為第2個，…"〃為第〃個，其特性為

（%,g，…,冊）=（瓦,壇,…,b,J

當且僅當勺=/4424=1%。

在C語言中是一維數(shù)；在線性代數(shù)為〃維空間中的向量；長為〃的序列；這是一個十

分有用的工具。

集合A，&一??）”的笛卡兒乘積記為AxAzx.--xA,定義為集合

｛（。1，。2,…，％）1%eA，i=l,2｝，即

A\XA2X???XAn=｛（。］,。2,…M"）I41￡4，生￡A2,???,??￡AJ。

/?元組、笛卡兒乘積是十分有用的概念，它是映射、二（〃）元關(guān)系的基礎(chǔ)。在數(shù)學(xué)、

計算機科學(xué)中是重要的描述工具，是建立數(shù)學(xué)模型的有用工具之一。在形式語言、自動機

理論等課中會經(jīng)常使用這一工具。

§5有窮集合的基數(shù)

計數(shù)的概念是一個復(fù)雜的概念，它建立在更基本的概念一一“一一對應(yīng)”--------配

對之上。

我們是用數(shù)數(shù)的方法計數(shù)的，數(shù)數(shù)的過程是建立一一對應(yīng)-------配對的過程。

5.1對應(yīng)

定義5.1設(shè)X與y為集，/qXxy。如果VreX有唯一的yeY使（乂）”省聲￡丫有

唯一的xGX使（乂y）€/,則/稱為X到Y(jié)的---對應(yīng)VjeX,那個唯一的使（x,y）ef的元

素記為f（x）。

于是X到丫的一個一一對應(yīng)是一個法則了,對X的每個元x,根據(jù)f有唯一的），eY與

之對應(yīng)，而每個ycY有唯一的x使在/下，x對應(yīng)于y。

例如，X=｛（l,2,3｝,y=（4也c｝,財=（（lm）,（2/）,（3,c）｝是X到y(tǒng)間的一個一一對應(yīng)。這

時，f（l）=aj（2）=bj（3）=c,如右圖（略）所示。

如果x與y間存在一一對應(yīng)，則記為x~y。

5.2有限集及基數(shù)

定義5.2設(shè)X是一個集合，若X=①則稱X為有窮集且說X的基數(shù)為0；否則X。①，

若存在一個自然數(shù)〃使X與｛1,2,…,〃｝間有一個一一對應(yīng)，則稱X為有限（窮）集且〃稱為

X的基數(shù)。否則X稱為無限集。有限集X的基數(shù)記為因，

5.3基本計數(shù)法則（原理）

定理5.1設(shè)X和丫為有限集。

1°相等法則：ifx~y,ixi=|y|；

20加法法則：ifxny=<t>，貝IJIXUWWXI+IW

3°乘法法則：|XxyRX|“y|。

設(shè)X1,…,X”為有窮集，應(yīng)用數(shù)學(xué)歸納法可以證明

|X.x...xXM|=|X1|.|X2|……|X'|

n_JL,

若xnxj=①,i。，ij=12…,〃，則?ux,?i=z?*，

*=，/=l

4°XgS且|513則|X°|=|S1-1X1。

5.3容斥原理

定理5.2設(shè)A,8為有窮集，則

IAU6RAI+I0一|4仆8|。

[證]AUB=AU(8\A),An(B\A)=(D(否則，三工€AA(3\A),x￡A,ReB\A,矛

盾。)于是|AU8|=I八l+|B\A|°又小4=3\(405),所以8=(B\A)U(八D3),故

|B\A|=|B|-|AnB|,代入即得證。

類似地

|AU8UCHAU8|+|C|-|(AU8)nC|=|A|+|8|+|C|-|An8|-|(AnC)U(8nC)|

HA|+|B|+|C|-|AnB|-|AnC|-|Bne|4-MnBAC|

定理5.3(容斥原理的形式之一)設(shè)…,4“為有限集，則

IUAI=ZIAi-EIAHAI+Zian&n4i+…+(—i嚴inn…nA"

“If=l7l^i<j<k^n

定理5.4(容斥原理的形式之二)設(shè)AuS,i=l,2,….以|SI<8,則

IAAHSI-IUAHSI-XIAI+XlAAAj-|+…+(-1)"IACI&n…ClA”|

,'|'Ti-iIf""

5.4例題

例5.1甲、乙、丙三人在同一時刻開始放向一種炮，每人各放21個。甲每5秒放一

個，乙每6秒放一個，丙每7秒放一個。試問共能聽到多少個炮聲？

解：令A(yù),B,C分別為甲、乙、丙放炮時刻之集，則

4={0,5,10,…,100}

4={0,6,12,…』20}

C={0,7,14,-..,140)

顯然，|*=|3|=|。|=21,并且

?ss「10°]???o

14nBi=|—~~-+1=4.[AAC|=———+1=3?

15x6」15x7」

MCI/界]+1=3,1408001=1^^/1+1=1。

|_6x7J[5x6x7

于是，

|4UBUC|=21x3-4-3-3+1=54。

所以，共聽到54個炮聲。#

例5.2(Euler裝錯信簽問題)一位秘書寫了〃封信和〃個信封，然后隨機地把信裝入

信封，試求每封信都裝錯了信封的概率是多少。

解：解古典概率問題的第1步是確定基本事件的集合Q。在這里，。是〃封信裝入〃

個信封的所有不同裝法之集，每一裝法是一個初等(基本)事件。把信封編號為12…視

為位置，把相應(yīng)信也編為相應(yīng)的號12…，，人于是一種裝法就是12…，〃的一個全排列。所

以，C是1,2,…/的所有合排列集S”,即。=S“，我們知道，

由于Q是有限集，C的每個子集都是事件，即事件之集為2。=/,它是一個代數(shù)數(shù),

即Cw/且ifABE/,則AUaAfiaw/。

最后，賦以每個初等事件(樣本)一個數(shù)23)使之04尸(0?1且2〃初)=1。于是得到

CDE(1

一個概率模型(C,凡P)。在這PQ)=l/〃!°

我們要求事件4=宿，2工Li2H2,…,i,尸〃J也…eQ｝的概率，即

|A|/|CHA|/M。于是歸結(jié)為求|川。

應(yīng)用容斥原理求IAI需把A分解成若干集之并或交(視應(yīng)用形式一還是形式二)，這

是關(guān)鍵的一步，也是“能力”的表現(xiàn)。在此，令E是Q中元的性質(zhì)：C中g(shù)具有性質(zhì)2當

且僅當在3中i排在第，個位置上，而其他數(shù)j豐i可排在任何位置上。令凡為具有性質(zhì)P,的

那些排列之集，i=l,2,…于是，

易見，應(yīng)該應(yīng)用容斥原理的形式二來求IAI。對此

l4nAj|=A-2)!,iwj。

?A,nA,n…n&1=(〃一幻!」〈j<…〈乙=

因此，

IA|=|3A；|=〃!—(：)(〃-1)!+(介(〃-2)!—+(-1)<)(〃-幻!+,一+(-1)”(；；)0!

/=1

=〃!(1一:+《-；+…+(-1)?、+…+(-1)〃；)=〃!(/-｛卓-)

?????r=w+l>

|A|/n!=e-,-0.3679

/=?+1''

有趣的是，當〃>10時，這個概率幾乎沒多大變化。

作業(yè)：P25—26：1,2,3,5,6,7,8,9

P33—34：1—5

本章總結(jié)：

1、概念：集、子集、累集、u、n、\、△、u、。、x,基數(shù)

2、結(jié)論：運算的性質(zhì)、計數(shù)法則、容斥原理*

3、方法：證明兩個集相等的方法：邏輯推理。第1章教學(xué)記事；學(xué)時分配：共6學(xué)時。

第2章映射(mapping)

內(nèi)容提要

1.映射(mapping)>單射(injection)>滿射(sinjeclion)、雙射(bijeciion)、恒等映射(idemica】

mapping)、部分映射

2.映射的一般性質(zhì)

3.鴿巢原理、奇偶性原理、最大一相似一譯碼

4.映射的合成運算、逆映射

5.置換(permutation)

6.應(yīng)用：二元運算、集的特征函數(shù)

本章重點

概念：映射、單(滿、雙)射、合成運算、置換、逆映射、特征函數(shù)、/''(A)

方法：置換的循環(huán)置換分解

應(yīng)用：復(fù)合函數(shù)應(yīng)用概述，建立數(shù)學(xué)模型DFA

自17世紀近代數(shù)學(xué)產(chǎn)生以來，函數(shù)的概念一直處于數(shù)學(xué)思想的真正核心。函數(shù)關(guān)系

這一概念的重要意義遠遠超出了數(shù)學(xué)領(lǐng)域。

數(shù)學(xué)和自然科學(xué)的絕大部分都受著函數(shù)關(guān)系的支配。

§1函數(shù)的一般概念一映射

1.1函數(shù)概念的回顧

分析已知的函數(shù)概念，引出嚴格的定義的必要。對于函數(shù)，我們有如下的認識：

數(shù)學(xué)上的函數(shù)，只不過是變量之間相互依賴的一個規(guī)律。函數(shù)不意味著變量之間存在

任何“因果”關(guān)系。函數(shù)是數(shù)學(xué)家所關(guān)心的兩個變量間的聯(lián)系方式。

數(shù)學(xué)家和物埋學(xué)家對函數(shù)概念強調(diào)的地方不同。數(shù)學(xué)家強調(diào)的是對應(yīng)規(guī)律，即/()是

一個運算符號。值〃=/(?是把/()作用于x的結(jié)果。物理學(xué)家通常更感興趣的是量〃，而

不是(通過x能)計算出”的值的任何數(shù)學(xué)程序。除非這樣的公式對研究〃的性質(zhì)有好處。

當人們把數(shù)學(xué)用到物理和工程上的時候，通常就是采用這種態(tài)度的。在用函數(shù)學(xué)作更高的

計算時，有時只有搞清人們究竟指的是由x得到量〃=/5)的運算/()，還是量〃本身，

才可以避免混亂。因為量〃本身還可以被認為是用別的方式而依賴于其他變量z。

物理規(guī)律不是別的，只是這樣的一些命題，這些命題說明了一些量中有一些變動時，

其他一些量如何跟著變動,

對函數(shù)概念的通常定義的分析，我們發(fā)現(xiàn)其中的“規(guī)則”、“對應(yīng)”等概念未定義且有

些含糊，不令人滿意。19世紀的后半葉，數(shù)學(xué)家們把函數(shù)定義為笛卡兒乘積的子集，從而

把函數(shù)視為集合。于是，作為規(guī)則的函數(shù)定義已經(jīng)過去。這樣，把函數(shù)與它們的圖等同，

這是嚴格的。但大多數(shù)數(shù)學(xué)家更偏愛用規(guī)則定義函數(shù)，因為它直觀、生動。

1.2映射

定義1.1設(shè)X,V為集合，f^XxY.如果/滿足

1°VxwX,為eV使得(x,.y)w/,并且

2°若(x,y),(x,y')e/,那么)，=>',

則稱/是X到丫的一個映射，并記為了:X-Y。X稱為/的定義域。若則記

為)，=/"),或)，=(幻/。集合｛/")|xwX｝稱為/的值域。

定義1.2設(shè)廣X-y。如果%,％26X，陽工必，就有/(陽)=/。2)，則稱/為從X

到Y(jié)的里射。如果Vyw匕蟲wX使之/(.t)=j，則稱/是從X到Y(jié)的滿射或從X到y(tǒng)上的

映射。如果,既是單射又是滿射，則稱/是雙射或一一對應(yīng)。

定義1.3設(shè)/：x-y且g:zfw。我們說/與卷當且僅當XN,y=w,并且

Yxex^f(x)=g(x)。

定義1.4設(shè)f:XfX。如果Wxwx=x，則稱f為X到X的恒等映射,簡稱X上

的恒等映射，習(xí)慣用/x或〃或lx表示。

定義1.5設(shè)/:X->y,AqX,0：A->y。如果對"A的每個元素X有伊(x)=/(x),則稱

0為/在4上的限制，并常把。記為/|從，而/稱為。在X上的擴張。

定義1.6/:人—YH.X二八，則稱f為從X到Y(jié)的部分映射,我們假定從空集6到Y(jié)

有唯一的一個映射，它也是x到丫的部分映射。

1.3有限集間的映射

設(shè)-={12：〃},丫={。1，。2「,，金)，/：乂->丫。把/作如下解釋是有益的。

1°視x為物件之集，丫為盒子之集，/為把x中物件裝(放)入，”個命名的盒子里

的一種方法：若/(i)=4,則意即把物件，放到盒子4.旦。

2°視X中的1,2,…，〃為〃個位置，而y中元為小個不同字母：if/(，)=4，則意即把

4放在位置i上。于是，/?就是字母表丫上長為〃的一個字(序列、可重復(fù)排列)。

定理1.1設(shè)廠Xf八貝I」

1°if/是單射，則

2°if/是滿射，則心〃7

3°if/是雙射，則加=〃

4。if/〃=〃，則/是單射當且僅當/是滿射當且僅當/是雙射。

定理1.2設(shè)ix|=〃,|y|=〃?,則|yx|=|{/"：Xfy}|=〃?"。(回憶定義1.6,

n=(M,mn=m0=1)若〃4〃?，則從X到丫共有加(m-1)…(m-〃+1)個單射。若,〃=〃，則

〃】一1

從X到V共有4個雙射。*如果〃N"?,則從X到y(tǒng)的滿射的個數(shù)等于。

Jt=o

*習(xí)題1、連續(xù)擲一個骰子7次，試求1,2,3,456點都出現(xiàn)的概率。

解：由1,2,3,4,5,6組成的7—重集中，其中一個出現(xiàn)2次，其他每個各出現(xiàn)1次。

這樣的重集中元素的全排列共有7!/2!=Zx6!0由于重復(fù)的元可為I,2,???，6中的任一

2

個，故共有(，7x6!)x6=」6x7^x6!。因此，所求的概率為21x6!/67。(200l/07/23/pm8:40

22

看《還珠格格》)

本題還可用滿射個數(shù)的公式計算得到，稍繁些。

§2鴿巢原理

“天下的某一種事情，只要你對它有過深刻的觀察或研究，那么很可能在你遇到棘手

問題時就會用上它二

21鴿洞原理

在日常生活中，我們知道。將3個蘋果放在兩個抽屜中，則必有一個抽屜里放兩個。

在數(shù)學(xué)上，把一個具有很多元素的集劃分成不多的幾個子集，則必有一個子集含有相當數(shù)

量的元素。設(shè)/：Xf匕|乂|>|丫|,則存在”的兩個不同元素和電，使得/?)=/(工2)。

鴿洞原理的簡單形式〃+1個物體放入〃個盒子中，則必有一個盒子里至少裝兩個物

體。

因為否則，，2個盒子中至多裝了〃個物體，矛盾。

據(jù)說19I比紀德國數(shù)學(xué)家狄里赫萊（PerterGL.Dirichlet1805—1859）最早明確地用這

??原理證明數(shù)論中的?些命題。后人為紀念他也稱這?原理為狄里赫萊原理。人們也為這

一原理取了各種形象的名字：鴿洞（巢、舍）原理、抽屜原理、……。

鴿洞原理的強形式設(shè)％，…國〃為正整數(shù)，把+1個物體放入〃個盒中，則有

/=!

一個盒子，?里至少裝/個物體。

當/=%=-=%=2時，就得到簡單形式的鴿洞原理。

由鴿洞原理可演化出一系列其他結(jié)果或原理，有時也很有用。

平均值原理設(shè)叫,…，"?「為正整數(shù)且（￡，%）/，.>A-1,則〃小叫，…,”中必有

1-1

一個>k。

2.2應(yīng)用鴿洞原理的例題

例2.1取模運算（C中的%）是一種常用的方法。記明；任5個整數(shù)中必有3個整數(shù)，

其和是3的倍數(shù)。

［證］設(shè)這5個整數(shù)分別為占,12，%3，%4，％5。由于看=3%+小。工〃W2,/'=1,2,…,5,所以

可把余數(shù)為分的放到盒子4,A，&之一中，即々=左時，XjGAk,k=0,1,2o若有一個盒子

為空，則由鴿洞原理必有一盒中有3個整數(shù)，其和是3的倍數(shù)；否則每個盒子不空，從每

個盒子中各取一個數(shù)，其和是3的倍數(shù)。

例2.2平面上任意5個整點（坐標均為整數(shù)）中，必有兩個點，連接此二點的線段的

中點也必為整點。

［證］每個整點*,），）只能是以下四種之一：

（奇，奇），（奇.偶），（偶，奇），（偶，偶）。

這就得到4個盒子。5個整點按屬于何類裝入盒中，由鴿洞原理，必有一個盒中至少含兩

點，它們的對應(yīng)坐標的奇偶性相同，從而連接此二點的線段中點為整點。

2.3奇偶性原理

以下的事實就是奇偶性原理：

奇數(shù)W偶數(shù)，奇數(shù)+奇數(shù):偶數(shù)，奇數(shù)+偶數(shù):奇數(shù)，…

例2.3一個8x8的網(wǎng)格去掉了右上角和左下角的方格，問能否用31個1x2的骨牌蓋

住？

10101010

解：如圖所示將8x8網(wǎng)格的每個方格標上0或1,共

01010101

32個格標0,32個格標1。去掉了右上角和左下角兩

10101010

格后的