离散数学第二章练习题答案

1、一、选择题1 .下列四个公式正确的是 /x(A(x)八 B(x) = VxA(x)八 xB(x)/x(A(x)¥ B(x) = VxA(x) vVxB(x) 3x(A(x) mB(x) n 3xA(x) v3xB(x)三xA(x)八三xB(x)= 3x(A(x) A B(x)A.B.C.D.2 .谓词公式Vx(P(x)v三yR(y)-> Q(x)中量词7x的辖域是()(A) -x(P(x) yR(y) (B) P(x) (C) P(x) yR(y) (D) Q(x)3 .谓词公式 VxP(x)T (Ux-Q(x)T -3xQ(x)的类型是()(A)永真式(B)矛盾式(C)非永真

2、式的可满足式(D)蕴涵式4 .设个体域为整数集，下列公式中其真值为1的是()(A) -xTy(x y = 0)(B) -iy_x(x y = 0)(C) -x-y(x y =0)(D) - x y(x y = 0)5 .设个体域A=a,b,公式VxP(x)a3xS(x)在中消去量词后应为()(A)P(x)S(x)(B) P(a)P(b)(S(a) S(b)(C)P(a)S(b)(D) P(a)P(b)S(a) S(b)6 .在谓词演算中，下列各式正确的是()(A) Tx-yA(x, y)二 -yTxA(x,y)(B) TxTyA(x, y) = yTxA(x, y)(C) TxyA(x, y)

3、 = "x yA(x, y)(D) -xyA(x, y)：= _y_xA(x,y)7 .下列各式不正确的是()(A) -x(P(x) Q(x)= -xP(x) -xQ(x)(B) -x(P(x) Q(x)= -xP(x) -xQ(x)(C) x(P(x) Q(x)：= xP(x) xQ(x)(D) - x(P(x) Q)= -xP(x) QP(a,a) P(a,b) P(b,a) P(b,b)8 .设I是如下一个解释：D = a,b,101则在解释I下取真值为1的公式是().(A) x-yP(x,y) (B) -x-yP(x,y)(C) -xP(x,x)(D)-x-lyP(x,y).

4、9 .设个体变元x, y, z的论域都为自然数集合，P(x, y, z): x + y = z,A. AxP(x, 0, x)C VxzyQ(y, x,x)10.下面不是命题的是()A. VxP(x)C. (Vx)P(x) vP( y)B. 3xVyP(x, y, y)D. VxR(x,0)B.(三x)P(x)D.(三x)(三y)(P(x)T R(y)Q(x, y,z)： x y =z, R(x, y): x < y ,则以下命题中()是假命题11公式(Vx)P(x)T (Vx)Q(x)的前束范式为()A. (Vx)(Vy)(P(x)-> Q(y)C.(三x)(Vy)(P(x)T

5、Q(y)12.公式(/x)(P(x)H Q)u ()A. (X/x)P(x)T Q)a(Qt (Vx)P(x)C( x)P(x) > Q) (Q > (-x)P(x)B. (Vx)仁y)(P(x)T Q(y)D.(三x)(三y)(P(x)T Q(y)B. (Vx)P(x)T Q)a(Qt (5x)P(x)D.(三x)P(x)T Q)八(Qt (3x)P(x)13.(Vx)(By)P(x, y)的否定是(-x)(-y)-P(x, y)B .仁x)(Vy)P(x,y)C.Cx)( y)-P(x, y)D.(三x)(三y)P(x, y)14 .下列谓词公式与(Vx)(A(x) 】B(x)

6、等价的是()A. (Vx)A(x) (Vx)B(x)B. (Vx)A(x) (Vx)B(x)C.(三x)A(x) J(三x)B(x)D,(三x)A(x)(三x)B(x)15 .在谓词演算中，P(a)是VxP(x)的有效结论，其理论依据是()A. USB. UGC. ESD. EG16 .设个体域是整数集合，P代表vxVy(x<y)-» (x-y<x),下面4个命题中为真的是()(A) P是真命题(B) P是假命题(C) P是一阶逻辑公式，但不是命题(D) P不是一阶逻辑公式二、填空题1 .设全体域D是正整数集合，确定下列命题的真值：(1) x y(xy=y) (0)(2)

7、x-y(x+y = y)(0)(3)Tx-y(x+y =x) (0)(4)-xTy(y = 2x)(1)2 .谓词公式(寸x)(P(x, y) vQ(z)八(三y)(R(x, y)T (Vz)Q(z)中量词Vx的辖域是 3 .公式(7x)(P(x)t Q(x, y)(三z)R(y,z)T S(x)中量的自由变量为x,y 约束变量为x,z 4 .设个体域 D = 1,2,那么谓词公式 三xA(x) vVyB(y)消去量词后的等值式为 . A(1) A(2) (B(1) B(2) .5 .设个体域D=a,b,公式Vx(G(x)t 力H(x,y)消去量词化为 . (G(a)- (H(a,a) H(a

8、,b) (G(b) >(H(b,a) H(b,b) 6 .设N(x)： x是自然数，Z(y); y是整数，则命题 每个自然数都是整数，而有些整数不是自然数”符号化为 Vx(N(x)T Z(x)八三x(Z(x) AN(x)7 .谓词公式Vx(F(x尸G(x)yrZy(F(y尸G(y )的类型是 永假式.8 .设个体域1,2,谓词 P(1)=1,P(2)=0 , Q(1)=0, Q(2)=1 ,则 Vx(P(x)1Q(x)的真值是9 .只用联结词 7V,T表示以下公式(x)(P(x) Q(x) =-( -x ) (P (x ) > Q (x_J(x)(P(x) (-y)Q(y) =-(

9、 -x)(P x )> 一(y Q y ) 一®Q)y(，)P»(-y)(-x)P(x) Q(y)=(-y)(Q(y) >x)P(x)三、计算及证明1 .求谓词公式 "Pt Q(x) AR(f (a)的真值.其中 P： 4>3, Q (x)： x>1, R (x)： xM.f (4)=1, f (1) =5, f =3. a： 5.个体域D=(当，1, 5).解：-x(P > Q(x) R(f(a)=(P > Q(-3) (P > Q(1) (P > Q(5) R(f(5)=(1 > 0) (1 > 0)

10、 (1 > 1) R(-3)=0011=02 .说明公式 寸xP(x)t (三yG(x, y)T VxP(x)是逻辑有效式(永真式).解：因为 VxP(x)t (三yG(x, y)T VxP(x)是 Pt (Qt P)的代换实例, 可知 VxP(x)t (三yG(x, y)T VxP(x)是逻辑有效式.或 -xP(x) (- yG(x, y) -xP(x):= _ xP(x) . -JyG(x, y) P(x)：= 13 .通过等值演算说明下列等值式成立：-ix(P(x) Q(x)- xP(x)- -xQ(x)证：x(P(x) Q(x)：= x( P(x) Q(x)=x P(x) . T

11、xQ(x)= _ xP(x) -JxQ(x):="xP(x)二xQ(x)4 .求谓词公式(寸xF(x, y)T VyG(x, y)八三zH(x,y,z)的前束范式解：(-xF(x, y) . yG(x, y)3二izH (x, y, z)二( - xF(x,y) - yG(x,y) zH (x, y, z) =(u-F(u,y) -vG (x, v) TzH (x, y, z)= u(F(u, y) -vG(x,v)二izH(x, y,z)=u-v z(-F(u,y) G(x,v) H(x,y,z)(或u 三u/v攵(F(u, y)T G(x,v) aH (x, y,z)5 .前提：水F(x), Ux(F(x)tG(x)八H(x)结论：x(F (x) H(x)6 .构造推理证明三xP(x)T VxQ(x)= Vx(P(x)T Q(x).(提示:-xA(x) -xB(x)= -x(A(x) B(x).)证 次P(x)t VxQ(x) xP(x) - xQ(x) -x_P(x) -x