离散数学章节练习2KEY解析

1、离散数学章节练习2范围：谓词逻辑班级： 学号：姓名：一、单项选择题1 .下列那个公式是永真式：()a (p )v(pas) ； b. (p ap)t qc - xb(x) = x_ b(x) d. (p - p) q2 .下列公式中正确的等价式是()a. - xa(x)= x- a(x)b. - - xa(x)= x- a(x)c. - x - ya(x,y) = y - xa(x,y)d. - x(a(x) b(x) = - xa(x) - xb(x)3 .“人总是要死的”谓词公式表示为()(论域为全总个体域)m(x) : x是人；mortal(x) : x是要死的。a、m(x) morta

2、l(x)b、m(x) mortal(x)c、- x (m(x) mortal(x)d、 x (m(x) mortal(x)4 .谓词公式 v x(p(x) v(3y)r(y) t q(x)中的 x ()a.只是约束变元。b.既是约束变元又是自由变元。c.既非约束变元又非自由变元。d.只是自由变元。5 .当个体域d=a, b时，下列与xp(x)等值的式子是()a.p(a) p(b) b. p(a) p(b)c.p(a) p(b) d. -p(a) p(b)6 .设个体域是正整数集，则下列公式中真值为真的公式是()a. ( vx)( 3y)(x , y=0)b. ( v x)(三y)(x , y=

3、1)c. 一 x)( 3y)(x y=2)d. ( vx)( v y)( ”)(x-y=z)7 .下列公式中正确的等价式是()a. -( x)a(x) = (x) - a(x)b. -( - x)a(x) = (x) - a(x)c. (-x)( - y)a(x,y) =( y)(-x)a(x,y)d. ( - x)(a(x)b(x) = (- x)a(x) (- x)b(x)8 .命题逻辑中一i组公式hi, h2, ,hn. , c,存在关系 h a h2 alhnc当且仅当 hia h2a a h-c是()a.矛盾式。b.永假式。c.可满足式。d.永真式。9 .下列公式中正确的等价式是()

4、a. - xa(x)= x- a(x)b. - - xa(x)= x- a(x)c. - x - ya(x,y) = y - xa(x,y)d. - x(a(x) b(x) = - xa(x) - xb(x)10 .命题公式(p t q) t (q-*-1 p) vr的类型是()a.永真式。b.永假式。c.非永真式可满足式。d.重言式11 .下列公式中那个为永真式()a. - x(f(x) g(x)b. x(f(x) g(x)c. - xf(x) - - xf(x)d. -x-y(f(x) g(y) h(x,y)12 .“所有的狗都是会飞”谓词公式表示为()(论域为全总个体域)m(x) : x

5、是狗；mortal(x) : x是会飞的。a m (x) t mortal (x).b、 m (x) mortal (x)c、 vx(m (x)t mortal (x).d、 x(m (x) mortal (x)13 .公式 a = mx(p(x)t q(x)的解释 i 为：个体域 d=2 , p(x) : x3, q(x):x=4则a的真值为()a 1; b、0; c、可满足式； d、无法判定。14 .下列公式中正确的等价式是()a. 一 xa(x)匕 x-a(x)b. - - xa(x) = x-a(x)c. -x-ya(x,y) : y- xa(x,y)d. - x(a(x) b(x)

6、= - xa(x) - xb(x)15.谓词公式vxp(x,y) 3 - yq(x,y)的前束范式是()a、v xp(x,y) 3 yq(x,y);b、urp(r,y) 3vsq(x,s);c、r s( - p(r,y) q(x,s)d 、 murmsp(r,y) vq(x,s)16 .下列公式中正确的等价式是()a. - xa(x)= x- a(x)b. - - xa(x) 二 x-a(x)c. - x - ya(x,y)= y - xa(x,y)d. - x(a(x) b(x) = - xa(x) - xb(x)17 .下列公式中，不是pt (qt p)的代换实例的是()a. f(x,y)

7、 (g(x,y) f(x,y)b. f(x,y) g(x,y) f(x,y)c. f(y,x)(g(x,y)f(x,y)d. f(x,y)(g(x,y)f(y,x)18 .下列公式中等价的是()a、- x(a(x)b(x) =-xa(x)-xb(x)b、- x(a(x)b(x) =-xa(x)-xb(x)c、- x(a(x) b(x) = - xa(x) - xb(x)d、- x(a(x) b(x) = - x_ a(x) - xb(x)19 .对公式 vx(f(x) t g(y) tmy(h(x) a l(x,y,z) 的变元分析正确的 是 ()a. x是约束变元b. y是约束变元。c. z

8、是约束变元。d. x既是约束变元，又是自由变元。20.对公式vxy(p(x,y)八q(y,z)八三xp(x,y)中量词的作用域分析不正确的是()a x的作用域是p(x,y)b vy 的作用域是 p(x,y) aq(y,z)c日x的作用域是 p(x,y)d vx 的作用域是 p(x,y) aq(y,z)二、判断题1、3xvy(p(x,y) aq(a,y) xvy(p(x,y) aq(x,y)(其中 a 是个体常元)是永真式。()2、谓词逻辑中，量词(quantifiers )是表示个体常项或个体变项之 间数量关系的词。()3、谓词 w(x),m(z)中只有1个个体变元，则称为 1元谓词公式。 (

9、)4、f(y) ag(x,y)是合法的公式 ()5、v s(p(s)左 rq(r,z) 3 tr(s,t)不是闭公式()6、一个谓词公式，如果量词均在全式的开头，则该公式称为前束范式 ()7、量词指导变元是指 vxa和三xa中的x ()8、全称量词vx是指个体域中所有对象具有某性质或具有某相互关系()三、填空题1 .公式vxp(x) -* 3 x q(x)的前束范式是，。2 . v x(p(x) v(3y)r(y) t q(x)中vx 的辖域是 。3 .谓词公式(vx)( hy)(p(x,y)vr(y) t q(y),则其自由变元是o4 . v xp(x) tvyq(y)的前束范式为 。5 .

10、命题“对于任意给定的正实数，都存在比它大的实数”令 f(x) : x 为实数，ldy): x y则命题的逻辑谓词公式为 6 .谓词合式公式 -xp(x) xq(x)的前束范式为 。7 .将量词辖域中由现的 和指导变元交换为另一变 元符号，公式其余的部分不变，这种方法称为换名规则。8 .设x是谓词合式公式 a的一个客体变元，a的论域为d, a(x)关于y 是自由的，则 被称为存在量词消去规则，记为 e49 .公式vxp(x) -*3 x q(x)的前束范式是， 。10 .表示个体词的性质或个体词之间关系的词称为。11 .公式bxp(x) t v x q(x) 的前束范式是，12 . 一个析取范式

11、中，如果所有简单合取式均为极小项，则称为。13 .设a、b是两个合法的谓词公式，如果在任何解释下两个公式的真值都相等，则称a与b o四、计算题1 .将vxp(x,y) - 3 yq(x,y)转换为前束范式解：- xp(x,y) - - yq(x,y)二v rp(r,y) t 3 sq(x,s)约束变元改名 2分之寸rp(r,y) 二sq(x,s) 转换条件式2分u ”p(r,y) 7m sq(x,s)德摩律 2 分。三cs(p(r,y) v q(x,s)量词辖域的扩张2分2 .求谓词公式v x(p(x)外三y)r(y) t q(x)的前束范式。- x(p(x) yr(y) q(x)=v z(p

12、(z) v(3y)r(y) t q(x)1 分=vz3y(p(z) 7 r(y) t q(x)1 分=vz3y(p(z) 7 r(y) vq(x)1 分= hzvy-(p(z) 7 r(y) vq(x)1 分= ezvy(p(z) a-r(y) vq(x)1 分= hzvy( -p(z) a-r(y) v q(x)3 分3 .求谓词公式v x(p(x)外三y)q(y) t r(x)的前束范式。解 - x(p(x) yq(y) r(x)=v z(p(z) v(3y)q(y) t r(x)1 分=vz3y(p(z) 7 q(y) t r(x)1 分=_,v z3y(p(z) 7 q(y) vr(x

13、)1 分= bzvy-(p(z) 7 q(y) vr(x)1 分= ezvy( -p(z) a-q(y) v r(x)1分= ezvy( -p(z) a-q(y) v r(x)3分4 .将命题“并不是所有的汽车都比火车快”符号化。设f(x):x 是汽车，g(y):y 是火车, h(x,y):x 比 y 快，命题符号化为-x-y(f(x) g(y) h(x,y)或 x y(f(x) g(y) - h(x,y)5.给定解释i如下，试求下公式vx5yf(x,y)在i下白真值.个体域d=3,4;(b) f(x“为 f(3) =4,f(4)=3(c) f(x,y)为f(3,3) =f(4,4) =0,

14、f(3,4) =f(4,3) =1.解:-x yf(x,y) ：=-x(f(x,3) f(x,4)u (f(3,3) f(3,4) (f(4,3) f(4,4) u (0 1) (1 0) = 16.在一阶逻辑将下列命题符号化：(1) 火车都比轮船快.(2) 不存在比所有火车都快的汽车.解：(1)f(x): x 是火车；g(x): x 是轮船；h(x,y): x 比 y 快 命题符号化为：-x-y(f(x) g(y) h (x,y)(2) (1)f(x): x 是火车；g(x): x 是汽车；h(x,y): x 比 y 快 命题符号化为：-y(g(y) -x(f(x) h(x,y)7 .在一阶

15、逻辑中将下列命题符号化：(1)没有不能表示成分数的有理数.(2)在北京卖菜的人不全是外地人.解：(1)f(x): x能表示成分数h(x): x 是有理数命题符号化为：-x(-f(x) h(x)(2)f(x): x是北京卖菜的人h(x): x是外地人命题符号化为：-x(f(x)-； h (x)8 .判断vx木f(y)t太kyf(x,y)的类型：解:取解释i个体域为全体实数f(x,y) : x+y=5所以，前件为任意实数x存在实数y使x+y=5,前件真；后件为存在实数x对任意实数y都有x+y=5,后件假， 此时为假命题再取解释i个体域为自然数n,f(x,y) : :x+y=5所以，前件为任意自然数

16、x存在自然数y使x+y=5 ,前件假 命题。此公式为非永真式的可满足式。9 .求vxf(x)t vyg(x,y)的前束范式。 解：-xf(x) -yg(x,y)=-xf (x) 一 yg(t, y)二 x-y(f(x) g(t,y)10 .求三xf(xi，x2)t (h(xi)t px2g(x1,x2)的前束范式。解：x1f(x1,x2)- (h(x1)- -x2g(x1,x2)= x1f(xi,x2)(h 诲)g(x3, x?)二 xif(xi,x4) - x?(h (x3) - g(x3, x?)xi x2( f (xi, x4 ) ( h (x3) g(x3 , x2)五、综合题1 .证

17、明如下推理式：v x(f(x) 7 g(x) , vx(r(x) 7 g g(x) , v x(r(x) 证明：(1) v x(r(x)引入前提 1 分此时为假yf(x)r(x) us规则2分 vx(r(x) g(x) 引入前提1分(4)r(x) vg(x) us 规则2分(5)g(x)由(2),(4)2 分(6) vx(f(x) v g(x)引入前提1 分f(x) 7 g(x) us 规则2分(8) f(x)由(5),(7)1 分(9)三 yf(x)eg 规则2 .在自然推理系统中，构造下面推理的证明：每个科学工作者都是该项钻研的，每个刻苦钻研而又聪明的人在他的 事业中都奖获得成功。王大海是

18、科学工作者，并且是聪明的。所以王 大海在他的事业中获得成功(个体域为人类集合)解：设f(x) : x是科学工作者，g(x) : x是刻苦钻研的，h(x) : x是聪明的，i(x) : x在事业中获得成功。前提：vx(f(x) -g(x),甲x(g(x) ah(x) -i(x),a:王大海,f(a) , h(a)结论：i(a)证明f(a)前提引入vx(f(x) -g(x)前提引入 f(a) -g(a) uig(a)假言推理h(a)前提引入,x(g(x) ah(x) - i(x) 前提引入g(a) ah(a)-i(a)uig(a) ah(a)合取 i(a)3 .在自然推理系统中，构造下面推理的证明

19、(14分)：。每个喜欢步行的人都不喜欢骑自行车。每个人或者喜欢骑自行车或者喜欢乘汽车。有的人不喜欢乘汽车。所以，有的人不喜欢步行。(个体域为人类集合)解：设f(x) : x喜欢步行，g(x) : x喜欢骑自行车，h(x) : x喜欢乘汽车。前提：vx( 1 f(x) - 1 g(x), 结论：_xi f(x)证明3xq h(x) 1 h(c) *x(g(x) vh(x)g(c) v h(c) g(c) x(f(x) -g(x)f(c) 一i g(c)f(c)我1f(x)推理正确。x(g(x) vh(x) ,xi h(x)前提引入ui前提引入ui析取三段论前提引入ui拒取式ug4 .在自然推理系

20、统中，构造下面推理的证明(14分)：有理数和无理数都是实数，虚数不是实数。因此，虚数即不是有理数，也不是无理数。解：设f(x) : x是有理数，g(x):x是无理数，h(x) : x是实数，i(x) x是虚数。前提：vx(f(x) v g(x) -h(x) , x( i(x) - 1 h(x)结论：x(i(x) -(i f(x) an g(x)证明 x(i(x) - (1 h(x)ui w(f(x) vg(x) -h(x)(f(y) vg(y)-h(y) 1 h(y)-( f(y) an g(y)前提引入i(y) -h(y)前提引入ui置换假言三段论ugi(y) -(1 f(y) ai g(y) 式(i(x) -(1 f(x) a1 g(x) 推理正确。5.在自然推理系统中，构造下面推理的证明(前提：甲x(f(x) v