逻辑试题2006上末答案

1、2006年上学期逻辑导论期末考试系别 姓名 学号一、 把下列语句翻译为谓词逻辑的公式，设个体域为全域（20分）：1 北京大学是中国最好的大学。（要求：不把“最好”当性质）解：令U表示“中国的大学”，B表示“比好”，则该语句翻译为：U(a) x(U(x) xaB(a, x)2 有最小的自然数，但没有最大的自然数。解：N：自然数；R：；S：$x(N(x)y(N(y)R(x, y) $x(N(x)y(N(y)S(x, y)3 每个人都有唯一的母亲，但并非每位母亲都有唯一的子女。解：H：人；M(x, y)：x是y的母亲。 x(H(x)$y(M(y, x)z(M(z, x)zy)x($y(M(x, y)

2、z(M(x, z)zy)4有些学生尊敬所有的老师，所以，所有老师都有学生尊敬。 解：S：学生；T：老师；R：尊敬$x(S(x)y(T(y)R(x, y) x(T(x)$y(S(y)R(y, x)二、用一阶树形图判定下列公式或推理是不是普遍有效的（15分）：（1）x(F(x)G(x)xF(x)xG(x)解：(x(F(x)G(x)xF(x)xG(x) |x(F(x)G(x)(xF(x)xG(x) |xF(x) xG(x) |F(a)|G(b)|F(a)G(a) F(a) G(a) | F(b)G(b) F(b) G(b) 结论：图已经画完，有一个不闭的枝，因此，带否定号的公式可满足，原公式不是普遍

3、有效式。（2） ($xF(x)xG(x)x(F(x)$yH(y)G(x)解：($xF(x)xG(x)x(F(x)$yH(y)G(x) |($xF(x)xG(x) (x(F(x)$yH(y)G(x) |(F(a)$yH(y)G(a) |F(a)$yH(y) G(a)|F(a)$yH(y)| $xF(x) xG(x) | |F(a) G(a) 结论：图已经画完，所有的枝都是闭枝，因此，带否定号的公式不可满足，原公式是普遍有效式。（3） $x(A(x)y(B(y)C(x,y) /y(B(y)$x(A(x)C(x,y)解： $x(A(x)y(B(y)C(x,y) y(B(y)$x(A(x)C(x,y)

4、 |(B(a)$x(A(x)C(x, a) |B(a)$x(A(x)C(x, a)|A(b)y(B(y)C(b, y) |A(b)y(B(y)C(b, y) |B(a)C(b, a) B(a) C(b, a) | (A(b)C(b, a) A(b) C(b, a) 结论：图已经画完，所有的枝都是闭枝，因此，带否定号的公式不可满足，原公式是普遍有效式。三、分别构造一个相应的解释，证明（15分）：（1）$xF(x)$xG(x)$x(F(x)G(x)不是普遍有效的。解：个体域：N；F：偶数；G：奇数。$xF(x)表示“有的自然数是偶数”，真命题；$xG(x)表示“有的自然数是奇数”，真命题；因此，该

5、蕴涵式的前件是真命题；$x(F(x)G(x)表示“有的自然数既是偶数又是奇数”，假命题。整个蕴涵式前件真后件假，假命题。所以，该蕴涵式不是普遍有效的。（2）(xF(x)$xG(x)$x(F(x)G(x)是可满足的。解：个体域：N；F：偶数；G：奇数。xF(x)表示“所有自然数是偶数”，假命题；$xG(x)表示“有的自然数是奇数”，真命题；故$xG(x)是假命题；前件假后件假，故作为这个蕴涵式前件的那个蕴涵式是真命题；$x(F(x)G(x)表示“有的自然数并非既是偶数又是奇数”，真命题；真命题蕴涵真命题，整个蕴涵式是真命题；所以，该蕴涵式是可满足的。（3）x$yR(x, y)$yxR(x, y)

6、是可满足但不普遍有效的。解：（i）个体域：N；R：。x$yR(x, y)表示“所有自然数都大于等于有的自然数”，真命题；$yxR(x, y)表示“有的自然数（比如1），所有自然数都大于等于它”，真命题；真命题蕴涵真命题，真命题；所以，该蕴涵式是可满足的。（ii）个体域：N；R：。x$yR(x, y)表示“所有自然数都小于等于有的自然数”，即“没有最大的自然数”，真命题；$yxR(x, y)表示“有的自然数，所有自然数都小于等于它”，即“有最大的自然数”，假命题；真命题蕴涵假命题，假命题；所以，该蕴涵式不是普遍有效的。四、证明下列公式或推理是自然推理系统QN的定理（35分）：1$xF(x)$xG

7、(x)，x(R(x)F(x)，x(R(x)G(x) /$xR(x)（证明只能使用15个初始规则）证明：（1）$xF(x)$xG(x) 前提（2）x(R(x)F(x) 前提（3）x(R(x)G(x) 前提（4） $xF(x) 假设（5） F(a) (4) $（6） R(a)F(a) (2) （7） R(a) 假设（8） F(a) (6)(7)（9） F(a) (5) （10） R(a) (7)(8)(9) （11）$xF(x) R(a) (4)(10) （12）$xG(x) R(a) 同理可证 （13）R(a) (1)(11)(12) （14）$xR(x) (13) $2x(F(x)G(x)$y

8、(R(x, y)H(y)，$x(S(x)F(x)y(R(x, y) S(y)，x(S(x)G(x) /$x(S(x)H(x)证明：（1）x(F(x)G(x)$y(R(x, y)H(y) 前提（2）$x(S(x)F(x)y(R(x, y) S(y) 前提（3）x(S(x)G(x) 前提（4）(S(a)F(a)y(R(a, y) S(y) (2) $（5） S(a)F(a) (4) （6）y(R(a, y) S(y) (4) （7）S(a) (5) （8）F(a) (5) （9） S(a)G(a) (3) （10）G(a) (7)(9) （11）F(a)G(a) (7)(10) （12）F(a)G

9、(a)$y(R(a, y)H(y) (1) （13）$y(R(a, y)H(y) (11)(12) （14）R(a, b)H(b) (13) $（15）R(a,b) (14) （16）H(b) (14) （17）R(a,b) S(b) (6) （18）S(b) (15)(17) （19）S(b)H(b) (16)(18)（20）$x(S(x)H(x) (19) $3x(A(x)$y(A(y)B(x, y), $x(A(x)y(A(y)B(x, y)C(x, y) /$x$y(A(x)A(y)C(x, y)证明：（1）x(A(x)$y(A(y)B(x, y) 前提（2）$x(A(x)y(A(y)

10、B(x, y)C(x, y) 前提（3）A(a)y(A(y)B(a, y)C(a, y) (2) $（4）A(a) (3) （5） y(A(y)B(a, y)C(a, y) (3) （6）A(a)$y(A(y)B(a, y) (1) （7）$y(A(y)B(a, y) (4)(6) （8）A(b)B(a, b) (7) $（9） A(b)B(a, b)C(a, b) (5) （10）C(a,b) (8)(9) （11） A(b)A(b) 假设（12） C(a, b) (10) （13）A(b)A(b)C(a, b) (11)(12) （14）$y(A(a)A(y)C(a, y) (13) $（

11、15）$x$y(A(x)A(y)C(x, y) (14) $ 4 所有马都是动物，所以，所有马头都是动物头。翻译：x(M(x)A(x) /x($y(M(y)H(x, y)$y(A(y)H(x, y)证明：（1）x(M(x)A(x) 前提（2） $y(M(y)H(x, y) x, 假设（3） M(a)H(x, a) a x , (2) $（4） M(a) (3) （5） H(x, a) a x , (3) （6） M(a)A(a) (1) （7） A(a) (4)(6) （8） A(a)H(x, a) a x , (7)(5)（9） $y(A(y)H(x, y) x, (8) $（10）$y(M

12、(y)H(x, y)$y(A(y)H(x, y) (8)(9) （11）x($y(M(y)H(x, y)$y(A(y)H(x, y) (1) 上面是授课教师在课堂上讲授时的翻译，以及相应的证明方法。（第二版）教学辅导书第113页有下面的符号化：设个体域为全域，一元谓词M()表示“是马”，D()表示“是动物”，二元谓词H(, )表示“是头”，则上述命题可符号化为：x(M(x)D(x) /xy(M(x)H(y, x)D(x)H(y, x)从这个公式出发进行证明，如果证明无误，也算正确。（5）奉承拍马的人都不是正直的人。奉承拍马的人是不受人尊敬的。科学家都是正直的或受人尊敬的。因此，科学家都不是奉承

13、拍马的人。翻译：x(M(x)Z(x), x(M(x)R(x), x(S(x)Z(x)R(x) / x(S(x)M(x)证明：（1）x(M(x)Z(x) 前提（2）x(M(x)R(x) 前提（3）x(S(x)Z(x)R(x) 前提（4） S(x) x, 假设（5） M(x)Z(x) (1) （6） M(x)R(x) (2) （7） S(x)Z(x)R(x) (3) （8） M(x) x, 假设（9） Z(x) x, (5)(8)（10） R(x) x, (6)(8)（11） Z(x)R(x) x, (9)(10) （12） (Z(x)R(x) x, (12)QN定理（13） S(x) x, (7

14、)(12)QN定理（14） S(x) x, (4) （15） M(x) x, (8)(13)(14)（16）S(x)M(x) (4)(15) （17）x(S(x)M(x) (16)五、简述休谟对归纳推理的质疑（5分）。答：休谟认为，（1）归纳推理不能得到演绎的（或理性的）证成，因为归纳推理的结论所断定的内容超出了前提所断定的，其前提的真不能保证结论的真，归纳推理不是演绎有效的推理。（2）归纳推理也不能用它在实践上的成功来证成，因为后者也是在使用归纳推理，用归纳推理去证成归纳推理是循环论证，在逻辑上是不允许的。（3）归纳推理所依赖的“将来与过去一致”、“自然齐一律”、“因果律”等等没有客观基础，

15、它们只不过是人的习惯性的心理联想，“习惯是人生的伟大指南。”六、在一次魔术表演中，从七位魔术师G、H、K、L、N、P和Q中，选择六位上场表演，表演时分成两队：1队和2队。每一队有前、中、后三个位置，上场的魔术师恰好每人各占一个位置，魔术师的选择和位置安排必须符合下列条件（10分）：（1） 如果安排G或H上场，他们必须在前位；（2） 如果安排K上场，他必须在中位；（3） 如果安排L上场，他必须在1队；（4） P和K都不能与N在同一队；（5） P不能与Q在同一队；（6） 如果H在2队，则Q在1队的中位。1以下哪项列出的是2队上场表演可接受的安排？A前：H；中：P；后：K B前：H；中：L；后：NC前：G；中：Q；后：P D前：G；中：Q；后：NE前：K；中：Q；后：P2如果H在2 队，哪项列出的是1队可以接受的安排？