離散數(shù)學(xué)西北大學(xué)

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

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

離散性

能行性

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

數(shù)理邏輯

集合論

代數(shù)系統(tǒng)

圖論2第一篇數(shù)理邏輯

數(shù)理邏輯是用數(shù)學(xué)方法研究形式邏輯演繹推理規(guī)則的科學(xué)，它是一門(mén)數(shù)學(xué)，是一門(mén)研究演繹推理規(guī)則的數(shù)學(xué)，在學(xué)習(xí)此部分時(shí)，主要要掌握如下幾個(gè)要點(diǎn)：①思維的形式化②指派法③公式推理④公理系統(tǒng)⑤范式⑥自動(dòng)定理證明3

本篇由命題邏輯、謂詞邏輯、公理化理論及非經(jīng)典邏輯等四部分組成，其中命題邏輯以命題為研究對(duì)象而謂詞邏輯則以謂詞為研究對(duì)象，而公理化理論則是數(shù)理邏輯中演繹推理的形式化思想的介紹，最后非經(jīng)典邏輯則介紹若干種計(jì)算機(jī)科學(xué)中常用的一些特殊形式邏輯，以上四部分有機(jī)結(jié)合構(gòu)成完整的整體。4§1.4命題邏輯基本等式（6）命題邏輯42個(gè)基本等式。交換律

P∨Q＝Q∨P；

P∧Q＝Q∧P；

P

Q＝Q

P．結(jié)合律（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）；5否定深入

P＝P；

（P∧Q）＝

P∨

Q；

（P∨Q）＝

P∧

Q；

（P

Q）＝P∧

Q；(14)

（P

Q）＝

P

Q＝P

Q；變?cè)韧琍∧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；6常值與變?cè)穆?lián)結(jié)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；7聯(lián)結(jié)詞化歸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）＝P8§1.5對(duì)偶定理（7）對(duì)偶公式定義（8）對(duì)偶公式性質(zhì)：一個(gè)等式成立其對(duì)偶等式也成立9§1.6命題邏輯基本蘊(yùn)含式及推理規(guī)則（9）19個(gè)基本蘊(yùn)含重言式

P∧Q

P；

P∧Q

Q；

P

P∨Q；

Q

P∨Q；

P

P

Q；

Q

P

Q；

（P

Q）

P；

（P

Q）

Q；10

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))．11

（10）11個(gè)推理規(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；12§1.7范式（11）范式——命題公式的一種標(biāo)準(zhǔn)形式（12）特異析取范式：該范式是一個(gè)析取式，每個(gè)析取項(xiàng)是所有命題變?cè)狡浞穸ǖ暮先∈?。?3）特異合取范式：該范式是一個(gè)合取式，每個(gè)析取項(xiàng)是所有命題變?cè)狡浞穸ǖ奈鋈∈健?3§1.8命題聯(lián)結(jié)詞的擴(kuò)充與歸約（13）命題聯(lián)結(jié)詞的擴(kuò)充——異或：

、與非：、或非：

、蘊(yùn)含否定：C

（14）命題聯(lián)結(jié)詞的歸約命題聯(lián)結(jié)詞可歸約為如下形式之一：

{

,

}

{

,

}

{

}

{

}14第二章謂詞邏輯

§2.1謂詞與個(gè)體（1）個(gè)體

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

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

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

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

n元謂詞——刻劃n個(gè)個(gè)體間關(guān)系15量詞（3）存在量詞：

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

xP(x)——“所有”之語(yǔ)義（5）量詞的轄域——量詞所作用的范圍函數(shù)（6）函數(shù)——個(gè)體間的特定關(guān)系稱(chēng)函數(shù)，它是個(gè)體間的映射。

f(x)中X是個(gè)體而f為函數(shù)符號(hào)，f(x)為函數(shù)。16§2.2謂詞邏輯公式（7）謂詞邏輯公式

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

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

公式：

原子公式是公式；

A，B是公式，則（

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

B），（A

B）是公式；

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

x）A，（

x）A為公式；

公式由且僅由有限次使用前面三步而得。17§2.3自由變?cè)c約束變?cè)?）謂詞公式中的自由變?cè)c約束變?cè)?/p>

謂詞公式中的自由變?cè)c約束變?cè)?/p>

約束變?cè)母拿?guī)則——改名在量詞變?cè)捌漭犛蛑性撟冊(cè)募s束出現(xiàn)處進(jìn)行且該變?cè)辉诹吭~轄域內(nèi)出現(xiàn)過(guò)。

