離散數(shù)學(xué)第一章

離散數(shù)學(xué)主講：韓蘭勝Hanlansheng@88學(xué)時兩個故事1成書于公元0年前后《孫子算經(jīng)》中有一題曰“今有物不知其數(shù)，三三數(shù)之余二，五五數(shù)之余三，七七數(shù)之余二，問物幾何？”“答曰：二十三”。述曰：“三三數(shù)之余二，置一百四十；五五數(shù)之余三，置六十三；七七數(shù)之余二，置三十；并之，得二百三十三，以二百一十減之既得；凡三三數(shù)之余一，則置七十；五五數(shù)之余一，則置二十一；七七數(shù)之余一，則置十五；一百零五減之，即得?！眱蓚€故事上述解為：設(shè)該數(shù)為x,則：

x=2（mod3）

x=3(mod5)x=2(mod7)求解一次同余方程得:x=70r1+21r2+15r3-105k,k為自然數(shù)。這就是著名的孫子定理課程說明一、離散數(shù)學(xué)課程的地位和作用離散數(shù)學(xué)是計算機(jī)專業(yè)的一門核心基礎(chǔ)課程。

1離散數(shù)學(xué)為計算機(jī)專業(yè)的后繼課程如數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、數(shù)據(jù)庫、編譯原理、網(wǎng)絡(luò)和算法設(shè)計等課程提供必要的數(shù)學(xué)基礎(chǔ)。

2為學(xué)生今后從事計算機(jī)科學(xué)和技術(shù)各方面的工作提供有力的工具。

3離散數(shù)學(xué)是現(xiàn)代數(shù)學(xué)的一個重要分支，通過該課程的學(xué)習(xí)可以提高學(xué)生的抽象思維、嚴(yán)格推理以及綜合歸納分析能力，培養(yǎng)出高素質(zhì)的人才。

二、離散數(shù)學(xué)課程的特點

離散數(shù)學(xué)課程是應(yīng)計算機(jī)科學(xué)和技術(shù)發(fā)展的需要，綜合了高等數(shù)學(xué)的多個分支而形成的。其特點是以離散量為研究對象，內(nèi)容豐富，涉及面較寬。因此概念多、定理多、推理多并且內(nèi)容較為抽象。但由于它是為學(xué)生后繼專業(yè)知識的學(xué)習(xí)做必要的數(shù)學(xué)準(zhǔn)備，因此它研究的內(nèi)容均比較基礎(chǔ)，難度不大。

三、如何學(xué)好離散數(shù)學(xué)要學(xué)好這門課程，首先必須充分認(rèn)識到這門課程的上述特點，需要做到以下幾點：1熟讀教材。準(zhǔn)確理解各個概念和定理的含義（結(jié)合多個例子來理解），必要的推理過程要看懂、理解（它可以幫助你熟悉和深刻理解定理的含義）。

2獨立思考，大量練習(xí)。僅靠熟讀教材并不能將書本上的知識

變成你自己的知識，在熟讀教材的基礎(chǔ)上，必須通過大量練

習(xí)，獨立思考來真正獲取知識。

3注重抽象思維能力的培養(yǎng)。數(shù)學(xué)與其他學(xué)科相比較具有

較高的抽象性，而離散數(shù)學(xué)的抽象性特點更為顯著，它有著大量抽象的概念和抽象的推理，要學(xué)好這門課程必須具有較好的

抽象思維能力，才能深入地掌握課程內(nèi)容。第四部分

數(shù)理邏輯。包括命題邏輯和謂詞邏輯。（教材的第九、十章

四、離散數(shù)學(xué)課程的主要內(nèi)容離散數(shù)學(xué)課程的主要內(nèi)容可以分為四個部分：第一部分集合論。包括集合、關(guān)系和函數(shù)。（教材的第一、二、三章）第二部分代數(shù)系統(tǒng)。包括代數(shù)系統(tǒng)的一般概念，幾類典型的代數(shù)系統(tǒng)。（教材的第四、五、六、七章）第三部分圖論。包括圖的基本概念，幾種特殊的圖。（教材的第八章）五、教材及參考書2參考書：《離散數(shù)學(xué)習(xí)題題解》

洪帆、付小青編，華中理工大學(xué)出版社。

1、教材：《離散數(shù)學(xué)基礎(chǔ)》第二版，洪帆主編，華中理工大學(xué)出版社。第一章集合

