1、離散數學常考題型梳理第6章 命題邏輯一、題型分析本章主要介紹命題、聯結詞的概念，命題公式與翻譯，真值表與等價公式，重言式與蘊含式，范式和命題邏輯的推理理論等內容。經常涉及到的題型有：6-1 將陳述句翻譯成命題公式6-2 求命題公式的真值6-3 命題公式類型的判斷6-4 等價公式的證明6-5 求范式和主范式6-6判斷有效結論的直接證法和間接證法因此，在本章學習過程中希望大家要清楚地知道：1將陳述句翻譯成命題公式命題表述為具有確定真假意義的陳述句。命題必須具備二個條件：語句是陳述句；語句有唯一確定的真假意義。因此判斷一個句子是否為命題，應首先判斷它是否為陳述句，再判斷它是否有唯一的真值。例如，“北

2、京是中國的首都”是陳述句，有確定的真假意義，是命題，為真命題。將陳述句翻譯成命題公式關鍵在于陳述句的邏輯含義要與命題公式的邏輯含義保持一致。因此首先要注意陳述句中表示特殊邏輯關系的詞語的含義，其次要掌握五個聯結詞“， ， ，”所表示的命題間的邏輯關系：“” 是唯一一元聯結詞，表示否定；合取聯結詞“”在語句中相當于“不但而且”，“既又”；析取聯結詞“”在語句中表示“或”的含義；條件聯結詞“”在語句中表示“如果P則Q”或“只有Q，才P”；雙條件聯結詞“”在語句中相當于“當且僅當”。例如，“我們不能劃船，又跑步”。設P：我們劃船，G：我們跑步，那么該命題符號化為：或。2求命題公式的真值一般將命題的合

3、式公式簡稱為命題公式。要理解合式公式的遞歸定義： （1）單個命題變元本身是一個合式公式 （2）若A是合式公式，則A是合式公式 （3）若A與B是合式公式，則（AB），（AB），（AB）與（AB）是合式公式（4）當且僅當能夠有限次應用（1）、（2）、（3）所得到的包含命題變元，聯結詞和括號的符號串是合式公式顯然，如果對一個命題公式中的命題變元不給以真值指派，則命題公式無真值可言。如果對命題公式中的每個命題變元都賦以真值（1或0），則命題公式就變成了一個有真值的命題，并可求出其真值。對于特殊的命題公式（永真式和永假式），對命題公式中的命題變元不給以真值指派，利用常用的等價公式也可以求出其真值（永真式

4、為1，永假式為0）。對命題公式中的所有命題變元指派各種可能的真值組合，就可確定這個命題公式對應的取值，將命題變元的所有真值組合及命題公式對應的取值匯列成表，就得到命題公式的真值表如果一個命題公式有n個命題變元，那么命題變元的真值指派就可能出現種不同的組合。在真值表中是包含了命題變元的所有真值指派。例如，如果一個命題公式有3個命題變元，那么命題變元的真值指派就有8種不同的組合，作其真值表就是將這8種真值組合及命題公式對應的真值匯列成表。要非常熟練地掌握命題公式的真值表作法，因為利用真值表可以判定命題公式類型，驗證等價公式和蘊含式，求命題公式的主析取(合取)范式，在推理理論中判別有效結論。3. 命

5、題公式類型的判斷在各種真值指派下均為真的命題公式，稱為重言式或永真式；在各種真值指派下均為假的命題公式，稱為矛盾式或永假式；不是矛盾式的命題公式，稱為可滿足式。 判定命題公式類型的方法：(1) 真值表法：任給命題公式，列出其真值表，若真值表的最后一列全為1，則該公式為永真式；若真值表的最后一列全為0，則該公式是永假式；若真值表的最后一列既非全1，又非全0，則該公式是可滿足式。(2) 等值演算法：利用常用的等價公式，對給定公式進行等值推導，若該公式的真值為1，則該公式為永真式；若該公式的真值為0，則該公式為永假式。既非永真，也非永假，則為非永真的可滿足式。4. 等價公式的證明等價公式：給定兩個命

