第一章命題邏輯

1、3/28/2022chapter111.1 命題及其表示法命題及其表示法1.2 聯(lián)結詞聯(lián)結詞1.3 命題公式與翻譯命題公式與翻譯1.4 重言式、矛盾式、可滿足公式重言式、矛盾式、可滿足公式1.5 等價與蘊含等價與蘊含1.6 其它聯(lián)結詞其它聯(lián)結詞1.7 對偶與范式對偶與范式1.8 推理理論推理理論 3/28/2022chapter121.1 命題及其表示法命題及其表示法1、命題、命題命題命題非真即假的陳述句。非真即假的陳述句。命題的真值命題的真值對，成立，則真值為真，對，成立，則真值為真，T，1 錯，不成立，則真值為假，錯，不成立，則真值為假，F(xiàn)，0 斷言斷言是一陳述語句。一個命題命題是一個或真

2、或假而不能兩者都是的斷言。如果命題是真, 我們說它的真值真值為真真；如果命題是假，我們說它的真值真值是假假。 3/28/2022chapter13【例例1 】判定下列各語句是否為命題：判定下列各語句是否為命題：(a) 巴黎在法國。巴黎在法國。(b) 煤是白色的。煤是白色的。(c) 3+2=5(d) 別的星球上有生物。別的星球上有生物。(e) 全體立正。全體立正。(f) 明天是否開大會？明天是否開大會？(g) 天氣多好??！天氣多好啊！(h) 我正在說謊。我正在說謊。(i) 如果天氣好，那么我去散步。如果天氣好，那么我去散步。(j) x3（是）（是）（是）（是）（是）（是）（是）（是）（否，祈使句

3、）（否，祈使句）（否，疑問句）（否，疑問句）（否，感嘆句）（否，感嘆句）（否（否, 悖論）悖論）（是（是,復合命題）復合命題）（否，不能確定真值）（否，不能確定真值） 1.1 命題及其表示法命題及其表示法 3/28/2022chapter142、命題的表示、命題的表示命題變元命題變元常用常用P、Q、R、S等大寫字母或加下標的大等大寫字母或加下標的大寫字母寫字母P1, Q2, R10, 表示來表示一個命題，稱為命題變表示來表示一個命題，稱為命題變元。元。如：如： P:巴黎在法國。巴黎在法國。 Q:煤是白色的。煤是白色的。 1.1 命題及其表示法命題及其表示法 3/28/2022chapter15

4、3、命題相關概念、命題相關概念簡單命題（原子命題）簡單命題（原子命題）不能再分解的命題。不能再分解的命題。復合命題復合命題由若干個簡單命題復合而成的命題。由若干個簡單命題復合而成的命題。真值表真值表把組成復合命題的各命題變元的真值的所有把組成復合命題的各命題變元的真值的所有組合及其相對應的復合命題的真值列成表，稱為真值表。組合及其相對應的復合命題的真值列成表，稱為真值表。1.1 命題及其表示法命題及其表示法 3/28/2022chapter16【例例2 】求公式求公式(PQ)P的真值表。的真值表。 解：解： 分以下步求得分以下步求得: (1) 寫出公式寫出公式P的真值表的真值表;(2) 寫出公

5、式寫出公式PQ的真值表的真值表; (3) 根據(jù)根據(jù)(1)和和(2), 寫出公式寫出公式(PQ)P的真值表。的真值表。 為清楚起見為清楚起見, 我們將這步列在一個表內(nèi)我們將這步列在一個表內(nèi), 見下表。見下表。1.1 命題及其表示法命題及其表示法 3/28/2022chapter17【例例3 】求公式求公式 (PR)(QR)的真值表。的真值表。 解：解：公式含有個命題變元公式含有個命題變元P、Q、R, 真值表有真值表有3=8行。其真值表如下表行。其真值表如下表 所示：所示： 1.1 命題及其表示法命題及其表示法 3/28/2022chapter18 1.2 聯(lián)結詞聯(lián)結詞 命題和原子命題?？赏ㄟ^一些

6、聯(lián)結詞構成新命題, 這種新命題叫復合命題（復合命題（Compositional Proposition ）。例如： P: 明天下雪, Q: 明天下雨是兩個命題, 利用聯(lián)結詞“不”, “并且”, “或”等可構成新命題: “明天不下雪”； “明天下雪并且下雨”； “明天下雪或下雨”等 。 3/28/2022chapter191.2 聯(lián)結詞聯(lián)結詞即 ： “非P”； “P并且Q”； “P或Q”等 。 在代數(shù)式x+3 中, x , 3 叫運算對象, +叫運算符, x+3 表示運算結果。在命題演算中, 聯(lián)結詞聯(lián)結詞就是命題演算中的運算符, 叫邏輯運算符邏輯運算符或叫邏輯聯(lián)結詞邏輯聯(lián)結詞。常用的有以下 5

