離散數(shù)學(xué)第一頁，共95頁。教材(jiàocái)及參考書(1)教材(jiàocái)耿素云，屈婉玲，張立昂：離散數(shù)學(xué)(第三版)，清華大學(xué)出版社第二頁，共95頁。教材(jiàocái)及參考書(2)參考書耿素云：離散數(shù)學(xué)(修訂版)，高等教育出版社屈婉玲，耿素云，張立昂：離散數(shù)學(xué)題解(tíjiě)（修訂版），清華大學(xué)出版社李盤林，李麗雙，李洋，王春立：離散數(shù)學(xué)，高等教育出版社第三頁，共95頁。學(xué)習(xuéxí)目的初步掌握現(xiàn)代數(shù)學(xué)的觀點和方法；初步掌握處理離散結(jié)構(gòu)和方法，提高計算機系統(tǒng)設(shè)計和程序設(shè)計的邏輯(luójí)數(shù)字的能力；初步掌握計算機在進行數(shù)的處理時的方法和計算；培養(yǎng)學(xué)習抽象思維和縝密思考的能力；第四頁，共95頁。首都師范大學(xué)教育(jiàoyù)技術(shù)系

離散數(shù)學(xué)第一章命題邏輯第五頁，共95頁。第一章

命題邏輯一、命題與聯(lián)結(jié)詞二、命題公式及其賦值三、等值式四、析取范式與合取范式五、聯(lián)結(jié)詞的完備集六、推理的形式(xíngshì)結(jié)構(gòu)七、自然推理系統(tǒng)P第六頁，共95頁。命題(mìngtí)與聯(lián)結(jié)詞一、命題(mìngtí)

定義：能判斷真假的陳述句，被稱為(chēnɡwéi)命題。

說明：命題的真值：作為命題所表達的判斷只有兩個結(jié)果：正確和錯誤，此結(jié)果稱為命題的真值。 命題是正確的，稱此命題的真值為真；命題是錯誤的，稱此命題的真值為假。

真值為真的命題稱為真命題

；真值為假的命題稱為假命題。

任何命題的真值都是唯一的。其它類型的句子，如疑問句、祈使句、感嘆句均沒有真假意義，因為均不是命題。

在數(shù)理邏輯中，命題的真值的真和假，有時分別用1和0來表達，也有時分別用T和F來表達。

第七頁，共95頁。命題(mìngtí)與聯(lián)結(jié)詞如何(rúhé)判斷命題：

首先(shǒuxiān)判斷其是否為陳述句其次判斷其是否有唯一真值例1：判斷下列句子是否為命題，真值如何？

（1）10是整數(shù)。（2）北京是我們祖國的首都。真命題

真命題

（3）雪是黑的。（4）x大于y。（5）向右看齊?。?）你吃飯了嗎？疑問句非命題

祈使句非命題

真值不唯一非命題

假命題第八頁，共95頁。命題(mìngtí)與聯(lián)結(jié)詞例1：判斷下列句子是否為命題(mìngtí)，真值如何？

（7）本命題(mìngtí)是假的。（8）我正在說謊。悖論非命題

悖論非命題

（9）2014年元旦是晴天。是命題真假未定第九頁，共95頁。命題(mìngtí)與聯(lián)結(jié)詞三、原子(yuánzǐ)命題（簡單命題）

定義：不能被分解(fēnjiě)為更簡單的命題的命題，稱為原子命題。

四、復(fù)合命題

定義：由若干個原子命題用命題聯(lián)結(jié)詞聯(lián)結(jié)而成的命題，稱為復(fù)合命題。

二、命題符號化

本書中用小寫字母p，q，r來表示命題。

例2:

p:10是整數(shù)。q：北京是我們祖國的首都。r:雪是黑的。第十頁，共95頁。命題(mìngtí)與聯(lián)結(jié)詞例3：判斷下列(xiàliè)命題是否為復(fù)合命題。

（1）5能被2整除(zhěngchú)。（2）2是素數(shù)當且僅當三角形有三條邊。原子命題

復(fù)合命題

（3）4是2的倍數(shù)或是3的倍數(shù)。復(fù)合命題（4）李明與王華是同學(xué)。原子命題（5）藍色和黃色可以調(diào)配成綠色。原子命題（6）2不是合數(shù)。復(fù)合命題第十一頁，共95頁。1.1命題(mìngtí)與聯(lián)結(jié)詞五、命題(mìngtí)聯(lián)結(jié)詞

否定(fǒudìng)符號：pp0110真值表：定義1.1：設(shè)p為命題，復(fù)合命題“非p”（或“p的否定”）稱為p的否定式，記作

