離散數(shù)學(xué)命題邏輯PPT課件

1、11/4/2021 2:51 PM1【例1 】判定下列各語(yǔ)句是否為命題：(a) 巴黎在法國(guó)。(b) 煤是白色的。(c) 3+2=5(d) 別的星球上有生物。(e) 全體立正。(f) 明天是否開(kāi)大會(huì)？(g) 天氣多好啊！(h) 我正在說(shuō)謊。(i) 如果天氣好，那么我去散步。(j) x3（是）（是）（是）（是）（否，祈使句）（否，疑問(wèn)句）（否，感嘆句）（否,悖論）（是,復(fù)合命題）（否，不能確定真值） 1.1 命題及其表示法第1頁(yè)/共53頁(yè)11/4/2021 2:51 PM22、命題的表示命題變?cè)Ｓ肞、Q、R、S等大寫(xiě)字母或加下標(biāo)的大寫(xiě)字母P1, Q2, R10, 表示來(lái)表示一個(gè)命題，稱為命題變?cè)?/p>

2、。如： P:巴黎在法國(guó)。 Q:煤是白色的。 1.1 命題及其表示法第2頁(yè)/共53頁(yè)11/4/2021 2:51 PM33、命題相關(guān)概念簡(jiǎn)單命題（原子命題）不能再分解的命題。復(fù)合命題由若干個(gè)簡(jiǎn)單命題復(fù)合而成的命題。真值表把組成復(fù)合命題的各命題變?cè)恼嬷档乃薪M合及其相對(duì)應(yīng)的復(fù)合命題的真值列成表，稱為真值表。1.1 命題及其表示法第3頁(yè)/共53頁(yè)11/4/2021 2:51 PM4【例2 】求公式(PQ)P的真值表。 解： 分以下步求得: (1) 寫(xiě)出公式P的真值表;(2) 寫(xiě)出公式PQ的真值表; (3) 根據(jù)(1)和(2), 寫(xiě)出公式(PQ)P的真值表。 為清楚起見(jiàn), 我們將這步列在一個(gè)表內(nèi),

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

4、6頁(yè)/共53頁(yè)11/4/2021 2:51 PM71.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頁(yè)/共53頁(yè)11/4/2021 2:51 PM81、否定 P是P的否定，讀作“非P”， “ P的否定” 。0110pp如： P:成都是中國(guó)的首都。 P：成都不是中國(guó)的首都。 否定與漢語(yǔ)中的“非”、“不是”、“否定”是一致的。1.2 聯(lián)結(jié)詞第8頁(yè)/共53頁(yè)11/4/2021 2:51 PM92、合

5、取 PQ是P和Q的合取, 讀做“P與Q”或“P并且Q”。如： P: 王華的成績(jī)很好。 Q: 王華的品德很好。 PQ: 王華的成績(jī)很好并且品德很好。合取與漢語(yǔ)中的“和”、“與”、“并且”是一致的。P QP Q0 00 11 01 100011.2 聯(lián)結(jié)詞第9頁(yè)/共53頁(yè)11/4/2021 2:51 PM103、析取 PQ是P和Q的析取, 讀做“P或Q”。如： P:小王喜歡唱歌。 Q:小王喜歡跳舞 。 P Q:小王喜歡唱歌或喜歡跳舞 。從真值表可知PQ為真, 當(dāng)且僅當(dāng)P或Q至少有一為真。P QP Q0 00 11 01 101111.2 聯(lián)結(jié)詞第10頁(yè)/共53頁(yè)11/4/2021 2:51 PM1

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

7、或前件, 而Q叫做結(jié)論或后件。P QP Q0 00 11 01 111011.2 聯(lián)結(jié)詞如： P:雪是黑的。 Q:太陽(yáng)從東方升起 。 P Q:如果雪是黑的，則太陽(yáng)從東方升起 。命題PQ是假, 當(dāng)且僅當(dāng)P是真而Q是假。第12頁(yè)/共53頁(yè)11/4/2021 2:51 PM13 條件與漢語(yǔ)中“如果，就”相類(lèi)似，但有所區(qū)別:(1)自然語(yǔ)言中，“如果P則Q”，往往P和Q有一定的因果關(guān)系，而條件復(fù)合命題PQ中 P和Q 可以完全不相關(guān)。(2)自然語(yǔ)言中，“如果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

