大學(xué)教學(xué)課件：離散數(shù)學(xué)導(dǎo)論（第四版）

1離散數(shù)學(xué)導(dǎo)論（第四版）

電子教案

2第一篇緒言

本篇是對離散數(shù)學(xué)的宏觀介紹。

1．計(jì)算機(jī)學(xué)科與離散數(shù)學(xué)介紹離散數(shù)學(xué)在計(jì)算機(jī)學(xué)科發(fā)展中的作用與關(guān)系，明確離散數(shù)學(xué)是掌握與研究計(jì)算機(jī)學(xué)科的基礎(chǔ)理論與工具。

2．離散數(shù)學(xué)的特征

離散性

可構(gòu)造性

抽象性

3．離散數(shù)學(xué)的內(nèi)容離散數(shù)學(xué)的主要內(nèi)容為：

集合論

代數(shù)結(jié)構(gòu)

圖論

數(shù)理邏輯3第二篇集合論

本篇由集合論初步、關(guān)系、函數(shù)、有限集與無限集等與集合論相關(guān)等四部分內(nèi)容組成，它們間是一個(gè)內(nèi)容關(guān)聯(lián)的整體。4第一章集合論初步

集合論是數(shù)學(xué)的基礎(chǔ)，也是離散數(shù)學(xué)的基礎(chǔ)。故學(xué)好集合論十分重要，在本章學(xué)習(xí)中要掌握：

集合中的一個(gè)基本概念

集合中的兩種關(guān)系

集合中的三種特殊集合

集合中的三種表示方法

集合中的五種運(yùn)算

集合中的21個(gè)常用公式5

§1.1集合論基本概念

（1）

一個(gè)主要的概念——集合的基本概念：一些不同確定的對象全體稱集合，而這些對象稱集合的元素。（2）集合中的兩個(gè)關(guān)系

集合間的比較關(guān)系：A＝B，A≠B，AB，AB。

集合與元素間的隸屬關(guān)系：aA，aA。（3）三種特殊的集合

空集

全集E

冪集（A）。6

（4）集合的三種表示法：

枚舉法。即將集合元素一一列舉。例：{1,2,3,…}

特性刻劃法。即用元素的性質(zhì)刻劃集合。例：{x|p(x)}

圖示法。即用文氏圖表示集合及集合間的關(guān)系。例：

AAB7§

2.2集合代數(shù)（5）集合的五種運(yùn)算：

交運(yùn)算：A∩B

倂運(yùn)算：A∪B

差運(yùn)算：A－B

補(bǔ)運(yùn)算：～A

對稱差運(yùn)算：A＋B8（6）集合的21個(gè)公式：交換律：A∪B＝B∪AA∩B＝B∩A結(jié)合律：A∪（B∪C）＝（A∪B）∪CA∩（B∩C）＝（A∩B）∩C分配律：A∪（B∩C）＝（A∪B）∩（A∩C）A∩（B∪C）＝（A∩B）∪（A∩C）9同一律：A∪＝AA∩E＝A零一律：A∪E＝EA∩＝互補(bǔ)律：A∪～A＝EA∩～A＝雙補(bǔ)律：～（～A）＝A10E與

的互補(bǔ)：～E＝～＝E等冪律：A∪A＝AA∩A＝A吸收律：A∪（A∩B）＝AA∩（A∪B）＝A狄·莫根定律：～（A∪B）＝～A∩～B～（A∩B）＝～A∪～B11

§1.3冪集

冪集定義：集合A的所有子集所組成的集合，可記為（A）。

冪集性質(zhì)：|A|＝n則|(A)|＝2n

12第二章關(guān)系關(guān)系研究集合內(nèi)元素間的關(guān)聯(lián)及集合間元素關(guān)聯(lián)，主要有：

一種預(yù)備知識

一個(gè)基本概念

兩種表示方法

三種運(yùn)算

九個(gè)公式

五種性質(zhì)

六種常用關(guān)系13§2.1關(guān)系的預(yù)備知識－n元有序組與笛卡爾乘積

n元有序組是一種特殊的集合結(jié)構(gòu)形式，它有兩個(gè)基本概念與一種基本運(yùn)算（笛卡爾乘積）。

基本概念之一：有序偶。例：（a,b）

基本概念之二：n元有序組。例：（a1,a2,…an

）

基本運(yùn)算：笛卡爾乘積。例：AB14§2.2

關(guān)系基本概念

（1）一個(gè)主要的概念——二元關(guān)系的基本概念：

關(guān)系定義：從集合A到B的關(guān)系R是A×B的一個(gè)子集。（2）兩種表示方法：

集合表示法：有序偶的集合

圖表示法：有向圖15§2.2關(guān)系運(yùn)算（3）兩種運(yùn)算：

關(guān)系的復(fù)合運(yùn)算

關(guān)系的逆運(yùn)算（4）有關(guān)運(yùn)算的五個(gè)公式：復(fù)合運(yùn)算的公式：

(RS)T＝R(S

T)

Rm

Rn＝Rm+n(Rm)n＝Rmn

逆運(yùn)算的公式：

R＝R(R

S)＝R

S

～～～16§2.4

關(guān)系重要性質(zhì)（5）關(guān)系的五種性質(zhì)

關(guān)系的自反性

關(guān)系的反自反性

關(guān)系的對稱性

關(guān)系的反對稱性

關(guān)系的傳遞性17（6）六種常用關(guān)系

次序關(guān)系之一：偏序關(guān)系

次序關(guān)系之二：擬序關(guān)系

次序關(guān)系之三：線性次序關(guān)系