7、個。 3/28/2022chapter1101、否定、否定 P是是P的否定，讀作的否定，讀作“非非P”， “ P的否定的否定” 。0110pp如：如： P:成都是中國的首都。成都是中國的首都。 P：成都不是中國的首都。：成都不是中國的首都。 否定與漢語中的否定與漢語中的“非非”、“不是不是”、“否定否定”是一致是一致的。的。1.2 聯(lián)結詞聯(lián)結詞 3/28/2022chapter1112、合取、合取 PQ是是P和和Q的合取的合取, 讀做讀做“P與與Q”或或“P并且并且Q”。如：如： P: 王華的成績很好。王華的成績很好。 Q: 王華的品德很好。王華的品德很好。 PQ: 王華的成績很好并且品德很好

8、。王華的成績很好并且品德很好。合取與漢語中的合取與漢語中的“和和”、“與與”、“并且并且”是一致的。是一致的。P QP Q0 00 11 01 100011.2 聯(lián)結詞聯(lián)結詞 3/28/2022chapter1123、析取、析取 PQ是是P和和Q的析取的析取, 讀做讀做“P或或Q”。如：如： P:小王喜歡唱歌。小王喜歡唱歌。 Q:小王喜歡跳舞小王喜歡跳舞 。 P Q:小王喜歡唱歌或喜歡跳舞小王喜歡唱歌或喜歡跳舞 。從真值表可知從真值表可知PQ為真為真, 當且僅當當且僅當P或或Q至少有一為真。至少有一為真。P QP Q0 00 11 01 101111.2 聯(lián)結詞聯(lián)結詞 3/28/2022cha

9、pter113 “或”字常見的含義有兩種: 一種是“可兼或可兼或”, 如上例中的或, 它不排除小王既喜歡唱歌又喜歡跳舞這種情況。一種是“排斥或排斥或”（異或）（異或）, 例如“人固有一死, 或重于泰山, 或輕于鴻毛”中的“或”, 它表示非此即彼, 不可兼得。 運算符運算符表示可兼或表示可兼或, 排斥或以后用另一符號表達。排斥或以后用另一符號表達。如：(1)小李明天出差去上?；蛉V州。 (2)劉昕這次考試可能是全班第一也可能是全班第二。 這兩例表示的均是排斥或，即兩種情況不能同時出現(xiàn)，這時便不能僅用析取詞表示。 1.2 聯(lián)結詞聯(lián)結詞 3/28/2022chapter1144、條件、條件 PQ,

10、讀做讀做 “如果如果P, 那么那么Q”或或“P則則Q” 。運算對象運算對象P叫做前提叫做前提 , 假設或前件假設或前件, 而而Q叫做結論或后件。叫做結論或后件。P QP Q0 00 11 01 111011.2 聯(lián)結詞聯(lián)結詞如：如： P:雪是黑的。雪是黑的。 Q:太陽從東方升起太陽從東方升起 。 P Q:如果雪是黑的，則太陽從東方升起如果雪是黑的，則太陽從東方升起 。命題命題PQ是假是假, 當且僅當當且僅當P是真而是真而Q是假。是假。 3/28/2022chapter115 條件與漢語中條件與漢語中“如果如果，就，就”相類似，但有所區(qū)別相類似，但有所區(qū)別:(1)自然語言中，自然語言中，“如果如

11、果P則則Q”，往往，往往P和和Q有一定的因果有一定的因果關系，而條件復合命題關系，而條件復合命題PQ中中 P和和Q 可以完全不相關。可以完全不相關。(2)自然語言中，自然語言中，“如果如果P則則Q”，當，當P為為0、Q為為1時，整個時，整個句子真值難以確定；而條件復合命題句子真值難以確定；而條件復合命題PQ中，當中，當P為為0時，時，復合命題的真值為復合命題的真值為1。 P則則Q的邏輯含義的邏輯含義:P是是Q的充分條件的充分條件,Q是是P的必要條件。的必要條件。 所以所以,“如果如果P則則Q”, “只要只要P則則Q”,只有只有Q才才P”, “僅當僅當Q則則P”都可符號化為都可符號化為PQ 的形