6、題公式A與B，設P1，P2，Pn為所有出現于A與B中的原子變元，若給P1，P2，Pn任一組真值指派，A與B的真值均相同，則稱公式A與B是等價的或邏輯相等，記作AB，此公式可稱為等價公式。真值表法（驗證公式等價）：將兩個命題公式的真值表列出，在所有的真值指派下，兩個公式的真值都對應相同，則說明兩個公式等價，否則，就不等價。等值演算法（證明公式等價）：利用教材182頁的14個基本等價式對給定公式進行等值演算，可以證明命題公式等價。5求范式和主范式求范式，包括求析取范式、合取范式、主析取范式和主合取范式。關鍵有兩點：其一是準確掌握范式定義；其二是巧妙使用基本等價式中的分配律、同一律和摩根律，結果的前

7、一步適當使用冪等律。范式的相關定義有：合取范式：一個命題公式稱為合取范式，當且僅當它具有形式： A1A2An ， （n1）其中A1，A2，An均是由命題變元或其否定所組成的析取式 析取范式：一個命題公式稱為析取范式，當且僅當它具有形式：A1A2An ， （n1）其中A1，A2，An均是有命題變元或其否定所組成的合取式 布爾合取、小項：n個命題變元的合取式，稱為布爾合取或小項，其中每個變元與它的否定不能同時存在，但兩者必須出現且僅出現一次一般n個命題變元共有個小項。布爾析取、大項：n個命題變元的析取式，稱為布爾析取或大項，其中每個變元與它的否定不能同時存在，但兩者必須出現且僅出現一次一般n個命題

8、變元共有個大項。主析取范式：對于給定的命題公式，若有一個等價公式，它僅僅由小項的析取組成，則該等價式稱為原式的主析取范式 主合取范式：對于給定的命題變元，如果有一個等價公式，它僅僅由大項的合取組成，則該等價式稱為原式的主合取范式 求析取(合取)范式的步驟： 將公式中的聯結詞都化成，(即消去聯結詞，)； 將否定聯結詞消去或移到各命題變元之前； 利用分配律、結合律等，將公式化為析取(合取)范式。求主析取范式(主合取范式)的方法：真值表法：在命題公式的真值表中，真值為1的指派所對應的小項的析取，為此命題公式的主析取范式；在命題公式的真值表中，真值為0的指派所對應的大項的合取，為此命題公式的主合取范式

9、。等值演算法：利用等價公式，求命題公式A的主析取(合取)范式的步驟： 將公式A化為析取(合取)范式； 除去析取(合取)范式中永假(永真)的析取 (合取) 項，并將析取(合取)式中重復出現的合取項(析取項)和相同變元合并。 對于不是小項（大項）的合取（析取）式，補入沒有出現的命題變元，即通過合取（析取）添加PP(PP) 式，然后利用分配律展開公式。一般地，若命題公式A的主析取范式為則A的主合取范式為 由此可見，命題公式A的主析取范式的小項個數與主合取范式的大項個數之和等于。6判斷有效結論的直接證法和間接證法判斷有效結論的過程就是論證過程，基本方法有真值表法、直接證法和間接證法。要重點掌握后兩種方

10、法。直接證法：就是由一組給定的前提，利用一些公認的推理規則，并根據已知的等價公式和蘊含公式，推演得到有效結論的方法在證明過程中一般要用到的兩個公認的推理規則，即P規則與T規則P規則：前提在推導過程中的任何時候都可以引入使用T規則：在推導中，如果有一個或多個公式重言蘊含著公式C，則公式C可以作為前提在推導引用因此要掌握直接證法，就必須理解并掌握好教材第182頁的14個等價公式和14個蘊含公式，并會使用P規則和T規則。將證明的過程用三列的形式表示，第一列為序號，第二列為當前得到的結論，第三列為得到當前結論的理由或根據E與I分別表示已經證明成立的等價式與蘊含式間接證法：有兩種，一種為反證法，是由不相

