離散數學導論（第三版）

電子教案

徐潔磐1第1頁第一篇緒言

本篇是對離散數學宏觀介紹。1．計算機科學與離散數學介紹離散數學在計算機科學發(fā)展中作用與關系，明確離散數學是掌握與研究計算機科學基礎理論與工具。2．離散數學特征

離散性

能行性3．離散數學內容離散數學主要內容為：

集合論

代數結構

圖論

數理邏輯2第2頁第二篇集合論

本篇由集合論初步、關系、函數、有限集與無限集等與集合論相關等四部分內容組成，它們間是一個內容關聯整體。3第3頁第一章集合論初步集合論是數學基礎，也是離散數學基礎。故學好集合論十分主要，在本章學習中要掌握：

集合中一個基本概念

集合中兩種關系

集合中三種特殊集合

集合中四種表示方法

集合中五種運算

集合中21個慣用公式4第4頁

§1.1集合論基本概念

（1）

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

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

B，A

B。

集合與元素間隸屬關系：a

A，a

A。（3）三種特殊集合

空集

全集E

冪集

（A）。5第5頁（4）集合四種表示法：

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

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

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

運算法。即用已知集合運算結構新集合。例：S＝A∪（B∩C）AAB6第6頁（5）集合五種運算：

交運算：A∩B

倂運算：A∪B

差運算：A－B

補運算：～A

對稱差運算：A＋B7第7頁（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）8第8頁同一律：A∪

＝AA∩E＝A零一律：A∪E＝EA∩

＝

互補律：A∪～A＝EA∩～A＝

雙補律：～（～A）＝A9第9頁E與

互補：～E＝

～

＝E等冪律：A∪A＝AA∩A＝A吸收律：A∪（A∩B）＝AA∩（A∪B）＝A狄·莫根定律：～（A∪B）＝～A∩～B～（A∩B）＝～A∪～B10第10頁§1.2冪集、n元有序組與笛卡爾乘積

（7）冪集冪集定義：集合A全部子集所組成集合，可記為（A）。冪集性質：|A|＝n則|(A)|＝2n

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

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

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

基本運算：笛卡爾乘積。例：AB12第12頁第二章關系關系研究集合內元素間關聯及集合間元素關聯，主要有：

一個基本概念

兩種表示方法

三種運算

九個公式

五種性質

六種慣用關系13第13頁§2.1關系基本概念

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

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

集合表示法：有序偶集合

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

關系復合運算

關系逆運算（4）相關運算五個公式：復合運算公式：(RS)T＝R(S

T)Rm

Rn＝Rm+n(Rm)n＝Rm

n

逆運算公式：R＝R(R

S)＝R

S

～～～15第15頁§2.3關系主要性質

（5）關系五種性質

關系自反性

關系反自反性

關系對稱性

關系反對稱性

關系傳遞性16第16頁（6）六種慣用關系

次序關系之一：偏序關系

次序關系之二：擬序關系

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

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

相容關系

