離散數(shù)學(xué)第一章命題邏輯.ppt

1、第一章 命題邏輯 Proposition Logic,1.1 命題及其表示法 1.2 聯(lián)結(jié)詞 1.3 命題公式與翻譯 1.4 重言式、矛盾式、可滿足公式 1.5 等價與蘊(yùn)含 1.6 推理理論,8/3/2020 6:04 AM,chapter1,2,1.1 命題及其表示法,1、命題 命題非真即假的陳述句。,斷言是一陳述語句。一個命題是一個或真或假而不能兩者都是的斷言。如果命題是真, 我們說它的真值為真；如果命題是假，我們說它的真值是假。,8/3/2020 6:04 AM,chapter1,3,【例1 】判定下列各語句是否為命題： (a) 巴黎在法國。 (b) 煤是白色的。 (c) 3+2=5 (

2、d) 別的星球上有生物。 (e) 全體立正。 (f) 明天是否開大會？ (g) 天氣多好啊！ (h) 我正在說謊。 (i) 如果天氣好，那么我去散步。 (j) x3,（是）,（是）,（是）,（是）,（否，祈使句）,（否，疑問句）,（否，感嘆句）,（否,悖論）,（是,復(fù)合命題）,（否，不能確定真值）,1.1 命題及其表示法,8/3/2020 6:04 AM,chapter1,4,2、命題的表示 命題變元常用P、Q、R、S等大寫字母或加下標(biāo)的大寫字母P1, Q2, R10, 表示來表示一個命題，稱為命題變元。 如： P:巴黎在法國。 Q:煤是白色的。,1.1 命題及其表示法,8/3/2020 6:

3、04 AM,chapter1,5,3、命題相關(guān)概念 簡單命題（原子命題）不能再分解的命題。 復(fù)合命題由若干個簡單命題復(fù)合而成的命題。 真值表把組成復(fù)合命題的各命題變元的真值的所有組合及其相對應(yīng)的復(fù)合命題的真值列成表，稱為真值表。,1.1 命題及其表示法,8/3/2020 6:04 AM,chapter1,6,【例2 】求公式(PQ)P的真值表。 解： 分以下步求得: (1) 寫出公式P的真值表; (2) 寫出公式PQ的真值表; (3) 根據(jù)(1)和(2), 寫出公式(PQ)P的真值表。 為清楚起見, 我們將這步列在一個表內(nèi), 見下表。,1.1 命題及其表示法,8/3/2020 6:04 AM,

4、chapter1,7,【例3 】求公式 (PR)(QR)的真值表。 解：公式含有個命題變元P、Q、R, 真值表有3=8行。其真值表如下表 所示：,1.1 命題及其表示法,8/3/2020 6:04 AM,chapter1,8,1.2 聯(lián)結(jié)詞,命題和原子命題常可通過一些聯(lián)結(jié)詞構(gòu)成新命題, 這種新命題叫復(fù)合命題（Compositional Proposition ）。例如： P: 明天下雪, Q: 明天下雨 是兩個命題, 利用聯(lián)結(jié)詞“不”, “并且”, “或”等可構(gòu)成新命題: “明天不下雪”； “明天下雪并且下雨”； “明天下雪或下雨”等 。,8/3/2020 6:04 AM,chapter1,9

5、,1.2 聯(lián)結(jié)詞,即 ： “非P”； “P并且Q”； “P或Q”等 。 在代數(shù)式x+3 中, x , 3 叫運(yùn)算對象, +叫運(yùn)算符, x+3 表示運(yùn)算結(jié)果。在命題演算中, 聯(lián)結(jié)詞就是命題演算中的運(yùn)算符, 叫邏輯運(yùn)算符或叫邏輯聯(lián)結(jié)詞。常用的有以下 5 個。,8/3/2020 6:04 AM,chapter1,10,1、否定 P是P的否定，讀作“非P”， “ P的否定” 。,如： P:成都是中國的首都。 P：成都不是中國的首都。 否定與漢語中的“非”、“不是”、“否定”是一致的。,1.2 聯(lián)結(jié)詞,8/3/2020 6:04 AM,chapter1,11,2、合取 PQ是P和Q的合取, 讀做“P與Q

6、”或“P并且Q”。,如： P: 王華的成績很好。 Q: 王華的品德很好。 PQ: 王華的成績很好并且品德很好。 合取與漢語中的“和”、“與”、“并且”是一致的。,1.2 聯(lián)結(jié)詞,8/3/2020 6:04 AM,chapter1,12,3、析取 PQ是P和Q的析取, 讀做“P或Q”。,如： P:小王喜歡唱歌。 Q:小王喜歡跳舞 。 P Q:小王喜歡唱歌或喜歡跳舞 。 從真值表可知PQ為真, 當(dāng)且僅當(dāng)P或Q至少有一為真。,1.2 聯(lián)結(jié)詞,8/3/2020 6:04 AM,chapter1,13,“或”字常見的含義有兩種: 一種是“可兼或”, 如上例中的或, 它不排除小王既喜歡唱歌又喜歡跳舞這種情

