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

第二章命題邏輯數(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)容如下：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)把門關(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ù)合命題，記作“PQ”（讀作“P且Q”）。,例5設(shè)P：我們?nèi)タ措娪?。Q：房間里有十張桌子。則PQ表示“我們?nèi)タ措娪安⑶曳块g里有十張桌子?！?當(dāng)且僅當(dāng)命題P和Q均取值為真時(shí)，PQ才取值為真。,3.析取“”定義2.2.3設(shè)P和Q是兩個(gè)命題，則P和Q的析取是一個(gè)復(fù)合命題，記作“PQ”（讀作“P或Q”）。,例6設(shè)命題P：他可能是100米賽跑冠軍；Q：他可能是400米賽跑冠軍。,則命題PQ表示：他可能是100米或400米賽跑的冠軍。,當(dāng)且僅當(dāng)P和Q至少有一個(gè)取值為真時(shí)，PQ取值為真。,4.蘊(yùn)含“”定義2.2.4設(shè)P和Q是兩個(gè)命題，則它們的條件命題是一個(gè)復(fù)合命題，記作“PQ”（讀作“如果P，則Q”）。,例9將命題“如果我得到這本小說(shuō)，那么我今夜就讀完它?！狈?hào)化。,解令P：我得到這本小說(shuō)；Q：我今夜就讀完它。于是上述命題可表示為PQ。,例8若P：雪是黑色的；Q：太陽(yáng)從西邊升起；R：太陽(yáng)從東邊升起。則PQ和PR所表示的命題都是真的.,當(dāng)P為真，Q為假時(shí)，PQ為假，否則PQ為真。,5等值“”定義2.2.5設(shè)P和Q是兩個(gè)命題，則它們的等值命題是一個(gè)復(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é)校。,（1）（PQ）R；（2）（PQ）R；（3）(PQ）R（4）R（PQ）,例13將下列命題符號(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í)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)的是老李。,則該命題可表示為PQ,（2）如果晚上做完了作業(yè)并且沒(méi)有其它的事，他就會(huì)看電視或聽(tīng)音樂(lè)。,解令P：他晚上做完了作業(yè)；Q：他晚上有其它的事；R：他看電視；S：他聽(tīng)音樂(lè)。則該命題可表示為（PQ）（RS）,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是命題公式，則（AB），（AB）,(AB）,(AB）也是命題公式；有限次地利用上述（1）（4）而產(chǎn)生的符號(hào)串是命題公式。,例1判斷下列符號(hào)串是否為命題公式。（1）P(QPR）；（2）（PQ）（QR）,解（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(QP）,判斷下列命題公式是否是A的代入實(shí)例：B=SR(Q(SR)）C=SR(QP）,解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=(（PQ）（QR）)(PR）的真值表。,解公式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）（PQ）（PQ）；（2）（QP）（PQ）；（3）（PQ）（QR）（PR）。,由上可知：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à)，記為AB,稱AB為等價(jià)式。,注意：（1）符號(hào)“”與“”的區(qū)別與聯(lián)系。,（2）可以驗(yàn)證等價(jià)關(guān)系滿足：自反性：對(duì)任意公式A，有AA。對(duì)稱性：對(duì)任意公式A，B，若AB，則BA。可傳遞性：對(duì)任意公式A、B、C，若AB，BC，則AC。,（3）當(dāng)A是重言式時(shí)，A1；當(dāng)A是矛盾式時(shí)，則A0。,定理2.4.1AB當(dāng)且僅當(dāng)AB是永真公式。,二、基本的等價(jià)式設(shè)P、Q、R是命題變?cè)?，下表中列出?4個(gè)最基本的等價(jià)式:,三、等價(jià)式的判別有兩種方法：真值表方法，命題演算方法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ī)則重言式的代入實(shí)例仍是重言式。,2命題演算方法,例如F=（PQ）（QP）是重言式，若用公式AB代換命題變?cè)狿得公式F1=（AB）Q）（Q（AB），F(xiàn)1仍是重言式。,注意：因?yàn)锳B當(dāng)且僅當(dāng)AB是重言式。所以，若對(duì)于等價(jià)式中的任一命題變?cè)霈F(xiàn)的每一處均用同一命題公式代入，則得到的仍是等價(jià)式。,(2)置換規(guī)則設(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)等價(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)系：（PQ）（RQ）（PR）Q；,證明（PQ）（RQ）（PQ）(RQ)E11（PR）QE3(分配律)(PR)QE10(德.摩根定律)(PR)QE11所以（PQ）（RQ）（PR）Q,例3證明下列命題公式的等價(jià)關(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)系定義2.4.2設(shè)A，B是兩個(gè)公式，若公式AB是重言式，即AB1，則稱公式A蘊(yùn)含公式B，記作AB。稱“AB”為蘊(yùn)含式。,注意：（1）符號(hào)“”和“”的區(qū)別和聯(lián)系,（2）AB是偏序關(guān)系,即自反性：AA反對(duì)稱：若AB，BA，則AB傳遞性：若AB，BC，則AC,（3）若A、B和C是三個(gè)命題公式，且AB，AC，則ABC,（4）若A、B和C是三個(gè)命題公式，且AC，BC，則ABC,定理2.4.2AB當(dāng)且僅當(dāng)AB是永真公式。,四、基本的蘊(yùn)含式,五、蘊(yùn)含式的判別判定“AB”是否成立的問(wèn)題可轉(zhuǎn)化為判定AB是否為重言式，有下述判定方法：,（1）真值表；（2）等價(jià)演算；（3）假定前件A為真；（4）假定后件B為假。,1.真值表方法,例4證明I14：(（PQ）（PR）（QR）)R,證明令公式F=（PQ）（PR）（QR）R，其真值表如下：,公式F對(duì)任意的一組真值指派取值均為1，故F是重言式。,2.等價(jià)演算方法例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í)2-41判斷下列等值式是否成立（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)含式成立。,2.5功能完備集、其他聯(lián)結(jié)詞,問(wèn)題：為了能構(gòu)造任何意義的命題公式，究竟需要定義多少邏輯聯(lián)結(jié)詞？,A0=FA1=PQA2=PQA3=PA4=PQA5=QA6=（PQ）（PQ）A7=PQ,定義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*。,例如：PQR和（PQ）R互為對(duì)偶式,PQR的對(duì)偶式是,(PQ)R,定理2.6.1設(shè)A是一個(gè)僅含有聯(lián)結(jié)詞、和的命題公式，P1，P2.Pn是出現(xiàn)于其中的全部命題變?cè)?，則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é)詞、和的命題公式，如果AB，則A*B*。,二、范式1、析取范式和合取范式,定義2.6.2一個(gè)命題公式若具有P1*P2*Pn*的形式（n1），其中Pi*是命題變?cè)狿i或其否定Pi，則稱其為質(zhì)合取式。例如,PQRS是由命題變?cè)狿、Q、R、S組成的一質(zhì)合取式。,定義2.6.3一個(gè)命題公式若具有P1*P2*Pn*（n1）的形式，其中P*i是命題變?cè)狿i或是其否定Pi，則稱其為質(zhì)析取式。例如,QPR是由命題變?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，而PiPi是永真式，由結(jié)合律和零一律，A的真值必為1，故A也是永真式。,定義2.6.4質(zhì)合取式的析取稱為析取范式。即具有A1A2An(n1)的形式的公式，其中Ai是質(zhì)合取式。,例如，F(xiàn)1=P(PQ)R(PQR)是一析取范式。,定義2.6.5質(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,定理2.6.4（1）公式A為永真式的充分必要條件是，A的合取范式中每一質(zhì)析取式至少包含一對(duì)互為否定的析取項(xiàng)。,三、利用范式判定公式類型,證明（2）必要性（用反證法）：假設(shè)AA1A2An中某個(gè)Ai不包含一對(duì)互為否定的合取項(xiàng)，,（2）公式A為永假式的充分必要條件是，A的析取范式中每一質(zhì)合取式至少包含一對(duì)互為否定的合取項(xiàng)。,則由定理知，Ai不是矛盾式。,于是存在一組真值指派使Ai取值為真。,對(duì)同一組真值指派，A的取值也必為真，這與A是矛盾式不符，假設(shè)不成立。,充分性：假設(shè)任一Ai(1in)中含有形如PP合取式，其中P為命題變?cè)Ｓ谑怯啥ɡ碇?，每一Ai(1in)都為矛盾式，因此A1A2An必為矛盾式，即A為矛盾式。,因此A的析取范式中每一質(zhì)合取式至少包含一對(duì)互為否定的合取項(xiàng)。,例3判別公式A=P(P(QP)是否為重言式或矛盾式。,解AP(P(QP)E11,P(PQ)(PP)(析取范式)E3,根據(jù)定理2.6.4，A不是矛盾式。,又AP(P(QP),（PP）（PQP)（合取范式）E3,由定理2.6.4知，A是重言式。,例4利用范式判斷公式P(PQ)的類型。,解P(PQ)(P(PQ)(P(PQ)E12,(PQ)(P(PQ)E10,(PQ)P(析取范式)E9,由定理，該公式不是永假公式。,(PP)(PQ)（合取范式）E1，E3,由定理，該公式也不是永真公式。,由上可知，該公式是一可滿足公式。,又P(PQ)(PQ)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)镻i(i=1,2,n).,例如,P1P2P3，P1P2P3均是由P1，P2，P3所產(chǎn)生的極小項(xiàng)。P1P2P3是由P1，P2，P3產(chǎn)生的一個(gè)極大項(xiàng),常用mk(0k2n-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=PQR，m1=PQR，m2=PQRm3=PQR，m4=PQR，m5=PQRm6=PQR，m7=PQR,常用Mk(0k2n-1)表示極大項(xiàng)，其中k為二進(jìn)制t1t2.tn對(duì)應(yīng)的十進(jìn)制。且若Pi*為Pi,ti=1.否則Pi*為0。,M0=PQR，M1=PQR，M2=PQRM3=PQR，M4=PQR，M5=PQRM6=PQR，M7=PQR,極小項(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)所組成的合取式，稱為主合取范式。,例如(P1P2P3)(P1P2P3)(P1P2P3)是一個(gè)主析取范式。,(P1P2P3)(P1P2P3)(P1P2P3)(P1P2P3)是一個(gè)主合取范式。,五、求公式的主析取范式和主合取范式(一）真值表法,例：(PQ)(PR)(PQR)(PQR)(PQR)(PQR)m2m3m5m7(PQR)(PQR)(PQR)(PQR)M0M1M4M6,定理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(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,例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,六、利用主范式判定公式類型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(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í)2-61判斷公式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不是重言式和矛盾式，只是可滿足式。,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è)命題公式，如果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,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（PQ）是前提PQ，QR，PS，S的結(jié)論。,所以PQ，QR，PS，SR（PQ),例3證明RS是前提P（QS），RP和Q的有效結(jié)論。,練習(xí)用形式證明方法證明：（1）PQ是前提（PQ）R，RS，S的結(jié)論。,因此，（PQ）R，RS，SPQ,CP規(guī)則：利用永真蘊(yùn)含式：要證明PQR，則等價(jià)于證明PQR將例3等價(jià)地改為證明由前提推出結(jié)論S。,例4符號(hào)化下面語(yǔ)句的推理過(guò)程，并指出推理是否正確。“如果甲是冠軍，則乙或丙將得亞軍；如果乙得亞軍，則甲不能得冠軍；如果丁得亞軍，丙不能得亞軍；事實(shí)是甲已得冠軍，可知丁不能得亞軍”。,解設(shè)A：甲得冠軍；B：乙得亞軍；C：丙得亞軍；D：丁得亞軍。,推理過(guò)程符號(hào)化為A（BC），BA，DC，AD,4、間接證明(或反證法),定義2.7.2如果對(duì)于出現(xiàn)在公式H1，H2，,Hn中的命題變?cè)娜魏我唤M真值指派，公式H1，H2，,Hn中至少有一個(gè)為假，即它們的合取式H1H2Hn是矛盾式，則稱公式H1，H2，Hn是不相容的。否則稱公式H1，H2,Hn是相容的。,定理2.7.1若存在一個(gè)公式R，使得H1H2HnRR則公式H1，H2，,Hn是不相容的。,證明設(shè)H1H2Hn=>RR，,而RR是矛盾式，所以前件H1Hn必永假。因此，H1，H2，,Hn是不相容的。,則意味著（H1H2Hn）（RR）是重言式，,為了證明H1、H2、HnC，利用定理2.7.1，將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í)題2-71判斷下列推理是否正確如果這里有球賽，則通行是困難的；如果他們按指定的時(shí)間到達(dá)，則通行是不困難的；他們按指定時(shí)間到達(dá)了，所以這里沒(méi)有球賽。,解先將已知條件符號(hào)化,令P：這里有球賽；Q：通行是困難的；R：他們按指定的時(shí)間到達(dá)了。,編號(hào)公式依據(jù)（1）RQP,因此上述推理正確。,（2）RP,（3）QT（1），（2）,I,（4）PQP,（5）PT（3），（4）,I,則上述推理過(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ō)真話。,