离散数学及其应用数理逻辑部分课后习题答案.doc

1、作业答案：数理逻辑部分P14：习题一1、下列句子中，哪些是命题？在是命题的句子中，哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？（3） 是无理数。5答：简单命题，真命题。（9）吸烟请到吸烟室去！答：不是命题。（12）8 是偶数的充分必要条件是 8 能被 3 整除。答：复合命题，假命题。14、讲下列命题符号化。（6）王强与刘威都学过法语。答： 王强学过法语； 刘威学过法语。:p:q符号化为： （10）除非天下大雨，他就乘班车上班。答： 天下大雨； 他乘班车上班。:符号化为： pq（13） “2 或 4 是素数，这是不对的”是不对的。答： 2 是素数； 4 是素数。:符号化为： ()1

2、5、设 2+3=5.:p大熊猫产在中国。q太阳从西方升起。:r求下列复合命题的真值。（2） ()p（4） ()qrqr解答： 真值为 1； 真值为 1； 真值为 0.（2） 真值为 1； 真值为 1； 真值为 0；pp所以 真值为 0.()r（4） 真值为 1， 真值为 0， 真值为 1；pqq()qr所以 真值为 1.()r19、用真值表判断下列公式的类型。（4） ()()pqpqqp()()qp0 0 1 1 1 1 10 1 1 0 1 1 11 0 0 1 0 0 11 1 0 0 1 1 1所以为重言式。（7） ()()pqrs()()pqrs0 0 0 0 1 1 10 0 0 1

3、 1 0 00 0 1 0 1 0 00 0 1 1 1 1 10 1 0 0 1 1 10 1 0 1 1 0 00 1 1 0 1 0 00 1 1 1 1 1 11 0 0 0 0 1 01 0 0 1 0 0 11 0 1 0 0 0 11 0 1 1 0 1 01 1 0 0 1 1 11 1 0 1 1 0 01 1 1 0 1 0 01 1 1 1 1 1 1所以为可满足式。P36:习题二3、用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出其成真赋值。（1） ()pq解答： ()10pq所以为永假式。（2） ()()pqpr解答： ()()1rpqpr所以