自由變?cè)拇胍?guī)則——代入在公式的自由變?cè)霈F(xiàn)的每一處進(jìn)行且該代入變?cè)辉试S在式中以任何約束形式出現(xiàn)。18

§2.4謂詞邏輯永真公式（9）謂詞邏輯永真公式定義謂詞公式的解釋與賦值（10）謂詞邏輯永真公式定義——公式在所有解釋下對(duì)所有賦值均為真（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）19

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）20（12）謂詞邏輯的蘊(yùn)含永真公式

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）21§2.5范式（13）前束范式——公式的所有量詞均非否定的出現(xiàn)在公式最前面，它的轄域一直延伸至公式末尾，且公式中不出現(xiàn)

與

。（14）斯科林范式——前束范式的首標(biāo)處僅出現(xiàn)全稱(chēng)量詞且公式中不出現(xiàn)自由變?cè)?/p>

x1

x2…

xnM（x1,x2,…,xn）22命題邏輯與謂詞邏輯的公理化理論（16）公理系統(tǒng)的組成

命題：P1，P2，…，Pn；

命題聯(lián)結(jié)詞：

，∨，∧，

，

；

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

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

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

謂詞：

，

；

括號(hào)：（，）

23

項(xiàng)：①

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

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

24

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

P是公式則（

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

Q），（P

Q）是公式；④

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

謂詞邏輯公式：①原子公式是公式；②A，B是公式則：（

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

B）,（A

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

x）A，（

x）B是公式；④公式由且僅由有限次使用①、②、③而得。26

（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）；

27⑦（P

Q）（Q

P）

（P

Q））；⑧P∧Q

Q；⑨P∧Q

P；⑩P

（Q

P∧Q）；

P

P∨Q；

Q

P∨Q；（Q

P）

（（R

P）

（Q∨R

P））；（P

Q）

（Q

P）；

P

P；282）推理規(guī)則分離規(guī)則：P

Q，P

Q。

3）證明（過(guò)程）與定理證明（過(guò)程）給出了公理系統(tǒng)中定理生成的過(guò)程，它是一個(gè)公式序列：P1，P2，…，Pn，其中每個(gè)Pi（i＝1，2，…，n）必須滿足下條件之一。29①Pi是公理；②Pi是由Pk，Pr，（k，r<i）施行分離規(guī)則而得。最后，Pn＝Q即為定理。（18）導(dǎo)出規(guī)則——如有A

B為定理則必有A

B。（19）推理定理——設(shè)有設(shè)有A1，A2，…，An

B，則必有：A1,A2,…An-1

An

B。

30

（20）謂詞邏輯公理系統(tǒng)

1．系統(tǒng)組成部分可見(jiàn)（16）

2．推理部分

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

31①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）．⑦（P

Q）

（（Q

P）

（P

Q））．⑧P∧Q

Q．32⑨P∧Q

P．⑩P

（Q

P∧Q）．

P

P∨Q．

Q

P∨Q．（Q

P）

（（R

P）

（Q∨R

P））．（P

Q）

（Q

P）．

P

P．

xP（x）

P（x）．

P（x）

xP（x）。11121314151617332）推理規(guī)則①分離規(guī)則：P

Q，P

Q.②全稱(chēng)規(guī)規(guī)：Q

P（x）

Q

xP（x）．③存在規(guī)則：P（x）

Q

xP（x）

Q．上面17個(gè)公理與3個(gè)規(guī)則中有15個(gè)公理與1個(gè)規(guī)則是命題邏輯公理系統(tǒng)的，真正屬謂詞邏輯的僅有2個(gè)公理與2個(gè)規(guī)則。

343）證明（過(guò)程）與定理。證明（過(guò)程）是一個(gè)公式序列：P1，P2，…，Pn，其中每個(gè)Pi（i＝1，2，…，n）必須滿足下條件之一：①Pi是公理；②Pi是由Pk，Pr，（k，r<i）施行分離規(guī)則而得；③Pi是由Pk（k<i）施行全稱(chēng)規(guī)則而得；④Pi是由Pk（k<i）施行存在規(guī)則而得。最后，Pn＝Q即為定理。35（21）謂詞邏輯中四個(gè)重要的推理規(guī)則

全稱(chēng)指定規(guī)則：US

xP（x）＝＞

P