次序關(guān)系之四：字典次序關(guān)系

相容關(guān)系

等價(jià)關(guān)系18§2.5

閉包運(yùn)算（1）關(guān)系的閉包運(yùn)算

自反閉包r(R)對稱閉包s(R）

傳遞閉包t(R）（2）閉包的公式：

r（R）＝R∪s（R）＝R∪Rt（R）＝∪Ri

～i=119§2.6

次序關(guān)系

（7）次序關(guān)系

四個(gè)定義：偏序關(guān)系：X上自反、反對稱與傳遞的關(guān)系稱偏序關(guān)系并用‘≤’表示。

擬序關(guān)系：反自反、傳遞的關(guān)系稱擬序關(guān)系并用‘<’表示。線性次序關(guān)系：X上偏序關(guān)系R如有x,yx必有x≤y或y

≤x則稱R是X上線性次序關(guān)系。字典次序關(guān)系：有限字母表∑

上的偏序關(guān)系。如建立∑＊上的次序關(guān)系：設(shè)x=x1,x2,…xn

,y=y1,y2,…ym

；x,y*；x1,x2,…xn

,y1,y2,…,ym.20（1）x1≠y1且如x1≤y1則我們說xLy；如y1≤x1，則我們說yLx；（2）如存在一個(gè)最大的K且K＜min(n，m)，使得x1＝y(tǒng)1，x2＝y(tǒng)2，…，xk＝y(tǒng)k而xk＋1＝y(tǒng)k+1，如果xk＋1≤yk＋1，則我們說xLy；如yk＋1≤xk＋1，則我們說yLx；（3）如存在一個(gè)最大的K＝min(n，m)，使得x1＝y(tǒng)1，x2＝y(tǒng)2，…，xn＝y(tǒng)n

，此時(shí)如n≤m，則我們說xLy；如m≤n，則我們說yLx。

21四個(gè)次序關(guān)系間的關(guān)系：

R是擬序則r(R)=RR是偏序則R－Q是擬序

字典次序關(guān)系必為線性次序關(guān)系

R是擬序則必反對稱八個(gè)概念：

最大元素（最小元素）

極大元素（極小元素）

上界（下界）

上確界（下確界）22§2.7相容關(guān)系

（8）相容關(guān)系

相容關(guān)系定義——X上自反、對稱關(guān)系稱相容關(guān)系并用“≈”表示。

相容關(guān)系的極大相容塊——設(shè)有集合X上的相容關(guān)系≈，設(shè)A是X的子集，如A中任何元素都互為相容，且X—A中的任何元素沒有一個(gè)與A中的所有元素相容，則稱A是X中的極大相容性分塊。

相容關(guān)系完全覆蓋——X上相容關(guān)系≈，它的極大相容性分塊的集合稱X的完全覆蓋。

23§2.8等價(jià)關(guān)系

（9）等價(jià)關(guān)系

等價(jià)關(guān)系定義——X上自反、對稱、傳遞的關(guān)系稱等價(jià)關(guān)系。

等價(jià)類——R是X上等價(jià)關(guān)系，對xX可構(gòu)造一個(gè)X的子集[x]R

稱為x對R的等價(jià)類。

劃分——S的子集A1，A2，…An滿足：①Ai均分離(i=1，2，…，n)②A1∪A2∪…∪An＝S則A＝｛A1，A2，…，An｝為S的劃分，而Ai稱為劃分的塊（i=1,2,…n）。

商集——X上等價(jià)關(guān)系R所構(gòu)成的類產(chǎn)生X的劃分叫X關(guān)于R的商集記以X／R。24第三章函數(shù)

函數(shù)是一種特殊的關(guān)系，它在數(shù)學(xué)中具有普遍重要價(jià)值，函數(shù)主要內(nèi)容有：

一個(gè)基本概念

兩種基本運(yùn)算

三種性質(zhì)函數(shù)

四種常用函數(shù)25

§3.1函數(shù)的基本概念

（1）一個(gè)基本概念——函數(shù)的基本概念。

函數(shù)建立了從一個(gè)集合到另一個(gè)集合的特殊對應(yīng)關(guān)系。設(shè)有集合X與Y，如果我們有一種對應(yīng)關(guān)系f，使X的任一元素x能與y中的一個(gè)唯一的元素y相對應(yīng)，則這個(gè)對應(yīng)關(guān)系f叫從X到Y(jié)的函數(shù)或叫從X到Y(jié)的映射。x所對應(yīng)的y內(nèi)的元素y叫x的像，而x則叫y的像源。上述函數(shù)我們可以表示成f：XY；或?qū)懗蒟Y；以及y＝f（x）。（2）三種不同性質(zhì)函數(shù)：

滿射與內(nèi)射

一對一與多對一

一一對應(yīng)（雙射）26

y1y2y3y4

x1x2x3x4

y1y2y3y4

x1x2x3x4x5

y1y2y3y4

x1x2x3x4

XYg

XYf

XYh27

從圖中可以看出函數(shù)f使得Y中的每個(gè)元素均有X中的元素與之對應(yīng)，這種函數(shù)叫做從X到Y(jié)上的函數(shù)，否則叫做從X到Y(jié)內(nèi)的函數(shù)。從圖中可以看出，函數(shù)g使得不但X中的每一個(gè)元素xi唯一對應(yīng)一個(gè)Y中的一個(gè)元素yj，而且也只有一個(gè)xi對應(yīng)yj，也就是說一個(gè)像只有一個(gè)像源與之對應(yīng)，這種函數(shù)叫做一對一的函數(shù)，否則叫做多對一的函數(shù)。從圖中可以看出，函數(shù)h使得X與Y間建立了—一對應(yīng)的關(guān)系，這種函數(shù)叫X與了間—一對應(yīng)的函數(shù)。

28

§3.2復(fù)合函數(shù)、反函數(shù)、多元函數(shù)

（3）兩種運(yùn)算：

復(fù)合運(yùn)算（復(fù)合函數(shù)）設(shè)函數(shù)f：XY，g：YZ則復(fù)合函數(shù)h＝gf：XZ是一個(gè)新的函數(shù)。定義：設(shè)函數(shù)f：XY，g：YZ，它們所組成的復(fù)合函數(shù)或叫復(fù)合映射gf，也是一個(gè)函數(shù)h：XZ，即：

h＝g

f：{(x,z)|xX,zZ且至少存在一個(gè)yY，有y=f（x），z＝g（y）}．29

y1y2

x1x2x3

z1z2YXZhfg30逆運(yùn)算（反函數(shù)）定義：設(shè)f：XY是—一對應(yīng)的函數(shù)，則f所構(gòu)成的逆關(guān)系叫f的逆映射或叫f的反函數(shù)，記以f—1：YX

（4）函數(shù)分類：

一元函數(shù)：f(x)二元函數(shù)：f(x,y)多元函數(shù)：f(x1,x2,…xn)31

§3.3常用函數(shù)

（5）四種常用函數(shù)

常值函數(shù)：f(x)＝b

恒等函數(shù)：f(a)＝a

單調(diào)遞增函數(shù)與嚴(yán)格單調(diào)遞增函數(shù)：a<b，必有f(a)≤f(b)

：a<b，必有f(a)f(b)單調(diào)遞減函數(shù)與嚴(yán)格單調(diào)遞減函數(shù)：a<b，必有f(a)f(b)

：a<b，必有f(a)f(b)1aA’特征函數(shù)：f(a)＝

0aA’

32第四章有限集與無限集

§4.1有限集與無限集基本概念（1）有限集與無限集的基本概念

有限集的兩個(gè)定義

集合S與Nn

一一對應(yīng)

非無限集即為有限集

無限集的兩個(gè)定義

S與一一對應(yīng)函數(shù)f：SS使得：f(S)S

S存在與其等勢的真子集33

§4.2有限集（2）有限集有限集的基數(shù)——有限集元素個(gè)數(shù)有限集的計(jì)數(shù)——計(jì)算有限集中元素個(gè)數(shù)有限集計(jì)數(shù)的四種方法：

|A∪B|＝|A|+|B|

|A∪B|＝|A|+|B|－|A∩B|

|A∪B∪C|＝|A|+|B|+|C|－|A∩B|－|A∩C|－|B∩C|+|A∩B∩C|

|S1∪S2∪…∪Sn|＝∑|Si|－∑|Si∩Sj|＋∑

|Si∩Sj∩Sk|（－1）∑|S1∩S2∩…∩Sn|ni=11≤i＜j≤n1≤i＜j＜k≤nn－134

§4.3無限集（3）四個(gè)常用的無限集：

自然數(shù)集N

整數(shù)集I

有理數(shù)集Q

實(shí)數(shù)集R

（4）無限集的勢（5）無限集分類（按勢分類）自然數(shù)集可列集——基數(shù)為0

整數(shù)集無限集實(shí)數(shù)集——基數(shù)為有理數(shù)集更大基數(shù)的集——（A）35第三篇代數(shù)系統(tǒng)

代數(shù)系統(tǒng)是建立在集合論基礎(chǔ)上以代數(shù)運(yùn)算為研究對象的學(xué)科。本篇共三章，第五章代數(shù)系統(tǒng)基礎(chǔ)介紹代數(shù)系統(tǒng)的一般原理與性質(zhì)，

第六章群論，主要介紹具有代表性的代數(shù)系統(tǒng)－群，最后第七章其它代數(shù)系統(tǒng)，介紹除群外常見的一些代數(shù)系統(tǒng)，如環(huán)、域、格與布爾代數(shù)等，這三章相互配合構(gòu)成了代數(shù)系統(tǒng)的完整的整體。36第五章代數(shù)系統(tǒng)基礎(chǔ)

§5.1代數(shù)系統(tǒng)一般概念

1．代數(shù)系統(tǒng)中的基本概念（1）代數(shù)系統(tǒng)：集合上具有封閉性的運(yùn)算組成代數(shù)系統(tǒng)（S,

）。（2）子代數(shù)：代數(shù)系統(tǒng)（S,

），（S，）滿足：

①SS

②如

a,bS，ab=a

b則稱（S，）為（S,）的子代數(shù)。37§5.2代數(shù)系統(tǒng)常見的一些性質(zhì)（3）代數(shù)系統(tǒng)常見性質(zhì)

1）結(jié)合律：（a

b）

c＝a

（b

c）

2）交換律：a

b＝b

a3）分配律：a

（b＋c）＝（a

b）＋（ac）

4）單位元：a

1＝a5）逆元：a

a－1＝16）零元：a

0＝0

38

§5.3同構(gòu)與同態(tài)（4）同構(gòu)：（X，

）與（Y，）存在一一對應(yīng)函數(shù)g:XY使得如x1,x2X，則有：g（x1

x2）＝g（x1）g（x2）此時(shí)則稱（X,

）與（Y，）同構(gòu)。（5）同態(tài)：（X,

）與（Y，）存在函數(shù)g:XY使得如x1,x2X，則有：g（x1

x2）＝g（x1）g（x2）此時(shí)則稱（X，

）與（Y，）同態(tài)。

§5.4常用代數(shù)系統(tǒng)（6）代數(shù)系統(tǒng)的構(gòu)成39（一個(gè)二元運(yùn)算

）兩個(gè)運(yùn)算有逆元兩個(gè)運(yùn)算有單位元代數(shù)系統(tǒng)結(jié)合律半群單位元、逆元群循環(huán)群可換群變換群子群循環(huán)半群單元半群可換半群整環(huán)域商環(huán)理想有補(bǔ)格有界格布爾代數(shù)正規(guī)子群、商群特殊環(huán)特殊子環(huán)兩個(gè)運(yùn)算的單位元、逆元

（兩個(gè)二元運(yùn)算：,)兩個(gè)運(yùn)算的結(jié)合律、交換律、吸收律格兩個(gè)運(yùn)算的分配律分配格單位元，無零因子

