1、等價式和蘊涵式第1頁，共80頁，2022年，5月20日，5點29分，星期二 從上節例8.5中我們看到，雖然公式一般隨所含命題變元的真值變化而變化，但也有公式無論變元真值指派是什么它的真值都是真，也有公式無論變元真值指派是什么它的真值都是假，它們是兩類特殊的命題公式即重言式（也叫永真式）和矛盾式（也叫永假式），當然更多的是命題公式的真值隨變元真值的不同有真有假，我們稱它們為可滿足式。第2頁，共80頁，2022年，5月20日，5點29分，星期二定義8.3 對于命題公式A，如果對A中命題變元的一切指派A的真值都為真，則稱命題公式A為重言式（tautology），又稱永真式；記作T。如果對A中命題變元

2、的一切指派A的真值都為假，則稱命題公式A為矛盾式（contradication），又稱永假式。記作F。如果對A中命題變元的一切指派A的真值有真有假則稱A為可滿足式（satisfactable formula）。第3頁，共80頁，2022年，5月20日，5點29分，星期二那么任何一個公式肯定是永真式、永假式和可滿足式三種公式中的一個，判定一個公式是這三類公式中的哪一個往往稱為公式的判定問題，目前我們可以借助真值表有效判定。 很顯然，而當A是永真式（永假式）時， A必為永假式（永真式）。第4頁，共80頁，2022年，5月20日，5點29分，星期二例8.9 用真值表證明(PQ)PQ為重言式。 證 待

3、證公式的真值表為： 表8.9 由表的最后一列可以看出，原式為重言式。第5頁，共80頁，2022年，5月20日，5點29分，星期二 如果能給一組命題公式中的每一變元一個真值，使各表達式均為真，則這一組命題公式是一致的。在給出系統規范時，必須使這些規范一致。例如：“當且僅當系統正常操作時，系統處于多用戶狀態。如果系統正常操作，則它的核心程序正在運行。核心程序不能正常運行，或者系統處于中斷模式。如果系統不處于多用戶狀態，它就處于中斷模式。系統不處在中斷模式”這個系統規范就不一致。第6頁，共80頁，2022年，5月20日，5點29分，星期二822 等價式第7頁，共80頁，2022年，5月20日，5點2

4、9分，星期二我們再來觀察一下例 8.4公式PQ的真值表,它與公式PQ的真值表相同，也就是說，公式PQ與PQ對于P，Q的所有真值指派它們的真值都相同。這時我們稱這兩個公式等價，即有等價式PQPQ。第8頁，共80頁，2022年，5月20日，5點29分，星期二定義3.3 對于命題公式A，B中所有變元的任何指派，A和B的真值都相同，則稱A等價于B，或邏輯相等。記為A B，又稱它為邏輯等價式(logically equivalent)。注意：（1）符號“”與“”的區別：“”表示兩個公式等價，是關系符，而“”是邏輯聯接詞，任何兩個公式都可以用它聯接成一個新的公式。（2）“”與“”還有密切的聯系：易證AB當

5、且僅當AB是重言式。（3）“”是公式間的一個等價關系，滿足自反性、對稱性和傳遞性。首先我們有以下的基本等價式，它們都是以命題定律的形式出現的，故也叫命題定律。其中A，B，C表示任意命題變元：第9頁，共80頁，2022年，5月20日，5點29分，星期二 表8 .10 第10頁，共80頁，2022年，5月20日，5點29分，星期二除以上基本等價式外，還有一些不是運算律的重要等價式，也是在今后常用的。E20 ABABE21 ABBAE22 A B (AB)(BA)E23 A B (AB)(AB)E24 ABCA(BC) 第11頁，共80頁，2022年，5月20日，5點29分，星期二說明：這些等價式是

6、今后作運算和推理的重要依據，它們就象代數中(a+b)2=a2+2ab+b2, (a+b)3=a3+3a2b+3ab2+b3那么重要。如E21就是我們熟悉的原命題與其逆否命題等價。基本等價式的運算律與集合運算滿足的運算律相似，它們的對應是：對應，對應， 對應（補），T對應E（全集）， F對應（空集），讀者可以對應記憶。當然它們都可以用真值表來驗證。上面所有等價式中的A，B，C是任意的公式也可以，因為對任意的命題變元成立的等價式與變元取值無關，因此把變元換成任意公式也成立。第12頁，共80頁，2022年，5月20日，5點29分，星期二如：（PQ）（PQ）T；（AB）（AB）F（AB）C （AB）C

