離散數(shù)學第1章課件

目錄序言第一章集合第二章關(guān)系第三章函數(shù)第四章代數(shù)系統(tǒng)第五章格與布爾系統(tǒng)第六章圖論1離散的數(shù)學結(jié)構(gòu)

DiscreteMathematicStructures離散數(shù)學簡介。內(nèi)容：集合論、代數(shù)系統(tǒng)、布爾代數(shù)、圖論、數(shù)理邏輯。離散數(shù)學具有抽象性、非線性、非尋繹性、構(gòu)造性、結(jié)構(gòu)性、整體性等結(jié)構(gòu)性數(shù)學特點。方法和手段證明方法：包括（數(shù)學）歸納法、演繹法、反證法、歸謬法、二難法、二分法、枚舉法（窮舉法）、相容排斥法等方法，特別著重于存在性、結(jié)構(gòu)性、構(gòu)造性方法，以及各部分內(nèi)容自己所特有的方法。2

第一章集合(set)

§１.集合理論中的一些基本概念

個體與集合之間的關(guān)系

集合的表示法

集合與集合之間的關(guān)系

冪集

§2.集合代數(shù)集合的基本運算

集合的補運算

集合的交運算和并運算

集合的宏運算3

第一章集合(set)§１.集合理論中的一些基本概念1.凡具有某種特殊性質(zhì)的對象的匯集稱之為集。——莫斯科大學的那湯松教授2.凡可供吾人思維的，不論它有形或無形，都叫做物。具有某種條件的物，稱它們的全部謂之一集。——復旦大學的陳建功教授3.集就是“烏合之眾”。不考慮怎樣“烏合”起來的，眾可以具體，可以抽象?！祥_大學的楊宗磐教授任意性：組成集合的元素任意；構(gòu)成的法則任意；什么都可以構(gòu)成集合，不加任何限制。4

4.集合是由總括某些個體成一個整體而成的。對于每個個體，只設其為可思考的對象，辨別它的異同。個體之間并不需要有任何關(guān)系?！险撝窯.Cantor（1845-1918）事實：(a)承認集合的存在性。即，接受集合概念；(b)承認集合是由一些個體（對象）組成的。這些個體稱為該集合的成員或元素（member,element）；(c)承認個體是可辯認的。即，一個個體要么是一個集合的成員，要么不是；二者必居其一，也只居其一。確定性：確定性是說集合確定；個體確定；集合與個體之間的關(guān)系確定。5

(1)a屬于（belongto）A，記為aA（記號是希臘字i的第一個字母，意思是“是”。由意大利數(shù)學家G.Peano首先采用），同時稱a是A的元素或A的成員。(2)a不屬于A，記為aA或aA，稱a不是A的元素或a不是A的成員。

判斷個體a屬于A還是不屬于A，必須使用個體的可辨認性。AaAaAaAa7

二.集合的表示法（用花括號{}表示集合）：(1)文字表示法：用文字表示集合的元素，兩端加上花括號。

比較粗放。比較適合在對集合中的元素了解甚少、不詳，難以用精確的數(shù)學語言來刻劃時使用。(2)元素列舉法（羅列法）：將集合中的元素逐一列出，兩端加上花括號。比較適合集合中的元素有限（較少或有規(guī)律），無限（離散而有規(guī)律）的情況。(3)謂詞表示法：{x:P(x)}或者{x︱P(x)}其中：P表示x所滿足的性質(zhì)（一元謂詞）。比較適合在對集合中的元素性質(zhì)了解甚詳，且易于用精確的數(shù)學語言來刻劃時使用。8

外延(extension)：集合{x:P(x)}稱為性質(zhì)謂詞P(x)的外延；內(nèi)涵(intension,connotation)：性質(zhì)謂詞P(x)稱為集合{x:P(x)}的內(nèi)涵；采用謂詞法定義集合，關(guān)鍵是要得出內(nèi)涵P(x)，并且顯然有如下的：概括原理：集合{x:P(x)}恰由那些滿足性質(zhì)謂詞P(x)的元素組成。即

