等價(jià)式和蘊(yùn)涵式

等價(jià)式和蘊(yùn)涵式第1頁(yè)，共80頁(yè)，2023年，2月20日，星期三從上節(jié)例8.5中我們看到，雖然公式一般隨所含命題變?cè)恼嬷底兓兓灿泄綗o(wú)論變?cè)嬷抵概墒鞘裁此恼嬷刀际钦?，也有公式無(wú)論變?cè)嬷抵概墒鞘裁此恼嬷刀际羌?，它們是兩?lèi)特殊的命題公式即重言式（也叫永真式）和矛盾式（也叫永假式），當(dāng)然更多的是命題公式的真值隨變?cè)嬷档牟煌姓嬗屑?，我們稱(chēng)它們?yōu)榭蓾M(mǎn)足式。第2頁(yè)，共80頁(yè)，2023年，2月20日，星期三定義8.3

對(duì)于命題公式A，如果對(duì)A中命題變?cè)囊磺兄概葾的真值都為真，則稱(chēng)命題公式A為重言式（tautology），又稱(chēng)永真式；記作T。如果對(duì)A中命題變?cè)囊磺兄概葾的真值都為假，則稱(chēng)命題公式A為矛盾式（contradication），又稱(chēng)永假式。記作F。如果對(duì)A中命題變?cè)囊磺兄概葾的真值有真有假則稱(chēng)A為可滿(mǎn)足式（satisfactableformula）。第3頁(yè)，共80頁(yè)，2023年，2月20日，星期三那么任何一個(gè)公式肯定是永真式、永假式和可滿(mǎn)足式三種公式中的一個(gè)，判定一個(gè)公式是這三類(lèi)公式中的哪一個(gè)往往稱(chēng)為公式的判定問(wèn)題，目前我們可以借助真值表有效判定。很顯然，而當(dāng)A是永真式（永假式）時(shí)，A必為永假式（永真式）。第4頁(yè)，共80頁(yè)，2023年，2月20日，星期三例8.9

用真值表證明(P∨Q)∧P→Q為重言式。

證待證公式的真值表為：表8.9

由表的最后一列可以看出，原式為重言式。第5頁(yè)，共80頁(yè)，2023年，2月20日，星期三如果能給一組命題公式中的每一變?cè)粋€(gè)真值，使各表達(dá)式均為真，則這一組命題公式是一致的。在給出系統(tǒng)規(guī)范時(shí)，必須使這些規(guī)范一致。例如：“當(dāng)且僅當(dāng)系統(tǒng)正常操作時(shí)，系統(tǒng)處于多用戶(hù)狀態(tài)。如果系統(tǒng)正常操作，則它的核心程序正在運(yùn)行。核心程序不能正常運(yùn)行，或者系統(tǒng)處于中斷模式。如果系統(tǒng)不處于多用戶(hù)狀態(tài)，它就處于中斷模式。系統(tǒng)不處在中斷模式”這個(gè)系統(tǒng)規(guī)范就不一致。第6頁(yè)，共80頁(yè)，2023年，2月20日，星期三8．2．2等價(jià)式第7頁(yè)，共80頁(yè)，2023年，2月20日，星期三我們?cè)賮?lái)觀(guān)察一下例8.4公式P∨Q的真值表,它與公式P→Q的真值表相同，也就是說(shuō)，公式P→Q與P∨Q對(duì)于P，Q的所有真值指派它們的真值都相同。這時(shí)我們稱(chēng)這兩個(gè)公式等價(jià)，即有等價(jià)式P→QP∨Q。第8頁(yè)，共80頁(yè)，2023年，2月20日，星期三定義3.3