7、 因此我們今后要靈活運用這些等價式。前面已述，我們可以用真值表來判定一個公式是永真式、永假式還是可滿足式，也可以用真值表來判斷兩個公式是否等價。但真值表對公式含有少量變元是可行的，當變元數目增長時，就不可行了。 第13頁，共80頁，2022年，5月20日，5點29分，星期二例如，對于含20個變元的公式，它的真值指派組合有220=1048576組，顯然此時需要用一臺計算機幫你做這個工作。可當變元有1000個時，一臺計算機要檢查21000種真值組合的真值在幾億年內都不能完成，而迄今為止尚沒有其他已知的計算過程能使計算機在合理可接受的時間內完成，這涉及到算法復雜性問題，也是計算機解決問題最重要最根本

8、的問題。第14頁，共80頁，2022年，5月20日，5點29分，星期二那么我們還可以用什么方法判定一個公式是哪一種公式，還能用什么方法討論兩個公式等價呢？那就是現在的等價公式。依據等價公式作運算，還有一個重要的置換規則。第15頁，共80頁，2022年，5月20日，5點29分，星期二定理8.1 置換原理（rule of replacement）設A為一命題公式，C為A的子公式，且CD。若將A中出現子公式C的某處（未必全部）替換為D后得到的公式記為B，那么AB。這是明顯的。由于C和D等值，因而用D替換C不會改變A的真值，因此B與A等值。在邏輯運算中用置換規則和在代數中運用那些恒等式是相似的。第16

9、頁，共80頁，2022年，5月20日，5點29分，星期二例8.11求證：Q（PQ）P）是一個重言式。證：原式 Q（PQ）P） Q（PQ）P） Q（PP）（PQ） Q（T（PQ） Q（PQ） （QQ）P TP T所以，Q（PQ）P）是一個重言式。第17頁，共80頁，2022年，5月20日，5點29分，星期二例8.12試證對任意公式A，B，C， (AB)C (AC)(BC)證： (AB)C(AB)C (AB)C (AC)(BC) (AC) (BC) (AC) (BC) 故等價公式成立。第18頁，共80頁，2022年，5月20日，5點29分，星期二例8.13 化簡命題公式：（P QR）（P QR）

10、解：原式（QR ）P）（QR） P）（QR ）（PP）（QR ）T （QR ）第19頁，共80頁，2022年，5月20日，5點29分，星期二從例中可看出，一個命題公式的表示形式并不是唯一的，可以有多種不同的表達式，通過等值演算可以尋求出最簡單的邏輯表達式。這在數字電路中，當電路的功能明確后，如何尋求簡單而又可靠的電子線路，提供了有力的手段。這一點我們在下一節中會看到。第20頁，共80頁，2022年，5月20日，5點29分，星期二823 蘊涵式第21頁，共80頁，2022年，5月20日，5點29分，星期二我們知道兩個公式A，B等價，即A B 當且僅當AB是重言式。而A B (AB)(BA)，從而

11、 AB與BA 都為重言式。如果現在只要求AB一個是重言式，則就是我們下邊要研究的另一種公式間的關系-蘊涵。 第22頁，共80頁，2022年，5月20日，5點29分，星期二定義8.5 當命題公式AB為永真式時，稱A邏輯蘊涵B，記為A B，又稱它為邏輯蘊涵式(logically implication)。與符號“”與“”的區別類似，同樣要注意符號 “” 與“”的區別。考慮“”還是公式間的一個等價關系嗎？ 我們可以很容易得出下面十分重要的邏輯蘊涵式：第23頁，共80頁，2022年，5月20日，5點29分，星期二表8.11第24頁，共80頁，2022年，5月20日，5點29分，星期二由定義，要證A B

