《離散數(shù)學(xué)左孝陵版第一章答案.ppt》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)左孝陵版第一章答案.ppt（86頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、課 程 說 明,一、離散數(shù)學(xué)課程的地位和作用,離散數(shù)學(xué)是計(jì)算機(jī)專業(yè)的一門核心基礎(chǔ)課程。,1 離散數(shù)學(xué)為計(jì)算機(jī)專業(yè)的后繼課程如數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、數(shù)據(jù)庫、編譯原理、網(wǎng)絡(luò)和算法設(shè)計(jì)等課程提供必要的數(shù)學(xué)基礎(chǔ)。,2 為學(xué)生今后從事計(jì)算機(jī)科學(xué)和技術(shù)各方面的工作提供有力的工具。,3 離散數(shù)學(xué)是現(xiàn)代數(shù)學(xué)的一個重要分支，通過該課程的學(xué)習(xí)可以提高學(xué)生的抽象思維、嚴(yán)格推理以及綜合歸納分析能力，培養(yǎng)出高素質(zhì)的人才。,二、離散數(shù)學(xué)課程的特點(diǎn),離散數(shù)學(xué)課程是應(yīng)計(jì)算機(jī)科學(xué)和技術(shù)發(fā)展的需要，綜合了高等數(shù)學(xué)的多個分支而形成的。其特點(diǎn)是以離散量為研究對象，內(nèi)容豐富，涉及面較寬。因此概念多、定理多、推理多并且內(nèi)容較為抽象。但由于

2、它是為學(xué)生后繼專業(yè)知識的學(xué)習(xí)做必要的數(shù)學(xué)準(zhǔn)備，因此它研究的內(nèi)容均比較基礎(chǔ)，難度不大。,三、如何學(xué)好離散數(shù)學(xué),要學(xué)好這門課程，首先必須充分認(rèn)識到這門課程的上述特點(diǎn)，需要做到以下幾點(diǎn)：,1 熟讀教材。準(zhǔn)確理解各個概念和定理的含義（結(jié)合多個例子來理解），必要的推理過程要看懂、理解（它可以幫助你熟悉和深刻理解定理的含義）。,2 獨(dú)立思考，大量練習(xí)。僅靠熟讀教材并不能將書本上的知識 變成你自己的知識，在熟讀教材的基礎(chǔ)上，必須通過大量練 習(xí)，獨(dú)立思考來真正獲取知識。,3 注重抽象思維能力的培養(yǎng)。數(shù)學(xué)與其他學(xué)科相比較具有較高的抽象性，而離散數(shù)學(xué)的抽象性特點(diǎn)更為顯著，它有著大量抽象的概念和抽象的推理，要學(xué)好

3、這門課程必須具有較好的抽象思維能力，才能深入地掌握課程內(nèi)容。,第四部分 數(shù)理邏輯。包括命題邏輯和謂詞邏輯。（教材的第九、十章,四、 離散數(shù)學(xué)課程的主要內(nèi)容,離散數(shù)學(xué)課程的主要內(nèi)容可以分為四個部分：,第一部分 集合論。包括集合、關(guān)系和函數(shù)。（教材的第一、二、三章）,第二部分 代數(shù)系統(tǒng)。包括代數(shù)系統(tǒng)的一般概念，幾類典型的代數(shù)系統(tǒng)。（教材的第四、五、六、七章）,第三部分 圖論。包括圖的基本概念，幾種特殊的圖。（教材的第八章）,五、 教材及參考書,2 參考書：離散數(shù)學(xué)習(xí)題題解 洪帆、付小青編，華中理工大學(xué)出版社。,1、教材：離散數(shù)學(xué)基礎(chǔ) 第二版，洪帆主編，華中理工大學(xué)出版社。,第七章 命題邏輯 數(shù)

4、理邏輯是用數(shù)學(xué)方法研究思維規(guī)律的一門學(xué)科。所謂數(shù)學(xué)方法是指:用一套數(shù)學(xué)的符號系統(tǒng)來描述和 處理思維的形式與規(guī)律。因此, 數(shù)理邏輯又稱為符號邏輯。本章介紹數(shù)理邏輯中最基本的內(nèi)容命題邏輯。首先引入命題、命題公式等概念。然后,在此基礎(chǔ)上研究命題公式間的等值關(guān)系和蘊(yùn)含關(guān)系,并給出推理規(guī)則,進(jìn)行命題演繹。 主要內(nèi)容如下： 7.1 命題和命題聯(lián)結(jié)詞 7.2 命題公式 7.3 命題公式的等值關(guān)系和蘊(yùn)含關(guān)系 7.4 范式 7.5 命題演算的推理理論,例1 判斷下列語句是否是命題。 （1）空氣是人生存所必需的。 （2）請把門關(guān)上。 （3）南京是