等價關系17第17頁§2.4閉包運算（1）關系閉包運算自反閉包r(R)對稱閉包s(R）傳遞閉包t(R）（2）閉包公式：r（R）＝R∪

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

～i=1

18第18頁

§2.5次序關系（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

.19第19頁（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。

20第20頁

四個次序關系間關系：

R是擬序則r(R)=RR是偏序則R－Q是擬序字典次序關系必為線性次序關系R是擬序則必反對稱

八個概念：

最大元素（最小元素）

極大元素（極小元素）

上界（下界）

上確界（下確界）21第21頁

§2.6相容關系（8）相容關系

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

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

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

22第22頁§2.7等價關系（9）等價關系

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

等價類——R是X上等價關系，對x

X可結構一個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。23第23頁第三章函數函數是一個特殊關系，它在數學中含有普遍主要價值，函數主要內容有：

一個基本概念兩種基本運算三種性質函數四種慣用函數24第24頁

§3.1函數基本概念

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

函數建立了從一個集合到另一個集合特殊對應關系。設有集合X與Y，假如我們有一個對應關系f，使X任一元素x能與y中一個唯一元素y相對應，則這個對應關系f叫從X到Y函數或叫從X到Y映射。x所對應y內元素y叫x像，而x則叫y像源。上述函數我們能夠表示成f：X

Y；或寫成X

Y；以及y＝f（x）。（2）三種不一樣性質函數：

滿射與內射

一對一與多對一

一一對應（雙射）25第25頁y1y2y3y4

x1x2x3x4

y1y2y3y4

x1x2x3x4x5y1y2y3y4

x1x2x3x4

XYgXYfXYh26第26頁

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

27第27頁

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

（3）兩種運算：

復合運算（復合函數）設函數f：X

Y，g：Y

Z則復合函數h＝gf：X

Z是一個新函數。定義：設函數f：X

Y，g：Y

Z，它們所組成復合函數或叫復合映射gf，也是一個函數h：X

Z，即：h＝g

f：{(x,z)|x

X,z

Z且最少存在一個y

Y，有y=f（x），z＝g（y）}．28第28頁

y1y2x1x2x3

z1z2YXZhfg29第29頁

逆運算（反函數）定義：設f：X

Y是—一對應函數，則f所組成逆關系叫f逆映射或叫f反函數，記以f—1：Y

X（4）函數分類：

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

§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’

31第31頁第四章有限集與無限集§4.1有限集與無限集基本概念（1）有限集與無限集基本概念

有限集兩個定義

集合S與Nn一一對應

非無限集即為有限集

無限集兩個定義

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

S存在與其等勢真子集32第32頁

§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－133第33頁

§4.3無限集（3）四個慣用無限集：

自然數集N

整數集I

有理數集Q

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

0整數集無限集實數集——基數為

有理數集更大基數集——

（A）34第34頁第三篇代數系統(tǒng)代數系統(tǒng)是建立在集合論基礎上以代數運算為研究對象學科。本篇共三章，第五章代數系統(tǒng)基礎介紹代數系統(tǒng)普通原理與性質，

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

§5.1代數系統(tǒng)普通概念1．代數系統(tǒng)中基本概念（1）代數系統(tǒng)：集合上含有封閉性運算組成代數系統(tǒng)（S,

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

），（S

，

）滿足：

①S

S

②如a,b

S

，a

b=a

b則稱（S

，

）為（S,）子代數。36第36頁§5.2代數系統(tǒng)常見一些性質（3）代數系統(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＝07）生成元37第37頁

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

）與（Y，

）存在一一對應函數g:X

Y使得如x1,x2

X，則有：g（x1

x2）＝g（x1）

g（x2）此時則稱（X,

）與（Y，

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

）與（Y，

）存在函數g:X

Y使得如x1,x2

X，則有：g（x1

x2）＝g（x1）

g（x2）此時則稱（X，

）與（Y，

）同態(tài)。

§5.4慣用代數系統(tǒng)（6）代數系統(tǒng)組成38第38頁（一個二元運算

）兩個運算有逆元兩個運算有單位元代數系統(tǒng)結合律半群單位元、逆元群

循環(huán)群

可換群

變換群

子群

循環(huán)半群

單元半群

可換半群

整環(huán)

域

商環(huán)

理想

有補格

有界格

布爾代數

正規(guī)子群、商群特殊環(huán)特殊子環(huán)兩個運算單位元、逆元（兩個二元運算：,)兩個運算結合律、交換律、吸收律格兩個運算分配律分配格單位元，無零因子（兩個二元運算：,)可換群,半群,對分配群

環(huán)

交換律

可換環(huán)

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

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

所組成代數系統(tǒng)（E（A）,

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

）中S為有限集。（14）子群：群（G，

）上G子集所組成群。40第40頁（15）正規(guī)子群：（H，

）是群（G，

）子群，如對a

G都有：aH=Ha則稱（H，

）是（G，

）正規(guī)子群。（16）陪集：H是G子群，Ha＝{ha|h

H},aH={ah|h

H}分別稱H在G中一個右陪集或左陪集。（17）商群：H是G正規(guī)子群，對Ha，Hb

G/H，二元運算（Ha)