12、，只要證AB為永真式，進而用真值表或依據置換規則的等價變形都可以。但對蘊涵我們還有兩個特殊的方法： A）前真推后真法：即由前件A為真若能推得后件也為B真，則A B。因為A真B也一定為真的話，則AB不存在A真B假的情況，從而AB永真。B）后假推前假法：即由后件B為假若能推得前件A也為假，則A B。因為B假A也一定為假的話，則AB不存在A真B假的情況，從而AB永真。第25頁，共80頁，2022年，5月20日，5點29分，星期二例8.14證明：(AB) B A 證：（用前真推后真法）假設前件(AB) B為真，則AB為真，B也為真，于是B為假，又AB為真，從而A為假，故A為真，所以(AB) B A。第

13、26頁，共80頁，2022年，5月20日，5點29分，星期二例8.15對任意公式A，B，C，證明： ABA(CB)證：法一：用后假推前假法假設后件A(CB)為假，則A為真，CB為假，于是A為假，C為真，B為假，從而AB為假，故ABA(CB)。法二：依據等價式和置換規則作等價變形（以后簡稱等價變形法）因為ABA(CB) （AB）A(CB) ABACBT故ABA(CB)。讀者還可以用真值表嘗試一下。第27頁，共80頁，2022年，5月20日，5點29分，星期二很明顯：邏輯等價式與邏輯蘊涵式有如下關系：定理8.2 AB當且僅當A B且B A 即說明等價是雙向的，蘊涵是單向的。第28頁，共80頁，20

14、22年，5月20日，5點29分，星期二練習821、試判定下列各式是三類公式的那一類： （1）(PQ)(QP) （2）P(PQ) （3）Q(PQ) （4）PQ(PQ) 2、證明下列邏輯等價式： （1）AB (AB)(AB)（2）A(BC) B(AC)（3）A(BC) (AB)(AC)（4）(AB)(AB) A 3、證明下列邏輯蘊涵式： （1）AB AB （2）(AB)A A （3）AB (AB)A)B（4）(AB)C A(BC) （5）(AB)(AC)(BC) C（6）(AB) A(BC) 4、化簡下列各式： （1）(AB)(AB)(AB) （2）B(AB)A) （3）(PQ) (QP) （4）

15、(QP) (PQ) （5）(Q(PQ)P)(QP)第29頁，共80頁，2022年，5月20日，5點29分，星期二8 3 命題公式的范式第30頁，共80頁，2022年，5月20日，5點29分，星期二在第一節我們介紹了五個聯接詞，強調它們是基本的重要的，因為它們是自然語言中最常用的。實際上，只有這五個是不夠用的，我們還會涉及其它的聯接詞。第31頁，共80頁，2022年，5月20日，5點29分，星期二831 聯結詞的擴充與最小聯接詞集首先我們回過頭來分析一下五個基本聯接詞，我們發現其中的析取“”所表示的“或者”允許兩個都為真，即是可兼的，且當A，B都為真時，AB為真。而比如一快餐館中寫到：一套快餐包

16、括“主菜一個，湯或沙拉一份”，此句中的“或”不是可兼的。再來區分一下：“明天上午我或者在教室或者在圖書館”，“明天上午十點我或者在教室或者在圖書館”，前一語句中的“或”是可兼的，可用“”來表示，而后一語句中的“或”是不可兼的，不能用“”來表示。本節我們要引進邏輯電路中涉及的 “異或（不可兼或）門”、 “與非門”、“或非門”等四個擴充聯接詞。當然我們只作最少的介紹。 第32頁，共80頁，2022年，5月20日，5點29分，星期二“異或（不可兼或）”，用符號（或 ）表示，其含義可由下列等價式決定：PQ (PQ)(PQ) (P Q) (PQ) (PQ)也就是說當P，Q都為真時PQ為假。“與非（NAN

