数理逻辑练习题及答案-5

.一阶逻辑等值式与置换规则1 设个体域D=a,b,c，消去下列各式的量词：(1) xy(F(x)G(y)(2) xy(F(x)G(y)(3) xF(x)yG(y)(4) x(F(x,y)yG(y)2 设个体域D=1,2，请给出两种不同的解释I1和I2，使得下面公式在I1下都是真命题，而在I2下都是假命题。(1) x(F(x)G(x)(2) x(F(x)G(x)3 给定解释I如下：(a) 个体域D=3,4。(b) (x)为(3)=4，(4)=3。(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)4 构造下面推理的证明：(1) 前提：x(F(x)(G(a)R(x)，xF(x)结论：x(F(x)R(x)(2) 前提：x(F(x)G(x)，xG(x)结论：xF(x)(3) 前提：x(F(x)G(x)，x(G(x)R(x)，xR(x)结论：xF(x)5 证明下面推理：(1) 每个有理数都是实数，有的有理数是整数，因此有的实数是整数。(2) 有理数、无理数都是实数，虚数不是实数，因此虚数既不是有理数、也不是无理数。(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)14.(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)UG5.(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