逻辑试题2006上末答案

2006年上学期《逻辑导论》期末考试系别姓名学号一、把下列语句翻译为谓词逻辑的公式，设个体域为全域（20分）：1．北京大学是中国最好的大学。（要求：不把“最好”当性质）解：令U表示“中国的大学”，B表示“…比…好”，则该语句翻译为：U(a)∧x(U(x)∧x≠aB(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)z＝y)))∧x(y(M(x,y)z(M(x,z)z＝y)))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()G()F()∨G()√F()G()×F()∨G()√F()G()×结论：图已经画完，有一个不闭的枝，因此，带否定号的公式可满足，原公式不是普遍有效式。（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()∧yH(y)G())√F()∧yH(y)√G()F()yH(y)xF(x)xG(x))F()G()××结论：图已经画完，所有的枝都是闭枝，因此，带否定号的公式不可满足，原公式是普遍有效式。（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)))√(B()x(A(x)∧C(x,)))√B()x(A(x)∧C(x,))A()∧y(B(y)C(,y))√A()y(B(y)C(,y))B()C(,)√B()C(,)))×(A()∧C(,))√A()C(,))××结论：图已经画完，所有的枝都是闭枝，因此，带否定号的公式不可满足，原公式是普遍有效式。三、分别构造一个相应的解释，证明（15分）：（1）xF(x)∧xG(x)x(F(x)∧G(x))不是普遍有效的。解：个体域：N；F：偶数；G：奇数。xF(x)表示“有的自然数是偶数”，真命题；xG(x)表示“有的自然数是奇数”，真命题；因此，该蕴涵式的前件是真命题；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)yxR(x,y)是可满足但不普遍有效的。解：（i）个体域：N；R：≥。xyR(x,y)表示“所有自然数都大于等于有的自然数”，真命题；yxR(x,y)表示“有的自然数（比如1），所有自然数都大于等于它”，真命题；真命题蕴涵真命题，真命题；所以，该蕴涵式是可满足的。（ii）个体域：N；R：≤。xyR(x,y)表示“所有自然数都小于等于有的自然数”，即“没有最大的自然数”，真命题；yxR(x,y)表示“有的自然数，所有自然数都小于等于它”，即“有最大的自然数”，假命题；真命题蕴涵假命题，假命题；所以，该蕴涵式不是普遍有效的。四、证明下列公式或推理是自然推理系统QN的定理（35分）：1．xF(x)∨xG(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()(4)－（6）R()F()(2)－（7）R()假设（8）F()(6)(7)－（9）F()(5)∈（10）R()(7)(8)(9)－（11）xF(x)R()(4)(10)＋（12）xG(x)R()同理可证（13）R()(1)(11)(12)∨－（14）xR(x)(13)＋2．x(F(x)∧G(x)y(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()∧F())∧y(R(,y)S(y))(2)－（5）S()∧F()(4)∧－（6）y(R(,y)S(y))(4)∧－（7）S()(5)∧－（8）F()(5)∧－（9）S()G()(3)－（10）G()(7)(9)－（11）F()∧G()(7)(10)∧＋（12）F()∧G()y(R(,y)∧H(y))(1)－（13）y(R(,y)∧H(y))(11)(12)－（14）R(,)∧H()(13)－（15）R(,)(14)∧－（16）H()(14)∧－（17）R(,)S()(6)－（18）S()(15)(17)－（19）S()∧H()(16)(18)∧＋（20）x(S(x)∧H(x))(19)＋3．x(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)∧B(x,y)C(x,y)))前提（3）A()∧y(A(y)∧B(,y)C(,y))(2)－（4）A()(3)∧－（5）y(A(y)∧B(,y)C(,y))(3)∧－（6）A()y(A(y)∧B(,y))(1)－（7）y(A(y)∧B(,y))(4)(6)－（8）A()∧B(,)(7)－（9）A()∧B(,)C(,)(5)－（10）C(,)(8)(9)－（11）A()∧A()假设（12）C(,)(10)∈（13）A()∧A()C(,)(11)(12)＋（14）y(A()∧A(y)C(,y))(13)＋（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()∧H(x,)x,(2)－（4）M()(3)∧－（5）H(x,)x,(3)∧－（6）M()A()(1)－（7）A()(4)(6)－（8）A()∧H(x,)x,(7)(5)∧＋（9）y(A(y)∧H(x,y))x,(8)＋（10）y(M(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))/∴xy(M(x)∧H(y,x)→D(x)∧H(y,x))从这个公式出发进行证明，如果证明无误，也算正确。（5）奉承拍马的人都不是正直的人。奉承拍马的人是不受人尊敬的。科学家都是正直的或受人尊敬的。因此，科学家都不是奉承拍马的人。翻译：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)(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）归纳推理所依赖的“将来与过去一致”、“自然齐一律”、“因果律”等等没有客观基础，它们只不过是人的习惯性的心理联想，“习惯是人生的伟大指南。”六、在一次魔术表演中，从七位魔术师——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；后：KB．前：H；中：L；后：NC．前：G；中：Q；后：PD．前：G；中：Q；后：NE．前：K；中：Q；后：P2．如果H在2队，哪项列出的是1队可以接受的安排？A．前：L；中：Q；后：NB．前：G；中：K；后：NC．前：L；中：Q；后：GD．前：G；中：K；后：LE．前：G；中：Q；后：K3．以下哪项列出的是1队上场表演可接受的安排？A．前：Q；中：L；后：NB．前：L；中：K；后：QC．前：Q；中：K；后：PD．前：G；中：K；后：PE．前：G；中：Q；后：P4．如果G在1队，以下哪一对魔