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

整理文档整理文档一阶逻辑等值式与置换规则1.设个体域D={a,b,c},消去下列各式的量词：(1)「x」y(F(x)AG(y))(2)-''x.-'y(F(x)VG(y))⑶中xF(x)yG(y)(4)1'x(F(x,y)八G(y)).设个体域D={1,2},请给出两种不同的解释Ii和I2,使得下面公式在Ii下都是真命题，而在I2下都是假命题。Vx(F(x)-G(x))3x(F(x)AG(x)).给定解释I如下：(a)个体域D={3,4}。(b)『(x)为『(3)=4,/(4)=3o(c)耳(x,y)为夕(3,3)=耳(4,4)=0,芹(3,4)二9(4,3)=1。试求下列公式在I下的真值：,xJyF(x,y)⑵」x「yF(x,y)3)VxVy(F(x,y)-F(f(x),f(y))).构造下面推理的证明：(1)前提：Vx(F(x)-(G(aR(x))),3xF(x)结论：3x(F(x)AR(x))(2)前提：Vx(F(x)VG(x)),n3xG(x)结论：」xF(x)(3)前提：Yx(F(x)VG(x)),Vx(nG(x)VnR(x)歹xR(x)结论：xF(x).证明下面推理：(1)每个有理数都是实数，有的有理数是整数，因此有的实数是整数。(2)有理数、无理数都是实数，虚数不是实数，因此虚数既不是有理数、也不是无理数。(3)不存在能表示成分数的无理数，有理数都能表示成分数，因此有理数都不是无理数。答案(1)，x」y(F(x)AG(y))OXFxF(x)A3yG(y)O(F(a)AF(b))AF(c))A(G(a)VG(b)VG(c))'x'y(F(x)VG(y))OYxF(x)VVyG(y)O(F(a)AF(b)AF(c))V(G(a)AG(b)AG(c))⑶VxF(x)与yG(y)O(F(a)AF(b)AF(c))一(G(aG(协AG(c))'x(F(x,y)-^G(y))—」xF(x,y)工yG(y)0(F(a,y)VF(b,y)VF(c,y)) 一(G(GKb)WG(c)).(1)Ii：F(x):x<2,G(x):x <3F(1),F(2),G(1),G(2曲为真，所以整理文档整理文档A(F(4,3) F(f⑷,A(F(4,3) F(f⑷,f(3)))整理文档Vx(F(x)一G(x))O(F(1)一G(1)八(F(2)一G(2))为真I2：F(x)同Ii,G(x):x <0则F(1),F(2曲为真，而G(1),G(2)均为假，飞x(F(x)一G(x))为假。(2)留给读者自己做。.(1)，x」yF(x,y)—(F(3,3)VF(3,4))A(F(4,3)VF(4,4))O(0V1)A(1V0)Ol⑵Jx'yF(x,y)—(F(3,3)AF(3,4))V(F(4,3)AF(4,4))—(0A1)V(1A0尸0⑶VxVy(F(x,y)-F(f(x),f(y)))O(F(3,3)一F(f(3),f(3)))A(F(3,4)A(F(4,4) -F(f(4),f(4)))0(0—0)八(1-1)A(1一1)A@书0)4.(1)证明：①3xF(x) 前提引入②F(c) ①ESVx(F(x) -(G(a)A(R(x))) 前提引入F(c)一(G(a)AR(c)) ④US⑤G(a)A R(c) ②④假言推理⑥R(c) ⑤化简⑦F(c)A R(c) ②⑥合取3x(F(x)AR(x)) ⑥EG证明：①q3xG(x) 前提引入②VX]G(x) ①置换③[G(c) ②US④Wx(F(x)VQ(x) 前提引入⑤⑤F(c)VG(c) ④US整理文档整理文档⑥F(c)⑥F(c)⑦3xF(x)⑥EG证明：①vx(F(x)VG(x))前提引入②F(y)VG(y)①US③ G(x)VnR(x))前提引入④[G(y)VnR(y)③us⑤VxR(x)前提引入⑥R(y)⑤us⑦nG(y)④⑥析取三段论⑧F(y)②⑦析取三段论⑨VxF(x)UG5.(1)设F(x):x为有理数，R(x):x为实数，G(x):x是整数前提： 可x(F(x)一R(x)户x(F(x)AG(x))结论： 3x(R(x)AG(x))整理文档整理文档证明：①mx(F(x)AG(x))前提引入①①ES②化简②化简前提引入⑤US③⑥假言推理④⑦合取⑧EG②F(c)AG(c)③F(c)G(c)Vx(F(x)-R(x))F(c)一R(c)R(c)R(c)AG(c)3x(R(x)AG(x))⑵设：F(x):x为有理数，G(x):x为无理数，R(x)为实数，H(x)为虚数前提： Vx((F(x)VG(x))一4x(Hl(x)一［R(x))结论： Vx(H(x)-(［F(x)AnG(x)))证明：①Vx((F(x)VG(x)一R(x)) 前提引入F(y)VG(y))一R(y) ①USVx(H(x)一［R(x)) 前提引入H(y)一IR(y) ③US1R(y)一］(F(y)VG(y)) ②置换

⑥H(y)一］(F(y)VG(y))④⑤假言三段论⑥H(y)一］(F(y)VG(y))④⑤假言三段论⑦H(y)一(［F(y)A「G(y))⑥置换⑧'x(H(x)-(「F(x)AnG(x)))⑦UG设：F(x):x能表示成分数，G(x):x为无理数，H(x)为有理数前提：Vx(G(x)一［F(x))x(H(x)-F(x))结论：Vx(H(x)一［G(x))证明：①Vx(H(x)一