對(duì)于命題公式A，B中所有變?cè)娜魏沃概?，A和B的真值都相同，則稱(chēng)A等價(jià)于B，或邏輯相等。記為AB，又稱(chēng)它為邏輯等價(jià)式(logicallyequivalent)。注意：（1）符號(hào)“”與“”的區(qū)別：“”表示兩個(gè)公式等價(jià)，是關(guān)系符，而“”是邏輯聯(lián)接詞，任何兩個(gè)公式都可以用它聯(lián)接成一個(gè)新的公式。（2）“”與“”還有密切的聯(lián)系：易證AB當(dāng)且僅當(dāng)AB是重言式。（3）“”是公式間的一個(gè)等價(jià)關(guān)系，滿(mǎn)足自反性、對(duì)稱(chēng)性和傳遞性。首先我們有以下的基本等價(jià)式，它們都是以命題定律的形式出現(xiàn)的，故也叫命題定律。其中A，B，C表示任意命題變?cè)旱?頁(yè)，共80頁(yè)，2023年，2月20日，星期三表8.10第10頁(yè)，共80頁(yè)，2023年，2月20日，星期三除以上基本等價(jià)式外，還有一些不是運(yùn)算律的重要等價(jià)式，也是在今后常用的。E20A→B┐A∨BE21A→B┐B→┐AE22AB(A→B)∧(B→A)E23AB(A∧B)∨(┐A∧┐B)E24A∧B→CA→(B→C)第11頁(yè)，共80頁(yè)，2023年，2月20日，星期三說(shuō)明：這些等價(jià)式是今后作運(yùn)算和推理的重要依據(jù)，它們就象代數(shù)中(a+b)2=a2+2ab+b2,(a+b)3=a3+3a2b+3ab2+b3那么重要。如E21就是我們熟悉的原命題與其逆否命題等價(jià)。基本等價(jià)式的運(yùn)算律與集合運(yùn)算滿(mǎn)足的運(yùn)算律相似，它們的對(duì)應(yīng)是：∧對(duì)應(yīng)∩，∨對(duì)應(yīng)∪，對(duì)應(yīng)ˉ（補(bǔ)），T對(duì)應(yīng)E（全集），F(xiàn)對(duì)應(yīng)（空集），讀者可以對(duì)應(yīng)記憶。當(dāng)然它們都可以用真值表來(lái)驗(yàn)證。上面所有等價(jià)式中的A，B，C是任意的公式也可以，因?yàn)閷?duì)任意的命題變?cè)闪⒌牡葍r(jià)式與變?cè)≈禑o(wú)關(guān)，因此把變?cè)獡Q成任意公式也成立。第12頁(yè)，共80頁(yè)，2023年，2月20日，星期三如：（P∨Q）∨（P∨Q）T；（A→B）∧┐（A→B）F（┐A┐B）→C（┐A∧┐B）∨C因此我們今后要靈活運(yùn)用這些等價(jià)式。前面已述，我們可以用真值表來(lái)判定一個(gè)公式是永真式、永假式還是可滿(mǎn)足式，也可以用真值表來(lái)判斷兩個(gè)公式是否等價(jià)。但真值表對(duì)公式含有少量變?cè)强尚械?，?dāng)變?cè)獢?shù)目增長(zhǎng)時(shí)，就不可行了。第13頁(yè)，共80頁(yè)，2023年，2月20日，星期三例如，對(duì)于含20個(gè)變?cè)墓?，它的真值指派組合有220=1048576組，顯然此時(shí)需要用一臺(tái)計(jì)算機(jī)幫你做這個(gè)工作。可當(dāng)變?cè)?000個(gè)時(shí)，一臺(tái)計(jì)算機(jī)要檢查21000種真值組合的真值在幾億年內(nèi)都不能完成，而迄今為止尚沒(méi)有其他已知的計(jì)算過(guò)程能使計(jì)算機(jī)在合理可接受的時(shí)間內(nèi)完成，這涉及到算法復(fù)雜性問(wèn)題，也是計(jì)算機(jī)解決問(wèn)題最重要最根本的問(wèn)題。第14頁(yè)，共80頁(yè)，2023年，2月20日，星期三那么我們還可以用什么方法判定一個(gè)公式是哪一種公式，還能用什么方法討論兩個(gè)公式等價(jià)呢？那就是現(xiàn)在的等價(jià)公式。依據(jù)等價(jià)公式作運(yùn)算，還有一個(gè)重要的置換規(guī)則。第15頁(yè)，共80頁(yè)，2023年，2月20日，星期三定理8.1置換原理（ruleofreplacement）設(shè)A為一命題公式，C為A的子公式，且CD。若將A中出現(xiàn)子公式C的某處（未必全部）替換為D后得到的公式記為B，那么AB。這是明顯的。由于C和D等值，因而用D替換C不會(huì)改變A的真值，因此B與A等值。在邏輯運(yùn)算中用置換規(guī)則和在代數(shù)中運(yùn)用那些恒等式是相似的。第16頁(yè)，共80頁(yè)，2023年，2月20日，星期三例8.11求證：Q∨（（P∨Q）∧P）是一個(gè)重言式。

證：原式

Q∨（（P∨Q）∨P）

Q∨（（P∧Q）∨P）

Q∨（（P∨P）∧（P∨Q））

Q∨（T∧（P∨Q））

Q∨（P∨Q））（Q∨Q）∨P

T∨PT所以，Q∨（（P∨Q）∧P）是一個(gè)重言式。第17頁(yè)，共80頁(yè)，2023年，2月20日，星期三例8.12試證對(duì)任意公式A，B，C，

(A∨B)→C(A→C)∧(B→C)證：(A∨B)→C┐(A∨B)∨C(┐A∧┐B)∨C(┐A∨C)∧(┐B∨C)

(A→C)∧(┐B∨C)(A→C)∧(B→C)故等價(jià)公式成立。第18頁(yè)，共80頁(yè)，2023年，2月20日，星期三例8.13化簡(jiǎn)命題公式：（P∧Q∧R）∨（P∧Q∧R）解：原式（（Q∧R）∧P）∨（（Q∧R）∧P）（Q∧R）∧（P∨P）（Q∧R）∧T（Q∧R）第19頁(yè)，共80頁(yè)，2023年，2月20日，星期三從例中可看出，一個(gè)命題公式的表示形式并不是唯一的，可以有多種不同的表達(dá)式，通過(guò)等值演算可以尋求出最簡(jiǎn)單的邏輯表達(dá)式。這在數(shù)字電路中，當(dāng)電路的功能明確后，如何尋求簡(jiǎn)單而又可靠的電子線(xiàn)路，提供了有力的手段。這一點(diǎn)我們?cè)谙乱还?jié)中會(huì)看到。第20頁(yè)，共80頁(yè)，2023年，2月20日，星期三8．2．3蘊(yùn)涵式第21頁(yè)，共80頁(yè)，2023年，2月20日，星期三我們知道兩個(gè)公式A，B等價(jià)，即AB當(dāng)且僅當(dāng)AB是重言式。而AB(A→B)∧(B→A)，從而A→B與B→A都為重言式。如果現(xiàn)在只要求A→B一個(gè)是重言式，則就是我們下邊要研究的另一種公式間的關(guān)系----蘊(yùn)涵。第22頁(yè)，共80頁(yè)，2023年，2月20日，星期三定義8.5

