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