7、況。一種是“排斥或”（異或）, 例如“人固有一死, 或重于泰山, 或輕于鴻毛”中的“或”, 它表示非此即彼, 不可兼得。 運(yùn)算符表示可兼或, 排斥或以后用另一符號表達(dá)。 如：(1)小李明天出差去上?；蛉V州。 (2)劉昕這次考試可能是全班第一也可能是全班第二。 這兩例表示的均是排斥或，即兩種情況不能同時出現(xiàn)，這時便不能僅用析取詞表示。,1.2 聯(lián)結(jié)詞,8/3/2020 6:04 AM,chapter1,14,4、條件 PQ, 讀做 “如果P, 那么Q”或“P則Q” 。 運(yùn)算對象P叫做前提 , 假設(shè)或前件, 而Q叫做結(jié)論或后件。,1.2 聯(lián)結(jié)詞,如： P:雪是黑的。 Q:太陽從東方升起 。 P

8、Q:如果雪是黑的，則太陽從東方升起 。 命題PQ是假, 當(dāng)且僅當(dāng)P是真而Q是假。,8/3/2020 6:04 AM,chapter1,15,條件與漢語中“如果，就”相類似，但有所區(qū)別: (1)自然語言中，“如果P則Q”，往往P和Q有一定的因果關(guān)系，而條件復(fù)合命題PQ中 P和Q 可以完全不相關(guān)。 (2)自然語言中，“如果P則Q”，當(dāng)P為0、Q為1時，整個句子真值難以確定；而條件復(fù)合命題PQ中，當(dāng)P為0時，復(fù)合命題的真值為1。 P則Q的邏輯含義:P是Q的充分條件,Q是P的必要條件。 所以,“如果P則Q”, “只要P則Q”,只有Q才P”, “僅當(dāng)Q則P”都可符號化為PQ 的形式。,1.2 聯(lián)結(jié)詞,8

9、/3/2020 6:04 AM,chapter1,16,如：小李對小王說：“如果天不下雨，我就來找你”。 天沒下雨，小李去找了小王。 天沒下雨，小李沒去找小王。 天下雨了，小李去找了小王。 天下雨了，小李沒去找小王。,1.2 聯(lián)結(jié)詞,【例4 】電燈不亮是電燈壞或電路有毛病。 解：設(shè)P電燈不亮，Q電燈壞，R電路有毛病。 上述語句應(yīng)表示為: (Q R) P,8/3/2020 6:04 AM,chapter1,17,5、雙條件 P Q, 讀做 “P當(dāng)且僅當(dāng)Q” 。,如： P:兩個三角形全等。 Q:兩個三角形的對應(yīng)邊相等 。 P Q:兩個三角形全等當(dāng)且僅當(dāng)其對應(yīng)邊相等 。 P當(dāng)且僅當(dāng)Q的邏輯含義:P和

10、Q互為充要條件 。,1.2 聯(lián)結(jié)詞,8/3/2020 6:04 AM,chapter1,18,6、聯(lián)結(jié)詞的優(yōu)先次序 聯(lián)結(jié)詞的優(yōu)先級： , , , , ，括號優(yōu)先。 如： (PQ)R 可寫成 ：PQR (PQ)R 可寫成：PQR (P Q)R)(RP)Q) 可寫成： (P QR)RPQ 為方便起見，公式最外層的括號可省略。有時為了看起來清楚醒目, 也可保留某些原可省去的括號。,1.2 聯(lián)結(jié)詞,8/3/2020 6:04 AM,chapter1,19,單個命題變元和命題常元叫原子公式。由以下形成規(guī)則生成的公式叫命題公式 (簡稱公式): (1) 單個原子公式A、B是命題公式。 (2) 如果A和B是命

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

12、（是）,1.3 命題公式,8/3/2020 6:04 AM,chapter1,21,【例6】 將下列自然語言形式化: (a) 如果天不下雨并且不刮風(fēng)，我就去書店。 解 ：設(shè)P：今天天下雨，Q：今天天刮風(fēng)，R：我去書店。 則原命題符號化為： (PQ)R (b) 小王邊走邊唱。 解：設(shè)p：小王走路，q：小王唱歌。 則原命題符號化為： pq (c) 除非a能被2整除，否則a不能被4整除。 解：設(shè)p：a能被2整除，q：a能被4整除。 則原命題符號化為： p q 或 q p,1.3 命題公式,8/3/2020 6:04 AM,chapter1,22,(d) 此時，小剛要么在學(xué)習(xí)，要么在玩游戲。 解：設(shè)p

