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

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

第二章命題邏輯數(shù)理邏輯是用數(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)容如下：2.1命題的概念和表示2.2邏輯聯(lián)結(jié)詞2.3命題演算的合適公式2.4等價(jià)與蘊(yùn)含2.5對偶與范式2.6命題演算的推理理論,例1判斷下列語句是否是命題。（1）空氣是人生存所必需的。（2）請把門關(guān)上。（3）南京是中國的首都。（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是命題,原子命題：由簡單句形成的命題。,復(fù)合命題：由一個或幾個原子命題通過聯(lián)結(jié)詞的聯(lián)接而構(gòu)成的命題。,例3A：李明是三好學(xué)生。B：李明既是三好學(xué)生又是足球隊(duì)員C:明天天氣晴朗.D：張平或者正在釣魚或者正在睡覺。E：如果明天天氣晴朗，那么我們舉行運(yùn)動會。,解A、C是原子命題B、D、E是復(fù)合命題,2.2邏輯聯(lián)結(jié)詞,1.否定“”,定義2.2.1設(shè)P是一個命題，則P的否定是一個復(fù)合命題，稱為P的否命題，記作“P”(讀作“非P”)。,例4設(shè)P：上海是一個城市；Q：每個自然數(shù)都是偶數(shù)。則有P：上海不是一個城市;Q：并非每個自然數(shù)都是偶數(shù)。,命題P取值為真時(shí)，命題P取值為假；命題P取值為假時(shí)，命題P取值為真。,2．合取“∧”定義2.2.2設(shè)P和Q是兩個命題，則P和Q的合取是一個復(fù)合命題，記作“P∧Q”（讀作“P且Q”）。,例5設(shè)P：我們?nèi)タ措娪?。Q：房間里有十張桌子。則P∧Q表示“我們?nèi)タ措娪安⑶曳块g里有十張桌子?！?當(dāng)且僅當(dāng)命題P和Q均取值為真時(shí)，P∧Q才取值為真。,3.析取“∨”定義2.2.3設(shè)P和Q是兩個命題，則P和Q的析取是一個復(fù)合命題，記作“P∨Q”（讀作“P或Q”）。,例6設(shè)命題P：他可能是100米賽跑冠軍；Q：他可能是400米賽跑冠軍。,則命題P∨Q表示：他可能是100米或400米賽跑的冠軍。,當(dāng)且僅當(dāng)P和Q至少有一個取值為真時(shí)，P∨Q取值為真。,4.蘊(yùn)含“→”定義2.2.4設(shè)P和Q是兩個命題，則它們的條件命題是一個復(fù)合命題，記作“P→Q”（讀作“如果P，則Q”）。,例9將命題“如果我得到這本小說，那么我今夜就讀完它。”符號化。,解令P：我得到這本小說；Q：我今夜就讀完它。于是上述命題可表示為P→Q。,例8若P：雪是黑色的；Q：太陽從西邊升起；R：太陽從東邊升起。則P→Q和P→R所表示的命題都是真的.,當(dāng)P為真，Q為假時(shí)，P→Q為假，否則P→Q為真。,5．等值“?”定義2.2.5設(shè)P和Q是兩個命題，則它們的等值命題是一個復(fù)合命題，稱為等值式復(fù)合命題，記作“P?Q”（讀作“P當(dāng)且僅當(dāng)Q”）。,當(dāng)P和Q的真值相同時(shí),P?Q取真,否則取假。,例10非本倉庫工作人員，一律不得入內(nèi)。,解令P：某人是倉庫工作人員；Q：某人可以進(jìn)入倉庫。,則上述命題可表示為P?Q。,例11黃山比喜馬拉雅山高，當(dāng)且僅當(dāng)3是素?cái)?shù)令P：黃山比喜馬拉雅山高；Q：3是素?cái)?shù)本例可符號化為P?Q,從漢語的語義看，P與Q之間并無聯(lián)系，但就聯(lián)結(jié)詞?的定義來看，因?yàn)镻的真值為假，Q的真值為真，所以P?Q的真值為假。,對于上述五種聯(lián)結(jié)詞，應(yīng)注意到：復(fù)合命題的真值只取決于構(gòu)成它的各原子命題的真值，而與這些原子命題的內(nèi)容含義無關(guān)。,命題符號化利用聯(lián)結(jié)詞可以把許多日常語句符號化?；静襟E如下：,（1）從語句中分析出各原子命題，將它們符號化（2）使用合適的命題聯(lián)結(jié)詞，把原子命題逐個聯(lián)結(jié)起來，組成復(fù)合命題的符號化表示。,例12用符號形式表示下列命題。（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．將下列命題符號化（1）派小王或小李出差；（2）我們不能既劃船又跑步；（3）如果你來了，那么他唱不唱歌將看你是否伴奏而定；（4）如果李明是體育愛好者，但不是文藝愛好者，那么李明不是文體愛好者；（5）假如上午不下雨，我去看電影，否則就在家里看書。,解（1）令P：派小王出差；Q：派小李出差。命題符號化為P∨Q。,（2）令P：我們劃船；Q：我們跑步。則命題可表示為(P∧Q）。,（3）令P：你來了；Q：他唱歌；R：你伴奏。則命題可表示為P→（Q?R）,（4）令P：李明是體育愛好者；Q：李明是文藝愛好者。則命題可表示為（P∧Q）→（P∧Q）,（5）令P：上午下雨；Q：我去看電影；R：我在家讀書。則命題可表示為（P→Q）∧（P→R）。,練習(xí)2-21.判斷下列語句哪些是命題，若是命題，則指出其真值。（1）只有小孩才愛哭。（2）X+6=Y（3）銀是白的。（4）起來吧，我的朋友。,(是假),(不是),(是真),(不是),2．將下列命題符號化（1）我看見的既不是小張也不是老李。,解令P：我看見的是小張；Q：我看見的是老李。,則該命題可表示為P∧Q,（2）如果晚上做完了作業(yè)并且沒有其它的事，他就會看電視或聽音樂。,解令P：他晚上做完了作業(yè)；Q：他晚上有其它的事；R：他看電視；S：他聽音樂。則該命題可表示為（P∧Q）→（R∨S）,2.3命題演算的合適公式一、命題公式的概念1.命題常元一個表示確定命題的大寫字母。,2．命題變元一個沒有指定具體內(nèi)容的命題符號。,一個命題變元當(dāng)沒有對其賦予內(nèi)容時(shí)，它的真值不能確定，一旦用一個具體的命題代入，它的真值就確定了。,3.命題公式命題公式（或簡稱公式）是由0、1和命題變元以及命題聯(lián)結(jié)詞按一定的規(guī)則產(chǎn)生的符號串。,定義2.3.1（命題公式的遞歸定義。）（1）0，1是命題公式；（2）命題變元是命題公式；（3）如果A是命題公式，則A是命題公式；（4）如果A和B是命題公式，則（A∨B），（A∧B）,(A→B）,(A?B）也是命題公式；有限次地利用上述（1）—（4）而產(chǎn)生的符號串是命題公式。,例1判斷下列符號串是否為命題公式。（1）P→(Q∧PR）；（2）（P∨Q）→（（Q∧R））,解（1）不是命題公式。（2）是命題公式。,4.代入實(shí)例定義2.3.2設(shè)A和B是兩個命題公式，如果將A中的某些命題變元用命題公式進(jìn)行代換便可得到B，并且此種代換滿足：（1）被代換的是命題變元；（2）如果要代換某個命題變元，則要將該命題變元在A中的一切出現(xiàn)進(jìn)行代換（3）代換必須同時(shí)獨(dú)立地進(jìn)行則稱B是A的一個代入實(shí)例,例2設(shè)A=P→(Q∧P）,判斷下列命題公式是否是A的代入實(shí)例：B=S∧R→(Q∧(S∧R)）C=S∧R→(Q∧P）,解B是；C不是,二、真值指派命題公式代表一個命題，但只有當(dāng)公式中的每一個命題變元都用一個確定的命題代入時(shí)，命題公式才有確定的真值，成為命題。,定義2.3.3設(shè)A(P1，P2，…,Pn)是一個命題公式，P1，P2，…,Pn是出現(xiàn)于其中的全部命題變元，對P1，P2，…,Pn分別指定一個真值,稱為對P1，P2，…,Pn公式A的一組真值指派。,列出命題公式A在P1，P2，…,Pn的所有2n種真值指派下對應(yīng)的真值，這樣的表稱為A的真值表。,例3給出公式F=(（P∨Q）?（Q∧R）)?(P∧R）的真值表。,解公式F的真值表如下：,三、公式類型定義2.3.5如果對于命題公式F所包含的命題變元的任何一組真值指派，F(xiàn)的真值恒為真，則稱公式F為重言式（或永真公式），常用“1”表示。相反地，若對于F所包含的命題變元的任何一組真值指派，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是兩個命題公式,P1,P2,…,Pn是所有出現(xiàn)于A和B中的命題變元，如果對于P1,P2,…,Pn的任一組真值指派，A和B的真值都相同,則稱公式A和B等價(jià)，記為A?B,稱A?B為等價(jià)式。,注意：（1）符號“?”與“?”的區(qū)別與聯(lián)系。,（2）可以驗(yàn)證等價(jià)關(guān)系滿足：自反性：對任意公式A，有A?A。對稱性：對任意公式A，B，若A?B，則B?A?？蓚鬟f性：對任意公式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是命題變元，下表中列出了24個最基本的等價(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代換命題變元P得公式F1=（（A∧B）?Q）?（?Q??（A∧B）），F(xiàn)1仍是重言式。,注意：因?yàn)锳?B當(dāng)且僅當(dāng)A?B是重言式。所以，若對于等價(jià)式中的任一命題變元出現(xiàn)的每一處均用同一命題公式代入，則得到的仍是等價(jià)式。,(2)置換規(guī)則設(shè)C是命題公式A的一部分（即C是公式A中連續(xù)的幾個符號），且C本身也是一個命題公式，則稱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ī)則知前述的基本等價(jià)式，不僅對任意的命題變元P，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是兩個公式，若公式A?B是重言式，即A?B?1，則稱公式A蘊(yùn)含公式B，記作A?B。稱“A?B”為蘊(yùn)含式。,注意：（1）符號“?”和“?”的區(qū)別和聯(lián)系,（2）A?B是偏序關(guān)系,即自反性：A?A反對稱：若A?B，B?A，則A?B傳遞性：若A?B，B?C，則A?C,（3）若A、B和C是三個命題公式，且A?B，A?C，則A?B∧C,（4）若A、B和C是三個命題公式，且A?C，B?C，則A∧B?C,定理2.4.2A?B當(dāng)且僅當(dāng)A?B是永真公式。,四、基本的蘊(yùn)含式,五、蘊(yùn)含式的判別判定“A?B”是否成立的問題可轉(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對任意的一組真值指派取值均為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至少一個為假。,由此可知P?Q與R?S中至少一個為假,,因此(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é)詞,問題：為了能構(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是一個由一些邏輯聯(lián)結(jié)詞組成的集合，若對于任意給定的命題公式，總可以找到一個僅含有S中的邏輯聯(lián)結(jié)詞的命題公式與之等價(jià)，則稱S是一個聯(lián)結(jié)詞功能完備集。,定義2.5.2設(shè)S是一個聯(lián)結(jié)詞功能完備集，若S中的任一聯(lián)結(jié)詞都不能用S中的其他聯(lián)結(jié)詞等價(jià)表達(dá)，則稱S是一個極小的聯(lián)結(jié)詞功能完備集。,例{∧，?},{∨，?}是極小的聯(lián)結(jié)詞功能完備集,2.6對偶與范式一、對偶,定義2.6.1設(shè)A是一個僅含有聯(lián)結(jié)詞?、∧、和∨的命題公式，在A中用∨代替∧，用∧代替∨，用T代替F,用F代替T，所得的命題公式稱為A的對偶式，記為A*。,例如：P∧Q∨R和（P∨Q）∧R互為對偶式,?P∧Q∨R的對偶式是,(?P∨Q)∧R,定理2.6.1設(shè)A是一個僅含有聯(lián)結(jié)詞?、∧、和∨的命題公式，P1，P2.....Pn是出現(xiàn)于其中的全部命題變元，則?A(P1，P2.....Pn)?A*(?P1，?P2.....?Pn)A(?P1，?P2.....?Pn)??A*(P1，P2.....Pn),定理2.6.2設(shè)A和B是兩個僅含有聯(lián)結(jié)詞?、∧、和∨的命題公式，如果A?B，則A*?B*。,二、范式1、析取范式和合取范式,定義2.6.2一個命題公式若具有P1*∧P2*∧…∧Pn*的形式（n≥1），其中Pi*是命題變元Pi或其否定Pi，則稱其為質(zhì)合取式。例如,P∧Q∧R∧S是由命題變元P、Q、R、S組成的一質(zhì)合取式。,定義2.6.3一個命題公式若具有P1*∨P2*∨…∨Pn*（n≥1）的形式，其中P*i是命題變元Pi或是其否定Pi，則稱其為質(zhì)析取式。例如,Q∨P∨R是由命題變元P、Q、R組成的一質(zhì)析取式。,定理2.6.3（1）一質(zhì)合取式為永假式的充分必要條件是，它同時(shí)包含某個命題變元P及其否定P。（2）一質(zhì)析取式為永真式的充分必要條件是，它同時(shí)包含某個命題變元P及其否定P。,證明（2）必要性：假設(shè)A=P1*∨P2*∨…∨Pn*為一質(zhì)析取式，且A為一永真式。,(反證法)假設(shè)A式中不同時(shí)包含任一命題變元及其否定，,則在A中，當(dāng)Pi*為Pi時(shí)指派Pi取0，當(dāng)Pi*為Pi時(shí)，指派Pi取1。(i=1,2,…n).這樣的一組真值指派使A的真值取0，這與A為永真式矛盾。,充分性：設(shè)A含命題變元Pi和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)也是一合取范式。,二、求公式的析取范式和合取范式,任何一個命題公式都可以變換為與它等值的析取范式或合取范式。按下列步驟進(jìn)行：,（1）利用E11，E12和E14消去公式中的運(yùn)算符“?”和“?”；,(2)利用德?摩根定律將否定符號“?”向內(nèi)深入，使之只作用于命題變元；,（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ì)析取式至少包含一對互為否定的析取項(xiàng)。,三、利用范式判定公式類型,證明（2）必要性（用反證法）：假設(shè)A＝A1∨A2∨…∨An中某個Ai不包含一對互為否定的合取項(xiàng)，,（2）公式A為永假式的充分必要條件是，A的析取范式中每一質(zhì)合取式至少包含一對互為否定的合取項(xiàng)。,則由定理知，Ai不是矛盾式。,于是存在一組真值指派使Ai取值為真。,對同一組真值指派，A的取值也必為真，這與A是矛盾式不符，假設(shè)不成立。,充分性：假設(shè)任一Ai(1≤i≤n)中含有形如P∧P合取式，其中P為命題變元。于是由定理知，每一Ai(1≤i≤n)都為矛盾式，因此A1∨A2∨…∨An必為矛盾式，即A為矛盾式。,因此A的析取范式中每一質(zhì)合取式至少包含一對互為否定的合取項(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è)有命題變元P1，P2，…,Pn，形如的命題公式稱為是由命題變元P1，P2，…，Pn所產(chǎn)生的極小項(xiàng)。而形如的命題公式稱為是由命題變元P1，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)生的一個極大項(xiàng),常用mk(0≤k≤2n-1)表示極小項(xiàng)，其中k為二進(jìn)制t1t2...tn對應(yīng)的十進(jìn)制。且若Pi*為?Pi,ti=0.否則Pi*為1。,例如，三個命題變元P,Q,R共形成八個極小項(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對應(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)的簡記：,極小項(xiàng)的性質(zhì)：,1）每一個極小項(xiàng)mk在與其下標(biāo)相對應(yīng)的真值指派下真值為真，而在其余2n-1種真值指派下真值為假。,2）任意兩個不同的極小項(xiàng)的合取式是一個永假式。,3）全部2n個極小項(xiàng)的析取式是一個重言式,極大項(xiàng)的性質(zhì)：,1）每一個極大項(xiàng)Mk在與其下標(biāo)相對應(yīng)的真值指派下真值為假，而在其余2n-1種真值指派下真值為真。2）任意兩個不同的極大項(xiàng)的析取式是一個永真式3）全部2n個極大項(xiàng)的合取式是一個矛盾式,定義2.6.7由不同極小項(xiàng)所組成的析取式，稱為主析取范式。,定義7-18由不同極大項(xiàng)所組成的合取式，稱為主合取范式。,例如(?P1??P2?P3)?(?P1?P2?P3)?(P1?P2?P3)是一個主析取范式。,(P1??P2?P3)?(P1?P2?P3)?(?P1??P2??P3)?(?P1?P2??P3)是一個主合取范式。,五、求公式的主析取范式和主合取范式(一）真值表法,例：(?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每一個不為永假的命題公式F（P1,P2,…,Pn）必與一個由P1，P2，…，Pn所產(chǎn)生的主析取范式等價(jià)。,永真公式的主析取范式包含所有2n個最小項(xiàng)。,永假公式的主析取范式是一個空公式。用0表示。,定理2.6.6每一個不為永真的公式F(P1,P2,…,Pn）必與一個由P1,P2,…,Pn所產(chǎn)生的主合取范式等價(jià)。,永假公式的主合取范式包含所有2n個最大項(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,(二）公式演算法對任一給定的公式除了用求范式時(shí)的四個步驟外，還要利用同一律、等冪律、互否律、分配律等進(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個最小項(xiàng)，則F是永真公式。,(2)若F的主析取范式是一空公式且為0，則F是永假公式。,(3)否則，F(xiàn)為可滿足的公式。,2利用主合取范式判定,(1)若公式F（P1,P2,…,Pn）的主合取范式包含所有2n個最大項(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個項(xiàng)，故F不是重言式和矛盾式，只是可滿足式。,2.7命題演算的推理理論,3、如果甲是冠軍，則乙或丙將得亞軍；如果乙得亞軍，則甲不能得冠軍；如果丁得亞軍，丙不能得亞軍；事實(shí)是甲已得冠軍，可知_______不能得亞軍。,例1、如果天不下雨，我就去看電影；我沒有去看電影，說明_________,2、如果李敏出差到學(xué)校，若王軍不生病，則王軍一定去看望李敏。如果李敏出差到長沙，那么李敏一定來學(xué)校。王軍沒有生病。所以，___________,一、推理推理是由已知的命題得到新命題的思維過程。,定義2.7.1設(shè)A和B是兩個命題公式，如果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、真值表法對于命題公式中所有命題變元的每一組真值指派作出該公式的真值表，看是否為永真。,例1考察結(jié)論C是否是下列前提H1，H2的結(jié)論。（1）H1：P→Q，H2：P，C：Q,二、如何判斷由一個前提集合能否推出某個結(jié)論?,（2）H1：P→Q，H2：P，C：Q,2、真值演算方法例證明,分析根據(jù)題意，需證明,證明,3、“形式證明”方法（1）基本述語形式證明：一個描述推理過程的命題序列，其中每個命題或者是已知的命題，或者是由某些前提所推得的結(jié)論，序列中最后一個命題就是所要求的結(jié)論，這樣的命題序列稱為形式證明。,有效的證明：如果證明過程中的每一步所得到的結(jié)論都是根據(jù)推理規(guī)則得到的，則這樣的證明稱作是有效的。有效的結(jié)論：通過有效的證明而得到結(jié)論，稱作是有效的結(jié)論。,合理的證明：一個證明是否有效與前提的真假沒有關(guān)系。如果所有的前提都是真的，那么通過有效的證明所得到的結(jié)論也是真的。這樣的證明稱作是合理的。合理的結(jié)論：一個結(jié)論是否有效與它自身的真假沒有關(guān)系。通過合理證明而得到的結(jié)論稱作合理的結(jié)論。,(2)推理規(guī)則前提引用規(guī)則(P規(guī)則）：在證明的任何步驟上都可以引用前提。結(jié)論引用規(guī)則（T規(guī)則）：在證明的任何步驟上所得到的結(jié)論都可以在其后的證明中引用。,置換規(guī)則：在證明的任何步驟上，命題公式的子公式都可以用與它等價(jià)的其它命題公式置換。代入規(guī)則：在證明的任何步驟上，重言式中的任一命題變元都可以用一命題公式代入，得到的仍是重言式。,例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符號化下面語句的推理過程，并指出推理是否正確?！叭绻资枪谲?，則乙或丙將得亞軍；如果乙得亞軍，則甲不能得冠軍；如果丁得亞軍，丙不能得亞軍；事實(shí)是甲已得冠軍，可知丁不能得亞軍”。,解設(shè)A：甲得冠軍；B：乙得亞軍；C：丙得亞軍；D：丁得亞軍。,推理過程符號化為A→（B∨C），B→A，D→C，A?D,4、間接證明(或反證法),定義2.7.2如果對于出現(xiàn)在公式H1，H2，…,Hn中的命題變元的任何一組真值指派，公式H1，H2，…,Hn中至少有一個為假，即它們的合取式H1∧H2∧…∧Hn是矛盾式，則稱公式H1，H2，…Hn是不相容的。否則稱公式H1，H2…,Hn是相容的。,定理2.7.1若存在一個公式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á)了，所以這里沒有球賽。,解先將已知條件符號化,令P：這里有球賽；Q：通行是困難的；R：他們按指定的時(shí)間到達(dá)了。,編號公式依據(jù)（1）R→QP,因此上述推理正確。,（2）RP,（3）QT（1），（2）,I,（4）P→QP,（5）PT（3），（4）,I,則上述推理過程符號化為P→Q，R→Q，R?P,2.張三說李四在說謊，李四說王五在說謊，王五說張三、李四都在說謊。問張三、李四、王五三人，到底誰說真話，誰說假話？,解先將簡單命題符號化。令P：張三說真話；Q：李四說真話；R：王五說真話，由題意知推理的前提為：P→Q，P→Q，Q→R，Q→R，R→（P∧Q），R→（P∨Q）。下面根據(jù)已知前提進(jìn)行形式推理。,因此，由上述推理知張三說假話，王五說假話，只有李四說真話。,