(Hb)＝Hab組成群，則稱H是G商群。（18）單元半群性質：

單元半群子系統(tǒng)若包含單位元也是單元半群。可列個元素單元半群運算組合表每行（列）均不相同。循環(huán)單元半群是可換單元半群?？蓳Q單元半群全部等冪元素是一個子單元半群。41第41頁§6.2一些群理論與半群性質：半群子代數也是半群。循環(huán)半群是可換半群。（19）關于群基本理論群方程可解性：a

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

群消去律：a

b=a

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

任一群必與變換群同構；

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

H則a

b

H,a

H則a－1

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

H則ab－1

H；一個有限群階一定被它子群階所等分（拉格朗日定理）；f是群（G,）與（G，）滿同態(tài)，K是f核，則必有：（G/k,）與（G，）同構；43第43頁第七章其它代數系統(tǒng)§7.1環(huán)、理想、整環(huán)和域（20）環(huán)：（R，＋,

），對＋可換群，對

半群，

對＋分配律；（21）理想：（D，＋,

），環(huán)（R，＋,

）子環(huán)，滿足：a

R,b

D，必有：a

b

D,ba

D；（22）整環(huán)：環(huán)（R，＋,

）中，運算

有單位元，無零因子；（23）域：環(huán)（P，＋,）中，運算

交換律，有單位元，逆元；

44第44頁（24）環(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)充要條件是a

s則必有a－1

S。（25）域基本理論1）域是整環(huán)；2）有限整環(huán)必是域。45第45頁§7.2格與布爾代數（26）格：（P，＋,

）中，兩個運算結合律、吸收律、交換律；（27）布爾代數：格（B，＋,

）中，兩個運算分配律、單位元、逆元。46第46頁（28）格基本理論1）一個偏序格必是一個代數格，反之亦然；2）格運算性質。

a≤a∨b,b≤a∨b（a∨b≥a,a∨b≥b）

a≤c且b≤c

a∨b≤c（a≤c且b≤c

c≥a∨b）

a∧b≤a,a∧b≤b（a≥a∧b,b≥a∧b）

c≤a且c≤b

c≤a∧b（c≤a且c≤b

c≥a∧b≥c）47第47頁（29）布爾代數基本理論—布爾代數（B，＋，）滿足：（對＋與

）

交換律

結合律

等冪律

吸收律

分配律

零一律

同一律

互補律

雙補律

德

摩根律48第48頁第四篇圖論

圖論用‘結點’表示事物，而用‘邊’表示事物間聯絡，并用‘結點’與‘邊’所組成圖用以研究客觀世界。為便于計算，建立了圖矩陣表示，這么能夠將圖論研究與計算相結合，從而使圖論研究含有很大實用性。因為圖形式很多，在實用中我們普通對若干種慣用圖作研究，它們是樹、平面圖與兩步圖。在圖論學習中主要要掌握以下幾個方面：49第49頁①圖論中基本概念。②圖論中基礎理論。③圖矩陣計算。④幾個慣用圖。在本篇中共有兩部分組成，它們是圖論原理與慣用圖，其中圖論原理部分介紹圖基本概念、理論與計算而慣用圖部分則介紹樹、平面圖與兩步圖等三種慣用圖，這兩部分有機結合組成了圖論完整整體。50第50頁第八章圖論原理

§8.1圖基本概念§8.1.1圖§8.1.2圖基本概念（1）圖概念圖由結點集V＝{v1，v2，…，vn}與邊集E＝{l1，l2，…，lm}所組成，可記為：G＝<V，E>（2）有向圖與無向圖①邊為有向圖稱為有向圖②邊為無向圖稱為無向圖51第51頁（3）幾個特殊圖①零圖：無邊圖。②平凡圖：僅有一個結點所組成圖。③完全圖：各結點間都有邊相聯圖。④補圖：G＝<V，E>，G

＝<V，E

>如有＝<V，E∪E

>為完全圖且E∩E

＝

，則稱G為G補圖。⑤簡單圖與多重圖：包含多重邊圖稱為多重圖，不然稱為簡單圖。⑥有權圖：邊帶權圖。52第52頁