x{x:P(x)}（當且僅當）

P(x)真。9

悖論(paradox)：所謂悖論是指這樣一個所謂的命題P，由P真立即推出P假；由P假立即推出P真；即P真P假。理發(fā)師悖論：某偏遠小山村僅有一位理發(fā)師。這位理發(fā)師規(guī)定：他只給那些不給自己刮臉的人刮臉。那么要問：這位理發(fā)師的臉由誰來刮？如果他給自己刮臉，那么，按他的規(guī)定，他不應該給自己刮臉；如果他不給自己刮臉，那么，按他的規(guī)定，他應該給自己刮臉；

10

羅素悖論(Russellparadox(1902))：羅素1902年在集合論中也發(fā)現(xiàn)了如下的悖論。他構(gòu)造了這樣一個集合S={x:xx}然后他提出問題：SS？如果SS，那么，按羅素給S的定義，則應有SS；如果SS，那么，按羅素給S的定義，則應有SS；羅素悖論的發(fā)現(xiàn)，幾乎毀滅集合論，動搖數(shù)學的基礎，傾危數(shù)學的大廈。直接引發(fā)了數(shù)學的第三次危機。

11

為了解決集合論中的悖論問題，人們產(chǎn)生了類型論和形式化公理化集合論(ZF和ZFC公理系統(tǒng))，以求排除集合論中的悖論。近年來，基于ZFC公理系統(tǒng)和一階邏輯(謂詞邏輯)，人們提出了抽象的計算機程序設計語言__Z語言。在公理化集合論中，人們引進了類(class)的概念。本章所講解的集合論是‘樸素（naive）’集合論；所討論的集合一般也不會產(chǎn)生悖論。12

三.集合的名字：(1)大寫的拉丁字母：例如A、B；(2)小寫的希臘字母：例如、；(3)花寫的徳文字母：例如,；不夠用時可以加下標。

同一個集合可以有幾個名字。四.集合的相等（equality）：

外延性原理：

兩個集合相等，當且僅當，它們的成員完全相同。即A=Bx(xAxB)；兩個集合不相等，記為AB。13

無序性：集合中的元素是無序的。

因此，為了使用方便，可任意書寫集合中元素的順序。但一般情況下，通常采用字母序、字典序；有時，還需要強行命名一種序。

(2)無重復性：集合中元素的重復是無意義的。

包（bag）：若允許元素重復稱為包。集合的性質(zhì)：任意性、確定性、無序性、無重復性。14

五.空集（empty,null,voidset）：記為空集是沒有成員的集合。即

x(x）（空集公理）；所以={}；空集是集合（作這點規(guī)定是運算封閉性的要求）?？占俏ㄒ坏摹Ｒ驗槿粲袃蓚€空集，則它們有完全相同的元素（都沒有任何元素），所以它們相等，是同一集合。六.全集（universeofdiscourse）：記為X全集是所要研究的問題所需的全部對象（元素）所構(gòu)成的集合。全集給個體（研究的對象）劃定適當?shù)姆秶?5

七.單元素集合（singletonset）：

只含一個元素的集合稱為單元素集。例如{a}；{張三}；{}左邊是空集；右邊不是空集，而是單元素集合，有一個成員；這說明：差別在于級別。即，右邊的集合級別高。單元素集合是構(gòu)造復雜集合的‘原子’。16

八.子集（subset）：對于兩個集合A，B，若A中的每個元素x都是B的一個元素，則稱A包含在B中（或者B包含A），記為AB。同時稱A是B的子集（稱B是A的超集(superset)）。即

ABx(xAxB)。真子集（propersubset）：稱A是B的真子集或者A真包含在B中（或者B真包含A），記為AB。即AB

ABAB。

ABX17