11、容的概念引出的一種間接證法。相容、不相容：假設公式H1，H2，Hm中的命題變元為P1，P2，Pn，對于P1，P2，Pn的一些真值指派，如果能使H1H2Hm的真值為T，則稱公式H1，H2，Hm是相容的如果對于P1，P2，Pn的每一組真值指派，使得H1H2Hm的真值為F，則稱公式H1，H2，Hm是不相容的其證明思路就是，如要證明，只要把作為前提使用，推出矛盾的結論即可。另一種間接證法就是附加前提證明法：該方法使用的前提是有效結論以蘊含的形式出現，即具有這樣的形式。則把B作為附加前提使用，只要推出結論C即可。即證明。通常將此方法稱為CP規則。二、常考知識點分析常考知識點1：將陳述句翻譯成命題公式（歷

12、年考核次數：6次，本課程共考過6次；重要程度：）1.（2009年10月試卷第11題）將語句“他是學生”翻譯成命題公式解題過程 依據命題必須具備的二個條件，可設P：他是學生， 則該語句翻譯成命題公式為： P 2.（2008年7月試卷第12題）將語句“今天沒有人來”翻譯成命題公式解題過程 依據命題必須具備的二個條件以及否定聯結詞“”的定義，可設 P：今天有人來， 則語句“今天沒有人來” 翻譯成命題公式為 P。3.（2008年7月試卷第11題）將語句“如果所有人今天都去參加活動，則明天的會議取消”翻譯成命題公式解題過程 在該語句中出現表示邏輯關系的連詞“如果，則”，這樣我們就很容易聯想到條件聯結詞“

13、”在語句中表示“如果，則”，但要注意的是，似乎PQ是“因果關系”，但是不一定總有因果關系，只要P，Q是命題，那么PQ就是命題(即有真值)，不管P，Q是否有無因果關系。因此，設P：所有人今天都去參加活動，Q：明天的會議取消，于是該語句可翻譯成命題公式為： P Q 4.（2009年1月試卷第12題）（2010年1月試卷第12題）將語句“我去旅游，僅當我有時間”翻譯成命題公式解題過程 PQ表示的基本邏輯關系是，Q是P的必要條件，P是Q的充分條件，因此復合命題“只要P，就Q”，“P僅當Q”，“只有Q才P”等都可以符號化為PQ的形式。因此可設P：我去旅游，Q：我有時間，則語句“我去旅游，僅當我有時間”翻

14、譯成命題公式為：PQ 5.（2008年9月試卷第12題）將語句“小王去旅游，小李也去旅游”翻譯成命題公式解題過程 合取聯結詞“”在語句中相當于“并且”，“不但而且”，“既又”。但要注意“”與 “并且”等是有區別的，“并且”等要考慮語義，而“合取”只考慮命題之間的關系以及復合命題的取值情況，不考慮語義。因此，可設P：小王去旅游，Q：小李去旅游，則語句“小王去旅游，小李也去旅游”翻譯成命題公式為：PQ常考知識點2：求命題公式的真值（歷年考核次數：1次，本課程共考過6次；重要程度：）1.（2009年 1月試卷第6題）命題公式的真值是 解題過程 依次利用蘊含等價式、結合律和零律，可將該命題公式化為：，

15、因此該公式的真值是1。常考知識點3：命題公式類型的判斷（歷年考核次數：2次，本課程共考過6次；重要程度：）1.（2008年 7月試卷第14題）判斷說明題（判斷下列各題正誤，并說明理由）為永真式 解題過程 正確因為聯結詞運算的優先次序為：，再利用等價公式中的蘊含等價式，吸收律和否定律，對給定公式進行等值推導如下：因此該公式是永真式。以上是利用等值演算法判斷公式的類型，也可利用如下真值表法。PQPQPQP (PQ)P (PQ) P 1100001 1001101 01101110011111由真值表可見該公式在任意真值指派下的真值都是1，因此該公式是永真式。2.（2009年1月試卷第5題）下列公式

