数理逻辑习题部分解答.doc

一、命题逻辑3将下列命题符号化。（3）如果公用事业费用增加或者增加基金的要求被否定，那么当且仅当现有计算机设不适用的时候，才需购买一台新计算机；（5）虽然天气很好，老王还是不来；（7）停机的原因在于语法错误或程序错误；解：（3）设P：公用事业费用增加； Q：要求增加基金； R：现有计算机设备适用； S：购买一台计算机；则命题可符号化为：。（5）设P：天气很好；Q：老王来；则命题可符号化为：。（7）设P：停机的原因在于语法错误； Q：停机的原因在于程序错误。则命题可符号化为：。4设命题P：这个材料很有趣；Q：这些习题很难；R：这门课程使人喜欢。将下列句子符号化。（4）这个材料很有趣意味着这些习题很难，反之亦然；（5）或者这个材料很有趣，或者这些习题很难，并且两者恰具其一。解：（4） （5）或者12用基本等价公式的转换方法验证下述论断是否有效。（1）PQ,RS,QPS；（2）(PQ),QR,QP；（3）P,QR,RSQS。解：（1）（2）（3） 14符号化下列论断，并用演绎法验证论断是否正确。（1）有红、黄、蓝、白四队参加足球联赛。如果红队第三，则当黄队第二时，蓝队第四；或者白对不是第一，或者红队第三；事实上，黄队第二。因此，如果白队第一，那么蓝队第四；证明：设P：红队第三；Q：黄队第二；R：蓝队第四；S：白队第一。 则上述句子可符号为：， PP（附加前提）T，IPT，IPT，ICP，（2）如果6是偶数，则2不能整除7；或者5不是素数，或者2整除7；5是素数。因此，6是奇数；证明：设P：6是偶数；Q：2整除7；R：5是素数 则上述句子可符号化为： ， P（附加前提）T，EPT，IPT，IPT，I（3）若今天是星期二，那么我要考计算机科学或经济学；若经济学教授病了，就不考经济学；今天是星期二，并且经济学教授病了。所以，我要考计算机科学；证明：设P：今天是星期二；Q：我要考计算机科学；R：我要考经济学；S：经济学教授病了。 则上述句子可符号化为：，PT，IPT, ,IPT, ,IT, ,IT, ,I二、谓词逻辑1 用谓词和量词，将下列命题符号化。（4）会叫的狗未必会咬人；（5）每个人的外祖母都是他母亲的母亲；（6）任何金属均可溶解于某种液体之中；解：（4）设：D(x)：x是会叫的狗，R(x)：x是会咬人的狗。则上述句子可符号化为：（5）设H(x)：x是人，G(x,y)：x是y的外祖母，M(x,y)：x是y的母亲。则上述句子可符号化为：（6）设：P(x)：x是液体，G(x)：x是金属，R(x,y)：x溶解y。则上述句子可符号化为：8求下述公式的前束范式和Skolem范式。（1）(y) (P(x)($y)Q(x, y)；（3）($x) P(x,y)(z)Q(z)；（5）($y)(x)(z)($u)(v)P(x, y, z, u, v)。解：（1）求前束范式求Skolem范式（3）求前束范式求Skolem范式11指出下列推导中的错误，并加以改正。（1） (x)P(x)Q(x) P P(y)Q(y) US,解：，在第步中的量词(x)就辖域为P(x)，而非P(x)Q(x)，所以消去量词时，不能直接使用US规则。正确的推导可为： (x)(P(x)Q(x) P P(y)Q(y) US,（2） P(x)Q(c) P ($x)(P(x)Q(x) EG,解：在第步中x是以自由变元的身份出现，所以在对个体常量加入量词时，该量词的变元符号不能在原公式中以自由变元的身份出现。正确的推导可为： P(x)Q(c) P ($y)(P(x)Q(y) EG,（3） (x)($y)(xy) P ($y)(zy) S, (zc) ES, (x)(xc) G, cc US,解：由于在第步中含有自由变元符号z，所以在消去量词($y)时，应选的常量符号为含有z作为下标的常量符号。正确的推导可为： (x)($y)(xy) P ($y)(zy) S, (z) ES,（4） (x)($y)(xy) P ($y)(zy) US, (zcZ) ES, (x)(xx) UG,解：在第步中，常量符号中的z是一个下标符号，因此，不能对下标z使用UG规则。正确的推导可为： (x)($y)(xy) P ($y)(zy) US, (zcZ) ES,12将下列命题符号化，并用演绎法证明其论证是否正确。（1）每一个大学生，不是文科学生，就是理工科学生；有的大学生是优等生；小张不是文科生，但他是优等生。因而，如果小张是大学生，他就是理工科学生；（2）伟大的物理学家都具有广博的知识；新闻记者具有广博的知识。所以新闻记者是伟大的物理学家；（3）不存在白色的乌鸦；北京鸭是白色的。因此，北京鸭不是乌鸦；（4）所有的有理数都是实数；所有的无理数也是实数；虚数不是实数。因此，虚数即不是有理数也不是无理数；解：（1）设P(x)：x是一个大学生；Q(x)：x是文科生；S(x)：x是理科生；T(x)：x是优等生；c：小张；则上述句子可符号为：，PPUS，P(附加前提)T，IT，IT，ICP，（2）设P(x)：x是伟大的物理学家；Q(x)：x是新闻工作者；S(x)：x具有广博的知识；则上述句子可符号化为：，PPUS，US，上述公式无法推出，即无法推出。所以，此论证并非是正确的。（3）设W(x)：x是白色的；Q(x)：x是乌鸦；R(x)：x是北京鸭；则上述句