子集的兩種特殊情況（平凡子集）：(1)空集（見下面定理2）；(2)每個集合自己（見下面定理1的(1)）；九.集合與集合之間的關(guān)系:集合與集合之間的關(guān)系：(1)B包含A，ABx(xAxB)；(2)A包含B，BAx(xBxA)；(3)A等于B，A=Bx(xBxA)

ABBA；(4)A與B互不包含，(AB)(BA)x(xAxB)y(yByA)；

18

定理1.設A,B,C為任意三個集合。那么(1)自反性：AA(每個集合是它自己的子集)；(2)反對稱性：ABBA

A=B；(3)傳遞性：ABBC

AC；[證明].（采用邏輯法）(1)x(xAxA)(同一律：pp)

AA所以包含關(guān)系是自反的；(2)ABBA

x(xAxB)x(xBxA)x((xAxB)(xBxA))(量詞對的分配律：xA(x)xB(x)x(A(x)B(x)))x(xAxB)A=B

所以包含關(guān)系是反對稱的；19

(3)ABBC

x(xAxB)x(xBxC)x((xAxB)(xBxC))(量詞對的分配律：xA(x)xB(x)x(A(x)B(x)))x(xAxC)((假言)三段論原則：(pq)(qr)pr)AC

所以包含關(guān)系是傳遞的。20

定理2.空集是任一集合的子集。即A。[證明].(采用邏輯法)x(x）(空集的定義)x(x)x(xxA)(由析取構(gòu)成式及聯(lián)結(jié)詞歸約有：p(pq)(pq))A。

21

十.冪集(powerset)：定義1.冪集一個集合A的所有子集構(gòu)成的集合稱為A的冪集。記為2A(或P(A))

，即2A={B：BA}。

A的兩個平凡子集和A都屬于A的冪集。即

2A，A2A。例1.若A={1,2,3}，則2A={,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}。注：(1)包含關(guān)系兩邊必須是集合，并且這兩個集合的級別（廣義上）相同；(2)屬于關(guān)系左邊是元素（廣義上），右邊是集合，兩邊級別差一級。22

定義2.基數(shù)

一個有窮集合（有限集合——元素個數(shù)有限的集合）A中元素的個數(shù)稱為A的基數(shù)。記為|A|(或A，)?；鶖?shù)的性質(zhì)：(1)齊性：||=0；(2)非負性：|A|0（對任何集合A）；

定理3.若A是有限集合，則有|2A|=2|A|。

[證明].由于集合A有限，故可設A={a1，a2，…，an}，于是|A|=n。A的子集按其基數(shù)大小可分為0，1，2，…，n共n+1類。23

A的所有k個元素的子集（基數(shù)為k的類）為從n個元素中取k個元素的組合數(shù)。另外，因A，故（按加法原理）

2A=1+++…++…+=但由于二項式定理(x+y)n=xkyn-k

令x=y=1，則有2n=，

從而，有|2A

|=2n=2|A|

。24

定理4.若A，B是兩個集合，那么，A=B2A=2B。[證明].)：一方面，

AA(自反性)A2A

(因為2A={B:BA})

A2B(充分性條件：2A

=2B)

AB(因為2B

={A:AB})另一方面，BB(自反性)B2B

(因為2B

={A:AB})

B2A(充分性條件：2A=2B)

BA(因為2A

={B:BA})因此，由包含關(guān)系的反對稱性，得到

A=B。25

§2

.集合代數(shù)集合的基本運算定義1.余(補或非)運算((absolute)complment)設X是全集，一元運算

:2X2X

對任何集合AX，使得A={x

:

xXxA}(當全集明確時，A

={x

:

xA})稱為集合的余運算。稱A是A關(guān)于X的余集。余運算有時也記為，或A或A。

XAA26

定理1(1.3).余運算基本定理

設X是全集，A，B是X的子集。則(1)(A)=A；反身律(對合律)(2)ABB

A；換質(zhì)位律（逆否律）(3)A=

BA=

B；(4)X=，=X。零壹律[證明].(采用邏輯法)(1)對任何元素xX，x(A)

xA