（兩個(gè)二元運(yùn)算：,)可換群,半群,對分配群

環(huán)

交換律

可換環(huán)

單位元,逆元交換律單位元生成元交換律生成元子集上的群特殊群特殊群40第六章群論

§6.1一些群的定義（7）半群——代數(shù)系統(tǒng)滿足交換律（8）單元半群——半群存在單位元（9）群——半群存在單位元與逆元（10）可換群——群滿足交換律（11）變換群——集合A上所有的變換構(gòu)成的集合E（A），對于復(fù)合變換所構(gòu)成的代數(shù)系統(tǒng)（E（A）,

）是一個(gè)群，稱變換群。（12）循環(huán)群——群有生成元。（13）有限群：群（S,

）中S為有限集。（14）子群：群（G，）上G的子集所構(gòu)成的群。41

（15）正規(guī)子群：（H，）是群（G，）的子群，如對aG都有：aH=Ha則稱（H，）是（G，）的正規(guī)子群。（16）陪集：H是G的子群，Ha＝{ha|hH},aH={ah|hH}分別稱H在G中的一個(gè)右陪集或左陪集。（17）商群：H是G的正規(guī)子群，對Ha，HbG/H，二元運(yùn)算（Ha)(Hb)＝Hab構(gòu)成群，則稱H是G的商群。（18）單元半群性質(zhì)：