本章采用樸素集合論的方法，介紹有關(guān)集合的一些基本知識，內(nèi)容顯得較為直觀，學(xué)起來易于接受。但集合及其相關(guān)的概念是本門課程后面各章內(nèi)容的基礎(chǔ)，讀者務(wù)必熟練的掌握。

主要內(nèi)容如下：1.1集合及其表示方法1.2集合間的關(guān)系1.3集合的運(yùn)算和運(yùn)算定律1.4集合成員表1.5集合的分劃與覆蓋又例如

所有的正整數(shù)組成一個集合，每一個正整數(shù)均是這個集

合的元素。例如

全體中國人可組成一個集合，每一個中國人均是這個集合的

元素第一章集合

1.1集合及其表示方法一、集合和元素

把一些確定的、彼此不同的事物作為一個整體來

看待時，這個整體便稱為是一個集合。

組成集合的那些個體稱為集合的元素。

通常用大寫英文字母來標(biāo)記集合，用小寫英文字母標(biāo)記組成集合的個體若個體a是集合A的元素，則記作“a∈A”若a不是集合A的元素，則記作“aA”幾個常見的集合的表示符號：N：所有正整數(shù)的集合。Q：所有有理數(shù)的集合。Z：所有非負(fù)整數(shù)的集合。R：所有實數(shù)的集合。I：所有整數(shù)的集合。Nm：從1到m，這m個正整數(shù)的集合。P：所有素數(shù)的集合。Zm：從0到m-1，這m個非負(fù)整數(shù)的集合。

于是2∈N，2.5N，-3N，但2.5∈Q，-3∈I。

二、集合的表示方法(1)列舉法：按任意順序逐一列舉集合中的元素于花括號內(nèi)，元素之間用逗號隔開。例如：A={2,a,b,9},B={4,5,6,7,8}(2)描述法：給定一個條件P(x)，當(dāng)且僅當(dāng)個體a使P(a)成立時，a∈A。其一般形式為A={a∣P(a)}

例如上述集合B={a∣a∈N且4≤a≤8}

又如

C={2i∣i∈Z},即C={20,21,22,23,…}D={2x∣x∈Z且x≤50},即D={0,2,4,6,…,98,100}三、集合的基數(shù)集合A中不同元素的個數(shù)稱為集合A的基數(shù)，記作#A。例如上頁中的集合，#A=4，#B=5，#D=51，集合C有無窮多個元素，因此C的基數(shù)是無窮大。若#A是有限數(shù)，則稱A為有限集，否則稱A為無限集。例如

N,Z,I,R等均為無限集。

四、空集定義1-1

不含有任何元素的集合，稱為空集，記作φ。

例如

A={x|x∈R且

x2+8=0}=φ

練習(xí)1-1

用列舉法表示下列集合（1）A={a|a∈P且a<20}（2）B={a||a|<4且a為奇數(shù)}2.用描述法表示下列集合

(1)A={0,2,4,…,200}(2)B={2,4,8,…,1024}{2,3,5,7,11,13,17,19}{-3,-1,1,3}{2x|x∈Z且x≤100}{2n|n∈N且n≤10}

1.2集合間的關(guān)系集合的包含和相等是集合間的兩個基本關(guān)系。例如

設(shè)A={a,b,c,d},B={a,e,x,y,z},C={a,x}BA，AB。則，CA，一、集合的包含定義1-2

設(shè)有集合A、B，如果A的每一個元素都是B的元素，則稱A是B的子集或B是A的包含集，記。如果A不是B的子集，則記作AB。

集合的包含關(guān)系具有如下幾條性質(zhì)：證明性質(zhì)（1）

（反證法）假設(shè)，（1）對任意集合A，；

（2）對任意集合A，；（3）對任意集合A、B、C，若

，，則。

則至少有一個元素但，這與空集的定義相矛盾，因此成立。二、集合的相等例如

設(shè)A={x|x∈N且x能整除24}，

B={1,2,3,4,6,8,12,24}

則A=B=又例如

（1）{a,b,c}{b,c,a}（2）{a,b,c,c}{a,b,c}（3）{a,{b,c}}{{a,b},c}（4）

{}=≠≠定義1-3

設(shè)有集合A、B，若且

，則稱集合A與B相等，記作A=B。

例如

設(shè)A={0，1}，B={0，1，2}，C={0}則但四、空集的唯一性定理1-1

空集是唯一的

因為空集被包含于每一個集合中，三、集合的真包含定義1-4

設(shè)有集合A、B，若

,且A≠B，則稱A是B的真子集，記作，若A不是B的真子集，則記作。