§8.1.3圖同構⑦同構圖：G＝<V，E>，G

＝<V

，E

>，V與V

以及對應邊結點對中有一一對應關系?！?.1.4圖中結點次數（4）圖中結點次數

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

定理：deg（vi）=2m

53第53頁§8.2通路、回路與連通性（5）通路與回路①通路：圖中vi至vj通路是在邊序列：（vi，vi1），（vi1，vi2），…（vik－1，vik），其中vik＝vj②基本通路與簡單通路：圖各邊全不一樣通路叫簡單通路，各點全不一樣通路叫基本通路。③環(huán)與回路：邊始點與終點相同稱環(huán)，通路起始點與終止點相同稱回路。④簡單回路與基本回路：簡單（基本）通路起始點與終止點相同稱簡單（基本）回路。⑤有向圖（n,m）基本通路長度≤n－1，基本回路長度≤n。54第54頁（6）圖連通性①圖可達性：圖結點vi到vj間存在通路則稱從vi到vj是可達。②連通圖：圖任何兩結點間均可達。③三種連通圖：

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

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

單向連通：有向圖兩結點間最少有一向是可達則稱單向連通。55第55頁

§8.3歐拉圖（7）歐拉圖

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

每個結點次數為偶數。由vi到vj歐拉通路

vi，vj結點次數為奇數，其它結點次數為偶數。56第56頁§8.4漢密爾頓圖（8）漢密爾頓圖

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

漢密爾頓圖與漢密爾頓通路中定理漢密爾頓圖必要條件G＝<V,E>中V1

V且P（G－V1）≤|V1|，其中P（G－V1）為從G中刪除V1（包含V1中各結點及其關聯邊）后所得到連通分支數。漢密爾頓圖充分條件：G＝<V,E>無向簡單圖，|V|≥3，G中每結點對次數之和≥|V|。漢密爾頓通路：有向圖D＝<V,E>，|V|≥2全部有向邊均用無向邊替換后得無向圖含生成子圖Kn。57第57頁§8.5圖矩陣表示法（9）圖鄰接矩陣：G＝<V,E>為（n，m）圖，其鄰接矩陣：A＝（aij）n×n.

1（vi，vj）

Eaij＝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）連通性計算：可達性矩陣除對角線元素外均為158第58頁第九章慣用圖§9.1樹§9.1.1樹基本性質（13）樹基本概念與屬性①樹：不含回路連通圖。（n,m）樹中必有m＝n－1②樹性質T為樹

兩結點間只有一條通路?！?.1.2有向樹（14）有向樹

59第59頁（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時稱二元樹或二元完全樹?！?.1.4生成樹（17）生成樹：連通圖G＝<V,E>生成樹TG＝<V

,E

>G子圖，且是樹并滿足V

＝V，E

E。

生成樹尋找算法：在G中尋找基本回路，尋到后刪除邊，并繼續(xù)尋找，直到無基本回路出現為止。60第60頁§9.2平面圖§9.2.1平面圖基本概念

（18）平面圖概念：圖邊間可不出現交叉稱為平面圖?！?.2.2平面圖區(qū)域

（n，m）連通平面圖，區(qū)域數為r，必有：n－m＋r＝2。

（19）平面圖區(qū)域性質

（n，m）連通平面圖，且無環(huán)，邊大于1，必有：m≤3n－6。§9.2.3判別平面圖庫拉托夫斯基定理（20）平面圖判別法（庫拉托夫斯基定理）：圖任何子圖都不可能減縮成下面兩個圖：61第61頁§9.3兩步圖（21）兩步圖概念：無向圖G＝<V,E>，有V1，V2

V，V1∩V2＝

，G中每一邊e都有：e＝（vi，vj），vi

V1，vj

V2，則稱G為兩步圖。（22）兩步圖判別法：圖全部回路長度為偶數。62第62頁第五篇數理邏輯

數理邏輯是用數學方法研究形式邏輯演繹推理規(guī)則科學，它是一門數學，是一門研究演繹推理規(guī)則數學，在學習此部分時，主要要掌握以下幾個關鍵點：①思維形式化②指派法③公式推理④公理系統(tǒng)⑤范式⑥自動定理證實