p

，符號稱為否定聯(lián)結(jié)詞。規(guī)定

p為真當且僅當p為假。說明：是一元聯(lián)結(jié)詞

念作“等值”，表示該符號兩邊的兩個命題在任何情況下真值相同。

性質(zhì)：

pp第十二頁，共95頁。命題(mìngtí)與聯(lián)結(jié)詞合取符號(fúhào)：

定義1.2：設(shè)p，q為二命題，復(fù)合命題“p并且q”（或“p與q”）稱為(chēnɡwéi)p與q的合取式，記作pq，符號稱為(chēnɡwéi)合取聯(lián)結(jié)詞。并規(guī)定pq為真當且僅當p與q同時為真時為真。真值表：PQPQ000010100111注意：自然語言中的“既……，又……”，“不但……，而且……”，“雖然……，但是……”，“一面……，一面……”等聯(lián)結(jié)次可符號化為。不要見到“與”或“和”就使用聯(lián)結(jié)詞。第十三頁，共95頁。命題(mìngtí)與聯(lián)結(jié)詞例4：將下列(xiàliè)命題符號化。

（1）吳穎既用功(yònggōng)又聰明。（2）吳穎不僅用功而且聰明。（3）吳穎雖然聰明，但不用功。（4）張輝與王麗都是三好學(xué)生。（5）張輝與王麗是同學(xué)。p:吳穎用功。q:吳穎聰明。r:張輝是三好學(xué)生。s:王麗是三好學(xué)生。t:張輝與王麗是同學(xué)。pq

p

q

pqpq

s第十四頁，共95頁。命題(mìngtí)與聯(lián)結(jié)詞真值表：析取符號(fúhào)：

定義1.3：設(shè)p，q為二命題，復(fù)合(fùhé)命題“p或q”稱為p與q的析取式，記作pq，符號稱為析取聯(lián)結(jié)詞。并規(guī)定pq為假當且僅當p與q同事為假。PQPQ000011101111注意：自然語言中的“或”具有二義性，用它做聯(lián)結(jié)的命題有時具有相容性，有時具有排斥性，對應(yīng)的聯(lián)結(jié)詞分別稱為相容或和排斥或第十五頁，共95頁。命題(mìngtí)與聯(lián)結(jié)詞例5：將下列(xiàliè)命題符號化。

（1）張明正在睡覺(shuìjiào)或游泳。（2）李強是位排球隊員或是足球隊員。（3）他昨晚做了二十或三十道題。（4）張靜只能挑選202或203房間。或表示約數(shù)，不能用析取p:張明正在睡覺。q:張明正在游泳pq排斥或p:李強是位排球隊員。q:李強是位足球隊員

pq相容或p:張靜挑選202房間。q:張靜挑選203房間（

pq）（p

q）

p

q不正確第十六頁，共95頁。命題(mìngtí)與聯(lián)結(jié)詞蘊含(yùnhán)符號：

定義1.4：設(shè)p，q為二命題，復(fù)合命題“如果p，則q”稱為p與q的蘊含式，記作pq，并稱p是蘊含式的前件，q為蘊含式的后件，符號(fúhào)稱為蘊含聯(lián)結(jié)詞。并規(guī)定pq為假當且僅當p為真q為假。真值表：PQPQ001011100111pq的邏輯關(guān)系為q是p的必要條件

p是q的充分條件。第十七頁，共95頁。命題(mìngtí)與聯(lián)結(jié)詞注意(zhùyì)：蘊含(yùnhán)符號：在自然語言和數(shù)學(xué)中，有很多方式來描述蘊含，例如：“只要p，就q”，”因為p，所以q”，”p僅當q”，”只有q才p”，”除非q才p”，”除非q，否則非p”，q是p的必要條件，因而所用的聯(lián)結(jié)詞應(yīng)符號化為，各種描述方式都應(yīng)該符號化為pq。在自然語言中，“如果p，則q”中的前件p與后件q往往具有某種內(nèi)在聯(lián)系，而在數(shù)理邏輯中，p與q可以無任何內(nèi)在聯(lián)系。在數(shù)學(xué)或其它自然科學(xué)中，“如果p，則q”往往表達的是前件p為真，后件q也為真的推理。但在數(shù)理邏輯中，作為一種規(guī)定，當p為假時，無論q是真還是假，pq均為真，也就是說，只有p為真q為假這一種情況，使得復(fù)合命題pq為假。第十八頁，共95頁。命題(mìngtí)與聯(lián)結(jié)詞例6：將下列(xiàliè)命題符號化。