單元半群的子系統(tǒng)若包含單位元也是單元半群。

可列個(gè)元素的單元半群的運(yùn)算組合表每行（列）均不相同。

循環(huán)單元半群是可換單元半群。

可換單元半群的所有等冪元素是一個(gè)子單元半群。42§6.2一些群的理論與半群性質(zhì)：

半群的子代數(shù)也是半群。

循環(huán)半群是可換半群。（19）關(guān)于群的基本理論

群方程可解性：a

x=b（或xa=b）對x存在唯一解；

群的消去律：a

b=a

c（或ba=ca）必有b=c；

任一群必與變換群同構(gòu)；

與一個(gè)群同構(gòu)或滿同態(tài)的代數(shù)系統(tǒng)必為群；

一個(gè)代數(shù)系統(tǒng)有限群滿足結(jié)合律及消去律則必為群；43有限群必與置換群同構(gòu)；循環(huán)群要么與（I,＋）同構(gòu)，要么與（Zm，＋m）同構(gòu)；一個(gè)群子集H構(gòu)成群（H,o）的充分必要條件：a,bH

則a

bH,aH

則a－1

H；一個(gè)群子集H構(gòu)成子群（H,o）的充分必要條件：a,b

H則ab－1H；一個(gè)有限群的階一定被它的子群的階所等分（拉格朗日定理）；f是群（G,）與（G，）的滿同態(tài)，K是f的核，則必有：（G/k,）與（G，）同構(gòu)；44第七章環(huán)論與格論

§7.1環(huán)論（20）環(huán)：（R，＋,?），對＋的可換群，對?的半群，

對＋的分配律；（21）整環(huán)：環(huán)（R，＋,?）中，運(yùn)算?有單位元，無零因子；（22）域：環(huán)（P，＋,?）中，運(yùn)算?交換律，有單位元，逆元；

45（23）環(huán)的基本理論環(huán)的基本運(yùn)算性質(zhì)：

a

0=0

a=0；

a（－b）=（－a）b=－（a

b）

(－a)

(－b)＝a

b環(huán)中無零因子環(huán)滿足消去律；

環(huán)中子系統(tǒng)S是子環(huán)的充要條件是as

則必有a－1S。（24）域的基本理論

1）域是整環(huán)；

2）有限整環(huán)必是域。

3)域滿足消去律46

§7.2格與布爾代數(shù)（25）格：（P，＋,

）中，兩個(gè)運(yùn)算的結(jié)合律、吸收律、交換律；（26）偏序格：P上的偏序關(guān)系≤所組成的偏序集(P，≤)對P的任意子集均有上確界與下確界，則稱(P，≤)為偏序格。（27）布爾代數(shù)：格（B，＋,

）中，兩個(gè)運(yùn)算的分配律、單位元、逆元。47（28）格的基本理論

1)格滿足冪等律；

2)格的子代數(shù)必為格；

3)格滿足對偶律；

4）一個(gè)偏序格必是一個(gè)代數(shù)格，反之亦然；

48（29）布爾代數(shù)的基本理論

—

布爾代數(shù)（B，＋，）滿足：（對＋與

）

交換律

結(jié)合律

等冪律

吸收律

分配律

零一律

同一律

互補(bǔ)律

雙補(bǔ)律

德摩根律49

(30)布爾函數(shù)

1)B={0,1}上的函數(shù)：f：Bn→B稱為布爾函數(shù)。

