離散數(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è)的一門核心基礎(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é)好這門課程，首先必須充分認(rèn)識(shí)到這門課程的上述特點(diǎn)，需要做到以下幾點(diǎn)：,1熟讀教材。準(zhǔn)確理解各個(gè)概念和定理的含義（結(jié)合多個(gè)例子來(lái)理解），必要的推理過(guò)程要看懂、理解（它可以幫助你熟悉和深刻理解定理的含義）。,2獨(dú)立思考，大量練習(xí)。僅靠熟讀教材并不能將書本上的知識(shí)變成你自己的知識(shí)，在熟讀教材的基礎(chǔ)上，必須通過(guò)大量練習(xí)，獨(dú)立思考來(lái)真正獲取知識(shí)。,3注重抽象思維能力的培養(yǎng)。數(shù)學(xué)與其他學(xué)科相比較具有較高的抽象性，而離散數(shù)學(xué)的抽象性特點(diǎn)更為顯著，它有著大量抽象的概念和抽象的推理，要學(xué)好這門課程必須具有較好的抽象思維能力，才能深入地掌握課程內(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)。（教材的第四、五、六、七章）,第三部分圖論。包括圖的基本概念，幾種特殊的圖。（教材的第八章）,五、教材及參考書,2參考書：《離散數(shù)學(xué)習(xí)題題解》洪帆、付小青編，華中理工大學(xué)出版社。,1、教材：《離散數(shù)學(xué)基礎(chǔ)》第二版，洪帆主編，華中理工大學(xué)出版社。,第七章命題邏輯數(shù)理邏輯是用數(shù)學(xué)方法研究思維規(guī)律的一門學(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)把門關(guān)上。（3）南京是中國(guó)的首都。（4）你吃飯了嗎？（5）x=3。（6）啊，真美呀！(7)明年春節(jié)是個(gè)大晴天。,解語(yǔ)句（1）,（3）,（5），(7)是陳述句（1）、（3）、(7)是命題,用真值來(lái)描述命題是“真”還是“假”。分別用“1”和“0”表示,命題用大寫的拉丁字母A、B、C、……P、Q、……或者帶下標(biāo)的大寫的字母來(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：張平或者正在釣魚或者正在睡覺(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ù)合命題，記作“P∧Q”（讀作“P且Q”）。,當(dāng)且僅當(dāng)命題P和Q均取值為真時(shí)，P∧Q才取值為真。,例5設(shè)P：我們?nèi)タ措娪?。Q：房間里有十張桌子。則P∧Q表示“我們?nèi)タ措娪安⑶曳块g里有十張桌子。”,3.析取“∨”定義7-3由命題P和Q利用“∨”組成的復(fù)合命題，稱為析取式復(fù)合命題，記作“P∨Q”（讀作“P或Q”）。,當(dāng)且僅當(dāng)P和Q至少有一個(gè)取值為真時(shí)，P∨Q取值為真。,例6將命題“他可能是100米或400米賽跑的冠軍?！狈?hào)化。,解令P：他可能是100米賽跑冠軍；Q：他可能是400米賽跑冠軍。,則命題可表示為P∨Q。,設(shè)P、Q是兩個(gè)命題，P異或Q是一個(gè)復(fù)合命題，記作P∨Q。,,4.蘊(yùn)含“→”定義7-4由命題P和Q利用“→”組成的復(fù)合命題，稱為蘊(yùn)含式復(fù)合命題，記作“P→Q”（讀作“如果P，則Q”）。,當(dāng)P為真，Q為假時(shí)，P→Q為假，否則P→Q為真。,例8將命題“如果我得到這本小說(shuō)，那么我今夜就讀完它?！狈?hào)化。,解令P：我得到這本小說(shuō)；Q：我今夜就讀完它。于是上述命題可表示為P→Q。,例9若P：雪是黑色的；Q：太陽(yáng)從西邊升起；R：太陽(yáng)從東邊升起。則P→Q和P→R所表示的命題都是真的.,5．等值“?”定義7-5由命題P和Q，利用“?”組成的復(fù)合命題，稱為等值式復(fù)合命題，記作“P?Q”（讀作“P當(dāng)且僅當(dāng)Q”）。,當(dāng)P和Q的真值相同時(shí),P?Q取真,否則取假。,例10非本倉(cāng)庫(kù)工作人員，一律不得入內(nèi)。,解令P：某人是倉(cāng)庫(kù)工作人員；Q：某人可以進(jìn)入倉(cāng)庫(kù)。,則上述命題可表示為P?Q。,例11黃山比喜馬拉雅山高，當(dāng)且僅當(dāng)3是素?cái)?shù)令P：黃山比喜馬拉雅山高；Q：3是素?cái)?shù)本例可符號(hào)化為P?Q,從漢語(yǔ)的語(yǔ)義看，P與Q之間并無(wú)聯(lián)系，但就聯(lián)結(jié)詞?的定義來(lái)看，因?yàn)镻的真值為假，Q的真值為真，所以P?Q的真值為假。,對(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）（P∧Q）→R；,（1）（P∨Q）→R；,（4）R→（P∧Q）,（3）(P∧Q）→R；,例12．將下列命題符號(hào)化（1）派小王或小李出差；（2）我們不能既劃船又跑步；（3）如果你來(lái)了，那么他唱不唱歌將看你是否伴奏而定；（4）如果李明是體育愛(ài)好者，但不是文藝愛(ài)好者，那么李明不是文體愛(ài)好者；（5）假如上午不下雨，我去看電影，否則就在家里看書。,解（1）令P：派小王出差；Q：派小李出差。命題符號(hào)化為P∨Q。,（2）令P：我們劃船；Q：我們跑步。則命題可表示為(P∧Q）。,（3）令P：你來(lái)了；Q：他唱歌；R：你伴奏。則命題可表示為P→（Q?R）,（4）令P：李明是體育愛(ài)好者；Q：李明是文藝愛(ài)好者。則命題可表示為（P∧Q）→（P∧Q）,（5）令P：上午下雨；Q：我去看電影；R：我在家讀書。則命題可表示為（P→Q）∧（P→R）。,練習(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)的是老李。,則該命題可表示為P∧Q,（2）如果晚上做完了作業(yè)并且沒(méi)有其它的事，他就會(huì)看電視或聽(tīng)音樂(lè)。,解令P：他晚上做完了作業(yè)；Q：他晚上有其它的事；R：他看電視；S：他聽(tīng)音樂(lè)。則該命題可表示為（P∧Q）→（R∨S）,7.2命題公式一、命題公式的概念1.命題常元一個(gè)表示確定命題的大寫字母。,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是命題公式，則（A∨B），（A∧B）,(A→B）,(A?B）也是命題公式；有限次地利用上述（1）—（4）而產(chǎn)生的符號(hào)串是命題公式。,例1下列符號(hào)串是否為命題公式。（1）P→(Q∧PR）；（2）（P∨Q）→（（Q∧R））,解（1）不是命題公式。（2）是命題公式。,二、真值指派命題公式代表一個(gè)命題，但只有當(dāng)公式中的每一個(gè)命題變?cè)加靡粋€(gè)確定的命題代入時(shí)，命題公式才有確定的真值，成為命題。,定義7—7設(shè)F為含有命題變?cè)狿1，P2，…,Pn的命題公式，對(duì)P1，P2，…,Pn分別指定一個(gè)真值,稱為對(duì)公式F的一組真值指派。,公式與其命題變?cè)g的真值關(guān)系，可以用真值表的方法表示出來(lái)。,例2給出公式F=(（P∨Q）?（Q∧R）)?(P∧R）的真值表。,解公式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）（P?Q）?（P?Q）；（2）（Q→P）∧（P∧Q）；（3）（（P∨Q）→（Q∧R））→（P∧R）。,由上可知：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等值，記為A?B,稱A?B為等值式。,注意：（1）符號(hào)“?”與“?”的區(qū)別與聯(lián)系。,“?”不是聯(lián)結(jié)詞，A?B不表示一個(gè)公式，它表示兩個(gè)公式間的一種關(guān)系，即等值關(guān)系。,“?”是聯(lián)結(jié)詞，A?B是一個(gè)公式。,A?B當(dāng)且僅當(dāng)A?B是永真公式。,（2）可以驗(yàn)證等值關(guān)系是等價(jià)關(guān)系。即自反性：對(duì)任意公式A，有A?A。對(duì)稱性：對(duì)任意公式A，B，若A?B，則B?A。可傳遞性：對(duì)任意公式A、B、C，若A?B，B?C，則A?C。,（3）當(dāng)A是重言式時(shí)，A?1；當(dāng)A是矛盾式時(shí)，則A?0。,二、基本的等值式設(shè)P、Q、R是命題變?cè)?，下表中列出?4個(gè)最基本的等值式:,三、等值式的判別有兩種方法：真值表方法，命題演算方法1、真值表方法,例1用真值表方法證明E10：?(P?Q)??P??Q,解令：A=?(P?Q)，B=?P??Q，構(gòu)造A，B以及A?B的真值表如下：,,,,,由于公式A?B所標(biāo)記的列全為1，因此A?B。,0,例2用真值表方法證明E11：P?Q??P?Q,解令A(yù)=P?Q，B=?P?Q構(gòu)造A，B以及A?B的真值表如下：,由于公式A?B所標(biāo)記的列全為1，因此A?B.,例3用真值表方法判斷P?Q??P??Q是否成立.,解令A(yù)=P?Q，B=?P??Q構(gòu)造A，B以及A?B的真值表,由于公式A?B所標(biāo)記的列不全為1，A?B不是永真公式，因此A?B不成立。,(1)代入規(guī)則代入規(guī)則對(duì)于重言式中的任一命題變?cè)霈F(xiàn)的每一處均用同一命題公式代入，得到的仍是重言式。,2．等值演算方法,例如F=（P?Q）?（?Q??P）是重言式，若用公式A∧B代換命題變?cè)狿得公式F1=（（A∧B）?Q）?（?Q??（A∧B）），F(xiàn)1仍是重言式。,注意：因?yàn)锳?B當(dāng)且僅當(dāng)A?B是重言式。所以，若對(duì)于等值式中的任一命題變?cè)霈F(xiàn)的每一處均用同一命題公式代入，則得到的仍是等值式。,(2)置換規(guī)則定義7-10設(shè)C是命題公式A的一部分（即C是公式A中連續(xù)的幾個(gè)符號(hào)），且C本身也是一個(gè)命題公式，則稱C為公式A的子公式。,例如設(shè)公式A=（?P∨Q）?（（P?Q）∨（R∧?S））。,則?P∨Q，P?Q，（P?Q）∨（R∧?S）等均是A的子公式，,但?P∨，P?和?Q等均不是A的子公式，,置換規(guī)則設(shè)C是公式A的子公式，C?D。如果將公式A中的子公式C置換成公式D之后，得到的公式是B，則A?B。,(3)等值演算等值演算是指利用已知的一些等值式，根據(jù)置換規(guī)則、代入規(guī)則以及等值關(guān)系的可傳遞性推導(dǎo)出另外一些等值式的過(guò)程。,由代入規(guī)則知前述的基本等值式，不僅對(duì)任意的命題變?cè)狿，Q，R是成立的，而且當(dāng)P，Q，R分別為命題公式時(shí)，這些等值式也成立,例2證明命題公式的等值關(guān)系：（P?Q）∧（R?Q）?（P∨R）?Q；,證明（P?Q）∧（R?Q）?（?P∨Q）∧(?R∨Q)E11?（?P∧?R）∨QE3ˊ(分配律)??(P∨R)∨QE10(德.摩根定律)?(P∨R)?QE11所以（P?Q）∧（R?Q）?（P∨R）?Q,例3證明下列命題公式的等值關(guān)系(P?Q)?(?P?(?P?Q))??P?Q,證明(P?Q)?(?P?(?P?Q))?(P?Q)?((?P??P)?Q)E2(結(jié)合律),?(P?Q)?(?P?Q)E7(等冪律),?(?P?Q)?(P?Q)E1(交換律),??P?(Q?(P?Q))E2(結(jié)合律),??P?QE?1，E9(交換律，吸收律),例4判別下列公式的類型。（1）Q∧?(?P?（?P∧Q）)（2）（P?Q）∧?P,解（1）Q∧?（?P?（?P∧Q））?Q∧?（P∨（?P∧Q））E11,E6?Q∧?（（P∨?P）∧（P∨Q））E3ノ?Q∧?（1∧（P∨Q））E5?Q∧?（P∨Q）E4ノ?Q∧?P∧?QE10?（Q∧?Q）∧?PE1ノ,E2?0E5ノ,E8ノ所以Q∧?(?P?(?P∧Q))是矛盾式。（2）（P?Q）∧?P?（?P∨Q）∧?PE11??PE9ノ于是該公式是可滿足式。,三、命題公式的蘊(yùn)含關(guān)系定義7-11設(shè)A，B是兩個(gè)公式，若公式A?B是重言式，即A?B?1，則稱公式A蘊(yùn)含公式B，記作A?B。稱“A?B”為蘊(yùn)含式。,注意：符號(hào)“?”和“?”的區(qū)別和聯(lián)系與符號(hào)“?”與“?”的區(qū)別和聯(lián)系類似。,“?”不是聯(lián)結(jié)詞，“A?B”不是公式，它表示公式A與B之間存在蘊(yùn)含關(guān)系。,“?”是聯(lián)系詞，A?B是一個(gè)公式。,A?B當(dāng)且僅當(dāng)A?B是永真公式。,A?B是偏序關(guān)系,即自反性：A?A。反對(duì)稱：若A?B，B?A，則A?B。傳遞性：若A?B，B?C，則A?C。,反對(duì)稱性的證明：設(shè)A?B且B?A，,由定義7-11A?B?1且B?A?1,于是A?B?(A?B)?(B?A)E14?1?1?1因此A?B,傳遞性的證明：設(shè)A?B，B?C，,則A?B?1，B?C?1,?(?A?B?C)?(?A??B?C),?((A?B)?C)?(?A?(B?C)),?(1?C)?(?A?1),?1?1?1,因此A?C.,于是A?C??A?C,?(?A?C)?(B??B),四、基本的蘊(yùn)含式,五、蘊(yùn)含式的判別判定“A?B”是否成立的問(wèn)題可轉(zhuǎn)化為判定A?B是否為重言式，有下述判定方法：,（1）真值表；（2）等值演算；（3）假定前件A為真；（4）假定后件B為假。,1.真值表方法,例4證明I14：(（P∨Q）∧（P?R）∧（Q?R）)?R,證明令公式F=（（P∨Q）∧（P?R）∧（Q?R））?R，其真值表如下：,公式F對(duì)任意的一組真值指派取值均為1，故F是重言式。,2.等值演算方法例5證明I11：P∧（P?Q）?Q,證明（P∧（P?Q））?Q,??（P∧（?P∨Q））∨QE11,?（?P∨?（?P∨Q））∨E10ノ,?（?P∨Q）∨?（?P∨Q）E2,?1代入規(guī)則,E5因此P∧（P?Q）?Q,3.假定前件A真假定前件A為真，檢查在此情況下，其后件B是否也為真。,例6證明I12:?Q∧（P?Q）??P,證明令前件?Q∧（P?Q）為真，,則?Q為真,且P?Q為真。,于是Q為假，因而P也為假。由此?P為真。,故蘊(yùn)含式I12成立。,4、假定后件B假假定后件B為假，檢查在此情況下，其前件A是否也為假.,例7證明蘊(yùn)含式(P?Q)?(R?S)?(P?R)?(Q?S),證明令后件(P?R)?(Q?S)為假，則P?R為真，Q?S為假,,于是P、R均為真，而Q和S至少一個(gè)為假。,由此可知P?Q與R?S中至少一個(gè)為假,,因此(P?Q)?(R?S)為假.,故上述蘊(yùn)含式成立。,練習(xí)7-31．判斷下列等值式是否成立（1）（P?Q）∧（R?Q）?（P∨R）?Q（2）?（P?Q）?（P∧?Q）∨（?P∧Q）,解（1）（P?Q）∧（R?Q）,?（?P∨Q）∧（?R∨Q）E11,?（?P∧?R）∨QE3ノ,??（P∨R）∨QE10,（2）（P∧?Q）∨（?P∧Q）,??(（?P∨Q）∧（?Q∨P）)E6，E10ノ,??(（P?Q）∧（Q?P）)E11,??（P?Q）E14,?（P∨R）?QE11,2．判定蘊(yùn)含式P?（Q?R）?（P?Q）?（P?R）是否成立,解假定后件（P?Q）?（P?R）為假，,則P?Q為真，P?R為假。,由P?R為假,得P為真，R為假。,又P?Q為真，故得Q為真。,于是P為真，Q?R為假。,從而P?（Q?R）為假。,因此蘊(yùn)含式成立。,7.4范式一、析取范式和合取范式,定義7-12一個(gè)命題公式若它具有P1*∧P2*∧…∧Pn*的形式（n≥1），其中Pi*是命題變?cè)狿i或其否定Pi，則稱其為質(zhì)合取式。例如,P∧Q∧R∧S是由命題變?cè)狿、Q、R、S組成的一質(zhì)合取式。,定義7-13一個(gè)命題公式若具有P1*∨P2*∨…∨Pn*（n≥1）的形式，其中P*i是命題變?cè)狿i或是其否定Pi，則稱其為質(zhì)析取式。例如,Q∨P∨R是由命題變?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=P1∨P2∨P3.則(P1,P2,P3)=(0,1,0)的指派，使A的真值為0.,充分性：設(shè)A含命題變?cè)狿i和Pi，而Pi∨Pi是永真式，由結(jié)合律和零一律，A的真值必為1，故A也是永真式。,定義7-14質(zhì)合取式的析取稱為析取范式。即具有A1∨A2∨…∨An(n≥1)的形式的公式，其中Ai是質(zhì)合取式。,例如，F(xiàn)1=P∨(P∧Q)∨R∨(?P∧?Q∧R)是一析取范式。,定義7-15質(zhì)析取式的合取稱為合取范式。即具有A1∧A2∧…∧An(n≥1)的形式的公式，其中Ai是質(zhì)析取式。,例如，F(xiàn)2=?P∧(P∨Q)∧R∧(P∨?Q∨R)是一合取范式。F3=(?P∨R∨Q)∧(P∨Q)∧R∧(P∨?R)也是一合取范式。,二、求公式的析取范式和合取范式,任何一個(gè)命題公式都可以變換為與它等值的析取范式或合取范式。按下列步驟進(jìn)行：,（1）利用E11，E12和E14消去公式中的運(yùn)算符“?”和“?”；,(2)利用德?摩根定律將否定符號(hào)“?”向內(nèi)深入，使之只作用于命題變?cè)?（3）利用雙重否定律E6將?(?P)置換成P；,（4）利用分配律、結(jié)合律將公式歸約為合取范式或析取范式。,例1求F1=(P∧(Q?R))?S的合取范式和析取范式,解F1??(P∧(?Q∨R))∨SE11,??P∨?(?Q∨R)∨SE10ノ,??P∨(Q∧?R)∨S(析取范式)E10,E6,又F1??P∨(Q∧?R)∨S,?(?P∨S)∨(Q∧?R)E1,E2,?(?P∨S∨Q)∧(?P∨S∨?R)（合取范式）E3ノ,另外由F1?(?P∨S∨Q)∧(?P∨S∨?R),?(?P∧(?P∨S∨?R))∨(S∧(?P∨S∨?R))∨(Q∧(?P∨S∨?R))E3,??P∨S∨(Q∧?P)∨(Q∧S)∨(Q∧?R)（析取范式）E9,E13,例2求F2=?(P∨Q)?(P∧Q)的析取范式、合取范式。,解F2?(?(P∨Q)?(P∧Q))∧((P∧Q)??(P∨Q))E14,?((P∨Q)∨(P∧Q))∧(?(P∧Q)∨?(P∨Q))E11,E6,?(P∨(Q∨(P∧Q)))∧(?P∨?Q∨(?P∧?Q))E2,E10ノ,E10,?(P∨Q)∧(?P∨?Q)（合取范式）E2,E9,?(P∧(?P∨?Q))∨(Q∧(?P∨?Q))E3,?(P∧?P)∨(P∧?Q)∨(?P∧Q)∨(Q∧?Q)（析取范式）E3,定理7-5（1）公式A為永真式的充分必要條件是，A的合取范式中每一質(zhì)析取式至少包含一對(duì)互為否定的析取項(xiàng)。,三、利用范式判定公式類型,證明（2）必要性（用反證法）：假設(shè)A＝A1∨A2∨…∨An中某個(gè)Ai不包含一對(duì)互為否定的合取項(xiàng)，,（2）公式A為永假式的充分必要條件是，A的析取范式中每一質(zhì)合取式至少包含一對(duì)互為否定的合取項(xiàng)。,則由定理7-4知，Ai不是矛盾式。,于是存在一組真值指派使Ai取值為真。,對(duì)同一組真值指派，A的取值也必為真，這與A是矛盾式不符，假設(shè)不成立。,充分性：假設(shè)任一Ai(1≤i≤n)中含有形如P∧P合取式，其中P為命題變?cè)?。于是由定?-4知，每一Ai(1≤i≤n)都為矛盾式，因此A1∨A2∨…∨An必為矛盾式，即A為矛盾式。,因此A的析取范式中每一質(zhì)合取式至少包含一對(duì)互為否定的合取項(xiàng)。,例3判別公式A=P?(P∧(Q?P))是否為重言式或矛盾式。,解A??P∨(P∧(?Q∨P))E11,??P∨(P∧?Q)∨(P∧P)(析取范式)E3,根據(jù)定理7-5，A不是矛盾式。,又A??P∨(P∧(?Q∨P)),?（?P∨P）∧（?P∨?Q∨P)（合取范式）E3ノ,由定理7-5知，A是重言式。,例4利用范式判斷公式P?(P?Q)的類型。,解P?(P?Q)?(P?(P?Q))?(?P??(P?Q))E12,?(P?Q)?(?P?(?P??Q))E?10,?(P?Q)??P(析取范式)E?9,由定理7-5，該公式不是永假公式。,?(P??P)?(?P?Q)（合取范式）E1，E?3,由定理7-5，該公式也不是永真公式。,由上可知，該公式是一可滿足公式。,又P?(P?Q)?(P?Q)??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)?Pi(i=1,2,…n).,例如,P1∧P2∧P3，?P1∧P2∧?P3均是由P1，P2，P3所產(chǎn)生的最小項(xiàng)。P1∨?P2∨P3是由P1，P2，P3產(chǎn)生的一個(gè)最大項(xiàng)。,定義7-17由不同最小項(xiàng)所組成的析取式，稱為主析取范式。,定義7-18由不同最大項(xiàng)所組成的合取式，稱為主合取范式。,例如(?P1??P2?P3)?(?P1?P2?P3)?(P1?P2?P3)是一個(gè)主析取范式。,(P1??P2?P3)?(P1?P2?P3)?(?P1??P2??P3)?(?P1?P2??P3)是一個(gè)主合取范式。,例4求公式F1=P?(P?(Q?P))和公式F2=(P?Q)?(P??Q)的主析取范式.,解F1??P∨(P∧(?Q∨P))E11,??P∨(P∧?Q)∨(P∧P)E3,?(?P∧(Q∨?Q))∨(P∧?Q)∨(P∧(Q∨?Q))E7ノ,E4ノ,E5,?(?P∧Q)∨(?P∧?Q)∨(P∧?Q)∨(P∧Q)∨(P∧?Q)E3,?(?P∧Q)∨(?P∧?Q)∨(P∧?Q)∨(P∧Q)E1,E7,五、求公式的主析取范式和主合取范式對(duì)任一給定的公式除了用求范式時(shí)的四個(gè)步驟外，還要利用同一律、等冪律、互否律、分配律等進(jìn)一步將質(zhì)合取式（質(zhì)析取式）變換為最小項(xiàng)（最大項(xiàng)）的形式。,F2?(P?Q)?(P??Q),?(?P?Q)?(P??Q)E11,?(?P?P??Q)?(Q?P??Q)E3,定理7-6每一個(gè)不為永假的命題公式F（P1,P2,…,Pn）必與一個(gè)由P1，P2，…，Pn所產(chǎn)生的主析取范式等值。,永真公式的主析取范式包含所有2n個(gè)最小項(xiàng)。,永假公式的主析取范式是一個(gè)空公式。用0表示。,例5求公式F1=(P?Q)?(P??Q)和公式F2=P?(P?(Q?P))的主合取范式,F1?(?P?Q)?(P??Q)E11,?(?P?Q)?(P?(Q??Q))?(?Q?(P??P))E?5,E4,?(?P?Q)?(P?Q)?(P??Q)?(P??Q)?(?P??Q)E?3,?(P?Q)?(P??Q)?(?P?Q)?(?P??Q)E?7,解F2??P∨(P∧(?Q∨P))E11,?(?P∨P)∧(?P∨?Q∨P)E3ノ,?1∧1E5,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?(P?Q))?P的主范式并判定公式的類型.,解(1)求F的主析取范式,F??(Q?(?P?Q))?P,??Q?(P??Q)?P,?(?Q?(P??P))?(P??Q)?(P?(Q??Q)),?（P??Q)?(?P??Q)?(P??Q)?(P?Q)?(P??Q),?(P?Q)?(P??Q)?(?P??Q),由此可知F是可滿足公式。,(2)求F的主合取范式,F?（?Q?(P??Q))?P,?P??Q,由前分析和舉例可知：僅需求出公式F的任一種主范式即可判定F的類型。,練習(xí)7-41．判斷公式F=(?P∨?Q)→(P??Q)是否為重言式或矛盾式？,解F??(?P∨?Q)∨((P→?Q)∧(?Q→P))E11,?(P∧Q)∨((?P∨?Q)∧(Q∨P))E10,E6,E11,?(P∧Q)∨((?P∧(Q∨P))∨(?Q∧(Q∨P)))E3,?(P∧Q)∨(?P∧Q)∨(?P∧P)∨(?Q∧Q)∨(?Q∧P)E3,?(P∧Q)∨(?P∧Q)∨(?Q∧P)E5ノ,E8,F的主析取范式既非空公式，又未包含22=4個(gè)項(xiàng)，故F不是重言式和矛盾式，只是可滿足式。,7.5命題演算的推理理論一、推理推理是由已知的命題得到新命題的思維過(guò)程。,定義7-19設(shè)A和B是兩個(gè)命題公式，如果A?B，即如果命題公式A?B為重言式，則稱B是前提A的結(jié)論或從A推出結(jié)論B。一般地設(shè)H1，H2，…,Hn和C是一些命題公式,若蘊(yùn)含式H1∧H2∧…∧Hn?C(*)成立，則稱C是前提集合{H1，H2，…,Hn}的結(jié)論，或稱從前提H1，H2，…,Hn能推出結(jié)論C。有時(shí)也記作H1，H2，…,Hn?C,1、真值表法對(duì)于命題公式中所有命題變?cè)拿恳唤M真值指派作出該公式的真值表，看是否為永真。,例1考察結(jié)論C是否是下列前提H1，H2的結(jié)論。（1）H1：P→Q，H2：P，C：Q,二、如何判斷由一個(gè)前提集合能否推出某個(gè)結(jié)論,（2）H1：P→Q，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∧（P∨Q）是前提P∨Q，Q→R，P→S，S的結(jié)論。,所以P∨Q，Q→R，P→S，S?R∧（P∨Q),例3證明R→S是前提P→（Q→S），R∨P和Q的有效結(jié)論。,利用蘊(yùn)含證明規(guī)則：可將例3等價(jià)地改為證明由前提推出結(jié)論S。,例4符號(hào)化下面語(yǔ)句的推理過(guò)程，并指出推理是否正確。“如果甲是冠軍，則乙或丙將得亞軍；如果乙得亞軍，則甲不能得冠軍；如果丁得亞軍，丙不能得亞軍；事實(shí)是甲已得冠軍，可知丁不能得亞軍”。,解設(shè)A：甲得冠軍；B：乙得亞軍；C：丙得亞軍；D：丁得亞軍。,推理過(guò)程符號(hào)化為A→（B∨C），B→A，D→C，A?D,4、間接證明(或反證法),定義7-20如果對(duì)于出現(xiàn)在公式H1，H2，…,Hn中的命題變?cè)娜魏我唤M真值指派，公式H1，H2，…,Hn中至少有一個(gè)為假，即它們的合取式H1∧H2∧…∧Hn是矛盾式，則稱公式H1，H2，…Hn是不相容的。否則稱公式H1，H2…,Hn是相容的。,定理7-8若存在一個(gè)公式R，使得H1∧H2∧…∧Hn?R∧R則公式H1，H2，…,Hn是不相容的。,證明設(shè)H1∧H2∧…∧Hn==>R∧R，,而R∧R是矛盾式，所以前件H1∧…∧Hn必永假。因此，H1，H2，…,Hn是不相容的。,則意味著（H1∧H2∧…∧Hn）→（R∧R）是重言式，,為了證明H1、H2、…、Hn?C，利用定理7-8，將?C添加到這一組前提中，轉(zhuǎn)化為證明H1?H2?…?Hn?C?R??R,于是得出H1、H2、…、Hn、?C是不相容的。,即H1?H2?…?Hn??C是永假公式。,這意味著當(dāng)H1?H2?…?Hn為真時(shí)，?C必為假，因而C必為真。,例5證明：R→Q、R∨S、S→Q、P→Q?P,用反證法，將（P）作為附加前提，添加到前提集合中，然后推出矛盾。證明,因此（R→Q）∧（R∨S）∧（S→Q）∧（P→Q)?P,練習(xí)7-5用形式證明方法證明：（1）P∨Q是前提（P∧Q）→R，R∨S，S的結(jié)論。,因此，（P∧Q）→R，R∨S，S?P∨Q,習(xí)題1．判斷下列推理是否正確如果這里有球賽，則通行是困難的；如果他們按指定的時(shí)間到達(dá)，則通行是不困難的；他們按指定時(shí)間到達(dá)了，所以這里沒(méi)有球賽。,解先將已知條件符號(hào)化,令P：這里有球賽；Q：通行是困難的；R：他們按指定的時(shí)間到達(dá)了。,編號(hào)公式依據(jù)（1）R→Q前提,因此上述推理正確。,（2）R前提,（3）Q（1），（2）;I11,（4）P→Q前提,（5）P（3），（4）；I12,則上述推理過(guò)程符號(hào)化為P→Q，R→Q，R?P,2.張三說(shuō)李四在說(shuō)謊，李四說(shuō)王五在說(shuō)謊，王五說(shuō)張三、李四都在說(shuō)謊。問(wèn)張三、李四、王五三人，到底誰(shuí)說(shuō)真話，誰(shuí)說(shuō)假話？,解先將簡(jiǎn)單命題符號(hào)化。令P：張三說(shuō)真話；Q：李四說(shuō)真話；R：王五說(shuō)真話，由題意知推理的前提為：P→Q，P→Q，Q→R，Q→R，R→（P∧Q），R→（P∨Q）。下面根據(jù)已知前提進(jìn)行形式推理。,因此，由上述推理知張三說(shuō)假話，王五說(shuō)假話，只有李四說(shuō)真話。,