第2章 谓词逻辑

习题2在一阶逻辑中将下面命题符号化。(1)所有的有理数均可表成分数。Q(x)：x可表成分数∀x(Q(x)→F(x))有的有理数是整数。Q(x)：x是有理数，Z(x)：x是整数∃x(Q(x)∧Z(x))2整除F(x)：x是偶数，G(x)：x能被2整除∀x(F(x)→G(x))存在着偶素数F(x)：x是偶数，G(x)：x是素数∃x(F(x)∧G(x))没有不犯错误的人M(x)：x是人，G(x)：x犯错误﹁∃x(M(x)∧﹁G(x))∀x(M(x)→G(x))（所有的人都犯错误）F(x)：x在北京工作，G(x)：x是北京人﹁∀x(F(x)→G(x))∃x(F(x)∧﹁G(x))（存在着在北京工作的非北京人）同课本p362.2.2(1)(7)可符号化为x(M(x)C(x))x(M(x)C(x))每列火车都比某些汽车快。T(x)：x是火车，B(x)：x是汽车，F(x,y)：x比y快。∀x(T(x)→∃y(B(y)∧F(x,y)))(9)T(x)：x是火车，B(x)：x是汽车，F(x,y)：x比y快。∃x(B(x)∧∀y(T(y)→F(y,x)))(1)x(F(x))yH(x,y)(2)xF(x)G(x,y)(3)xy(R(x,y)L(y,z))xH(x,y)∃yH(x,y)y是自由出现，∀x(F(x))中，x是指导变项，∀的辖域为F(x)，x是约束出现。∃xF(x)中，x为指导变项F(x)，xG(xy中，x,y都是自是自由出现。在xy(R(x,yLyz中，x,y为指导变项，量词的辖域为(R(x,yLyz))，x,y自由出现；在xH(x,y)中，x为指导变项H(x,y，x约束出现。给定解释N如下：个体域为自然数集合DND 中特定元素a0ND f(x,y)xyg(x,y)xyND F(xy)xy。N在解释N下，下面哪些公式为真？哪些公式为假？（1）F(f(x,y),g(x,y))解：f(x,y)=g(x,y) x+y=xy假（2）F(f(x,a),y)F(g(x,y),z)解：(f(x,a)=y)→(g(x,y)=z) x+a=y→xy=z x+0=y→xy=z x=y→xy=z假（3）xF(g(x,a),x)F(x,y)解：∀x(g(x,a)=x→x=y) ∀x(ax=x→x=y) ∀x(0=x→x=y) 假（4）xF(f(x,x),g(x,x))解：∃xf(x,x)=g(x,x) ∃x(x+x=xx) 真判断下列公式中哪些是逻辑有效式，哪些是矛盾式。(1)xF(x)xF(x)(2)xF(x)(xyG(x,y)xF(x))(3)xF(x)(xF(x)yG(y))(4) (F(x,y)R(x,y)(R(x,y))注：(4)(F(x,y)R(x,yR(x,y”解：(1)I是任意的解释，设其个体域为Dx0

D，F0

为假，则xF(x为xF(x)xF(x)xDxF(x)xF(x)均为真，所以xF(x)xF(x为真。由以上，原公式是逻辑有效的。原公式是命题公式p(qp)pppp1(重言式)，所以原公式是逻辑有效的。ppqppqppq1(重言式)，所以原公式是逻辑有效的。原公式是命题公式qq的代换实例，而且qqqqpqq0(矛盾式求下列公式的前束范式。(1)∀xF(x)∧∃xG(x)解：∀xF(x)∃xG(x)∀xF(x)∧∀xG(x) 量词否定等值式∃xP(x)∀xP(x)*)∀x(F(x)G(x)) ∀x(A(x)∧B(x))∀xB(x)*)3(2) (xP(x)yQ(y))xR(x)解：(xP(x)yQ(y))xR(x)x(P(x)yQ(y))zR(z)((A(x)∨B)(∀xA(x)∨B))xy(P(x)Q(y))zR(z)((A(x)∨B)(∃x)x(y(P(x)Q(y))zR(z))((A(x)→B)(∀xA(x)→B))xy((P(x)Q(y))zR(z)) ((A(x)→B)(∃xA(x)→B))xyz((P(x)Q(y))R(z)) ((B→A(x))(B→∀xA(x)) )构造下面定理的证明：x(F(xH(xx(G(x)H(x))x(G(x)F(x))证明：∃x(F(x)∧H(x))∀x(F(x)∧H(x))∀x(F(x)∨H(x))∀x(H(x)F(x))(1)∃x(F(x)∧H(x))前提引入(2)∀x(H(x)F(x)) (1)置换(3)F(y) (2)UI(4)∀x(G(x)H(x)) 前提引入(5)G(y)H(y) (4)UI(6)F(y) (3)(5)假言三段论(7)∀x(G(x)F(x)) (6)UG“”证明：令F(x)：x是鸟，G(x)：x会飞，M(x)：x是麻雀，前提：∀x(F(x)G(x))，∀x(M(x)F(x))结论：∀x(M(x)G(x))推演：∀x(F(x)G(x)) 前提引入∀x(M(x)F(x)) 前提引入(3)F(x)G(x) (1)UI(4)(2)UI(5)M(x)G(x) (3)(4)假言三段论(4)∀x(M(x)G(x)) (5)UG)公x((A(x)B(y，x))zC(y，z))D(x)中，自由变元( )，约束变元( 。辖域中的，D(xx辖域中的，辖域中的z设个体域为整数集，则下列公式的类型( (1) xy(x+y=0)(2)yx(x+y=0)“类型”改为“真值”解：1，0设全体域D(1)xy(xy=y) (2)xy(x+y=y)(3)xy(x+y=x) (4)xy(y=2x)解：0,0,0,1设谓词是奇数是偶数，谓词公式x(P(x)在哪个个体域中?( )(1)自然数 (2)实数 (3)复数 (4))立解：选复数，它是奇数或偶数。谓词公式x(P(x)yR(y))中量词x的辖域是（ 解：P(x)yR(y)令是实数是有理数。则命题“并非每个实数都是有理数”的符号化表为（ 。解：﹁Q(x)符号化下列命题，并给出构造推理证明：每个自然数不是奇数就是偶数，自然数是偶数当且仅当它能被2整除，并不是所有自然2解：令N2前提：(N)O(xE(x)，(N)→(E(x)F(x)﹁(NF(x))结论：x(N(x)∧O(x))证明：(1)﹁x(N(x)→F(x))前提引入﹁) 置换(3)F(a) (2)EI(4) (E(x)F(x))) 前提引入(5)N(a)→(E(a)F(a)) (4)UIN(a) ﹁F(a) 化简规则(8)E(a)F(a) (9)

(F()

E(a)) (10)(11)E(a) )取式规则(12) 前提引(13)NO(a∨E(a) (12)UI5(14)O(a)∨E(a) (6)(13)假言推理(15)O(a) 析取三段论(16)N(a)∧O(a) (6)(15)合取(17)) (16)EG未曾失败过，所以有些人不怕困难。注：该题应放第1章命题逻辑中。解：设PQ)∧(QQ)Q)P显然是重言式，所以推理是有效的。功。张有为是科学工作者并且是聪明的，所以，张有为在他的事