離散數(shù)學(xué)(命題邏輯)課后總結(jié).doc
《離散數(shù)學(xué)(命題邏輯)課后總結(jié).doc》由會(huì)員分享,可在線閱讀,更多相關(guān)《離散數(shù)學(xué)(命題邏輯)課后總結(jié).doc(10頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
離散數(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. 燈泡或者 線路有故障。(析取“∨”) 例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:也稱之為蘊(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é)。 如何安排課表,使得三位教師都滿意。令L1 、L2 、L3 分別表示語(yǔ)言課排在第一、第二、第三節(jié)。 M1 、M2 、M3 分別表示數(shù)學(xué)課排在第一、第二、第三節(jié)。 P1 、P2 、P3 分別表示原理課排在第一、 第二、第三節(jié)。 三位教師都滿意的條件是: (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. 命題邏輯推理 例題1求證 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 例題2求證 (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 例題3 用命題邏輯推理方法證明下面推理的有效性: 如果我學(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 例題4求證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 例題5 用條件論證,證明例題4 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 例題6 用命題邏輯推理方法證明下面推理的有效性: 如果體育館有球賽,青年大街交通就擁擠。在這種情況下,如果小王不提前出發(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∧R) 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 例7 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)容、及要求: 1.邏輯聯(lián)結(jié)詞,要熟練掌握聯(lián)結(jié)詞的真值表定義以及它們?cè)谧匀徽Z(yǔ)言中的含義。其中特別要注意“∨”和“→”的用法。 2.會(huì)命題符號(hào)化。 3.掌握永真式的證明方法: (1).真值表。 (2).等價(jià)變換,化簡(jiǎn)成T。 (3).主析取范式。 4.掌握永真蘊(yùn)含式的證明方法,熟練記憶并會(huì)應(yīng)用 43頁(yè)中表1-8.3中的永真蘊(yùn)含式。 5.掌握等價(jià)公式的證明方法,熟練記憶并會(huì)應(yīng)用 43頁(yè)表1-8.4中的等價(jià)公式。 6.熟練掌握范式的寫(xiě)法及其應(yīng)用。 7.熟練掌握三種推理方法。 以上自己是不是都已經(jīng)熟練掌握了呢??- 1.請(qǐng)仔細(xì)閱讀文檔,確保文檔完整性,對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來(lái)的問(wèn)題本站不予受理。
- 2.下載的文檔,不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請(qǐng)點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
9.9 積分
下載 |
- 配套講稿:
如PPT文件的首頁(yè)顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開(kāi)word文檔。
- 特殊限制:
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 離散數(shù)學(xué) 命題邏輯 課后 總結(jié)
鏈接地址:http://m.jqnhouse.com/p-9966618.html