离散数学答案_1-5章

1、第一章部分课后习题参考答案16设p、q的真值为0; r、s的真值为1 ,求下列各命题公式的真值。(1) pV(qAr) 0 V (0 A1)0(2) (p?r) A(qVs) (0?1) A (1 V 1)0A 10.(3) ( pA qAr) ?(pAqAr)(1A1A1) ? (0 A 0A 0)0(4) ( rAs) 一(pA q) (0A1) 一(1A0)00117.判断下面一段论述是否为真：”是无理数。并且，如果3是无理数，则、为也是无 理数。另外6能被2整除，6才能被4整除。”答：p:是无理数1q: 3是无理数0r: J2是无理数1s: 6能被2整除1t: 6 能被4整除0命题符号

2、化为：p A(q-r) A(t s)的真值为1,所以这一段的论述为真19.用真值表判断下列公式的类型:(4) (pq) 一( q - p)(5) (p Ar) ( pA q)(6) (p-q) A(q - r) 一(pr)p 001 1(4)011111110111001001110011q p- q q p q- p (p q)一( q- p)所以公式类型为永真式 等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值(pAq-q)(2)(p - (p V q) V(p r)(p Vq)-(pAr)pV pVqV r 1答：(2) (p 一 (pVq) V(p - r

3、) ( pV (p V q) V ( pV r)所以公式类型为永真式(3) PqrpV qpA r(pVq)-4（p八r）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 (p-r)(p V q) A ( p V r) p V (q A r)p-(q 八 r)(4) (pA q) V( pAq) (p V ( pAq) A( qV(pA q)(

4、p V p) A (p Vq) A ( qV 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(p V (q A r) (p Vq V r)解：( 1)主析取范式(pf 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)m0m2m313(0,2,3)主合取范式：(pfq)( q p)(p q) ( q p)( p q) (

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

6、p q, (q r),r结论： ps,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 t)qq pp(11)p q前提引入化简律前提引入前提引入等价三段论(t q)? 置换化简 假言推理前提引入假言推理合取pP 中用附加前提法证明下面各推理：15在自然推理系统(1) 前提：p(qr),s p,q结论：sr证明 s附加前提引入 s p 前提引入 p假言推理 p (q r) 前提引入 q r 假言推理 q前提引入 r假言推理16 在自然

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

8、(x)，在(a)中为假命题，在(b)中为真命题。(2)在两个个体域中都解释为xG(x),在(a) (b)中均为真命题。4. 在一阶逻辑中将下列命题符号化:(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 比

9、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)9. 给定解释I 如下 :(a) 个体域D为实数集合R.(b) D中特定元素=0.(c) 特定函数(x,y)=xy,x,yD .(d) 特定谓词(x,y):x=y,(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

10、, 如果 x<y, 那么 x y. 真值 1.(2) 对于任意两个实数x,y, 如果 x-y=0, 那么 x<y. 真值 0.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) xy(F(f(x,a),y) -F(f(y,a),x)答 :(1) 对于任意自然数x, 都有 2x=x, 真值 0.(2) 对于任意两个自然数x,y, 使得如果x+2=y, 那么 y+2=x. 真值

11、 0.11. 判断下列各式的类型:(1)(3) yF(x,y).解 :(1) 因为 p (q p) p ( q p) 1 为永真式；所以 为永真式；(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)解

12、 :(1) 个体域 : 本班同学F(x) : x会吃饭,G(x) : 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.给定解释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,

13、y)(3)x y(F(x,y)F(f (x), f(y)解:(1) x yF(x,y) 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

14、) (0 F (3,3)(00) (11) (11) (00)112.求下列各式的前束范式。(1) xF(x) yG(x, y)(5)x1F(x1,x2)(H(x1)x2G(x1,x2)(本题课本上有错误)G(t,y)解 :(1) xF(x) yG(x,y) xF(x) yG(t, y) x y(F(x)(5) x1F (x1, x2)(H (x1)x2G(x1, x2 )x1F(x1, x2)(H (x3)x2 G(x3,x2)x1F(x1, x4)x2(H (x3)G(x3,x2)x1 x2(F(x1,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) AR(x), xF(x)结论:x(F(x) A R(x)证明 (1) xF (x) 前提引入 F