63第63頁本篇由命題邏輯、謂詞邏輯、公理化理論及非經典邏輯等四部分組成，其中命題邏輯以命題為研究對象而謂詞邏輯則以謂詞為研究對象，而公理化理論則是數理邏輯中演繹推理形式化思想介紹，最終非經典邏輯則介紹若干種計算機科學中慣用一些特殊形式邏輯，以上四部分有機結合組成完整整體。64第64頁第十章命題邏輯

命題邏輯以命題為對象，研究命題符號體系及推理規(guī)則?！?0.1命題與命題聯結詞（1）命題——能判別真假語句。（2）基本命題聯結詞——否定、而且、或者、蘊含、等價?！?0.2命題公式（3）命題公式——由命題及命題聯結詞組成命題公式?！?0.3重言式（4）指派——命題公式中變元一組確定值。（5）重言式——全部指派均取值為真公式。65第65頁§10.4命題邏輯基本等式（6）命題邏輯42個基本等式。交換律P∨Q＝Q∨P；P∧Q＝Q∧P；P

Q＝Q

P．結合律（P∨Q）∨R＝P∨（Q∨R）；（P∧Q）∧R＝P∧（Q∧R）；（P

Q）

R＝P

（Q

R）．分配律P∧（Q∨R）＝（P∧Q）∨（P∧R）；P∨（Q∧R）＝（P∨Q）∧（P∨R）；66第66頁否定深入

P＝P；

（P∧Q）＝

P∨

Q；

（P∨Q）＝

P∧

Q；

（P

Q）＝P∧

Q；(14)

（P

Q）＝

P

Q＝P

Q；變元等同P∧P＝P；P∨P＝P；P∧

P＝F；P∨

P＝T；P

P＝T；P

P＝

P；

P

P＝P；P

P＝T；P

P＝

P

P＝F；67第67頁常值與變元聯結T∧P＝P；F∧P＝F；T∨P＝T；F∨P＝F；T

P＝P；F

P＝T；P

T＝T；P

F＝

P；T

P＝P；F

P＝

P；68第68頁聯結詞化歸P∧Q＝

（

P∨

Q）；P∨Q＝

（

P∧

Q）；P

Q＝

P∨Q；P

Q＝（P

Q）∧（Q

P）其它P

Q＝

Q

P(P

Q)∧（P

R）＝P

Q∧RP∨（P∧Q）＝PP

（Q

R）＝P∧Q

RP∧（P∨Q）＝P69第69頁§10.5對偶定理（7）對偶公式定義（8）對偶公式性質：一個等式成立其對偶等式也成立70第70頁§10.6命題邏輯基本蘊含式及推理規(guī)則（9）19個基本蘊含重言式P∧Q

P；P∧Q

Q；P

P∨Q；Q

P∨Q；

P

P

Q；Q

P

Q；

（P

Q）

P；

（P

Q）

Q；71第71頁

P∧（P∨Q）

Q；

Q∧（P∨Q）

P；P∧（P

Q）

Q；

Q∧（P

Q）

P；(P

Q)∧(Q

R)

P

R；(P

Q)∧(R

S)

P∧R

Q∧S；(P∨Q)∧(P

R)∧(Q

R)

R；P(Q

P∧Q)；(P

Q)((Q

R)(P

R))；(P(Q

R))(Q(P

R))；(P

Q)((R

Q)(P∨R

Q))．72第72頁

（10）11個推理規(guī)則P，Q

P；P，Q

Q；P

P∨Q；Q

P∨Q；P，Q

P∧Q；

P，P∨Q

Q；P，P

Q

Q；

Q，PQ

P；P

Q，Q

R

P

R；P

Q，R

S

P∧R

Q∧S；P∨Q，P

R，Q

R

R；

73第73頁§10.7范式（11）范式——命題公式一個標準形式（12）特異析取范式：該范式是一個析取式，每個析取項是全部命題變元式其否定合取式。（13）特異合取范式：該范式是一個合取式，每個析取項是全部命題變元式其否定析取式。74第74頁§10.8命題聯結詞擴充與歸約（13）命題聯結詞擴充——異或：