（1）只要(zhǐyào)不下雨，我就騎自行車上班。（2）只有不下雨，我才騎自行車上班。（3）若2+2=4，則太陽從東方升起。p:天下雨。q:我騎自行車上班。s:2+2=4。t:太陽從東方升起r:太陽從西方升起。（4）若2+24，則太陽從東方升起。（5）若2+2=4，則太陽從西方升起。（6）若2+24，則太陽從西方升起。

pqq

p

st

sr

sr

st第十九頁，共95頁。命題(mìngtí)與聯(lián)結(jié)詞等價(děngjià)符號：

定義1.5：設(shè)p，q為二命題，復(fù)合命題“p當且僅當q”稱為p與q的等價式，記作pq，符號(fúhào)稱為等價聯(lián)結(jié)詞。并規(guī)定pq為真當且僅當p與q同時為真或同時為假。

真值表：PQPQ001010100111pq的邏輯關(guān)系為q與p的互為充分必要條件。第二十頁，共95頁。命題(mìngtí)與聯(lián)結(jié)詞例7：將下列(xiàliè)命題符號化。

（1）2+2=4當且僅當3是奇數(shù)(jīshù)。（2）2+2=4當且僅當3不是奇數(shù)。p:2+2=4。q:3是奇數(shù)。（3）2+24當且僅當3是奇數(shù)。（4）2+24當且僅當3不是奇數(shù)。

pqp

qpqpq第二十一頁，共95頁。命題(mìngtí)與聯(lián)結(jié)詞說明(shuōmíng)

由聯(lián)結(jié)詞集｛｝中的一個聯(lián)結(jié)詞聯(lián)結(jié)一個或兩個原子命題組成的復(fù)合命題是簡單的復(fù)合命題，可以稱他們?yōu)榛镜膹?fù)合命題。多次使用聯(lián)結(jié)詞集中的聯(lián)結(jié)詞，可以組成更為復(fù)雜的復(fù)合命題。求復(fù)雜復(fù)合命題的真值時，還要規(guī)定聯(lián)結(jié)詞的先后順序。將括號也算在內(nèi)，這個順序為，對同一優(yōu)先級的聯(lián)結(jié)詞，先出現(xiàn)者先運算。我們只關(guān)心復(fù)合命題(mìngtí)中命題(mìngtí)之間的真值關(guān)系，而不關(guān)心命題(mìngtí)的內(nèi)容。例如:(((P∧Q)∨R)→((R∨P)∨Q))可寫成:(P∧Q∨R)→R∨P∨Q

但有時為了看起來清楚醒目,也可以保留某些原可省去的括號。第二十二頁，共95頁。例8將下列命題符號化設(shè)P表示“他有理論知識”,Q表示“他有實踐經(jīng)驗”,則“他既有理論知識又有實踐經(jīng)驗”可譯為:。設(shè)P:明天下雨,Q:明天下雪,R:我去學(xué)校。則(i)“如果(rúguǒ)明天不是雨夾雪則我去學(xué)?！笨蓪懗?(ii)“如果(rúguǒ)明天不下雨并且不下雪則我去學(xué)校”可寫成;(iii)“如果(rúguǒ)明天下雨或下雪則我不去學(xué)?！笨蓪懗?(iv)“當且僅當明天不下雪并且不下雨時我才去學(xué)校;命題(mìngtí)與聯(lián)結(jié)詞第二十三頁，共95頁。命題(mìngtí)與聯(lián)結(jié)詞例9：求式子(shìzi)的真值。

p:0q:0r:0p:1q:0r:1p:0q:1r:0第二十四頁，共95頁。第一章

命題邏輯一、命題與聯(lián)結(jié)詞二、命題公式及其賦值三、等值式四、析取范式與合取范式五、聯(lián)結(jié)詞的完備集六、推理的形式結(jié)構(gòu)七、自然(zìrán)推理系統(tǒng)P第二十五頁，共95頁。等值式一、等值

定義(dìngyì)2.1注意(zhùyì) 設(shè)A、B是兩個命題公式(gōngshì)，若A，B構(gòu)成的等價式AB為重言式，則稱A與B是等值的，記作AB。不是聯(lián)結(jié)符，它是用來說明A與B的等值，要與區(qū)分清楚。如何判斷兩個命題公式是否等值？方法一：通過真值表比較在各相同賦值情況下，真值是否相同。方法二：將A，B構(gòu)成AB等價式，判斷其是否為重言式。第二十六頁，共95頁。等值式例1：判斷下面兩個(liǎnɡɡè)公式是否等值：