當(dāng)命題公式A→B為永真式時(shí)，稱(chēng)A邏輯蘊(yùn)涵B，記為AB，又稱(chēng)它為邏輯蘊(yùn)涵式(logicallyimplication)。與符號(hào)“”與“”的區(qū)別類(lèi)似，同樣要注意符號(hào)“”與“→”的區(qū)別?？紤]“”還是公式間的一個(gè)等價(jià)關(guān)系嗎？我們可以很容易得出下面十分重要的邏輯蘊(yùn)涵式：第23頁(yè)，共80頁(yè)，2023年，2月20日，星期三表8.11第24頁(yè)，共80頁(yè)，2023年，2月20日，星期三由定義，要證AB，只要證A→B為永真式，進(jìn)而用真值表或依據(jù)置換規(guī)則的等價(jià)變形都可以。但對(duì)蘊(yùn)涵我們還有兩個(gè)特殊的方法：

A）前真推后真法：即由前件A為真若能推得后件也為B真，則AB。因?yàn)锳真B也一定為真的話(huà)，則A→B不存在A真B假的情況，從而A→B永真。B）后假推前假法：即由后件B為假若能推得前件A也為假，則AB。因?yàn)锽假A也一定為假的話(huà)，則A→B不存在A真B假的情況，從而A→B永真。第25頁(yè)，共80頁(yè)，2023年，2月20日，星期三例8.14證明：(A→B)∧┐B┐A

證：（用前真推后真法）假設(shè)前件(A→B)∧┐B為真，則A→B為真，┐B也為真，于是B為假，又A→B為真，從而A為假，故┐A為真，所以(A→B)∧┐B┐A。第26頁(yè)，共80頁(yè)，2023年，2月20日，星期三例8.15對(duì)任意公式A，B，C，證明：

A∧B┐A→(C→B)證：法一：用后假推前假法假設(shè)后件┐A→(C→B)為假，則┐A為真，C→B為假，于是A為假，C為真，B為假，從而A∧B為假，故A∧B┐A→(C→B)。法二：依據(jù)等價(jià)式和置換規(guī)則作等價(jià)變形（以后簡(jiǎn)稱(chēng)等價(jià)變形法）因?yàn)锳∧B→┐A→(C→B)┐（A∧B）∨A∨(┐C∨B)┐A∨┐B∨A∨┐C∨BT故A∧B┐A→(C→B)。讀者還可以用真值表嘗試一下。第27頁(yè)，共80頁(yè)，2023年，2月20日，星期三很明顯：邏輯等價(jià)式與邏輯蘊(yùn)涵式有如下關(guān)系：定理8.2AB當(dāng)且僅當(dāng)AB且BA即說(shuō)明等價(jià)是雙向的，蘊(yùn)涵是單向的。第28頁(yè)，共80頁(yè)，2023年，2月20日，星期三練習(xí)8．2

1、試判定下列各式是三類(lèi)公式的那一類(lèi)：（1）(P→Q)→(Q→P)

（2）┐P→(P→Q)

（3）Q∧┐(P→Q)

（4）P∧Q→(PQ)2、證明下列邏輯等價(jià)式：（1）AB(A∧B)∨(┐A∧┐B)（2）A→(B→C)B→(A→C)（3）A→(B→C)(A→B)→(A→C)（4）┐(┐A∨┐B)∨┐(┐A∨B)A3、證明下列邏輯蘊(yùn)涵式：（1）A∧BAB

（2）(A→B)→AA

（3）A→B((AB)→A)→B（4）┐(A∨B)∨CA∨(┐B∨C)（5）(A∨B)∧(A→C)∧(B→C)C（6）┐(A∨B)A∨(┐B∨C)4、化簡(jiǎn)下列各式：（1）(A∨┐B)∧(A∨B)∧(┐A∨┐B)

（2）B∨┐((┐A∨B)∧A)

（3）(P→Q)(┐Q→┐P)

（4）(┐Q→P)→(P→Q)

（5）(Q∧(P→┐Q)→P)∧┐(Q→P)第29頁(yè)，共80頁(yè)，2023年，2月20日，星期三§8．3命題公式的范式第30頁(yè)，共80頁(yè)，2023年，2月20日，星期三在第一節(jié)我們介紹了五個(gè)聯(lián)接詞，強(qiáng)調(diào)它們是基本的重要的，因?yàn)樗鼈兪亲匀徽Z(yǔ)言中最常用的。實(shí)際上，只有這五個(gè)是不夠用的，我們還會(huì)涉及其它的聯(lián)接詞。第31頁(yè)，共80頁(yè)，2023年，2月20日，星期三8．3．1

聯(lián)結(jié)詞的擴(kuò)充與最小聯(lián)接詞集