17、D）詞”，用記號表示，也稱為悉非爾（Sheffer）豎，其含義可由下列等價式決定：PQ(PQ)這說明當P，Q都為真時PQ為假。第33頁，共80頁，2022年，5月20日，5點29分，星期二“或非（NOR）”，用記號表示，也稱為皮爾斯（Peirce）箭頭，其含義可由下列等價式決定： PQ(PQ) 這說明當P，Q都為假時PQ為真。 “蘊涵否定詞”，用記號 表示，其含義可由下列等價式決定： PQ(PQ)第34頁，共80頁，2022年，5月20日，5點29分，星期二那么到現在為止，我們共介紹了九個聯接詞，可以證明這九個聯接詞就夠用了，即滿足完備性。但從我們本節引進的四個擴充聯接詞看，它們都能用前邊五個

18、基本聯接詞表示，而由等價式知道，和又能用，來等價表示，同時由德摩根律PQ(PQ)，PQ(PQ)又能將與互相轉換，因而，和，都是完備聯接詞集（complete group of connectives）。我們容易說明與，與是相互獨立的，我們稱既具有完備性又具有獨立性的聯接詞集為最小聯接詞集。 第35頁，共80頁，2022年，5月20日，5點29分，星期二常見的最小聯接詞集有，。，在研究邏輯系統的演繹和推理時很重要，在程序系統的研究中也經常用，如ifthenelse;，在大規模集成電路中有廣泛應用。注意，等都不是最小聯接詞集。但，是完備集，等價表示一公式也較簡單，因此是常用的聯接詞集。如布爾代數系

19、統以及下面要介紹的范式，就只用，三個聯接詞。第36頁，共80頁，2022年，5月20日，5點29分，星期二8.3.2 析取范式和合取范式第37頁，共80頁，2022年，5月20日，5點29分，星期二我們已經知道，對眾多的命題公式，可以依據它們之間的邏輯等價關系進行分類，使相互邏輯等價的公式為一類。那我們想，是否可以在各類公式中分別選出一個公式作為各類的“代表”，而且使它們具有統一的規范形式呢？這就是我們現在要講的公式的范式或標準形式。第38頁，共80頁，2022年，5月20日，5點29分，星期二定義8.5 命題公式A稱為析取范式（disjunctive normal form），當且僅當它具有

20、型式：A1A2An （n1）其中A1,A2,An為由命題常元、變元及它們的否定組成的合取式。如PQ，P(QP)Q都是析取范式。第39頁，共80頁，2022年，5月20日，5點29分，星期二定義8.6 命題公式A稱為合取范式（conjunctive normal form），當且僅當它具有型式：A1 A1A2An （n1）其中A1,A2,An為由命題常元、變元及它們的否定組成的析取式。如PQ，P（PQ）（PQQ）都是合取范式。 注：P，P都可以看成特殊的析取范式和合取范式，PQ是析取范式，也可以看成是含有一個析取式的合取范式。第40頁，共80頁，2022年，5月20日，5點29分，星期二例8.1

21、6求P(PQ)的析取范式及合取范式。 解：P(PQ) P(PQ)P(PQ)( P)析取范式 (PP)(PQ)P(PQ)( P)合取范式第41頁，共80頁，2022年，5月20日，5點29分，星期二 例8.17求 (PQ) (PQ)的析取范式和合取范式。解：(PQ) (PQ)（(PQ) (PQ)）( (PQ)(PQ)（PQ) (P）( (PQ)（PQ)(PQ)（PQ) 合取范式(PP)（PQ）（PQ) （QQ) （PQ）（PQ) 析取范式第42頁，共80頁，2022年，5月20日，5點29分，星期二我們看到：任一命題公式都可化為與其等價的析取范式和合取范式。其等價推演的方法步驟是：第一步，消去公

22、式中的聯結詞和：把公式中的PQ化為PQ；把公式中的PQ化為(PQ)(QP)或(PQ) (PQ)；第二步，將否定聯結詞 向內深入，使之只作用于命題變元或命題變元的否定，然后將P化為P；第三步，利用分配律，將公式進一步化為所需要的范式。 第43頁，共80頁，2022年，5月20日，5點29分，星期二我們已經發現，一公式的析取范式和合取范式可能不是唯一的，例如另一方面，一公式的合取范式與析取范式又可能是同一的。例如，P既是P(PQ)的合取范式，又是它的析取范式。又如PQ既可稱為PQ的析取范式，又可稱為它的合取范式。上述兩點不能不說是析取范式和合取范式的缺點，因此，我們需要更加規范公式的范式，這就是下