證明

假設(shè)有兩個空集和，

所以有，，

由定義1-3，,故空集是唯一的。

五、冪集定義1-5

設(shè)有集合A，由A的所有子集組成的集合，稱為集合A的冪集，記作2A

即例1

設(shè)A={a}

則0個元素的子集：

1個元素的子集：{a}因此

設(shè)B={a,b}

則0個元素的子集：

1個元素的子集：{a},2個元素的子集：{a,b}因此

設(shè)C={a,b,c}

則0個元素的子集：；1個元素的子集：{a},,{c}2個元素的子集：{a,b},{a,c},{b,c}

3個元素的子集：{a,b,c}因此

定理1-2

設(shè)A是有限集，則#(2A)=2#A

在二項式定理

中，令

x=y=1,便有

因此

#(2A)=2n即#(2A)=2#A::{a1},:{a2},…{an}:{a1,a2},{a1,a3}…:{a1,a2,…,

an}…證明

設(shè)A={a1,a2,…,

an},從n個元素中選取m個元素的方法有種，所以A的子集個數(shù)為例2

設(shè),

求2A和2B

解

對于集合A，它只有一個子集，

即

對于集合B，有

1個元素的子集：，{a}，{{a}}

2個元素的子集：,,3個元素的子集：

0個元素的子集：

因此

答案：ABD2設(shè),試判斷下列各式是否正確，并將正確的題號填入括號內(nèi)。

A.B.C.D.答案：ABCA.B.C.D.

練習(xí)1-2

1試判斷下列各式是否正確，并將正確的題號填入括號內(nèi)。

3設(shè),

，判斷下列論斷是否正確，并將“Y”或“N”填入相應(yīng)論斷后面的括號中。

(1)(2)(3)(4)()()()()()()()()YYYYYYNN令則1.3集合的運(yùn)算和運(yùn)算定律二、文氏圖定義1-6

如果在某個問題中，所討論的一切集合均是某個集合的子集，則稱這個集合是該問題的全集合。記作U（或E）。

一、全集合例如

UAAB三、集合的運(yùn)算1.并運(yùn)算

定義1-7

設(shè)有集合A、B，屬于A或?qū)儆贐的所有元素組成的集合稱為A與B的并集，記作。即例如

設(shè)A={a,b,c},B={c,d,f},C={b,e}則

由定義1-7知，

AB2.交運(yùn)算

定義1-8

設(shè)有集合A、B，屬于A同時又屬于B的所有元素組成的集合稱為A與B的交集，記作。即例如

設(shè)A={a,b,c,d},B={d,f,a},C={e,f,g}則

由定義1-8可知，

AB3.相對補(bǔ)運(yùn)算定義1-9

設(shè)有集合A、B，所有屬于B而不屬于A的元素組成的集合，稱為A相對于B的補(bǔ)集，記作B-A。即例如

設(shè)A={a,b,c,d},B={d,f,a},C={e,f,g}則B-A={f},C-A={e,f,g}=CBA32頁2.絕對補(bǔ)運(yùn)算

定義1-10

集合A相對于全集合U的補(bǔ)集稱為A的絕對補(bǔ)集，簡稱為A的補(bǔ)集，記作。即例如

設(shè)U={1，2，3，4，…，10}，A={2，4，6，8，10}則又例如

設(shè)U=I（I是整數(shù)集），

則四、集合運(yùn)算的定律1.集合運(yùn)算的十條定律對于全集合U的任意子集A、B、C，有：

交換律結(jié)合律分配律同一律互補(bǔ)律對合律等冪律零一律吸收律德?摩根律1.集合恒等式的幾種證明方法（1）根據(jù)定義進(jìn)行證明若要證明集合S=H，根據(jù)集合相等關(guān)系的定義，我們需證明且例1

證明證明

若

,則，因此或者于是或者從而，則反之若，故或者。因此，或者,于是，從而，故有。由上證得，。

例2

證明證明

若則且，即且，因此，故。反之若，則且，即且，因此。故。由上證得，（2）利用已有的集合恒等式證明新的恒等式例如假設(shè)交換律、分配律、同一律和零一律都成立，則可以證明吸收律也成立。

證明（由同一律）

（由分配律）（由交換律）

（由零一律）

（由同一律）

又例如證明等冪律

證明==A(3)利用下一節(jié)介紹的集合成員表證明集合恒等式

D若，則A=B練習(xí)1-3

1設(shè)A、B、C是任意集合，判斷下述論斷是否正確，并將正確的題號填入括號內(nèi)。