5、中國的首都。 （4）你吃飯了嗎？ （5）x=3。（6）啊，真美呀！ (7) 明年春節(jié)是個大晴天。,解 語句（1）,（3）,（5），(7)是陳述句 （1）、（3）、(7)是命題,用真值來描述命題是“真” 還是“假”。分別用“1”和“0”表示,命題用大寫的拉丁字母A、B、C、P、Q、或者帶下標(biāo)的大寫的字母來表示。,例2 判斷下列陳述句是否是命題。 P：地球外的星球上也有人； Q：小王是我的好朋友；,解 P、Q是命題,二、命題聯(lián)結(jié)詞,原子命題 ：由簡單句形成的命題。,復(fù)合命題：由一個或幾個原子命題通過聯(lián)結(jié)詞的聯(lián)接而構(gòu)成的命題。,例3 A：李明既是三好學(xué)生又是足球隊(duì)員。

6、 B：張平或者正在釣魚或者正在睡覺。 C：如果明天天氣晴朗，那么我們舉行運(yùn)動會。,定義五種聯(lián)結(jié)詞（或稱命題的五種運(yùn)算）。,1. 否定“”,定義7-1 設(shè)P是一個命題，利用“”和P組成的復(fù)合命題稱為P的否命題，記作“P” (讀作“非P”)。 命題P取值為真時，命題P取值為假；命題P取值為假時，命題P取值為真。,例4 設(shè)P：上海是一個城市；Q：每個自然數(shù)都是偶數(shù)。則有 P：上海不是一個城市; Q：并非每個自然數(shù)都是偶數(shù)。,2合取“” 定義7-2 設(shè)P和Q是兩個命題，由P、Q利用“”組成的復(fù)合命題，稱為合取式復(fù)合命題，記作“P Q”（讀作“P且Q”）。,當(dāng)且僅當(dāng)命題P和Q均取值

7、為真時，P Q才取值為真。,例5 設(shè)P：我們?nèi)タ措娪啊：房間里有十張桌子。則P Q表示“我們?nèi)タ措娪安⑶曳块g里有十張桌子。”,3. 析取“” 定義7-3 由命題P和Q利用“”組成的復(fù)合命題，稱為析取式復(fù)合命題，記作“PQ”（讀作“P或Q”）。,當(dāng)且僅當(dāng)P和Q至少有一個取值為真時，PQ取值為真。,例6 將命題“他可能是100米或400米賽跑的冠軍?！狈柣?。,解令 P：他可能是100米賽跑冠軍； Q：他可能是400米賽跑冠軍。,則命題可表示為PQ。,設(shè)P、Q是兩個命題，P異或Q是一個復(fù)合命題，記作PQ。,,4. 蘊(yùn)含“” 定義7

8、-4由命題P和Q利用“”組成的復(fù)合命題，稱為蘊(yùn)含式復(fù)合命題，記作“PQ”（讀作“如果P，則Q”）。,當(dāng)P為真，Q為假時，PQ為假，否則 PQ為真。,例8 將命題“如果我得到這本小說，那么我今夜就讀完它。”符號化。,解 令P：我得到這本小說；Q：我今夜就讀完它。 于是上述命題可表示為PQ。,例9 若P：雪是黑色的；Q：太陽從西邊升起； R：太陽從東邊升起。則PQ和PR所表示的命題都是真的.,5等值“” 定義7-5 由命題P和Q，利用“”組成的復(fù)合命題，稱為等值式復(fù)合命題，記作“PQ” （讀作“P當(dāng)且僅當(dāng)Q”）。,當(dāng)P和Q的真值相同時,PQ取真,否則取假。,例10

9、非本倉庫工作人員，一律不得入內(nèi)。,解 令P：某人是倉庫工作人員； Q：某人可以進(jìn)入倉庫。,則上述命題可表示為PQ。,例11 黃山比喜馬拉雅山高，當(dāng)且僅當(dāng)3是素?cái)?shù) 令P：黃山比喜馬拉雅山高；Q：3是素?cái)?shù) 本例可符號化為PQ,從漢語的語義看，P與Q之間并無聯(lián)系，但就聯(lián)結(jié) 詞的定義來看，因?yàn)镻的真值為假，Q的真值為真， 所以PQ的真值為假。,對于上述五種聯(lián)結(jié)詞，應(yīng)注意到： 復(fù)合命題的真值只取決于構(gòu)成它的各原子命題的真 值，而與這些原子命題的內(nèi)容含義無關(guān)。,三、命題符號化 利用聯(lián)結(jié)詞可以把許多日常語句符號化?；静襟E如下：,（1）從語句中分析出各原子命題，將它們符號化；,（2）使用

