离散数学课后答案(第1,2,4章)武汉大学出版社.doc

习题1.11、（1）否（2）否（3）是，真值为0（4）否（5）是，真值为12、（1）p：天下雨 q：我去教室 p q（2）p：你去教室 q：我去图书馆 p q（3）p，q同（2） q p（4）p：2是质数 q：2是偶数 pq3、（1）0（2）0（3）14、（1）如果明天是晴天，那么我去教室或图书馆。（2）如果我去教室，那么明天不是晴天，我也不去图书馆。（3）明天是晴天，并且我不去教室，当且仅当我去图书馆。习题1.21、（1）是（2）是（3）否（4）是（5）是（6）否2、（1）(p q) r，p q，r，p，q（2）(pq) （rp），p q，rp，p，q，r，p（3）(p q) (q p) (p q)，(p q) (q p)，(p q)，p q，(q p)，p q，p，q，q，p，p，q3、（1）(p q) (q p) (p q)（2）(p q) (p q) r) (p q) (p q) r)（3）(q pp) (pp q)4、(p q) (pq) (pq) (pq)习题1.31、（1）i(p(qr) = i(p)(i(q)i(r) = 1(10) = 1（2）i(pqr)(pq)(rs) = (110)(11)(01) = 0(00) = 0（3）i(pr)(qs) = (10)(11) = 01 = 0（4）i(p(qrp)(qs) = (1(1(01)(11) = 11 = 1（5）i(pq)r(qp)rs) = (11)0(11)(01) = 011 = 12、（1）pqpqq(pq)q(pq)p00101011101000111111（2）pqrqr(p(qr)pqpr(pq)(pr)原式000010000001010100010011000011101110100001110101001110110001110111101110（3）pqrpqqppqqppr原式00000100001001000101000101110001100100111011000111011111111111003、（1）原式 fq t 原式为永真式（2）原式 t(pq)(qp) (pq)(qp) (pq)(pq) t 原式为永真式（3）原式 (pq) (pq) t 原式为永真式（4）原式 p(qr) p(qr) t 原式为永真式（5）原式 (pq)q (pq)q q 原式为可满足式（6）原式 (pq)p pqp tq t 原式为永真式（7）原式 (ppq)p (tq)p tp p 原式为可满足式（8）原式 (pq) (qr)(pr) (pq)(qr)(pr) (pq)p)(qr)r) ( pp)(qp)( qr)(rr) (qp)( qr) t 原式为永真式4、（1）左 pqp p(pq) 右（2）左 (pq) 右（3）左 (pq)p pqp tq 右（4）左 (pq)(qp) (pq)(qp) 中 (pq)q)(pq)p) (pq)(qq)(pp)(qp) (pq)(pq) 右(5)左 ( p q) ( r q) (p q) q 右5.(1)左 q p q 右 (2)(p (q r) (p q) (p r) ( p q r) ( p q) ( p r) (p q r) (p q) p r (p q r) (p p) ( q p) r (p q r) ( q p r) (p q r) (p q r) t故p (q r) (p q) (p r) (3).(p q) (p p q) ( p q) p (p q) ( p q) ( p p) ( p q) ( p q) ( p q) t故p q p p q(4).(p q) q) p q ( ( p q) q) p q ( p q) q) p q ( p q) (q q) p q (p q) (p q) t故(p q) q p q(5).(p p) q) (p p) r) (q r) ( t q) ( t r) q r (q r) q r q r q r q t t故(p p) q) (p p) r) q r(6)左 (q f) (r f) ( q f) ( r f) q r r r q 右6.(1)原式 ( p q r) (2)原式 p q p (p q p)(3)原式 p (q r p) p q r ( p q r)7.(1)原式 ( p q p)(2)原式 ( p q r) p q ( ( p q r) p q)(3)原式 p q (r p) (p q (r p)8. (1) (p q) ( p ( p q) r) p(2)(p q r) ( p r)(3)(p f) (q t)习题1.41.(1)原式 ( p q) ( p q) (q p) ( p q) (q p) (p q) q p q p,既是析取范式又是合取范式 (2)原式 ( p q) ( p q) ( ( p q) ( p q) (p q) (p q) 析取范式 p (q q)合取范式 (3)原式 p q s ( p q)析取范式 ( p ( p q) q s p q s合取范式(4)原式 p p q q r既是析取范式又是合取范式2.(1)原式 p q r为真的解释是：000，001，011，100，101，110，111故原式的主析取范式为:( p q r) ( p q r) ( p q r) (p q r) (p qr) (p q r) (p q r)(2)原式 (p q) r (p q (r r) (p p) r) (p q r) (p q r) (p q) ( p r) (p q r) (p q r) (p (q q) r) ( p (q q) r) (p q r) (p q r) (p q r) (p q r) ( p q r) ( p q r) (p q r) (p q r) (p q r) ( p q r) ( p q r)为真的解释是101，100，111，011，001(3)原式 ( p (q r) (p ( q r) ( p (q r) p) ( p (q r) ( q r) ( p p) (q p r) ( p q r) (q r q r) (p q r) ( p q r) 为真的解释是：000,111(4)原式 p p q q r p q r为真的解释是：001，010，011，100，101，110，111故原式的主析取范式为：( p q r) ( p q r) ( p q r) (p q r) (p q r) (p q r) (p q r)3.(1)原式 p q p q t主合取范式，无为假的解释。(2)原式 (p q r) ( p q r) ( p q r) ( p q r)为真的解释为：111，011，001，000，故为假的解释为：010，100，101，110原式的主合取范式为：(p q r) ( p q r) ( p q r) ( p q r)(3)由2.(2)知，原式为真的解释是：101，100，111，011，001，故为假的解释是：000，010，110.故原式的主合取范式为：(p q r) (p q r) ( p q r)(4)由2.(4)知，原式为假的解释是：000，故原式的主合取范式为：p q r4.(1)左式 ( p q) ( p r) ( p q (r r) ( p (q q) r) ( p q r) ( p q r) ( p q r)右式 p (q r) ( p q) ( p r) ( p q r) ( p q r) ( p q r)故原式成立。(2)左式 （pq）（pq）， 右式 （pp）(qp) p（pq） p （pq）（pq）， 故原式成立(3)左式 （pq）（pq） f，主析取范式 右式 （pq）（pq） f， 故原式成立(4)左式 t（pq） t，主合取范式 右式 （pq）（pq） t， 故原式成立习题1.51.（1）pq 前提 p ，化简 p(qr) 前提 qr ，mp q ，化简 r ，mp （2）r 前提 （qr） 前提 qr ，e11 q ，析取三段论 pq 前提 p ，析取三段论 （3）s 假设前提 sp 前提 p ，析取三段论 （pq）（pr） 前提 pq ，化简 pr ，化简 q ，mp r ，mp qr ，合取引入 （qr） 前提 （qr）（qr） ，合取引入 f ，e21 故原推理成立 （4）r 假设前提 （pq）r 前提 （pq） ，拒取式 pq ，e14，e10 qt 前提 pqqt ，合取引入 f ，e21，e17 故原推理成立2.（1）p 附加前提 pq 前提 q ，析取三段论 qr 前提 r ，析取三段论 rs 前提 s ，mp ps cp （2）p 附加前提 pq 前提 q ，mp pq ，合取引入 ppq cp （3）pq 附加前提 p ，化简 pq ，附加规则 pqr 前提 r ，mp pqr cp （4）p 附加前提 q 附加前提 p（qr） 前提 qr ，mp r ，mp q（rs） 前提 rs ，mp s ，mp pqr cp3.（1）（p） 假设前提 p ，e1 pq 前提 q ，mp qr 前提 r ，析取三段论 rs 前提 rrs ，合取引入 f ，e21，e17 故原推理成立 （2）（rs） 假设前提 rs ，e10 r ，化简 s ，化简 pr 前提 qs 前提 p ，拒取式 q ，拒取式 pq ，合取引入 （pq） ，e10 pq 前提 （pq）（pq） ，合取引入 f ，e21 故原推理成立（3）1.(s) 假设前提2.s 1,e13.sq 前提4.q 2, 3,mp5.r q 前提6.(rq) (rq) 5,e157.rq 6,化简8.r 4, 7,拒取式9.r 前提10.rr 8,9,合取引入11.f 10,e21故反推原理正确(4) 1.(p q) 假设前提2.（pq）(qp) 1,e15,e113.(pq) (rs) 前提4. (qp) r 前提5.(qp) r 4,e146.(rs) r 2，3，5构造二难性7.(rs) r) 6，e118.r 7，e139.r 前提10.rr 8，9合取引入11.f 10，e21故反推原理正确4 （1）先证 aa a 附加前提 a(aa) p31例1.5.7中用a置换用a置换a (aa) ，mp (aa) (aa) l3中用a置换b aa ，mp a ，mp aa 演绎定理 再证aa aa 上述结论中用a置换a (aa) (aa) l3中用a置换a，用a置换b aa ，mp 最后证(ba) (ab)ba 附加前提bb 上述结论ba ，hsaa 上述结论ba ，hs(ba) (ab) l3中用b置换a，用a 置换bab ，mp(ba) (ab) 演绎定理(2)先证 (ab) a (ab) 附加前提 a(ab) p31,例1.5.7 (a(ab) (ab) a) （1） (ab) a ，mp a ，mp aa 上述结论 a ，mp (ab) a 演绎定理 再证 (ab) (ba) (ab) a 上述结论 a(ba) l1 (ab) (ba) ，hs习题1.61.pqpq(pp) q(pp) q) (pp) q)(pp) q)(pq) r(pq) r) (pq) (rr) (pq) (rr)2.p(qr) p(qr) (pq) (p r) (pq) (pr) (p(qq) (pr) (p(qq) (pr)3.(1)左式p q(pq) 右式(2)左式pq(pq) 右式4（1）否，见p33，例1.6.1 （2）否，见p33，例1.6.1 （3）是，pq (p q),pq(pq) (pq) p q, pqpq(p q),p q(pq) (qp) (pq) (qp) (pq) (qp) (pq) (qp) (p q) (q p)， 中去掉，无法表示否定，去掉 ，无法表示二元运算(4 ) 否。，为极小全功能集 (5 ) 否。因为没公式a(p,q)仅含p,q, , ,则a(p,q)仅在两种解释下为真，而pq仅在一种解释下为真，故a(p,q)与a不等价，即pq不能用仅含的公式等价地表示。 （6）是。p pp,pq (pq) (pq) (pq), pq (pq) pq (pp) (qq), p q(pq) (qp) (pq) (qp) (p(qq) (q(pp) (p(qq) (q(pp) (p(qq) (q(pp)(p(qq)(q(pp) (7) 否，由（6）知(8)是，类似于（6）习题2.11.(1)r(x):x是实数，m(x,y):x比y大，$x(r(x) y(r(y) m(x,y) (2)r(x):x是实数，m(x,y):x等于y，n(z,x,y):z在x与y之间,xy(r(x) r(y) m(x,y) $z(r(z) n(z,x,y) m(z,x) m(z,y) (3)e(x):x是偶数，m(x):x是质数。$!x(e(x) m(x) (4)o(x):x是奇数，e(x):x是偶数。$x(e(x) m(x) (5)n(x):x是自然数，m(x):x+1=0, $x(n(x) m(x) (6)n(x):x是自然数，m(x,y):x+1=y, x(n(x) $!y(n(y) m(x,y) (7)m(x):x是火车，n(x):x是汽车，f(x,y):x比y快，x(m(x) $y(n(y) f(x,y)2. (1)$xl(x,0)(2) xyz(l(x,y) l(y,z) l(x,z)(3) xy(l(x,y)$z(l(z,0) g(f(x,z),f(y,z).其中f(u,v)=uv (4) $xym(x,y,y)(5) x$ya(x,y,x)3. (1) $!x(e(x) m(x) (2)n(x):x是自然数，f(x,y):x大于y,m(x,y):x-1=y x(n(x) f(x,0) $!y(n(y) m(x,y) (3)m(x):x是平面上的点，n(x):x直线，f(z,x,y):z过x与y， xy(m(x) m(y) $!z(n(z) f(z,y,x) (4)m(x):x是平面上的点，n(x):x是平面上的直线，f(x,y):x在y上，g(x,y):x过y. h(x,y):x平行y xy(n(x) m(y) f(y,x) $!z(n(z) g(z,y) h(z,x)4.(1)存在x,对任意y,有x*y=1; (2)对任意x,存在y,使x*y=1. (3)对任意x,存在y，使x*y=0(4)存在x,对任意y，有x*y=0(5)对任意x,存在y，使x*y=x(6)存在x,对任意y，有x*y=x(7)对任意x和y，存在y，使x-y=y习题2.21. (1)x是约束变元，也是约束出现；y是自由变元，也是自由出现。 (2)x(p(x) q(x)中的x皆为约束出现，也是约束变元，r(x)中的x为自由出现，也是自由变元 (3)x,y是约束出现，也是约束变元；z是自由出现，也是自由变元。 (4)x(p(x) $xq(x)中的x圴为约束出现，也是约束变元；yr(z,y)中的y为约束出现，也是约束变元z和r(x,y)中的x与y为自由出现也是自由变元2. (1) 的辖域为p(x) q(x,y); $的辖域为p(x) (2) ,$的辖域均为r(x,y) p(y) (3) x,y的辖域为r(x,y) p(y,z); $x的辖域为q(x) (4) ,$的辖域均为r(x,y)3. (1) zp(z) y$wr(w,y) q(x) (2) u(p(u,y) q(y) $vr(,v,z) (3) $uvp(v,u) wp(w,y) $zr(x,z)习题2.31. (1)p(1) q(1)=1.p(2) q(2)=1.原式在i下为1 (2)由(1)知，原式在i下为1 (3)p(1) q(1)=0,原式在i下为0 (4)p(1) q(1)=0,p(2) q(2)=0.原式在i下为0 (5)p(1) q(1)=1,原式在i下为0 (6)p(2) q(2)=1,原式在i下为1 (7)p(2)=0, xp(x)=0;q(1)=0, xq(x)=0,原式在i下为0 (8)p(1)=1, $xp(x)=1;q(2)=1, $xq(x)=1,原式在i下为12.(1)构造i1：di1=， , ,原式在i1下为0构造i2: di2=， , 原式在i2下为1，故得证 (2) )构造i1：di1=， , , 原式在i1下为0 构造i2: di2= , , 原式在i2下为1，故得证 (3) 构造i1：di1=, , 原式在i1下为0 构造i2: di2=, , 原式在i2下为1，故得证 (4) 构造i1：di1=, , 原式在i1下为0 构造i2: di2=, , 原式在i2下为1，故得证.3. (1)成立。若xa(x) xb(x)为0，则xa(x)为1，且xb(x)为0，即i，di,a（）为1，且$di，b()为0，则a() b()为0，故x(a(x) b(x)在i下为0，从而原式成立。 (2)不成立。构造i: di=， , ,则a() b()为0，故x(a(x) b(x)为0,而xa(x), xb(x)在i下均为0，故xa(x) xb(x)在i下为1，从而(xa(x) xb(x) x(a(x) b(x)在i下为0，故原式不成立。 (3)成立。左式$xa(x) xb(x) xa(x) xb(x) x(a(x) b(x) 右式 (4)不成立。左式x(a(x) b(x) xa(x) xb(x) $xa(x) xb(x) 右式 4. (1)左式x(a(x) yb(y) 右式(2)左式$x(a(x) $yb(y) $xa(x) $yb(y) 右式(3)左式x(a(x) yb(y) 右式(4)左式$x(a(x) $yb(y) 右式(5)左式x(a(x) yb(y) 右式 5. 由$x(p(x) q(x) $xp(x) $xq(x)知$x(p(x) q(x) ($xp(x) $xq(x)习题2.41.（1）反式（xp(x) xq(x)）($xq(x) yr(y) x(p(x) q(x) ) ($zq(z) yr(y) x$zy(p(x) q(x) (q(z) r(y) (2)反式yp(y) (xq(x) xr(x) yp(y) x(q(x) r(x)yx(p(y) (q(x) r(x) (3)反式$xyp(x,y) ($xq(x,y) r(x) $uvp(u,v) ($uq(u,y) r(x) $uv(p(u,v) (q(u,y) r(x) (4)反式y$x(p(x) q(x,y) yr(y) $xp(x) y($x(p(x) q(x,y) p(x) yr(y) y$xp(x) yr(y) $xp(x) yr(y) $xy(p(x) r(y) (5)反式$xp(x) $xq(x) $x(p(x) q(x)2. (1) 反式的skolem范式为：xy(p(x) q(x) (q(f(x) r(y) (2) 反式的skolem范式为: y x(p(y) (q(x) r(x) (3) 反式的skolem范式为: v(p(a,v) (q(a,y) r(x) (4) 反式的skolem范式为: y(p(a) r(y) (5) 反式的skolem范式为: p(a) q(a)3.不正确。由于$xp(x,y) $xq(x) $x(p(x,y) q(x),故（$xp(x,y) $xq(x)）$yr(y) $x(p(x,y) q(x) $zr(z)习题2.51.由p37例2.1.3知，即证明x(m(x) d(x) m(a) d(a)x(m(x) d(x) 前提m(a) d(a) ,vsm(a) 前提d(a) ,mp2. (1) x(p(x) q(x) 前提 p(z) q(z) ,vs yq(y) 前提 q(z) ,vs p(z) ,拒取式 xp(x) ,ug (2) $x(p(x) q(x) 假设前提 x(p(x) q(x) ,q1,e10 $xp(x) 前提 p(c) ,es p(c) q(c) ,vs p(c) p(c) q(c) ,合取引入 f ,e21,e17 故反式成立 (3)xp(x) 附加前提 p(y) ,vs x(p(x) q(x) 前提 p(y) q(y) ,vs q(y) ,mp xq(x) ,ug xp(x) xq(x) cp (4)$x(p(x) r(x) 前提 p(c) r(c) ,es x(p(x) q(x) 前提 p(c) q(c) ,vs xq(x) 前提 q(c) ,vs p(c) ,拒取式，e1 r(c) ,mp $xr(x) .eg (5)$x(p(x) q(x) 前提 p(c) q(c) ,es p(c) 化简 x(p(x) q(x) r(x) 前提 p(c) q(c) r(c) ,vs q(c) r(c) ,mp $x(q(x) r(x) ,eg3.(1)$xp(x) 附加前提 p(c) ,es ($xp(x) q(a) 前提 xp(x) q(a) ,q3,e11 p(c) q(a) ,vs q(a) ,析取三段论 $xp(x) q(a) cp(2)x(p(x) q(x) 前提 p(y) q(y) ,vs xp(x) 前提 p(y) ,vs q(y) ,析取三段论 xq(x) ,ug(3)x(p(x) q(x) 前提 $x（p(x) q(x)） ,q4,e11 p(c) q(c) ,es xp(x) 前提 p(c) ,vs q(c) ,析取三段论 $xq(x) ,eg xq(x) ,q44.(1)为真。 $yp(y) 前提 p(c) ,es x(p(x) q(x) 前提 p(c) q(c) ,vs q(c) ,mp $zq(z) ,eg (2)为假。构造