《離散數(shù)學(xué)第一章命題邏輯.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)第一章命題邏輯.ppt（51頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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

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

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

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

5、20 12:53 AM,chapter1,9,1.2 聯(lián)結(jié)詞,即 ： “非P”； “P并且Q”； “P或Q”等 。 在代數(shù)式x+3 中, x , 3 叫運(yùn)算對(duì)象, +叫運(yùn)算符, x+3 表示運(yùn)算結(jié)果。在命題演算中, 聯(lián)結(jié)詞就是命題演算中的運(yùn)算符, 叫邏輯運(yùn)算符或叫邏輯聯(lián)結(jié)詞。常用的有以下 5 個(gè)。,7/9/2020 12:53 AM,chapter1,10,1、否定 P是P的否定，讀作“非P”， “ P的否定” 。,如： P:成都是中國(guó)的首都。 P：成都不是中國(guó)的首都。 否定與漢語中的“非”、“不是”、“否定”是一致的。,1.2 聯(lián)結(jié)詞,7/9/2020 12:53 AM,cha

6、pter1,11,2、合取 PQ是P和Q的合取, 讀做“P與Q”或“P并且Q”。,如： P: 王華的成績(jī)很好。 Q: 王華的品德很好。 PQ: 王華的成績(jī)很好并且品德很好。 合取與漢語中的“和”、“與”、“并且”是一致的。,1.2 聯(lián)結(jié)詞,7/9/2020 12:53 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é)詞,7/9/2020 12:53 AM,chapter1,13,“或”字常見的含

7、義有兩種: 一種是“可兼或”, 如上例中的或, 它不排除小王既喜歡唱歌又喜歡跳舞這種情況。一種是“排斥或”（異或）, 例如“人固有一死, 或重于泰山, 或輕于鴻毛”中的“或”, 它表示非此即彼, 不可兼得。 運(yùn)算符表示可兼或, 排斥或以后用另一符號(hào)表達(dá)。 如：(1)小李明天出差去上?；蛉V州。 (2)劉昕這次考試可能是全班第一也可能是全班第二。 這兩例表示的均是排斥或，即兩種情況不能同時(shí)出現(xiàn)，這時(shí)便不能僅用析取詞表示。,1.2 聯(lián)結(jié)詞,7/9/2020 12:53 AM,chapter1,14,4、條件 PQ, 讀做 “如果P, 那么Q”或“P則Q” 。 運(yùn)算對(duì)象P叫做前提 , 假設(shè)

8、或前件, 而Q叫做結(jié)論或后件。,1.2 聯(lián)結(jié)詞,如： P:雪是黑的。 Q:太陽從東方升起 。 P Q:如果雪是黑的，則太陽從東方升起 。 命題PQ是假, 當(dāng)且僅當(dāng)P是真而Q是假。,7/9/2020 12:53 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時(shí)，整個(gè)句子真值難以確定；而條件復(fù)合命題PQ中，當(dāng)P為0時(shí)，復(fù)合命題的真值為1。 P則Q的邏輯含義:P是Q的充分條件,Q是P的必要條件。 所以,

9、“如果P則Q”, “只要P則Q”,只有Q才P”, “僅當(dāng)Q則P”都可符號(hào)化為PQ 的形式。,1.2 聯(lián)結(jié)詞,7/9/2020 12:53 AM,chapter1,16,如：小李對(duì)小王說：“如果天不下雨，我就來找你”。 天沒下雨，小李去找了小王。 天沒下雨，小李沒去找小王。 天下雨了，小李去找了小王。 天下雨了，小李沒去找小王。,,,,,1.2 聯(lián)結(jié)詞,【例4 】電燈不亮是電燈壞或電路有毛病。 解：設(shè)P電燈不亮，Q電燈壞，R電路有毛病。 上述語句應(yīng)表示為: (Q R) P,7/9/2020 12:53 AM,chapter1,17,5、雙條件 P Q, 讀做 “P當(dāng)且僅當(dāng)Q” 。,如：