8、的必要條件。 所以,“如果P則Q”, “只要P則Q”,只有Q才P”, “僅當(dāng)Q則P”都可符號(hào)化為PQ 的形式。1.2 聯(lián)結(jié)詞第13頁(yè)/共53頁(yè)11/4/2021 2:51 PM14如：小李對(duì)小王說(shuō)：“如果天不下雨，我就來(lái)找你”。 天沒(méi)下雨，小李去找了小王。 天沒(méi)下雨，小李沒(méi)去找小王。 天下雨了，小李去找了小王。 天下雨了，小李沒(méi)去找小王。1.2 聯(lián)結(jié)詞【例4 】電燈不亮是電燈壞或電路有毛病。解：設(shè)P電燈不亮，Q電燈壞，R電路有毛病。上述語(yǔ)句應(yīng)表示為: (Q R) P第14頁(yè)/共53頁(yè)11/4/2021 2:51 PM155、雙條件 P Q, 讀做 “P當(dāng)且僅當(dāng)Q” 。如： P:兩個(gè)三角形全等。

9、 Q:兩個(gè)三角形的對(duì)應(yīng)邊相等 。 P Q:兩個(gè)三角形全等當(dāng)且僅當(dāng)其對(duì)應(yīng)邊相等 。P當(dāng)且僅當(dāng)Q的邏輯含義:P和Q互為充要條件 。P QP Q0 00 11 01 110011.2 聯(lián)結(jié)詞第15頁(yè)/共53頁(yè)11/4/2021 2:51 PM16 6、聯(lián)結(jié)詞的優(yōu)先次序聯(lián)結(jié)詞的優(yōu)先級(jí)： , , , , ，括號(hào)優(yōu)先。如： (PQ)R 可寫(xiě)成 ：PQR (PQ)R 可寫(xiě)成：PQR (P Q)R)(RP)Q) 可寫(xiě)成： (P QR)RPQ 為方便起見(jiàn)，公式最外層的括號(hào)可省略。有時(shí)為了看起來(lái)清楚醒目, 也可保留某些原可省去的括號(hào)。 1.2 聯(lián)結(jié)詞第16頁(yè)/共53頁(yè)11/4/2021 2:51 PM17 單個(gè)命

10、題變?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)寫(xiě)為wff。1.3 命題公式第17頁(yè)/共53頁(yè)11/4/2021 2:51 PM18【例5】 判斷下列表達(dá)式是否為合式公式: p(pq) (pq)r

11、) (p(qr) (pq)(qr) (pq)r) (pq)r) s) (pq)r) s（是）（是）（否）（否）（否）（是）（是）1.3 命題公式第18頁(yè)/共53頁(yè)11/4/2021 2:51 PM19 【例6】 將下列自然語(yǔ)言形式化:(a) 如果天不下雨并且不刮風(fēng)，我就去書(shū)店。解 ：設(shè)P：今天天下雨，Q：今天天刮風(fēng)，R：我去書(shū)店。 則原命題符號(hào)化為： (PQ)R (b) 小王邊走邊唱。解：設(shè)p：小王走路，q：小王唱歌。 則原命題符號(hào)化為： pq (c) 除非a能被2整除，否則a不能被4整除。解：設(shè)p：a能被2整除，q：a能被4整除。 則原命題符號(hào)化為： p q 或 q p1.3 命題公式第19

12、頁(yè)/共53頁(yè)11/4/2021 2:51 PM20 (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 命題公式第20頁(yè)/共53頁(yè)11/4/2021 2:51 PM21 1、 重言式（Tautology）重言式(永真式)真值恒為1的公式。如：PP 【例7】判斷（P P(P Q)）是否為重言式。P QPQP(PQ)P P(PQ)0 00 11 01 10

13、0 010 0 111 1 11（P P(P Q)）為重言式。1.4 重言式、矛盾式、可滿足公式第21頁(yè)/共53頁(yè)11/4/2021 2:51 PM22 2、 矛盾式（Contradiction)矛盾式（永假式）真值恒為0的公式。如：P P 【例8】判斷(PQ)P是否為矛盾式。P QPQ(PQ)P0 00 11 01 10 0 010 0 00（ (PQ)P ）為矛盾式。1.4 重言式、矛盾式、可滿足公式第22頁(yè)/共53頁(yè)11/4/2021 2:51 PM233、 可滿足公式（Satisfaction） 可滿足公式至少有一種真值為1的情況。 (除矛盾式之外的公式) ，永真式也是可滿足公式。定理

