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

離散數(shù)學(xué)（課件上習(xí)題）第一章例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：小王能跳舞。 PQ：小王能歌善舞。 例1-2.3. 燈泡或者 線路有故障。（析取“”） 例1-2.4. 第一節(jié)課上數(shù)學(xué)或者上英語。（異或 、排斥或 。即“”） 注意：P Q 與 (PQ)(QP ) 是一樣的。 歸納自然語言中的聯(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 是等邊三角形 當且僅當它是等角三角形。課后練習(xí)：填空已知PQ為T，則P為( )，Q為( )。已知PQ為F，則P為( )，Q為( )。已知P為F，則PQ為( )。已知P為T，則PQ為( )。已知PQ為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 的真值為( )。13節(jié)例1.說離散數(shù)學(xué)無用且枯燥無味是不對的。 P：離散數(shù)學(xué)是有用的。 Q：離散數(shù)學(xué)是枯燥無味的。 該命題可寫成： (PQ)例2. 如果小張與小王都不去，則小李去。 P ： 小張去。 Q ： 小王去。 R ： 小李去。 該命題可寫成： (PQ)R 如果小張與小王不都去，則小李去。 該命題可寫成： (PQ)R 也可以寫成： (PQ)R例3. 僅當天不下雨且我有時間，才上街。 P：天下雨。Q：我有時間。R：我上街。 分析：由于 “僅當 ”是表示 “必要條件 ”的，既 “天不下雨且我有時間 ”，是 “我上街 ”的必要條件。所以 該命題可寫成： R(PQ) 例4. 人不犯我，我不犯人；人若犯我，我必犯人。 P ： 人犯我。Q ： 我犯人。 該命題可寫成：(PQ)(PQ)或?qū)懗桑?PQ例5 .若天不下雨，我就上街；否則在家。 P：天下雨。Q ：我上街。R：我在家。 該命題可寫成： (PQ)(PR). 注意：中間的聯(lián)結(jié)詞一定是“”，而不是“”，也不是“ ”。14節(jié)重言(永真)蘊涵式證明方法方法1.列真值表。方法2.假設(shè)前件為真，推出后件也為真。例如求證： (AB)C)D(CD) AB證明:設(shè)前件(AB)C)D(CD) 為真則(AB)C)、D、(CD)均真， D為T，則D為F CD為T 得C為F (AB)C )為T 得AB為F 如果A為F，則A為T，所以AB為T。 如果B為F，則B為T，所以AB 為T。 (AB)C)D(CD) AB方法3.假設(shè)后件為假，推出前件也為假 。例如求證： (AB)C)D(CD) AB 證明: 假設(shè)后件AB 為F, 則A 與B 均為T 。 1. 如C 為F ，則(AB)C為F，所以 前件(AB)C)D(CD) 為F 。 2. 如C 為T ，則 若D 為T ，則D 為F ， 所以前件(AB)C)D(CD) 為假； 若D為F，則CD 為F ， 所以 前件(AB)C)D(CD) 為假。(AB)C)D(CD) AB重要的重言蘊涵式( 如教材第43 頁所示)（課件中出現(xiàn)過多次，可不用記憶） I1. PQP I2. PQQ I3. PPQ I4. QPQ I5. PPQ I6. QPQ I7. (PQ)P I8. (PQ)Q I9. P,Q PQ I10. P(PQ)Q I11. P(PQ)Q I12. Q(PQ)P I13. (PQ)(QR)PR I14. (PQ)(PR)(QR)R I15. AB (AC)(BC) I16. AB (AC)(BC)15節(jié)重要的等價公式（課件中出現(xiàn)多次，可不用記憶） 對合律 P P 冪等律 PPP PPP 結(jié)合律 P(QR)(PQ)R P(QR)(PQ)R 交換律 PQQP PQQP 分配律 P(QR)(PQ)(PR) P(QR)(PQ)(PR) 吸收律 P(PQ)P P(PQ)P 底-摩根定律 (PQ)PQ (PQ)PQ 同一律 PFP PTP 零律 PTT PFF 互補律 PPT PPF PQ PQ PQ QP PQ (PQ)(QP) PQ (PQ)(PQ) PQ (PQ)(PQ )例題1. 求證吸收律 P(PQ)P證明 ： P(PQ) (PF)(PQ) (同一律) P(FQ) (分配律) PF (零律) P (同一律)例題2. 求證 (PQ)(PQ) P 證明 (PQ)(PQ) (PQ)(PQ) ( 公式E16) (PQ)(PQ) ( 摩根定律) (PQ)(PQ) ( 對合律) P(QQ) ( 分配律) PT ( 互補律) P ( 同一律) 公式E16 ： PQPQ 例題3.化簡(PQ)(P(PQ)解 原公式(PQ)(PP)Q) (E16,結(jié)合) (PQ)(PQ) (對合律，冪等律) (PQ)(QP) (交換律) (PQ)Q)P (結(jié)合律) QP (吸收律)公式E16 ： PQPQ 1-6.范式(Paradigm) 例1. 求 PQ 和PQ的 主析取范式TTTTFFFTFTTFTTFFPQPQQP方法一：真值表 PQ m0m1m3 (PQ)(PQ)(PQ) PQm0m3 (PQ)(PQ)方法 ：用公式的等價變換 先寫出給定公式的析取范式 A1A2.An 。 為使每個Ai 都變成小項，對缺少變元的Ai 補全變元，比如缺變元R ， 就用 聯(lián)結(jié)永真式(RR) 形式補R 。 用分配律等公式加以整理。 PQPQ(P(QQ)(P P) Q)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)思考題: 永真式的主析取范式是什么樣 ？（包含所有小項） 例2.求 PQ 和PQ的 主合取范式TTTTFFFTFTTFTTFFPQPQQP PQ M2 PQ PQ M1M2 (PQ )(PQ)方法：用公式的等價變換 先寫出給定公式的合取范式 A1A2.An 。 為使每個Ai 變成大項，對缺少變元的析取式Ai 補全變元，比如缺變元R ， 就用聯(lián) 結(jié)永假式(RR) 形式補R 。 用分配律等公式加以整理。 例如，求(PQ)R 的主合取范式 (PQ)R (PQ)R (PQ)R (PR)(QR) (P(QQ)R)(PP)QR) (PQR) (PQR) (PQR)(PQR) (PQR)(PQR) (PQR) 例3. 安排課表，教語言課的教師希望將課程安排在第一或第三節(jié)；教數(shù)學(xué)課的教師希望將課程安排在第二或第三節(jié)；教原理課的教師希望將課程安排在第一或第二節(jié)。如何安排課表，使得三位教師都滿意。令L1 、L2 、L3 分別表示語言課排在第一、第二、第三節(jié)。 M1 、M2 、M3 分別表示數(shù)學(xué)課排在第一、第二、第三節(jié)。 P1 、P2 、P3 分別表示原理課排在第一、 第二、第三節(jié)。 三位教師都滿意的條件是：(L1L3)(M2M3)(P1P2 ) 為真。 將上式寫成析取范式( 用分配律) 得：(L1M2)(L1M3)(L3M2)(L3M3)(P1P2)(L1M2P1)(L1M3P1) (L3M2P1)(L3M3P1) (L1M2P2)(L1M3P2) (L3M2P2)(L3M3P2) 可以取(L3 M2P1)、(L1M3P2) 為T ， 得到兩種排法。TTTTTFTTFTFTTFFTTTTFFFTFFTFFTFFFA(P,Q,R)RQP課堂練習(xí)：1.已知A(P,Q,R)的真值表如圖： 求它的主析取和主合取范式。2. 已知A(P,Q,R)的主析取范式中 含有下面小項m1, m3, m5, m7 求它的主合取范式.3. 已知A(P1,P2,Pn)的主合取范式中 含有k個大項，問它的主析取范式 中有多少個小項？課堂練習(xí)答案1.A(P,Q,R)的主析取范式: A(P,Q,R) m0m3m4m6m7 (PQR)(PQR) (PQR)(PQR)(PQ R) A(P,Q,R)的主合取范式： A(P,Q,R) M1M2M5 (PQR)(PQR)(PQR) 2. A(P,Q,R) M0M2M4 M6 (PQR)(PQR)(PQR) (PQR)3. A(P1,P2,Pn)的主析取范式中含有2n-k個小項.1-7. 命題邏輯推理例題求證 PQ，QR，P R證明 序號 前提或結(jié)論 所用規(guī)則 從哪幾步得到 所用公式 (1) P P (2) PQ P (3) Q T (1)(2) I11 (4) QR P (5) R T (3)(4) I11例題求證(PQ)(QR)R P(1) QR P(2) R P(3) Q T (1)(2) I10(4) (PQ) P(5) PQ T (4) E8(6) P T (3)(5) I10注公式I10為： P,PQ Q 公式E8為： (PQ) PQ 例題 用命題邏輯推理方法證明下面推理的有效性： 如果我學(xué)習(xí)，那么我數(shù)學(xué)不會不及格。如果我不熱衷于玩樸克，那么我將學(xué)習(xí)。但是我數(shù)學(xué)不及格。因此，我熱衷于玩樸克。解:設(shè) P：我學(xué)習(xí)。 Q：我數(shù)學(xué)及格。 R：我熱衷于玩樸克。 于是符號化為： PQ，RP，Q RPQ，RP，Q R(1) PQ P(2) Q P (3) P T (1)(2) I12 (4) RP P(5) R T (3)(4) I12 (6) R T (5) E1注：公式I12為： Q，PQ P公式E1 為： RR 例題求證P(QS),RP,Q RS 證明(1) P(QS) P (2) P(QS) T (1) E16 (3) P(SQ) T (2) E3 (4) (PS)Q T (3) E5 (5) Q P (6) PS T (4)(5) I10 (7) PS T (6) E16 (8) RP P (9) RP T (8) E16 (10) RS T (7)(9) I13例題 用條件論證，證明例題 P(QS),RP,Q RS證明 (1) R P(附加前提) (2) RP P (3) P T (1)(2) I10 (4) P(QS) P (5) QS T (3)(4) I11 (6) Q P (7) S T (5)(6) I11 (8) RS CP例題 用命題邏輯推理方法證明下面推理的有效性： 如果體育館有球賽，青年大街交通就擁擠。在這種情況下，如果小王不提前出發(fā)，就會遲到。因此，小王沒有提前出發(fā)也未遲到，則體育館沒有球賽。證明 先將命題符號化。 設(shè) P：體育館有球賽。 Q：青年大街交通擁擠。 R：小王提前出發(fā)。 S：小王遲到。 PQ，(QR)S (RS)P PQ，(QR)S (RS)P證明(1) RS P(附加前提)(2) R T (1) I1(3) S T (1) I2(4) (QR)S P(5) (Q) T (3)(4) I12(6) QR T (5) E8 (7) Q T (2)(6) I10(8) PQ P(9) P T (7)(8) I12(10)(RS)P CP例 PQ,(QR)R, (PS)S 證明 (1) S P(假設(shè)前提)(2) S T (1) E1(3) (PS) P(4) PS T (3) E8(5) P T (2)(4) I10(6) PQ P(7) Q T (5)(6) I11(8) (QR)R P(9) QR T (8) I1 (10) R T (8) I2(11) R T (7)(9) I10(12) RR T (10)(11) I9第一章 習(xí)題課1.有工具箱A、B、C、D，各個箱內(nèi)裝的工具如下表所示。試問如何攜帶數(shù)量最少工具箱，而所包含的工具種類齊全。工具箱 改錐扳 手鉗 子錘 子A有有B有有有C有有D有有解：設(shè)A、B、C、D分別表示帶A、B、C、D箱。則總的條件為： (AC)(ABD)(BC)(BD) 為真。 改錐 扳手 鉗子 錘子將(AC)(ABD)(BC)(BD)寫成析取范式，上式(AC)(BC)(A(BD)(BD) (交換 ) (AB)C)(BD) (分配(提取C)、吸收) (ABB )(CB )(ABD)(CD) (分配) (AB)(CB )(ABD)(CD)分別可以取(AB)、(CB )、(CD)為真。于是可以得到三種攜帶方法：帶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(yù):清潔工謀害了經(jīng)理。 B:秘書謀害了經(jīng)理。 C:謀害發(fā)生在午夜前。 D:秘書的證詞是正確的. E:午夜時屋里燈光滅了。H:清潔工富裕. G:經(jīng)理有錢.命題符號為：AB,AC,DC,DE,HA,GH,E ?AB,AC,BC, DC DE,HA,GH,E ? E P DE P D T I D T E DC P C T I AC P A T I AB 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)熟練掌握了呢？