23、面的主范式。 第44頁，共80頁，2022年，5月20日，5點29分，星期二8.3.3 主析取范式與主合取范式第45頁，共80頁，2022年，5月20日，5點29分，星期二主析取范式主析取范式與析取范式的區別就在于對析取范式中的合取式有更嚴格的要求，即要達到都是小項。那么什么是小項，小項又有什么性質呢？第46頁，共80頁，2022年，5月20日，5點29分，星期二定義8.7 在含n個變元的合取式中，若每個變元與其否定二者必出現且僅出現一個，則稱此合取式為含n個變元的小項。 如：兩個變元P，Q能夠組成的小項有：4 = 22 個 PQ， PQ，PQ，PQ三個變元P，Q，R能夠組成的小項有：8 =

24、23 個PQR，PQR， PQR，PQR，PQR，PQR， PQR，PQR因此，n個變元能夠組成的小項有2N個.第47頁，共80頁，2022年，5月20日，5點29分，星期二我們知道2N隨n的增長速率很快，下面討論一下對小項編碼問題。由于含有n個變元的每個小項都是n項的合取，而每一項或者是變元出現或者是變元否定出現。我們約定：當變元出現時相應位置記為“1”；當變元否定出現時相應位置記為“0”。這樣每個小項就對應一個n位二進制數。那么這個小項的編碼就用m帶上這個n位二進制數為右下標組成。如PQ的編碼為m01，PQR的編碼為m101，因此小項與編碼是一一對應的，編碼為m010的小項為PQR。再來看

25、看小項的性質，我們從它們的真值表去分析：（表8 .12和表8 .13分別是兩個變元的小項與三個變元的小項真值表）第48頁，共80頁，2022年，5月20日，5點29分，星期二第49頁，共80頁，2022年，5月20日，5點29分，星期二由上兩個小項真值表不難看出，小項具有如下性質：任兩小項均不等價；每個小項有且僅有一組指派使其真值為真，且恰當指派與小項編碼一致時。即其它任何指派都使此小項為假。如小項m101只在指派101時為真，其它指派都是假。有了對小項的充分討論，下面我們研究主析取范式的概念、性質與求法。第50頁，共80頁，2022年，5月20日，5點29分，星期二定義8.8 對一析取范式，

26、若其每一個合取式均為小項時，即是主析取范式（majordisjunctive normal form）。第51頁，共80頁，2022年，5月20日，5點29分，星期二我們可以有兩種方法求主析取范式：方法1：真值表法真值表中使公式A為真的指派所對應的小項組成的析取式即為A的主析取范式。其道理不難從小項的性質得出這樣的主析取范式與A等價，因而可作為A的主析取范式。第52頁，共80頁，2022年，5月20日，5點29分，星期二例8.18 用真值表求 P Q的主析取范式解：P Q的真值表為： 表8.14因此P Q的主析取范式為m00 m01 m11 （PQ）（PQ）（PQ）由此我們知道，一個公式的主析

27、取范式是惟一的。第53頁，共80頁，2022年，5月20日，5點29分，星期二方法2：等價變形法例8.19 用等價變形法求 P Q的主析取范式解：P Q PQ（這是析取范式。現將這范式中的合取式P添加變元Q, 合取式Q添加P, 即填滿變元P、Q, 以構成小項）（P（QQ）（Q（PP）（PQ）（PQ）（PQ）第54頁，共80頁，2022年，5月20日，5點29分，星期二由此得出利用等價變形法求公式的主析取范式的方法步驟：第一步：求出該公式的析取范式；第二步：除去范式中所有恒假的合取式，即化掉含有互補對的合取式；同時，將合取式中同一變元的多個出現合并為一個；第三步：對并非每一變元都出現的析取范式中

