《数理逻辑》期末考试试题

1、(A卷)()中山大学授予学士学位工作细则 考试作弊不授予学士学位。年级：2008级班级：A,B,C,E班(共202分)1. 设A是含命题变量p q rA(p q)2. 设公式A含变量p q rM M M Mr)的类型是矛盾式。m。mmm23514673. 设F(x)表x是实数G(x)表x是有理数”，则命题“实数不都是有理数”符号化为x(F(x)G(x)。4. 公式xF(x)yG(x y)的前束范式是xy(F(x)G(z y)。5.6. 设F(x)xG(x)x x(F(x)G(x)7. 设p r为真命题，q s(p8. 求与公式F = x(A(x) B(x y)xtz(A(x) B(x y) (

2、C(t)D(y z)9. 令L(x)表示x是人，E(x)表示x是食物，F(x y)表示x对y公式(pq)r的主析取范式是m m m m m13567。q) (rs)的真值为0。(yC(y) zD(y z)等值的一个前束范式是：。xy(L(x)E(y)F(x y)。10. 公式(yG(x)xF(x)yG(y)xF(x)的类型是永真式。(8分)(1) 请指出公式x(P(x)xQ(x)(xH(x) G(x)中各量词的辖域；解答：第一个量词x的辖域是(P(x)(x)Q(x)x的辖域是Q(x)，第二个量词x的辖域是P(x。(2) 请给出公式y(A(x y)xB(x y) zC(x y z)中每个变量符号

3、的出现身份，即是指导变元、还是自由出现或约束出现。解答y中的y是指导变元，A(x y)中的y是约束出现，而x是自由出现，x中的x是指导变元，而B(x y)中的x和y都是约束出现，z中的zC(x y z)中的zx和y都是自由出现。(3) 请指出变量x和y分别是公式x(A(x y)变量；B(y z)yxC(x y z)的自由变量还是约束解答xy是该公式的自由变量。(4) 请使用约束变量改名规则或自由变量替换规则将公式x(A(x y)yB(y z)yC(x y z)变换成语法等价但所有量词的指导变元不同，且没有变量符号既自由出现又约束出现的公式形式。注意，请依次选择个体变量符号x y z u v w

4、 r s t等等。解答x(A(x y)uB(u z)vC(w v z)(16分)1(1) 给定解释I = 2 4P(x)为真当且仅当x是素数，D(x y)为真当且仅当x可整除yE(x y)为真当且仅当x+y = xyxy(P(x)D(x y)E(x y)在解释I下的真值。解答1.(2) 给定解释I fE(x y)的解释是x = y，请给出公式xyE(f(x y) y)的直观含义，并根据常识确定其真值。解答：该公式的直观含义是：存在一个整数和任意另一整数的和都等于另一整数，其真值为1，因为对任意的整数xx+0 = 。(3) 给定论域 = a bxy(P(x y)P(y x)中的量词。解答：xy(

5、P(x y)P(y x)P(y a)y(P(b y) y(P(a y)P(y b) (P(a a)(P(b a)P(a a)(P(a b)P(a b)(P(b b)P(b a) P(b b)(4) 利用一阶逻辑的基本等值式证明x(F(x)G(x) (xG(x)xF(x)；证明(xG(x)xF(x) (xG(x)xF(x) xG(x)xF(x)/ 蕴涵等值式/ 德摩根律 xG(x)xF(x)/ 量词否定等值式/ 量词分配等值式 x(F(x)G(x)四、求解下面有关一阶逻辑公式自然推理的题目。注意下列题目中必须写出详细的证明序列，并注明所使用的自然推理规则。(38分)(1) 待验证的推理是：x(A

6、(x)B(x) xA(x)xB(x)，请指出下面证明序列中的错误，(6分)(1) x(A(x)B(x)B(a)/ 前提引入(2) A(a)/ (1)全称量词消除/ 附加前提引入(3) xA(x)(4) A(a)/ (3)存在量词消除/ (2),(4)蕴涵消除/ (5)存在量词引入/ (3),(6)附加前提证明法(5) B(a)(6) xB(x)(7) xA(x)xB(x)解答(3)步到第(4)步使用存在量词消除规则错误，常量符号a已经在前面的证明序列出2现过，正确的证明序列如下：(1) xA(x)(2) A(a)/ 附加前提引入/ (1)存在量词消除/ 前提引入(3) x(A(x)B(x)B(

7、a)(4) A(a)/ (3)全称量词消除/ (2),(4)蕴涵消除/ (5)存在量词引入/ (3),(6)附加前提证明法(5) B(a)(6) xB(x)(7) xA(x)xB(x)(2) 在一阶逻辑中验证推理：(10分)xP(x) x(P(x)Q(x)R(x) xP(x) xQ(x) xy(R(x)R(y)证明(1) xP(x)(2) xP(x)x(P(x)Q(x)R(x)/ 前提引入/ 前提引入(3) x(P(x)Q(x)(4) P(a)R(x)/ (1),(2)蕴涵消除/ (2)存在量词消除/ 附加律(5) P(a)Q(a)(6) P(a)Q(a)(7) R(a)R(a)/ (3)全称

8、量词消除/ (5),(6)蕴涵消除/ 前提引入(8) xQ(x)(9) Q(b)/ (8)存在量词消除/ 附加律(10) P(b)Q(b)(11) P(b)Q(b)(12) R(b)R(b)/ (3)全称量词消除/ (10),(11)蕴涵消除/ (7),(12)合取引入/ (13)存在量词引入/ (14)存在量词引入(13) R(a)R(b)(14) y(R(a)R(y)(15) xy(R(x)R(y)(3) 在一阶逻辑中验证推理：x(C(x)D(x) x(B(x)C(x) x(D(x)B(x)(10分)3证明(1) x(C(x)D(x)D(y)/ 前提引入(2) C(y)/ (1)全称量词消

9、除/ 前提引入(3) x(B(x)C(x)(4) B(y)C(y)(5) D(y)/ (3)全称量词消除/ 附加前提引入/ (2),(5)拒取式(6) C(y)(7) B(y)/ (4),(6)析取三段论/ (5),(7)附加前提证明法/ (8)全称量词引入(8) D(y)B(y)B(x)(9) x(D(x)(4) 符号化下面的推理，并在一阶逻辑中验证其正确性：每一个自然数不是奇数就是偶数，自然数是偶数当且仅当它能被2整除，并不是所有的自然数都能被2整除，因此有的自然数是奇数。（提示：令个体域是自然数集合，Q(x)表示x是奇数，P(x)表示x是偶数，R(x)表示x能被2整除）(12分)证明 首

10、先将前提和结论进行符号化，得到要验证的推理是：x(Q(x)P(x) x(P(x) R(x) xR(x) Q(x)而验证该推理的证明序列如下：(1) xR(x)/ 前提引入(2) xR(x)/ (1)量词否定等值式/ (2)存在量词消除/ 前提引入(3) R(c)(4) x(P(x) R(x)(5) P(c) R(c)/ (4)全称量词消除/ (5)等价消除(6) P(c)R(c)(7) P(c)/ (3),(6)拒取式/ 前提引入(8) x(Q(x)P(x)(9) Q(c)P(c)(10) Q(c)/ (8)全称量词消除/ (7),(9)析取三段论/ (10)存在量词引入(11) xQ(x)(

11、18分)(1) 在命题逻辑中证明等值式：(10分)(pq)(q r)(r p) (pq)(q r)(r p)4我们通过求左边公式的主合取范式，以及右边公式的主析取范式，再进行比较而证明：(pq)(q r)(r p)/ 极大项扩展/ 极大项编码 (pq r)(pqr)(pq r)(pq r) M M M M142(pq)(q r)(r p)/ 极小项扩展/ 极小项编码 (pq r)(pq r)(pq r)(pq r) m m m m7635由主析取范式和主合取范式之间的关系有M M M M m m m m1243567材的主范式编码稍有不同，因此有必要时可说明主范式的编码及主析取范式和主合取范式之间的关(2) 在命题逻辑中验证推理（可使用带前提集的证明序列