14、：由n個(gè)命題變?cè)还部山M成 個(gè)不同的命題。其中永真式有一個(gè)，矛盾式有一個(gè)，可滿足公式有 個(gè)。 n22122n1.4 重言式、矛盾式、可滿足公式第23頁(yè)/共53頁(yè)11/4/2021 2:51 PM24 【例9】 構(gòu)造公式PQ、(PQ)、PQ、Q P的真值 。解：真值表如下： 由例題可見(jiàn)，公式PQ、(PQ)、PQ、Q P的真值表是完全相同的，我們稱其為等值的。那么如何判斷兩個(gè)公式等值呢？ 1.5 等價(jià)與蘊(yùn)涵第24頁(yè)/共53頁(yè)11/4/2021 2:51 PM251.5.1 等價(jià)1、 等價(jià)的定義等價(jià)設(shè)A、B是兩個(gè)命題公式，當(dāng)A與B有完全相同的真值，則稱A和B等價(jià)，即為AB。定理：設(shè)A、B是兩個(gè)命題公

15、式， AB 的充要條件是AB為永真式。等價(jià)置換：假設(shè)X是公式A的子公式，如果XY，則將X置換為Y所得的公式與A等價(jià)。1.5 等價(jià)與蘊(yùn)涵第25頁(yè)/共53頁(yè)11/4/2021 2:51 PM262、 等價(jià)與雙條件的區(qū)別等價(jià)：不是一個(gè)聯(lián)結(jié)詞，AB不是一個(gè)命題公式，表示的是A、B之間的邏輯關(guān)系。雙條件：是一個(gè)聯(lián)結(jié)詞， AB是命題公式。 1.5 等價(jià)與蘊(yùn)涵第26頁(yè)/共53頁(yè)11/4/2021 2:51 PM27 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)

16、(AB)(AC) A(BC) (AB)(AC)(6)德摩根律 (AB) AB (AB) AB1.5 等價(jià)與蘊(yùn)涵第27頁(yè)/共53頁(yè)11/4/2021 2:51 PM28 (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(12)等價(jià)等值式 AB (AB)(BA)(13)逆反律 AB BA(14)輸出律 A(BC) (AB)C(15)歸謬論 (AB)(AB) A1.5 等價(jià)與蘊(yùn)涵第28頁(yè)/共53頁(yè)11/4/2021 2:51 PM29 思考：證明兩個(gè)公式等價(jià)的方法：1、構(gòu)造真值表

17、。2 、等價(jià)推導(dǎo)法。（若一個(gè)公式變?cè)?，由于n個(gè)變?cè)M成的真值表有2n行，所以用等價(jià)推導(dǎo)的方法來(lái)證明。）1.5 等價(jià)與蘊(yùn)涵第29頁(yè)/共53頁(yè)11/4/2021 2:51 PM30 【例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 等價(jià)與蘊(yùn)涵第30頁(yè)/共53頁(yè)11/4/2021 2:51 PM31 【例12】化解公式(p(qr)(qr)(pr)。解： (p(qr)(qr)(pr) (pqr)(qp )r) (pq)r)(qp)r)

18、(pq)(qp )r (pq)(qp )r 1r r 1.5 等價(jià)與蘊(yùn)涵第31頁(yè)/共53頁(yè)11/4/2021 2:51 PM32 1.5.2 蘊(yùn)含1、蘊(yùn)涵的定義蘊(yùn)含設(shè)A、B是兩個(gè)命題公式，若A為真，B必定為真，則稱A蘊(yùn)含B，記作AB。定理：設(shè)A、B是兩個(gè)命題公式， AB 的充要條件是AB為永真式。1.5 等價(jià)與蘊(yùn)涵第32頁(yè)/共53頁(yè)11/4/2021 2:51 PM33 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)涵第33頁(yè)/共53頁(yè)11/4/2021 2:51 PM34 【例13】 證明

19、 (PQ)PQ 。證明：真值表如下：由真值表可見(jiàn)， (PQ)P為1時(shí)，Q為真。 (PQ)PQ P QPQ(PQ)P(PQ)PQ0 00 11 01 11 1 010 0 011 1 111.5 等價(jià)與蘊(yùn)涵第34頁(yè)/共53頁(yè)11/4/2021 2:51 PM35 1.6.1 推理推理已知H1、H2、Hm，證明C的過(guò)程。寫(xiě)成命題邏輯的形式為： H1 H2 HmC 其中， H1、H2、Hm稱為推理的前提，C為這一組前提的有效結(jié)論。推理的過(guò)程就是證明H1H2HmC的過(guò)程。 1.6.2 推理方法 證明H1H2Hm C為永真式。1、真值表法2、等價(jià)推導(dǎo)法1.6 推理理論第35頁(yè)/共53頁(yè)11/4/2021