28、的合取式，利用PPTP(QQ)把未出現的變元（Q）補進來，并用分配律將其展開，最后得到給定公式的主析取范式。 第55頁，共80頁，2022年，5月20日，5點29分，星期二下面我們對應地介紹主合取范式。主合取范式 主合取范式與合取范式的區別就在于對合取范式中的析取式有更嚴格的要求，即要達到都是大項。那么什么是大項，大項又有什么性質呢？第56頁，共80頁，2022年，5月20日，5點29分，星期二定義8.9 在含n個變元的析取式中，若每個變元與其否定二者必出現且僅出現一個，則稱此析取式為含n個變元的大項。如：兩個變元P，Q能夠組成的大項有：4 = 22 個PQ， PQ，PQ，PQ三個變元P，Q，

29、R能夠組成的大項有：8 = 23 個PQR，PQR， PQR，PQR，PQR，PQR， PQR，PQR因此，n個變元能夠組成的大項有2N個.同樣，下面討論一下對大項編碼問題。由于含有n個變元的每個大項都是n項的析取，而每一項或者是變元出現或者是變元否定出現。第57頁，共80頁，2022年，5月20日，5點29分，星期二我們約定：當變元出現時相應位置記為“0”；當變元否定出現時相應位置記為“1”。這樣每個大項就對應一個n位二進制數。那么這個大項的編碼就用M帶上這個n位二進制數為右下標組成。如PQ的編碼為M10，PQR的編碼為M010，因此大項與編碼是一一對應的，編碼為M101的小項為PQR。再來

30、看看大項的性質，我們也從它們的真值表去分析：（表8 .15和表8 .16分別是兩個變元的大項與三個變元的大項真值表） 第58頁，共80頁，2022年，5月20日，5點29分，星期二第59頁，共80頁，2022年，5月20日，5點29分，星期二由上兩個大項真值表不難看出，大項具有如下性質： 任兩大項均不等價；每個大項有且僅有一組指派使其真值為假，且恰當指派與大項編碼一致時。即其它任何指派都使此大項為真。如大項M101只在指派101時為假，其它指派都是真。有了對大項的充分討論，下面我們研究主合取范式的概念、性質與求法。第60頁，共80頁，2022年，5月20日，5點29分，星期二定義8.10 對一

31、合取范式，若其每一個合取式均為大項時，即是主合取范式（conjunctive normal form）。我們也可以有兩種方法求主合取范式：方法1：真值表法真值表中使公式A為假的指派所對應的大項組成的合取式即為A的主合取范式。其道理不難從大項的性質得出這樣的主合取范式與A等價，因而可作為A的主合取范式。第61頁，共80頁，2022年，5月20日，5點29分，星期二例8.20 用真值表求 P Q的主合取范式解：由表8.14知， P Q的主合取范式為M10 （PQ）由此我們知道，一個公式的主合取范式也是惟一的。第62頁，共80頁，2022年，5月20日，5點29分，星期二方法2：等價變形法例8.21

32、 求公式(PQ)R的主合取范式。 解： (PQ)R (PR)(QR) (P(QQ)R)(PP)QR)(pQR)(PQR)(PQR)(PQR) (PQR)(PQR)(PQR) 第63頁，共80頁，2022年，5月20日，5點29分，星期二由此得出利用等價變形法求公式的主合取范式的方法步驟：第一步：求出該公式的合取范式；第二步：除去范式中所有恒真的析取式，即化掉含有互補對的析取式；同時，將析取式中同一變元的多個出現合并為一個；第三步：對并非每一變元都出現的析取范式中的析取式，利用PPFP (QQ)把未出現的變元（Q）補進來，并用分配律將其展開，最后得到給定公式的主合取范式。應用主析取范式分析和解決

