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

1離散數(shù)學導論（第四版）

電子教案

2第一篇緒言

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

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

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

離散性

可構造性

抽象性

3．離散數(shù)學的內容離散數(shù)學的主要內容為：

集合論

代數(shù)結構

圖論

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

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

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

集合中的一個基本概念

集合中的兩種關系

集合中的三種特殊集合

集合中的三種表示方法

集合中的五種運算

集合中的21個常用公式5

§1.1集合論基本概念

（1）

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

集合間的比較關系：A＝B，A≠B，AB，AB。

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

空集

全集E

冪集（A）。6

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

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

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

圖示法。即用文氏圖表示集合及集合間的關系。例：

AAB7§

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

交運算：A∩B

倂運算：A∪B

差運算：A－B

補運算：～A

對稱差運算：A＋B8（6）集合的21個公式：交換律：A∪B＝B∪AA∩B＝B∩A結合律：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∩＝互補律：A∪～A＝EA∩～A＝雙補律：～（～A）＝A10E與

的互補：～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）。

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

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

一種預備知識

一個基本概念

兩種表示方法

三種運算

九個公式

五種性質

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

n元有序組是一種特殊的集合結構形式，它有兩個基本概念與一種基本運算（笛卡爾乘積）。

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

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

）

基本運算：笛卡爾乘積。例：AB14§2.2

關系基本概念

（1）一個主要的概念——二元關系的基本概念：

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

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

圖表示法：有向圖15§2.2關系運算（3）兩種運算：

關系的復合運算

關系的逆運算（4）有關運算的五個公式：復合運算的公式：

(RS)T＝R(S

T)

Rm

Rn＝Rm+n(Rm)n＝Rmn

逆運算的公式：

R＝R(R

S)＝R

S

～～～16§2.4

關系重要性質（5）關系的五種性質

關系的自反性

關系的反自反性

關系的對稱性

關系的反對稱性

關系的傳遞性17（6）六種常用關系

次序關系之一：偏序關系

次序關系之二：擬序關系

次序關系之三：線性次序關系

次序關系之四：字典次序關系

相容關系

等價關系18§2.5

閉包運算（1）關系的閉包運算

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

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

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

～i=119§2.6

次序關系

（7）次序關系

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

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

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

上的偏序關系。如建立∑＊上的次序關系：設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）如存在一個最大的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）如存在一個最大的K＝min(n，m)，使得x1＝y(tǒng)1，x2＝y(tǒng)2，…，xn＝y(tǒng)n

，此時如n≤m，則我們說xLy；如m≤n，則我們說yLx。

21四個次序關系間的關系：

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

字典次序關系必為線性次序關系

R是擬序則必反對稱八個概念：

最大元素（最小元素）

極大元素（極小元素）

上界（下界）

上確界（下確界）22§2.7相容關系

（8）相容關系

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

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

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

23§2.8等價關系

（9）等價關系

等價關系定義——X上自反、對稱、傳遞的關系稱等價關系。

等價類——R是X上等價關系，對xX可構造一個X的子集[x]R

稱為x對R的等價類。

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

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

函數(shù)是一種特殊的關系，它在數(shù)學中具有普遍重要價值，函數(shù)主要內容有：

一個基本概念

兩種基本運算

三種性質函數(shù)

四種常用函數(shù)25

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

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

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

滿射與內射

一對一與多對一

一一對應（雙射）26

y1y2y3y4

x1x2x3x4

y1y2y3y4

x1x2x3x4x5

y1y2y3y4

x1x2x3x4

XYg

XYf

XYh27

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

28

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

（3）兩種運算：

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

h＝g

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

y1y2

x1x2x3

z1z2YXZhfg30逆運算（反函數(shù)）定義：設f：XY是—一對應的函數(shù)，則f所構成的逆關系叫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

單調遞增函數(shù)與嚴格單調遞增函數(shù)：a<b，必有f(a)≤f(b)

：a<b，必有f(a)f(b)單調遞減函數(shù)與嚴格單調遞減函數(shù)：a<b，必有f(a)f(b)

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

0aA’

32第四章有限集與無限集

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

有限集的兩個定義

集合S與Nn

一一對應

非無限集即為有限集

無限集的兩個定義

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

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

§4.2有限集（2）有限集有限集的基數(shù)——有限集元素個數(shù)有限集的計數(shù)——計算有限集中元素個數(shù)有限集計數(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）四個常用的無限集：

自然數(shù)集N

整數(shù)集I

有理數(shù)集Q

實數(shù)集R

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

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

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

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

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

1．代數(shù)系統(tǒng)中的基本概念（1）代數(shù)系統(tǒng)：集合上具有封閉性的運算組成代數(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)常見的一些性質（3）代數(shù)系統(tǒng)常見性質

1）結合律：（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同構與同態(tài)（4）同構：（X，

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

x2）＝g（x1）g（x2）此時則稱（X,

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

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

x2）＝g（x1）g（x2）此時則稱（X，

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

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

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

（兩個二元運算：,)兩個運算的結合律、交換律、吸收律格兩個運算的分配律分配格單位元，無零因子