2)布爾表達(dá)式：由0,1，布爾變元經(jīng)補(bǔ)、和、積可構(gòu)成布爾表達(dá)式。

3)布爾積之和展開式。

4)布爾函數(shù)可以用一個(gè)布爾積之和展開式表示。50第四篇圖論

圖論用‘結(jié)點(diǎn)’表示事物，而用‘邊’表示事物間聯(lián)系，并用‘結(jié)點(diǎn)’與‘邊’所構(gòu)成的圖用以研究客觀世界。為便于計(jì)算，建立了圖的矩陣表示，這樣可以將圖論研究與計(jì)算相結(jié)合，從而使圖論研究具有很大的實(shí)用性。由于圖的形式很多，在實(shí)用中我們一般對若干種常用的圖作研究，它們是樹。在圖論學(xué)習(xí)中主要要掌握如下幾個(gè)方面：51

①圖論中的基本概念。

②圖論中的基礎(chǔ)理論。

③圖的矩陣計(jì)算。

④幾種常用的圖。在本篇中共有兩部分組成，它們是圖論原理與常用圖，其中圖論原理部分介紹圖的基本概念、理論與計(jì)算而常用圖部分則介紹樹。這兩部分的有機(jī)結(jié)合構(gòu)成了圖論的完整的整體。52第八章圖論原理

§8.1圖的基本概念

§8.1.1圖

§8.1.2圖的基本概念（1）圖的概念圖由結(jié)點(diǎn)集V＝{v1，v2，…，vn}與邊集E＝{l1，l2，…，lm}所組成，可記為：

G＝<V，E>

（2）有向圖與無向圖

①邊為有向的圖稱為有向圖

②邊為無向的圖稱為無向圖53

（3）幾種特殊的圖

①零圖：無邊的圖。

②平凡圖：僅有一個(gè)結(jié)點(diǎn)所組成的圖。

③完全圖：各結(jié)點(diǎn)間均有邊相聯(lián)的圖。

④補(bǔ)圖：G＝<V，E>，G＝<V，E>如有＝<V，E∪E>為完全圖且E∩E＝，則稱G為G的補(bǔ)圖。

⑤簡單圖與多重圖：包括多重邊的圖稱為多重圖，否則稱為簡單圖。

⑥有權(quán)圖：邊帶權(quán)的圖。54

§8.1.3圖的同構(gòu)

⑦同構(gòu)圖：G＝<V，E>，G＝<V，E>，V與V以及相應(yīng)邊的結(jié)點(diǎn)對中有一一對應(yīng)關(guān)系。

§8.1.4圖中結(jié)點(diǎn)的次數(shù)（4）圖中結(jié)點(diǎn)的次數(shù)

引入次數(shù)deg（v）、引出次數(shù)deg（v）、次數(shù)deg（v）。

定理：deg（vi）=2m55

§8.2通路、回路與連通性（5）通路與回路

①通路：圖中vi至vj的通路是在邊的序列：（vi，vi1），（vi1，vi2），…（vik－1，vik），其中vik＝vj②基本通路與簡單通路：圖各邊全不同的通路叫簡單通路，各點(diǎn)全不同的通路叫基本通路。

③環(huán)與回路：邊的始點(diǎn)與終點(diǎn)相同稱環(huán)，通路的起始點(diǎn)與終止點(diǎn)相同稱回路。

④簡單回路與基本回路：簡單（基本）通路的起始點(diǎn)與終止點(diǎn)相同稱簡單（基本）回路。

⑤有向圖（n,m）的基本通路長度≤n－1，基本回路長度≤n。56

（6）圖的連通性

①圖的可達(dá)性：圖的結(jié)點(diǎn)vi到vj間存在通路則稱從vi到vj是可達(dá)的。

②連通圖：圖的任何兩結(jié)點(diǎn)間均可達(dá)。

③三種連通圖：

強(qiáng)連通：有向圖中任何兩結(jié)點(diǎn)間相互可達(dá)則稱強(qiáng)連通。

弱連通：有向圖忽略其邊的方向所構(gòu)成的無向圖為連通則稱弱連通。

單向連通：有向圖兩結(jié)點(diǎn)間至少有一向是可達(dá)的則稱單向連通。57

§8.3歐拉圖（7）歐拉圖

歐拉回路與歐拉通路：通過G中每邊一次的回（通）路稱歐拉回（通）路，具此回路的圖稱歐拉圖。

③歐拉圖與歐拉通路：歐拉圖每個(gè)結(jié)點(diǎn)次數(shù)為偶數(shù)。由vi到vj歐拉通路vi，vj結(jié)點(diǎn)次數(shù)為奇數(shù)，其它結(jié)點(diǎn)次數(shù)為偶數(shù)。58

§8.4漢密爾頓圖（8）漢密爾頓圖

漢密爾頓回路與漢密爾頓通路：通過G中每個(gè)結(jié)點(diǎn)一次的回（通）路稱漢密爾回（通）路，具此回路的圖稱漢密爾頓圖。

漢密爾頓圖與漢密爾頓通路中的定理漢密爾頓圖的必要條件G＝<V,E>中V1V且P（G－V1）≤|V1|，其中P（G－V1）為從G中刪除V1（包括V1中各結(jié)點(diǎn)及其關(guān)聯(lián)邊）后所得到的連通分支數(shù)。漢密爾頓圖的充分條件：G＝<V,E>無向簡單圖，|V|≥3，G中每結(jié)點(diǎn)對次數(shù)之和≥|V|。漢密爾頓通路：有向圖D＝<V,E>，|V|≥2所有有向邊均用無向邊替代后得無向圖含生成子圖Kn。59