10、 P:兩個(gè)三角形全等。 Q:兩個(gè)三角形的對(duì)應(yīng)邊相等 。 P Q:兩個(gè)三角形全等當(dāng)且僅當(dāng)其對(duì)應(yīng)邊相等 。 P當(dāng)且僅當(dāng)Q的邏輯含義:P和Q互為充要條件 。,1.2 聯(lián)結(jié)詞,7/9/2020 12:53 AM,chapter1,18,,6、聯(lián)結(jié)詞的優(yōu)先次序 聯(lián)結(jié)詞的優(yōu)先級(jí)： , , , , ，括號(hào)優(yōu)先。 如： (PQ)R 可寫成 ：PQR (PQ)R 可寫成：PQR (((P Q)R)((RP)Q)) 可寫成： (P QR)RPQ 為方便起見，公式最外層的括號(hào)可省略。有時(shí)為了看起來清楚醒目, 也可保留某些原可省去的括號(hào)。,1.2 聯(lián)結(jié)詞,7/9/2020 12:5

11、3 AM,chapter1,19,,單個(gè)命題變?cè)兔}常元叫原子公式。由以下形成規(guī)則生成的公式叫命題公式 (簡(jiǎn)稱公式): (1) 單個(gè)原子公式A、B是命題公式。 (2) 如果A和B是命題公式, 則(A) , (AB) , (AB) , (AB) , (AB)是命題公式。 (3) 只有有限步使用(1)和(2)所組成的包含命題變?cè)?、?lián)結(jié)詞以及成對(duì)的括號(hào)組成的符號(hào)串才是命題公式。 這種定義叫歸納定義, 也叫遞歸定義。由這種定義產(chǎn)生的公式也叫合式公式（Well-Formed Formulas），簡(jiǎn)寫為wff。,1.3 命題公式,7/9/2020 12:53 AM,chapter1,20,【

12、例5】 判斷下列表達(dá)式是否為合式公式: p(pq) ((pq)r) (p(qr)) (((pq)(qr)) ((pq)r) ((pq)r) s) ((pq)r) s,（是）,（是）,（否）,（否）,（否）,（是）,（是）,1.3 命題公式,7/9/2020 12:53 AM,chapter1,21,,【例6】 將下列自然語言形式化: (a) 如果天不下雨并且不刮風(fēng)，我就去書店。 解 ：設(shè)P：今天天下雨，Q：今天天刮風(fēng)，R：我去書店。 則原命題符號(hào)化為： (PQ)R (b) 小王邊走邊唱。 解：設(shè)p：小王走路，q：小王唱歌。 則原命題符號(hào)化為： pq (c) 除非a能被2整

13、除，否則a不能被4整除。 解：設(shè)p：a能被2整除，q：a能被4整除。 則原命題符號(hào)化為： p q 或 q p,1.3 命題公式,7/9/2020 12:53 AM,chapter1,22,,(d) 此時(shí)，小剛要么在學(xué)習(xí)，要么在玩游戲。 解：設(shè)p：小剛在學(xué)習(xí)，q：小剛在玩游戲。 則原命題符號(hào)化為： (pq)(pq) 或 (pq)(pq) (e) 如果天不下雨，我們?nèi)ゴ蚧@球，除非班上有會(huì)。 解：設(shè)p：今天天下雨，q：我們?nèi)ゴ蚧@球，r：今天班上有會(huì)。 則原命題符號(hào)化為： r (p q),1.3 命題公式,7/9/2020 12:53 AM,chapter1,23,,

14、1、 重言式（Tautology） 重言式(永真式)真值恒為1的公式。如：PP 【例7】判斷（P P(P Q)）是否為重言式。,（P P(P Q)）為重言式。,1.4 重言式、矛盾式、可滿足公式,7/9/2020 12:53 AM,chapter1,24,,2、 矛盾式（Contradiction) 矛盾式（永假式）真值恒為0的公式。如：P P 【例8】判斷(PQ)P是否為矛盾式。,（ (PQ)P ）為矛盾式。,1.4 重言式、矛盾式、可滿足公式,7/9/2020 12:53 AM,chapter1,25,3、 可滿足公式（Satisfaction） 可滿足公式至少有一種真值為1的情況。 (除

15、矛盾式之外的公式) ，永真式也是可滿足公式。,定理：由n個(gè)命題變?cè)还部山M成 個(gè)不同的命題。其中永真式有一個(gè)，矛盾式有一個(gè)，可滿足公式有 個(gè)。,1.4 重言式、矛盾式、可滿足公式,7/9/2020 12:53 AM,chapter1,26,,【例9】 構(gòu)造公式PQ、(PQ)、PQ、Q P的真值 。 解：真值表如下：,由例題可見，公式PQ、(PQ)、PQ、Q P的真值表是完全相同的，我們稱其為等值的。那么如何判斷兩個(gè)公式等值呢？,1.5 等價(jià)與蘊(yùn)涵,7/9/2020 12:53 AM,chapter1,27,1.5.1 等價(jià) 1、 等價(jià)的定義 等價(jià)設(shè)A、B是兩個(gè)命題公式，當(dāng)A與B有完全相同