12、式。的形式。1.2 聯(lián)結詞聯(lián)結詞 3/28/2022chapter116如：小李對小王說：如：小李對小王說：“如果天不下雨，我就來找你如果天不下雨，我就來找你”。 天沒下雨，小李去找了小王。天沒下雨，小李去找了小王。 天沒下雨，小李沒去找小王。天沒下雨，小李沒去找小王。 天下雨了，小李去找了小王。天下雨了，小李去找了小王。 天下雨了，小李沒去找小王。天下雨了，小李沒去找小王。1.2 聯(lián)結詞聯(lián)結詞【例【例4 】電燈不亮是電燈壞或電路有毛病?！侩姛舨涣潦请姛魤幕螂娐酚忻?。解：設解：設P電燈不亮，電燈不亮，Q電燈壞，電燈壞，R電路有毛病。電路有毛病。上述語句應表示為上述語句應表示為: (Q R)

13、P 3/28/2022chapter1175、雙條件、雙條件 P Q, 讀做讀做 “P當且僅當當且僅當Q” 。如：如： P:兩個三角形全等。兩個三角形全等。 Q:兩個三角形的對應邊相等兩個三角形的對應邊相等 。 P Q:兩個三角形全等當且僅當其對應邊相等兩個三角形全等當且僅當其對應邊相等 。P當且僅當當且僅當Q的邏輯含義的邏輯含義:P和和Q互為充要條件互為充要條件 。P QP Q0 00 11 01 110011.2 聯(lián)結詞聯(lián)結詞 3/28/2022chapter118 6、聯(lián)結詞的優(yōu)先次序、聯(lián)結詞的優(yōu)先次序聯(lián)結詞的優(yōu)先級：聯(lián)結詞的優(yōu)先級： , , , , ，括號優(yōu)先。，括號優(yōu)先。如：如： (

14、PQ)R 可寫成可寫成 ：PQR (PQ)R 可寫成：可寫成：PQR (P Q)R)(RP)Q) 可寫成：可寫成： (P QR)RPQ 為方便起見，公式最外層的括號可省略。有時為了為方便起見，公式最外層的括號可省略。有時為了看起來清楚醒目看起來清楚醒目, 也可保留某些原可省去的括號。也可保留某些原可省去的括號。 1.2 聯(lián)結詞聯(lián)結詞 3/28/2022chapter119 單個命題變元和命題常元叫原子公式。單個命題變元和命題常元叫原子公式。由以下形成規(guī)則生成的公式叫命題公式命題公式 (簡稱公式簡稱公式): (1) 單個原子公式單個原子公式A、B是命題公式。是命題公式。 (2) 如果如果A和和B

15、是命題公式是命題公式, 則則(A) , (AB) , (AB) , (AB) , (AB)是命題公式。是命題公式。 (3) 只有有限步使用只有有限步使用(1)和和(2)所組成的包含命題變元、所組成的包含命題變元、聯(lián)結詞以及成對的括號組成的符號串才是命題公式。聯(lián)結詞以及成對的括號組成的符號串才是命題公式。 這種定義叫歸納定義, 也叫遞歸定義。由這種定義產(chǎn)生的公式也叫合式公式（合式公式（Well-Formed Formulas），簡），簡寫為寫為wff。1.3 命題公式命題公式 3/28/2022chapter120【例例5】 判斷下列表達式是否為合式公式判斷下列表達式是否為合式公式: p(pq)

16、 (pq)r) (p(qr) (pq)(qr) (pq)r) (pq)r) s) (pq)r) s（是）（是）（是）（是）（否）（否）（否）（否）（否）（否）（是）（是）（是）（是）1.3 命題公式命題公式 3/28/2022chapter121 【例例6】 將下列自然語言形式化將下列自然語言形式化:(a) 如果天不下雨并且不刮風，我就去書店。如果天不下雨并且不刮風，我就去書店。解解 ：設：設P：今天天下雨，：今天天下雨，Q：今天天刮風，：今天天刮風，R：我去書店。：我去書店。 則原命題符號化為：則原命題符號化為： (PQ)R (b) 小王邊走邊唱。小王邊走邊唱。解：設解：設p：小王走路，：小