(pq)PQ

000010100111

01010111

pq

(pq)

(pq)(pq)pq第二十七頁，共95頁。等值式例2：判斷(pànduàn)下面公式是否等值：

(pq)(pq)qpq

000010100111

00001101(pq)(pq)(pq)(pq)第二十八頁，共95頁。等值式

pqr

000111001111

010111011111100

001101

001110

00111111

1((pq)(pr))(p(qr))((pq)(pr))(p(qr))((pq)(pr))(p(qr))第二十九頁，共95頁。等值式二、16組重要(zhòngyào)的等值式

雙重(shuāngchóng)否定AA等冪律AAA AAA 交換(jiāohuàn)率 ABBA ABBA分配律 (AB)C(AC)(BC) (AB)C(AC)(BC)結(jié)合律 (AB)CA(BC) (AB)CA(BC)第三十頁，共95頁。等值式吸收(xīshōu)律 A(AB)A A(AB)A德摩根律

(AB)AB (AB)AB

零律 A11 A00 同一律A0A A1A排中律 AA1第三十一頁，共95頁。等值式矛盾律 A0蘊涵(yùnhán)等值式 AAB等價(děngjià)等值式 AB(AB)(BA) 假言(jiǎyán)易位 ABBA等價否定等值式ABAB

歸謬論 (AB)(AB)A

第三十二頁，共95頁。等值式注意(zhùyì)： 以上的16組等值式都是用元語言符號書寫的，稱這樣的等值式為等值式模式?？梢?kěyǐ)將這些元語言符號用具體的命題公式代替，則這些具體命題公式被稱為等值式模式的代入實例。第三十三頁，共95頁。等值式三、等值演算(yǎnsuàn)定義(dìngyì)等值演算(yǎnsuàn)規(guī)則

由已知等值式推演出另外一些等值式的過程為等值演算。

置換規(guī)則設(shè)(A)是含公式A的命題公式，(B)是用公式B置換了(A)中所有的A后得到的命題公式，若A

B，則(A)(B)第三十四頁，共95頁。等值式等值演算(yǎnsuàn)的用途（1）證明(zhèngmíng)等值式

例3：用等值演算法驗證(yànzhèng)等值式：

(pq)r(pr)(qr)

(pq)((pq)(pq))

第三十五頁，共95頁。等值式(pq)r(pr)(qr)

方法(fāngfǎ)一：（pq)r(pq)r(pq)r(pr)(qr)(pr)(qr)

方法(fāngfǎ)二：(pr)(qr)(pr)(qr)(pq)r(pq)r(pq)r

第三十六頁，共95頁。等值式(pq)((pq)(pq))

(pq)((pq)(qp))((pq)(qp))(pq)(qp)(pq)(qp)(pq)(qq)(pp)(qp)(pq)(qp)(pq)(pq)

第三十七頁，共95頁。等值式（2）判斷命題公式(gōngshì)的類型

例4：判斷下列(xiàliè)公式的類型：

((pq)p)

((pq)(qp))(pq)

(pq)(qp)

第三十八頁，共95頁。等值式((pq)p)

((pq)p)((pq)p)(pq)p(pq)q0q0永假式(矛盾(máodùn)式)第三十九頁，共95頁。等值式((pq)(qp))(pq)

((pq)(qp))(pq)(pq)(pq)1永真式(重言式)第四十頁，共95頁。等值式(pq)(qp)

(pq)(qp)(pq)(qp)(pq)(pq)(pq)(pq)(ppq)(qpq)pq可滿足(mǎnzú)式第四十一頁，共95頁。等值式（3）等值演算方法(fāngfǎ)還可以幫助人們解決現(xiàn)實生活中的一些判斷問題

第四十二頁，共95頁。等值式例5：用等值演算法解決(jiějué)下面問題。

A、B、C、D4人做百米競賽，觀眾甲、乙、丙預(yù)報比賽的名次為： 甲：C第一，B第二； 乙：C第二，D第三； 丙：A第二，D第四。 比賽結(jié)束后發(fā)現(xiàn)甲、乙、丙每人報告(bàogào)的情況都是各對一半，試問實際名次如何（假設(shè)并無并列者）？

第四十三頁，共95頁。等值式 甲：C第一，B第二(dìèr)； 乙：C第二(dìèr)，D第三； 丙：A第二(dìèr)，D第四。

1)(r1q2)(r1q2)1

pi:A第i qi:B第i ri:C第i si:D第i2)(r2s3)(r2s3)1