16、的真值，則稱A和B等價(jià)，即為AB。 定理：設(shè)A、B是兩個(gè)命題公式， AB 的充要條件是AB為永真式。 等價(jià)置換：假設(shè)X是公式A的子公式，如果XY，則將X置換為Y所得的公式與A等價(jià)。,1.5 等價(jià)與蘊(yùn)涵,7/9/2020 12:53 AM,chapter1,28,2、 等價(jià)與雙條件的區(qū)別 等價(jià)：不是一個(gè)聯(lián)結(jié)詞，AB不是一個(gè)命題公式，表示的是A、B之間的邏輯關(guān)系。 雙條件：是一個(gè)聯(lián)結(jié)詞， AB是命題公式。,1.5 等價(jià)與蘊(yùn)涵,7/9/2020 12:53 AM,chapter1,29,,3、常用的等值式 (1)雙重否定律 A A (2)冪等律 A AA A AA (3)交換律 AB BA

17、 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 等價(jià)與蘊(yùn)涵,7/9/2020 12:53 AM,chapter1,30,,(7)吸收律 A(AB) A A(AB) A (8)零律 A1 1 A0 0 (9)同一律 A0 A A1 A (10)否定律 AA 1 AA 0 (11)蘊(yùn)涵等值式 AB AB (1

18、2)等價(jià)等值式 AB (AB)(BA) (13)逆反律 AB BA (14)輸出律 A(BC) (AB)C (15)歸謬論 (AB)(AB) A,1.5 等價(jià)與蘊(yùn)涵,7/9/2020 12:53 AM,chapter1,31,,思考： 證明兩個(gè)公式等價(jià)的方法： 1、構(gòu)造真值表。 2 、等價(jià)推導(dǎo)法。（若一個(gè)公式變?cè)?，由于n個(gè)變?cè)M成的真值表有2n行，所以用等價(jià)推導(dǎo)的方法來證明。）,1.5 等價(jià)與蘊(yùn)涵,7/9/2020 12:53 AM,chapter1,32,,【例11】用等值演算證明p(qr) (pq)r。 證明： p(qr) p(qr) （蘊(yùn)涵等值式） p(qr)

19、 （蘊(yùn)涵等值式） (pq) r （結(jié)合律） (pq) r （德摩根律） (pq)r （蘊(yùn)涵等值式）,1.5 等價(jià)與蘊(yùn)涵,7/9/2020 12:53 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 等價(jià)與蘊(yùn)涵,7/9/2020 12:53 AM,chapter1,34,,1.5.2 蘊(yùn)含 1、蘊(yùn)涵的定義 蘊(yùn)含設(shè)A、B是兩個(gè)命題公式

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

21、r1,37,,1.6.1 推理 推理已知H1、H2、Hm，證明C的過程。 寫成命題邏輯的形式為： H1 H2 HmC 其中， H1、H2、Hm稱為推理的前提，C為這一組前提的有效結(jié)論。 推理的過程就是證明H1H2HmC的過程。 1.6.2 推理方法 證明H1H2Hm C為永真式。 1、真值表法 2、等價(jià)推導(dǎo)法,1.6 推理理論,7/9/2020 12:53 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)

22、 (PQ) (QR) (PR) ((PQ)P)((QR)R) (QP)(QR) T,1.6 推理理論,7/9/2020 12:53 AM,chapter1,39,3、幾種常用的推理的定律 (1) 假言推理（肯定的肯定） P(PQ)Q 通過肯定條件的前件從而肯定條件的后件。 如： PQ：如果他喝酒，則他臉紅。 P：他喝酒。,Q：他臉紅。,,注意：不能通過肯定條件的后件而肯定條件的前件。,1.6 推理理論,7/9/2020 12:53 AM,chapter1,40,,(2) 拒取式（否定的否定） Q(PQ)P 通過否定條件的后件從而否定條件的前件。 如： PQ：小

