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

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

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

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

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

5、不會(huì)遲到.(9) 他遲到當(dāng)且僅當(dāng)交通阻塞他遲到當(dāng)且僅當(dāng)交通阻塞.簡(jiǎn)單命題簡(jiǎn)單命題合取式合取式析取式析取式異或異或PQ PQ或或QP QP 或或PQ PQ 或或QPPQ 6練習(xí)練習(xí)3o設(shè)設(shè) P : 2是素?cái)?shù)是素?cái)?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個(gè)公式）個(gè)公式）n

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

7、合取式與極小項(xiàng)的關(guān)系9習(xí)題課習(xí)題課-命題邏輯命題邏輯(2)l基本要求基本要求l熟練掌握求主范式的方法（等值演算、真熟練掌握求主范式的方法（等值演算、真值表等）值表等）l會(huì)用主范式求公式的成真賦值、成假賦值、會(huì)用主范式求公式的成真賦值、成假賦值、判斷公式的類型、判斷兩個(gè)公式是否等值判斷公式的類型、判斷兩個(gè)公式是否等值l會(huì)將公式等值地化成指定聯(lián)結(jié)詞公式會(huì)將公式等值地化成指定聯(lián)結(jié)詞公式l會(huì)用命題邏輯的概念及運(yùn)算解決簡(jiǎn)單的應(yīng)會(huì)用命題邏輯的概念及運(yùn)算解決簡(jiǎn)單的應(yīng)用問(wèn)題用問(wèn)題10練習(xí)練習(xí)1 概念概念o設(shè)設(shè)A與與B為含為含n個(gè)命題變項(xiàng)的公式，判斷下列命題個(gè)命題變項(xiàng)的公式，判斷下列命題是否為真？是否為真？(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個(gè)命題變項(xiàng)個(gè)命題變項(xiàng)P, Q, R，并知，并知道它的成真賦值為道它的成真賦值為001, 010, 111, 求求A的主析取范的主析取范式和主合取范式，及式和主合取范式，及A對(duì)應(yīng)的真值函數(shù)對(duì)應(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é)生中選派一些人出國(guó)學(xué)習(xí)大學(xué)生中選派一些人出國(guó)學(xué)習(xí). 選派必須滿足以選派必須滿足以下條件：下條件：(1) 若趙去，錢也去若趙去，錢也去.(2) 李、周兩人中至少有一人去李、周兩人中至少有一人去(3) 錢、孫兩人中去且僅去一人錢、孫兩人中去且僅去一人.(4) 孫、李兩人同去或同不去孫、李兩人同去或同不去.(5) 若周去，則趙、錢也去若周去，則趙、錢也去. 用等值演算法分析該公司

12、如何選派他們出國(guó)？用等值演算法分析該公司如何選派他們出國(guó)？17練習(xí)練習(xí)4解答解答o解此類問(wèn)題的步驟：解此類問(wèn)題的步驟：1.設(shè)簡(jiǎn)單命題并符號(hào)化設(shè)簡(jiǎn)單命題并符號(hào)化2. 用復(fù)合命題描述各條件用復(fù)合命題描述各條件3. 寫出由復(fù)合命題組成的合取式寫出由復(fù)合命題組成的合取式4. 將合取式成析取式（最好是主析取范式）將合取式成析取式（最好是主析取范式）5. 求成真賦值求成真賦值, 并做出解釋和結(jié)論并做出解釋和結(jié)論18練習(xí)練習(xí)4解答解答o1. 設(shè)簡(jiǎn)單命題并符號(hào)化設(shè)簡(jiǎn)單命題并符號(hào)化 設(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會(huì)解決實(shí)際中的簡(jiǎn)單推理問(wèn)題會(huì)解決實(shí)際中的簡(jiǎn)單推理問(wè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)造下面推理的證明： 如果今天是周六，我們就到頤和園或圓明園玩如果今天是周六，我們就到頤和園或圓明園玩. 如果頤和園游人太多，就不去頤和園如果頤和園游人太多，就不去頤和園. 今天是周今天是周六，并且頤和園游