xA所以(A)=A；27

(4)對任何元素x，xXxXx所以X=；對任何元素x，xxxX(已證：X=)xX所以=X。28

定義1.2.交運算、并運算(intersection,union)設X是全集。(1)二元運算∩

:2X2X2X

對任何集合A,BX，使得A∩B={x:

xAxB}稱為集合的交運算。稱A∩B為A與B的交集?！捎⒄Z讀作cap（帽子）。若A∩B=,則稱A與B互不相交(pairwise)disjoint)。(2)二元運算∪:2X2X2X

對任何集合A,BX，使得A∪B={x:

xAxB}稱為集合的并運算。稱A∪B為A與B的并集。

∪英語讀作cup（酒杯）。

29

定理2.交、并、余運算的基本定理

設X是全集，A，B，C是X的三個子集。則

(1)A∩A=A，A∪A=A；冪等律(2)A∩A=，A∪A=X；互補律(2’)A∩X=A，A∪X=X；零壹律

(2”)A∩=，A∪=A；零壹律

(3)

AA∪B，B

A∪B；上界

A∩BA，A∩BB

；下界

(3’)

ACBCA∪BC；上確界

(3”)CACBCA∩B；下確界(4)A∩(A∪B)=A，A∪(A∩B)=A；吸收律(5)A∩B=B∩A，A∪B=B∪A；交換律(6)(A∩B)∩C=A∩(B∩C)，結(jié)合律(A∪B)∪C=A∪(B∪C)；(7)A∩(B∪C)=(A∩B)∪(A∩C)，分配律

A∪(B∩C)=(A∪B)∩(A∪C)。

30

[證明].(3’)(采用邏輯法)對任何元素xX

，

xA∪B

xAxBxCxC

(已知條件：AC，BC)

xC(冪等律：ppp)所以，A∪BC。

31

(7)先證：A∩(B∪C)(A∩B)∪(A∩C)(采用元素法)對任何元素xX

，若xA∩(B∪C)，則xA，且xB∪C。于是x

A，且xB或者xC。若xB，則xA且xB，于是xA∩B；

若xC，則xA且xC，于是xA∩C；綜合xA∩B或者xA∩C，因此x(A∩B)∪(A∩C)；所以，A∩(B∪C)(A∩B)∪(A∩C)。次證：(A∩B)∪(A∩C)A∩(B∪C)(采用包含法)由(3)有A∩BA，A∩BBB∪C（逐步放大法）。于是根據(jù)(3”)可得A∩BA∩(B∪C)同理可得A∩CA∩(B∪C)于是根據(jù)(3’)可得(A∩B)∪(A∩C)A∩(B∪C)。最后，根據(jù)包含關(guān)系的反對稱性，就得到A∩(B∪C)=(A∩B)∪(A∩C)。

32

定理3.deMorgan律（對偶律）

設A，B為兩個集合。則(1)(A∪B)=A∩B，(2)(A∩B)=A∪B。[證明].只證(1)先證：(A∪B)A∩B(采用包含法)由定理2(3)有AA∪B，BA∪B于是由定理1(2)可得(A∪B)A，(A∪B)B再用定理2(3”)，就有(A∪B)A∩B；

次證：A∩B(A∪B)(采用邏輯法)

33

對任何元素xX

，xA∩BxAxB

xAxB

xA∪B(否則xA∪BxAxB，這與xAxB矛盾)

x(A∪B)所以A∩B(A∪B)

根據(jù)包含關(guān)系的反對稱性，就得到(A∪B)=A∩B。定理4

設A，B為兩個集合。則下面三式等價。(1)A

B；(2)A∪B=B；(3)A∩B=A。34

[證明].(采用循環(huán)論證法)(1)(2)：(采用包含法)根據(jù)定理2(3)，得到BA∪B；由已知條件AB，及自反性BB，根據(jù)定理2(3’)，得到A∪BB；最后，根據(jù)包含關(guān)系的反對稱性，

