1離散數學導論（第四版）

電子教案

2第一篇緒言

本篇是對離散數學的宏觀介紹。

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

2．離散數學的特征

離散性

可構造性

抽象性

3．離散數學的內容離散數學的主要內容為：

集合論

代數結構

圖論

數理邏輯3第二篇集合論

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

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

集合中的一個基本概念

集合中的兩種關系

集合中的三種特殊集合

集合中的三種表示方法

集合中的五種運算

集合中的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集合代數（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第二章關系關系研究集合內元素間的關聯及集合間元素關聯，主要有：

一種預備知識

一個基本概念

兩種表示方法

三種運算

九個公式

五種性質

六種常用關系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＝y1，x2＝y2，…，xk＝yk而xk＋1＝yk+1，如果xk＋1≤yk＋1，則我們說xLy；如yk＋1≤xk＋1，則我們說yLx；（3）如存在一個最大的K＝min(n，m)，使得x1＝y1，x2＝y2，…，xn＝yn

，此時如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所構成的類產生X的劃分叫X關于R的商集記以X／R。24第三章函數

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

一個基本概念

兩種基本運算

三種性質函數

四種常用函數25

§3.1函數的基本概念

（1）一個基本概念——函數的基本概念。

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

滿射與內射

一對一與多對一

一一對應（雙射）26

y1y2y3y4

x1x2x3x4

y1y2y3y4

x1x2x3x4x5

y1y2y3y4

x1x2x3x4

XYg

XYf

XYh27

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

28

§3.2復合函數、反函數、多元函數

（3）兩種運算：

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

h＝g

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

y1y2

x1x2x3

z1z2YXZhfg30逆運算（反函數）定義：設f：XY是—一對應的函數，則f所構成的逆關系叫f的逆映射或叫f的反函數，記以f—1：YX

（4）函數分類：

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

§3.3常用函數

（5）四種常用函數

常值函數：f(x)＝b

恒等函數：f(a)＝a

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

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

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

0aA’

32第四章有限集與無限集

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

有限集的兩個定義

集合S與Nn

一一對應

非無限集即為有限集

無限集的兩個定義

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

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

§4.2有限集（2）有限集有限集的基數——有限集元素個數有限集的計數——計算有限集中元素個數有限集計數的四種方法：

|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）四個常用的無限集：

自然數集N

整數集I

有理數集Q

實數集R

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

整數集無限集實數集——基數為有理數集更大基數的集——（A）35第三篇代數系統

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

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

§5.1代數系統一般概念

1．代數系統中的基本概念（1）代數系統：集合上具有封閉性的運算組成代數系統（S,

）。（2）子代數：代數系統（S,

），（S，）滿足：

①SS

②如

a,bS，ab=a

b則稱（S，）為（S,）的子代數。37§5.2代數系統常見的一些性質（3）代數系統常見性質

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同構與同態（4）同構：（X，

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

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

）與（Y，）同構。（5）同態：（X,

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

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

）與（Y，）同態。

§5.4常用代數系統（6）代數系統的構成39（一個二元運算

）兩個運算有逆元兩個運算有單位元代數系統結合律半群單位元、逆元群循環群可換群變換群子群循環半群單元半群可換半群整環域商環理想有補格有界格布爾代數正規子群、商群特殊環特殊子環兩個運算的單位元、逆元

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

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

環

交換律

可換環

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

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

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

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

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

單元半群的子系統若包含單位元也是單元半群。

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

循環單元半群是可換單元半群。

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

半群的子代數也是半群。

循環半群是可換半群。（19）關于群的基本理論

群方程可解性：a

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

群的消去律：a

b=a

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

任一群必與變換群同構；

與一個群同構或滿同態的代數系統必為群；

一個代數系統有限群滿足結合律及消去律則必為群；43有限群必與置換群同構；循環群要么與（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，）的滿同態，K是f的核，則必有：（G/k,）與（G，）同構；44第七章環論與格論

§7.1環論（20）環：（R，＋,?），對＋的可換群，對?的半群，

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

45（23）環的基本理論環的基本運算性質：

a

0=0

a=0；

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