33、實際問題。 第64頁，共80頁，2022年，5月20日，5點29分，星期二例8.22某科研所要從3名科研骨干A，B，C中挑選12名出國進修。由于工作需要，選派時要滿足以下條件：（1） 若A去，則C同去；（2） 若B去，則C不能去；（3） 若C不去，則A或B可以去。問所里應如何選派他們？解：設P：派A去Q：派B去R：派C去那么需要滿足的條件是(PR)(Q R)(R( PQ)經過變形可得(PR)(QR)(R( PQ) m001m010m101（PQR）（PQR ）（PQR因此，選派方案有三種：（a） C去，而A，B都不去；（b） B去，而A，C都不去；（c） A，C同去，而B不去。第65頁，共80

34、頁，2022年，5月20日，5點29分，星期二練習8.3*1、把公式(pq) ( qp)變換為與之等價的、只含聯結詞 ，的公式。2、求下列公式的析取范式、合取范式及主析取范式、主合取范式，并據主析（合）取范式直接確定使該公式為真和為假的指派：（1）(PQ)(PQ)（2）Q(PQ)（3）P(P(Q(QR)（4）P(P(QR)（5）(PQ)PQ（6）(PQ) (PQ)(PQ)*（7）(PQ) （PQ）*（8）(PQ) （PQ）3、某單位要在A、B、C、D四個人中派兩個人出差，按下述三個條件有幾種派法：？如何派？（1）若A去，則C和D中要去一人；（2） 若B和C不能都去；（3） 若C去，則D要留下。

35、 4、A、B、C、D四人做競賽游戲，其中三人報告情況如下： A：C第一，B第二； B：C第二，D第三； C：A第二，D第四。 后經核實發現每個人的報告都是至少有一個為真，問實際名次究竟如何？第66頁，共80頁，2022年，5月20日，5點29分，星期二*84命題邏輯在邏輯電路與語句邏輯中的應用第67頁，共80頁，2022年，5月20日，5點29分，星期二 1 簡單開關電路的化簡例8.23 化簡如圖8.1所示的開關電路。解：該電路結構的公式： f=(uv) （x(uy) X(uw) (yz) Zu） 將其等價變形化簡之： fu（x(uy) X(uw) (yz) Zu）v（x(uy) X(uw)

36、(yz) Zu）u（v（(xy)（Xw)） 第68頁，共80頁，2022年，5月20日，5點29分，星期二 與最簡式相對應的開關電路圖（圖8.2）：圖8.2所示的電路與圖8.1所示的電路具有相同的功能，但較前大大簡化了。這在實際生產過程中，在自動控制和電路設計中，有著很重要的意義。第69頁，共80頁，2022年，5月20日，5點29分，星期二2 開關電路分析開關電路分析的任務是：確定電路接通或斷開的條件，即確定相應的邏輯公式之值為1或0的條件。很顯然，我們可以得到如下的方法：電路工作的條件： 寫出給定的開關電路相對應的邏輯命題公式； 將該表達式化為析取標準式； 令其某一項取值為1即可。第70頁

37、，共80頁，2022年，5月20日，5點29分，星期二 例8.24 試決定下圖（圖8.3）所示的電路工作的條件。解：該電路的表達式為 f=（Xyz）（uvx）此為析取范式。令Xyz=1，得 x=0，y=1且z=1 ；或令uvx=1，得u=1，v=1且x=1。以上結果表明使電路工作時，各開關x、y、z、u、v所應取的開或閉的狀態。 第71頁，共80頁，2022年，5月20日，5點29分，星期二（2）電路不工作的條件： 寫出給定的開關電路相對應的布爾表達式； 將該表達式化為合取范式； 令其某一項取值為0即可。對于塔型開關電路，可化為1值小項范式（即主析取范式）或0值大項范式（即主合取范式），以分別

38、確定其工作或不工作的條件。第72頁，共80頁，2022年，5月20日，5點29分，星期二3 邏輯電路設計例8.25 一家航空公司，為了保證安全可靠，用計算機復核飛行計劃。每臺計算機能給出飛行計劃正確或者有誤的回答。由于計算機也有可能發生故障，因此采用3臺計算機同時復核。由所給信息，根據“少數服從多數”的原則作出判斷。試將結果用命題公式表示，并加以簡化，設計出相應的電路圖。第73頁，共80頁，2022年，5月20日，5點29分，星期二第74頁，共80頁，2022年，5月20日，5點29分，星期二4 指令變換例8.26 一位觀測者看著在自己面前緩緩移動的紙帶上的數字，他必須按照指令把某些數字消除掉。這指令內容如下：“把能被3除盡，末尾是0，各數字之和大于31的數消除；把不能被3除盡，末尾是0，各數字之和小于31的數消除；把能被3除盡，末尾是0，各數字之和小于31的數消除；再把不能被3除盡，末尾是0，各數字之和大于31的數消除；把能被3除盡，末尾不是0，各數字之和