3)(p2s4)(p2s4)1

第四十四頁，共95頁。等值式其中(qízhōng)： r1q2r2s3中C不可能既得第一名，又得第二名；r1q2r2s3中B、C不能同時為第二名；

1)2)1((r1q2)(r1q2))((r2s3)(r2s3))(r1q2r2s3)(r1q2r2s3)(r1q2r2s3)(r1q2r2s3)

4):1)2)(r1q2r2s3)(r1q2r2s3)1第四十五頁，共95頁。等值式第三名第一名、第四名、第二名、所以：DCB

A1)()()()()())()(())()(()4)31322142322142322142322142322142322132214242?ù?ù?ùù?ù?ù?ùù?ùù?úù?ù?ùùù?úù?ùù?ù?ùúù?ù?ùù?ù?ù?ùù?úù?ù?ùùù?ú?ù?ù?srqrspsrqrspsrqrspsrqrspsrqrspsrqrsrqrspsp第四十六頁，共95頁。第一章

命題邏輯一、命題(mìngtí)與聯(lián)結(jié)詞二、命題(mìngtí)公式及其賦值三、等值式四、析取范式與合取范式五、聯(lián)結(jié)詞的完備集六、推理的形式結(jié)構(gòu)七、自然推理系統(tǒng)P第四十七頁，共95頁。析取范式與合取范式一、簡單(jiǎndān)析取式、簡單(jiǎndān)合取式

定義(dìngyì)1.18注意(zhùyì)

命題變項及其否定統(tǒng)稱作文字。僅由有限個文字構(gòu)成的析取式稱作簡單析取式。僅由有限個文字構(gòu)成的合取式稱作簡單合取式。

一個文字既是簡單析取式，又是簡單合取式。

定理

（1）一個簡單析取式是重言式當且僅當它同時含某個命題變項及它的否定式。

（2）一個簡單合取式是矛盾式當且僅當它同時含有某個命題變項及它的否定式。

第四十八頁，共95頁。例1：判斷下面公式哪些(nǎxiē)是簡單析取式，哪些(nǎxiē)是簡單合取式：

析取范式與合取范式(pq)

ppr

pq

ppr

pqr

pqr

p第四十九頁，共95頁。二、析取范式、合取范式

定義(dìngyì)1.19 （1）由有限個簡單合取式構(gòu)成(gòuchéng)的析取式被稱為析取范式。

（2）由有限(yǒuxiàn)個簡單析取式構(gòu)成的合取式被稱為合取范式。

（3）析取范式與合取范式統(tǒng)稱為范式。

析取范式與合取范式第五十頁，共95頁。例2：判斷下面(xiàmian)公式哪些是析取式范式，哪些是合取范式：

注意：

（1）簡單析取式既是析取范式，也是合取范式；

（2）簡單合取式既是合取范式，也是析取范式；

析取范式與合取范式(pq)(pq)(pq)(pr)prpqpqrp第五十一頁，共95頁。二、析取范式、合取范式

定理(dìnglǐ) （1）一個析取范式是矛盾(máodùn)式當且僅當它的每個簡單合取式都是矛盾(máodùn)式。 （2）一個(yīɡè)合取范式是重言式當且僅當它的每個簡單析取式都是重言式。如何將一個命題公式轉(zhuǎn)換成析取范式或合取范式

（1）首先，消去公式中的和聯(lián)結(jié)詞。

（2）其次，范式中不允許出現(xiàn)p、(pq)、(pq)。

（3）最后，析取范式中不允許出現(xiàn)A(BC), 合取范式中不允許出現(xiàn)A(BC)析取范式與合取范式第五十二頁，共95頁。二、析取范式、合取范式

定理1.4（范式(fànshì)存在定理） 任一命題公式(gōngshì)都存在著與之等值的析取范式與合取范式。析取范式與合取范式第五十三頁，共95頁。例3：求下面(xiàmian)公式的析取范式與合取范式

析取范式與合取范式

注意：

命題公式的析取范式與合取范式不唯一；

