离散数学屈婉玲耿素云张立昂主编课后答案高等教育出版社.doc

1、1第一章部分课后习题参考答案16 设 p、q 的真值为 0；r、s 的真值为 1，求下列各命题公式的真值。（1）p(qr) 0(01) 0 （2） （pr）(qs) （01）(11) 01 0.（3） （ p qr）(pqr) （111） (000) 0(4)（ rs）(p q) （01）(10) 00 117判断下面一段论述是否为真：“ 是无理数。并且，如果 3 是无理数，则 也是 2无理数。另外 6 能被 2 整除，6 才能被 4 整除。 ”答：p: 是无理数 1q: 3 是无理数 0r: 是无理数 1 2s: 6 能被 2 整除 1t: 6 能被 4 整除 0命题符号化为： p(qr)(

2、t s)的真值为 1，所以这一段的论述为真。19用真值表判断下列公式的类型：（4）(p q) ( q p)（5）(p r) ( p q)（6）(pq) (qr) (pr)答： （4）p q pq q p q p (pq)( q p)0 0 1 1 1 1 10 1 1 0 1 1 11 0 0 1 0 0 11 1 1 0 0 1 1所以公式类型为永真式（5）公式类型为可满足式（方法如上例）（6）公式类型为永真式（方法如上例）第二章部分课后习题参考答案3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.2(1) (pqq)(2)(p(pq)(pr)(3)(pq

3、)(pr)答：(2)（p (pq)）(pr) ( p(pq) ( pr) ppqr 1所以公式类型为永真式(3) P q r pq pr （pq）(pr)0 0 0 0 0 10 0 1 0 0 10 1 0 1 0 00 1 1 1 0 01 0 0 1 0 01 0 1 1 1 11 1 0 1 0 01 1 1 1 1 1所以公式类型为可满足式4.用等值演算法证明下面等值式：(2)(pq)(pr) (p(qr)(4)(p q)( pq) (pq) (pq)证明（2）(pq)(pr)( pq)( pr)p(qr)p(qr)（4）(p q)( pq) (p( pq) ( q( pq)(p p

4、)(pq)( q p) ( qq)1(pq) (pq)1(pq) (pq)5.求下列公式的主析取范式与主合取范式，并求成真赋值(1)( pq)( qp)(2) (pq)qr(3)(p(qr)(pqr)解：（1）主析取范式3( pq)( 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)320m(0,2,3) 主合取范式：( pq)( q p) (p q) ( q p) ( p q) ( q p)( p ( q p) ( q ( q p)1 (p q)(p q) M1(1)(2) 主

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

6、q证明：（2） (q r) 前提引入 q r 置换q r 蕴含等值式r 前提引入 q 拒取式p q 前提引入p（3） 拒取式证明（4）：t r 前提引入t 化简律q s 前提引入s t 前提引入q t 等价三段论（q t） (t q) 置换（q t） 化简q 假言推理q p 前提引入p 假言推理5(11)p q 合取 15 在自然推理系统 P 中用附加前提法证明下面各推理：(1)前提：p (q r),s p,q结论：s r证明s 附加前提引入s p 前提引入p 假言推理p (q r) 前提引入q r 假言推理q 前提引入r 假言推理16 在自然推理系统 P 中用归谬法证明下面各推理：(1)前提

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

8、在(b)中为真命题。)(xF(2)在两个个体域中都解释为 ，在（a）(b)中均为真命题。)(G4. 在一阶逻辑中将下列命题符号化:(1) 没有不能表示成分数的有理数.(2) 在北京卖菜的人不全是外地人.解:(1)F(x): x 能表示成分数H(x): x 是有理数命题符号化为: )(xHF(2)F(x): x 是北京卖菜的人H(x): x 是外地人命题符号化为: )()(x5. 在一阶逻辑将下列命题符号化:(1) 火车都比轮船快.(3) 不存在比所有火车都快的汽车. 解:(1)F(x): x 是火车; G(x): x 是轮船; H(x,y): x 比 y 快命题符号化为: ),()(HyGFy

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

10、 给定解释 I 如下：（a） 个体域 D=N(N 为自然数集合).（b） D 中特定元素 =2.（c） D 上函数 =x+y, (x,y)=xy.(,) （d） D 上谓词 (x,y):x=y.说明下列各式在 I 下的含义，并讨论其真值.(1) xF(g(x,a),x)(2) x y(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) (,)(,)(,).(3) yF(x,y).x(,)解:(1)因为 为永真式；1)

11、()( pqpq所以 为永真式；(,)(,)(,).(3)取解释 I 个体域为全体实数F(x,y)：x+y=5所以,前件为任意实数 x 存在实数 y 使 x+y=5，前件真；后件为存在实数 x 对任意实数 y 都有 x+y=5，后件假，此时为假命题再取解释 I 个体域为自然数 N，8F(x,y)：:x+y=5所以,前件为任意自然数 x 存在自然数 y 使 x+y=5，前件假。此时为假命题。此公式为非永真式的可满足式。13. 给定下列各公式一个成真的解释，一个成假的解释。(1) (F(x)x ()(2) x(F(x) G(x) H(x) 解:(1)个体域:本班同学F(x)：x 会吃饭, G(x)

12、：x 会睡觉.成真解释F(x)：x 是泰安人,G(x)：x 是济南人.（2）成假解释(2)个体域:泰山学院的学生F(x)：x 出生在山东,G(x):x 出生在北京,H(x):x 出生在江苏,成假解释.F(x)：x 会吃饭,G(x)：x 会睡觉,H(x)：x 会呼吸. 成真解释.第五章部分课后习题参考答案5.给定解释如下:(a)个体域 D=3,4;(b) 为)(xf 3)4(,)3(ff(c) .1)3,4(),(0, FFyF为试求下列公式在下的真值.(1) ),(x(3) )(,yfxy解:(1) 4,3),(FF),()(),(10)1(2) )(,yfxyx)4(,)4,(3)3( fx

13、FxF3()4,(, ff),)(9)3,4(),()4,()3,4( fFfF30)3,(01F)1()( )0()(12.求下列各式的前束范式。(1) ),()(yxGxF(5) (本题课本上有错误),(, 212121 xH解:(1) ),()(,)ytGF),()(ytGxF(5) (, 212121xxF),)()( 33x(, 2241H),)()( 332 Gxx15.在自然数推理系统 F 中,构造下面推理的证明:(1) 前提: ,)()()( yRy )(xF结论: xR(x)(2) 前提: x(F(x)(G(a)R(x), xF(x)结论: x(F(x)R(x)证明(1) 前

14、提引入)(xFF(c) EI 前提引入)()()( yRGy 假言推理)y(F(c)G(c)R(c) UIF(c)G(c) 附加R(c) 假言推理 xR(x) EG(2) xF(x) 前提引入10F(c) EI x(F(x)(G(a)R(x) 前提引入F(c)(G(a)R(c) UIG(a)R(c) 假言推理R(c) 化简F(c)R(c) 合取引入 x(F(x)R(x) EG第六章部分课后习题参考答案5.确定下列命题是否为真：（1） 真 （2） 假（3） 真（4） 真（5） a,b a,b,c,a,b,c 真（6） a,b a,b,c,a,b 真（7） a,b a,b,a,b 真（8） a,b a,b,a,b 假6设 a,b,c 各不相同，判断下述等式中哪个等式为真:（1） a,b ，c, =a,b,c 假（2） a ,b,a=a,b 真（3） a ，b=a,b 假（4） ， ，a,b= , ,a,b 假8求下列集合的幂集：（1） a,b,c P(A)= ,a,b,c,a,b,a,c,b,c,a,b,c（2） 1， 2，3 P(A)= , 1, 2,3, 1，2，3 （3） P(A)= , （4） ， P(A)= , 1, 2,3, 1，2，3 14化简下列集合表达式：