首先我們回過(guò)頭來(lái)分析一下五個(gè)基本聯(lián)接詞，我們發(fā)現(xiàn)其中的析取“∨”所表示的“或者”允許兩個(gè)都為真，即是可兼的，且當(dāng)A，B都為真時(shí)，A∨B為真。而比如一快餐館中寫(xiě)到：一套快餐包括“主菜一個(gè)，湯或沙拉一份”，此句中的“或”不是可兼的。再來(lái)區(qū)分一下：“明天上午我或者在教室或者在圖書(shū)館”，“明天上午十點(diǎn)我或者在教室或者在圖書(shū)館”，前一語(yǔ)句中的“或”是可兼的，可用“∨”來(lái)表示，而后一語(yǔ)句中的“或”是不可兼的，不能用“∨”來(lái)表示。本節(jié)我們要引進(jìn)邏輯電路中涉及的“異或（不可兼或）門(mén)”、“與非門(mén)”、“或非門(mén)”等四個(gè)擴(kuò)充聯(lián)接詞。當(dāng)然我們只作最少的介紹。第32頁(yè)，共80頁(yè)，2023年，2月20日，星期三“異或（不可兼或）”，用符號(hào)（或）表示，其含義可由下列等價(jià)式?jīng)Q定：PQ(P∨Q)∧┐(P∧Q)┐(PQ)(P∧┐Q)∨(┐P∧Q)也就是說(shuō)當(dāng)P，Q都為真時(shí)PQ為假?！芭c非（NAND）詞”，用記號(hào)表示，也稱(chēng)為悉非爾（Sheffer）豎，其含義可由下列等價(jià)式?jīng)Q定：PQ┐(P∧Q)這說(shuō)明當(dāng)P，Q都為真時(shí)PQ為假。第33頁(yè)，共80頁(yè)，2023年，2月20日，星期三“或非（NOR）”，用記號(hào)表示，也稱(chēng)為皮爾斯（Peirce）箭頭，其含義可由下列等價(jià)式?jīng)Q定：

PQ┐(P∨Q)

這說(shuō)明當(dāng)P，Q都為假時(shí)PQ為真。“蘊(yùn)涵否定詞”，用記號(hào)?表示，其含義可由下列等價(jià)式?jīng)Q定：

P?Q┐(P→Q)第34頁(yè)，共80頁(yè)，2023年，2月20日，星期三那么到現(xiàn)在為止，我們共介紹了九個(gè)聯(lián)接詞，可以證明這九個(gè)聯(lián)接詞就夠用了，即滿(mǎn)足完備性。但從我們本節(jié)引進(jìn)的四個(gè)擴(kuò)充聯(lián)接詞看，它們都能用前邊五個(gè)基本聯(lián)接詞表示，而由等價(jià)式知道，→和又能用┐，∧，∨來(lái)等價(jià)表示，同時(shí)由德摩根律P∨Q┐(┐P∧┐Q)，P∧Q┐(┐P∨┐Q)又能將∧與∨互相轉(zhuǎn)換，因而{┐，∧}和{┐，∨}都是完備聯(lián)接詞集（completegroupofconnectives）。我們?nèi)菀渍f(shuō)明┐與∧，┐與∨是相互獨(dú)立的，我們稱(chēng)既具有完備性又具有獨(dú)立性的聯(lián)接詞集為最小聯(lián)接詞集。

第35頁(yè)，共80頁(yè)，2023年，2月20日，星期三常見(jiàn)的最小聯(lián)接詞集有{┐，∧}，{┐，∨}，{┐，→}，{}，{}。{┐，→}在研究邏輯系統(tǒng)的演繹和推理時(shí)很重要，在程序系統(tǒng)的研究中也經(jīng)常用，如{if…then…else};{}，{}在大規(guī)模集成電路中有廣泛應(yīng)用。注意，{┐，∧，∨}，{∧，∨}，{┐，}等都不是最小聯(lián)接詞集。但{┐，∧，∨}是完備集，等價(jià)表示一公式也較簡(jiǎn)單，因此是常用的聯(lián)接詞集。如布爾代數(shù)系統(tǒng)以及下面要介紹的范式，就只用┐，∧，∨三個(gè)聯(lián)接詞。第36頁(yè)，共80頁(yè)，2023年，2月20日，星期三8.3.2析取范式和合取范式第37頁(yè)，共80頁(yè)，2023年，2月20日，星期三我們已經(jīng)知道，對(duì)眾多的命題公式，可以依據(jù)它們之間的邏輯等價(jià)關(guān)系進(jìn)行分類(lèi)，使相互邏輯等價(jià)的公式為一類(lèi)。那我們想，是否可以在各類(lèi)公式中分別選出一個(gè)公式作為各類(lèi)的“代表”，而且使它們具有統(tǒng)一的規(guī)范形式呢？這就是我們現(xiàn)在要講的公式的范式或標(biāo)準(zhǔn)形式。第38頁(yè)，共80頁(yè)，2023年，2月20日，星期三定義8.5

命題公式A稱(chēng)為析取范式（disjunctivenormalform），當(dāng)且僅當(dāng)它具有型式：A1∨A2∨…∨An（n≥1）其中A1,A2,…,An為由命題常元、變?cè)八鼈兊姆穸ńM成的合取式。如┐P∨Q，┐P∨(Q∧┐P)∨┐Q都是析取范式。第39頁(yè)，共80頁(yè)，2023年，2月20日，星期三定義8.6