prqrpprqpprqpprqpprqpú?ú??ú?ùú?úúú????úú????ú)()())(())(())(())(()(求析取范式2((pq)r)p(1)求合取范式((pq)r)p((pq)r)p((pq)r)p((pq)r)p(pq)(rp)第五十四頁，共95頁。三、極大(jídà)項、極小項

定義(dìngyì)1.20 在含有(hányǒu)n個命題變項的簡單合取式（簡單析取式）中，若每個命題變項和它的否定式不同時出現(xiàn)，而二者之一必須出現(xiàn)且僅出現(xiàn)一次，且第i個命題變項或它的否定式出現(xiàn)在從左算起的第i位上（若命題變項無角標，就按字典順序排列），稱這樣的簡單合取式（簡單析取式）為極小項（極大項）。

析取范式與合取范式第五十五頁，共95頁。析取范式與合取范式例4：公式(gōngshì)中出現(xiàn)P，Q，R三個命題變項，下列公式(gōngshì)哪些是極小項，極大項？PQPQP不是(bùshi)極小項，P，P同時出現(xiàn)不是極小(jíxiǎo)項，其中沒出現(xiàn)RPQR是極小項PQ

RPQPQP是極大項不是極大項，P，P同時出現(xiàn)

不是極大項，其中沒出現(xiàn)R注意： n個命題變項共可產(chǎn)生2n

個不同的極小項，也可產(chǎn)生2n

個不同的極大項。第五十六頁，共95頁。三、極大(jídà)項、極小項

極小(jíxiǎo)項與極大項的記法析取范式與合取范式極小項極大項公式成真賦值名稱公式成假賦值名稱PQR000m0PQR000M0PQR001m1PQR001M1PQR010m2PQR010M2PQR011m3PQR011M3PQR100m4PQR100M4PQR101m5PQR101M5PQR110m6PQR110M6PQR111m7PQR111M7第五十七頁，共95頁。三、極大(jídà)項、極小項

定理(dìnglǐ) 設(shè)mi與Mi是命題變項p1，p2，p3，……，pn形成的極小(jíxiǎo)項和極大項，則miMi，Mimi。

析取范式與合取范式四、主析取范式、主合取范式

定義1.21

設(shè)由n個命題變項構(gòu)成的析取范式（合取范式）中所有的簡單合取范式（簡單析取范式）都是極小項（極大項），則稱該析取范式（合取范式）為主析取范式（主合取范式）。

第五十八頁，共95頁。析取范式與合取范式四、主析取范式、主合取范式

定理(dìnglǐ)2.5 任何命題公式(gōngshì)都存在著與之等值的主析取范式和主析取范式，并且是唯一的。

第五十九頁，共95頁。例5：求主析取范式和主合取范式

析取范式與合取范式((pq)r)p(1)求主合取范式((pq)r)p((pq)r)p((pq)r)p((pq)r)p(pq)(rp)((pq)(rr))(p(qq)r)(pqr)(pqr)(pqr)第六十頁，共95頁。析取范式與合取范式(2)求主析取范式((pq)r)p((pq)r)p((pq)r)p((pq)r)p(pr)(qr)p(p(qq)r)((pp)qr)(p(qq)(rr))(pqr)(pqr)(pqr)(pqr)(pqr)第六十一頁，共95頁。析取范式與合取范式四、主析取范式、主合取范式

主析取范式、主合取范式的用途(yòngtú)（1）求公式(gōngshì)的成真與成假賦值（2）判斷公式類型 A為重言式當且僅當A的主析取范式包含(bāohán)2n個極小項。 A為矛盾式當且僅當A的主析取范式不含任何極小項。 A為可滿足式當且僅當A的主析取范式至少含有一個極小項。第六十二頁，共95頁。例6：用公式(gōngshì)的主析取范式判斷公式(gōngshì)的類型 2.2析取范式與合取范式(pq)qp(pq)(pq)q(pq)q(pq)q0p(pq)p(pq)(pq)(pq)(pq)(pq)1第六十三頁，共95頁。析取范式與合取范式（3）判斷兩個(liǎnɡɡè)公式是否等值。例7：判斷下列(xiàliè)公式是否等值 p(pq)(pq)pp(qq)(pq)(pq)所以兩個(liǎnɡɡè)公式等值第六十四頁，共95頁。析取范式與合取范式（4）應(yīng)用主析取范式分析和解決(jiějué)實際問題。例8：某科研所要從3名科研骨干(gǔgàn)A，B，C中挑選1～2名出國進修。由于工作需要，選派時要滿足以下條件：若A去，則C同去；若B去，則C不能去；若C不去，則A或B可以去。問所里應(yīng)如何選派他們？第六十五頁，共95頁。2.2析取范式與合取范式四、主析取范式、主合取范式

說明(shuōmíng)（1）由公式(gōngshì)的主析取范式求主合取范式（2）重言式與矛盾式的主合取范式 A為重言式當且僅當A的主合取范式不包含任何(rènhé)極大項。 A為矛盾式當且僅當A的主合取范式包含2n個極大項。 A為可滿足式當且僅當A的主合取范式包含的極大項少于2n個。第六十六頁，共95頁。第一章數(shù)理邏輯(shùlǐ-luójí)一、命題與聯(lián)結(jié)詞二、命題公式及其賦值三、等值式四、析取范式與合取范式五、聯(lián)結(jié)詞的完備集六、推理的形式結(jié)構(gòu)(jiégòu)七、自然推理系統(tǒng)P第六十七頁，共95頁。聯(lián)結(jié)詞的完備(wánbèi)集一、n元真值函數(shù)(hánshù)

定義(dìngyì)注意稱F:｛0，1｝n

｛0，1｝為n元真值函數(shù)。n個命題變項可構(gòu)成

(2n個2相乘)個不同的n元真值函數(shù)。

二、聯(lián)結(jié)詞完備集

定義設(shè)S是一個聯(lián)結(jié)詞集合，如果任何n（n>=1）元真值函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表示，則稱S是聯(lián)結(jié)詞完備集。第六十八頁，共95頁。聯(lián)結(jié)詞的完備(wánbèi)集二、聯(lián)結(jié)詞完備(wánbèi)集

定理(dìnglǐ)S={

、、

}是聯(lián)結(jié)詞完備集。推論以下聯(lián)結(jié)詞集都是完備集：（1）S1＝｛、、、｝（2）S2＝｛、、、、｝（3）S3＝｛、｝（4）S4＝｛、｝（5）S5＝｛、｝第六十九頁，共95頁。聯(lián)結(jié)詞的完備(wánbèi)集二、聯(lián)結(jié)詞完備(wánbèi)集

定義(dìngyì)1.121.13定理設(shè)p、q為兩個命題，復(fù)合命題“p與q的否定式”（“p或q的否定式”）稱作p，q的與非式（或非式），記作pq(pq)。符號()稱作與非聯(lián)結(jié)詞或非聯(lián)結(jié)詞）。pq為真當且僅當p與q不同時為真（pq為真當且僅當p與q同時為假）。｛｝｛｝都是聯(lián)結(jié)詞完備集：第七十頁，共95頁。例：給定(ɡěidìnɡ)命題公式(P∨Q)→R，該公式在聯(lián)結(jié)詞的完備集{,→}中的形式為，在{,∧}中的形式為，在{↑}中的形式為，在{↓}中的形式為。2.2析取范式與合取范式第七十一頁，共95頁。第一章

命題邏輯一、命題與聯(lián)結(jié)詞二、命題公式及其賦值三、等值式四、析取范式與合取范式五、聯(lián)結(jié)詞的完備集六、推理的形式(xíngshì)結(jié)構(gòu)七、自然推理系統(tǒng)P第七十二頁，共95頁。推理(tuīlǐ)的形式結(jié)構(gòu)一、推理(tuīlǐ)

推理(tuīlǐ)定義推理有效性定義（定義1.24）推理是指從前提出發(fā)推出結(jié)論的思維過程，而前提是已知命題公式集合，結(jié)論是從前提出發(fā)應(yīng)用推理規(guī)則推出的命題公式。設(shè)A1，A2，……Ak，B都是命題公式，若對于A1，A2，……Ak，B中出現(xiàn)的命題變項的任意一組賦值，或者A1

A2

……

Ak為假，或者當A1

A2

……

Ak為真時，B也為真，則稱由前提A1，A2，……Ak

推出B的推理是有效的或正確的，并稱B是有效的結(jié)論。第七十三頁，共95頁。3.1推理的形式(xíngshì)結(jié)構(gòu)說明(shuōmíng)（1）推理的正確性與前提的排列次序無關(guān)，因而前提中的公式不一定是序列，而是一個有限(yǒuxiàn)公式集合，若這個集合極為，可將推B的推理記為?B。若推理是正確的記為?B，否則記為?B。這里可以成?B和｛A1，A2，……Ak｝?B為推理的形式結(jié)構(gòu)。第七十四頁，共95頁。3.1推理的形式(xíngshì)結(jié)構(gòu)（2）設(shè)A1，A2，……Ak，B中共出現(xiàn)n個命題變項，對于任一組賦值，前提和結(jié)論的取值情況有以下四種：A1A2……Ak

為0，B為0；A1A2……Ak

為0，B為1；A1A2……Ak

為1，B為0；A1A2……Ak

為1，B為1只要不出現(xiàn)3)中的情況，推理就是正確的，因此判斷方法是判斷是否會出現(xiàn)3)中的情況。第七十五頁，共95頁。3.1推理的形式(xíngshì)結(jié)構(gòu)（3）推理正確，并不能保證(bǎozhèng)結(jié)論B一定為真，這與數(shù)學(xué)中的推理不同。例1：判斷下列推理(tuīlǐ)是否正確： （1）｛p,p→q｝?q （2）｛p,q→p｝?q方法一：真值表法，分別計算出前提合取式以及結(jié)論的真值情況，查看是否出現(xiàn)情況3)，如果不出現(xiàn)，則有效推理。方法二：簡單推理法，首先判斷結(jié)論為0時，各命題變項的取值情況，然后，更據(jù)個變項取值求出前提合取式的真值，如果真值可以為1，則，推理不正確。第七十六頁，共95頁。3.1推理(tuīlǐ)的形式結(jié)構(gòu)定理(dìnglǐ)命題公式(gōngshì)A1，A2，……Ak推B的推理正確當且僅當(A1A2……Ak)→B為重言式。如何證明該定理？判斷推理是否正確的三種方法判斷(A1A2……Ak)→B是否為重言式

