離散數(shù)學(xué)習(xí)題課-命題邏輯

1、1習(xí)題課習(xí)題課-命題邏輯命題邏輯(1)o主要內(nèi)容主要內(nèi)容n命題、真值、簡單命題與復(fù)合命題、命題命題、真值、簡單命題與復(fù)合命題、命題符號化符號化n聯(lián)結(jié)詞聯(lián)結(jié)詞 , , , , 及復(fù)合命題符號化及復(fù)合命題符號化n命題公式及層次命題公式及層次n公式的類型公式的類型n真值表及應(yīng)用真值表及應(yīng)用2習(xí)題課習(xí)題課-命題邏輯命題邏輯(1)o基本要求基本要求n深刻理解各聯(lián)結(jié)詞的邏輯關(guān)系深刻理解各聯(lián)結(jié)詞的邏輯關(guān)系, 熟練地將熟練地將命題符號化命題符號化n會求復(fù)合命題的真值會求復(fù)合命題的真值n深刻理解合式公式及重言式、矛盾式、可深刻理解合式公式及重言式、矛盾式、可滿足式等概念滿足式等概念n熟練地求公式的真值表，并用它

2、求公式的熟練地求公式的真值表，并用它求公式的成真賦值與成假賦值及判斷公式類型成真賦值與成假賦值及判斷公式類型3練習(xí)練習(xí)1o判斷下列語句是否為命題：判斷下列語句是否為命題：n十是一個整數(shù)十是一個整數(shù).n北京是一個村莊北京是一個村莊.n請勿吸煙請勿吸煙!n雪是黑色的雪是黑色的.n今天是今天是7號號.n1+101=110.n您吃飯了嗎您吃飯了嗎?n我學(xué)英語或法語我學(xué)英語或法語.n如果天氣好如果天氣好,我就去散步我就去散步.1.我不給所有自己替自己理發(fā)的人理發(fā)，但卻給我不給所有自己替自己理發(fā)的人理發(fā)，但卻給所有自己不替自己理發(fā)的人理發(fā)。所有自己不替自己理發(fā)的人理發(fā)。是是否否是是是是是是否否是是是是否否

3、是是4練習(xí)練習(xí)2o將下列命題符號化將下列命題符號化 (1) 豆沙包是由面粉和紅小豆做成的豆沙包是由面粉和紅小豆做成的. (2) 蘋果樹和梨樹都是落葉喬木蘋果樹和梨樹都是落葉喬木. (3) 王小紅或李大明是物理組成員王小紅或李大明是物理組成員. (4) 王小紅或李大明中的一人是物理組成員王小紅或李大明中的一人是物理組成員. (5) 由于交通阻塞，他遲到了由于交通阻塞，他遲到了. (6) 如果交通不阻塞，他就不會遲到如果交通不阻塞，他就不會遲到. (7) 他沒遲到，所以交通沒阻塞他沒遲到，所以交通沒阻塞. (8) 除非交通阻塞，否則他不會遲到除非交通阻塞，否則他不會遲到. (9) 他遲到當(dāng)且僅當(dāng)交

4、通阻塞他遲到當(dāng)且僅當(dāng)交通阻塞.5練習(xí)練習(xí)2解答解答(1) 豆沙包是由面粉和紅小豆做成的豆沙包是由面粉和紅小豆做成的.(2) 蘋果樹和梨樹都是落葉喬木蘋果樹和梨樹都是落葉喬木.(3) 王小紅或李大明是物理組成員王小紅或李大明是物理組成員.(4) 王小紅或李大明中的一人是物理組成員王小紅或李大明中的一人是物理組成員.設(shè)設(shè) P: 交通阻塞，交通阻塞，Q: 他遲到他遲到(5) 由于交通阻塞，他遲到了由于交通阻塞，他遲到了. (6) 如果交通不阻塞，他就不會遲到如果交通不阻塞，他就不會遲到.(7) 他沒遲到，所以交通沒阻塞他沒遲到，所以交通沒阻塞.(8) 除非交通阻塞，否則他不會遲到除非交通阻塞，否則他

