離散數(shù)學(xué)(命題邏輯)課后總結(jié).doc

離散數(shù)學(xué)（課件上習(xí)題） 第一章 例1-1.1 判定下面這些句子哪些是命題。 ⑴ 2是個(gè)素?cái)?shù)。 ⑵ 雪是黑色的。 ⑶ 2013年人類(lèi)將到達(dá)火星。 ⑷ 如果 a>b且b>c，則a>c 。（其中a,b,c都是 確定的實(shí)數(shù)） ⑸ x+y<5 ⑹ 請(qǐng)打開(kāi)書(shū)！ ⑺ 您去嗎？ ⑴⑵⑶⑷是命題 例1-2.1 P：2是素?cái)?shù)。 P：2不是素?cái)?shù) 。 例1-2.2 P：小王能唱歌。 Q：小王能跳舞。 P∧Q：小王能歌善舞。 例1-2.3. 燈泡或者 線(xiàn)路有故障。（析取“∨”） 例1-2.4. 第一節(jié)課上數(shù)學(xué)或者上英語(yǔ)。（異或 、排斥或 。即“?”） 注意：P ? Q 與 (P∧Q)∨(Q∧P ) 是一樣的。 歸納自然語(yǔ)言中的聯(lián)結(jié)詞，定義了六個(gè)邏輯聯(lián)結(jié)詞，分別是：（1）否定 “ ” (2) 合取 “∧ ” (3) 析取 “∨ ” (4) 異或 “? ” (5) 蘊(yùn)涵 “ ” (6) 等價(jià) “ ” 例1-2.5： P表示：缺少水分。 Q表示：植物會(huì)死亡。 PQ：如果缺少水分，植物就會(huì)死亡。 PQ：也稱(chēng)之為蘊(yùn)涵式，讀成 “P蘊(yùn)涵Q”， “如果P則Q”。 也說(shuō)成P是PQ 的前件，Q是PQ的后件。 還可以說(shuō)P是Q的充分條件，Q是P的必要條件。 以下是關(guān)于蘊(yùn)含式的一個(gè)例子 P：天氣好。 Q：我去公園。 1.如果天氣好，我就去公園。 2.只要天氣好，我就去公園。 3.天氣好，我就去公園。 4.僅當(dāng)天氣好，我才去公園。 5.只有天氣好，我才去公園。 6.我去公園，僅當(dāng)天氣好。 命題1.、2.、3.寫(xiě)成： PQ 命題4.、5.、6.寫(xiě)成： QP 例1-2.6： P：△ABC 是等邊三角形。 Q ：△ABC是等角三角形。 PQ ：△ABC 是等邊三角形 當(dāng)且僅當(dāng)它是等角三角形。 課后練習(xí)：填空 已知P∧Q為T(mén)，則P為( )，Q為( )。 已知P∨Q為F，則P為( )，Q為( )。 已知P為F，則P∧Q為( )。 已知P為T(mén)，則P∨Q為( )。 已知P∨Q為T(mén)，且P為F ，則Q為( )。 已知PQ為F，則P為( )，Q為( )。 已知P為F，則PQ為( )。 已知Q為T(mén)，則PQ為( )。 已知 PQ為F，則P為( )， Q為( )。 已知P為T(mén)， PQ為T(mén)，則Q為( )。 已知Q為T(mén), PQ為T(mén)，則P為( )。 已知PQ 為T(mén) ，P 為T(mén) , 則Q 為( ). 已知PQ 為F ，P 為T(mén) , 則Q 為( ). PP 的真值為( ). PP 的真值為( )。 1—3節(jié) 例1.說(shuō)離散數(shù)學(xué)無(wú)用且枯燥無(wú)味是不對(duì)的。 P：離散數(shù)學(xué)是有用的。 Q：離散數(shù)學(xué)是枯燥無(wú)味的。 該命題可寫(xiě)成： (P∧Q) 例2. 如果小張與小王都不去，則小李去。 P ： 小張去。 Q ： 小王去。 R ： 小李去。 該命題可寫(xiě)成： (P∧Q)R 如果小張與小王不都去，則小李去。 該命題可寫(xiě)成： (P∧Q)R 也可以寫(xiě)成： (P∨Q)R 例3. 僅當(dāng)天不下雨且我有時(shí)間，才上街。 P：天下雨。Q：我有時(shí)間。R：我上街。 分析：由于 “僅當(dāng) ”是表示 “必要條件 ”的，既 “天不下雨且我有時(shí)間 ”，是 “我上街 ”的必要條件。所以 該命題可寫(xiě)成： R(P∧Q) 例4. 人不犯我，我不犯人；人若犯我，我必犯人。 P ： 人犯我。Q ： 我犯人。 該命題可寫(xiě)成：(PQ)∧(PQ)或?qū)懗桑?PQ 例5 .若天不下雨，我就上街；否則在家。 P：天下雨。Q ：我上街。R：我在家。 該命題可寫(xiě)成： (PQ)∧(PR). 注意：中間的聯(lián)結(jié)詞一定是“∧”，而不是“∨”，也不是“? ”。 1—4節(jié) 重言(永真)蘊(yùn)涵式證明方法 方法1.列真值表。 方法2.假設(shè)前件為真，推出后件也為真。 例如求證： ((A∧B)C)∧D∧(C∨D) A∨B 證明:設(shè)前件((A∧B)C)∧D∧(C∨D) 為真則((A∧B)C)、D、(C∨D)均真， D為T(mén)，則D為F C∨D為T(mén) 得C為F ((A∧B)C )為T(mén) 得A∧B為F 如果A為F，則A為T(mén)，所以A∨B為T(mén)。 如果B為F，則B為T(mén)，所以A∨B 為T(mén)。 \((A∧B)C)∧D∧(C∨D) A∨B 方法3.假設(shè)后件為假，推出前件也為假 。 例如求證： ((A∧B)C)∧D∧(C∨D) A∨B 證明: 假設(shè)后件A∨B 為F, 則A 與B 均為T(mén) 。 1. 如C 為F ，則(A∧B)C為F，所以 前件((A∧B)C)∧D∧(C∨D) 為F 。 2. 如C 為T(mén) ，則 ⑴ 若D 為T(mén) ，則D 為F ， 所以前件((A∧B)C)∧D∧(C∨D) 為假； ⑵若D為F，則C∨D 為F ， 所以 前件((A∧B)C)∧D∧(C∨D) 為假。 \((A∧B)C)∧D∧(C∨D) A∨B 重要的重言蘊(yùn)涵式( 如教材第43 頁(yè)所示)（課件中出現(xiàn)過(guò)多次，可不用記憶） I1. P∧QP I2. P∧QQ I3. PP∨Q I4. QP∨Q I5. PPQ I6. QPQ I7. (PQ)P I8. (PQ)Q I9. P,Q P∧Q I10. P∧(P∨Q)Q I11. P∧(PQ)Q I12. Q∧(PQ)P I13. (PQ)∧(QR)PR I14. (P∨Q)∧(PR)∧(QR)R I15. AB (A∨C)(B∨C) I16. AB (A∧C)(B∧C) 1—5節(jié) 重要的等價(jià)公式（課件中出現(xiàn)多次，可不用記憶） ⑴ 對(duì)合律 P P ⑵ 冪等律 P∨PP P∧PP ⑶ 結(jié)合律 P∨(Q∨R)(P∨Q)∨R P∧(Q∧R)(P∧Q)∧R ⑷ 交換律 P∨QQ∨P P∧QQ∧P ⑸分配律 P∨(Q∧R)(P∨Q)∧(P∨R) P∧(Q∨R)(P∧Q)∨(P∧R) ⑹ 吸收律 P∨(P∧Q)P P∧(P∨Q)P ⑺底-摩根定律 (P∨Q)P∧Q (P∧Q)P∨Q ⑻ 同一律 P∨FP P∧TP ⑼ 零律 P∨TT P∧FF ⑽ 互補(bǔ)律 P∨PT P∧PF ⑾ PQ P∨Q ⑿ PQ QP ⒀ PQ (PQ)∧(QP) ⒁ PQ (P∨Q)∧(P∨Q) ⒂ PQ (P∧Q)∨(P∧Q ) 例題1. 求證吸收律 P∧(P∨Q)P 證明 ： P∧(P∨Q) (P∨F)∧(P∨Q) (同一律) P∨(F∧Q) (分配律) P∨F (零律) P (同一律) 例題2. 求證 (P∨Q)→(P∧Q) P 證明 (P∨Q)→(P∧Q) (P∨Q)∨(P∧Q) ( 公式E16) (P∧Q)∨(P∧Q) ( 摩根定律) (P∧Q)∨(P∧Q) ( 對(duì)合律) P∧(Q∨Q) ( 分配律) P∧T ( 互補(bǔ)律) P ( 同一律) 公式E16 ： PQP∨Q 例題3.化簡(jiǎn)(P∧Q)→(P∨(P∨Q)) 解 原公式(P∧Q)∨((P∨P)∨Q) (E16,結(jié)合) (P∧Q)∨(P∨Q) (對(duì)合律，冪等律) (P∧Q)∨(Q∨P) (交換律) ((P∧Q)∨Q)∨P (結(jié)合律) Q∨P (吸收律) 公式E16 ： PQP∨Q 1-6.范式(Paradigm) 例1. 求 PQ 和PQ的 主析取范式 T T T T F F F T F T T F T T F F PQ PQ Q P 方法一：真值表 PQ m0∨m1∨m3 (P∧Q)∨(P∧Q)∨(P∧Q) PQm0∨m3 (P∧Q)∨(P∧Q) 方法Ⅱ ：用公式的等價(jià)變換 ⑴ 先寫(xiě)出給定公式的析取范式 A1∨A2∨...∨An 。 ⑵ 為使每個(gè)Ai 都變成小項(xiàng)，對(duì)缺少變?cè)腁i 補(bǔ)全變?cè)热缛弊冊(cè)猂 ， 就用∧ 聯(lián)結(jié)永真式(R∨R) 形式補(bǔ)R 。 ⑶ 用分配律等公式加以整理。 PQP∨Q (P∧(Q∨Q))∨((P∨ P)∧ Q) (P∧Q)∨(P∧Q)∨(P∧Q)∨(P∧Q) (P∧Q)∨(P∧Q)∨(P∧Q) 思考題: 永真式的主析取范式是什么樣 ？（包含所有小項(xiàng)） 例2.求 PQ 和PQ的 主合取范式 T T T T F F F T F T T F T T F F PQ PQ Q P PQ M2 P∨Q PQ M1∧M2 (P∨Q )∧(P∨Q) 方法Ⅱ：用公式的等價(jià)變換 ⑴ 先寫(xiě)出給定公式的合取范式 A1∧A2∧...∧An 。 ⑵ 為使每個(gè)Ai 變成大項(xiàng)，對(duì)缺少變?cè)奈鋈∈紸i 補(bǔ)全變?cè)?，比如缺變?cè)猂 ， 就用∨聯(lián) 結(jié)永假式(R∧R) 形式補(bǔ)R 。 ⑶ 用分配律等公式加以整理。 例如，求(PQ)R 的主合取范式 (PQ)R (P∨Q)∨R (P∧Q)∨R (P∨R)∧(Q∨R) (P∨(Q∧Q)∨R)∧((P∧P)∨Q∨R) (P∨Q∨R)∧ (P∨Q∨R)∧ (P∨Q∨R)∧(P∨Q∨R) (P∨Q∨R)∧(P∨Q∨R)∧ (P∨Q∨R) 例3. 安排課表，教語(yǔ)言課的教師希望將課程安排在第一或第三節(jié)；教數(shù)學(xué)課的教師 希望將課程安排在第二或第三節(jié)；教原理課的教師希望將課程安排在第一或第二節(jié)。 如何安排課表，使得三位教師都滿(mǎn)意。令L1 、L2 、L3 分別表示語(yǔ)言課排在第一、第二、第三節(jié)。 M1 、M2 、M3 分別表示數(shù)學(xué)課排在第一、第二、第三節(jié)。 P1 、P2 、P3 分別表示原理課排在第一、 第二、第三節(jié)。 三位教師都滿(mǎn)意的條件是： (L1∨L3)∧(M2∨M3)∧(P1∨P2 ) 為真。 將上式寫(xiě)成析取范式( 用分配律) 得： ((L1∧M2)∨(L1∧M3)∨(L3∧M2)∨ (L3∧M3))∧(P1∨P2) (L1∧M2∧P1)∨(L1∧M3∧P1)∨ (L3∧M2∧P1)∨(L3∧M3∧P1)∨ (L1∧M2∧P2)∨(L1∧M3∧P2)∨ (L3∧M2∧P2)∨(L3∧M3∧P2) 可以取(L3 ∧M2∧P1)、(L1∧M3∧P2) 為T(mén) ， 得到兩種排法。 T T T T T F T T F T F T T F F T T T T F F F T F F T F F T F F F A(P,Q,R) R Q P 課堂練習(xí)： 1.已知A(P,Q,R)的真值表如圖： 求它的主析取和主合取范式。 2. 已知A(P,Q,R)的主析取范式中 含有下面小項(xiàng)m1, m3, m5, m7 求它的主合取范式. 3. 已知A(P1,P2,…,Pn)的主合取范式中 含有k個(gè)大項(xiàng)，問(wèn)它的主析取范式 中有多少個(gè)小項(xiàng)？ 課堂練習(xí)答案 1.A(P,Q,R)的主析取范式: A(P,Q,R) m0∨m3∨m4∨m6∨m7 (P∧Q∧R)∨(P∧Q∧R)∨ (P∧Q∧R)∨(P∧Q∧R)∨(P∧Q ∧R) A(P,Q,R)的主合取范式： A(P,Q,R) M1∧M2∧M5 (P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R) 2. A(P,Q,R) M0∧M2∧M4 ∧M6 (P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R) ∧(P∨Q∨R) 3. A(P1,P2,…,Pn)的主析取范式中含有2n-k個(gè)小項(xiàng). 1-7. 命題邏輯推理 例題１求證 P→Q，Q→R，P R 證明 序號(hào) 前提或結(jié)論 所用規(guī)則 從哪幾步得到 所用公式 (1) P P (2) PQ P (3) Q T (1)(2) I11 (4) Q→R P (5) R T (3)(4) I11 例題２求證 (P∧Q)∧(Q∨R)∧R P (1) Q∨R P (2) R P (3) Q T (1)(2) I10 (4) (P∧Q) P (5) P∨Q T (4) E8 (6) P T (3)(5) I10 注公式I10為： P,P∨Q Q 公式E8為： (P∧Q) P∨Q 例題３ 用命題邏輯推理方法證明下面推理的有效性： 如果我學(xué)習(xí)，那么我數(shù)學(xué)不會(huì)不及格。如果我不熱衷于玩樸克，那么我將學(xué)習(xí)。但是我數(shù)學(xué)不及格。因此，我熱衷于玩樸克。 解:設(shè) P：我學(xué)習(xí)。 Q：我數(shù)學(xué)及格。 R：我熱衷于玩樸克。 于是符號(hào)化為： P→Q，R→P，Q R P→Q，R→P，Q R (1) P→Q P (2) Q P (3) P T (1)(2) I12 (4) R→P P (5) R T (3)(4) I12 (6) R T (5) E1 注：公式I12為： Q，P→Q P 公式E1 為： RR 例題４求證P→(Q→S),R∨P,Q R→S 證明(1) P→(Q→S) P (2) P∨(Q∨S) T (1) E16 (3) P∨(S∨Q) T (2) E3 (4) (P∨S)∨Q T (3) E5 (5) Q P (6) P∨S T (4)(5) I10 (7) P→S T (6) E16 (8) R∨P P (9) R→P T (8) E16 (10) R→S T (7)(9) I13 例題５ 用條件論證，證明例題４ P→(Q→S),R∨P,Q R→S 證明 (1) R P(附加前提) (2) R∨P P (3) P T (1)(2) I10 (4) P→(Q→S) P (5) Q→S T (3)(4) I11 (6) Q P (7) S T (5)(6) I11 (8) R→S CP 例題６ 用命題邏輯推理方法證明下面推理的有效性： 如果體育館有球賽，青年大街交通就擁擠。在這種情況下，如果小王不提前出發(fā)，就會(huì)遲到。因此，小王沒(méi)有提前出發(fā)也未遲到，則體育館沒(méi)有球賽。 證明 先將命題符號(hào)化。 設(shè) P：體育館有球賽。 Q：青年大街交通擁擠。 R：小王提前出發(fā)。 S：小王遲到。 P→Q，(Q∧R)→S (R∧S)→P P→Q，(Q∧R)→S (R∧S)→P 證明 (1) R∧S P(附加前提) (2) R T (1) I1 (3) S T (1) I2 (4) (Q∧R)→S P (5) (Q∧Ｒ) T (3)(4) I12 (6) Q∨R T (5) E8 (7) Q T (2)(6) I10 (8) P→Q P (9) P T (7)(8) I12 (10)(R∧S)→P CP 例７ P→Q,(Q∨R)∧R, (P∧S)S 證明 (1) S P(假設(shè)前提) (2) S T (1) E1 (3) (P∧S) P (4) P∨S T (3) E8 (5) P T (2)(4) I10 (6) P→Q P (7) Q T (5)(6) I11 (8) (Q∨R)∧R P (9) Q∨R T (8) I1 (10) R T (8) I2 (11) R T (7)(9) I10 (12) R∧R T (10)(11) I9 第一章 習(xí)題課 1.有工具箱A、B、C、D，各個(gè)箱內(nèi)裝的工具如下表所示。試問(wèn)如何攜帶數(shù)量最少工具箱，而所包含的工具種類(lèi)齊全。 工具箱 改錐 扳 手 鉗 子 錘 子 A 有 有 B 有 有 有 C 有 有 D 有 有 解：設(shè)A、B、C、D分別表示帶A、B、C、D箱。 則總的條件為： (A∨C)∧(A∨B∨D)∧(B∨C)∧(B∨D) 為真。 改錐 扳手 鉗子 錘子 將(A∨C)∧(A∨B∨D)∧(B∨C)∧(B∨D)寫(xiě)成析取范式，上式((A∨C)∧(B∨C))∧((A∨(B∨D))∧(B∨D)) (交換 ) ((A∧B)∨C))∧(B∨D) (分配(提取C)、吸收) (A∧B∧B )∨(C∧B )∨(A∧B∧D)∨(C∧D) (分配) (A∧B)∨(C∧B )∨(A∧B∧D)∨(C∧D) 分別可以取(A∧B)、(C∧B )、(C∧D)為真。 于是可以得到三種攜帶方法： 帶A和B箱， 帶B和C箱，帶C和D箱。 請(qǐng)根據(jù)下面事實(shí)，找出兇手： 1. 清潔工或者秘書(shū)謀害了經(jīng)理。 2. 如果清潔工謀害了經(jīng)理，則謀害不會(huì)發(fā)生在午夜前。 3.如果秘書(shū)的證詞是正確的，則謀害發(fā)生在午夜前。 4.如果秘書(shū)的證詞不正確，則午夜時(shí)屋里燈光未滅。 5. 如果清潔工富裕，則他不會(huì)謀害經(jīng)理。 6.經(jīng)理有錢(qián)且清潔工不富裕。 7.午夜時(shí)屋里燈滅了。 令A(yù):清潔工謀害了經(jīng)理。 B:秘書(shū)謀害了經(jīng)理。 C:謀害發(fā)生在午夜前。 D:秘書(shū)的證詞是正確的. E:午夜時(shí)屋里燈光滅了。H:清潔工富裕. G:經(jīng)理有錢(qián). 命題符號(hào)為： A∨B,AC,DC,DE,HA,G∧H,E ? A∨B,AC,BC, DC DE,HA,G∧H,E ? ⑴ E P ⑵ DE P ⑶ D T ⑴⑵ I ⑷ D T ⑶ E ⑸ DC P ⑹ C T ⑷⑸ I ⑺ AC P ⑻ A T ⑹⑺ I ⑼ A∨B P ⑽ B T ⑻⑼ I 結(jié)果是秘書(shū)謀害了經(jīng)理。 第一章 小結(jié) 本章的重點(diǎn)內(nèi)容、及要求： １.邏輯聯(lián)結(jié)詞，要熟練掌握聯(lián)結(jié)詞的真值表定義以及它們?cè)谧匀徽Z(yǔ)言中的含義。其中特別要注意“∨”和“→”的用法。 ２.會(huì)命題符號(hào)化。 ３.掌握永真式的證明方法： (1).真值表。 (2).等價(jià)變換，化簡(jiǎn)成Ｔ。 (3).主析取范式。 ４.掌握永真蘊(yùn)含式的證明方法，熟練記憶并會(huì)應(yīng)用 43頁(yè)中表1-8.3中的永真蘊(yùn)含式。 ５.掌握等價(jià)公式的證明方法，熟練記憶并會(huì)應(yīng)用 43頁(yè)表1-8.4中的等價(jià)公式。 ６.熟練掌握范式的寫(xiě)法及其應(yīng)用。 ７.熟練掌握三種推理方法。 以上自己是不是都已經(jīng)熟練掌握了呢？？