。第七十七頁，共95頁。3.1推理的形式(xíngshì)結(jié)構(gòu)例2:判斷下列(xiàliè)推理是否正確（1）若a能被4整除(zhěngchú)，則a能被2整除(zhěngchú)。a能被4整除(zhěngchú)，所以a能被2整除(zhěngchú)。（2）若a能被4整除，則a能被2整除。a能被2整除，所以a能被4整除。（3）若下午氣溫超過30攝氏度，則王小燕必去游泳。若她去游泳，她就不去看電影了。所以，若王小燕沒去看電影，下午氣溫必超過了30攝氏度。第七十八頁，共95頁。3.1推理(tuīlǐ)的形式結(jié)構(gòu)例2:判斷下列(xiàliè)推理是否正確（4）如果他是理科學(xué)生，他必學(xué)好數(shù)學(xué)(shùxué)。如果他不是文科學(xué)生，他必是理科學(xué)生。他沒學(xué)好數(shù)學(xué)(shùxué)。所以他是文科學(xué)生。步驟：首先，將簡單命題符號化，然后分別寫出前提、結(jié)論。然后，根據(jù)判斷推理是否正確的方法，判斷推理。

真值表法、等值演算法或主析取范式法第七十九頁，共95頁。3.1推理(tuīlǐ)的形式結(jié)構(gòu)定義(dìngyì)九條重要的推理(tuīlǐ)定律人們在研究的過程中，發(fā)現(xiàn)的一些重要的重言蘊含式，這些重要的重言蘊含式被稱為推理定律。二、推理定律A?（A∨B）附加律（A∧B）