命題公式A稱(chēng)為合取范式（conjunctivenormalform），當(dāng)且僅當(dāng)它具有型式：A1A1∧A2∧…∧An（n≥1）其中A1,A2,…,An為由命題常元、變?cè)八鼈兊姆穸ńM成的析取式。如┐P∧Q，P∧（P∨Q）∧（P∨Q∨Q）都是合取范式。注：P，┐P都可以看成特殊的析取范式和合取范式，┐P∨Q是析取范式，也可以看成是含有一個(gè)析取式的合取范式。第40頁(yè)，共80頁(yè)，2023年，2月20日，星期三例8.16求┐P→┐(P→Q)的析取范式及合取范式。解：P→┐(P→Q)P∨┐(┐P∨Q)P∨(P∧┐Q)(P)析取范式

(P∨P)∧(P∨┐Q)P∧(P∨┐ Q)(P)合取范式第41頁(yè)，共80頁(yè)，2023年，2月20日，星期三例8.17求┐(P∨Q)(P∧Q)的析取范式和合取范式。解：┐(P∨Q)(P∧Q)（┐(P∨Q)∧(P∧Q)）∨((P∨Q)∧┐(P∧Q))（┐P∧┐Q)∧(P）∨((P∨Q)∧（┐P∨┐Q))(P∨Q)∧（┐P∨┐Q)合取范式(P∧┐P)∨（┐P∧Q）∨（P∧┐Q)∨（Q∧┐Q)（┐P∧Q）∨（P∧┐Q)析取范式第42頁(yè)，共80頁(yè)，2023年，2月20日，星期三我們看到：任一命題公式都可化為與其等價(jià)的析取范式和合取范式。其等價(jià)推演的方法步驟是：第一步，消去公式中的聯(lián)結(jié)詞和：把公式中的P→Q化為┐P∨Q；把公式中的PQ化為(┐P∨Q)∧(┐Q∨P)或(P∧Q)∨(┐P∧┐Q)；第二步，將否定聯(lián)結(jié)詞┐向內(nèi)深入，使之只作用于命題變?cè)蛎}變?cè)姆穸ǎ缓髮ⅸ穿碢化為P；第三步，利用分配律，將公式進(jìn)一步化為所需要的范式。第43頁(yè)，共80頁(yè)，2023年，2月20日，星期三我們已經(jīng)發(fā)現(xiàn)，一公式的析取范式和合取范式可能不是唯一的，例如另一方面，一公式的合取范式與析取范式又可能是同一的。例如，P既是P→┐(P→Q)的合取范式，又是它的析取范式。又如┐P∨Q既可稱(chēng)為P→Q的析取范式，又可稱(chēng)為它的合取范式。上述兩點(diǎn)不能不說(shuō)是析取范式和合取范式的缺點(diǎn)，因此，我們需要更加規(guī)范公式的范式，這就是下面的主范式。第44頁(yè)，共80頁(yè)，2023年，2月20日，星期三8.3.3主析取范式與主合取范式第45頁(yè)，共80頁(yè)，2023年，2月20日，星期三主析取范式

主析取范式與析取范式的區(qū)別就在于對(duì)析取范式中的合取式有更嚴(yán)格的要求，即要達(dá)到都是小項(xiàng)。那么什么是小項(xiàng)，小項(xiàng)又有什么性質(zhì)呢？第46頁(yè)，共80頁(yè)，2023年，2月20日，星期三定義8.7在含n個(gè)變?cè)暮先∈街?，若每個(gè)變?cè)c其否定二者必出現(xiàn)且僅出現(xiàn)一個(gè)，則稱(chēng)此合取式為含n個(gè)變?cè)男№?xiàng)。

如：兩個(gè)變?cè)狿，Q能夠組成的小項(xiàng)有：4=22個(gè)

P∧Q，P∧┐Q，┐P∧Q，┐P∧┐Q三個(gè)變?cè)狿，Q，R能夠組成的小項(xiàng)有：8=23個(gè)P∧Q∧R，┐P∧Q∧R，P∧┐Q∧R，P∧Q∧┐R，┐P∧┐Q∧R，┐P∧Q∧┐R，P∧┐Q∧┐R，┐P∧┐Q∧┐R因此，n個(gè)變?cè)軌蚪M成的小項(xiàng)有2N個(gè).第47頁(yè)，共80頁(yè)，2023年，2月20日，星期三我們知道2N隨n的增長(zhǎng)速率很快，下面討論一下對(duì)小項(xiàng)編碼問(wèn)題。由于含有n個(gè)變?cè)拿總€(gè)小項(xiàng)都是n項(xiàng)的合取，而每一項(xiàng)或者是變?cè)霈F(xiàn)或者是變?cè)穸ǔ霈F(xiàn)。我們約定：當(dāng)變?cè)霈F(xiàn)時(shí)相應(yīng)位置記為“1”；當(dāng)變?cè)穸ǔ霈F(xiàn)時(shí)相應(yīng)位置記為“0”。這樣每個(gè)小項(xiàng)就對(duì)應(yīng)一個(gè)n位二進(jìn)制數(shù)。那么這個(gè)小項(xiàng)的編碼就用m帶上這個(gè)n位二進(jìn)制數(shù)為右下標(biāo)組成。如┐P∧Q的編碼為m01，P∧┐Q∧R的編碼為m101，因此小項(xiàng)與編碼是一一對(duì)應(yīng)的，編碼為m010的小項(xiàng)為┐P∧Q∧┐R。再來(lái)看看小項(xiàng)的性質(zhì)，我們從它們的真值表去分析：（表8.12 和表8.13分別是兩個(gè)變?cè)男№?xiàng)與三個(gè)變?cè)男№?xiàng)真值表）第48頁(yè)，共80頁(yè)，2023年，2月20日，星期三第49頁(yè)，共80頁(yè)，2023年，2月20日，星期三由上兩個(gè)小項(xiàng)真值表不難看出，小項(xiàng)具有如下性質(zhì)：任兩小項(xiàng)均不等價(jià)；每個(gè)小項(xiàng)有且僅有一組指派使其真值為真，且恰當(dāng)指派與小項(xiàng)編碼一致時(shí)。即其它任何指派都使此小項(xiàng)為假。如小項(xiàng)m101只在指派101時(shí)為真，其它指派都是假。有了對(duì)小項(xiàng)的充分討論，下面我們研究主析取范式的概念、性質(zhì)與求法。第50頁(yè)，共80頁(yè)，2023年，2月20日，星期三定義8.8

