离散数学(下)单元测试(二).doc

离散数学(下)单元测试（二）一、选择题（在每个小题四个备选答案中选出一个正确答案，填在题末括号里）1. 谓词公式x(P(x)$yR(y)Q(x)中量词x的作用域是（C）A. x(P(x)$yR(y)B.P(x)C. (P(x)$yR(y)D.P(x)，Q(x)2. 谓词公式x(P(x)$yR(y)Q(x)中变元x是（D ）A.自由变量B.约束变量C.既不是自由变量也不是约束变量D.既是自由变量也是约束变量3. 若个体域为整数域，下列公式中哪个值为真？（ A ）A.x$y(x+y=0)B.$yx(x+y=0)C.xy(x+y=0)D.$x$y(x+y=0)4. 设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式$x(P(x)Q(x)在下面哪个个体域中是可满足的？（ D ）A.自然数集B.整数集C.实数集D.以上均不成立5. 设C(x)：x是运动员，G(x)：x是强壮的。命题“没有一个运动员不是强壮的”可符号化为（C）A.x(C(x)G(x)B.x(C(x)G(x)C.$x(C(x)G(x)D.$x(C(x)G(x)6. 设A(x)：x是人，B(x)：x犯错误，命题“没有不犯错误的人”符号化为（D）A.x(A(x)B(x)B.$x(A(x)B(x)C.$x(A(x)B(x)D.$x(A(x)B(x)7. 设Z(x)：x是整数，N(x)：x是负数，S(x,y)：y是x的平方，则“任何整数的平方非负”可表示为下述谓词公式（A） x (Z(x) $y (N(y) S(x,y)A.xy(Z(x)S(x,y)N(y)B.x$y(Z(x)S(x,y)N(y)C.xy(Z(x)S(x,y)N(y)D.x(Z(x)S(x,y)N(y)8. 令F(x)：x是火车，G(y)：y是汽车，H(x,y)：x比y快。则语句“某些汽车比所有的火车慢”可表示为（B）A.$y(G(y)x(F(x)H(x,y)B.$y(G(y)x(F(x)H(x,y)C.x$y(G(y)(F(x)H(x,y)D.$y(G(y)x(F(x)H(x,y)9. 在谓词演算中，下列各式哪个是正确的？（B，D）A.$xyA(x,y)y$xA(x,y)B.$x$yA(x,y)$y$xA(x,y)C.$xyA(x,y)x$yA(x,y)D.xyA(x,y)yxA(x,y)10. 下列各式哪个不正确？（A ）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.xP(x)Q)xP(x)Q11. 下面谓词公式哪个是前束范式？（A）A.xy$z(B(x,y)A(z)B.x$yB(x,y)C.$xyx(A(x,y)B(x,y)D.x(A(x,y)$yB(y)二、填空题1 设D=a，b，公式xyA(x，y)消去量词后等价于 (A(a，a)A(a，b) (A(b，a) A(b，b)。2 设个体域为A=a,b,c，消去公式xP(x)$xQ(x)中的量词公式等价于_ (P(a) P(b) P(c) ( Q(a) Q(b) Q(c)。3设解释T为：个体域为D-2,3,6，谓词F(x)：x3，G(x)：x5，R(x)：x7根据解释T，则公式x(R(x)F(x)G(5)的真值为_0_。4. 令R(x)：x是实数，Q(x)：x是有理数。(1) 命题“并非每个实数都是有理数”。其符号化为x(R(x) Q(x)或$x(R(x) Q(x)。(2) 命题“虽然有些实数是有理数，但并非一切实数都是有理数”。则其符号化可表示为 $x(R(x) Q(x) x(R(x) Q(x) 。5.设G(x)：x是金子，F(x)：x是闪光的，则命题“金子是闪光的，但闪光的不一定是金子”符号化为 x(G(x) F(x) x(F(x) G(x) 。6.设C(x)：x是计算机，P(x,y)：x能做y，I(x)：x是智能工作，则命题“并非所有智能工作都能由计算机来做”符号化为 y(I(y)$x(C(x) P(x,y)或 $y(I(y) x(C(x) P(x,y) 。7. 设Q(x)：x是偶数，P(x)：x是素数，则命题“存在惟一一个偶素数”可符号化为 $x(P(x) Q(x) y(P(y) Q(y) (y=x) ，“至多存在一个偶素数”可符号化为 xy(P(x) Q(x) P(y) Q(y) (y=x) 。8.设Q(x)：x是奇数，Z(x)：x是整数，则语句“不是所有整数都是奇数”所对应的谓词公式为（Z(x) Q(x)）。9.设个体域为自然数集，P(x)：x是奇数，Q(x)：x是偶数，则命题“不存在既是奇数又是偶数的自然数”可符号化为$x(P(x) Q(x) 。10.设个体域为全总个体域，R(x)：x是实数，Q(x)：x是有理数，Z(x)：x是整数，则命题“所有的有理数是实数”，“有些有理数是整数”，“有些有理数是实数担不是整数”符号化分别为 x（Q (x) R (x)）， $ x（Q (x) Z (x) ) ， $ x（Q (x) Z (x) )。11.xy(P(x,y)Q(y,z)$xP(x,y)中x的辖域为 y(P(x,y)Q(y,z) ，y的辖域为 (P(x,y)Q(y,z) ，$x的辖域为 P(x,y) 。9. 公式x(P(x)Q(x,y)$ y R(y,z)S(x)中自由变量为 x,y,z ，约束变量为 x,y 。10. 取个体域为整数集，给定下列公式：(1).x$y(xy=0)(2).x$y(xy=1)(3)$x$y(xy=2)(4)xy$z(x-y=z)(5).x-y=-y+x(6).xy(xy=y)(7)x(xy=x) 不是命题 (8).$xy(x+y=2y)上面公式中，真命题的有 (1) (3)(4) (5) ,假命题的有 (2)(6)(8) 。*11.下列谓词公式(1).($xA(x)与xA(x)(2).x(A(x)B(x)与xA(x)xB(x)(3).x(A(x)B(x)与xA(x)xB(x)(4).$xyD(x,y)与y$xD(x,y)中 (1) (3) 是等值的。12. 对公式x(P(x)Q(x)，其中P(x):x=1，Q(x):x=2，当论域为1,2时，其真值为 1 ，当论域为0,1,2时，其真值为 0 。13.下列各式(1).x(P(x)Q(x)(xP(x)$xQ(x)(2).(x(A(x)B(x)A(c)A(c)(3).(x(A(x)B(x)xB(x)$xA(x)(4).($x(P(x)Q(x)$xP(x)Q(x)其中(1). (2). (3).是永真式。14 给定下列各公式：(1).($xF(x)yG(y)(F(u)zH(z)(2).$xF(y,x)yG(y)(3).x(F(x,y)yG(x,y)则 是(1)的前束范式， 是(2)的前束范式， 是(3)的前束范式。供选择的答案有$xyz(F(x)G(y)(F(u)H(z)xyz(F(x)G(y)(F(u)H(z)$xy(F(y,x)G(y)xy(F(z,x)G(y)xy(F(z,x)G(y)x$y(F(x,z)G(x,y)xy(F(x,z)G(x,y)yx(F(x,z)G(x,y)yx(F(x,z)G(y)15.谓词公式xP(x)xQ(x)$yR(y)的前束范式为$xz$y(P(x)Q(z) R(y)。16谓词公式x(P(x)Q(x,y)$zR(y,z)S(x)的前束范式为$xz(P(x)Q(x,y) R(y,z)S(t)。*17.谓词公式$x(yG(y,b)H(x)的前束范式为x $y ( G(y,b) H(x)或x$y (G(y,b) H(x) 。三、判断题1 公式x(P(x)Q(x)R(y)中x的作用域为P(x)。（）2.同一谓词公式，指定不同的论域，其真值不一定相同。（）3.谓词公式xP(x)$y(P(y)是矛盾式。（）4.x(P(x)Q(x)($xP(x)$xQ(x)为永真。（）证明：x(P(x) Q(x)( $xP(x) $xQ(x) x(P(x) Q(x) ( $xP(x) $xQ(x) $x (P(x) Q(x) ( $xP(x) $xQ(x)$x (P(x) Q(x) ( $xP(x) $xQ(x)$x (P(x) Q(x) $xQ(x) $xP(x)$x (P(x) Q(x) Q(x) )$xP(x)$x (P(x) Q(x)$xP(x)$xP(x) $xP(x) $x Q(x)15. xy(P(x)Q(y)$xP(x)yQ(y)（）6.P(x)，Q(x)表示谓词，P表示命题，有x(P(x)P)$xP(x)P（）7.x(A(x)B(x)xA(x)xB(x)（）8.任意一个谓词公式都与一个前束范式等价。（）9.公式xP(x)$yQ(x,y)前束范式为xy(P(x)Q(x,y)（）正确的：$x$y(P(x)Q(z,y)10.公式$x($yP(x,y)($zQ(z)R(x)的前束范式为$x$y$z(P(x,y)Q(z)R(x)（） 11. 对公式$z(P(z)Q(x,z)M(z,y)R(z)中约束变量z改名后，得到的等价公式为：$t(P(t)Q(x,t)M(t,y)R(t)（）正确的：$t(P(t)Q(x,t)M(t,y)R(z)四、解答题1.将下列命题在一阶谓词中符号化（1）每一名计算机专业的大学生都要学习离散数学。解：设F(x):x是计算机专业的大学生 G(x):x学习离散数学 x(F(x)G(x)（2）并非一切推理都能用计算机完成。解：设F(x):x是推理 G(x):x是计算机 H(x,y):x能用y完成。 x (F(x) $y(G(y) H(x,y)（3）不存在最大的自然数。解：设F(x):x是自然数 H(x,y):x比y大。$x (F(x) y(F(y)H(x,y)（4）相等的两个角未必都是对顶角。解：设F(x):x是角，H(x,y):x与y相等，L(x,y):x与y是对顶角。 x y (F(x) F(y) H(x,y) L(x,y)（5）说有的火车比所有的汽车快是不对的。 解：设F(x):x是火车，G(x):x是汽车，H(x,y):x比y快 $ x (F(x) y(G (y) H (x,y) 或 x (F(x) $y (G (y) H (x,y)(6) 任何自然数都有惟一的一个后继数。解：设N(x):x是自然数，M(x,y):y是x的后继数x(N(x)$y(N(y) M(x,y) x y z (N(x) N(y)N(z)(M(x,y) M(x,z)(y=z)即：“一切自然数x，都有一个自然数y，使得y是x的后继数；并且对任何自然数x，当y和z都是x的后继时，则有y=z”。2求公式（1）xA(x)xB(x)的前束范式。解：xA(x)xB(x)yA(y)xB(x) 换名规则y(A(y)xB(x) 量词辖域扩张等值式yx(A(y)B(x) 量词辖域扩张等值式（2）xA(x) xB(x) L(x,y)的前束范式。解：xA(x) xB(x) L(x,y)xA(x)xB(x)L(t,y) 代替规则x(A(x)B(x)L(t,y) 量词分配等值式x(A(x)B(x)L(t,y)）量词辖域扩张等值式3.用谓词公式表示命题“”，并写出该命题的否定命题。解：对任意的e0，总存在d0，使得当0|x-a|d时，有|f(x)-A|0)d(d0) x(|x-a|0) (|f(x)-A|0) d(d0)$x(|x-a|0) (|f(x)-A|e)”*4.设P(x)：x是外语学的好的学生，Q(x)：x是三好学生，对下述自然语言用谓词符号化：(1).并不是外语学的好的都是三好学生。(2).有这样的学生，外语学的好而不是三好学生，但外语学不好的学生一定不是三好学生。解：(1). x (P (x) Q(x)(2). $x (P (x) Q(x) x(P (x) Q(x)5. 指出下列公式中量词每次出现的辖域，并指出个体变量是约束变量还是自由变量。(1).xy(R(x,y)L(y,z)$xH(x,y)(2).x(P(x)$xQ(x)(xP(x)Q(x)6. 设f,g,h是二元运算符号，E，L是二元谓词符号，考查的个体域为有理数集。给出解释如下：f(x,y)=xy；g(x,y)=x+y；h(x,y)=x2-y2；a=0；b=1；E(x,y):x=y；L(x,y):xy根据上面的解释，以下公式中哪些为真，哪些为假？(1).E(f(x,y),g(x,y) 解: (1)“xy=x+y” 不是命题(2).E(f(x,x),h(x,a) (2) “x2= x2-0” 有理数集下，它是真命题(3).L(x,y)L(y,x) (3) “(xy)（yx)” 不是命题(4).$xE(f(x,y),b) (4) “$x(xy=1)” 不是命题,该值随y变化(5).E(x,a)E(g(y,x),y) (5)“x0 x+y=y”假命题7. 设解释T如下：个体域为实数集R，元素a=0，函数f(x,y)=x-y，特定谓词F(x,y)为xy。根据解释T，下列哪些公式为真？哪些为假？(1).xF(f(a,x),a) (2).xy(F(f(x,y),x)(3).xyz(F(x,y)F(f(x,z),f(y,z)(4).x$yF(x,f(f(x,y),y)解：(1).x(-x)0) 假命题 (2).xy(x-yx) 假命题(3).xyz(xy)(x-z)(y-z) 真命题(4).x$y (x5，R(x)：x7。根据解释T，求下列各式的真值：(1).x(F(x)G(x)(2).x(R(x)F(x)G(5)(3).$x(F(x)G(x)解：(1). x(F(x)G(x)(F(-2)G(-2) (F(3)G(3) (F(6)G(6)(10) (10) (01)0 所以在解释T下为假命题 (2). x(R(x)F(x)G(5)( R(-2)F(-2) ( R(3)F(3) ( R(6)F(6) )G(5)(11) (11) (10) 00 所以在解释T下为假命题 (3). $x(F(x)G(x) $xF(x) $xG(x)(F(-2) F(3) F(6) (G(-2) G(3) G(6)1 所以在解释T下为真命题 9.下面公式是否是永真式？说明理由。(1).(A$xB(x)$x(AB(x)(2).$x(A(x)B(x)(xA(x)$xB(x) 解：（1）（2）都是永真式 (1).(A$xB(x)$x(AB(x) $x (AB(x)$x(AB(x) 量词辖域的收缩与扩张 1(2).$x(A