5、不會遲到.(9) 他遲到當(dāng)且僅當(dāng)交通阻塞他遲到當(dāng)且僅當(dāng)交通阻塞.簡單命題簡單命題合取式合取式析取式析取式異或異或PQ PQ或或QP QP 或或PQ PQ 或或QPPQ 6練習(xí)練習(xí)3o設(shè)設(shè) P : 2是素數(shù)是素數(shù) Q : 北京比天津人口多北京比天津人口多 R : 烏鴉是白色的烏鴉是白色的 求下面命題的真值求下面命題的真值 (1) (P Q)R (2) (Q R)(PR) (3) (QR)(PR) (4) (QP)(PR)( RQ)01007習(xí)題課習(xí)題課-命題邏輯命題邏輯(2)o主要內(nèi)容主要內(nèi)容n等值式與等值演算等值式與等值演算n基本等值式（基本等值式（10.410.4；4242個公式）個公式）n

6、主析取范式與主合取范式主析取范式與主合取范式n聯(lián)結(jié)詞的擴充聯(lián)結(jié)詞的擴充8習(xí)題課習(xí)題課-命題邏輯命題邏輯(2)l基本要求基本要求l深刻理解等值式的概念深刻理解等值式的概念l牢記基本等值式的名稱及它們的內(nèi)容牢記基本等值式的名稱及它們的內(nèi)容l熟練地應(yīng)用基本等值式及置換規(guī)則進行等熟練地應(yīng)用基本等值式及置換規(guī)則進行等值演算值演算l理解簡單析取式、簡單合取式、析取范式、理解簡單析取式、簡單合取式、析取范式、合取范式的概念合取范式的概念l深刻理解極小項、極大項的概念、名稱及深刻理解極小項、極大項的概念、名稱及下角標與成真、成假賦值的關(guān)系，并理解下角標與成真、成假賦值的關(guān)系，并理解簡單合取式與極小項的關(guān)系簡單

7、合取式與極小項的關(guān)系9習(xí)題課習(xí)題課-命題邏輯命題邏輯(2)l基本要求基本要求l熟練掌握求主范式的方法（等值演算、真熟練掌握求主范式的方法（等值演算、真值表等）值表等）l會用主范式求公式的成真賦值、成假賦值、會用主范式求公式的成真賦值、成假賦值、判斷公式的類型、判斷兩個公式是否等值判斷公式的類型、判斷兩個公式是否等值l會將公式等值地化成指定聯(lián)結(jié)詞公式會將公式等值地化成指定聯(lián)結(jié)詞公式l會用命題邏輯的概念及運算解決簡單的應(yīng)會用命題邏輯的概念及運算解決簡單的應(yīng)用問題用問題10練習(xí)練習(xí)1 概念概念o設(shè)設(shè)A與與B為含為含n個命題變項的公式，判斷下列命題個命題變項的公式，判斷下列命題是否為真？是否為真？(1

8、) AB當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)A與與B有相同的主析取范式有相同的主析取范式(2) 若若A為重言式，則為重言式，則A的主合取范式為的主合取范式為0(3) 若若A為矛盾式，則為矛盾式，則A的主析取范式為的主析取范式為1(4) 任何公式都能等值地化成任何公式都能等值地化成 , 中的公式中的公式(5) 任何公式都能等值地化成任何公式都能等值地化成 , , 中的公式中的公式真真假假假假假假真真11練習(xí)練習(xí)2: 判斷公式類型判斷公式類型o判斷下列公式的類型判斷下列公式的類型: (1) (PQ)( QP)(2) (PQ) Q(3) (PQ)P12練習(xí)練習(xí)2: 判斷公式類型判斷公式類型o(1) (PQ)( QP)o

9、解解 用等值演算法求主范式用等值演算法求主范式 (PQ)( QP) ( P Q) (QP) (PQ) (QP) (PQ) ( P Q) (P Q) ( PQ) m2 m1 m3 m0 m0 m1 m2 m3 主析取范式主析取范式 1 主合取范式主合取范式重言式重言式13練習(xí)題練習(xí)題2(續(xù)續(xù))o(2) (PQ) Qo解解 用等值演算法求公式的主范式用等值演算法求公式的主范式 (PQ) Q ( P Q) Q PQ Q 0 主析取范式主析取范式 M0 M1 M2 M3 主合取范式主合取范式矛盾式矛盾式14練習(xí)練習(xí)2(續(xù)續(xù))o(3) (PQ)Po解解 用等值演算法求公式的主范式用等值演算法求公式的主范