b）

(－a)

(－b)＝a

b環中無零因子環滿足消去律；

環中子系統S是子環的充要條件是as

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

1）域是整環；

2）有限整環必是域。

3)域滿足消去律46

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

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

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

1)格滿足冪等律；

2)格的子代數必為格；

3)格滿足對偶律；

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

48（29）布爾代數的基本理論

—

布爾代數（B，＋，）滿足：（對＋與

）

交換律

結合律

等冪律

吸收律

分配律

零一律

同一律

互補律

雙補律

德摩根律49

(30)布爾函數

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

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

3)布爾積之和展開式。

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

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

①零圖：無邊的圖。

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

③完全圖：各結點間均有邊相聯的圖。

④補圖：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圖中結點的次數（4）圖中結點的次數

引入次數deg（v）、引出次數deg（v）、次數deg（v）。

定理：deg（vi）=2m55

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

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

③環與回路：邊的始點與終點相同稱環，通路的起始點與終止點相同稱回路。

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

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

（6）圖的連通性

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

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

③三種連通圖：

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

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

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

§8.3歐拉圖（7）歐拉圖

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

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

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

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

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

的通路數，Bij表示vi的回路數。（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）外向樹與內向樹：有向樹中，僅有一個結點引入次數為0（根），其它結點引入次數為1，有些結點引出次數為0（葉）稱外向樹。有向樹中，僅有一個結點引出次數為0（根），其它結點引入次數為1，有些結點引入次數為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中尋找基本回路，尋到后刪除邊，并繼續尋找，直到無基本回路出現為止。62第五篇數理邏輯

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

①思維的形式化

②指派法

③公式推理

④公理系統

⑤范式

⑥自動定理證明

63

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

命題邏輯以命題為對象，研究命題的符號體系及推理規則。§10.1命題與命題聯結詞（1）命題——能判別真假的語句。（2）基本命題聯結詞——否定、并且、或者、蘊含、等價。§10.2命題公式（3）命題公式——由命題及命題聯結詞構成命題公式。§10.3重言式（4）指派——命題公式中變元的一組確定的值。（5）重言式——所有指派均取值為真的公式。65§10.4命題邏輯基本等式及等式推理（6）等式推理：由三部分組成：它們是基本等式、推理規則及推理過程。（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常值與變元的聯結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聯結詞化歸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）推理規則：

代入規則

替換規則

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

P=P1P1=P2

……Pn-1=Pn

Pn=P70§10.5

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

(11)蘊含推理組成：基本蘊含式推理規則證明過程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個推理規則

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)證明過程

是一個公式序列并運用三個規則：

P規則

T規則

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

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

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

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

個體常量與個體變量

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

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

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

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

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

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

項：個體是項，函數是項

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

公式：

原子公式是公式；

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

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

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

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

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

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

自由變元的代入規則——代入在公式的自由變元出現的每一處進行且該代入變元不允許在式中以任何約束形式出現。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）＝yx（P（x,y）xyP（x,y）＝yx（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)有三部分組成：

基本等式

推理規則——代入規則與替換規則

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

前提

證明——推理規則與證明過程

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

推理規則：——ＵＳ規則——ＵＧ規則——ＥＳ規則——ＥＧ規則

證明規則：——Ｐ規則——Ｔ規則——ＣＰ規則85

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

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

公理系統的組成與推理

公理系統的討論：

不矛盾性

完整性

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

命題：P1，P2，…，Pn；

命題聯結詞：，∨，∧，，；

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

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

函數：f，g，h；

謂詞：，；

括號：（，）

88

項：

①

個體常量是項；

②個體變量是項；

③

f是n元函數，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）推理規則分離規則：PQ，P├Q。

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

94

①Pi是公理；

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

B。

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

①Ｐi是假設前提；

②Ｐi是公理；

③Ｐi是由Ｐk，Pr用分離規則而得

最后。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用分離規則而得。最后Pn=P∧P，而此時：A1→(A2→(…(An→B））…）為定理。97

（23）謂詞邏輯永真公理系統

1．系統組成部分

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）推理規則

①分離規則：PQ，