對(duì)一析取范式，若其每一個(gè)合取式均為小項(xiàng)時(shí)，即是主析取范式（majordisjunctivenormalform）。第51頁(yè)，共80頁(yè)，2023年，2月20日，星期三我們可以有兩種方法求主析取范式：方法1：真值表法真值表中使公式A為真的指派所對(duì)應(yīng)的小項(xiàng)組成的析取式即為A的主析取范式。其道理不難從小項(xiàng)的性質(zhì)得出這樣的主析取范式與A等價(jià)，因而可作為A的主析取范式。第52頁(yè)，共80頁(yè)，2023年，2月20日，星期三例8.18

用真值表求P→Q的主析取范式解：P→Q的真值表為：表8.14因此P→Q的主析取范式為m00∨m01∨m11

（P∧Q）∨（P∧Q）∨（P∧Q）由此我們知道，一個(gè)公式的主析取范式是惟一的。第53頁(yè)，共80頁(yè)，2023年，2月20日，星期三方法2：等價(jià)變形法例8.19

用等價(jià)變形法求P→Q的主析取范式解：P→Q

P∨Q（這是析取范式。現(xiàn)將這范式中的合取式P添加變?cè)猀,合取式Q添加P,即填滿(mǎn)變?cè)狿、Q,以構(gòu)成小項(xiàng)）（P∧（Q∨Q））∨（Q∧（P∨P））（P∧Q）∨（P∧Q）∨（P∧Q）第54頁(yè)，共80頁(yè)，2023年，2月20日，星期三由此得出利用等價(jià)變形法求公式的主析取范式的方法步驟：第一步：求出該公式的析取范式；第二步：除去范式中所有恒假的合取式，即化掉含有互補(bǔ)對(duì)的合取式；同時(shí)，將合取式中同一變?cè)亩鄠€(gè)出現(xiàn)合并為一個(gè)；第三步：對(duì)并非每一變?cè)汲霈F(xiàn)的析取范式中的合取式，利用PP∧TP∧(Q∨┐Q)把未出現(xiàn)的變?cè)≦）補(bǔ)進(jìn)來(lái)，并用分配律將其展開(kāi)，最后得到給定公式的主析取范式。第55頁(yè)，共80頁(yè)，2023年，2月20日，星期三下面我們對(duì)應(yīng)地介紹主合取范式。主合取范式主合取范式與合取范式的區(qū)別就在于對(duì)合取范式中的析取式有更嚴(yán)格的要求，即要達(dá)到都是大項(xiàng)。那么什么是大項(xiàng)，大項(xiàng)又有什么性質(zhì)呢？第56頁(yè)，共80頁(yè)，2023年，2月20日，星期三定義8.9在含n個(gè)變?cè)奈鋈∈街?，若每個(gè)變?cè)c其否定二者必出現(xiàn)且僅出現(xiàn)一個(gè)，則稱(chēng)此析取式為含n個(gè)變?cè)拇箜?xiàng)。如：兩個(gè)變?cè)狿，Q能夠組成的大項(xiàng)有：4=22個(gè)P∨Q，P∨┐Q，┐P∨Q，┐P∨┐Q三個(gè)變?cè)狿，Q，R能夠組成的大項(xiàng)有：8=23個(gè)P∨Q∨R，┐P∨Q∨R，P∨┐Q∨R，P∨Q∨┐R，┐P∨┐Q∨R，┐P∨Q∨┐R，P∨┐Q∨┐R，┐P∨┐Q∨┐R因此，n個(gè)變?cè)軌蚪M成的大項(xiàng)有2N個(gè).同樣，下面討論一下對(duì)大項(xiàng)編碼問(wèn)題。由于含有n個(gè)變?cè)拿總€(gè)大項(xiàng)都是n項(xiàng)的析取，而每一項(xiàng)或者是變?cè)霈F(xiàn)或者是變?cè)穸ǔ霈F(xiàn)。第57頁(yè)，共80頁(yè)，2023年，2月20日，星期三我們約定：當(dāng)變?cè)霈F(xiàn)時(shí)相應(yīng)位置記為“0”；當(dāng)變?cè)穸ǔ霈F(xiàn)時(shí)相應(yīng)位置記為“1”。這樣每個(gè)大項(xiàng)就對(duì)應(yīng)一個(gè)n位二進(jìn)制數(shù)。那么這個(gè)大項(xiàng)的編碼就用M帶上這個(gè)n位二進(jìn)制數(shù)為右下標(biāo)組成。如┐P∨Q的編碼為M10，P∨┐Q∨R的編碼為M010，因此大項(xiàng)與編碼是一一對(duì)應(yīng)的，編碼為M101的小項(xiàng)為┐P∨Q∨┐R。再來(lái)看看大項(xiàng)的性質(zhì)，我們也從它們的真值表去分析：（表8.15和表8.16分別是兩個(gè)變?cè)拇箜?xiàng)與三個(gè)變?cè)拇箜?xiàng)真值表）第58頁(yè)，共80頁(yè)，2023年，2月20日，星期三第59頁(yè)，共80頁(yè)，2023年，2月20日，星期三由上兩個(gè)大項(xiàng)真值表不難看出，大項(xiàng)具有如下性質(zhì)：任兩大項(xiàng)均不等價(jià)；每個(gè)大項(xiàng)有且僅有一組指派使其真值為假，且恰當(dāng)指派與大項(xiàng)編碼一致時(shí)。即其它任何指派都使此大項(xiàng)為真。如大項(xiàng)M101只在指派101時(shí)為假，其它指派都是真。有了對(duì)大項(xiàng)的充分討論，下面我們研究主合取范式的概念、性質(zhì)與求法。第60頁(yè)，共80頁(yè)，2023年，2月20日，星期三定義8.10