16、 ( )為重言式APQPQ B(Q(PQ) (Q(PQ) C(P(QP)(P(PQ) D(P(PQ) Q解題過程 C選A錯誤.因為利用蘊含等價式，可將PQ化為(PQ)，即PQ (PQ)，依據等價聯結詞的定義可知(PQ)PQ為矛盾式。選B錯誤.因為利用蘊含等價式、分配律和結合律，可將(Q(PQ)化為(Q(PQ) (Q(PQ) (QQ)P) (1 P) 1 而用分配律和否定律得(Q(PQ) (QP)(QQ) (QP)0) (QP)依據等價聯結詞的定義可知1(QP)為可滿足式。選C正確.因為利用蘊含等價式可將(P(QP)(P(PQ)化為(P(QP)(P (PQ)，再利用結合律得(P (QP)( P

17、(Q P)。再依據等價聯結詞的定義可知該式為重言式。選D錯誤.因為利用分配律可將(P(PQ)化為(P(PQ) (PP)(PQ) (1 (PQ) (PQ)依據等價聯結詞的定義可知(PQ)Q為可滿足式。常考知識點4：等價公式的證明（歷年考核次數：2次，本課程共考過6次；重要程度：）1.（2008年 9月試卷第5題）下列等價公式成立的為( )APQPQ BP(QP) P(PQ) CQ(PQ) Q(PQ) DP(PQ) Q解題過程 B選A錯誤.因為依據德摩根律，PQ(PQ)，所以PQ與PQ不等價。選B正確.因為依次利用蘊含等價式、分配律和蘊含等價式可得，P(QP) P(QP) P (Q P) P (

18、P Q) P (PQ) P (PQ)。選C錯誤.因為依次利用蘊含等價式、結合律、否定律和零律可得，Q(PQ) Q (PQ) 1，而 Q(PQ) (QP) (Q Q) (QP) 0(QP) ，其真值不等于1。選D錯誤.因為依次利用分配律、否定律和同一律可得，P(PQ) (PP)(PQ) 1(PQ) (PQ)，顯然與Q不等價。2.（2010年 1月試卷第5題）下列公式成立的為( )APQ PQ BPQ PQ CQP P DP(PQ)Q解題過程 D選A錯誤.因為依據德摩根律，PQ (PQ)，顯然與PQ不等價。選B錯誤.因為利用蘊含等價式可得，PQ PQ，同理，PQ PQ，顯然PQ與PQ不等價。選C錯

19、誤.因為QP P是一個蘊含式，依據蘊含的定義，該蘊含式成立只需證明(QP) P為重言式即可。依次利用蘊含等價式、分配律、否定律和同一律，(QP) P (QP) P (QP) P (QP) P (QP) ( P P) (QP) 1 (QP)，顯然結果不是重言式，因此QP P不成立。選D正確.也可以利用直接證法來證明該蘊含式，思路是：證明P(PQ)為真時，Q一定為真。假定P(PQ)為T，則P為T，且PQ為T，由P為F，PQ為T，知Q為T。則P(PQ)Q成立。常考知識點5：求范式和主范式（歷年考核次數：6次，本課程共考過6次；重要程度：）1.（2008年7月試卷第17題）求PQR的析取范式、合取范式

20、、主析取范式、主合取范式 解題過程 依據求析取(合取)范式的步驟可得，P（RQ）P(RQ) PQR （析取范式、合取范式、主合取范式）因此該公式的主析取范式對應的小項為：，故該公式的主析取范式為： (PQR)(PQR) (PQR) (PQR) (PQR) (PQR) (PQR) 。此外，我們也可利用真值表法求該命題公式的主析取范式和主合取范式 PQRPQR小項大項0001PQR0011PQR0101PQR0111PQR1000PQR1011PQR110 1 PQR1111PQR表中所有小項的析取就是公式的主析取范式，所有大項的合取就是公式的主合取范式，從真值表中可以看出所得結果與用上述等值演算

21、法所得結果相同。2.（2008年9月試卷第3題）命題公式（PQ）R的析取范式是 ( ) A（PQ）R B（PQ）R C（PQ）R D（PQ）R解題過程 D 依據求析取范式的步驟可得，（PQ）R(PQ）R (PQ)R，這就是命題公式（PQ）R的析取范式，雖然命題公式的析取范式不唯一，但這個結論與選項D相同，故選擇D。3.（2009年1月試卷第16題）試求出（PQ）R的析取范式，合取范式，主合取范式解題過程 （PQ）R(PQ)R (PQ)R（析取范式） (PR) (QR)（合取范式） (PR)(QQ) (QR)(PP) (PRQ)(PRQ) (QRP)(QRP) (PQR)(PQR) (PQR)

22、（主合取范式） 常考知識點6：判斷有效結論的直接證法和間接證法（歷年考核次數：0次，本課程共考過6次）1. 試證明（）， 。判斷有效結論的直接證法和間接證法，它的理論根據是14個等價公式（P167），14個蘊含式(P170-171)，三個規則(P規則、T規則和CP規則)。在這些公式中，我們并不需要全部記住，記住最基本的即可，在這些公式中，下列這些式子是最基本的和最常用，其它公式有的可以根據它推導出來。14個蘊含式中最常用和最基本的式子有(1)，(2)，(3)，(8)，(10)，(11)。14個等價式中（12）,（14）式用得較少。利用直接證明法和間接證明法來證明，一個關鍵問題就是在多個前提條件

23、下，不知道按什么順序來引入前提？一般的來說是根據析取三段論（或假言推理）（即教材P170第（9）、（10）式），即一個前提中含有A，再引入一個含有A的前提，就可以去掉A了。這樣我們可以先從遠離結論的前提入手，逐步推導出結論。分析：結論是，先從遠離結論的前提（或者）出發引入第一個前提，然后根據析取三段論再引入一個含有的前提（或者），這樣就可以去掉了，只剩下了，再引入一個含有的前提（），就又可以去掉了，只剩下含有、了，這正是結論所需要的。證明：(直接證法) P P T I () P () TI () TI TE 三、模擬練習練習1。（2009年1月試卷第11題）將語句“他不去學校”翻譯成命題公式解

24、析：依據命題和否定聯結詞的定義，可設P：他去學校， 則語句“他不去學校”翻譯成命題公式為 P 練習2。（2009年7月試卷第12題）將語句“今天沒有下雨”翻譯成命題公式解析：依據命題和否定連接詞的定義，可設P：今天下雨， 則語句“今天沒有下雨”翻譯成命題公式為 P練習3。（2008年9月試卷第11題）將語句“如果你去了，那么他就不去”翻譯成命題公式解析：條件聯結詞“”在語句中表示“如果，則”，與本語句中的“如果，那么”，語意相同，再依據否定聯結詞的定義，則可設P：你去，Q：他去，于是語句“如果你去了，那么他就不去”翻譯成命題公式為PQ練習4。（2009年10月試卷第12題）將語句“如果明天不下

25、雨，我們就去郊游”翻譯成命題公式解析：依據條件聯結詞“”在語句中表示“如果，則”，以及否定聯結詞的定義，可設P：明天下雨，Q：我們就去郊游，則該語句可翻譯成命題公式為 P Q 練習5。（2009年7月試卷第11題）將語句“盡管他接受了這個任務，但他沒有完成好”翻譯成命題公式解析：依據合取聯結詞“”在語句中相當于“并且”，“不但而且”，“既又”，以及否定聯結詞的定義，可設P：他接受了這個任務，Q：他完成好了這個任務。則該語句可翻譯成命題公式為 P Q練習6。（2010年1月試卷第11題）將語句“今天考試，明天放假”翻譯成命題公式解析：合取聯結詞“”只考慮命題之間的關系以及復合命題的取值情況等。因

26、此，可設P：今天考試，Q：明天放假則該語句可翻譯成命題公式為 PQ練習7。將語句“如果天不下雪，我有時間，那么我就去市里”翻譯成命題公式解析：依據合取聯結詞“”，在語句中相當于“并且”，“不但而且”，條件聯結詞“” 在語句中表示“如果，則”。因此，可設P：天下雪，Q：我去市里，R：我有時間，則該語句可翻譯成命題公式為：PRQ練習8。命題公式的真值是 解析：該命題公式的真值為1。依據蘊含等價式、結合律和零律，可將該命題公式化為：練習9。命題公式（PQ）Q為（ ）A. 矛盾式 B可滿足式C重言式 D合取范式解析：B因為利用蘊含等價式可將（PQ）Q化為（PQ）Q，利用德摩根律得（PQ）Q，利用分配律得（PQ ）(QQ)，利用否定律得（PQ）1，再利用同一律得PQ，因此該命題公式為可滿足式。練習10。判