離散數(shù)學 第6章 命題邏輯

1、離 散 數(shù) 學第3編 數(shù)理邏輯第六章第六章 命題邏輯命題邏輯6.1 命題的概念與表示 一、基本概念 命題：具有明確的判斷結果的陳述句。 兩個條件：1.陳述句 2.判斷結果唯一確定 真值：命題的判斷結果稱為真值。真為1,假為0。 真命題：判斷結果為真的命題。真值為1。 假命題：判斷結果為假的命題。真值為0。 原子命題：命題的真假可以獨立確定的命題。 復合命題：由原子命題、聯(lián)結詞和括號組合而成的命題。 命題變項：命題常用P,Q,R等表示，當它們表示任意命題時稱為命題變元。1否定 否定表示一個命題的反面，P的否定記作 如果P：天氣熱，那么 ：天氣不熱， 如果P：教室里沒有人，那么 ：教室里有人。 如

2、果命題P是真命題，則 是假命題。 如果命題P是假命題，則 是真命題。用符號表示為： 如果P的真值為1，則 的真值為0，即 。 如果P的真值為0，則 的真值為1，即 。PPP6.2 命題聯(lián)結詞 PPPP0110 2。合取 兩個命題P、Q的合取記作 當P、Q都為真命題時， 才是真命題。P和Q中只要有一個是假命題時， 就是假命題。 命題的合取是將兩個簡單的命題組合在一起，構成一個復合命題。命題的合取具有兩個命題同時成立的含義，“和”、“與”是命題的合取的關鍵字。命題的合取的真值表如右。QPQPQP 的真值表P Q0 0 00 1 01 0 01 1 1QPQP111001,010,0003。析取 兩

3、個命題P和Q的析取記作 命題的析取是將兩個簡單的命題組合在一起，形成一個復合命題，它具有二者中任一成立即可的含義復合命題的真假是由兩個簡單命題的真假決定的。 當P,Q中至少有一個是真命題時， 即為真命題。只有當P,Q都是假命題時， 才是假命題。 命題的析取的真值表如右。 QPQPQP 的真值表P Q0 0 00 1 11 0 11 1 1QPQP111, 101, 110,0004。蘊含 兩個命題P蘊含Q記作 ，它表示由P是真命題能否推論出Q是真命題。如果那么是蘊含命題的關鍵字。 如當P是真命題時Q一定是真命題，則 成立。但是，如果P是假命題，則無論Q是真命題還是假命題， 也都成立在蘊含命題中

