《離散數(shù)學(命題邏輯)課后總結(jié).doc》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(命題邏輯)課后總結(jié).doc（10頁珍藏版）》請在裝配圖網(wǎng)上搜索。

離散數(shù)學（課件上習題） 第一章 例1-1.1 判定下面這些句子哪些是命題。 ⑴ 2是個素數(shù)。 ⑵ 雪是黑色的。 ⑶ 2013年人類將到達火星。 ⑷ 如果 a>b且b>c，則a>c 。（其中a,b,c都是 確定的實數(shù)） ⑸ x+y<5 ⑹ 請打開書！ ⑺ 您去嗎？ ⑴⑵⑶⑷是命題 例1-2.1 P：2是素數(shù)。 P：2不是素數(shù) 。 例1-2.2 P：小王能唱歌。 Q：小王能跳舞。 P∧Q：小王能歌善舞。 例1-2.3. 燈泡或者 線路有故障。（析取“∨”） 例1-2.4. 第一節(jié)課上數(shù)學或者上英語。（異或 、排斥或 。即“?”） 注意：P ? Q 與 (P∧Q)∨(Q∧P ) 是一樣的。 歸納自然語言中的聯(lián)結(jié)詞，定義了六個邏輯聯(lián)結(jié)詞，分別是：（1）否定 “ ” (2) 合取 “∧ ” (3) 析取 “∨ ” (4) 異或 “? ” (5) 蘊涵 “ ” (6) 等價 “ ” 例1-2.5： P表示：缺少水分。 Q表示：植物會死亡。 PQ：如果缺少水分，植物就會死亡。 PQ：也稱之為蘊涵式，讀成 “P蘊涵Q”， “如果P則Q”。 也說成P是PQ 的前件，Q是PQ的后件。 還可以說P是Q的充分條件，Q是P的必要條件。 以下是關(guān)于蘊含式的一個例子 P：天氣好。 Q：我去公園。 1.如果天氣好，我就去公園。 2.只要天氣好，我就去公園。 3.天氣好，我就去公園。 4.僅當天氣好，我才去公園。 5.只有天氣好，我才去公園。 6.我去公園，僅當天氣好。 命題1.、2.、3.寫成： PQ 命題4.、5.、6.寫成： QP 例1-2.6： P：△ABC 是等邊三角形。 Q ：△ABC是等角三角形。 PQ ：△ABC 是等邊三角形 當且僅當它是等角三角形。 課后練習：填空 已知P∧Q為T，則P為( )，Q為( )。 已知P∨Q為F，則P為( )，Q為( )。 已知P為F，則P∧Q為( )。 已知P為T，則P∨Q為( )。 已知P∨Q為T，且P為F ，則Q為( )。 已知PQ為F，則P為( )，Q為( )。 已知P為F，則PQ為( )。 已知Q為T，則PQ為( )。 已知 PQ為F，則P為( )， Q為( )。 已知P為T， PQ為T，則Q為( )。 已知Q為T, PQ為T，則P為( )。 已知PQ 為T ，P 為T , 則Q 為( ). 已知PQ 為F ，P 為T , 則Q 為( ). PP 的真值為( ). PP 的真值為( )。 1—3節(jié) 例1.說離散數(shù)學無用且枯燥無味是不對的。 P：離散數(shù)學是有用的。 Q：離散數(shù)學是枯燥無味的。 該命題可寫成： (P∧Q) 例2. 如果小張與小王都不去，則小李去。 P ： 小張去。 Q ： 小王去。 R ： 小李去。 該命題可寫成： (P∧Q)R 如果小張與小王不都去，則小李去。 該命題可寫成： (P∧Q)R 也可以寫成： (P∨Q)R 例3. 僅當天不下雨且我有時間，才上街。 P：天下雨。Q：我有時間。R：我上街。 分析：由于 “僅當 ”是表示 “必要條件 ”的，既 “天不下雨且我有時間 ”，是 “我上街 ”的必要條件。所以 該命題可寫成： R(P∧Q) 例4. 人不犯我，我不犯人；人若犯我，我必犯人。 P ： 人犯我。Q ： 我犯人。 該命題可寫成：(PQ)∧(PQ)或?qū)懗桑?PQ 例5 .若天不下雨，我就上街；否則在家。 P：天下雨。Q ：我上街。R：我在家。 該命題可寫成： (PQ)∧(PR). 注意：中間的聯(lián)結(jié)詞一定是“∧”，而不是“∨”，也不是“? ”。 1—4節(jié) 重言(永真)蘊涵式證明方法 方法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，則D為F C∨D為T 得C為F ((A∧B)C )為T 得A∧B為F 如果A為F，則A為T，所以A∨B為T。 如果B為F，則B為T，所以A∨B 為T。 \((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 。 1. 如C 為F ，則(A∧B)C為F，所以 前件((A∧B)C)∧D∧(C∨D) 為F 。 2. 如C 為T ，則 ⑴ 若D 為T ，則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 重要的重言蘊涵式( 如教材第43 頁所示)（課件中出現(xiàn)過多次，可不用記憶） 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é) 重要的等價公式（課件中出現(xiàn)多次，可不用記憶） ⑴ 對合律 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 ⑽ 互補律 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) ( 對合律) P∧(Q∨Q) ( 分配律) P∧T ( 互補律) P ( 同一律) 公式E16 ： PQP∨Q 例題3.化簡(P∧Q)→(P∨(P∨Q)) 解 原公式(P∧Q)∨((P∨P)∨Q) (E16,結(jié)合) (P∧Q)∨(P∨Q) (對合律，冪等律) (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) 方法Ⅱ ：用公式的等價變換 ⑴ 先寫出給定公式的析取范式 A1∨A2∨...∨An 。 ⑵ 為使每個Ai 都變成小項，對缺少變元的Ai 補全變元，比如缺變元R ， 就用∧ 聯(lián)結(jié)永真式(R∨R) 形式補R 。 ⑶ 用分配律等公式加以整理。 PQP∨Q (P∧(Q∨Q))∨((P∨ P)∧ Q) (P∧Q)∨(P∧Q)∨(P∧Q)∨(P∧Q) (P∧Q)∨(P∧Q)∨(P∧Q) 思考題: 永真式的主析取范式是什么樣 ？（包含所有小項） 例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) 方法Ⅱ：用公式的等價變換 ⑴ 先寫出給定公式的合取范式 A1∧A2∧...∧An 。 ⑵ 為使每個Ai 變成大項，對缺少變元的析取式Ai 補全變元，比如缺變元R ， 就用∨聯(lián) 結(jié)永假式(R∧R) 形式補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. 安排課表，教語言課的教師希望將課程安排在第一或第三節(jié)；教數(shù)學課的教師 希望將課程安排在第二或第三節(jié)；教原理課的教師希望將課程安排在第一或第二節(jié)。 如何安排課表，使得三位教師都滿意。令L1 、L2 、L3 分別表示語言課排在第一、第二、第三節(jié)。 M1 、M2 、M3 分別表示數(shù)學課排在第一、第二、第三節(jié)。 P1 、P2 、P3 分別表示原理課排在第一、 第二、第三節(jié)。 三位教師都滿意的條件是： (L1∨L3)∧(M2∨M3)∧(P1∨P2 ) 為真。 將上式寫成析取范式( 用分配律) 得： ((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 ， 得到兩種排法。 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 課堂練習： 1.已知A(P,Q,R)的真值表如圖： 求它的主析取和主合取范式。 2. 已知A(P,Q,R)的主析取范式中 含有下面小項m1, m3, m5, m7 求它的主合取范式. 3. 已知A(P1,P2,…,Pn)的主合取范式中 含有k個大項，問它的主析取范式 中有多少個小項？ 課堂練習答案 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個小項. 1-7. 命題邏輯推理 例題１求證 P→Q，Q→R，P R 證明 序號 前提或結(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 例題３ 用命題邏輯推理方法證明下面推理的有效性： 如果我學習，那么我數(shù)學不會不及格。如果我不熱衷于玩樸克，那么我將學習。但是我數(shù)學不及格。因此，我熱衷于玩樸克。 解:設(shè) P：我學習。 Q：我數(shù)學及格。 R：我熱衷于玩樸克。 于是符號化為： 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ā)，就會遲到。因此，小王沒有提前出發(fā)也未遲到，則體育館沒有球賽。 證明 先將命題符號化。 設(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 第一章 習題課 1.有工具箱A、B、C、D，各個箱內(nèi)裝的工具如下表所示。試問如何攜帶數(shù)量最少工具箱，而所包含的工具種類齊全。 工具箱 改錐 扳 手 鉗 子 錘 子 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)寫成析取范式，上式((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箱。 請根據(jù)下面事實，找出兇手： 1. 清潔工或者秘書謀害了經(jīng)理。 2. 如果清潔工謀害了經(jīng)理，則謀害不會發(fā)生在午夜前。 3.如果秘書的證詞是正確的，則謀害發(fā)生在午夜前。 4.如果秘書的證詞不正確，則午夜時屋里燈光未滅。 5. 如果清潔工富裕，則他不會謀害經(jīng)理。 6.經(jīng)理有錢且清潔工不富裕。 7.午夜時屋里燈滅了。 令A:清潔工謀害了經(jīng)理。 B:秘書謀害了經(jīng)理。 C:謀害發(fā)生在午夜前。 D:秘書的證詞是正確的. E:午夜時屋里燈光滅了。H:清潔工富裕. G:經(jīng)理有錢. 命題符號為： 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é)果是秘書謀害了經(jīng)理。 第一章 小結(jié) 本章的重點內(nèi)容、及要求： １.邏輯聯(lián)結(jié)詞，要熟練掌握聯(lián)結(jié)詞的真值表定義以及它們在自然語言中的含義。其中特別要注意“∨”和“→”的用法。 ２.會命題符號化。 ３.掌握永真式的證明方法： (1).真值表。 (2).等價變換，化簡成Ｔ。 (3).主析取范式。 ４.掌握永真蘊含式的證明方法，熟練記憶并會應(yīng)用 43頁中表1-8.3中的永真蘊含式。 ５.掌握等價公式的證明方法，熟練記憶并會應(yīng)用 43頁表1-8.4中的等價公式。 ６.熟練掌握范式的寫法及其應(yīng)用。 ７.熟練掌握三種推理方法。 以上自己是不是都已經(jīng)熟練掌握了呢？？