§8.5圖的矩陣表示法（9）圖的鄰接矩陣：G＝<V,E>為（n，m）圖，其鄰接矩陣：A＝（aij）n×n.

1（vi，vj）

E

aij＝

0（vi，vj）

E

（10）通路計(jì)算：

B＝A

，B＝（bij）n×n，Bij表示從vi到vj長度為

的通路數(shù)，Bij表示vi的回路數(shù)。（11）可達(dá)性計(jì)算：

P＝A（＋）A（2）（＋）……（＋）A（n），P＝（Pij）n×n，Pij表示從vi到vj是否可達(dá)（0不可達(dá)，1可達(dá)）。（12）連通性計(jì)算：可達(dá)性矩陣除對角線元素外均為160第九章常用圖

§9.1樹

§9.1.1樹的基本性質(zhì)（13）樹的基本概念與屬性

①樹：不含回路的連通圖。（n,m）樹中必有m＝n－1②樹的性質(zhì)

T為樹兩結(jié)點(diǎn)間只有一條通路。

§9.1.2有向樹（14）有向樹

61

（15）外向樹與內(nèi)向樹：有向樹中，僅有一個(gè)結(jié)點(diǎn)引入次數(shù)為0（根），其它結(jié)點(diǎn)引入次數(shù)為1，有些結(jié)點(diǎn)引出次數(shù)為0（葉）稱外向樹。有向樹中，僅有一個(gè)結(jié)點(diǎn)引出次數(shù)為0（根），其它結(jié)點(diǎn)引入次數(shù)為1，有些結(jié)點(diǎn)引入次數(shù)為0（葉）稱內(nèi)向樹。

§9.1.3二元樹（16）二元樹與多元樹：一個(gè)n個(gè)結(jié)點(diǎn)的外向樹：（vi）≤m（i=1,2,…,n），稱m元樹。如（vi）＝m（i=1,2,…,n）（除葉外），稱m元完全樹，當(dāng)m＝2時(shí)稱二元樹或二元完全樹。

§9.1.4生成樹（17）生成樹：連通圖G＝<V,E>的生成樹TG＝<V,E>G的子圖，且是樹并滿足V＝V，EE。

生成樹尋找算法：在G中尋找基本回路，尋到后刪除邊，并繼續(xù)尋找，直到無基本回路出現(xiàn)為止。62第五篇數(shù)理邏輯

數(shù)理邏輯是用數(shù)學(xué)方法研究形式邏輯演繹推理規(guī)則的科學(xué)，它是一門數(shù)學(xué)，是一門研究演繹推理規(guī)則的數(shù)學(xué)，在學(xué)習(xí)此部分時(shí)，主要要掌握如下幾個(gè)要點(diǎn)：

①思維的形式化

②指派法

③公式推理

④公理系統(tǒng)

⑤范式

⑥自動(dòng)定理證明

63

本篇由命題邏輯、謂詞邏輯、公理化理論部分組成，其中命題邏輯以命題為研究對象而謂詞邏輯則以謂詞為研究對象，而公理化理論則是數(shù)理邏輯中演繹推理的形式化思想的介紹，它們的有機(jī)結(jié)合構(gòu)成完整的整體。64第十章命題邏輯

命題邏輯以命題為對象，研究命題的符號體系及推理規(guī)則?！?0.1命題與命題聯(lián)結(jié)詞（1）命題——能判別真假的語句。（2）基本命題聯(lián)結(jié)詞——否定、并且、或者、蘊(yùn)含、等價(jià)?！?0.2命題公式（3）命題公式——由命題及命題聯(lián)結(jié)詞構(gòu)成命題公式?！?0.3重言式（4）指派——命題公式中變元的一組確定的值。（5）重言式——所有指派均取值為真的公式。65§10.4命題邏輯基本等式及等式推理（6）等式推理：由三部分組成：它們是基本等式、推理規(guī)則及推理過程。（7）命題邏輯42個(gè)基本等式。交換律

P∨Q＝Q∨P；

P∧Q＝Q∧P；

PQ＝QP．結(jié)合律（P∨Q）∨R＝P∨（Q∨R）；（P∧Q）∧R＝P∧（Q∧R）；（PQ）R＝P（QR）．分配律

P∧（Q∨R）＝（P∧Q）∨（P∧R）；

P∨（Q∧R）＝（P∨Q）∧（P∨R）；66否定深入P＝P；（P∧Q）＝P∨Q；（P∨Q）＝P∧Q；（PQ）＝P∧Q；(14)（PQ）＝PQ＝PQ；變元等同P∧P＝P；P∨P＝P；P∧P＝F；P∨P＝T；PP＝T；PP＝P；PP＝P；PP＝T；PP＝PP＝F；67常值與變元的聯(lián)結(jié)T∧P＝P；F∧P＝F；T∨P＝T；F∨P＝F；TP＝P；FP＝T；PT＝T；PF＝P；TP＝P；FP＝P；68聯(lián)結(jié)詞化歸P∧Q＝（P∨Q）；P∨Q＝（P∧Q）；PQ＝P∨Q；PQ＝（PQ）∧（QP）其它PQ＝QP(PQ)∧（PR）＝PQ∧RP∨（P∧Q）＝PP（QR）＝P∧QRP∧（P∨Q）＝P69（8）推理規(guī)則：

代入規(guī)則

替換規(guī)則

(9)推理過程由P到Q的推理過程是一個(gè)等式序列：

P=P1P1=P2

……Pn-1=Pn

Pn=P70§10.5