4、，P 稱為蘊含的前項，Q 稱為蘊含的后項。當前項為假命題時，蘊含命題一定是真命題。QPQPQP 的真值表P Q0 0 10 1 11 0 01 1 1QP QP 111, 110, 100,0015。等價 如果兩個命題P和Q有同時又有 則記作 就是 合取、析取和等價都滿足交換律，而蘊含是不滿足交換律的。例如， 在一個命題公式中如果沒有括號，各種聯(lián)結詞的運算順序從先到后依次為： QP 的真值表 P Q 0 0 1 0 1 0 1 0 0 1 1 1QP PQ QP QP QP )()(PQQP,PQQPPQQPPQQP, 祈使句、感嘆句、帶有“也許”、“可能”字樣的句子和悖論都不是命題。 將命題

5、符號化的方法是定義命題。不同的定義法，符號化的結果是不同的。課本P.164有6個例子。例如有命題：張三沒有病。 如定義P:張三沒有病，命題符號化的結果為P， 如定義P:張三有病，命題符號化的結果為 P。再如有命題：張三胖但沒有病。 定義：P:張三胖，Q:張三有病，命題符號化的結果為 。要注意：命題只有P才Q，符號化的結果是而不是 。QPPQ QP 例題1： 設P：我們劃船，Q：我們跑步，那么命題“我們不能既劃船，又跑步”可符號化為 。例題2：設P：他生病了。Q：他出差了。R：我同意他不參加學習。則命題“若不是他生病或出差了，我不會同意他不參加學習”符號化的結果為 。例題3：符號化命題：除非天下

6、雨，否則我們不去郊游。此命題的意義為：只有天下雨，我們才去郊游。P：天下雨，Q：我們?nèi)ソ加巍７柣癁椋?(QPRQP)(PQ 1.合式公式 單個命題變元是一個合式公式， 如果A是合式公式，則 是合式公式，如果A、B是合式公式，則 是合式公式，有限次運用所得到的符號串是合式公式。2.命題公式 由命題變元、聯(lián)結詞和園括號組成的合式公式稱為命題公式。命題公式是沒有確定的判斷結果的，只有在真值指派下才有確定的判斷結果。ABABABA,BA 6.3 命題公式的翻譯 6.4 真值表與等價公式一、賦值 對于一個命題公式P中的所有命題變元指定一組真值，則稱為P的一個賦值。 如果在某種賦值下，命題公式P的值為1

7、，這種賦值稱為成真賦值， 如果在某種賦值下，命題公式P的值為0，這種賦值稱為成假賦值。 命題公式P的所有賦值的總和就構成了真值表。二、真值表 在命題公式中，對所有的命題變元指派所有可能取得的真值，從而可以確定此命題公式在各種情況下的真值情況，所得到的表稱為真值表。如果對于兩個命題公式A和B，在任意一組真值指派下， A和B的真值都相同，則稱A和B等值。 記作 。注意： 用于兩個命題的等價， 用于兩個命題公式的等價，稱為等值。兩者不可混淆。BA三、等價公式 等價公式又稱為命題定律，是14組重要的等值式，在命題公式的化簡和證明中經(jīng)常用到。 課本P.167中有這14組等價公式的匯總表，其中要特別記住的

8、有： 5.分配律 6.吸收律 7.摩根律)()()(RPQPRQP)()()(RPQPRQPPQPPPQPP)()(QPQP)(QPQP)( 9.零律 10.否定律 11.蘊含等價 12.雙條件等價 13.假言易位律 14.歸謬律PQPQP)()(QPQPPQQP)()(PQQPQPPPPP1001PPPP四、等值演算 用命題定律對命題公式進行化簡稱為等值演算。例題4： 化簡命題公式解：PQPQP)()(PQPQP)()()()(PQPPQP0)(QP)()(PQPPQPQP一、重言式、矛盾式、可滿足式 如果命題公式P在各種賦值下的值均為真，則稱P為永真式或重言式， 如果命題公式P在各種賦值下

9、的值均為假，則稱P為永假式或矛盾式， 如果命題公式P既不是矛盾式，又不是永真式，則稱P為可滿足式。三、真值表法 判斷一個命題公式是重言式、矛盾式還是可滿足式，可用真值表法。列出真值表，綜觀所有的真值。6.5 重言式與蘊含式例題5： 用真值表證明命題公式 是重言式解：)(RQPPPQR0000100111010110111110011101111101111111)(RQPPRQP三、蘊含式 如果命題公式 是永真式是則稱“P蘊含Q” 記作 蘊含式有14個重要的命題公式，見課本P.170在證明中經(jīng)常用到。課本P.170有5處錯誤。 蘊含式中常用的有：1?；?。附加3。析取三段論4。假言推理5。拒

10、取式QQPPQP,QQPP)(QQPP)(PQPQ)(QP QP QPP6.6 范式一、析取范式和合取范式 由若干個括號通過析取符號連接而成的命題公式稱為析取范式，其中每一個擴號是命題變元或其否定構成的合取式。如 由若干個括號通過合取符號連接而成的命題公式稱為合取范式，其中每一個擴號是命題變元或其否定構成的析取式。如 任何命題公式都存在與之等值的析取范式和合取范式，且形式不唯一。)()(TSPRQP)()(TSRQP二、主析取范式 如組成析取范式的每一個括號中都包括所有的命題變項或其否定形式，則該析取范式稱為主析取范式。在主析取范式中的每一個括號是一個包括所有的命題變項或其否定形式的簡單合取式

11、，稱為小項。 如果將小項中各命題變項看成為1，其否定看成為0, 按字母順序排列后的二進制數(shù)為i,該小項表示為 ， 因此，由兩個命題變項組成的小項為由三個命題變項組成的小項為 ， 在真值表中，真值為1的項是小項，主析取范式就是真值表中所有真值為1的項的析取范式。im30 mm70 mm例題6 求 的主析取范式解： 小項RQP)(PQR0000000101010000110110000101011101111111RQP)(QPRQPRQPRQPRPRQP)7 , 6 , 5 , 3 , 1 ()(76531mmmmmRQP三、主合取范式 如組成合取范式的每一個括號中都包括所有的命題變項或其否定形

12、式，則該合取范式稱為主合取范式。在主合取范式中的每一個括號是一個包括所有的命題變項或其否定形式的簡單析取式，稱為大項。 如果將大項中各命題變項看成為0，其否定看成為1, 按字母順序排列后的二進制數(shù)為i,該大項表示為 ，注意： 不是 ，而是例如，在某命題公式A中P,Q,R為(0,0,1)和(1,1,1)時真值為0，則A的主合取范式可記作為： iM1M)(RQP)(RQP)7 , 1 ()()(RQPRQP由主析取范式可直接求出主合取范式 例如，上面的例3 主析取范式已經(jīng)求得，為那么，它的主合取范式為： 有下列結論，請記?。?任意兩個小項的合取式為永假式，全體小項的析取式為永真式。 任意兩個大項的

13、析取式為永真式，全體大項的合取式為永假式。)7 , 6 , 5 , 3 , 1 ()4 , 2 , 0()()()(RQPRQPRQPRQP)(6.7 命題邏輯的推理理論一、有效結論 如果命題公式 是重言式，則稱C是前提集合 的有效結論，記作二、推理方法 真值表法 真值表法就是用真值表驗證是重言式。例如，前面的例1就是用真值表證明了： CAAAm)(21,21mAAACAAAm21CAAAm)(21)()()(RPRQQP等值演算法 等值演算法就是用等值演算的方法驗證命題公式的化簡結果為1。例如，前面的例1證明，證明： )()()(RPRQQP)()()(RPRQQP)()()(RPRQQP)()()(RPRQQP)()()(RPRQQP)()(RPPRQQ)1 ()()(RRQQQ11)(RQ直接證法 先介紹兩條規(guī)則：P規(guī)則：前提中的命題在任何需要時都可以引入。T規(guī)則：在推導過程中可根據(jù)前提和已得到的結論，按推理規(guī)則得到新的結論。推理證明過程的書寫方法： 1.在左邊第一列中給推理步驟編號， 2.在左邊第二列中書寫引入的前提和推出的結論， 3.在右邊一列中注明運用的規(guī)則，是T規(guī)則時要注明依據(jù)的步驟的編號和推理規(guī)則的種類。 E表示運用的是等價公式，I表示運用的是蘊含公式例題7： 證明證明： P TI TI TI P T I P TE TIDDACCBBA)()()(CCCB