23、王評(píng)上三好學(xué)生，則小王成績(jī)好。 Q ：小王成績(jī)不好。,P ：小王沒評(píng)上三好學(xué)生。 注意：不能通過否定條件的前件而肯定條件的后件。,,1.6 推理理論,7/9/2020 12:53 AM,chapter1,41,(3) 析取三段論 (PQ)PQ 產(chǎn)生一個(gè)事件的原因有P和Q，否定P，則一定是Q。 如： PQ：成績(jī)不好是老師教得不好或自己不努力。 P ：老師教得好。,Q：自己不努力。 推廣： (PQRS)PQR S,,1.6 推理理論,7/9/2020 12:53 AM,chapter1,42,,(4) 假言三段論 (PQ)(QR)PR 如： PQ：如果不下雨，就開運(yùn)動(dòng)會(huì)。

24、QR：如果開運(yùn)動(dòng)會(huì)，就不上課。,PR ：如果不下雨，就不上課。,,1.6 推理理論,7/9/2020 12:53 AM,chapter1,43,1.6 推理理論,常用的蘊(yùn)涵式,7/9/2020 12:53 AM,chapter1,44,,4、證明方法（形式演繹） (1) P規(guī)則（前提引入規(guī)則）：給定的前提在證明的過程中隨時(shí)都可以加以引用。 (2) 規(guī)則（結(jié)論引用規(guī)則）：在證明過程中產(chǎn)生的結(jié)論可以作為后續(xù)證明的前提加以引用。 (3) CP規(guī)則（附加前提引入規(guī)則）： 如果證明的形式為H1 H2 Hm AB，等價(jià)于證明H1H2HmAB。A稱為附加前提。,1.6 推理理論,7/9/2020 12:5

25、3 AM,chapter1,45,,證明：證明H1 H2 HmAB等價(jià)于證明(H1 H2 Hm) (AB)為永真式。 (H1 H2 Hm) (AB) (H1 H2 Hm) (AB) (H1 H2 HmA) B (H1 H2 HmA)B 證明H1 H2 Hm AB等價(jià)于證明 H1H2HmAB。,1.6 推理理論,7/9/2020 12:53 AM,chapter1,46,,【例15】證明 (PQ)(PR)(QS)(RS) 證明： PQ P PQ T QS P PS T SP T PR P S

26、R T RS T ,1.6 推理理論,7/9/2020 12:53 AM,chapter1,47,,【例16】證明 P(QS)，RP，Q(RS) 證明： RP P RP T R CP P T P(QS) P QS T Q P S T ,1.6 推理理論,7/9/2020 12:53 AM,chapter1,48,,【例17】 證明下面諸命題推得的結(jié)論是有效的: 如果今天是星期三, 那么我有一次離散數(shù)學(xué)或數(shù)據(jù)結(jié)構(gòu)測(cè)驗(yàn); 如果離散

27、數(shù)學(xué)課老師有事, 那么沒有離散數(shù)學(xué)測(cè)驗(yàn); 今天是星期三且離散數(shù)學(xué)老師有事, 所以, 我有一次數(shù)據(jù)結(jié)構(gòu)測(cè)驗(yàn)。 證明：先將各命題形式化。 設(shè) A: 今天是星期三。 B: 我有一次離散數(shù)學(xué)測(cè)驗(yàn)。 C: 我有一次數(shù)據(jù)結(jié)構(gòu)測(cè)驗(yàn)。 D: 離散數(shù)學(xué)課老師有事。 則本題要求證: ABC, DB, ADC。,1.6 推理理論,7/9/2020 12:53 AM,chapter1,49,,ABC, DB, ADC AD P A T ABC P BC T D T DB P B

28、 T C T ,1.6 推理理論,7/9/2020 12:53 AM,chapter1,50,,【例17】 公安人員審一件盜竊案。 已知： (1) 甲或乙盜竊了電腦。 (2) 若甲盜竊了電腦， 則作案時(shí)間不能發(fā)生在午夜前。 (3) 若乙證詞正確， 則在午夜時(shí)屋里燈光未滅。 (4) 若乙證詞不正確， 則作案時(shí)間發(fā)生在午夜前。 (5) 午夜時(shí)屋里燈光滅了。 問： 誰是盜竊犯？ 解: 設(shè)P：甲盜竊了電腦， Q：乙盜竊了電腦， R：作案時(shí)間發(fā)生在午夜前， S：乙證詞正確， T：午夜時(shí)屋里燈光滅了。 前提： PQ，PR，ST，SR，T,1.6 推理理論,7/9/2020 12:53 AM,chapter1,51,,前提： PQ，PR，ST，SR，T 推理： T P ST P S T SR P R T PR P P T Q T 因此可得結(jié)論： 乙是盜竊犯。,1.6 推理理論,