17、王走路，q：小王唱歌。：小王唱歌。 則原命題符號化為：則原命題符號化為： pq (c) 除非除非a能被能被2整除，否則整除，否則a不能被不能被4整除。整除。解：設解：設p：a能被能被2整除，整除，q：a能被能被4整除。整除。 則原命題符號化為：則原命題符號化為： p q 或或 q p1.3 命題公式命題公式 3/28/2022chapter122 (d) 此時，小剛要么在學習，要么在玩游戲。此時，小剛要么在學習，要么在玩游戲。解：設解：設p：小剛在學習，：小剛在學習，q：小剛在玩游戲。：小剛在玩游戲。 則原命題符號化為：則原命題符號化為： (pq)(pq) 或或 (pq)(pq)(e) 如果天

18、不下雨，我們?nèi)ゴ蚧@球，除非班上有會。如果天不下雨，我們?nèi)ゴ蚧@球，除非班上有會。解：設解：設p：今天天下雨，：今天天下雨，q：我們?nèi)ゴ蚧@球，：我們?nèi)ゴ蚧@球，r：今天班上：今天班上有會。有會。 則原命題符號化為：則原命題符號化為： r (p q)1.3 命題公式命題公式 3/28/2022chapter123 1、 重言式（重言式（Tautology）重言式重言式(永真式永真式)真值恒為真值恒為1的公式。如：的公式。如：PP 【例例7】判斷判斷（P P(P Q)）是否為重言式。）是否為重言式。P QPQP(PQ)P P(PQ)0 00 11 01 10 0 010 0 111 1 11（P P(P

19、 Q)）為重言式。）為重言式。1.4 重言式、矛盾式、可滿足公式重言式、矛盾式、可滿足公式 3/28/2022chapter124 2、 矛盾式（矛盾式（Contradiction)矛盾式（永假式）矛盾式（永假式）真值恒為真值恒為0的公式。如：的公式。如：P P 【例例8】判斷判斷(PQ)P是否為矛盾式。是否為矛盾式。P QPQ(PQ)P0 00 11 01 10 0 010 0 00（ (PQ)P ）為矛盾式。）為矛盾式。1.4 重言式、矛盾式、可滿足公式重言式、矛盾式、可滿足公式 3/28/2022chapter1253、 可滿足公式（可滿足公式（Satisfaction） 可滿足公式可滿

20、足公式至少有一種真值為至少有一種真值為1的情況。的情況。 (除矛盾式之外的公式除矛盾式之外的公式) ，永真式也是可滿足公式。，永真式也是可滿足公式。定理：由定理：由n個命題變元一共可組成個命題變元一共可組成 個不同的命題。其中個不同的命題。其中永真式有一個，矛盾式有一個，可滿足公式有永真式有一個，矛盾式有一個，可滿足公式有 個。個。 n22122n1.4 重言式、矛盾式、可滿足公式重言式、矛盾式、可滿足公式 3/28/2022chapter126 【例【例9】 構造公式構造公式PQ、(PQ)、PQ、Q P的真值的真值 。解：真值表如下：解：真值表如下： 由例題可見，公式由例題可見，公式PQ、(

21、PQ)、PQ、Q P的真值表是完全相同的，我們稱其為等值的。那么如何判的真值表是完全相同的，我們稱其為等值的。那么如何判斷兩個公式等值呢？斷兩個公式等值呢？ 1.5 等價與蘊涵等價與蘊涵 3/28/2022chapter1271.5.1 等價等價1、 等價的定義等價的定義等價等價設設A、B是兩個命題公式，當是兩個命題公式，當A與與B有完全相有完全相同的真值，則稱同的真值，則稱A和和B等價，即為等價，即為AB。定理：設定理：設A、B是兩個命題公式，是兩個命題公式， AB 的充要條件是的充要條件是AB為永真式。為永真式。等價置換：假設等價置換：假設X是公式是公式A的子公式，如果的子公式，如果XY，

22、則將，則將X置換為置換為Y所得的公式與所得的公式與A等價。等價。1.5 等價與蘊涵等價與蘊涵 3/28/2022chapter1282、 等價等價與與雙條件雙條件的區(qū)別的區(qū)別等價等價：不是一個聯(lián)結詞，：不是一個聯(lián)結詞，AB不是一個命題公式，表不是一個命題公式，表示的是示的是A、B之間的邏輯關系。之間的邏輯關系。雙條件雙條件：是一個聯(lián)結詞，：是一個聯(lián)結詞， AB是命題公式。是命題公式。 1.5 等價與蘊涵等價與蘊涵 3/28/2022chapter129 3、常用的等值式、常用的等值式(1)雙重否定律雙重否定律 A A(2)冪等律冪等律 A AA A AA(3)交換律交換律 AB BA AB B

