离散数学屈婉玲答案

1、百度文库-让每个人平等地提升自我11第一章部分课后习题参考答案16设p、q的真值为0; r、s的真值为1,求下列各命题公式的真值。(1)pV(qAr) 0 V (0A1) / 0(2)(p? r) A (qVs)(0? 1) A(1 V1)0A 10.(3)(p A q A r), ? (p A q Ar)(1 A 1 A 1) ?式0 A0A 0)0(rAs).-(pA q)(0A 1) 一(1 A0)00117.判断下面一段论述是否为真:是无理数。并且，如果3是无理数，则也是无理数。另外6能被2整除，6才能被4整除。”答：p: 是无理数q：3是无理数r:s:6能被2整除1t:6能被4整除

2、0命题符号化为：p A (q-r) A (t-s)的真值为1,所以这一段的论述为真19.用真值表判断下列公式的类型:(4)(p-q) 一( q - p)(5)(pAr) ( pA q)(6)(p-q)八(q-r) (pr)(4)p0011q 0101p-q11 011010所以公式类型为永真式p1100q 一p1101(p-q)( q - p)1111等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.(1) (pAq-q)(2)(p-(pVq)V (pr)(3)(pVq)-(pAr)答：(2) (p一(pVq) V (p-r)( pV(pVq)V( pVr)pV

3、pV qV r 1所以公式类型为永真式PqrpVqp A r(pV q) (pAr)000001001001010100011100100100101111110100111111所以公式类型为可满足式4 .用等值演算法证明下面等值式：(p 一 q) A (p 一 r) (p 一 (q A r)(p A q) V ( pA q) (p V q) A (p A q)证明(2) (p q) A (pr)(pVq)A( pVr) pV(q A r)p 一 (q 八 r)(4) (pA q) V( pAq) (p V ( pAq) A( qV( pA q) (p V p) A (p Vq) A ( q

4、V p) A ( qVq)1 A (p V q) A (p A q) A 1 (p V q) A (p A q)5 .求下列公式的主析取范式与主合取范式，并求成真赋值(1)(p-q)(qvp)(2) (p q)AqAr(3)(p V(q Ar) 一(p VqVr)解：(1)主析取范式/(p一 q)(q p)/(p q) ( q p)(p q) ( q p) /(p q)(q p) ( q p) (p q) (p q)(p q) (p q) (p q)mo m2 m3三(0,2,3)主合取范式：(p-q)(q p)(p q) ( q p)(p q) ( q p)(p ( q p)( q ( q

5、p)1 (p q)(p q)Min(2) 主合取范式为：(p-q) q r ( p q) q r(p q) q r 0所以该式为矛盾式.主合取范式为n (0,1,2,3,4,5,6,7)矛盾式的主析取范式为0(3)主合取范式为： (p (q r) 一 (p q r)(p (q r) 一 (p q r)(p ( q r) (p q r)(p (p q r)( q r) (p q r)1 11所以该式为永真式.永真式的主合取范式为1主析取范式为三(0,1,2,3,4,5,6,7)第三章部分课后习题参考答案14.在自然推理系统P中构造下面推理的证明：*(2)前提：p q, (q r),r结论： ps

6、,s t,t r(4)前提：q p,q 结论：p q证明：(2)(q r)q rq rrqp q前提引入置换蕴含等值式前提引入拒取式前提引入拒取式证明(4):t rtq ss tq t(q t)(q 7)qq pp(ii)p q前提引入化简律前提引入前提引入等价三段论(t q) 置换化简假言推理前提引入假言推理合取15在自然推理系统P中用附加前提法证明下面各推理:p前提：p (q r),s p,q结论：s r证明附加前提引入前提引入(qr)假言推理前提引入假言推理前提引入假言推理16在自然推理系统P中用归谬法证明下面各推理:(1)前提：pq, r q,r s结论:证明:结论的否定引入前提引入假

7、言推理 前提引入 化简律 前提引入 化简律r r合取由于最后一步rr是矛盾式，所以推理正确.第四章部分课后习题参考答案条件时命3.在一阶逻辑中将下面将下面命题符号化，并分别讨论个体域限制为(a),(b) 题的真值:(1)对于任意x,均有松,-2=仅+a)仅7?).(2)存在 x,使彳# x+5=9. /其中(a)个体域为自然数集合./(b)个体域为实数集合./解：F(x):- -2=(x+品)(x - ” ).G(x): x+5=9.(1)在两个个体域中都解释为xF(x)，在(a)中为假命题，在(b)中为真命题。(2)在两个个体域中都解释为xG(x),在(a) (b)中均为真命题。4 .在一阶

8、逻辑中将下列命题符号化：(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)5 .在一阶逻辑将下列命题符号化：(1) 火车都比轮船快.(3)不存在比所有火车都快的汽车.解： (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

9、 比 y 快命题符号化为： y(G(y)x(F(x) H(x,y)9.给定解释I如下：/(a) 个体域D为实数集合R./(b) D中特定元素工=0./(c) 特定函数：(x,y)=x -y,x,y DwD>(d) 特定谓词 F(x,y):x=y, 1(x,y):x<y,x,y D.说明下列公式在I下的含义，并指出各公式的真值:(1) x y(G(x,y) F(x, y)(2) x y(F(f(x,y),a)G(x,y)答：(1)对于任意两个实数x,y,如果x<y,那么x y.真值1.(2)对于任意两个实数x,y,如果x-y=0,那么x<y.真值0.10.给定解释I如下：

10、/(a)个体域D=N(N为自然数集合).(b) D中特定元素曜=2.(c) D上函数果工切=x+y,鼠x,y)=xy.(d) D 上谓词M(x,y):x=y.说明下列各式在I下的含义，并讨论其真值.(1) -xF(g(x,a),x)(2) vxvy(F(f(x,a),y)一F(f(y,a),x)答：(1)对于任意自然数x,都有2x=x,真值0.(2)对于任意两个自然数x,y,使得如果x+2=y,那么y+2=x.真值0.11.判断下列各式的类型：(1) 7 .-'.-二(3) - 7- - yF(x,y).解：(1)因为p (q p) p ( q p) 1 为永真式；所以F(xp) t伯

11、值巾-F双力).为永真式；(3)取解释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所以，前件为任意自然数x存在自然数y使x+y=5,前件假。此时为假命题。 此公式为非永真式的可满足式。13.给定下列各公式一个成真的解释，一个成假的解释。/(1)-：(F(x)依腾微/(2)三x(F(x) G(x) H(x)解:(1)个体域：本班同学F(x) : x会吃饭,G(x) : x会睡觉.成真解释F(x)： x是泰安人,G(x)

12、 : x是济南人.(2)成假解释(2)个体域：泰山学院的学生 /F(x) : x出生在山东,G(x):x出生在北京，H(x):x出生在江苏，成假解释.F(x) : x会吃饭,G(x) : x会睡觉,H(x) : x会呼吸.成真解释./第五章部分课后习题参考答案5.给定解释I如下：(a)个体域 D=3,4;(b) f(x)为 f(3) 4,f(4) 3(c) F(x,y)为F(3,3)F(4,4) 0, F(3,4)F(4,3) 1丁 一为丁 门；二二 ；二.试求下列公式在I下的真值.(1) x yF(x, y)(3)x y(F(x,y)F(f (x), f(y)解:(1) x yF(x,y)

13、x(F(x,3) F(x,4)(F(3,3) F(3,4) (F(4,3) F(4,4)(0 1) (1 0)1(2) x y(F(x,y) F(f(x), f(y)x(F(x,3)F(f(x), f (3) (F(x,4)F(f(x), f (4)x(F(x,3)F(f(x),4) (F(x,4)F(f (x),3)(F(3,3)F(f(3),4) (F(3,4)F(f(3),3)(F(4,3)F(f (4),4) (F(4,4)F(f(4),3)(0F(4,4) (F(3,4)F(4,3)(1F(3,4) (0 F (3,3)(00) (11)(11) (00)112.求下列各式的前束范式

14、。、/(1) xF(x) yG(x, y)(5) XiF(Xi,X2)(H(xi)X2G(Xi,X2)(本题课本上有错误)解：(1) xF(x) yG(x,y) xF(x) yG(t,y) x y(F(x) G(t,y)(6) x1 F (x1, x2)(H (x1)x2G(x1,x2)XlF(Xi,X2)(H ( X3 )X2 G(X3,X2)xi F (xi, X4)X2(H (X3)G(X3,X2)Xi X2(F(Xi,X4)(H(X3)G(X3,X2)15.在自然数推理系统F中，构造下面推理的证明：(1)前提：xF(x) y(F(y) G(y)R(y), xF(x) 结论：xR(x)(2)前提： x(F(x) 一(G(a) A R(x),三 xF(x)结论：三x(F(x) A R(x)证明(1)xF (x