离散数学习题课-命题逻辑

1、1习题课习题课-命题逻辑命题逻辑(1)o主要内容主要内容n命题、真值、简单命题与复合命题、命题命题、真值、简单命题与复合命题、命题符号化符号化n联结词联结词 , , , , 及复合命题符号化及复合命题符号化n命题公式及层次命题公式及层次n公式的类型公式的类型n真值表及应用真值表及应用2习题课习题课-命题逻辑命题逻辑(1)o基本要求基本要求n深刻理解各联结词的逻辑关系深刻理解各联结词的逻辑关系, 熟练地将熟练地将命题符号化命题符号化n会求复合命题的真值会求复合命题的真值n深刻理解合式公式及重言式、矛盾式、可深刻理解合式公式及重言式、矛盾式、可满足式等概念满足式等概念n熟练地求公式的真值表，并用它

2、求公式的熟练地求公式的真值表，并用它求公式的成真赋值与成假赋值及判断公式类型成真赋值与成假赋值及判断公式类型3练习练习1o判断下列语句是否为命题：判断下列语句是否为命题：n十是一个整数十是一个整数.n北京是一个村庄北京是一个村庄.n请勿吸烟请勿吸烟!n雪是黑色的雪是黑色的.n今天是今天是7号号.n1+101=110.n您吃饭了吗您吃饭了吗?n我学英语或法语我学英语或法语.n如果天气好如果天气好,我就去散步我就去散步.1.我不给所有自己替自己理发的人理发，但却给我不给所有自己替自己理发的人理发，但却给所有自己不替自己理发的人理发。所有自己不替自己理发的人理发。是是否否是是是是是是否否是是是是否否

3、是是4练习练习2o将下列命题符号化将下列命题符号化 (1) 豆沙包是由面粉和红小豆做成的豆沙包是由面粉和红小豆做成的. (2) 苹果树和梨树都是落叶乔木苹果树和梨树都是落叶乔木. (3) 王小红或李大明是物理组成员王小红或李大明是物理组成员. (4) 王小红或李大明中的一人是物理组成员王小红或李大明中的一人是物理组成员. (5) 由于交通阻塞，他迟到了由于交通阻塞，他迟到了. (6) 如果交通不阻塞，他就不会迟到如果交通不阻塞，他就不会迟到. (7) 他没迟到，所以交通没阻塞他没迟到，所以交通没阻塞. (8) 除非交通阻塞，否则他不会迟到除非交通阻塞，否则他不会迟到. (9) 他迟到当且仅当交

4、通阻塞他迟到当且仅当交通阻塞.5练习练习2解答解答(1) 豆沙包是由面粉和红小豆做成的豆沙包是由面粉和红小豆做成的.(2) 苹果树和梨树都是落叶乔木苹果树和梨树都是落叶乔木.(3) 王小红或李大明是物理组成员王小红或李大明是物理组成员.(4) 王小红或李大明中的一人是物理组成员王小红或李大明中的一人是物理组成员.设设 P: 交通阻塞，交通阻塞，Q: 他迟到他迟到(5) 由于交通阻塞，他迟到了由于交通阻塞，他迟到了. (6) 如果交通不阻塞，他就不会迟到如果交通不阻塞，他就不会迟到.(7) 他没迟到，所以交通没阻塞他没迟到，所以交通没阻塞.(8) 除非交通阻塞，否则他不会迟到除非交通阻塞，否则他

5、不会迟到.(9) 他迟到当且仅当交通阻塞他迟到当且仅当交通阻塞.简单命题简单命题合取式合取式析取式析取式异或异或PQ PQ或或QP QP 或或PQ PQ 或或QPPQ 6练习练习3o设设 P : 2是素数是素数 Q : 北京比天津人口多北京比天津人口多 R : 乌鸦是白色的乌鸦是白色的 求下面命题的真值求下面命题的真值 (1) (P Q)R (2) (Q R)(PR) (3) (QR)(PR) (4) (QP)(PR)( RQ)01007习题课习题课-命题逻辑命题逻辑(2)o主要内容主要内容n等值式与等值演算等值式与等值演算n基本等值式（基本等值式（10.410.4；4242个公式）个公式）n