對(duì)一合取范式，若其每一個(gè)合取式均為大項(xiàng)時(shí)，即是主合取范式（conjunctivenormalform）。我們也可以有兩種方法求主合取范式：方法1：真值表法真值表中使公式A為假的指派所對(duì)應(yīng)的大項(xiàng)組成的合取式即為A的主合取范式。其道理不難從大項(xiàng)的性質(zhì)得出這樣的主合取范式與A等價(jià)，因而可作為A的主合取范式。第61頁(yè)，共80頁(yè)，2023年，2月20日，星期三例8.20

用真值表求P→Q的主合取范式解：由表8.14知，P→Q的主合取范式為

M10

（P∨Q）由此我們知道，一個(gè)公式的主合取范式也是惟一的。第62頁(yè)，共80頁(yè)，2023年，2月20日，星期三方法2：等價(jià)變形法例8.21

求公式(P∧Q)∨R的主合取范式。解：(P∧Q)∨R(P∨R)∧(Q∨R)(P∨(Q∧┐Q)∨R)∧((P∧┐P)∨Q∨R)(p∨Q∨R)∧(P∨┐Q∨R)∧(P∨Q∨R)∧(┐P∨Q∨R)(P∨Q∨R)∧(P∨┐Q∨R)∧(┐P∨Q∨R)第63頁(yè)，共80頁(yè)，2023年，2月20日，星期三由此得出利用等價(jià)變形法求公式的主合取范式的方法步驟：第一步：求出該公式的合取范式；第二步：除去范式中所有恒真的析取式，即化掉含有互補(bǔ)對(duì)的析取式；同時(shí)，將析取式中同一變?cè)亩鄠€(gè)出現(xiàn)合并為一個(gè)；第三步：對(duì)并非每一變?cè)汲霈F(xiàn)的析取范式中的析取式，利用PP∨FP∨(Q∧┐Q)把未出現(xiàn)的變?cè)≦）補(bǔ)進(jìn)來(lái)，并用分配律將其展開(kāi)，最后得到給定公式的主合取范式。應(yīng)用主析取范式分析和解決實(shí)際問(wèn)題。第64頁(yè)，共80頁(yè)，2023年，2月20日，星期三例8.22某科研所要從3名科研骨干A，B，C中挑選1～2名出國(guó)進(jìn)修。由于工作需要，選派時(shí)要滿(mǎn)足以下條件：（1）若A去，則C同去；（2）若B去，則C不能去；（3）若C不去，則A或B可以去。問(wèn)所里應(yīng)如何選派他們？解：設(shè)P：派A去Q：派B去R：派C去那么需要滿(mǎn)足的條件是(P→R)∧(Q→R)∧(R→(P∨Q))

經(jīng)過(guò)變形可得(P→R)∧(Q→R)∧(R→(P∨Q))

m001∨m010∨m101（P∧Q∧R）∨（P∧Q∧R）∨（P∧Q∧R因此，選派方案有三種：

（a）C去，而A，B都不去；（b）B去，而A，C都不去；（c）A，C同去，而B(niǎo)不去。第65頁(yè)，共80頁(yè)，2023年，2月20日，星期三練習(xí)8.3