13、：小剛在學(xué)習(xí)，q：小剛在玩游戲。 則原命題符號化為： (pq)(pq) 或 (pq)(pq) (e) 如果天不下雨，我們?nèi)ゴ蚧@球，除非班上有會。 解：設(shè)p：今天天下雨，q：我們?nèi)ゴ蚧@球，r：今天班上有會。 則原命題符號化為： r (p q),1.3 命題公式,8/3/2020 6:04 AM,chapter1,23,1、 重言式（Tautology） 重言式(永真式)真值恒為1的公式。如：PP 【例7】判斷（P P(P Q)）是否為重言式。,（P P(P Q)）為重言式。,1.4 重言式、矛盾式、可滿足公式,8/3/2020 6:04 AM,chapter1,24,2、 矛盾式（Contrad

14、iction) 矛盾式（永假式）真值恒為0的公式。如：P P 【例8】判斷(PQ)P是否為矛盾式。,（ (PQ)P ）為矛盾式。,1.4 重言式、矛盾式、可滿足公式,8/3/2020 6:04 AM,chapter1,25,3、 可滿足公式（Satisfaction） 可滿足公式至少有一種真值為1的情況。 (除矛盾式之外的公式) ，永真式也是可滿足公式。,定理：由n個命題變元一共可組成 個不同的命題。其中永真式有一個，矛盾式有一個，可滿足公式有 個。,1.4 重言式、矛盾式、可滿足公式,8/3/2020 6:04 AM,chapter1,26,【例9】 構(gòu)造公式PQ、(PQ)、PQ、Q P的真

15、值 。 解：真值表如下：,由例題可見，公式PQ、(PQ)、PQ、Q P的真值表是完全相同的，我們稱其為等值的。那么如何判斷兩個公式等值呢？,1.5 等價與蘊(yùn)涵,8/3/2020 6:04 AM,chapter1,27,1.5.1 等價 1、 等價的定義 等價設(shè)A、B是兩個命題公式，當(dāng)A與B有完全相同的真值，則稱A和B等價，即為AB。 定理：設(shè)A、B是兩個命題公式， AB 的充要條件是AB為永真式。 等價置換：假設(shè)X是公式A的子公式，如果XY，則將X置換為Y所得的公式與A等價。,1.5 等價與蘊(yùn)涵,8/3/2020 6:04 AM,chapter1,28,2、 等價與雙條件的區(qū)別 等價：不是一個

16、聯(lián)結(jié)詞，AB不是一個命題公式，表示的是A、B之間的邏輯關(guān)系。 雙條件：是一個聯(lián)結(jié)詞， AB是命題公式。,1.5 等價與蘊(yùn)涵,8/3/2020 6:04 AM,chapter1,29,3、常用的等值式 (1)雙重否定律 A A (2)冪等律 A AA A AA (3)交換律 AB BA AB BA (4)結(jié)合律 (AB)C A(BC) (AB)C A(BC) (5)分配律 A(BC) (AB)(AC) A(BC) (AB)(AC) (6)德摩根律 (AB) AB (AB) AB,1.5 等價與蘊(yùn)涵,8/3/2020 6:04 AM,chapter1,30,(7)吸收律 A(AB) A A(AB)

17、 A (8)零律 A1 1 A0 0 (9)同一律 A0 A A1 A (10)否定律 AA 1 AA 0 (11)蘊(yùn)涵等值式 AB AB (12)等價等值式 AB (AB)(BA) (13)逆反律 AB BA (14)輸出律 A(BC) (AB)C (15)歸謬論 (AB)(AB) A,1.5 等價與蘊(yùn)涵,8/3/2020 6:04 AM,chapter1,31,思考： 證明兩個公式等價的方法： 1、構(gòu)造真值表。 2 、等價推導(dǎo)法。（若一個公式變元太多，由于n個變元組成的真值表有2n行，所以用等價推導(dǎo)的方法來證明。）,1.5 等價與蘊(yùn)涵,8/3/2020 6:04 AM,chapter1,3

18、2,【例11】用等值演算證明p(qr) (pq)r。 證明： p(qr) p(qr) （蘊(yùn)涵等值式） p(qr) （蘊(yùn)涵等值式） (pq) r （結(jié)合律） (pq) r （德摩根律） (pq)r （蘊(yùn)涵等值式）,1.5 等價與蘊(yùn)涵,8/3/2020 6:04 AM,chapter1,33,【例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 等價與蘊(yùn)涵,8/3/2020 6:04 AM,chapter1,34,1.5.2 蘊(yùn)含 1、蘊(yùn)涵的定義 蘊(yùn)含設(shè)