10、式 (PQ)P ( P Q)P P ( PQ) ( P Q) m0 m1 主析取范式主析取范式 M2 M3 主合取范式主合取范式可滿足式可滿足式15練習(xí)練習(xí)3：求公式的主范式求公式的主范式o已知命題公式已知命題公式A中含中含3個命題變項個命題變項P, Q, R，并知，并知道它的成真賦值為道它的成真賦值為001, 010, 111, 求求A的主析取范的主析取范式和主合取范式，及式和主合取范式，及A對應(yīng)的真值函數(shù)對應(yīng)的真值函數(shù).o解：解： oA的主析取范式為的主析取范式為m1 m2 m7 A的主合取范式為的主合取范式為M0 M3 M4 M5 M6 P Q R A P Q R A 0 0 0 0 1

11、 0 0 0 0 0 1 1 1 0 1 0 0 1 0 1 1 1 0 0 0 1 1 0 1 1 1 116練習(xí)練習(xí)4：應(yīng)用題：應(yīng)用題o某公司要從趙、錢、孫、李、周五名新畢業(yè)的某公司要從趙、錢、孫、李、周五名新畢業(yè)的大學(xué)生中選派一些人出國學(xué)習(xí)大學(xué)生中選派一些人出國學(xué)習(xí). 選派必須滿足以選派必須滿足以下條件：下條件：(1) 若趙去，錢也去若趙去，錢也去.(2) 李、周兩人中至少有一人去李、周兩人中至少有一人去(3) 錢、孫兩人中去且僅去一人錢、孫兩人中去且僅去一人.(4) 孫、李兩人同去或同不去孫、李兩人同去或同不去.(5) 若周去，則趙、錢也去若周去，則趙、錢也去. 用等值演算法分析該公司

12、如何選派他們出國？用等值演算法分析該公司如何選派他們出國？17練習(xí)練習(xí)4解答解答o解此類問題的步驟：解此類問題的步驟：1.設(shè)簡單命題并符號化設(shè)簡單命題并符號化2. 用復(fù)合命題描述各條件用復(fù)合命題描述各條件3. 寫出由復(fù)合命題組成的合取式寫出由復(fù)合命題組成的合取式4. 將合取式成析取式（最好是主析取范式）將合取式成析取式（最好是主析取范式）5. 求成真賦值求成真賦值, 并做出解釋和結(jié)論并做出解釋和結(jié)論18練習(xí)練習(xí)4解答解答o1. 設(shè)簡單命題并符號化設(shè)簡單命題并符號化 設(shè)設(shè) P: 派趙去，派趙去，Q: 派錢去，派錢去，R: 派孫去，派孫去，S: 派派李去，李去，U: 派周去派周去o2. 寫出復(fù)合命