就得到A∪B=B。(2)(3)：(采用變換法(公式法))A∩B=A∩(A∪B)(根據(jù)(2)條件A∪B=B)=A(根據(jù)定理2(4)吸收律)即A∩B=A。(3)(1)：(采用：包含法)A=A∩B(根據(jù)(3)條件A∩B=A)

B(根據(jù)定理2(3)A∩BB)即AB。35

定義3

.差運算(difference)設X是全集。二元運算\:2X2X2X

對任何集合A,BX，使得A\B={x

:

xAxB}稱為集合的差運算。稱A\B為A和B的差集。

差集也稱為相對補(relativecomplement)。而余運算可看成絕對補。即A=

X\A。由差運算、交運算、余運算的定義知A\B=A∩B，稱差運算為宏運算。注：請問：交、并、余三個運算是線性無關(guān)的嗎？根據(jù)反身律、deMorgan律，有

A∩B=(A∪B)；A∪B=(A∩B)。36

定理5.差運算基本定理設X是全集，A，B，C是X的三個子集。則(1)A\BA；(2)ABA\B=；(3)A\A=；(4)X\A=A；A\X=；(5)A\=A；\A=；(6)A∩(B\C)=(A∩B)\(A∩C)；交對差的分配律(7)A\(B\C)=(A\B)∪(A∩C)；

(8)A\(B∪C)=(A\B)∩(A\C)；相對補的deMorgan律(9)A\(B∩C)=(A\B)∪(A\C)。相對補的deMorgan律37

[證明].(采用包含法和變換法(公式法))(1)A\B=A∩B

A(根據(jù)定理2(3)A∩BA)；(2)A\B=A∩B=(A∩B)∩B(由已知AB根據(jù)定理4(3)有A∩B=A)=A∩(B∩B)(結(jié)合律)=A∩(互補律B∩B=)=(零壹律)；(7)A\(B\C)=A\(B∩C)=A∩(B∩C)=A∩(B∪C)(deMorgan律,反身律)=(A∩B)∪(A∩C)(分配律)=(A\B)∪(A∩C)；

38

(6)A∩(B\C)=A∩(B∩C)=∪(A∩B∩C)(零壹律,結(jié)合律)=(B∩)∪(A∩B∩C)(零壹律)

=(B∩A∩A)∪(A∩B∩C)(互補律,結(jié)合律)=(A∩B∩A)∪(A∩B∩C)(交換律)=(A∩B)∩(A∪C)(分配律)=(A∩B)∩(A∩C)(deMorgan律)=(A∩B)\(A∩C)；

39

(8)A\(B∪C)=A∩(B∪C)=A∩(B∩C)(deMorgan律)=(A∩A)∩(B∩C)(冪等律)=(A∩B)∩(Ａ∩C)(結(jié)合律，交換律)=(A\B)∩(A\C)；(9)A\(B∩C)=A∩(B∩C)=A∩(B∪C)(deMorgan律)=(A∩B)∪(Ａ∩C)(分配律)=(A\B)∪(A\C)。40

定義4.對稱差（環(huán)和）運算(symmetricdifference)設X是全集，二元運算

:2X2X2X，

對任何集合A,BX，使得AB={x:(xAxB)(xBxA)}稱為集合的對稱差運算，稱AB為A和B的對稱差集。由環(huán)和運算和并、差運算的定義可知AB=(A\B)∪(B\A)由環(huán)和運算和交、并、余運算的定義可知

AB=(A∩B)∪(B∩A)因此環(huán)和運算也是宏運算。41

定理6.環(huán)和運算基本定理設X是全集，A，B，C是X的三個子集。則(1)AB=(A∪B)\(A∩B)=(A∪B)∩(A∪B)；

(2)A=A；（空集是環(huán)和的幺元）AX=A；(3)AA=；（自己是自己（環(huán)和）的逆元）