6、主析取范式与主合取范式主析取范式与主合取范式n联结词的扩充联结词的扩充8习题课习题课-命题逻辑命题逻辑(2)l基本要求基本要求l深刻理解等值式的概念深刻理解等值式的概念l牢记基本等值式的名称及它们的内容牢记基本等值式的名称及它们的内容l熟练地应用基本等值式及置换规则进行等熟练地应用基本等值式及置换规则进行等值演算值演算l理解简单析取式、简单合取式、析取范式、理解简单析取式、简单合取式、析取范式、合取范式的概念合取范式的概念l深刻理解极小项、极大项的概念、名称及深刻理解极小项、极大项的概念、名称及下角标与成真、成假赋值的关系，并理解下角标与成真、成假赋值的关系，并理解简单合取式与极小项的关系简单

7、合取式与极小项的关系9习题课习题课-命题逻辑命题逻辑(2)l基本要求基本要求l熟练掌握求主范式的方法（等值演算、真熟练掌握求主范式的方法（等值演算、真值表等）值表等）l会用主范式求公式的成真赋值、成假赋值、会用主范式求公式的成真赋值、成假赋值、判断公式的类型、判断两个公式是否等值判断公式的类型、判断两个公式是否等值l会将公式等值地化成指定联结词公式会将公式等值地化成指定联结词公式l会用命题逻辑的概念及运算解决简单的应会用命题逻辑的概念及运算解决简单的应用问题用问题10练习练习1 概念概念o设设A与与B为含为含n个命题变项的公式，判断下列命题个命题变项的公式，判断下列命题是否为真？是否为真？(1

8、) AB当且仅当当且仅当A与与B有相同的主析取范式有相同的主析取范式(2) 若若A为重言式，则为重言式，则A的主合取范式为的主合取范式为0(3) 若若A为矛盾式，则为矛盾式，则A的主析取范式为的主析取范式为1(4) 任何公式都能等值地化成任何公式都能等值地化成 , 中的公式中的公式(5) 任何公式都能等值地化成任何公式都能等值地化成 , , 中的公式中的公式真真假假假假假假真真11练习练习2: 判断公式类型判断公式类型o判断下列公式的类型判断下列公式的类型: (1) (PQ)( QP)(2) (PQ) Q(3) (PQ)P12练习练习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练习题练习题2(续续)o(2) (PQ) Qo解解 用等值演算法求公式的主范式用等值演算法求公式的主范式 (PQ) Q ( P Q) Q PQ Q 0 主析取范式主析取范式 M0 M1 M2 M3 主合取范式主合取范式矛盾式矛盾式14练习练习2(续续)o(3) (PQ)Po解解 用等值演算法求公式的主范式用等值演算法求公式的主范

10、式 (PQ)P ( P Q)P P ( PQ) ( P Q) m0 m1 主析取范式主析取范式 M2 M3 主合取范式主合取范式可满足式可满足式15练习练习3：求公式的主范式求公式的主范式o已知命题公式已知命题公式A中含中含3个命题变项个命题变项P, Q, R，并知，并知道它的成真赋值为道它的成真赋值为001, 010, 111, 求求A的主析取范的主析取范式和主合取范式，及式和主合取范式，及A对应的真值函数对应的真值函数.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练习练习4：应用题：应用题o某公司要从赵、钱、孙、李、周五名新毕业的某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习大学生中选派一些人出国学习. 选派必须满足以选派必须满足以下条件：下条件：(1) 若赵去，钱也去若赵去，钱也去.(2) 李、周两人中至少有一人去李、周两人中至少有一人去(3) 钱、孙两人中去且仅去一人钱、孙两人中去且仅去一人.(4) 孙、李两人同去或同不去孙、李两人同去或同不去.(5) 若周去，则赵、钱也去若周去，则赵、钱也去. 用等值演算法分析该公司

12、如何选派他们出国？用等值演算法分析该公司如何选派他们出国？17练习练习4解答解答o解此类问题的步骤：解此类问题的步骤：1.设简单命题并符号化设简单命题并符号化2. 用复合命题描述各条件用复合命题描述各条件3. 写出由复合命题组成的合取式写出由复合命题组成的合取式4. 将合取式成析取式（最好是主析取范式）将合取式成析取式（最好是主析取范式）5. 求成真赋值求成真赋值, 并做出解释和结论并做出解释和结论18练习练习4解答解答o1. 设简单命题并符号化设简单命题并符号化 设设 P: 派赵去，派赵去，Q: 派钱去，派钱去，R: 派孙去，派孙去，S: 派派李去，李去，U: 派周去派周去o2. 写出复合命

