离散数学习题五

1、习题五1 .设个体域D=a,b,c,在D中消去公式x(F(x)yG(y)的量词。甲乙用了不同的演算过程：甲的演算过程如下：x(F(x)yG(y)x(F(x)(G(a)G(b)G(c)(F(a)(G(a)G(b)G(c)(F(b)(G(a)G(b)G(c)(F(c)(G(a)G(b)G(c)(F(a)F(b)F(c)(G(a)G(b)G(c)乙的演算过程如下：x(F(x)yG(y)xF(x)yG(y)(F(a)F(b)F(c)(G(a)G(b)G(c)显然，乙的演算过程简单，试指出乙在演算过程中的关键步骤。解：乙在演算中的关键步骤是，在演算开始就利用量词辖域收缩与扩等值式，将量词的辖域缩小,因而

2、演算简单。2 .设个体域D=a,b,c,消去下列各式的量词：(1) xy(F(x)G(y)(2) xy(F(x)G(y)(3) xF(x)yG(y)(4) (xF(x,y)yG(y)解：i)(F(a)F(b)F(c)(G(a)G(b)G(c)2)(F(a)F(b)F(c)(G(a)G(b)G(c)3)(F(a)F(b)F(c)(G(a)G(b)G(c)在(1)(2) (4)中均将量词的辖域缩小，所以演算结果都比较简单3.设个体域D=1,25请给出两种不同的解释Ii和12,使得下面公式在Ii下都是真命题,而在I2下都是假命题(1) x(F(x)G(x)(2) x(F(x)G(x)解：解释I1为：

3、个体为实数集合R,F(x):x为自然数，G(x):x为整数。在I1下，(1)为自然数都是整数，(2)为存在整数为自然数。他们都是真命题解释I2为：个体域仍为实数集RF(x):x是无理数，G(x):x能表示成分数，在I2下，(1)为无理数都能表示成分数，(2)为存在能表示成分数的无理数，他们都是假命题4 .给定公式AxF(x)xF(x)(1)在解释I1中，个体域D=a,证明公式A在I1下的真值为1.(2)在解释12中，个体域。2=印旦_L)an,n2,A在I2下的真值还一定是1吗？为什么？解：(1)在I1下，xF(x)xF(x)F(a)F(a)F(a)F(a)1在I2下xF(x)xF(x)(F(

4、aJF(a2)F(an)(F(aJFMF(an)为可满足式，设F(x):x为奇数，qi,i1,2,n,n2，此时，蕴涵式前件为真，后件为假，故蕴含式为假,若令F(x)；x为整数，则蕴含式前后件均为真，所以(2)中公式在I2下为可满足式5 .给定解释I如下：(a)个体域D=3,4;(b)f(x)为f(3)4,f3;(C)F(x,y)为F(3,3)F(4,4)0,F(3,4)F(4,3)1.试求下列公式在I下的真值(1) xyF(x,y)(2) xyF(x,y)(3) xyF(x,y)F(f(x),f(y)解：(1)xyF(x,y)x(F(x,3)F(x,4)(F(3,3)F(3,4)(F(4,3

5、)F(4,4)111(2)x(F(x,3)F(x,4)(F(3,3)F(3,4)(F(4,3)F(4,4)0(3) x(F(x,3)F(f(x),f(3)(F(x,4)F(f(x),f(4)(F(3,3)F(f(3),f(3)(F(3,4)F(f(3),f(4)(F(4,3)F(f(4),f(3)(F(4,4)F(f(4),f(4)16. 甲使用量词辖域收缩与扩等值式进行如下演算x(F(x)G(x,y)xF(x)G(x,y)乙说甲错了，乙说的对吗？为什么？解：乙说的对，甲错了，全称量词的指导变元x，辖域为(F(x)G(x,y)，其中F(x)与G(x,y)都是x的约束变元，因而不能讲量词的辖域变

6、小7. 请指出下面等值运算的两处错误xy(F(x)(G(y)H(x,y)xy(F(x)(G(y)H(x,y)xy(F(x)G(y)H(x,y)解：演算的第一步，应用量词辖域收缩与扩算值式时丢掉了否定连接词，演算的第二步，在不等值原错的基础上又用错了等值式(F(x)G(y)H(x,y)和(F(x)G(y)H(x,y)8 .在一阶逻辑中将下列命题符号化，要求用两种不同的等值形式(1)没有小于负数的正数(2)相等的两个角未必都是对顶角解：(1) x(F(x)G(x)x(G(x)F(x)其中F(x):x小于负数，G(x):x是正数(2) xy(F(x)F(y)H(x,y)L(x,y)xy(F(x)F(

7、y)H(x,y)L(x,y)其中F(x):x是角，H(x,y)x=y,L(x,y):x和y是对顶角9 .设个体域D为实数集合，命题“有的实数既是有理数又是无理数”，这显然是个假命题。可是某人却说这是真命题，其理由如下设F(x):x是有理数，G(x):x是无理数。xF(x),xG(x)都是真命题，于是，xF(x)xG(x)x(F(x)G(x)由于xF(x)xG(x)是真命题，故x(F(x)G(x)也是真命题，即有的实数是有理数，也是无理数这个人的结论对吗？为什么？解：存在量词对无分配律10 .在求前束式时有人说x(F(x)G(x,y)已是前束式，理由是量词已在公式的前面，他说的对吗？为什么？解：

8、在前束式中，否定联结词不能在量词前面出现11 .有人说无法求公式x(F(x)G(x)xG(x,y)的前束式，因为公式中的两个量词的指导变元相同。他的理由对吗？为什么？换名规则可以使两个指导变元不相同12 .求下列各式的前束式：(1)xF(x)yG(x,y)(2) x(F(x,y)yG(x, y,z)(3) xF(x,y)xG(x,y)(4) xi(F(x1)G(xi,x2)(x2H(x2)xsL(x2,x3)(5) xiF(xi,x2)(F(x1)X2G(xi,x2)解：(1) xy(F(x)G(z,y)(2) xt(F(x,t)G(x,t,z)(3) x1x2x3x4(F(x1,y)G(x2

9、,y)(G(x3,y)F(x4,y)y1y2y3(F(y1)G(y1,x2)(H(y2)L(x2,y3)(5) yiy2(F(yI,x2)(F(x1)G(xi,y2)13.将下列命题符号化，要求符号化的公式权威前束式：(1)有点火车比有的汽车跑的快(2)有的火车比所有的汽车跑的快(3)说有的火车比所有汽车跑得快是不对的(4)说有的飞机比有的汽车慢也是不对的解：(1) xy(F(x)G(y)H(x,y)其中F(x):x是汽车G(y):y是火车H(x,y):x比y跑得快(2) xy(F(x)(G(y)H(x,y)其中F(x):x是火车G(y):y是汽车H(x,y):x比y跑得快(3) xy(F(x

10、)G(y)H(x,y)其中F(x):x是火车G(y):y是汽车H(x,y):x比y跑得快H(x,y):x比y跑得慢14.在自然推理系统F中，指出下面各证明序列中的错误(1)F(x)xG(x)前提引入F(c)G(c)El规则(2) xF(x)yG(y)前提引入F(a)F(b)El规则(3) F(y)G(y)前提引入x(F(x)G(x)EG规则(4) F(a)F(b)前提引入x(F(x)G(x)EG规则(5) F(c)G(c)前提引入x(F(x)G(x)UGB则解：(1)对F(x)xG(x)不能使用EI规则，它不是前束式，首先化成前束式F(x)xG(x)x(F(y)G(x)，因为量词辖域(F(y)

11、G(x)中，除了x还有自由出现的y所以不能用EI规则(2)对xF(x)yG(y)也应该先化成前束式才能消去量词，其前束式为xy(F(x)G(y)，要消去量词，既要用UI规则，又要用EI规则(3)这里 A(y)=F(y) G(y) 满足要求(4)这里，使F(a)为真的a不一定使G(a)为真，同样的，使G(b)为真的b不一定使F(b)为真1)前提：xF(x)y(F(y)G(y)R(y),xF(x)结论：xR(x)2)前提：x(F(x)(G(a)R(x),xF(x)结论：x(F(x)R(x)3)前提：x(F(x)G(x),xG(x)结论：xF(x)4)前提：x(F(x)G(x),x(G(x)R(x)

12、,xR(x)结论：xF(x)1)证明：1xF(x)前提引入2xF(x)y(F(y)G(y)R(y)前提引入y(F(y)G(y)R(y)12假言推理35(F(c)G(c) R(c)3 UI6F(c)G(c)44F(c) 1 EI附加56假言推理7R(c)8xR(x)7EG弓I入全称量词(5)这里，c为个体常项，不能对F(c)G(c)15.在自然推理系统F中，构造下面推理的证明:6 R(y) 5UI前提引入2)证明：1xF(x)x(H(x),xF(x)x(F(x) (G(a)R(x)x(F(a)G(a),G(a)I(y)H(a)x(G(a)H(a)I(a)前提引入2xF(x)1置换3F(c)F(c)45 G(a)6 R(c)F(c)1EI(G(a)R(