、謝佛：

、魏泊：

、蘊含否定：（14）命題聯結詞歸約命題聯結詞可歸約為以下形式之一：

{

,

}

{

,

}

{

}

{

}75第75頁第十一章謂詞邏輯

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

個體常量與個體變量

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

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

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

n元謂詞——刻劃n個個體間關系76第76頁§11.2量詞（3）存在量詞：

xP(x)——“有一些”之語義（4）全稱量詞：

xP(x)——“全部”之語義（5）量詞轄域——量詞所作用范圍§11.3函數（6）函數——個體間特定關系稱函數，它是個體間映射。f(x)中X是個體而f為函數符號，f(x)為函數。77第77頁§11.4謂詞邏輯公式（7）謂詞邏輯公式

項：個體是項，函數是項

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

公式：

原子公式是公式；

A，B是公式，則（

A）,（A∨B）,（A∧B）,（A

B），（A

B）是公式；

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

xA），（

xA）為公式；

公式由且僅由有限次使用前面三步而得。78第78頁§11.5自由變元與約束變元（8）謂詞公式中自由變元與約束變元

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

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

自由變元代入規(guī)則——代入在公式自由變元出現每一處進行且該代入變元不允許在式中以任何約束形式出現。79第79頁

§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）80第80頁

xP（x）∨Q＝

x（P（x）∨Q）

xP（x）∧Q＝

x（P（x）∧Q）

x

yP（x,y）＝

y

x（P（x,y）

x

yP（x,y）＝

y

x（P（x,y）

xP（x）

Q＝

x（P（x）

Q）

xP（x）

Q＝

x（P（x）

Q）Q

xP（x）＝

x（Q

P（x））Q

xP（x）＝

x（Q

P（x））

x（P（x）∧Q（x））＝

x（P（x）∧

xQ（x）

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

x（P（x）∨

xQ（x）81第81頁（12）謂詞邏輯蘊含永真公式

x

yP（x,y）

y

x（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）82第82頁

§11.7范式（13）前束范式——公式全部量詞均非否定出現在公式最前面，它轄域一直延伸至公式末尾，且公式中不出現

與

。（14）斯科林范式——前束范式首標處僅出現全稱量詞且公式中不出現自由變元

x1

x2…

xnM（x1,x2,…,xn）83第83頁第十二章數理邏輯公理化理論

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

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

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

不矛盾性

完整性

獨立性84第84頁§12.2命題邏輯與謂詞邏輯公理化理論（16）公理系統(tǒng)組成

命題：P1，P2，…，Pn；

命題聯結詞：

，∨，∧，

，

；

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

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

函數：f，g，h；

謂詞：

，

；

括號：（，）

85第85頁項：①

個體常量是項；②個體變量是項；③

f是n元函數，t1，t2，…,tn是項，則f(t1，t2，…,tn)是項；④項由且僅由有限次使用①、②、③而得。

86第86頁原子公式：P是n元謂詞，t1，t2，…，tn是項，則P（t1，t2，…，tn)是原子公式。命題邏輯公式：①命題是公式；②

P是公式則（

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

Q），（P

Q）是公式；④

公式由且僅由有限次使用①，②，③而得。87第87頁謂詞邏輯公式：①原子公式是公式；②A，B是公式則：（

A），（A∨B），（A∧B），（A

B）,（A

B）是公式；③A是公式則（

xA），（

xB）是公式；④公式由且僅由有限次使用①、②、③而得。88第88頁（17）公理系統(tǒng)推理1）公理如P，Q，R為公式，則有下述公理：①P

P；②（P

（Q

R））

（Q

（P

R））；③（P

Q）

（（Q

R）

（P

R））；④（P

（P

Q））

（P

Q）；⑤（P

Q）

（P

Q）；⑥（P

Q）

（Q

P）；

89第89頁⑦（P

Q）（Q

P）

（P

Q））；⑧P∧Q

Q；⑨P∧Q

P；⑩P

（Q

P∧Q）；P

P