?

A化簡律（A→B）∧

A?B假言推理（A→B）∧

B?

A拒取式第八十頁，共95頁。3.1推理的形式(xíngshì)結(jié)構(gòu)（A∨B）∧

B?A析取三段論（A→B）∧（B→C）

?A→C假言三段論（A?B）∧（B?C）

?A?C等價三段論（A→B）∧（C→D）∧(A∨C)

?(B∨D)

（A→B）∧（A→B）∧(A∨A)

?B

構(gòu)造性二難（A→B）∧（C→D）∧(B∨

D)

?(A∨

C)

破壞性二難第八十一頁，共95頁。3.1推理的形式(xíngshì)結(jié)構(gòu)注意(zhùyì)（1）出現(xiàn)的A、B、C等依然(yīrán)是元語言符號，它們代表的是任意的命題公式，因而九條推理定律全是以模式的形式出現(xiàn)的。（2）若一個推理的形式結(jié)構(gòu)與某條推理定律對應(yīng)的蘊含式一致，則不用證明就可斷定這個推理是正確的，只需說明用了某條推理定律即可。（3）24個等值式中的每一個都派生出兩條推理定律。第八十二頁，共95頁。第一章數(shù)理邏輯(shùlǐ-luójí)一、命題與聯(lián)結(jié)詞二、命題公式及其賦值三、等值式四、析取范式與合取范式五、聯(lián)結(jié)詞的完備集六、推理的形式結(jié)構(gòu)(jiégòu)七、自然推理系統(tǒng)P第八十三頁，共95頁。3.2自然推理(tuīlǐ)系統(tǒng)P定義(dìngyì)3.2一個形式系統(tǒng)I由下面(xiàmian)四個部分組成：一、形式語言系統(tǒng)，形式演算系統(tǒng)（1）非空的字母表，記作A(I)。（2）A(I)中符號構(gòu)造的合式公式集，記作E(I)。（3）E(I)中一些特殊的公式組成的公理集，記作Ax(I