A若，則B=CB若，則B=CC若A-B=A-C，則B=C()D反例設(shè)A={a,b,c},B={b,d},C={c,d}則但23頁2設(shè)U={1，2，3，4，5}，A={2，4}，B={4，3，5}，C={2，5，3}，確定下列集合的元素，將其填入相應(yīng)的花括號內(nèi)。

(1){}(2){}(3){}(4){}(5}21,42,3,4,543設(shè)U表示劉平擁有的所有書的集合，，其中A是離散數(shù)學(xué)參考書的集合，B是操作系統(tǒng)參考書的集合，C是今年出版的新書的集合，D是從圖書館借來的書的集合。現(xiàn)知道如下情形：（1）所有離散數(shù)學(xué)參考書都是今年出版的新書。（）（2）所有操作系統(tǒng)參考書都是從圖書館借來的。（）（3）今年出版的新書不是從圖書館借來的。（）（4）沒有一本操作系統(tǒng)的參考書是今年出版的。（

）

3157試用集合的方法分別表示上述四種情形，可供選擇的答案如下，請從下述答案中挑選出相應(yīng)表達(dá)式的編號填入每一種情形后面的括號中。2.3.4.5.6.7.4判斷下列論斷是否正確，對正確的論斷在相應(yīng)題后的括號中標(biāo)入“Y”，對錯誤的論斷在相應(yīng)題后的括號中標(biāo)入“N”。1）若，則（）2）若，則（）3）若，則（）4）若，則（）5）若，則()6）若，則()7）若，則()8）若，則()YYYYNNNN1.4集合成員表一、并、交和補(bǔ)集的成員表根據(jù)集合的并和交運(yùn)算的定義，全集合U中的元素u可分為如下四種情形：（1），（2），（3），（4），AB00

01

10

1100

10

10

11設(shè)A是全集合U的子集，根據(jù)補(bǔ)集的定義，全集合U中的元素可分為兩種情形，（1）若，則（2）若，則的成員表

A0110二、由集合A1、A2、…、Ar所產(chǎn)生的集合的成員表。設(shè)A1、A2、…、Ar是全集合U的子集，對這些集合以及Φ和U有限次地施加補(bǔ)、并、交運(yùn)算，可以產(chǎn)生出一些新的集合，這樣產(chǎn)生的集合稱為是由A1、A2、…、Ar所產(chǎn)生的集合。例如S例1

構(gòu)造T=的成員表

AB0001011011110100010例2構(gòu)造S的成員表

ABC00000101001100101110111S110011000100010010101010001000100110011000000110三、利用集合成員表證明集合恒等式例３

設(shè)A、B、C是任意集合，試問等式S=T是否成立？

解

令S=T=分別構(gòu)造S和T的成員表如下：

ABC000

001

010

011

100

101

110

111ST1

1

1

1

00

0

00

0

1

1

1

1

1

11

1

1

1

0

1

0

10

0

1

1

0

1

0

10

0

1

1

0

0

0

00

0

0

0

0

1

0

10

0

1

1

0

1

0

11.5集合的分劃與覆蓋一、集合的分劃定義1-11

設(shè)有非空集合A，H={A1、A2、…、Am}，其中，且（i=1，2，…，m），若

（1），當(dāng)i≠j時

(2)例1

設(shè)A={1，2，3，4}

則H1={{1}，{2}，{3，4}}H2={{2，3}，{1，4}}H3={{1}，{2}，{3}，{4}}。

都是A的分劃則稱H是集合A的一個分劃，每一個稱為這個分劃的一個分塊。例2設(shè)A={2，3，4，8，9，10，15}

定義A的如下子集：

試問是否A的一個分劃。

解

根據(jù)題意{2，4，8，10}

{3，9，15}{10，15}

不是A的分劃，

可成為A的一個分劃。

二、集合的覆蓋定義1-12

設(shè)有非空集合A，,其中

且（i=1，2，…，m），若，

則稱S是集合A的一個覆蓋。

例如

例2中是A的分劃，也是A的覆蓋。是A的覆蓋，但不是A的分劃。練習(xí)1-5

1設(shè)A={a，b，c，d，e，f}，指出下列哪些是A的分劃（在相應(yīng)括號內(nèi)填入“1”），哪些是A的覆蓋（在相應(yīng)括號內(nèi)填入“2”），哪些既不是分劃，也不是覆蓋（在相應(yīng)括號內(nèi)填入“0