20、 2:51 PM36 【例14】證明 (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.6 推理理論第36頁(yè)/共53頁(yè)11/4/2021 2:51 PM373、幾種常用的推理的定律(1) 假言推理（肯定的肯定）P(PQ)Q 通過(guò)肯定條件的前件從而肯定條件的后件。如： PQ：如果他喝酒，則他臉紅。 P：他喝酒。 Q：他臉紅。但是， PQ：如果他喝酒，則他臉紅。 Q：他臉紅。 P：他喝酒。不成立注意：不

21、能通過(guò)肯定條件的后件而肯定條件的前件。1.6 推理理論第37頁(yè)/共53頁(yè)11/4/2021 2:51 PM38 (2) 拒取式（否定的否定）Q(PQ)P 通過(guò)否定條件的后件從而否定條件的前件。如： PQ：小王評(píng)上三好學(xué)生，則小王成績(jī)好。 Q ：小王成績(jī)不好。 P ：小王沒(méi)評(píng)上三好學(xué)生。注意：不能通過(guò)否定條件的前件而肯定條件的后件。1.6 推理理論第38頁(yè)/共53頁(yè)11/4/2021 2:51 PM39(3) 析取三段論 (PQ)PQ 產(chǎn)生一個(gè)事件的原因有P和Q，否定P，則一定是Q。如： PQ：成績(jī)不好是老師教得不好或自己不努力。 P ：老師教得好。 Q：自己不努力。推廣： (PQRS)PQR

22、S 1.6 推理理論第39頁(yè)/共53頁(yè)11/4/2021 2:51 PM40 (4) 假言三段論 (PQ)(QR)PR 如： PQ：如果不下雨，就開(kāi)運(yùn)動(dòng)會(huì)。 QR：如果開(kāi)運(yùn)動(dòng)會(huì)，就不上課。 PR ：如果不下雨，就不上課。1.6 推理理論第40頁(yè)/共53頁(yè)11/4/2021 2:51 PM411.6 推理理論常用的蘊(yùn)涵式 (9) P，PQQ；(10) Q，PQP；(11) P，PQQ；(12) PQ，QRPR；(13) PQ，PR，QRR；(14) PQ，RS(PR)(QS)；(15) P，QPQ。(1) PQP；(2) PQQ；(3) PPQ；(4) QPQ；(5) P(PQ)；(6) Q(P

23、Q)；(7) (PQ)P；(8) (PQ)Q；第41頁(yè)/共53頁(yè)11/4/2021 2:51 PM42 4、證明方法（形式演繹）(1) P規(guī)則（前提引入規(guī)則）：給定的前提在證明的過(guò)程中隨時(shí)都可以加以引用。(2) 規(guī)則（結(jié)論引用規(guī)則）：在證明過(guò)程中產(chǎn)生的結(jié)論可以作為后續(xù)證明的前提加以引用。(3) CP規(guī)則（附加前提引入規(guī)則）：如果證明的形式為H1 H2 Hm AB，等價(jià)于證明H1H2HmAB。A稱為附加前提。1.6 推理理論第42頁(yè)/共53頁(yè)11/4/2021 2:51 PM43 證明：證明H1 H2 HmAB等價(jià)于證明 (H1 H2 Hm) (AB)為永真式。(H1 H2 Hm) (AB) (

24、H1 H2 Hm) (AB) (H1 H2 HmA) B(H1 H2 HmA)B證明H1 H2 Hm AB等價(jià)于證明 H1H2HmAB。1.6 推理理論第43頁(yè)/共53頁(yè)11/4/2021 2:51 PM44 【例15】證明 (PQ)(PR)(QS)(RS)證明： PQ P PQ T QS P PS T SP T PR P SR T RS T 1.6 推理理論第44頁(yè)/共53頁(yè)11/4/2021 2:51 PM45 【例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 推理理論第45頁(yè)/共53頁(yè)11/4/2021 2:51 PM46 【例17】 證明下面諸命題推得的結(jié)論是有效的: 如果今