*1、把公式(p→q)(┐q→┐p)變換為與之等價(jià)的、只含聯(lián)結(jié)詞┐，∧的公式。2、求下列公式的析取范式、合取范式及主析取范式、主合取范式，并據(jù)主析（合）取范式直接確定使該公式為真和為假的指派：（1）(┐P∨┐Q)→(P┐Q)（2）Q∧(P∨┐Q)（3）P∨(┐P→(Q∨(┐Q→R)))（4）P→(P∧(Q→R))（5）(P→Q)∧P→Q（6）(PQ)((P∧Q)∨(┐P∧┐Q))*（7）┐(PQ)（┐P┐Q）*（8）┐(PQ)（┐P┐Q）3、某單位要在A、B、C、D四個(gè)人中派兩個(gè)人出差，按下述三個(gè)條件有幾種派法：？如何派？（1）若A去，則C和D中要去一人；（2）若B和C不能都去；（3）若C去，則D要留下。

4、A、B、C、D四人做競(jìng)賽游戲，其中三人報(bào)告情況如下：

A：C第一，B第二；

B：C第二，D第三；

C：A第二，D第四。后經(jīng)核實(shí)發(fā)現(xiàn)每個(gè)人的報(bào)告都是至少有一個(gè)為真，問(wèn)實(shí)際名次究竟如何？第66頁(yè)，共80頁(yè)，2023年，2月20日，星期三*§8．4命題邏輯在邏輯電路與語(yǔ)句邏輯中的應(yīng)用第67頁(yè)，共80頁(yè)，2023年，2月20日，星期三

1簡(jiǎn)單開(kāi)關(guān)電路的化簡(jiǎn)

例8.23

化簡(jiǎn)如圖8.1所示的開(kāi)關(guān)電路。解：該電路結(jié)構(gòu)的公式：

f=(u∨v)∧（x∧(u∨y)∨X∧(u∨w)∨(y∨z)∧Z∧u）將其等價(jià)變形化簡(jiǎn)之：

fu∧（x∧(u∨y)∨X∧(u∨w)∨(y∨z)∧Z∧u）∨v∧（x∧(u∨y)∨X∧(u∨w)∨(y∨z)∧Z∧u）u∨（v∧（(x∧y)∨（X∧w)））第68頁(yè)，共80頁(yè)，2023年，2月20日，星期三與最簡(jiǎn)式相對(duì)應(yīng)的開(kāi)關(guān)電路圖（圖8.2）：圖8.2所示的電路與圖8.1所示的電路具有相同的功能，但較前大大簡(jiǎn)化了。這在實(shí)際生產(chǎn)過(guò)程中，在自動(dòng)控制和電路設(shè)計(jì)中，有著很重要的意義。第69頁(yè)，共80頁(yè)，2023年，2月20日，星期三2開(kāi)關(guān)電路分析

開(kāi)關(guān)電路分析的任務(wù)是：確定電路接通或斷開(kāi)的條件，即確定相應(yīng)的邏輯公式之值為1或0的條件。很顯然，我們可以得到如下的方法：電路工作的條件：①寫(xiě)出給定的開(kāi)關(guān)電路相對(duì)應(yīng)的邏輯命題公式；②將該表達(dá)式化為析取標(biāo)準(zhǔn)式；③令其某一項(xiàng)取值為1即可。第70頁(yè)，共80頁(yè)，2023年，2月20日，星期三

例8.24

試決定下圖（圖8.3）所示的電路工作的條件。解：該電路的表達(dá)式為

f=（X∧y∧z）∨（u∧v∧x）此為析取范式。令X∧y∧z=1，得

x=0，y=1且z=1；或令u∧v∧x=1，得u=1，v=1且x=1。以上結(jié)果表明使電路工作時(shí)，各開(kāi)關(guān)x、y、z、u、v所應(yīng)取的開(kāi)或閉的狀態(tài)。第71頁(yè)，共80頁(yè)，2023年，2月20日，星期三（2）電路不工作的條件：①寫(xiě)出給定的開(kāi)關(guān)電路相對(duì)應(yīng)的布爾表達(dá)式；②將該表達(dá)式化為合取范式；③令其某一項(xiàng)取值為0即可。對(duì)于塔型開(kāi)關(guān)電路，可化為1值小項(xiàng)范式（即主析取范式）或0值大項(xiàng)范式（即主合取范式），以分別確定其工作或不工作的條件。第72頁(yè)，共80頁(yè)，2023年，2月20日，星期三3邏輯電路設(shè)計(jì)例8.25一家航空公司，為了保證安全可靠，用計(jì)算機(jī)復(fù)核飛行計(jì)劃。每臺(tái)計(jì)算機(jī)能給出飛行計(jì)劃正確或者有誤的回答。由于計(jì)算機(jī)也有可能發(fā)生故障，因此采用3臺(tái)計(jì)算機(jī)同時(shí)復(fù)核。由所給信息，根據(jù)“少數(shù)服從多數(shù)”的原則作出判斷。試將結(jié)果用命題公式表示，并加以簡(jiǎn)化，設(shè)計(jì)出相應(yīng)的電路圖。第73頁(yè)，共80頁(yè)，2023年，2月20日，星期三第74頁(yè)，共80頁(yè)，2023年，2月20日，星期三4指令變換

例8.26

一位觀(guān)測(cè)者看著在自己面前緩緩移動(dòng)的紙帶上的數(shù)字，他必須按照指令把某些數(shù)字消除掉。這指令內(nèi)容如下：“把能被3除盡，末尾是0，各數(shù)字之和大于31的數(shù)消除；把不能被3除盡，末尾是0，各數(shù)字之和小于31的數(shù)消除；把能