命題邏輯基本蘊(yùn)含式及蘊(yùn)含推理（10）蘊(yùn)含推理是單向推理，它有三部分組成：前提－已知條件證明－是一種過程定理－結(jié)論

(11)蘊(yùn)含推理組成：基本蘊(yùn)含式推理規(guī)則證明過程71（9）19個(gè)基本蘊(yùn)含重言式

P∧QP；

P∧QQ；

PP∨Q；

QP∨Q；

PPQ；

QPQ；

（PQ）

P；

（PQ）

Q；72P∧（P∨Q）Q；

Q∧（P∨Q）P；

P∧（PQ）Q；

Q∧（PQ）P；

(PQ)∧(QR)PR；

(PQ)∧(RS)P∧RQ∧S；

(P∨Q)∧(PR)∧(QR)R；

P(QP∧Q)；

(PQ)((QR)(PR))；

(P(QR))(Q(PR))；

(PQ)((RQ)(P∨RQ))．73

（13）11個(gè)推理規(guī)則

P∧Q├P；

P∧Q├Q；

P├P∨Q；

Q├P∨Q；

P，QP├Q；

P，P∨Q├Q；

P，PQ├Q；

Q，PQ├P；

PQ，QR├PR；

PQ，RS├P∧RQ∧S；

P∨Q，PR，QR├R；

74

(14)證明過程

是一個(gè)公式序列并運(yùn)用三個(gè)規(guī)則：

P規(guī)則

T規(guī)則

CP規(guī)則§10.6范式（15）范式——命題公式的一種標(biāo)準(zhǔn)形式（16）主析取范式：該范式是一個(gè)析取式，每個(gè)析取項(xiàng)是所有命題變元式其否定的合取式。（17）主異合取范式：該范式是一個(gè)合取式，每個(gè)析取項(xiàng)是所有命題變元式其否定的析取式。75

§10.8命題聯(lián)結(jié)詞的擴(kuò)充與歸約（18）命題聯(lián)結(jié)詞的擴(kuò)充——異或：、謝佛：、魏泊：、蘊(yùn)含否定：（19）命題聯(lián)結(jié)詞的歸約命題聯(lián)結(jié)詞可歸約為如下形式之一：

{,}{,}{}{}76第十一章謂詞邏輯

謂詞邏輯基本概念§11.1謂詞與個(gè)體（1）個(gè)體

個(gè)體常量與個(gè)體變量

個(gè)體域與全總個(gè)體域（2）謂詞

一元謂詞——刻劃個(gè)體性質(zhì)

二元謂詞——刻劃兩個(gè)個(gè)體間關(guān)系

n元謂詞——刻劃n個(gè)個(gè)體間關(guān)系77§11.2量詞（3）存在量詞：xP(x)——“有一些”之語義（4）全稱量詞：xP(x)——“所有”之語義（5）量詞的轄域——量詞所作用的范圍§11.3函數(shù)（6）函數(shù)——個(gè)體間的特定關(guān)系稱函數(shù)，它是個(gè)體間的映射。

f(x)中X是個(gè)體而f為函數(shù)符號，f(x)為函數(shù)。78

§11.4謂詞邏輯公式（7）謂詞邏輯公式

項(xiàng)：個(gè)體是項(xiàng)，函數(shù)是項(xiàng)

原子公式：P（t1,t2,…tn）是原子公式（其中ti為項(xiàng)）

公式：

原子公式是公式；

A，B是公式，則（A）,（A∨B）,（A∧B）,（AB），（AB）是公式；

A是公式，x為個(gè)體變量，則（xA），（xA）為公式；

公式由且僅由有限次使用前面三步而得。79

§11.5自由變元與約束變元（8）謂詞公式中的自由變元與約束變元

謂詞公式中的自由變元與約束變元

約束變元的改名規(guī)則——改名在量詞變元及其轄域中該變元的約束出現(xiàn)處進(jìn)行且該變元不在量詞轄域內(nèi)出現(xiàn)過。

自由變元的代入規(guī)則——代入在公式的自由變元出現(xiàn)的每一處進(jìn)行且該代入變元不允許在式中以任何約束形式出現(xiàn)。80

§11.6謂詞邏輯永真公式（9）謂詞邏輯永真公式定義謂詞公式的解釋與賦值（10）謂詞邏輯永真公式定義——公式在所有解釋下對所有賦值均為真（11）謂詞邏輯永真公式等式：

（xP（x））＝x（P（x））

（xP（x））＝x（P（x））

xP（x）∨Q＝x（P（x）∨Q）

xP（x）∧Q＝x（P（x）∧Q）81xP（x）∨Q＝x（P（x）∨Q）xP（x）∧Q＝x（P（x）∧Q）xyP（x,y）＝y(tǒng)x（P（x,y）xyP（x,y）＝y(tǒng)x（P（x,y）xP（x）Q＝x（P（x）Q）xP（x）Q＝x（P（x）Q）QxP（x）＝x（QP（x））QxP（x）＝x（QP（x））x（P（x）∧Q（x））＝x（P（x）∧xQ（x）x（P（x）∨Q（x））＝x（P（x）∨xQ（x）82（12）謂詞邏輯的蘊(yùn)含永真公式xyP（x,y）

yx（P（x,y））xP（x）

P（x）P（x）xP（x）xP（x）∨xQ（x）x（P（x）∨Q（x））xP（x）∧xQ（x）x（P（x）∧Q（x））x（P（x）x（P（x））x（P（x）Q（x））x（P（x）xQ（x）x（P（x）Q（x））xP（x）xQ（x）83§11.7謂詞邏輯等式推理(13)有三部分組成：

基本等式

