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

第二章 命題邏輯 數(shù)理邏輯是用數(shù)學(xué)方法研究思維規(guī)律的一門學(xué)科。所謂數(shù)學(xué)方法是指:用一套數(shù)學(xué)的符號系統(tǒng)來描述和 處理思維的形式與規(guī)律。因此, 數(shù)理邏輯又稱為符號邏輯。本章介紹數(shù)理邏輯中最基本的內(nèi)容命題邏輯。首先引入命題、命題公式等概念。然后,在此基礎(chǔ)上研究命題公式間的等值關(guān)系和蘊含關(guān)系,并給出推理規(guī)則,進行命題演繹。主要內(nèi)容如下： 2.1 命題的概念和表示 2.2 邏輯聯(lián)結(jié)詞 2.3 命題演算的合適公式 2.4 等價與蘊含 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)成的命題。,例3 A：李明是三好學(xué)生。 B：李明既是三好學(xué)生又是足球隊員 C: 明天天氣晴朗. D：張平或者正在釣魚或者正在睡覺。 E：如果明天天氣晴朗，那么我們舉行運動會。,解 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取值為真時，命題P取值為假；命題P取值為假時，命題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均取值為真時，P Q才取值為真。,3. 析取“” 定義2.2.3 設(shè)P和Q是兩個命題，則P和Q的析取是一個復(fù)合命題，記作“PQ”（讀作“P或Q”）。,例6 設(shè)命題P：他可能是100米賽跑冠軍； Q：他可能是400米賽跑冠軍。,則命題PQ表示： 他可能是100米或400米賽跑的冠軍。,當(dāng)且僅當(dāng)P和Q至少有一個取值為真時，PQ取值為真。,4. 蘊含“” 定義2.2.4 設(shè)P和Q是兩個命題，則它們的條件命題是一個復(fù)合命題，記作“PQ”（讀作“如果P，則Q”）。,例9 將命題“如果我得到這本小說，那么我今夜就讀完它?！狈柣?。,解 令P：我得到這本小說；Q：我今夜就讀完它。 于是上述命題可表示為PQ。,例8 若P：雪是黑色的；Q：太陽從西邊升起； R：太陽從東邊升起。則PQ和PR所表示的命題都是真的.,當(dāng)P為真，Q為假時，PQ為假，否則 PQ為真。,5等值“” 定義2.2.5 設(shè)P和Q是兩個命題，則它們的等值命題是一個復(fù)合命題，稱為等值式復(fù)合命題，記作“P Q” （讀作“P當(dāng)且僅當(dāng)Q”）。,當(dāng)P和Q的真值相同時,PQ取真,否則取假。,例10 非本倉庫工作人員，一律不得入內(nèi)。,解 令P：某人是倉庫工作人員； Q：某人可以進入倉庫。,則上述命題可表示為P Q。,例11 黃山比喜馬拉雅山高，當(dāng)且僅當(dāng)3是素數(shù) 令P：黃山比喜馬拉雅山高；Q：3是素數(shù) 本例可符號化為PQ,從漢語的語義看，P與Q之間并無聯(lián)系，但就聯(lián)結(jié) 詞的定義來看，因為P的真值為假，Q的真值為真， 所以PQ的真值為假。,對于上述五種聯(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)明天早上不下雨且不下雪時，我才去學(xué)校。,解 令P：明天早上下雨； Q：明天早上下雪； R：我去學(xué)校。,（1）（PQ） R； （2）（P Q）R； （3）(PQ）R （4）R（P Q）,例13將下列命題符號化 （1） 派小王或小李出差； （2） 我們不能既劃船又跑步； （3） 如果你來了，那么他唱不唱歌將看你是否伴奏而定； （4） 如果李明是體育愛好者，但不是文藝愛好者，那么 李明不是文體愛好者； （5） 假如上午不下雨，我去看電影，否則就在家里看書。,解 （1） 令P：派小王出差；Q：派小李出差。 命題符號化為PQ。,（2） 令P：我們劃船；Q：我們跑步。則命題可 表示為(PQ）。,（3） 令P：你來了；Q：他唱歌；R：你伴奏。 則命題可表示為 P（Q R）,（4） 令P：李明是體育愛好者；Q：李明是文藝愛好者。 則命題可表示為（P Q）（P Q）,（5） 令P：上午下雨；Q：我去看電影；R：我在家讀書。 則命題可表示為（P Q）（PR）。,練習(xí)2-2 1. 判斷下列語句哪些是命題，若是命題，則指出其真值。 （1） 只有小孩才愛哭。 （2） X+6=Y （3） 銀是白的。 （4） 起來吧，我的朋友。,( 是 假 ),( 不是 ),( 是 真 ),( 不是 ),2 將下列命題符號化 （1） 我看見的既不是小張也不是老李。,解 令P：我看見的是小張；Q：我看見的是老李。,則該命題可表示為PQ,（2） 如果晚上做完了作業(yè)并且沒有其它的事，他就會看電視或聽音樂。,解 令 P：他晚上做完了作業(yè)；Q：他晚上有其它的事； R：他看電視； S：他聽音樂。 則該命題可表示為（PQ）（RS）,2.3 命題演算的合適公式 一 、 命題公式的概念 1. 命題常元 一個表示確定命題的大寫字母。,2命題變元 一個沒有指定具體內(nèi)容的命題符號。,一個命題變元當(dāng)沒有對其賦予內(nèi)容時，它的真值不能確定，一旦用一個具體的命題代入，它的真值就確定了。,3. 命題公式 命題公式（或簡稱公式）是由0、1和命題變元以及命題聯(lián)結(jié)詞按一定的規(guī)則產(chǎn)生的符號串。,定義2.3.1 （命題公式的遞歸定義。） （1） 0，1是命題公式； （2） 命題變元是命題公式； （3） 如果A是命題公式，則A是命題公式； （4） 如果A和B是命題公式，則（AB）， （AB）,(AB）,(A B）也是命題公式； 有限次地利用上述（1）（4）而產(chǎn)生的符號串是命題公式。,例1 判斷下列符號串是否為命題公式。 （1） P(QPR）； （2）（PQ）（QR）,解 （1） 不是命題公式。 （2） 是命題公式。,4. 代入實例 定義2.3.2 設(shè)A和B是兩個命題公式，如果將A中的某些命題變元用命題公式進行代換便可得到B，并且此種代換滿足： （1）被代換的是命題變元； （2）如果要代換某個命題變元，則要將該命題變元在A中的一切出現(xiàn)進行代換 （3）代換必須同時獨立地進行 則稱B是A的一個代入實例,例2 設(shè)A=P(Q P ）,判斷下列命題公式是否是A的代入實例： B= SR (Q (SR) ） C= SR (Q P ）,解 B是；C不是,二、真值指派 命題公式代表一個命題，但只有當(dāng)公式中的每一個命題變元都用一個確定的命題代入時，命題公式才有確定的真值，成為命題。,定義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=(（PQ）（QR）) (PR）的真值表。,解 公式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）（QP）（PQ）； （3）（PQ）（QR）（PR）。,由上可知： F1是重言式 , F2是矛盾式。,2.4 等價與蘊含,一、命題公式的等價關(guān)系 定義2.4.1 設(shè)A和B是兩個命題公式, P1, P2, , Pn 是所有出現(xiàn)于A和B中的命題變元，如果對于P1, P2, , Pn 的任一組真值指派，A和B的真值都相同,則稱公式A和B等價，記為A B,稱 AB為等價式。,注意： （1）符號“”與“”的區(qū)別與聯(lián)系。,（2） 可以驗證等價關(guān)系滿足： 自反性：對任意公式A，有AA。 對稱性：對任意公式A，B，若AB，則BA。 可傳遞性：對任意公式A、B、C，若AB，BC，則AC。,（3）當(dāng)A是重言式時，A1；當(dāng)A是矛盾式時，則A0。,定理2.4.1 A B當(dāng)且僅當(dāng)A B是永真公式 。,二、基本的等價式 設(shè)P、Q、R是命題變元，下表中列出了24個最基本的等價式:,三、等價式的判別 有兩種方法：真值表方法，命題演算方法 1、真值表方法,例1 用真值表方法證明 E10： (PQ) PQ,解 令：A= (PQ)，B= PQ，構(gòu)造A，B 以及A B的真值表如下：,由于公式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ī)則 重言式的代入實例仍是重言式。,2命題演算方法,例如 F=（PQ） （QP）是重言式，若 用公式AB代換命題變元P得公式 F1=（AB）Q） （Q（AB）， F1仍是重言式。,注意：因為A B當(dāng)且僅當(dāng)A B是重言式。所以，若對于等價式中的任一命題變元出現(xiàn)的每一處均用同一命題公式代入，則得到的仍是等價式。,(2)置換規(guī)則 設(shè)C是命題公式A的一部分（即C是公式A中連續(xù)的幾個符號），且C本身也是一個命題公式，則稱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ī)則知前述的基本等價式，不僅對任意的命題變元P，Q，R是成立的，而且當(dāng)P，Q，R分別為命題公式時，這些等價式也成立,例2 證明命題公式的等價關(guān)系： （PQ）（RQ）（PR）Q；,證明 （PQ）（RQ） （ PQ）( RQ) E11 （ P R）Q E3( 分配律) (PR)Q E10(德.摩根定律) (PR) Q E11 所以（PQ）（RQ）（PR）Q,例3 證明下列命題公式的等價關(guān)系 (P Q ) ( P ( P Q ) ) P Q,證明 (PQ)( P(PQ) (PQ)( (P P ) Q ) E2(結(jié)合律), (PQ)( PQ) E7(等冪律), (P Q ) ( PQ ) E1 (交換律), P(Q(PQ) E2(結(jié)合律), PQ E1，E9(交換律，吸收律),例4 判別下列公式的類型。 （1） Q (P（PQ）) （2）（PQ）P,解（1） Q（P（PQ） Q（P（PQ） E11,E6 Q（PP）（PQ） E3 Q（1（PQ） E5 Q（PQ） E4 QPQ E10 （QQ）P E1,E2 0 E5,E8 所以Q (P (PQ)是矛盾式。 （2） （PQ）P （PQ）P E11 P E9 于是該公式是可滿足式。,三、命題公式的蘊含關(guān)系 定義2.4.2 設(shè)A，B是兩個公式，若公式AB是重言式，即AB1，則稱公式A蘊含公式B，記作AB。稱“AB”為蘊含式。,注意： （1） 符號“”和 “”的區(qū)別和聯(lián)系,（2） AB是偏序關(guān)系,即 自反性：AA 反對稱：若AB，BA，則AB 傳遞性：若AB，BC，則 AC,（3） 若A 、B和C是三個命題公式，且AB， A C，則ABC,（4） 若A 、B和C是三個命題公式，且A C ， B C，則A B C,定理2.4.2 A B當(dāng)且僅當(dāng)A B是永真公式 。,四、基本的蘊含式,五、蘊含式的判別 判定“A B”是否成立的問題可轉(zhuǎn)化為判定A B是否為重言式，有下述判定方法：,（1）真值表； （2）等價演算； （3）假定前件A為真； （4）假定后件B為假。,1. 真值表方法,例4 證明I14 ：(（PQ）（P R）（Q R）) R,證明 令公式 F =（PQ）（PR）（QR）R， 其真值表如下：,公式F對任意的一組真值指派取值均為1，故F是重言式。,2. 等價演算方法 例5 證明 I11：P（PQ） Q,證明 （P（PQ） Q, （P（PQ） Q E11, （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為真。,故蘊含式 I12 成立。,4、 假定后件B假 假定后件B為假，檢查在此情況下，其前件A是否也為假.,例7 證明蘊含式(PQ) (RS) (PR) (QS),證明 令后件(PR)(QS)為假，則PR為真，QS為假,于是P、R均為真，而Q和S至少一個為假。,由此可知 PQ與RS中至少一個為假,因此(PQ)(RS)為假.,故上述蘊含式成立。,練習(xí) 2-4 1判斷下列等值式是否成立 （1）（PQ） （R Q）（PR） Q （2）（PQ）（P Q）（PQ）,解 （1）（PQ）（RQ）,（PQ） （RQ） E11,（PR）Q E3,（PR）Q E10,（2）（PQ）（PQ）, (（PQ）（QP）) E6，E10, (（PQ）（QP）) E11, （PQ） E14,（PR）Q E11,2判定蘊含式P（QR） （PQ）（PR）是否成立,解 假定后件（PQ）（PR）為假，,則PQ為真，PR為假。,由PR為假,得P為真，R為假。,又PQ為真，故得Q為真。,于是P為真，QR為假。,從而 P（QR）為假。,因此蘊含式成立。,2.5 功能完備集、其他聯(lián)結(jié)詞,問題：為了能構(gòu)造任何意義的命題公式，究竟需要定義多少邏輯聯(lián)結(jié)詞？,A0=F A1=PQ A2=P Q A3=P A4= PQ A5=Q A6=（P Q）（ P Q） A7=P Q,定義2.5.1 設(shè)S是一個由一些邏輯聯(lián)結(jié)詞組成的集合，若對于任意給定的命題公式，總可以找到一個僅含有S中的邏輯聯(lián)結(jié)詞的命題公式與之等價，則稱S是一個聯(lián)結(jié)詞功能完備集。,定義2.5.2 設(shè)S是一個聯(lián)結(jié)詞功能完備集，若S中的任一聯(lián)結(jié)詞都不能用S中的其他聯(lián)結(jié)詞等價表達，則稱S是一個極小的聯(lián)結(jié)詞功能完備集。,例 ， , ， 是極小的聯(lián)結(jié)詞功能完備集,2.6 對偶與范式 一、對偶,定義2.6.1 設(shè)A是一個僅含有聯(lián)結(jié)詞 、 和的命題公式，在A中用代替，用代替，用T代替F,用F代替T，所得的命題公式稱為A的對偶式，記為A*。,例如：PQ R和（P Q） R互為對偶式, PQR的對偶式是,( 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*的形式（n1），其中Pi*是命題變元Pi或其否定Pi ，則稱其為質(zhì)合取式。 例如,PQRS是由命題變元P、Q、R、S組成的一質(zhì)合取式。,定義2.6.3 一個命題公式若具有P1*P2*Pn*（n1）的形式，其中P*i是命題變元Pi或是其否定Pi ，則稱其為質(zhì)析取式。 例如, QPR是由命題變元P、Q、R組成的一質(zhì)析取式。,定理2.6.3 （1）一質(zhì)合取式為永假式的充分必要條件是，它同時包含某個命題變元P及其否定P。 （2）一質(zhì)析取式為永真式的充分必要條件是，它同時包含某個命題變元P及其否定P。,證明（2） 必要性：假設(shè)A= P1*P2*Pn*為一質(zhì)析取式，且A為一永真式。,(反證法) 假設(shè)A式中不同時包含任一命題變元及其否定，,則在A中，當(dāng)Pi*為Pi時指派Pi取0，當(dāng)Pi*為Pi時，指派Pi取1。(i =1,2,n).這樣的一組真值指派使A的真值取0，這與A為永真式矛盾。,充分性：設(shè)A含命題變元Pi和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)也是一合取范式。,二、求公式的析取范式和合取范式,任何一個命題公式都可以變換為與它等值的析取范式或合取范式。按下列步驟進行：,（1）利用E11，E12和E14消去公式中的運算符“”和“”；,(2) 利用德摩根定律將否定符號“”向內(nèi)深入，使之只作用于命題變元；,（3）利用雙重否定律E6將 (P)置換成P；,（4）利用分配律、結(jié)合律將公式歸約為合取范式或析取范式。,例1 求F1=(P(QR)S的合取范式和析取范式,解 F1 (P(QR)S E11, P ( QR)S E10, P(QR)S (析取范式) E10 ,E6,又 F1 P(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ì)析取式至少包含一對互為否定的析取項。,三、利用范式判定公式類型,證明 （2）必要性（用反證法）： 假設(shè)AA1A2An中某個Ai不包含一對互為否定的合取項，,（2）公式A為永假式的充分必要條件是，A的析取范式中每一質(zhì)合取式至少包含一對互為否定的合取項。,則由定理知，Ai不是矛盾式。,于是存在一組真值指派使Ai取值為真。,對同一組真值指派，A的取值也必為真，這與A是矛盾式不符，假設(shè)不成立。,充分性：假設(shè)任一Ai(1in)中含有形如PP合取式，其中P為命題變元。于是由定理知，每一Ai(1in)都為矛盾式，因此A1A2An必為矛盾式，即A為矛盾式。,因此A的析取范式中每一質(zhì)合取式至少包含一對互為否定的合取項。,例3 判別公式A=P (P(QP)是否為重言式或矛盾式。,解 A P(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,四、主析取范式和主合取范式 （一）極小項、極大項 定義2.6.6 設(shè)有命題變元P1，P2，,Pn ，形如 的命題公式稱為是由命題變元P 1，P2，Pn所產(chǎn)生的極小項。而形如 的命題公式稱為是由命題變元P1，P2，Pn所產(chǎn)生的極大項。其中Pi*為Pi或為Pi(i=1,2,n).,例如,P1P2P3， P1P2P3均是由P1，P2，P3所產(chǎn)生的極小項。 P1P2P3是由P1，P2，P3產(chǎn)生的一個極大項,常用mk(0k2n-1)表示極小項 ，其中k為二進制t1t2.tn對應(yīng)的十進制。且若Pi*為Pi, ti=0.否則Pi*為1。,例如，三個命題變元P,Q,R共形成八個極小項 m0= PQR， m1= PQR ， m2= PQR m3=PQR， m4= PQR， m5= PQR m6= PQR， m7=PQR,常用Mk(0k2n-1)表示極大項 ，其中k為二進制t1t2.tn對應(yīng)的十進制。且若Pi*為Pi, ti=1.否則Pi*為0。,M0= PQ R， M1= P Q R ， M2= P Q R M3=PQ R， M4=PQR， M5= PQ R M6=PQR， M7=PQR,極小項、極小項的簡記：,極小項的性質(zhì)：,1）每一個極小項mk在與其下標(biāo)相對應(yīng)的真值指派下真值為真，而在其余2n-1種真值指派下真值為假。,2）任意兩個不同的極小項的合取式是一個永假式。,3）全部2n個極小項的析取式是一個重言式,極大項的性質(zhì)：,1）每一個極大項Mk在與其下標(biāo)相對應(yīng)的真值指派下真值為假 ，而在其余2n-1種真值指派下真值為真。 2）任意兩個不同的極大項的析取式是一個永真式 3）全部2n個極大項的合取式是一個矛盾式,定義2.6.7 由不同極小項所組成的析取式，稱為主析取范式。,定義7-18 由不同極大項所組成的合取式，稱 為主合取范式。,例如 (P1P2P3)(P1P2P3)(P1P2P3)是一個主析取范式。,(P1P2P3)(P1P2P3)(P1P2P3) (P1P2P3)是一個主合取范式。,五、求公式的主析取范式和主合取范式 (一）真值表法,例：( PQ) (P R ) ( PQ R) ( PQ 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)生的主析取范式等價。,永真公式的主析取范式包含所有2n個最小項。,永假公式的主析取范式是一個空公式。用0表示。,定理2.6.6 每一個不為永真的公式 F(P1, P2, , Pn） 必與一個由P1, P2, , Pn所產(chǎn)生的主合取范式等價。,永假公式的主合取范式包含所有 2n個最大項。,永真公式的主合取范式是一空公式，用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,(二）公式演算法 對任一給定的公式除了用求范式時的四個步驟外，還要利用同一律、等冪律、互否律、分配律等進一步將質(zhì)合取式（質(zhì)析取式）變換為最小項（最大項）的形式。,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,解 F2 P(P(QP) E11, (PP)(PQP) E3,11 E5,E1, 1,六、利用主范式判定公式類型 1. 利用主析取范式判定,(1) 若公式 F(P1, P2，Pn)的主析取范式包含所有2n個最小項，則 F是永真公式。,(2) 若 F的主析取范式是一空公式且為0，則 F是永假公式。,(3) 否則，F(xiàn)為可滿足的公式。,2 利用主合取范式判定,(1) 若公式F（P1, P2, , Pn）的主合取范式包含所有2n個最大項，則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-6 1判斷公式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個項，故F不是重言式和矛盾式，只是可滿足式。,2.7 命題演算的推理理論,3、如果甲是冠軍，則乙或丙將得亞軍；如果乙得亞軍，則甲不能得冠軍；如果丁得亞軍，丙不能得亞軍；事實是甲已得冠軍，可知_不能得亞軍。,例 1、如果天不下雨，我就去看電影；我沒有去看電影，說明_,2、如果李敏出差到學(xué)校，若王軍不生病，則王軍一定去看望李敏。如果李敏出差到長沙，那么李敏一定來學(xué)校。王軍沒有生病。所以，_,一、推理 推理是由已知的命題得到新命題的思維過程。,定義2.7.1 設(shè)A和B是兩個命題公式，如果AB，即如果命題公式AB為重言式，則稱B是前提A的結(jié)論或從A推出結(jié)論B。一般地設(shè)H1，H2，,Hn和C是一些命題公式,若蘊含式 H1H2Hn C (*) 成立，則稱C是前提集合 H1，H2，,Hn的結(jié)論，或稱從前提H1，H2，,Hn能推出結(jié)論C。有時也記作 H1，H2，,Hn C,1、真值表法 對于命題公式 中所有命題變元的每一組真值指派作出該公式的真值表，看是否為永真。,例1 考察結(jié)論C是否是下列前提H1，H2的結(jié)論。 （1）H1：PQ，H2：P，C：Q,二、如何判斷由一個前提集合能否推出某個結(jié)論?,（2）H1：PQ， 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é)論都可以在其后的證明中引用