AA=X；(4)AB=AB；(5)(AB)=AB=AB；(6)AB=BA；（交換律）(7)A(BC)=(AB)C；（結(jié)合律）(8A∩(BC)=(A∩B)(A∩C)；(交對環(huán)和的分配律）(9)AB=ACB=C。（消去律）42

[證明].(采用變換法(公式法))只證(5)，(7)，(9)(5)(AB)=((A∩B)∪(A∩B))

=(A∩B)∩(A∩B)(deMorgan律)=(A∪B)∩(A∪B)(deMorgan律，反身律)=((A∪B)∩A)∪((A∪B)∩B)(分配律)=(A∩A)∪(B∩A)∪(A∩B)∪(B∩B)(分配律，結(jié)合律)=(A∩A)∪(A∩B)∪(A∩B)∪(B∩B)(交換律)=∪(A∩B)∪(A∩B)∪(互補律)=(A∩B)∪(A∩B)(零壹律)AB=(A∩B)∪(A∩B)=(A∩B)∪(A∩B)(反身律)=(A∩B)∪(A∩B)(交換律)AB=(A∩B)∪(A∩B)=(A∩B)∪(A∩B)(反身律)所以(AB)=AB=AB=(A∩B)∪(A∩B)；43

(7)A(BC)=(A∩(BC))∪(A∩(BC))=(A∩((B∩C)∪(B∩C)))∪(A∩((B∩C)∪(B∩C)))(根據(jù)本定理的(5))=(A∩B∩C)∪(A∩B∩C)∪(A∩B∩C)∪(A∩B∩C)(分配律，結(jié)合律)(AB)C=((AB)∩C)∪((AB)∩C)=(((A∩B)∪(A∩B))∩C)∪(((A∩B)∪(A∩B))∩C)(根據(jù)本定理的(5))=(A∩B∩C)∪(A∩B∩C)∪(A∩B∩C)∪(A∩B∩C)(分配律，結(jié)合律)=(A∩B∩C)∪(A∩B∩C)∪(A∩B∩C)∪(A∩B∩C)(交換律，結(jié)合律)所以A(BC)=(AB)C；

44

(9)B=B(根據(jù)本定理的(2))=(AA)B(根據(jù)本定理的(3))=A(AB)(根據(jù)本定理的(7)結(jié)合律)=A(AC)(已知條件AB=AC)=(AA)B(根據(jù)本定理的(7)結(jié)合律)=C(根據(jù)本定理的(3))=C(根據(jù)本定理的(2))。45

定義5

.環(huán)積運算設X是全集，二元運算

:2X2X2X

對任何集合A,BX，使得AB={x:(xAxB)(xBxA)}稱為集合的環(huán)積運算。稱AB為A和B的環(huán)積集。由環(huán)積運算和交、并、余運算的定義可知

AB=(A∪B)∩(B∪A)因此環(huán)積運算也是宏運算。46

定理7.環(huán)積運算基本定理

設X是全集，A，B，C是X的三個子集。則(1)AB=(A∩B)∪(A∩B)=(A∩B)∪(A∪B)；

(2)AB=

(AB)=AB=AB；(3)A=A；AX=A（全集是環(huán)積的幺元）；(4)AA=X（自己是自己（環(huán)積）的逆元）；

AA=；(5)AB=AB；(6)(AB)=AB=AB；(7)交換律：AB=BA；

(8)結(jié)合律：A(BC)=(AB)C；(9)分配律：A∪(BC)=(A∪B)(A∪C)(并對的)；(10)消去律：AB=ACB=C。47

[證明].(采用變換法(公式法))只證(9)(9)A∪(BC)=A∪((A∪B)∩(A∪B))=(A∪B∪C)∩(A∪B∪C)(分配律，結(jié)合律)=X∩(A∪B∪C)∩X∩(A∪B∪C)(零壹律)=(A∪B∪Ａ)∩(A∪B∪C)∩(A∪C∪Ａ)∩(A∪B∪C)(互補律，零壹律，交換律，結(jié)合律)=((A∪B)∪((Ａ∩C))∩((A∩B)