4、因为永真式。（3） ()()pqr解答：()()prq为可满足式。真值表为 prqpr ()()qpr0 0 0 0 0 10 0 1 1 0 00 1 0 1 0 00 1 1 1 0 01 0 0 1 0 01 0 1 1 0 01 1 0 1 0 01 1 1 1 1 14、用等值演算法证明下面的等值式。（2） ()()()pqrpqr解答： ()()rpq（4） ()()()()pqpq解答： ()()()()pqp5、求下列公式的主析取范式，并求它们的成真赋值。（1） ()()q解答： 023()()()()()()(ppqppqpqq pm析 取 范 式 ）所以成真赋值为 00，1

5、0，11（3） ()()pqrpqr解答： ()()()()()rrpqpqrr析 取 范 式()()()()()()( ()(pqrpqrpqrrrrrpqpqrpqr01234567)()( ()(qrrprrmm所以为永真式，成真赋值为 000，001，010，011，100，101，110，1116、求下列公式的主合取范式，并求它们的成假赋值。（1） ()qp解答: 0123()()()()( ()()qppqpqpqpqM合 取 范 式为永假式，成假赋值为 00，01，10，11（3） ()pqr解答： ()1rpq永真式，无成假赋值7、求下列公式的主析取范式，再用主析取范式求主合取

6、范式。（1） ()pqr解答： 13567024()()()()()()()rpqrpqqrpqrqrprmmM已 经 是 析 取 范 式8、求下列公式的主合取范式，再用主合取范式求主析取范式。（2） ()pqr解答： 06123457()()()()()()()()prpqrrpqrqprpqrMmm13、已知公式 A 含 3 个命题变项 ，并且它的成假赋值为 010，011，110，111，求,pqrA 的主析取范式和主合取范式。解答：成真赋值为 000,001,100,101所以主析取范式为 0145而主合取范式为 2367M15、用主析取范式判断下列公式是否等值。（2） 和()pq()

7、解答： 012()()()pqpqpm0()pqm所以两式并不等值。18、将下列公式化成与之等值且仅含有 中联结词的公式,（3） ()pqrp解答： ()(1rpq29、在某班班委成员的选举中，已知王小红、李强、丁金生 3 位同学被选进了班委会。该班的的甲、乙、丙 3 位同学预言：甲说：王小红为班长，李强为生活委员；乙说：丁金生为班长，王小红为生活委员。丙说：李强为班长，王小红为学习委员。班委会分工名单公布后发现，甲乙丙三人都恰好猜对了一半。问王小红、李强、丁金生各任何职？（用等值演算求解）解答：命题符号化：王小红为班长； 李强为生活委员； 丁金生为班长； 王小红为生活委员；:p:q:r:s李

8、强为班长； 王小红为学习委员。uv设 ； ； ； ； ； ；1:A2:p1:Bs2:1:Cuv2:uv由题意可知： 0;0;0;0;prsuvqrs所以 112112221BACABC2,C所以 12121212122212212()()()()()00()0ABBACAABCC所以选举结果为：李强为生活委员；丁金生为班长；王小红为学习委员。30、某公司要从赵、钱、孙、李、周 5 名新毕业的大学生中选派一些人出国学习。选派必须满足条件：（1）若赵去，钱也去；（2）李、周两人中必有一人去；（3）钱、孙两人中去且仅去一人；（4）孙、李两人同去或同不去；（5）若周去，则赵、钱也同去。用等值演算法分析

9、该公司该如何选派他们出国。解答：命题符号化：赵去； 钱去； 孙去； 李去； 周去。:p:q:r:s:t所满足的条件即为（1）若赵去，钱也去： ；pq（2）李、周两人中必有一人去： ；st（3）钱、孙两人中去且仅去一人： ；()()rqr（4）孙、李两人同去或同不去： ；s（5）若周去，则赵、钱也同去： 。tp将所有条件进行合取，然后求其主析取范式()()()()()()pqstqrrsrstpqrt t（过程省略）所以最终方案有两套：（1）赵钱周不去，孙李去；（2）赵钱周去，孙李不去。P50:习题三9、用 3 种方法（真值表、等值演算、主析取范式）证明下面推理是正确的。若 a 是奇数，则 a

10、不能被 2 整除。若 a 是偶数，则 a 能被 2 整除。因此，如果 a 是偶数，则 a 不是奇数。解答：命题符号化： a 为奇数； a 为偶数； a 能被 2 整除:p:q:r推理的形式结构：前提： ； ；r结论： q推理的形式结构的另外一种描述：()()prp证明：（1）真值表法：pqrprrq()()prq()()prqp0 0 0 1 1 1 1 0 10 0 1 1 0 1 1 0 10 1 0 1 1 1 0 0 10 1 1 1 0 1 1 1 11 0 0 0 1 1 1 0 11 0 1 0 0 0 1 0 11 1 0 0 1 1 0 0 11 1 1 0 0 0 1 0

11、1所以 为永真式；推理 是()()prqp()()prqp正确的。（2）等值演算： ()()()()()()()11(rpqrprpqrrprqr)()1rqp（3）主析取范式 01234567()()()()()()()()().mrqpprrqppqrpqrpqrm12、填充下面推理证明中没有写出的推理规则。前提： ，()pqr()rs结论： s证明： 附加前提引入 化简p 化简q 前提引入()r 假言推理 假言推理r 前提引入()qs 假言推理 假言推理s14、在自然推理系统 P 中构造下面推理的证明：（2）前提： ,(),pqr结论：证明： 前提引入()r 置换q 前提引入 析取三段论 前提引入p 拒取式（4）前提： ,qstr结论： 证明： 前提引入tr 化简 化简 前提引入st 置换()()s 化简t 前提引入q 置换()()sq