23、A(4)結合律結合律 (AB)C A(BC) (AB)C A(BC)(5)分配律分配律 A(BC) (AB)(AC) A(BC) (AB)(AC)(6)德德摩根律摩根律 (AB) AB (AB) AB1.5 等價與蘊涵等價與蘊涵 3/28/2022chapter130 (7)吸收律吸收律 A(AB) A A(AB) A(8)零律零律 A1 1 A0 0(9)同一律同一律 A0 A A1 A(10)否定律否定律 AA 1 AA 0(11)蘊涵等值式蘊涵等值式 AB AB(12)等價等值式等價等值式 AB (AB)(BA)(13)逆反律逆反律 AB BA(14)輸出律輸出律 A(BC) (AB)C

24、(15)歸謬論歸謬論 (AB)(AB) A1.5 等價與蘊涵等價與蘊涵 3/28/2022chapter131 思考：思考：證明兩個公式等價的方法：證明兩個公式等價的方法：1、構造真值表。、構造真值表。2 、等價推導法。（若一個公式變元太多，由于、等價推導法。（若一個公式變元太多，由于n個變元個變元組成的真值表有組成的真值表有2n行，所以用等價推導的方法來證明。）行，所以用等價推導的方法來證明。）1.5 等價與蘊涵等價與蘊涵 3/28/2022chapter132 【例【例11】用等值演算證明】用等值演算證明p(qr) (pq)r。證明：證明： p(qr) p(qr) （蘊涵等值式）（蘊涵等值

25、式） p(qr) （蘊涵等值式）（蘊涵等值式） (pq) r （結合律）（結合律） (pq) r （德（德摩根律）摩根律） (pq)r （蘊涵等值式）（蘊涵等值式） 1.5 等價與蘊涵等價與蘊涵 3/28/2022chapter133 【例【例12】化解公式】化解公式(p(qr)(qr)(pr)。解：解： (p(qr)(qr)(pr) (pqr)(qp )r) (pq)r)(qp)r) (pq)(qp )r (pq)(qp )r 1r r 1.5 等價與蘊涵等價與蘊涵 3/28/2022chapter134 1.5.2 蘊含蘊含1、蘊涵的定義、蘊涵的定義蘊含蘊含設設A、B是兩個命題公式，若是兩

26、個命題公式，若A為真，為真，B必定為必定為真，則稱真，則稱A蘊含蘊含B，記作，記作AB。定理：設定理：設A、B是兩個命題公式，是兩個命題公式， AB 的充要條件是的充要條件是AB為永真式。為永真式。1.5 等價與蘊涵等價與蘊涵 3/28/2022chapter135 2、蘊含、蘊含與與條件條件的區(qū)別的區(qū)別蘊含蘊含：不是一個聯(lián)結詞，：不是一個聯(lián)結詞，AB不是一個命題公式，表不是一個命題公式，表示的是示的是A、B之間的邏輯關系。之間的邏輯關系。條件條件：是一個聯(lián)結詞，：是一個聯(lián)結詞， AB是命題公式。是命題公式。 1.5 等價與蘊涵等價與蘊涵 3/28/2022chapter136 【例【例13】

27、 證明證明 (PQ)PQ 。證明：真值表如下：證明：真值表如下：由真值表可見，由真值表可見， (PQ)P為為1時，時，Q為真。為真。 (PQ)PQ P QPQ(PQ)P(PQ)PQ0 00 11 01 11 1 010 0 011 1 111.5 等價與蘊涵等價與蘊涵 3/28/2022chapter1371、 異或（不可兼析?。┊惢颍ú豢杉嫖鋈。?P Q，讀作，讀作“P異或異或Q”或或P、Q的異或（排斥或）的異或（排斥或）1.6 其它聯(lián)結詞其它聯(lián)結詞0110PQQ11011000QP qpqpqpqpqpqp_ 3/28/2022chapter1381.6 其它聯(lián)結詞其它聯(lián)結詞qpqpqpq

28、pc2、 條件否定條件否定 ，讀作，讀作“P和和Q的條件否定的條件否定”QPcQPc0100P Q11011000QPc 3/28/2022chapter1391.6 其它聯(lián)結詞其它聯(lián)結詞qpqpqp3、 與非與非 P QP Q ，讀作，讀作“P與與Q的否定的否定”0111P Q11011000QP 3/28/2022chapter1401.6 其它聯(lián)結詞其它聯(lián)結詞qpqpqp4、 或非或非 P QP Q ，讀作，讀作“P或或Q的否定的否定”0001P Q11011000QP 3/28/2022chapter141 1、對偶、對偶定義定義1.7-1 在給定的命題公式中，將聯(lián)結詞在給定的命題公式