13、題寫出復(fù)合命題(1) 若趙去，錢也去若趙去，錢也去(2) 李、周兩人中至少有一人去李、周兩人中至少有一人去(3) 錢、孫兩人中去且僅去一人錢、孫兩人中去且僅去一人(4) 孫、李兩人同去或同不去孫、李兩人同去或同不去(5) 若周去，則趙、錢也去若周去，則趙、錢也去PQS U(QR) ( Q R)(R S) ( RS)U(P Q)19練習(xí)練習(xí)4解答解答o3. 設(shè)設(shè)(1)(5)構(gòu)成的合取式為構(gòu)成的合取式為A A = (PQ) (S U) (QR) ( Q R) (R S) ( RS) (U(P Q)o4. 化成析取式化成析取式 A ( PQ R SU) (P QRS U)o結(jié)論：由上述析取式可知，結(jié)

14、論：由上述析取式可知，A的成真賦值為的成真賦值為00110與與11001， 派孫、李去（趙、錢、周不去）派孫、李去（趙、錢、周不去） 派趙、錢、周去（孫、李不去）派趙、錢、周去（孫、李不去）20練習(xí)練習(xí)4解答解答A ( P Q) (QR) ( Q R) (S U) ( U (P Q) (R S) ( RS) B1=( P Q) (QR) ( Q R) ( P QR) ( PQ R) (QR) （分配律）（分配律）B2=(S U) ( U (P Q) (SU) (P Q S) (P Q U) （分配律）（分配律）B1 B2 ( P QR SU) ( PQ R SU) (QR SU) (P QR

15、S) (P QR U)再令再令 (R S) ( RS)=B3，則，則 B1 B2 B3 ( PQ R SU) (P QRS U)21習(xí)題課習(xí)題課-命題邏輯命題邏輯(3)o主要內(nèi)容主要內(nèi)容n推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)n判斷推理是否正確的方法判斷推理是否正確的方法o真值表法真值表法 o等值演算法等值演算法o主析取范式法主析取范式法n推理定律推理定律o自然推理系統(tǒng)自然推理系統(tǒng)o構(gòu)造推理證明的方法構(gòu)造推理證明的方法n直接證明法直接證明法n附加前提證明法附加前提證明法n歸謬法歸謬法(反證法反證法)22習(xí)題課習(xí)題課-命題邏輯命題邏輯(3)o基本要求基本要求n理解并記住推理形式結(jié)構(gòu)的兩種形式：理解并記住推

16、理形式結(jié)構(gòu)的兩種形式： 1. (A1 A2 Ak)B 2. 前提：前提：A1, A2, , Ak 結(jié)論：結(jié)論：Bn熟練掌握判斷推理是否正確的不同方法（如真值熟練掌握判斷推理是否正確的不同方法（如真值表法、等值演算法、主析取范式法等）表法、等值演算法、主析取范式法等）n牢記牢記 各條推理規(guī)則各條推理規(guī)則n熟練掌握構(gòu)造證明的直接證明法、附加前提證明熟練掌握構(gòu)造證明的直接證明法、附加前提證明法和歸謬法法和歸謬法n會解決實際中的簡單推理問題會解決實際中的簡單推理問題23練習(xí)練習(xí)1：判斷推理是否正確：判斷推理是否正確o1. 判斷下面推理是否正確：判斷下面推理是否正確：(1) 前提：前提： PQ, Q 結(jié)

17、論：結(jié)論： Po解解 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu): ( PQ)QP 方法一：等值演算法方法一：等值演算法 ( PQ)QP (P Q)Q)P ( PQ) QP ( P Q) ( Q Q)P P Q 易知易知10是成假賦值，不是重言式，所以推理不正是成假賦值，不是重言式，所以推理不正確確.24練習(xí)練習(xí)1解答解答o方法二：主析取范式法，方法二：主析取范式法， ( PQ)QP (P Q)Q)P P Q M2 m0 m1 m3未含未含m2, 不是重言式不是重言式, 推理不正確推理不正確.25練習(xí)練習(xí)1解答解答o方法三方法三 真值表法真值表法 111001110100( PQ)QPQP PQ 0 1 1

18、 1( PQ)Q 0 0 1 0o方法四方法四 直接觀察出直接觀察出10是成假賦值是成假賦值不是重言式不是重言式, 推理不正確推理不正確26練習(xí)練習(xí)1o(2) 前提：前提：QR, PR 結(jié)論：結(jié)論：QP o解解 推理的形式結(jié)構(gòu)：推理的形式結(jié)構(gòu)：(QR) (PR)(QP) 用等值演算法用等值演算法 (QR) (PR)(QP) ( Q R) ( PR)( QP) (QR) (P R)( QP) (Q P) (Q R) ( R P)( QP) (Q P) (Q R) ( R P) ( QP)1推理正確推理正確27練習(xí)練習(xí)2：構(gòu)造證明：構(gòu)造證明o2. 在系統(tǒng)在系統(tǒng)P中構(gòu)造下面推理的證明：中構(gòu)造下面推理的證明： 如果今天是周六，我們就到頤和園或圓明園玩如果今天是周六，我們就到頤和園或圓明園玩. 如果頤和園游人太多，就不去頤和園如果頤和園游人太多，就不去頤和園. 今天是周今天是周六，并且頤和園游