10、合適的命題聯(lián)結(jié)詞，把原子命題逐個聯(lián)結(jié)起來，組成復(fù)合命題的符號化表示。,例12 用符號形式表示下列命題。 （1）如果明天早上下雨或下雪，那么我不去學(xué)校 （2）如果明天早上不下雨且不下雪，那么我去學(xué)校。 （3）如果明天早上不是雨夾雪，那么我去學(xué)校。 （4）只有當(dāng)明天早上不下雨且不下雪時，我才去學(xué)校。,解 令P：明天早上下雨； Q：明天早上下雪； R：我去學(xué)校。,（2）（P Q）R；,（1）（PQ） R；,（4）R（P Q）,（3）(PQ）R；,例12將下列命題符號化 （1） 派小王或小李出差； （2） 我們不能既劃船又跑步； （3） 如果你來了，那么他唱不唱歌將看你是

11、否伴奏而定； （4） 如果李明是體育愛好者，但不是文藝愛好者，那么 李明不是文體愛好者； （5） 假如上午不下雨，我去看電影，否則就在家里看書。,解 （1） 令P：派小王出差；Q：派小李出差。 命題符號化為PQ。,（2） 令P：我們劃船；Q：我們跑步。則命題可 表示為(PQ）。,（3） 令P：你來了；Q：他唱歌；R：你伴奏。 則命題可表示為 P（QR）,（4） 令P：李明是體育愛好者；Q：李明是文藝愛好者。 則命題可表示為（P Q）（P Q）,（5） 令P：上午下雨；Q：我去看電影；R：我在家讀書。 則命題可表示為（P Q）（

12、PR）。,練習(xí)7-1 1. 判斷下列語句哪些是命題，若是命題，則指出其真值。 （1） 只有小孩才愛哭。 （2） X+6=Y （3） 銀是白的。 （4） 起來吧，我的朋友。,( 是 假 ),( 不是 ),( 是 真 ),( 不是 ),2 將下列命題符號化 （1）我看見的既不是小張也不是老李。,解 令P：我看見的是小張；Q：我看見的是老李。,則該命題可表示為PQ,（2）如果晚上做完了作業(yè)并且沒有其它的事，他就會看電視或聽音樂。,解 令 P：他晚上做完了作業(yè)；Q：他晚上有其它的事； R：他看電視； S：他聽音樂。 則該命題可表示為（PQ）

13、（RS）,7.2 命題公式 一 、 命題公式的概念 1. 命題常元 一個表示確定命題的大寫字母。,2命題變元 一個沒有指定具體內(nèi)容的命題符號。,一個命題變元當(dāng)沒有對其賦予內(nèi)容時，它的真值不能確定，一旦用一個具體的命題代入，它的真值就確定了。,3. 命題公式 命題公式（或簡稱公式）是由0、1和命題變元以及命題聯(lián)結(jié)詞按一定的規(guī)則產(chǎn)生的符號串。,定義7-6 （命題公式的遞歸定義。） （1） 0，1是命題公式； （2） 命題變元是命題公式； （3） 如果A是命題公式，則A是命題公式； （4） 如果A和B是命題公式，則（AB）， （AB）,(AB）

14、,(A B）也是命題公式； 有限次地利用上述（1）（4）而產(chǎn)生的符號串是命題公式。,例1 下列符號串是否為命題公式。 （1） P(QPR）； （2）（PQ）（（QR））,解 （1） 不是命題公式。 （2） 是命題公式。,二、真值指派 命題公式代表一個命題，但只有當(dāng)公式中的每一個命題變元都用一個確定的命題代入時，命題公式才有確定的真值，成為命題。,定義77 設(shè)F為含有命題變元P1，P2，,Pn的命題公式，對P1，P2，,Pn分別指定一個真值,稱為對公式F的一組真值指派。,公式與其命題變元之間的真值關(guān)系，可以用真值表的方法表示出來。,例2 給出公式 F=(（PQ）（QR）) (

15、PR）的真值表。,解 公式F的真值表如下：,三、公式類型 定義7-8 如果對于命題公式F所包含的命題變元的任何一組真值指派，F(xiàn)的真值恒為真，則稱公式F為重言式（或永真公式），常用“1”表示。相反地，若對于F所包含的命題變元的任何一組真值指派，F(xiàn)的真值恒為假，則稱公式F為矛盾式（或永假公式），常用“0”表示。如果至少有一組真值指派使公式F的真值為真，則稱F為可滿足公式 。,例3 構(gòu)造下列命題公式的真值表，并判斷它們是何種類型的公式 （1）（PQ） （PQ）； （2）（QP）（PQ）； （3）（（PQ）（QR））（PR）。,由上可知： F1是重言式 , F2是矛盾式。,(3)的真值表如

16、第4頁所示，它是可滿足公式。,7.3 命題公式的等值關(guān)系和蘊(yùn)含關(guān)系,一、命題公式的等值關(guān)系 定義7-9 設(shè)A和B是兩個命題公式, P1, P2, , Pn 是所有出現(xiàn)于A和B中的命題變元，如果對于P1, P2, , Pn 的任一組真值指派，A和B的真值都相同,則稱公式A和B等值，記為A B,稱 AB為等值式。,注意： （1）符號“”與“”的區(qū)別與聯(lián)系。,“”不是聯(lián)結(jié)詞，AB不表示一個公式，它表示兩個公式間的一種關(guān)系，即等值關(guān)系。,“”是聯(lián)結(jié)詞，AB是一個公式。,AB當(dāng)且僅當(dāng)AB是永真公式。,（2）可以驗(yàn)證等值關(guān)系是等價關(guān)系。 即自反性：對任意公式A，有AA。 對稱性：對任意公式A，

17、B，若AB，則BA。 可傳遞性：對任意公式A、B、C，若AB，BC，則AC。,（3）當(dāng)A是重言式時，A1；當(dāng)A是矛盾式時，則A0。,二、基本的等值式 設(shè)P、Q、R是命題變元，下表中列出了24個最基本的等值式:,三、等值式的判別 有兩種方法：真值表方法，命題演算方法 1、真值表方法,例1 用真值表方法證明 E10： (PQ) PQ,解 令：A= (PQ)，B= PQ，構(gòu)造A，B 以及A B的真值表如下：,,,,,由于公式AB所標(biāo)記的列全為1，因此AB。,0,例2 用真值表方法證明E11：PQPQ,解 令A(yù)=PQ，B=PQ 構(gòu)造A，B以及AB的真值表如下：,由于公式AB所標(biāo)記的列全

18、為1，因此AB.,例3 用真值表方法判斷PQPQ是否成立.,解 令A(yù)=PQ，B=PQ 構(gòu)造A，B以及AB的真值表,由于公式AB所標(biāo)記的列不全為1，AB不是永真公式，因此AB不成立。,(1) 代入規(guī)則 代入規(guī)則 對于重言式中的任一命題變元出現(xiàn)的每一處均用同一命題公式代入，得到的仍是重言式。,2等值演算方法,例如 F=（PQ）（QP）是重言式，若 用公式AB代換命題變元P得公式 F1=（（AB）Q）（Q（AB））， F1仍是重言式。,注意：因?yàn)锳 B當(dāng)且僅當(dāng)A B是重言式。所以，若對于等值式中的任一命題變元出現(xiàn)的每一處均用同一命題公式代入，則得到的仍是等值式。,(2) 置 換規(guī)則

19、 定義7-10 設(shè)C是命題公式A的一部分（即C是公式A中連續(xù)的幾個符號），且C本身也是一個命題公式，則稱C為公式A的子公式。,例如 設(shè)公式A=（PQ）（（PQ）（RS））。,則PQ，PQ，（PQ）（RS）等均是A的子公式，,但P，P和Q等均不是A的子公式，,置換規(guī)則 設(shè)C是公式A的子公式，CD。如果將公式A中的子公式C置換成公式D之后，得到的公式是B，則AB。,(3) 等值演算 等值演算是指利用已知的一些等值式，根據(jù)置換規(guī)則、代入規(guī)則以及等值關(guān)系的可傳遞性推導(dǎo)出另外一些等值式的過程。,由代入規(guī)則知前述的基本等值式，不僅對任意的命題變元P，Q，R是成立的，而且當(dāng)P，Q，R分別為命題公式時，這些

20、等值式也成立,例2 證明命題公式的等值關(guān)系： （PQ）（RQ）（PR）Q；,證明 （PQ）（RQ） （ PQ）( RQ) E11 （ P R）Q E3( 分配律) (PR)Q E10(德.摩根定律) (PR) Q E11 所以（PQ）（RQ）（PR）Q,例3 證明下列命題公式的等值關(guān)系 (P Q ) ( P ( P Q ) ) P Q,證明 (PQ)( P(PQ)) (PQ)( (P P ) Q ) E2(結(jié)合律), (PQ)( PQ) E7(等冪律), (P Q ) ( PQ )

21、 E1 (交換律), P(Q(PQ)) E2(結(jié)合律), PQ E1，E9(交換律，吸收律),例4 判別下列公式的類型。 （1） Q (P（PQ）) （2）（PQ）P,解（1） Q（P（PQ）） Q（P（PQ）） E11,E6 Q（（PP）（PQ）） E3 Q（1（PQ）） E5 Q（PQ） E4 QPQ E10 （QQ）P E1,E2 0 E5,E8 所以Q (P (PQ))是矛盾式。 （2）

22、 （PQ）P （PQ）P E11 P E9 于是該公式是可滿足式。,三、命題公式的蘊(yùn)含關(guān)系 定義7-11 設(shè)A，B是兩個公式，若公式AB是重言式，即AB1，則稱公式A蘊(yùn)含公式B，記作AB。稱“AB”為蘊(yùn)含式。,注意：符號“”和 “”的區(qū)別和聯(lián)系與符號“”與“”的區(qū)別和聯(lián)系類似。,“”不是聯(lián)結(jié)詞， “AB”不是公式，它表示公式A與B之間存在蘊(yùn)含關(guān)系。,“”是聯(lián)系詞，AB是一個公式。,AB當(dāng)且僅當(dāng)AB是永真公式 。,AB是偏序關(guān)系,即 自反性：AA。 反對稱：若AB，BA，則AB。 傳遞性：若AB，BC，則 AC。,反對稱性的證明： 設(shè)A

23、B且BA，,由定義7-11 AB1且BA1,于是AB(AB)(BA) E14 11 1 因此 AB,傳遞性的證明： 設(shè)AB，BC，,則AB1，BC1, (ABC)(ABC), ((AB) C)(A(BC)), (1C)(A1), 11 1,因此 AC.,于是 AC AC, (AC)(BB),四、基本的蘊(yùn)含式,五、蘊(yùn)含式的判別 判定“A B”是否成立的問題可轉(zhuǎn)化為判定A B是否為重言式，有下述判定方法：,（1）真值表； （2）等值演算； （3）假定前件A為真； （4）假定后件B為假。,1. 真值表方法,例4 證明I14 ：(（PQ）（P R）（Q R）

24、) R,證明 令公式 F =（（PQ）（PR）（QR））R， 其真值表如下：,公式F對任意的一組真值指派取值均為1，故F是重言式。,2. 等值演算方法 例5 證明 I11：P（PQ） Q,證明 （P（PQ）） Q, （P（PQ）） Q E11, （P（PQ）） E10,（PQ）（PQ） E2, 1 代入規(guī)則,E5 因此 P（PQ） Q,3. 假定前件A真 假定前件A為真，檢查在此情況下，其后件B是否也為真。,例6證明 I12 :Q （PQ） P,證明令前件Q（PQ）為真，,則Q為真, 且PQ為真。,于是Q為假，因而P也為假。由此P為真。,故蘊(yùn)含式 I12

25、 成立。,4、 假定后件B假 假定后件B為假，檢查在此情況下，其前件A是否也為假.,例7 證明蘊(yùn)含式(PQ) (RS) (PR) (QS),證明 令后件(PR)(QS)為假，則PR為真，QS為假,,于是P、R均為真，而Q和S至少一個為假。,由此可知 PQ與RS中至少一個為假,,因此(PQ)(RS)為假.,故上述蘊(yùn)含式成立。,練習(xí) 7-3 1判斷下列等值式是否成立 （1）（PQ） （R Q）（PR） Q （2）（PQ）（P Q）（PQ）,解（1）（PQ）（RQ）,（PQ） （RQ） E11,（PR）Q E3,（PR）Q E10,（2）（PQ）（PQ）, (

26、（PQ）（QP）) E6，E10, (（PQ）（QP）) E11, （PQ） E14,（PR）Q E11,2判定蘊(yùn)含式P（QR） （PQ）（PR）是否成立,解假定后件（PQ）（PR）為假，,則PQ為真，PR為假。,由PR為假,得P為真，R為假。,又PQ為真，故得Q為真。,于是P為真，QR為假。,從而 P（QR）為假。,因此蘊(yùn)含式成立。,7.4范式 一、 析取范式和合取范式,定義7-12 一個命題公式若它具有P1*P2*Pn*的形式（n1），其中Pi*是命題變元Pi或其否定Pi ，則稱其為質(zhì)合取式。 例如,PQRS是由命題變元P、Q、R、S

27、組成的一質(zhì)合取式。,定義7-13 一個命題公式若具有P1*P2*Pn*（n1）的形式，其中P*i是命題變元Pi或是其否定Pi ，則稱其為質(zhì)析取式。 例如, QPR是由命題變元P、Q、R組成的一質(zhì)析取式。,定理7-4 （1）一質(zhì)合取式為永假式的充分必要條件是，它同時包含某個命題變元P及其否定P。 （2）一質(zhì)析取式為永真式的充分必要條件是，它同時包含某個命題變元P及其否定P。,證明（2）必要性：假設(shè)A= P1*P2*Pn*為一質(zhì)析取式，且A為一永真式。,(反證法) 假設(shè)A式中不同時包含任一命題變元及其否定，,則在A中，當(dāng)Pi*為Pi時指派Pi取0，當(dāng)Pi*為Pi時，指派Pi取1。(i =1,2,

28、n).這樣的一組真值指派使A的真值取0，這與A為永真式矛盾。,例如A=P1P2P3.則(P1,P2,P3)=(0,1,0)的指派，使A的真值為0.,充分性：設(shè)A含命題變元Pi和Pi，而PiPi是永真式， 由結(jié)合律和零一律，A的真值必為1，故A也是永真式。,定義7-14質(zhì)合取式的析取稱為析取范式。即具有A1A2An(n1)的形式的公式，其中Ai是質(zhì)合取式。,例如，F(xiàn)1=P(PQ)R(PQR)是一析取范式。,定義7-15質(zhì)析取式的合取稱為合取范式。 即具有A1A2An (n1)的形式的公式，其中Ai是質(zhì)析取式。,例如，F(xiàn)2=P(PQ)R(PQR)是一合取范式。 F3=(PRQ)(PQ)R(PR)

29、也是一合取范式。,二、求公式的析取范式和合取范式,任何一個命題公式都可以變換為與它等值的析取范式或合取范式。按下列步驟進(jìn)行：,（1）利用E11，E12和E14消去公式中的運(yùn)算符“”和“”；,(2) 利用德摩根定律將否定符號“”向內(nèi)深入，使之只作用于命題變元；,（3）利用雙重否定律E6將 (P)置換成P；,（4）利用分配律、結(jié)合律將公式歸約為合取范式或析取范式。,例1 求F1=(P(QR))S的合取范式和析取范式,解 F1 (P(QR))S E11, P ( QR)S E10, P(QR)S (析取范式) E10 ,E6,又 F1 P(QR)S, (PS

30、)(QR) E1 ,E2, (PSQ)(PSR) （合取范式） E3,另外由 F1 (PSQ)(PSR),(P(PSR))(S(PSR))(Q(PSR)) E3,PS(QP)(QS)(QR) （析取范式） E9 ,E13,例2 求 F2= (PQ) (PQ)的析取范式、合取范式。,解F2 ((PQ) (PQ))((PQ) (PQ)) E14, ((PQ)(PQ))((PQ) (PQ)) E11,E6,(P(Q(PQ)))(PQ(PQ)) E2,E10,E10, (PQ)(PQ) （合取范式） E2,E9,(P(PQ))(Q(P

31、Q)) E3,(PP) (PQ)(PQ)(QQ)（析取范式） E3,定理7-5 （1）公式A為永真式的充分必要條件是，A的合取范式中每一質(zhì)析取式至少包含一對互為否定的析取項(xiàng)。,三、利用范式判定公式類型,證明（2）必要性（用反證法）： 假設(shè)AA1A2An中某個Ai不包含一對互為否定的合取項(xiàng)，,（2）公式A為永假式的充分必要條件是，A的析取范式中每一質(zhì)合取式至少包含一對互為否定的合取項(xiàng)。,則由定理7-4知，Ai不是矛盾式。,于是存在一組真值指派使Ai取值為真。,對同一組真值指派，A的取值也必為真，這與A是矛盾式不符，假設(shè)不成立。,充分性：假設(shè)任一Ai(1in)中含有形如PP合取式，其

32、中P為命題變元。于是由定理7-4知，每一Ai(1in)都為矛盾式，因此A1A2An必為矛盾式，即A為矛盾式。,因此A的析取范式中每一質(zhì)合取式至少包含一對互為否定的合取項(xiàng)。,例3 判別公式A=P (P(QP))是否為重言式或矛盾式。,解 A P(P(QP)) E11, P(PQ)(PP) (析取范式) E3,根據(jù)定理7-5，A不是矛盾式。,又AP(P(QP)),（PP）（PQP)（合取范式） E3,由定理7-5知，A是重言式。,例4 利用范式判斷公式P(PQ)的類型。,解 P(PQ) (P(PQ))(P(PQ))E12,(PQ)(P(PQ)) E10,(PQ)P (析取范式) E9

33、,由定理7-5，該公式不是永假公式。,(PP ) (PQ) （合取范式）E1，E3,由定理7-5，該公式也不是永真公式。,由上可知，該公式是一可滿足公式。,又 P(PQ)(PQ)P,四、主析取范式和主合取范式 定義7-16 設(shè)有命題變元P1，P2，,Pn ，形如 的命題公式稱為是由命題變元P 1，P2，，Pn所產(chǎn)生的最小項(xiàng)。而形如 的命題公式稱為是由命題變元P1，P2，，Pn所產(chǎn)生的最大項(xiàng) 。其中Pi*為Pi或?yàn)镻i(i=1,2,n).,例如,P1P2P3， P1P2P3均是由P1，P2，P3所產(chǎn)生的最小項(xiàng)。 P1P2P3是由P1，P2，P3產(chǎn)生的一個最大項(xiàng)。,定義7-17由不同最小項(xiàng)

34、所組成的析取式，稱為主析取范式。,定義7-18由不同最大項(xiàng)所組成的合取式，稱為主合取范式。,例如(P1P2P3)(P1P2P3)(P1P2P3)是一個主析取范式。,(P1P2P3)(P1P2P3)(P1P2P3)(P1P2P3)是一個主合取范式。,例4 求公式 F1 = P(P(QP))和公式 F2 = (PQ)(PQ)的主析取范式.,解 F1P(P(QP)) E11, P(PQ)(PP) E3,(P(QQ))(PQ)(P(QQ)) E7,E4,E5, (PQ)(PQ)(PQ)(PQ)(PQ) E3, (PQ)(PQ)(PQ)(PQ) E1,E

35、7,五、求公式的主析取范式和主合取范式 對任一給定的公式除了用求范式時的四個步驟外，還要利用同一律、等冪律、互否律、分配律等進(jìn)一步將質(zhì)合取式（質(zhì)析取式）變換為最小項(xiàng)（最大項(xiàng)）的形式。,F2(PQ)(PQ), (PQ) (PQ) E11, (PPQ)(QPQ) E3,定理7-6 每一個不為永假的命題公式F（P1, P2, , Pn）必與一個由P1，P2，，Pn所產(chǎn)生的主析取范式等值。,永真公式的主析取范式包含所有2n個最小項(xiàng)。,永假公式的主析取范式是一個空公式。用0表示。,例5 求公式 F1= (PQ)(PQ)和 公式F2=P(P(QP))的主合取范式,F1 (PQ)(PQ)

36、 E11, (PQ)(P(QQ))(Q(PP)) E5, E4, (PQ)(PQ)(PQ)(PQ)(PQ) E3, (PQ)(PQ)(PQ)(PQ) E7,解 F2 P(P(QP)) E11, (PP)(PQP) E3,11 E5,E1, 1,定理7-7 每一個不為永真的公式 F(P1, P2, , Pn）必與一個由P1, P2, , Pn所產(chǎn)生的主合取范式等值。,永假公式的主合取范式包含所有 2n個最大項(xiàng)。,永真公式的主合取范式是一空公式，用1表示。,六、利用主范式判定公式類型 1. 利用主析取范式判定,(1) 若公式 F(P1,

37、 P2，，Pn)的主析取范式包含所有2n個最小項(xiàng)，則 F是永真公式。例如，例4中的 F1。,(2) 若 F的主析取范式是一空公式且為0，則 F是永假公式。例如，例4中的 F2。,(3) 否則，F(xiàn)為可滿足的公式。,2 利用主合取范式判定,(1) 若公式F（P1, P2, , Pn）的主合取范式包含所有2n個最大項(xiàng)，則F是永假公式。例如，例5中的F1。,(2) 若F的主合取范式是一空公式且為1，則F是永真公式。例如，例5中的F2。,(3) 否則，F(xiàn)為可滿足公式,例6 求公式F=(Q(PQ))P的主范式并判定公式的類型.,解 (1) 求F的主析取范式,F (Q(PQ))P, Q (PQ)P, (Q

38、(PP)) (PQ)(P(QQ)), （PQ)(PQ)(PQ)(PQ)(PQ), (PQ)(PQ)(PQ),由此可知F是可滿足公式。,(2) 求F的主合取范式,F （Q(PQ))P, PQ,由前分析和舉例可知： 僅需求出公式F的任一種主范式即可判定F的類型。,練習(xí) 7-4 1判斷公式F=(PQ)(PQ)是否為重言式或矛盾式？,解 F (PQ)((PQ)(QP)) E11, (PQ)((PQ)(QP)) E10,E6,E11, (PQ)((P(QP))(Q(QP))) E3, (PQ)(PQ)(PP)(QQ)(QP) E3, (PQ)(PQ)(QP) E5,E

39、8,F的主析取范式既非空公式，又未包含22=4個項(xiàng)，故F不是重言式和矛盾式，只是可滿足式。,7.5 命題演算的推理理論 一、推理 推理是由已知的命題得到新命題的思維過程。,定義7-19 設(shè)A和B是兩個命題公式，如果AB，即如果命題公式AB為重言式，則稱B是前提A的結(jié)論或從A推出結(jié)論B。一般地設(shè)H1，H2，,Hn和C是一些命題公式,若蘊(yùn)含式 H1H2Hn C (*) 成立，則稱C是前提集合 H1，H2，,Hn的結(jié)論，或稱從前提H1，H2，,Hn能推出結(jié)論C。有時也記作H1，H2，,Hn C,1、真值表法 對于命題公式 中所有命題變元的每一組真值指派作出該公式的真值表，看是否為

40、永真。,例1 考察結(jié)論C是否是下列前提H1，H2的結(jié)論。 （1）H1：PQ，H2：P，C：Q,二、如何判斷由一個前提集合能否推出某個結(jié)論,（2）H1：PQ， H2： P ， C： Q,在這里，我們不關(guān)心結(jié)論是真還是假，而主要關(guān)心由給定的前提是否能推出這個結(jié)論來。,2、真值演算方法 例 證明,分析根據(jù)題意，需證明,證明,3、“形式證明”方法 （1）基本述語 形式證明：一個描述推理過程的命題序列，其中每個 命題或者是已知的命題，或者是由某些前提所推得的結(jié)論， 序列中最后一個命題就是所要求的結(jié)論，這樣的命題序列稱 為形式證明。,有效的證明：如果證明過程中的每一步所得到的結(jié)論 都是根據(jù)推理

41、規(guī)則得到的，則這樣的證明稱作是有效的。 有效的結(jié)論：通過有效的證明而得到結(jié)論，稱作是有效的結(jié)論。,合理的證明：一個證明是否有效與前提的真假沒有關(guān)系。 如果所有的前提都是真的，那么通過有效的證明所得到的結(jié)論 也是真的。這樣的證明稱作是合理的。 合理的結(jié)論：一個結(jié)論是否有效與它自身的真假沒有關(guān) 系。通過合理證明而得到的結(jié)論稱作合理的結(jié)論。,( 2) 推理規(guī)則 前提引用規(guī)則：在證明的任何步驟上都可以引用前提。 結(jié)論引用規(guī)則：在證明的任何步驟上所得到的結(jié)論都可以在其后的證明中引用。,置換規(guī)則：在證明的任何步驟上，命題公式的子公式都可以用與它等值的其它命題公式置換。 代入規(guī)則：在證明的任何

42、步驟上，重言式中的任一命題變元都可以用一命題公式代入，得到的仍是重言式。,例2 證明 R（PQ）是前提PQ，QR，PS ，S的結(jié)論。,所以PQ，QR，PS， S R（PQ),例3 證明RS是前提P（QS）， RP和Q的有效結(jié)論。,利用蘊(yùn)含證明規(guī)則： 可將例3等價地改為證明由前提 推出結(jié)論 S。,例4 符號化下面語句的推理過程，并指出推理是否正確?！叭绻资枪谲姡瑒t乙或丙將得亞軍；如果乙得亞軍，則甲不能得冠軍；如果丁得亞軍，丙不能得亞軍；事實(shí)是甲已得冠軍，可知丁不能得亞軍”。,解 設(shè) A：甲得冠軍；B：乙得亞軍； C：丙得亞軍；D：丁得亞軍。,推

43、理過程符號化為 A（BC），B A，DC，A D,4、 間接證明(或反證法),定義7-20 如果對于出現(xiàn)在公式H1，H2，,Hn中的命題變元的任何一組真值指派，公式H1，H2，,Hn中至少有一個為假，即它們的合取式H1 H2Hn是矛盾式，則稱公式H1，H2，Hn是不相容的。否則稱公式H1，H2,Hn是相容的。,定理7-8 若存在一個公式R，使得 H1H2 Hn R R則公式H1，H2，,Hn是不相容的。,證明 設(shè)H1 H2Hn ==R R ，,而RR是矛盾式，所以前件H1Hn必永假。 因此，H1，H2，,Hn是不相容的。,則意味著（H1 H2Hn）（RR）是重言式，,為了

44、證明H1、H2、、H nC，利用定理7-8，將C添加到這一組前提中，轉(zhuǎn)化為證明 H1H2HnC RR,于是得出H1、H2、、Hn、C是不相容的。,即H1H2HnC是永假公式。,這意味著當(dāng)H1H2Hn為真時，C必為假，因而C必為真。,例5 證明：R Q、RS、S Q、PQ P,用反證法，將（P）作為附加前提，添加到前提集合中，然后推出矛盾。 證明,因此（RQ）（RS）（S Q）（PQ) P,練習(xí)7-5 用形式證明方法證明： （1）PQ是前提（PQ）R，RS，S的結(jié)論。,因此，（PQ）R， RS， S P Q,習(xí) 題 1判斷下列推理是否正確 如果這里有球賽，則通行是困難的；如果他們按指

45、定的時間到達(dá)，則通行是不困難的；他們按指定時間到達(dá)了，所以這里沒有球賽。,解 先將已知條件符號化 , 令P：這里有球賽； Q：通行是困難的；R：他們按指定的時間到達(dá)了。,編 號 公 式 依 據(jù) （1） RQ 前提,因此上述推理正確。,（2） R 前提,（3） Q （1），（2）;I11,（4） PQ 前提,（5） P （3），（4）；I12,則上述推理過程符號化為P Q，R Q，R P,2. 張三說李四在說謊，李四說王五在說謊，王五說張三、 李四都在說謊。問張三、李四、王五三人，到底誰說真話，誰說假話？,解 先將簡單命題符號化。 令P：張三說真話；Q：李四說真話； R：王五說真話， 由題意知推理的前提為： P Q，PQ，QR， QR， R（P Q）， R（PQ）。 下面根據(jù)已知前提進(jìn)行形式推理。,因此，由上述推理知張三說假話，王五說假話，只有李四說真話。,