離散數(shù)學(xué)左孝陵版第一章答案.ppt

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

課程說(shuō)明,一、離散數(shù)學(xué)課程的地位和作用,離散數(shù)學(xué)是計(jì)算機(jī)專業(yè)的一門(mén)核心基礎(chǔ)課程。,1離散數(shù)學(xué)為計(jì)算機(jī)專業(yè)的后繼課程如數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、數(shù)據(jù)庫(kù)、編譯原理、網(wǎng)絡(luò)和算法設(shè)計(jì)等課程提供必要的數(shù)學(xué)基礎(chǔ)。,2為學(xué)生今后從事計(jì)算機(jī)科學(xué)和技術(shù)各方面的工作提供有力的工具。,3離散數(shù)學(xué)是現(xiàn)代數(shù)學(xué)的一個(gè)重要分支，通過(guò)該課程的學(xué)習(xí)可以提高學(xué)生的抽象思維、嚴(yán)格推理以及綜合歸納分析能力，培養(yǎng)出高素質(zhì)的人才。,二、離散數(shù)學(xué)課程的特點(diǎn),離散數(shù)學(xué)課程是應(yīng)計(jì)算機(jī)科學(xué)和技術(shù)發(fā)展的需要，綜合了高等數(shù)學(xué)的多個(gè)分支而形成的。其特點(diǎn)是以離散量為研究對(duì)象，內(nèi)容豐富，涉及面較寬。因此概念多、定理多、推理多并且內(nèi)容較為抽象。但由于它是為學(xué)生后繼專業(yè)知識(shí)的學(xué)習(xí)做必要的數(shù)學(xué)準(zhǔn)備，因此它研究的內(nèi)容均比較基礎(chǔ)，難度不大。,三、如何學(xué)好離散數(shù)學(xué),要學(xué)好這門(mén)課程，首先必須充分認(rèn)識(shí)到這門(mén)課程的上述特點(diǎn)，需要做到以下幾點(diǎn)：,1熟讀教材。準(zhǔn)確理解各個(gè)概念和定理的含義（結(jié)合多個(gè)例子來(lái)理解），必要的推理過(guò)程要看懂、理解（它可以幫助你熟悉和深刻理解定理的含義）。,2獨(dú)立思考，大量練習(xí)。僅靠熟讀教材并不能將書(shū)本上的知識(shí)變成你自己的知識(shí)，在熟讀教材的基礎(chǔ)上，必須通過(guò)大量練習(xí)，獨(dú)立思考來(lái)真正獲取知識(shí)。,3注重抽象思維能力的培養(yǎng)。數(shù)學(xué)與其他學(xué)科相比較具有較高的抽象性，而離散數(shù)學(xué)的抽象性特點(diǎn)更為顯著，它有著大量抽象的概念和抽象的推理，要學(xué)好這門(mén)課程必須具有較好的抽象思維能力，才能深入地掌握課程內(nèi)容。,第四部分?jǐn)?shù)理邏輯。包括命題邏輯和謂詞邏輯。（教材的第九、十章,四、離散數(shù)學(xué)課程的主要內(nèi)容,離散數(shù)學(xué)課程的主要內(nèi)容可以分為四個(gè)部分：,第一部分集合論。包括集合、關(guān)系和函數(shù)。（教材的第一、二、三章）,第二部分代數(shù)系統(tǒng)。包括代數(shù)系統(tǒng)的一般概念，幾類典型的代數(shù)系統(tǒng)。（教材的第四、五、六、七章）,第三部分圖論。包括圖的基本概念，幾種特殊的圖。（教材的第八章）,五、教材及參考書(shū),2參考書(shū)：離散數(shù)學(xué)習(xí)題題解洪帆、付小青編，華中理工大學(xué)出版社。,1、教材：離散數(shù)學(xué)基礎(chǔ)第二版，洪帆主編，華中理工大學(xué)出版社。,第七章命題邏輯數(shù)理邏輯是用數(shù)學(xué)方法研究思維規(guī)律的一門(mén)學(xué)科。所謂數(shù)學(xué)方法是指:用一套數(shù)學(xué)的符號(hào)系統(tǒng)來(lái)描述和處理思維的形式與規(guī)律。因此,數(shù)理邏輯又稱為符號(hào)邏輯。本章介紹數(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判斷下列語(yǔ)句是否是命題。（1）空氣是人生存所必需的。（2）請(qǐng)把門(mén)關(guān)上。（3）南京是中國(guó)的首都。（4）你吃飯了嗎？（5）x=3。（6）啊，真美呀！(7)明年春節(jié)是個(gè)大晴天。,解語(yǔ)句（1）,（3）,（5），(7)是陳述句（1）、（3）、(7)是命題,用真值來(lái)描述命題是“真”還是“假”。分別用“1”和“0”表示,命題用大寫(xiě)的拉丁字母A、B、C、P、Q、或者帶下標(biāo)的大寫(xiě)的字母來(lái)表示。,例2判斷下列陳述句是否是命題。P：地球外的星球上也有人；Q：小王是我的好朋友；,解P、Q是命題,二、命題聯(lián)結(jié)詞,原子命題：由簡(jiǎn)單句形成的命題。,復(fù)合命題：由一個(gè)或幾個(gè)原子命題通過(guò)聯(lián)結(jié)詞的聯(lián)接而構(gòu)成的命題。,例3A：李明既是三好學(xué)生又是足球隊(duì)員。B：張平或者正在釣魚(yú)或者正在睡覺(jué)。C：如果明天天氣晴朗，那么我們舉行運(yùn)動(dòng)會(huì)。,定義五種聯(lián)結(jié)詞（或稱命題的五種運(yùn)算）。,1.否定“”,定義7-1設(shè)P是一個(gè)命題，利用“”和P組成的復(fù)合命題稱為P的否命題，記作“P”(讀作“非P”)。命題P取值為真時(shí)，命題P取值為假；命題P取值為假時(shí)，命題P取值為真。,例4設(shè)P：上海是一個(gè)城市；Q：每個(gè)自然數(shù)都是偶數(shù)。則有P：上海不是一個(gè)城市;Q：并非每個(gè)自然數(shù)都是偶數(shù)。,2合取“”定義7-2設(shè)P和Q是兩個(gè)命題，由P、Q利用“”組成的復(fù)合命題，稱為合取式復(fù)合命題，記作“PQ”（讀作“P且Q”）。,當(dāng)且僅當(dāng)命題P和Q均取值為真時(shí)，PQ才取值為真。,例5設(shè)P：我們?nèi)タ措娪?。Q：房間里有十張桌子。則PQ表示“我們?nèi)タ措娪安⑶曳块g里有十張桌子。”,3.析取“”定義7-3由命題P和Q利用“”組成的復(fù)合命題，稱為析取式復(fù)合命題，記作“PQ”（讀作“P或Q”）。,當(dāng)且僅當(dāng)P和Q至少有一個(gè)取值為真時(shí)，PQ取值為真。,例6將命題“他可能是100米或400米賽跑的冠軍?！狈?hào)化。,解令P：他可能是100米賽跑冠軍；Q：他可能是400米賽跑冠軍。,則命題可表示為PQ。,設(shè)P、Q是兩個(gè)命題，P異或Q是一個(gè)復(fù)合命題，記作PQ。,4.蘊(yùn)含“”定義7-4由命題P和Q利用“”組成的復(fù)合命題，稱為蘊(yùn)含式復(fù)合命題，記作“PQ”（讀作“如果P，則Q”）。,當(dāng)P為真，Q為假時(shí)，PQ為假，否則PQ為真。,例8將命題“如果我得到這本小說(shuō)，那么我今夜就讀完它?！狈?hào)化。,解令P：我得到這本小說(shuō)；Q：我今夜就讀完它。于是上述命題可表示為PQ。,例9若P：雪是黑色的；Q：太陽(yáng)從西邊升起；R：太陽(yáng)從東邊升起。則PQ和PR所表示的命題都是真的.,5等值“”定義7-5由命題P和Q，利用“”組成的復(fù)合命題，稱為等值式復(fù)合命題，記作“PQ”（讀作“P當(dāng)且僅當(dāng)Q”）。,當(dāng)P和Q的真值相同時(shí),PQ取真,否則取假。,例10非本倉(cāng)庫(kù)工作人員，一律不得入內(nèi)。,解令P：某人是倉(cāng)庫(kù)工作人員；Q：某人可以進(jìn)入倉(cāng)庫(kù)。,則上述命題可表示為PQ。,例11黃山比喜馬拉雅山高，當(dāng)且僅當(dāng)3是素?cái)?shù)令P：黃山比喜馬拉雅山高；Q：3是素?cái)?shù)本例可符號(hào)化為PQ,從漢語(yǔ)的語(yǔ)義看，P與Q之間并無(wú)聯(lián)系，但就聯(lián)結(jié)詞的定義來(lái)看，因?yàn)镻的真值為假，Q的真值為真，所以PQ的真值為假。,對(duì)于上述五種聯(lián)結(jié)詞，應(yīng)注意到：復(fù)合命題的真值只取決于構(gòu)成它的各原子命題的真值，而與這些原子命題的內(nèi)容含義無(wú)關(guān)。,三、命題符號(hào)化利用聯(lián)結(jié)詞可以把許多日常語(yǔ)句符號(hào)化?；静襟E如下：,（1）從語(yǔ)句中分析出各原子命題，將它們符號(hào)化；,（2）使用合適的命題聯(lián)結(jié)詞，把原子命題逐個(gè)聯(lián)結(jié)起來(lái)，組成復(fù)合命題的符號(hào)化表示。,例12用符號(hào)形式表示下列命題。（1）如果明天早上下雨或下雪，那么我不去學(xué)校（2）如果明天早上不下雨且不下雪，那么我去學(xué)校。（3）如果明天早上不是雨夾雪，那么我去學(xué)校。（4）只有當(dāng)明天早上不下雨且不下雪時(shí)，我才去學(xué)校。,解令P：明天早上下雨；Q：明天早上下雪；R：我去學(xué)校。,（2）（PQ）R；,（1）（PQ）R；,（4）R（PQ）,（3）(PQ）R；,例12將下列命題符號(hào)化（1）派小王或小李出差；（2）我們不能既劃船又跑步；（3）如果你來(lái)了，那么他唱不唱歌將看你是否伴奏而定；（4）如果李明是體育愛(ài)好者，但不是文藝愛(ài)好者，那么李明不是文體愛(ài)好者；（5）假如上午不下雨，我去看電影，否則就在家里看書(shū)。,解（1）令P：派小王出差；Q：派小李出差。命題符號(hào)化為PQ。,（2）令P：我們劃船；Q：我們跑步。則命題可表示為(PQ）。,（3）令P：你來(lái)了；Q：他唱歌；R：你伴奏。則命題可表示為P（QR）,（4）令P：李明是體育愛(ài)好者；Q：李明是文藝愛(ài)好者。則命題可表示為（PQ）（PQ）,（5）令P：上午下雨；Q：我去看電影；R：我在家讀書(shū)。則命題可表示為（PQ）（PR）。,練習(xí)7-11.判斷下列語(yǔ)句哪些是命題，若是命題，則指出其真值。（1）只有小孩才愛(ài)哭。（2）X+6=Y（3）銀是白的。（4）起來(lái)吧，我的朋友。,(是假),(不是),(是真),(不是),2將下列命題符號(hào)化（1）我看見(jiàn)的既不是小張也不是老李。,解令P：我看見(jiàn)的是小張；Q：我看見(jiàn)的是老李。,則該命題可表示為PQ,（2）如果晚上做完了作業(yè)并且沒(méi)有其它的事，他就會(huì)看電視或聽(tīng)音樂(lè)。,解令P：他晚上做完了作業(yè)；Q：他晚上有其它的事；R：他看電視；S：他聽(tīng)音樂(lè)。則該命題可表示為（PQ）（RS）,7.2命題公式一、命題公式的概念1.命題常元一個(gè)表示確定命題的大寫(xiě)字母。,2命題變?cè)粋€(gè)沒(méi)有指定具體內(nèi)容的命題符號(hào)。,一個(gè)命題變?cè)?dāng)沒(méi)有對(duì)其賦予內(nèi)容時(shí)，它的真值不能確定，一旦用一個(gè)具體的命題代入，它的真值就確定了。,3.命題公式命題公式（或簡(jiǎn)稱公式）是由0、1和命題變?cè)约懊}聯(lián)結(jié)詞按一定的規(guī)則產(chǎn)生的符號(hào)串。,定義7-6（命題公式的遞歸定義。）（1）0，1是命題公式；（2）命題變?cè)敲}公式；（3）如果A是命題公式，則A是命題公式；（4）如果A和B是命題公式，則（AB），（AB）,(AB）,(AB）也是命題公式；有限次地利用上述（1）（4）而產(chǎn)生的符號(hào)串是命題公式。,例1下列符號(hào)串是否為命題公式。（1）P(QPR）；（2）（PQ）（QR）,解（1）不是命題公式。（2）是命題公式。,二、真值指派命題公式代表一個(gè)命題，但只有當(dāng)公式中的每一個(gè)命題變?cè)加靡粋€(gè)確定的命題代入時(shí)，命題公式才有確定的真值，成為命題。,定義77設(shè)F為含有命題變?cè)狿1，P2，,Pn的命題公式，對(duì)P1，P2，,Pn分別指定一個(gè)真值,稱為對(duì)公式F的一組真值指派。,公式與其命題變?cè)g的真值關(guān)系，可以用真值表的方法表示出來(lái)。,例2給出公式F=(（PQ）（QR）)(PR）的真值表。,解公式F的真值表如下：,三、公式類型定義7-8如果對(duì)于命題公式F所包含的命題變?cè)娜魏我唤M真值指派，F(xiàn)的真值恒為真，則稱公式F為重言式（或永真公式），常用“1”表示。相反地，若對(duì)于F所包含的命題變?cè)娜魏我唤M真值指派，F(xiàn)的真值恒為假，則稱公式F為矛盾式（或永假公式），常用“0”表示。如果至少有一組真值指派使公式F的真值為真，則稱F為可滿足公式。,例3構(gòu)造下列命題公式的真值表，并判斷它們是何種類型的公式（1）（PQ）（PQ）；（2）（QP）（PQ）；（3）（PQ）（QR）（PR）。,由上可知：F1是重言式,F2是矛盾式。,(3)的真值表如第4頁(yè)所示，它是可滿足公式。,7.3命題公式的等值關(guān)系和蘊(yùn)含關(guān)系,一、命題公式的等值關(guān)系定義7-9設(shè)A和B是兩個(gè)命題公式,P1,P2,Pn是所有出現(xiàn)于A和B中的命題變?cè)?，如果?duì)于P1,P2,Pn的任一組真值指派，A和B的真值都相同,則稱公式A和B等值，記為AB,稱AB為等值式。,注意：（1）符號(hào)“”與“”的區(qū)別與聯(lián)系。,“”不是聯(lián)結(jié)詞，AB不表示一個(gè)公式，它表示兩個(gè)公式間的一種關(guān)系，即等值關(guān)系。,“”是聯(lián)結(jié)詞，AB是一個(gè)公式。,AB當(dāng)且僅當(dāng)AB是永真公式。,（2）可以驗(yàn)證等值關(guān)系是等價(jià)關(guān)系。即自反性：對(duì)任意公式A，有AA。對(duì)稱性：對(duì)任意公式A，B，若AB，則BA?？蓚鬟f性：對(duì)任意公式A、B、C，若AB，BC，則AC。,（3）當(dāng)A是重言式時(shí)，A1；當(dāng)A是矛盾式時(shí)，則A0。,二、基本的等值式設(shè)P、Q、R是命題變?cè)?，下表中列出?4個(gè)最基本的等值式:,三、等值式的判別有兩種方法：真值表方法，命題演算方法1、真值表方法,例1用真值表方法證明E10：(PQ)PQ,解令：A=(PQ)，B=PQ，構(gòu)造A，B以及AB的真值表如下：,由于公式AB所標(biāo)記的列全為1，因此AB。,0,例2用真值表方法證明E11：PQPQ,解令A(yù)=PQ，B=PQ構(gòu)造A，B以及AB的真值表如下：,由于公式AB所標(biāo)記的列全為1，因此AB.,例3用真值表方法判斷PQPQ是否成立.,解令A(yù)=PQ，B=PQ構(gòu)造A，B以及AB的真值表,由于公式AB所標(biāo)記的列不全為1，AB不是永真公式，因此AB不成立。,(1)代入規(guī)則代入規(guī)則對(duì)于重言式中的任一命題變?cè)霈F(xiàn)的每一處均用同一命題公式代入，得到的仍是重言式。,2等值演算方法,例如F=（PQ）（QP）是重言式，若用公式AB代換命題變?cè)狿得公式F1=（AB）Q）（Q（AB），F(xiàn)1仍是重言式。,注意：因?yàn)锳B當(dāng)且僅當(dāng)AB是重言式。所以，若對(duì)于等值式中的任一命題變?cè)霈F(xiàn)的每一處均用同一命題公式代入，則得到的仍是等值式。,(2)置換規(guī)則定義7-10設(shè)C是命題公式A的一部分（即C是公式A中連續(xù)的幾個(gè)符號(hào)），且C本身也是一個(gè)命題公式，則稱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ò)程。,由代入規(guī)則知前述的基本等值式，不僅對(duì)任意的命題變?cè)狿，Q，R是成立的，而且當(dāng)P，Q，R分別為命題公式時(shí)，這些等值式也成立,例2證明命題公式的等值關(guān)系：（PQ）（RQ）（PR）Q；,證明（PQ）（RQ）（PQ）(RQ)E11（PR）QE3(分配律)(PR)QE10(德.摩根定律)(PR)QE11所以（PQ）（RQ）（PR）Q,例3證明下列命題公式的等值關(guān)系(PQ)(P(PQ)PQ,證明(PQ)(P(PQ)(PQ)(PP)Q)E2(結(jié)合律),(PQ)(PQ)E7(等冪律),(PQ)(PQ)E1(交換律),P(Q(PQ)E2(結(jié)合律),PQE1，E9(交換律，吸收律),例4判別下列公式的類型。（1）Q(P（PQ）)（2）（PQ）P,解（1）Q（P（PQ）Q（P（PQ）E11,E6Q（PP）（PQ）E3Q（1（PQ）E5Q（PQ）E4QPQE10（QQ）PE1,E20E5,E8所以Q(P(PQ)是矛盾式。（2）（PQ）P（PQ）PE11PE9于是該公式是可滿足式。,三、命題公式的蘊(yùn)含關(guān)系定義7-11設(shè)A，B是兩個(gè)公式，若公式AB是重言式，即AB1，則稱公式A蘊(yùn)含公式B，記作AB。稱“AB”為蘊(yùn)含式。,注意：符號(hào)“”和“”的區(qū)別和聯(lián)系與符號(hào)“”與“”的區(qū)別和聯(lián)系類似。,“”不是聯(lián)結(jié)詞，“AB”不是公式，它表示公式A與B之間存在蘊(yùn)含關(guān)系。,“”是聯(lián)系詞，AB是一個(gè)公式。,AB當(dāng)且僅當(dāng)AB是永真公式。,AB是偏序關(guān)系,即自反性：AA。反對(duì)稱：若AB，BA，則AB。傳遞性：若AB，BC，則AC。,反對(duì)稱性的證明：設(shè)AB且BA，,由定義7-11AB1且BA1,于是AB(AB)(BA)E14111因此AB,傳遞性的證明：設(shè)AB，BC，,則AB1，BC1,(ABC)(ABC),(AB)C)(A(BC),(1C)(A1),111,因此AC.,于是ACAC,(AC)(BB),四、基本的蘊(yùn)含式,五、蘊(yùn)含式的判別判定“AB”是否成立的問(wèn)題可轉(zhuǎn)化為判定AB是否為重言式，有下述判定方法：,（1）真值表；（2）等值演算；（3）假定前件A為真；（4）假定后件B為假。,1.真值表方法,例4證明I14：(（PQ）（PR）（QR）)R,證明令公式F=（PQ）（PR）（QR）R，其真值表如下：,公式F對(duì)任意的一組真值指派取值均為1，故F是重言式。,2.等值演算方法例5證明I11：P（PQ）Q,證明（P（PQ）Q,（P（PQ）QE11,（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成立。,4、假定后件B假假定后件B為假，檢查在此情況下，其前件A是否也為假.,例7證明蘊(yùn)含式(PQ)(RS)(PR)(QS),證明令后件(PR)(QS)為假，則PR為真，QS為假,于是P、R均為真，而Q和S至少一個(gè)為假。,由此可知PQ與RS中至少一個(gè)為假,因此(PQ)(RS)為假.,故上述蘊(yùn)含式成立。,練習(xí)7-31判斷下列等值式是否成立（1）（PQ）（RQ）（PR）Q（2）（PQ）（PQ）（PQ）,解（1）（PQ）（RQ）,（PQ）（RQ）E11,（PR）QE3,（PR）QE10,（2）（PQ）（PQ）,(（PQ）（QP）)E6，E10,(（PQ）（QP）)E11,（PQ）E14,（PR）QE11,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一個(gè)命題公式若它具有P1*P2*Pn*的形式（n1），其中Pi*是命題變?cè)狿i或其否定Pi，則稱其為質(zhì)合取式。例如,PQRS是由命題變?cè)狿、Q、R、S組成的一質(zhì)合取式。,定義7-13一個(gè)命題公式若具有P1*P2*Pn*（n1）的形式，其中P*i是命題變?cè)狿i或是其否定Pi，則稱其為質(zhì)析取式。例如,QPR是由命題變?cè)狿、Q、R組成的一質(zhì)析取式。,定理7-4（1）一質(zhì)合取式為永假式的充分必要條件是，它同時(shí)包含某個(gè)命題變?cè)狿及其否定P。（2）一質(zhì)析取式為永真式的充分必要條件是，它同時(shí)包含某個(gè)命題變?cè)狿及其否定P。,證明（2）必要性：假設(shè)A=P1*P2*Pn*為一質(zhì)析取式，且A為一永真式。,(反證法)假設(shè)A式中不同時(shí)包含任一命題變?cè)捌浞穸ǎ?則在A中，當(dāng)Pi*為Pi時(shí)指派Pi取0，當(dāng)Pi*為Pi時(shí)，指派Pi取1。(i=1,2,n).這樣的一組真值指派使A的真值取0，這與A為永真式矛盾。,例如A=P1P2P3.則(P1,P2,P3)=(0,1,0)的指派，使A的真值為0.,充分性：設(shè)A含命題變?cè)狿i和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)也是一合取范式。,二、求公式的析取范式和合取范式,任何一個(gè)命題公式都可以變換為與它等值的析取范式或合取范式。按下列步驟進(jìn)行：,（1）利用E11，E12和E14消去公式中的運(yùn)算符“”和“”；,(2)利用德摩根定律將否定符號(hào)“”向內(nèi)深入，使之只作用于命題變?cè)?（3）利用雙重否定律E6將(P)置換成P；,（4）利用分配律、結(jié)合律將公式歸約為合取范式或析取范式。,例1求F1=(P(QR)S的合取范式和析取范式,解F1(P(QR)SE11,P(QR)SE10,P(QR)S(析取范式)E10,E6,又F1P(QR)S,(PS)(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(PQ)E3,(PP)(PQ)(PQ)(QQ)（析取范式）E3,定理7-5（1）公式A為永真式的充分必要條件是，A的合取范式中每一質(zhì)析取式至少包含一對(duì)互為否定的析取項(xiàng)。,三、利用范式判定公式類型,證明（2）必要性（用反證法）：假設(shè)AA1A2An中某個(gè)Ai不包含一對(duì)互為否定的合取項(xiàng)，,（2）公式A為永假式的充分必要條件是，A的析取范式中每一質(zhì)合取式至少包含一對(duì)互為否定的合取項(xiàng)。,則由定理7-4知，Ai不是矛盾式。,于是存在一組真值指派使Ai取值為真。,對(duì)同一組真值指派，A的取值也必為真，這與A是矛盾式不符，假設(shè)不成立。,充分性：假設(shè)任一Ai(1in)中含有形如PP合取式，其中P為命題變?cè)?。于是由定?-4知，每一Ai(1in)都為矛盾式，因此A1A2An必為矛盾式，即A為矛盾式。,因此A的析取范式中每一質(zhì)合取式至少包含一對(duì)互為否定的合取項(xiàng)。,例3判別公式A=P(P(QP)是否為重言式或矛盾式。,解AP(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,由定理7-5，該公式不是永假公式。,(PP)(PQ)（合取范式）E1，E3,由定理7-5，該公式也不是永真公式。,由上可知，該公式是一可滿足公式。,又P(PQ)(PQ)P,四、主析取范式和主合取范式定義7-16設(shè)有命題變?cè)狿1，P2，,Pn，形如的命題公式稱為是由命題變?cè)狿1，P2，Pn所產(chǎn)生的最小項(xiàng)。而形如的命題公式稱為是由命題變?cè)狿1，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)生的一個(gè)最大項(xiàng)。,定義7-17由不同最小項(xiàng)所組成的析取式，稱為主析取范式。,定義7-18由不同最大項(xiàng)所組成的合取式，稱為主合取范式。,例如(P1P2P3)(P1P2P3)(P1P2P3)是一個(gè)主析取范式。,(P1P2P3)(P1P2P3)(P1P2P3)(P1P2P3)是一個(gè)主合取范式。,例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,E7,五、求公式的主析取范式和主合取范式對(duì)任一給定的公式除了用求范式時(shí)的四個(gè)步驟外，還要利用同一律、等冪律、互否律、分配律等進(jìn)一步將質(zhì)合取式（質(zhì)析取式）變換為最小項(xiàng)（最大項(xiàng)）的形式。,F2(PQ)(PQ),(PQ)(PQ)E11,(PPQ)(QPQ)E3,定理7-6每一個(gè)不為永假的命題公式F（P1,P2,Pn）必與一個(gè)由P1，P2，Pn所產(chǎn)生的主析取范式等值。,永真公式的主析取范式包含所有2n個(gè)最小項(xiàng)。,永假公式的主析取范式是一個(gè)空公式。用0表示。,例5求公式F1=(PQ)(PQ)和公式F2=P(P(QP)的主合取范式,F1(PQ)(PQ)E11,(PQ)(P(QQ)(Q(PP)E5,E4,(PQ)(PQ)(PQ)(PQ)(PQ)E3,(PQ)(PQ)(PQ)(PQ)E7,解F2P(P(QP)E11,(PP)(PQP)E3,11E5,E1,1,定理7-7每一個(gè)不為永真的公式F(P1,P2,Pn）必與一個(gè)由P1,P2,Pn所產(chǎn)生的主合取范式等值。,永假公式的主合取范式包含所有2n個(gè)最大項(xiàng)。,永真公式的主合取范式是一空公式，用1表示。,六、利用主范式判定公式類型1.利用主析取范式判定,(1)若公式F(P1,P2，Pn)的主析取范式包含所有2n個(gè)最小項(xiàng)，則F是永真公式。例如，例4中的F1。,(2)若F的主析取范式是一空公式且為0，則F是永假公式。例如，例4中的F2。,(3)否則，F(xiàn)為可滿足的公式。,2利用主合取范式判定,(1)若公式F（P1,P2,Pn）的主合取范式包含所有2n個(gè)最大項(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(PP)(PQ)(P(QQ),（PQ)(PQ)(PQ)(PQ)(PQ),(PQ)(PQ)(PQ),由此可知F是可滿足公式。,(2)求F的主合取范式,F（Q(PQ)P,PQ,由前分析和舉例可知：僅需求出公式F的任一種主范式即可判定F的類型。,練習(xí)7-41判斷公式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,E8,F的主析取范式既非空公式，又未包含22=4個(gè)項(xiàng)，故F不是重言式和矛盾式，只是可滿足式。,7.5命題演算的推理理論一、推理推理是由已知的命題得到新命題的思維過(guò)程。,定義7-19設(shè)A和B是兩個(gè)命題公式，如果AB，即如果命題公式AB為重言式，則稱B是前提A的結(jié)論或從A推出結(jié)論B。一般地設(shè)H1，H2，,Hn和C是一些命題公式,若蘊(yùn)含式H1H2HnC(*)成立，則稱C是前提集合H1，H2，,Hn的結(jié)論，或稱從前提H1，H2，,Hn能推出結(jié)論C。有時(shí)也記作H1，H2，,HnC,1、真值表法對(duì)于命題公式中所有命題變?cè)拿恳唤M真值指派作出該公式的真值表，看是否為永真。,例1考察結(jié)論C是否是下列前提H1，H2的結(jié)論。（1）H1：PQ，H2：P，C：Q,二、如何判斷由一個(gè)前提集合能否推出某個(gè)結(jié)論,（2）H1：PQ，H2：P，C：Q,在這里，我們不關(guān)心結(jié)論是真還是假，而主要關(guān)心由給定的前提是否能推出這個(gè)結(jié)論來(lái)。,2、真值演算方法例證明,分析根據(jù)題意，需證明,證明,3、“形式證明”方法（1）基本述語(yǔ)形式證明：一個(gè)描述推理過(guò)程的命題序列，其中每個(gè)命題或者是已知的命題，或者是由某些前提所推得的結(jié)論，序列中最后一個(gè)命題就是所要求的結(jié)論，這樣的命題序列稱為形式證明。,有效的證明：如果證明過(guò)程中的每一步所得到的結(jié)論都是根據(jù)推理規(guī)則得到的，則這樣的證明稱作是有效的。有效的結(jié)論：通過(guò)有效的證明而得到結(jié)論，稱作是有效的結(jié)論。,合理的證明：一個(gè)證明是否有效與前提的真假?zèng)]有關(guān)系。如果所有的前提都是真的，那么通過(guò)有效的證明所得到的結(jié)論也是真的。這樣的證明稱作是合理的。合理的結(jié)論：一個(gè)結(jié)論是否有效與它自身的真假?zèng)]有關(guān)系。通過(guò)合理證明而得到的結(jié)論稱作合理的結(jié)論。,(2)推理規(guī)則前提引用規(guī)則：在證明的任何步驟上都可以引用前提。結(jié)論引用規(guī)則：在證明的任何步驟上所得到的結(jié)論都可以在其后的證明中引用。,置換規(guī)則：在證明的任何步驟上，命題公式的子公式都可以用與它等值的其它命題公式置換。代入規(guī)則：在證明的任何步驟上，重言式中的任一命題變?cè)伎梢杂靡幻}公式代入，得到的仍是重言式。,例2證明R（PQ）是前提PQ，QR，PS，S的結(jié)論。,所以PQ，QR，PS，SR（PQ),例3證明RS是前提P（QS），RP和Q的有效結(jié)論。,利用蘊(yùn)含證明規(guī)則：可將例3等價(jià)地改為證明由前提推出結(jié)論S。,例4符號(hào)化下面語(yǔ)句的推理過(guò)程，并指出推理是否正確?！叭绻资枪谲?，則乙或丙將得亞軍；如果乙得亞軍，則甲不能得冠軍；如果丁得亞軍，丙不能得亞軍；事實(shí)是甲已得冠軍，可知丁不能得亞軍”。,解設(shè)A：甲得冠軍；B：乙得亞軍；C：丙得亞軍；D：丁得亞軍。,推理過(guò)程符號(hào)化為A（BC），BA，DC，AD,4、間接證明(或反證法),定義7-20如果對(duì)于出現(xiàn)在公式H1，H2，,Hn中的命題變?cè)娜魏我唤M真值指派，公式H1，H2，,Hn中至少有一個(gè)為假，即它們的合取式H1H2Hn是矛盾式，則稱公式H1，H2，Hn是不相容的。否則稱公式H1，H2,Hn是相容的。,定理7-8若存在一個(gè)公式R，使得H1H2HnRR則公式H1，H2，,Hn是不相容的。,證明設(shè)H1H2Hn=RR，,而RR是矛盾式，所以前件H1Hn必永假。因此，H1，H2，,Hn是不相容的。,則意味著（H1H2Hn）（RR）是重言式，,為了證明H1、H2、HnC，利用定理7-8，將C添加到這一組前提中，轉(zhuǎn)化為證明H1H2HnCRR,于是得出H1、H2、Hn、C是不相容的。,即H1H2HnC是永假公式。,這意味著當(dāng)H1H2Hn為真時(shí)，C必為假，因而C必為真。,例5證明：RQ、RS、SQ、PQP,用反證法，將（P）作為附加前提，添加到前提集合中，然后推出矛盾。證明,因此（RQ）（RS）（SQ）（PQ)P,練習(xí)7-5用形式證明方法證明：（1）PQ是前提（PQ）R，RS，S的結(jié)論。,因此，（PQ）R，RS，SPQ,習(xí)題1判斷下列推理是否正確如果這里有球賽，則通行是困難的；如果他們按指定的時(shí)間到達(dá)，則通行是不困難的；他們按指定時(shí)間到達(dá)了，所以這里沒(méi)有球賽。,解先將已知條件符號(hào)化,令P：這里有球賽；Q：通行是困難的；R：他們按指定的時(shí)間到達(dá)了。,編號(hào)公式依據(jù)（1）RQ前提,因此上述推理正確。,（2）R前提,（3）Q（1），（2）;I11,（4）PQ前提,（5）P（3），（4）；I12,則上述推理過(guò)程符號(hào)化為PQ，RQ，RP,2.張三說(shuō)李四在說(shuō)謊，李四說(shuō)王五在說(shuō)謊，王五說(shuō)張三、李四都在說(shuō)謊。問(wèn)張三、李四、王五三人，到底誰(shuí)說(shuō)真話，誰(shuí)說(shuō)假話？,解先將簡(jiǎn)單命題符號(hào)化。令P：張三說(shuō)真話；Q：李四說(shuō)真話；R：王五說(shuō)真話，由題意知推理的前提為：PQ，PQ，QR，QR，R（PQ），R（PQ）。下面根據(jù)已知前提進(jìn)行形式推理。,因此，由上述推理知張三說(shuō)假話，王五說(shuō)假話，只有李四說(shuō)真話。,