13、题写出复合命题(1) 若赵去，钱也去若赵去，钱也去(2) 李、周两人中至少有一人去李、周两人中至少有一人去(3) 钱、孙两人中去且仅去一人钱、孙两人中去且仅去一人(4) 孙、李两人同去或同不去孙、李两人同去或同不去(5) 若周去，则赵、钱也去若周去，则赵、钱也去PQS U(QR) ( Q R)(R S) ( RS)U(P Q)19练习练习4解答解答o3. 设设(1)(5)构成的合取式为构成的合取式为A A = (PQ) (S U) (QR) ( Q R) (R S) ( RS) (U(P Q)o4. 化成析取式化成析取式 A ( PQ R SU) (P QRS U)o结论：由上述析取式可知，结

14、论：由上述析取式可知，A的成真赋值为的成真赋值为00110与与11001， 派孙、李去（赵、钱、周不去）派孙、李去（赵、钱、周不去） 派赵、钱、周去（孙、李不去）派赵、钱、周去（孙、李不去）20练习练习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习题课习题课-命题逻辑命题逻辑(3)o主要内容主要内容n推理的形式结构推理的形式结构n判断推理是否正确的方法判断推理是否正确的方法o真值表法真值表法 o等值演算法等值演算法o主析取范式法主析取范式法n推理定律推理定律o自然推理系统自然推理系统o构造推理证明的方法构造推理证明的方法n直接证明法直接证明法n附加前提证明法附加前提证明法n归谬法归谬法(反证法反证法)22习题课习题课-命题逻辑命题逻辑(3)o基本要求基本要求n理解并记住推理形式结构的两种形式：理解并记住推

16、理形式结构的两种形式： 1. (A1 A2 Ak)B 2. 前提：前提：A1, A2, , Ak 结论：结论：Bn熟练掌握判断推理是否正确的不同方法（如真值熟练掌握判断推理是否正确的不同方法（如真值表法、等值演算法、主析取范式法等）表法、等值演算法、主析取范式法等）n牢记牢记 各条推理规则各条推理规则n熟练掌握构造证明的直接证明法、附加前提证明熟练掌握构造证明的直接证明法、附加前提证明法和归谬法法和归谬法n会解决实际中的简单推理问题会解决实际中的简单推理问题23练习练习1：判断推理是否正确：判断推理是否正确o1. 判断下面推理是否正确：判断下面推理是否正确：(1) 前提：前提： PQ, Q 结

17、论：结论： Po解解 推理的形式结构推理的形式结构: ( PQ)QP 方法一：等值演算法方法一：等值演算法 ( PQ)QP (P Q)Q)P ( PQ) QP ( P Q) ( Q Q)P P Q 易知易知10是成假赋值，不是重言式，所以推理不正是成假赋值，不是重言式，所以推理不正确确.24练习练习1解答解答o方法二：主析取范式法，方法二：主析取范式法， ( PQ)QP (P Q)Q)P P Q M2 m0 m1 m3未含未含m2, 不是重言式不是重言式, 推理不正确推理不正确.25练习练习1解答解答o方法三方法三 真值表法真值表法 111001110100( PQ)QPQP PQ 0 1 1

18、 1( PQ)Q 0 0 1 0o方法四方法四 直接观察出直接观察出10是成假赋值是成假赋值不是重言式不是重言式, 推理不正确推理不正确26练习练习1o(2) 前提：前提：QR, PR 结论：结论：QP o解解 推理的形式结构：推理的形式结构：(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练习练习2：构造证明：构造证明o2. 在系统在系统P中构造下面推理的证明：中构造下面推理的证明： 如果今天是周六，我们就到颐和园或圆明园玩如果今天是周六，我们就到颐和园或圆明园玩. 如果颐和园游人太多，就不去颐和园如果颐和园游人太多，就不去颐和园. 今天是周今天是周六，并且颐和园游