離散數(shù)學(xué)講義第二章命題邏輯.ppt

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

第二章命題邏輯數(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)容如下：2.1命題的概念和表示2.2邏輯聯(lián)結(jié)詞2.3命題演算的合適公式2.4等價(jià)與蘊(yùn)含2.5對(duì)偶與范式2.6命題演算的推理理論,例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是命題,原子命題：由簡(jiǎn)單句形成的命題。,復(fù)合命題：由一個(gè)或幾個(gè)原子命題通過(guò)聯(lián)結(jié)詞的聯(lián)接而構(gòu)成的命題。,例3A：李明是三好學(xué)生。B：李明既是三好學(xué)生又是足球隊(duì)員C:明天天氣晴朗.D：張平或者正在釣魚(yú)或者正在睡覺(jué)。E：如果明天天氣晴朗，那么我們舉行運(yùn)動(dòng)會(huì)。,解A、C是原子命題B、D、E是復(fù)合命題,2.2邏輯聯(lián)結(jié)詞,1.否定“”,定義2.2.1設(shè)P是一個(gè)命題，則P的否定是一個(gè)復(fù)合命題，稱為P的否命題，記作“P”(讀作“非P”)。,例4設(shè)P：上海是一個(gè)城市；Q：每個(gè)自然數(shù)都是偶數(shù)。則有P：上海不是一個(gè)城市;Q：并非每個(gè)自然數(shù)都是偶數(shù)。,命題P取值為真時(shí)，命題P取值為假；命題P取值為假時(shí)，命題P取值為真。,2．合取“∧”定義2.2.2設(shè)P和Q是兩個(gè)命題，則P和Q的合取是一個(gè)復(fù)合命題，記作“P∧Q”（讀作“P且Q”）。,例5設(shè)P：我們?nèi)タ措娪啊：房間里有十張桌子。則P∧Q表示“我們?nèi)タ措娪安⑶曳块g里有十張桌子。”,當(dāng)且僅當(dāng)命題P和Q均取值為真時(shí)，P∧Q才取值為真。,3.析取“∨”定義2.2.3設(shè)P和Q是兩個(gè)命題，則P和Q的析取是一個(gè)復(fù)合命題，記作“P∨Q”（讀作“P或Q”）。,例6設(shè)命題P：他可能是100米賽跑冠軍；Q：他可能是400米賽跑冠軍。,則命題P∨Q表示：他可能是100米或400米賽跑的冠軍。,當(dāng)且僅當(dāng)P和Q至少有一個(gè)取值為真時(shí)，P∨Q取值為真。,4.蘊(yùn)含“→”定義2.2.4設(shè)P和Q是兩個(gè)命題，則它們的條件命題是一個(gè)復(fù)合命題，記作“P→Q”（讀作“如果P，則Q”）。,例9將命題“如果我得到這本小說(shuō)，那么我今夜就讀完它?！狈?hào)化。,解令P：我得到這本小說(shuō)；Q：我今夜就讀完它。于是上述命題可表示為P→Q。,例8若P：雪是黑色的；Q：太陽(yáng)從西邊升起；R：太陽(yáng)從東邊升起。則P→Q和P→R所表示的命題都是真的.,當(dāng)P為真，Q為假時(shí)，P→Q為假，否則P→Q為真。,5．等值“?”定義2.2.5設(shè)P和Q是兩個(gè)命題，則它們的等值命題是一個(gè)復(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)化。基本步驟如下：,（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é)校。,（1）（P∨Q）→R；（2）（P∧Q）→R；（3）(P∧Q）→R（4）R→（P∧Q）,例13．將下列命題符號(hào)化（1）派小王或小李出差；（2）我們不能既劃船又跑步；（3）如果你來(lái)了，那么他唱不唱歌將看你是否伴奏而定；（4）如果李明是體育愛(ài)好者，但不是文藝愛(ài)好者，那么李明不是文體愛(ài)好者；（5）假如上午不下雨，我去看電影，否則就在家里看書(shū)。,解（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：我在家讀書(shū)。則命題可表示為（P→Q）∧（P→R）。,練習(xí)2-21.判斷下列語(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）,2.3命題演算的合適公式一、命題公式的概念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)串。,定義2.3.1（命題公式的遞歸定義。）（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）是命題公式。,4.代入實(shí)例定義2.3.2設(shè)A和B是兩個(gè)命題公式，如果將A中的某些命題變?cè)妹}公式進(jìn)行代換便可得到B，并且此種代換滿足：（1）被代換的是命題變?cè)?；?）如果要代換某個(gè)命題變?cè)?，則要將該命題變?cè)贏中的一切出現(xiàn)進(jìn)行代換（3）代換必須同時(shí)獨(dú)立地進(jìn)行則稱B是A的一個(gè)代入實(shí)例,例2設(shè)A=P→(Q∧P）,判斷下列命題公式是否是A的代入實(shí)例：B=S∧R→(Q∧(S∧R)）C=S∧R→(Q∧P）,解B是；C不是,二、真值指派命題公式代表一個(gè)命題，但只有當(dāng)公式中的每一個(gè)命題變?cè)加靡粋€(gè)確定的命題代入時(shí)，命題公式才有確定的真值，成為命題。,定義2.3.3設(shè)A(P1，P2，…,Pn)是一個(gè)命題公式，P1，P2，…,Pn是出現(xiàn)于其中的全部命題變?cè)?，?duì)P1，P2，…,Pn分別指定一個(gè)真值,稱為對(duì)P1，P2，…,Pn公式A的一組真值指派。,列出命題公式A在P1，P2，…,Pn的所有2n種真值指派下對(duì)應(yīng)的真值，這樣的表稱為A的真值表。,例3給出公式F=(（P∨Q）?（Q∧R）)?(P∧R）的真值表。,解公式F的真值表如下：,三、公式類型定義2.3.5如果對(duì)于命題公式F所包含的命題變?cè)娜魏我唤M真值指派，F(xiàn)的真值恒為真，則稱公式F為重言式（或永真公式），常用“1”表示。相反地，若對(duì)于F所包含的命題變?cè)娜魏我唤M真值指派，F(xiàn)的真值恒為假，則稱公式F為矛盾式（或永假公式），常用“0”表示。如果至少有一組真值指派使公式F的真值為真，則稱F為可滿足公式。,例4構(gòu)造下列命題公式的真值表，并判斷它們是何種類型的公式（1）（P?Q）?（P?Q）；（2）（Q→P）∧（P∧Q）；（3）（（P∨Q）→（Q∧R））→（P∧R）。,由上可知：F1是重言式,F2是矛盾式。,2.4等價(jià)與蘊(yùn)含,一、命題公式的等價(jià)關(guān)系定義2.4.1設(shè)A和B是兩個(gè)命題公式,P1,P2,…,Pn是所有出現(xiàn)于A和B中的命題變?cè)?，如果?duì)于P1,P2,…,Pn的任一組真值指派，A和B的真值都相同,則稱公式A和B等價(jià)，記為A?B,稱A?B為等價(jià)式。,注意：（1）符號(hào)“?”與“?”的區(qū)別與聯(lián)系。,（2）可以驗(yàn)證等價(jià)關(guān)系滿足：自反性：對(duì)任意公式A，有A?A。對(duì)稱性：對(duì)任意公式A，B，若A?B，則B?A?？蓚鬟f性：對(duì)任意公式A、B、C，若A?B，B?C，則A?C。,（3）當(dāng)A是重言式時(shí)，A?1；當(dāng)A是矛盾式時(shí)，則A?0。,定理2.4.1A?B當(dāng)且僅當(dāng)A?B是永真公式。,二、基本的等價(jià)式設(shè)P、Q、R是命題變?cè)?，下表中列出?4個(gè)最基本的等價(jià)式:,三、等價(jià)式的判別有兩種方法：真值表方法，命題演算方法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ī)則重言式的代入實(shí)例仍是重言式。,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ì)于等價(jià)式中的任一命題變?cè)霈F(xiàn)的每一處均用同一命題公式代入，則得到的仍是等價(jià)式。,(2)置換規(guī)則設(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)等價(jià)演算等價(jià)演算是指利用已知的一些等價(jià)式，根據(jù)置換規(guī)則、代入規(guī)則以及等價(jià)關(guān)系的可傳遞性推導(dǎo)出另外一些等價(jià)式的過(guò)程。,由代入規(guī)則知前述的基本等價(jià)式，不僅對(duì)任意的命題變?cè)狿，Q，R是成立的，而且當(dāng)P，Q，R分別為命題公式時(shí)，這些等價(jià)式也成立,例2證明命題公式的等價(jià)關(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證明下列命題公式的等價(jià)關(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)系定義2.4.2設(shè)A，B是兩個(gè)公式，若公式A?B是重言式，即A?B?1，則稱公式A蘊(yùn)含公式B，記作A?B。稱“A?B”為蘊(yùn)含式。,注意：（1）符號(hào)“?”和“?”的區(qū)別和聯(lián)系,（2）A?B是偏序關(guān)系,即自反性：A?A反對(duì)稱：若A?B，B?A，則A?B傳遞性：若A?B，B?C，則A?C,（3）若A、B和C是三個(gè)命題公式，且A?B，A?C，則A?B∧C,（4）若A、B和C是三個(gè)命題公式，且A?C，B?C，則A∧B?C,定理2.4.2A?B當(dāng)且僅當(dāng)A?B是永真公式。,四、基本的蘊(yùn)含式,五、蘊(yùn)含式的判別判定“A?B”是否成立的問(wèn)題可轉(zhuǎn)化為判定A?B是否為重言式，有下述判定方法：,（1）真值表；（2）等價(jià)演算；（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.等價(jià)演算方法例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í)2-41．判斷下列等值式是否成立（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)含式成立。,2.5功能完備集、其他聯(lián)結(jié)詞,問(wèn)題：為了能構(gòu)造任何意義的命題公式，究竟需要定義多少邏輯聯(lián)結(jié)詞？,A0=FA1=P∧QA2=P∨?QA3=PA4=?P∧QA5=QA6=（P∧?Q）∨（?P∧Q）A7=P∨Q,定義2.5.1設(shè)S是一個(gè)由一些邏輯聯(lián)結(jié)詞組成的集合，若對(duì)于任意給定的命題公式，總可以找到一個(gè)僅含有S中的邏輯聯(lián)結(jié)詞的命題公式與之等價(jià)，則稱S是一個(gè)聯(lián)結(jié)詞功能完備集。,定義2.5.2設(shè)S是一個(gè)聯(lián)結(jié)詞功能完備集，若S中的任一聯(lián)結(jié)詞都不能用S中的其他聯(lián)結(jié)詞等價(jià)表達(dá)，則稱S是一個(gè)極小的聯(lián)結(jié)詞功能完備集。,例{∧，?},{∨，?}是極小的聯(lián)結(jié)詞功能完備集,2.6對(duì)偶與范式一、對(duì)偶,定義2.6.1設(shè)A是一個(gè)僅含有聯(lián)結(jié)詞?、∧、和∨的命題公式，在A中用∨代替∧，用∧代替∨，用T代替F,用F代替T，所得的命題公式稱為A的對(duì)偶式，記為A*。,例如：P∧Q∨R和（P∨Q）∧R互為對(duì)偶式,?P∧Q∨R的對(duì)偶式是,(?P∨Q)∧R,定理2.6.1設(shè)A是一個(gè)僅含有聯(lián)結(jié)詞?、∧、和∨的命題公式，P1，P2.....Pn是出現(xiàn)于其中的全部命題變?cè)瑒t?A(P1，P2.....Pn)?A*(?P1，?P2.....?Pn)A(?P1，?P2.....?Pn)??A*(P1，P2.....Pn),定理2.6.2設(shè)A和B是兩個(gè)僅含有聯(lián)結(jié)詞?、∧、和∨的命題公式，如果A?B，則A*?B*。,二、范式1、析取范式和合取范式,定義2.6.2一個(gè)命題公式若具有P1*∧P2*∧…∧Pn*的形式（n≥1），其中Pi*是命題變?cè)狿i或其否定Pi，則稱其為質(zhì)合取式。例如,P∧Q∧R∧S是由命題變?cè)狿、Q、R、S組成的一質(zhì)合取式。,定義2.6.3一個(gè)命題公式若具有P1*∨P2*∨…∨Pn*（n≥1）的形式，其中P*i是命題變?cè)狿i或是其否定Pi，則稱其為質(zhì)析取式。例如,Q∨P∨R是由命題變?cè)狿、Q、R組成的一質(zhì)析取式。,定理2.6.3（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為永真式矛盾。,充分性：設(shè)A含命題變?cè)狿i和Pi，而Pi∨Pi是永真式，由結(jié)合律和零一律，A的真值必為1，故A也是永真式。,定義2.6.4質(zhì)合取式的析取稱為析取范式。即具有A1∨A2∨…∨An(n≥1)的形式的公式，其中Ai是質(zhì)合取式。,例如，F(xiàn)1=P∨(P∧Q)∨R∨(?P∧?Q∧R)是一析取范式。,定義2.6.5質(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,定理2.6.4（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)。,則由定理知，Ai不是矛盾式。,于是存在一組真值指派使Ai取值為真。,對(duì)同一組真值指派，A的取值也必為真，這與A是矛盾式不符，假設(shè)不成立。,充分性：假設(shè)任一Ai(1≤i≤n)中含有形如P∧P合取式，其中P為命題變?cè)?。于是由定理知，每一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ù)定理2.6.4，A不是矛盾式。,又A??P∨(P∧(?Q∨P)),?（?P∨P）∧（?P∨?Q∨P)（合取范式）E3ノ,由定理2.6.4知，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,由定理，該公式不是永假公式。,?(P??P)?(?P?Q)（合取范式）E1，E?3,由定理，該公式也不是永真公式。,由上可知，該公式是一可滿足公式。,又P?(P?Q)?(P?Q)??P,四、主析取范式和主合取范式（一）極小項(xiàng)、極大項(xiàng)定義2.6.6設(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),常用mk(0≤k≤2n-1)表示極小項(xiàng)，其中k為二進(jìn)制t1t2...tn對(duì)應(yīng)的十進(jìn)制。且若Pi*為?Pi,ti=0.否則Pi*為1。,例如，三個(gè)命題變?cè)狿,Q,R共形成八個(gè)極小項(xiàng)m0=?P∧?Q∧?R，m1=?P∧?Q∧R，m2=?P∧Q∧?Rm3=?P∧Q∧R，m4=P∧?Q∧?R，m5=P∧?Q∧Rm6=P∧Q∧?R，m7=P∧Q∧R,常用Mk(0≤k≤2n-1)表示極大項(xiàng)，其中k為二進(jìn)制t1t2...tn對(duì)應(yīng)的十進(jìn)制。且若Pi*為?Pi,ti=1.否則Pi*為0。,M0=P?Q?R，M1=P?Q??R，M2=P??Q?RM3=P??Q??R，M4=?P?Q?R，M5=?P?Q??RM6=?P??Q?R，M7=?P??Q??R,極小項(xiàng)、極小項(xiàng)的簡(jiǎn)記：,極小項(xiàng)的性質(zhì)：,1）每一個(gè)極小項(xiàng)mk在與其下標(biāo)相對(duì)應(yīng)的真值指派下真值為真，而在其余2n-1種真值指派下真值為假。,2）任意兩個(gè)不同的極小項(xiàng)的合取式是一個(gè)永假式。,3）全部2n個(gè)極小項(xiàng)的析取式是一個(gè)重言式,極大項(xiàng)的性質(zhì)：,1）每一個(gè)極大項(xiàng)Mk在與其下標(biāo)相對(duì)應(yīng)的真值指派下真值為假，而在其余2n-1種真值指派下真值為真。2）任意兩個(gè)不同的極大項(xiàng)的析取式是一個(gè)永真式3）全部2n個(gè)極大項(xiàng)的合取式是一個(gè)矛盾式,定義2.6.7由不同極小項(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è)主合取范式。,五、求公式的主析取范式和主合取范式(一）真值表法,例：(?P?Q)?(P?R)?(?P?Q??R)?(?P?Q?R)?(P??Q?R)?(P?Q?R)?m2?m3?m5?m7?(P?Q?R)?(P?Q??R)?(?P?Q?R)?(?P??Q?R)?M0?M1?M4?M6,定理2.6.5每一個(gè)不為永假的命題公式F（P1,P2,…,Pn）必與一個(gè)由P1，P2，…，Pn所產(chǎn)生的主析取范式等價(jià)。,永真公式的主析取范式包含所有2n個(gè)最小項(xiàng)。,永假公式的主析取范式是一個(gè)空公式。用0表示。,定理2.6.6每一個(gè)不為永真的公式F(P1,P2,…,Pn）必與一個(gè)由P1,P2,…,Pn所產(chǎn)生的主合取范式等價(jià)。,永假公式的主合取范式包含所有2n個(gè)最大項(xiàng)。,永真公式的主合取范式是一空公式，用1表示。,例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,例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,六、利用主范式判定公式類型1.利用主析取范式判定,(1)若公式F(P1,P2，…，Pn)的主析取范式包含所有2n個(gè)最小項(xiàng)，則F是永真公式。,(2)若F的主析取范式是一空公式且為0，則F是永假公式。,(3)否則，F(xiàn)為可滿足的公式。,2利用主合取范式判定,(1)若公式F（P1,P2,…,Pn）的主合取范式包含所有2n個(gè)最大項(xiàng)，則F是永假公式。,(2)若F的主合取范式是一空公式且為1，則F是永真公式。,(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í)2-61．判斷公式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不是重言式和矛盾式，只是可滿足式。,2.7命題演算的推理理論,3、如果甲是冠軍，則乙或丙將得亞軍；如果乙得亞軍，則甲不能得冠軍；如果丁得亞軍，丙不能得亞軍；事實(shí)是甲已得冠軍，可知_______不能得亞軍。,例1、如果天不下雨，我就去看電影；我沒(méi)有去看電影，說(shuō)明_________,2、如果李敏出差到學(xué)校，若王軍不生病，則王軍一定去看望李敏。如果李敏出差到長(zhǎng)沙，那么李敏一定來(lái)學(xué)校。王軍沒(méi)有生病。所以，___________,一、推理推理是由已知的命題得到新命題的思維過(guò)程。,定義2.7.1設(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,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ī)則(P規(guī)則）：在證明的任何步驟上都可以引用前提。結(jié)論引用規(guī)則（T規(guī)則）：在證明的任何步驟上所得到的結(jié)論都可以在其后的證明中引用。,置換規(guī)則：在證明的任何步驟上，命題公式的子公式都可以用與它等價(jià)的其它命題公式置換。代入規(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é)論。,練習(xí)用形式證明方法證明：（1）P∨Q是前提（P∧Q）→R，R∨S，S的結(jié)論。,因此，（P∧Q）→R，R∨S，S?P∨Q,CP規(guī)則：利用永真蘊(yùn)含式：要證明P?Q→R，則等價(jià)于證明P∧Q?R將例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、間接證明(或反證法),定義2.7.2如果對(duì)于出現(xiàn)在公式H1，H2，…,Hn中的命題變?cè)娜魏我唤M真值指派，公式H1，H2，…,Hn中至少有一個(gè)為假，即它們的合取式H1∧H2∧…∧Hn是矛盾式，則稱公式H1，H2，…Hn是不相容的。否則稱公式H1，H2…,Hn是相容的。,定理2.7.1若存在一個(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，利用定理2.7.1，將?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í)題2-71．判斷下列推理是否正確如果這里有球賽，則通行是困難的；如果他們按指定的時(shí)間到達(dá)，則通行是不困難的；他們按指定時(shí)間到達(dá)了，所以這里沒(méi)有球賽。,解先將已知條件符號(hào)化,令P：這里有球賽；Q：通行是困難的；R：他們按指定的時(shí)間到達(dá)了。,編號(hào)公式依據(jù)（1）R→QP,因此上述推理正確。,（2）RP,（3）QT（1），（2）,I,（4）P→QP,（5）PT（3），（4）,I,則上述推理過(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ō)真話。,