推理規(guī)則——代入規(guī)則與替換規(guī)則

推理過程——等式序列§11.８謂詞邏輯蘊(yùn)含推理(1４)謂詞邏輯蘊(yùn)含推理是單向推理，有三部分組成：

前提

證明——推理規(guī)則與證明過程

定理84（１５）謂詞邏輯蘊(yùn)含推理組成：

推理規(guī)則：——ＵＳ規(guī)則——ＵＧ規(guī)則——ＥＳ規(guī)則——ＥＧ規(guī)則

證明規(guī)則：——Ｐ規(guī)則——Ｔ規(guī)則——ＣＰ規(guī)則85

§11.９謂詞邏輯范式（1６）前束范式——公式的所有量詞均非否定的出現(xiàn)在公式最前面，它的轄域一直延伸至公式末尾，且公式中不出現(xiàn)與。（1７）斯科林范式——前束范式的首標(biāo)處僅出現(xiàn)全稱量詞且公式中不出現(xiàn)自由變元x1x2…xnM（x1,x2,…,xn）86第十二章數(shù)理邏輯公理化理論

§12.1公理化理論的基本思想（1８）公理系統(tǒng)的兩個(gè)部分

公理系統(tǒng)的組成與推理

公理系統(tǒng)的討論：

不矛盾性

完整性

獨(dú)立性87§12.2命題邏輯與謂詞邏輯的公理化理論（1９）命題邏輯永真公理系統(tǒng)的組成１、組成部分

命題：P1，P2，…，Pn；

命題聯(lián)結(jié)詞：，∨，∧，，；

個(gè)體常量：a，b，c，x，y，z；

個(gè)體變量：P，Q，R…；

函數(shù)：f，g，h；

謂詞：，；

括號：（，）

88

項(xiàng)：

①

個(gè)體常量是項(xiàng)；

②個(gè)體變量是項(xiàng)；

③

f是n元函數(shù)，t1，t2，…,tn是項(xiàng)，則f(t1，t2，…,tn)是項(xiàng)；

④項(xiàng)由且僅由有限次使用①、②、③而得。

89

原子公式：P是n元謂詞，t1，t2，…，tn是項(xiàng)，則P（t1，t2，…，tn)是原子公式。命題邏輯公式：

①命題是公式；

②

P是公式則（P）是公式；

③P，Q是公式則（P∨Q），（P∧Q），（PQ），（PQ）是公式；

④

公式由且僅由有限次使用①，②，③而得。90

謂詞邏輯公式：

①原子公式是公式；

②A，B是公式則：（A），（A∨B），（A∧B），（AB）,（AB）是公式；

③A是公式則（xA），（xB）是公式；

④公式由且僅由有限次使用①、②、③而得。91

２推理部分

1）公理如P，Q，R為公式，則有下述的公理：

①PP；

②（P（QR））（Q（PR））；

③（PQ）（（QR）（PR））；

④（P（PQ））（PQ）；

⑤（PQ）（PQ）；

⑥（PQ）（QP）；

92⑦（PQ）（QP）（PQ））；⑧P∧QQ；⑨P∧QP；⑩P（QP∧Q）；

PP∨Q；

QP∨Q；（QP）（（RP）（Q∨RP））；（PQ）（QP）；

PP；111213141593

2）推理規(guī)則分離規(guī)則：PQ，P├Q。

3）證明（過程）與定理證明（過程）給出了公理系統(tǒng)中定理生成的過程，它是一個(gè)公式序列：P1，P2，…，Pn，其中每個(gè)Pi（i＝1，2，…，n）必須滿足下條件之一。

94

①Pi是公理；

②Pi是由Pk，Pr，（k，r<i）施行分離規(guī)則而得。最后，Pn＝Q即為定理。（２０）導(dǎo)出規(guī)則——如有AB為定理則必有A├B。（２１）假設(shè)推理１具有特定環(huán)境下的假設(shè)作前提２推理定理——設(shè)有A1，A2，…，An├B，則必有：A1,A2,…An-1├An

B。

95３假設(shè)推理的證明過程必須滿足：

①Ｐi是假設(shè)前提；

②Ｐi是公理；

③Ｐi是由Ｐk，Pr用分離規(guī)則而得

最后。Pn=B，而Ａ１→（Ａ２→（…（Ａn→B））…）為定理。96（２２）額外假設(shè)推理——反證法１以結(jié)論為假設(shè)作前提２反證推理定理：設(shè)有A1，A2，…，An，B├P∧P，則必有：

├A1→(A2→(…(An→B））…）

3反證推理證明過程必須滿足

1)Pi是公理；

2)Pi是假設(shè)；

3)Pi是待證定理B的否定，即為P；

4)Pi是由Pk，Pr用分離規(guī)則而得。最后Pn=P∧P，而此時(shí)：A1→(A2→(…(An→B））…）為定理。97

（23）謂詞邏輯永真公理系統(tǒng)

1．系統(tǒng)組成部分

2．推理部分

1）公理設(shè)P，Q，R為公式，則有公理如下：

98①pp．②（P（QR））（Q（PR））．③（PQ）（（QR）（PR））．④（P（PQ））（PQ）．⑤（PQ）（PQ）．⑥（PQ）（QP）．⑦（PQ）（（QP）（PQ））．⑧P∧QQ．99⑨P∧QP．⑩P（QP∧Q）．

PP∨Q．

QP∨Q．（QP）（（RP）（Q∨RP））．（PQ）（QP）．

PP．

xP（x）P（x）．

P（x）xP（x）。11121314151617100

2）推理規(guī)則

①分離規(guī)則：PQ，