29、中，將聯(lián)結詞 換成換成，將，將 換成換成，若有特殊變元，若有特殊變元0和和1亦相互取代，所得公式亦相互取代，所得公式A*稱為稱為A的對偶式。的對偶式。顯然顯然A也是也是A*的對偶式。的對偶式。 【例【例14】寫出下列表達式的對偶式?！繉懗鱿铝斜磉_式的對偶式。（1） (PQ)R 的對偶式是的對偶式是(P Q) R （2） (PQ)T的對偶式是的對偶式是 (PQ)F （3）(PQ)(P (Q S)的對偶式是的對偶式是(PQ)(P (Q S)1.7 對偶與范式對偶與范式 3/28/2022chapter142 【例【例15】求】求PQ，PQ的對偶式。的對偶式。解：因為解：因為PQ (PQ) ，故，故

30、PQ 的對偶式為的對偶式為(PQ) ，即，即 PQ 。同理同理PQ的對偶式是的對偶式是PQ 。定理定理1.7-1設設A和和A*是對偶式，是對偶式，P1，P2，Pn是出現(xiàn)在是出現(xiàn)在A和和A*中的原子變元，則中的原子變元，則1.7 對偶與范式對偶與范式),.,(),.,(),.,(),.,(21212121nnnnPPPAPPPAPPPAPPPA定理定理1.7-2 設設P1，P2，Pn是出現(xiàn)在公式是出現(xiàn)在公式A和和B中的所有中的所有原子變元，如果原子變元，如果AB ，則，則A*B*。 3/28/2022chapter143 2、合取范式、合取范式定義定義1.7-2 一個命題公式稱為合取范式，當且僅

31、當它具有一個命題公式稱為合取范式，當且僅當它具有型式：型式： P1P2Pn，其中，其中P1，P2 ，Pn都是由命都是由命題變元或其否定所組成的析取式。題變元或其否定所組成的析取式。3、析取范式、析取范式定義定義1.7-3 一個命題公式稱為析取范式，當且僅當它具有一個命題公式稱為析取范式，當且僅當它具有型式：型式： P1P2Pn，其中，其中P1，P2 ，Pn都是由命都是由命題變元或其否定所組成的合取式。題變元或其否定所組成的合取式。1.7 對偶與范式對偶與范式 3/28/2022chapter144 定理定理1.7-3 任一命題公式都存在著與之等值的析取范式和任一命題公式都存在著與之等值的析取范

32、式和合取范式。合取范式。注：任何一個命題公式，可以通過下面三個步驟求它的注：任何一個命題公式，可以通過下面三個步驟求它的合取范式或析取范式：合取范式或析取范式：（1）將公式中的聯(lián)結詞化歸成）將公式中的聯(lián)結詞化歸成， 及及 。（2）利用德）利用德摩根律將否定摩根律將否定直接到各個命題變元之前直接到各個命題變元之前。（3）利用分配律、結合律將公式歸約為合取范式或析?。├梅峙渎?、結合律將公式歸約為合取范式或析取范式。范式。1.7 對偶與范式對偶與范式 3/28/2022chapter145 【例【例16】求】求(P(Q R)S的合取范式。的合取范式。解：解：1.7 對偶與范式對偶與范式)()()(

33、)()()()()(RSPQSPRQSPSRQPSRQPSRQPSRQP 【例【例17】求】求(PQ) (PQ)的的析取范式。析取范式。解：解：)()()()()()()()()()()()()()()(QPPQQQQPPQPPQPQPQPQPQPQPQPQPQPQP 3/28/2022chapter1464、主范式、主范式定義定義1.7-4 對于公式對于公式A，包含，包含A中所有命題變元或其否定一中所有命題變元或其否定一次且僅一次的簡單合取式稱為次且僅一次的簡單合取式稱為極小項極小項。注：小項有如下幾個性質：注：小項有如下幾個性質：1）每一個小項當其真值指派與編碼相同時，其真值為）每一個小項

34、當其真值指派與編碼相同時，其真值為T，在其余在其余2n-1種指派情況下均為種指派情況下均為F。2）任意兩個不同小項的合取式永假。）任意兩個不同小項的合取式永假。3）全體小項的析取式永為真，記為：）全體小項的析取式永為真，記為：1.7 對偶與范式對偶與范式Tmmmmnnii1210120. 3/28/2022chapter147定義定義1.7-5 對于給定的命題公式，如果有一個等價公式，對于給定的命題公式，如果有一個等價公式，它僅由小項的析取所組成，則該等價式稱作原式的它僅由小項的析取所組成，則該等價式稱作原式的主析主析取范式取范式。定理定理1.7-4 在真值表中，一個公式的真值為在真值表中，一

35、個公式的真值為T的指派所對的指派所對應的小項的析取，即為此公式的主析取范式。應的小項的析取，即為此公式的主析取范式。1.7 對偶與范式對偶與范式 3/28/2022chapter148【例【例18】給定】給定PQ，PQ和和(PQ) ，求這些公式的，求這些公式的主析取范式。主析取范式。1.7 對偶與范式對偶與范式PQPQ P Q (P Q) 00101011111001111110)()()()()()()()()()(QPQPQPQPQPQPQPQPQPQPQPQP 3/28/2022chapter149【例【例19】求】求 (PQ)(PR)(QR)的主析取范式。的主析取范式。1.7 對偶與范

36、式對偶與范式)()()()()()()()()()(QRPQRPRQPRQPPPRQQQRPRRQPRQRPQP 一個命題公式的主析取范式，可一個命題公式的主析取范式，可由公式的真值表得出由公式的真值表得出或或由基本等價公式推出由基本等價公式推出。其步驟可歸納為：。其步驟可歸納為：（1）化歸為析取范式。）化歸為析取范式。（2）除去析取范式中所有永假的析取項。）除去析取范式中所有永假的析取項。（3）將析取式中重復出現(xiàn)的合取項和相同的變元合并。）將析取式中重復出現(xiàn)的合取項和相同的變元合并。（4）對合取項補入沒有出現(xiàn)的命題變元，即添加）對合取項補入沒有出現(xiàn)的命題變元，即添加(PP) 式，然后，應用分

37、配律展開公式。式，然后，應用分配律展開公式。 3/28/2022chapter150定義定義1.7-6 對于公式對于公式A，包含，包含A中所有命題變元或其否定一中所有命題變元或其否定一次且僅一次的簡單析取式稱為極大項。次且僅一次的簡單析取式稱為極大項。注：大項有如下性質：注：大項有如下性質：1）每一個大項當其真值指派與編碼相同時，其真值為）每一個大項當其真值指派與編碼相同時，其真值為F，在其余在其余2n-1種指派情況下均為種指派情況下均為T。2）任意兩個不同大項的析取式為永真。）任意兩個不同大項的析取式為永真。MiMj T (ij)3）全體大項的合取式永為假，記為：）全體大項的合取式永為假，記

38、為：1.7 對偶與范式對偶與范式FMMMMnnii1210120. 3/28/2022chapter151定義定義1.7-7 對于給定的命題公式，如果有一個等價公式僅由對于給定的命題公式，如果有一個等價公式僅由大項的合取所組成，則該等價式稱作原式的大項的合取所組成，則該等價式稱作原式的主合取范式主合取范式。定理定理1.7-5 在真值表中，一個公式的真值為在真值表中，一個公式的真值為F的指派所對應的指派所對應的大項的合取，即為此公式的主合取范式。的大項的合取，即為此公式的主合取范式。注：公式的主合取范式，可用基本等價式推出，其步驟為：注：公式的主合取范式，可用基本等價式推出，其步驟為：（1）化歸

39、為合取范式。）化歸為合取范式。（2）除去合取范式中所有為永真的合取項。）除去合取范式中所有為永真的合取項。（3）合并相同的析取項和相同的變元。）合并相同的析取項和相同的變元。（4）對析取項補入沒有出現(xiàn)的命題變元，即添加）對析取項補入沒有出現(xiàn)的命題變元，即添加(P P) 式，然后，應用分配律展開公式。式，然后，應用分配律展開公式。1.7 對偶與范式對偶與范式 3/28/2022chapter152【例【例20】化】化 (PQ)(PR)為主合取范式。為主合取范式。1.7 對偶與范式對偶與范式)()()()()()()()()()()()()()()()()()()()()()()()(RQPRQP

40、RQPRQPPRQPRQQRPQRPRPQRPQPPRQQQRPRRPQRQRPPQRQRPPQPPRQPPQPRPQP 3/28/2022chapter153 1.8.1 推理推理推理推理已知已知H1、H2、Hm，證明，證明C的過程。的過程。寫成命題邏輯的形式為：寫成命題邏輯的形式為： H1 H2 HmC 其中，其中， H1、H2、Hm稱為推理的前提，稱為推理的前提，C為這一組前為這一組前提的有效結論。提的有效結論。推理的過程就是證明推理的過程就是證明H1H2HmC的過程。的過程。 1.8.2 推理方法推理方法 證明證明H1H2Hm C為永真式。為永真式。1、真值表法、真值表法2、等價推導法

41、、等價推導法1.8 推理理論推理理論 3/28/2022chapter154 【例【例21】證明】證明 (PQ)(QR)(PR)證明：證明： ( (PQ)(QR) )(PR) (PQ)(QR)(PR) (P Q)( Q R) (P R) (P Q) ( Q R) (P R) (PQ) (QR) (PR) (PQ)P)(QR)R) (QP)(QR) T 1.8 推理理論推理理論 3/28/2022chapter1553、幾種常用的推理的定律、幾種常用的推理的定律(1) 假言推理（肯定的肯定）假言推理（肯定的肯定）P(PQ)Q 通過肯定條件的前件從而肯定條件的后件。通過肯定條件的前件從而肯定條件的

42、后件。如：如： PQ：如果他喝酒，則他臉紅。：如果他喝酒，則他臉紅。 P：他喝酒。：他喝酒。 Q：他臉紅。：他臉紅。但是，但是， PQ：如果他喝酒，則他臉紅。：如果他喝酒，則他臉紅。 Q：他臉紅。：他臉紅。 P：他喝酒。：他喝酒。不成立不成立注意：不能通過肯定條件的后件而肯定條件的前件。注意：不能通過肯定條件的后件而肯定條件的前件。1.8 推理理論推理理論 3/28/2022chapter156 (2) 拒取式（否定的否定）拒取式（否定的否定）Q(PQ)P 通過否定條件的后件從而否定條件的前件。通過否定條件的后件從而否定條件的前件。如：如： PQ：小王評上三好學生，則小王成績好。：小王評上三好

43、學生，則小王成績好。 Q ：小王成績不好。：小王成績不好。 P ：小王沒評上三好學生。：小王沒評上三好學生。注意：不能通過否定條件的前件而肯定條件的后件。注意：不能通過否定條件的前件而肯定條件的后件。1.8 推理理論推理理論 3/28/2022chapter157(3) (3) 析取三段論析取三段論 (PQ)PQ 產(chǎn)生一個事件的原因有產(chǎn)生一個事件的原因有P和和Q，否定，否定P，則一定是，則一定是Q。如：如： PQ：成績不好是老師教得不好或自己不努力。：成績不好是老師教得不好或自己不努力。 P ：老師教得好。：老師教得好。 Q：自己不努力。：自己不努力。推廣：推廣： (PQRS)PQR S 1.

44、8 推理理論推理理論 3/28/2022chapter158 (4) 假言三段論假言三段論 (PQ)(QR)PR 如：如： PQ：如果不下雨，就開運動會。：如果不下雨，就開運動會。 QR：如果開運動會，就不上課。：如果開運動會，就不上課。 PR ：如果不下雨，就不上課。：如果不下雨，就不上課。1.8 推理理論推理理論 3/28/2022chapter1591.8 推理理論推理理論常用的蘊涵式常用的蘊涵式 ( (9 9) ) P P，P PQ QQ Q；( (1010) ) Q Q，P PQ QP P；( (1111) ) P P，P PQ QQ Q；( (1212) ) P PQ Q，Q QR

45、 RP PR R；( (1313) ) P PQ Q，P PR R，Q QR RR R；( (1414) ) P PQ Q，R RS S( (P PR R)()(Q QS S) )；( (1515) ) P P，Q QP PQ Q。( (1 1) ) P PQ QP P；(2(2) ) P PQ QQ Q；( (3 3) ) P PP PQ Q；( (4 4) ) Q QP PQ Q；( (5 5) ) P P( (P PQ Q) )；( (6 6) ) Q Q( (P PQ Q) )；( (7 7) ) ( (P PQ Q) )P P；( (8 8) ) ( (P PQ Q) )Q Q； 3/28/2022chapter160 4、證明方法（形式演繹）、證明方法（形式演繹）(1) P規(guī)則（前提引入規(guī)則）：規(guī)則（前提引入規(guī)則）：給定的前提在證明的過程給定的前提在證明的過程中隨時都可以加以引用。中隨時都可以加以引用。(2) 規(guī)則（結論引用規(guī)則）：規(guī)則（結論引用規(guī)則）：在證明過程中產(chǎn)生的結論在證明過程中產(chǎn)生的結論可以作為后續(xù)證