（兩個二元運算：,)可換群,半群,對分配群

環(huán)

交換律

可換環(huán)

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

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

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

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

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

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

可列個元素的單元半群的運算組合表每行（列）均不相同。

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

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

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

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

群方程可解性：a

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

群的消去律：a

b=a

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

任一群必與變換群同構；

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

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

則a

bH,aH

則a－1

H；一個群子集H構成子群（H,o）的充分必要條件：a,b

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

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

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

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

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，＋,

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

）中，兩個運算的分配律、單位元、逆元。47（28）格的基本理論

1)格滿足冪等律；

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

3)格滿足對偶律；

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

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

—

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

）

交換律

結合律

等冪律

吸收律

分配律

零一律

同一律

互補律

雙補律

德摩根律49

(30)布爾函數(shù)

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

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

3)布爾積之和展開式。

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

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

①圖論中的基本概念。

②圖論中的基礎理論。

③圖的矩陣計算。

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

§8.1圖的基本概念

§8.1.1圖

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

G＝<V，E>

（2）有向圖與無向圖

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

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

（3）幾種特殊的圖

①零圖：無邊的圖。

②平凡圖：僅有一個結點所組成的圖。

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

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

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

⑥有權圖：邊帶權的圖。54

§8.1.3圖的同構

⑦同構圖：G＝<V，E>，G＝<V，E>，V與V以及相應邊的結點對中有一一對應關系。

§8.1.4圖中結點的次數(shù)（4）圖中結點的次數(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②基本通路與簡單通路：圖各邊全不同的通路叫簡單通路，各點全不同的通路叫基本通路。

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

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

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

（6）圖的連通性

①圖的可達性：圖的結點vi到vj間存在通路則稱從vi到vj是可達的。

②連通圖：圖的任何兩結點間均可達。

③三種連通圖：

強連通：有向圖中任何兩結點間相互可達則稱強連通。

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

單向連通：有向圖兩結點間至少有一向是可達的則稱單向連通。57

§8.3歐拉圖（7）歐拉圖

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

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

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

漢密爾頓回路與漢密爾頓通路：通過G中每個結點一次的回（通）路稱漢密爾回（通）路，具此回路的圖稱漢密爾頓圖。

漢密爾頓圖與漢密爾頓通路中的定理漢密爾頓圖的必要條件G＝<V,E>中V1V且P（G－V1）≤|V1|，其中P（G－V1）為從G中刪除V1（包括V1中各結點及其關聯(lián)邊）后所得到的連通分支數(shù)。漢密爾頓圖的充分條件：G＝<V,E>無向簡單圖，|V|≥3，G中每結點對次數(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）通路計算：

B＝A

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

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

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

§9.1樹

§9.1.1樹的基本性質（13）樹的基本概念與屬性

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

T為樹兩結點間只有一條通路。

§9.1.2有向樹（14）有向樹

61

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

§9.1.3二元樹（16）二元樹與多元樹：一個n個結點的外向樹：（vi）≤m（i=1,2,…,n），稱m元樹。如（vi）＝m（i=1,2,…,n）（除葉外），稱m元完全樹，當m＝2時稱二元樹或二元完全樹。

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

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

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

①思維的形式化

②指派法

③公式推理

④公理系統(tǒng)

⑤范式

⑥自動定理證明

63

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

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

P∨Q＝Q∨P；

P∧Q＝Q∧P；

PQ＝QP．結合律（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)結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)結詞化歸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的推理過程是一個等式序列：

P=P1P1=P2

……Pn-1=Pn

Pn=P70§10.5

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

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

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個推理規(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)證明過程

是一個公式序列并運用三個規(guī)則：

P規(guī)則

T規(guī)則

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

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

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

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

個體常量與個體變量

個體域與全總個體域（2）謂詞

一元謂詞——刻劃個體性質

二元謂詞——刻劃兩個個體間關系

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

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

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

項：個體是項，函數(shù)是項

原子公式：P（t1,t2,…tn）是原子公式（其中ti為項）

公式：

原子公式是公式；

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

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

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

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

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

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

自由變元的代入規(guī)則——代入在公式的自由變元出現(xià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）謂詞邏輯的蘊含永真公式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.８謂詞邏輯蘊含推理(1４)謂詞邏輯蘊含推理是單向推理，有三部分組成：

前提

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

定理84（１５）謂詞邏輯蘊含推理組成：

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

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

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

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

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

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

不矛盾性

完整性

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

命題：P1，P2，…，Pn；

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

個體常量：a，b，c，x，y，z；

個體變量：P，Q，R…；

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

謂詞：，；

括號：（，）

88

項：

①

個體常量是項；

②個體變量是項；

③

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

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

89

原子公式：P是n元謂詞，t1，t2，…，tn是項，則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)中定理生成的過程，它是一個公式序列：P1，P2，…，Pn，其中每個Pi（i＝1，2，…，n）必須滿足下條件之一。

94

①Pi是公理；

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

B。

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

①Ｐi是假設前提；

②Ｐi是公理；

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

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

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

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

1)Pi是公理；

2)Pi是假設；

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

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

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

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

2．推理部分

1）公理設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，