19、A、B是兩個命題公式，若A為真，B必定為真，則稱A蘊(yùn)含B，記作AB。 定理：設(shè)A、B是兩個命題公式， AB 的充要條件是AB為永真式。,1.5 等價與蘊(yùn)涵,8/3/2020 6:04 AM,chapter1,35,2、蘊(yùn)含與條件的區(qū)別 蘊(yùn)含：不是一個聯(lián)結(jié)詞，AB不是一個命題公式，表示的是A、B之間的邏輯關(guān)系。 條件：是一個聯(lián)結(jié)詞， AB是命題公式。,1.5 等價與蘊(yùn)涵,8/3/2020 6:04 AM,chapter1,36,【例13】 證明 (PQ)PQ 。 證明：真值表如下：,由真值表可見， (PQ)P為1時，Q為真。 (PQ)PQ,1.5 等價與蘊(yùn)涵,8/3/2020 6:04 AM,c

20、hapter1,37,1.6.1 推理 推理已知H1、H2、Hm，證明C的過程。 寫成命題邏輯的形式為： H1 H2 HmC 其中， H1、H2、Hm稱為推理的前提，C為這一組前提的有效結(jié)論。 推理的過程就是證明H1H2HmC的過程。 1.6.2 推理方法 證明H1H2Hm C為永真式。 1、真值表法 2、等價推導(dǎo)法,1.6 推理理論,8/3/2020 6:04 AM,chapter1,38,【例14】證明 (PQ)(QR)(PR) 證明： ( (PQ)(QR) )(PR) (PQ)(QR)(PR) (P Q)( Q R) (P R) (P Q) ( Q R) (P R) (PQ) (QR)

21、(PR) (PQ)P)(QR)R) (QP)(QR) T,1.6 推理理論,8/3/2020 6:04 AM,chapter1,39,3、幾種常用的推理的定律 (1) 假言推理（肯定的肯定） P(PQ)Q 通過肯定條件的前件從而肯定條件的后件。 如： PQ：如果他喝酒，則他臉紅。 P：他喝酒。,Q：他臉紅。,注意：不能通過肯定條件的后件而肯定條件的前件。,1.6 推理理論,8/3/2020 6:04 AM,chapter1,40,(2) 拒取式（否定的否定） Q(PQ)P 通過否定條件的后件從而否定條件的前件。 如： PQ：小王評上三好學(xué)生，則小王成績好。 Q ：小王成績不好。,P ：小王沒評

22、上三好學(xué)生。 注意：不能通過否定條件的前件而肯定條件的后件。,1.6 推理理論,8/3/2020 6:04 AM,chapter1,41,(3) 析取三段論 (PQ)PQ 產(chǎn)生一個事件的原因有P和Q，否定P，則一定是Q。 如： PQ：成績不好是老師教得不好或自己不努力。 P ：老師教得好。,Q：自己不努力。 推廣： (PQRS)PQR S,1.6 推理理論,8/3/2020 6:04 AM,chapter1,42,(4) 假言三段論 (PQ)(QR)PR 如： PQ：如果不下雨，就開運(yùn)動會。 QR：如果開運(yùn)動會，就不上課。,PR ：如果不下雨，就不上課。,1.6 推理理論,8/3/2020 6

23、:04 AM,chapter1,43,1.6 推理理論,常用的蘊(yùn)涵式,8/3/2020 6:04 AM,chapter1,44,4、證明方法（形式演繹） (1) P規(guī)則（前提引入規(guī)則）：給定的前提在證明的過程中隨時都可以加以引用。 (2) 規(guī)則（結(jié)論引用規(guī)則）：在證明過程中產(chǎn)生的結(jié)論可以作為后續(xù)證明的前提加以引用。 (3) CP規(guī)則（附加前提引入規(guī)則）： 如果證明的形式為H1 H2 Hm AB，等價于證明H1H2HmAB。A稱為附加前提。,1.6 推理理論,8/3/2020 6:04 AM,chapter1,45,證明：證明H1 H2 HmAB等價于證明(H1 H2 Hm) (AB)為永真式。 (H1 H2 Hm) (AB) (H1 H2 Hm) (AB) (H1 H2 HmA) B (H1 H2 HmA)B 證明H1 H2 Hm AB等價于證明 H1H2HmAB。,1.6 推理理論,8/3/2020 6:04 AM,chapter1,46,【例15】證明 (PQ)(PR)(QS)(RS) 證明： PQ P PQ T QS P PS T SP T PR P SR T RS T ,1.6 推理理論,8/3/2020 6:0