数理逻辑练习题及答案-526164.pdf
一阶逻辑等值式与置换规则 1 设个体域 D=a,b,c，消去下列各式的量词：2 3 (1)xy(F(x)G(y)4 (2)xy(F(x)G(y)5 6 (3)xF(x)yG(y)7 8 (4)x(F(x,y)yG(y)9 设个体域 D=1,2，请给出两种不同的解释 I1和 I2，使得下面公式在 I1下都是真命题，而在 I2下都是假命题。10 11 (1)x(F(x)G(x)12 (2)x(F(x)G(x)13 给定解释 I 如下：14 15 (a)个体域 D=3,4。16 (b)(x)为(3)=4，(4)=3。17 (c)(x,y)为(3,3)=(4,4)=0，(3,4)=(4,3)=1。试求下列公式在 I 下的真值：(1)xyF(x,y)(2)xyF(x,y)(3)xy(F(x,y)F(f(x),f(y)18 构造下面推理的证明：19 20 (1)前提：x(F(x)(G(a)R(x)，xF(x)21 结论：x(F(x)R(x)22 23 (2)前提：x(F(x)G(x)，xG(x)24 结论：xF(x)25 26 (3)前提：x(F(x)G(x)，x(G(x)R(x)，xR(x)27 结论：xF(x)28 证明下面推理：29 30 (1)每个有理数都是实数，有的有理数是整数，因此有的实数是整数。31 32 (2)有理数、无理数都是实数，虚数不是实数，因此虚数既不是有理数、也不是无理数。33 34 (3)不存在能表示成分数的无理数，有理数都能表示成分数，因此有理数都不是无理数。答案 1.(1)xy(F(x)G(y)xF(x)yG(y)(F(a)F(b)F(c)(G(a)G(b)G(c)(2)xy(F(x)G(y)xF(x)yG(y)(F(a)F(b)F(c)(G(a)G(b)G(c)(3)xF(x)yG(y)(F(a)F(b)F(c)(G(a)G(b)G(c)(4)x(F(x,y)yG(y)xF(x,y)yG(y)(F(a,y)F(b,y)F(c,y)(G(a)G(b)G(c)2.(1)I1:F(x):x2,G(x):x3 F(1),F(2),G(1),G(2)均为真，所以 x(F(x)G(x)(F(1)G(1)(F(2)G(2)为真。I2:F(x)同 I1,G(x):x0 则 F(1),F(2)均为真，而 G(1),G(2)均为假，x(F(x)G(x)为假。(2)留给读者自己做。3.(1)xyF(x,y)(F(3,3)F(3,4)(F(4,3)F(4,4)(01)(10)1 (2)xyF(x,y)(F(3,3)F(3,4)(F(4,3)F(4,4)(01)(10)0 (3)xy(F(x,y)F(f(x),f(y)(F(3,3)F(f(3),f(3)(F(4,3)F(f(4),f(3)(F(3,4)F(f(3),f(4)(F(4,4)F(f(4),f(4)(00)(11)(11)(00)1 4.(1)证明:xF(x)前提引入 F(c)ES x(F(x)(G(a)(R(x)前提引入 F(c)(G(a)R(c)US G(a)R(c)假言推理 R(c)化简 F(c)R(c)合取 x(F(x)R(x)EG (2)证明：xG(x)前提引入 xG(x)置换 G(c)US x(F(x)G(x)前提引入 F(c)G(c)US F(c)析取三段论 xF(x)EG (3)证明：x(F(x)G(x)前提引入 F(y)G(y)US x(G(x)R(x)前提引入 G(y)R(y)US xR(x)前提引入 R(y)US G(y)析取三段论 F(y)析取三段论 xF(x)UG 5.(1)设 F(x):x 为有理数，R(x):x 为实数，G(x):x 是整数。前提：x(F(x)R(x)，x(F(x)G(x)结论：x(R(x)G(x)证明：x(F(x)G(x)前提引入 F(c)G(c)ES F(c)化简 G(c)化简 x(F(x)R(x)前提引入 F(c)R(c)US R(c)假言推理 R(c)G(c)合取 x(R(x)G(x)EG (2)设：F(x):x 为有理数，G(x):x 为无理数，R(x)为实数，H(x)为虚数 前提：x(F(x)G(x)R(x),x(H(x)R(x)结论：x(H(x)(F(x)G(x)证明：x(F(x)G(x)R(x)前提引入 F(y)G(y)R(y)US x(H(x)R(x)前提引入 H(y)R(y)US R(y)(F(y)G(y)置换 H(y)(F(y)G(y)假言三段论 H(y)(F(y)G(y)置换 x(H(x)(F(x)G(x)UG (3)设：F(x):x 能表示成分数，G(x):x 为无理数，H(x)为有理数 前提：x(G(x)F(x),x(H(x)F(x)结论：x(H(x)G(x)证明：x(H(x)F(x)前提引入 H(y)F(y)US x(G(x)F(x)前提引入 G(y)F(y)US F(y)G(y)置换 H(y)G(y)假言三段论 x(H(x)G(x)UG
