离散数学习题答案(2007042746)

1、离散数学习题答案习题一及答案： （ P14-15）14、将下列命题符号化：（ 5）李辛与李末是兄弟解：设 p：李辛与李末是兄弟，则命题符号化的结果是 p （ 6）王强与刘威都学过法语解：设 p：王强学过法语； q：刘威学过法语；则命题符号化的结果是p q（ 9）只有天下大雨，他才乘班车上班解：设p：天下大雨； ：他乘班车上班；则命题符号化的结果是 qpq（ 11）下雪路滑，他迟到了解：设 p：下雪； q：路滑； r ：他迟到了；则命题符号化的结果是( pq)r15、设 p：2+3=5.q：大熊猫产在中国.r：太阳从西方升起.求下列复合命题的真值：（ 4） (pqr )(pq)r )解： p=1

2、 ， q=1， r=0 ，(pqr )(110)1，(pq)r )(11)0)(00)1(p qr )( pq)r )1 1119、用真值表判断下列公式的类型：（ 2） ( pp)q解：列出公式的真值表，如下所示：pqpqp) ( pp)q( p001111011010100101110001由真值表可以看出公式有3 个成真赋值，故公式是非重言式的可满足式。20、求下列公式的成真赋值：（ 4）( pq)q解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是：( pq)1p0q0q0所以公式的 成真赋值有： 01，10， 11。习题二及答案： （ P38）5、求下列公式的主析取

3、范式，并求成真赋值：（ 2） (pq)(qr )解：原式( pq)q rqr( pp) q r(p qr )( pq r )m3m7 ，此即公式的主析取范式，所以成真赋值为011，111。6、求下列公式的主合取范式，并求成假赋值：（ 2） ( pq)(pr )解：原式( pp r ) ( p q r )( p q r )M 4 ，此即公式的主合取范式，所以成假赋值为 100。7、求下列公式的主析取范式，再用主析取范式求主合取范式：（ 1） ( p q) r解：原式pq(rr )(pp)(qq)r )( pqr)( pq)r(pq)r(pq) r(pq ) r (pqr(pqr)(pq)r(pq

4、)r(pq) r (pqrmmmmm，此即主析取范式。13567主析取范式中没出现的极小项为m0 ，m2 ，m4 ，所以主合取范式中含有三个极大项M 0 ， M 2 ，M4，故原式的主合取范式M0M2M4。9、用真值表法求下面公式的主析取范式：（ 1） ( pq)(pr )解：公式的真值表如下：pqrppqp r( p q) ( p r )00010000011011010110101111111000101101010111001011110101由真值表可以看出成真赋值的情况有7 种，此 7 种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式m1 m2m3 m4m5 m6m7习题三

5、及答案： （ P52-54）11、填充下面推理证明中没有写出的推理规则。前提：pq,qr , rs, p结论： s证明： p前提引入pq前提引入 q析取三段论qr前提引入 r析取三段论rs前提引入 s假言推理15、在自然推理系统P 中用附加前提法证明下面推理：（ 2）前提：( pq)(rs),( st)u结论：pu证明：用附加前提证明法。 p附加前提引入pq附加( pq)( rs) 前提引入rs假言推理 s化简st附加(st)u前提引入 u假言推理故推理正确。16、在自然推理系统 P 中用归谬法证明下面推理：（ ）前提：pq ， r q，rs1结论：p证明：用归谬法 p结论的否定引入pq前提引

6、入q假言推理rq前提引入r析取三段论rs前提引入 r化简 rr合取由于 rr0，所以推理正确。17、在自然推理系统 P 中构造下面推理的证明：只要 A 曾到过受害者房间并且11 点以前没离开， A 就是谋杀嫌犯。 A 曾到过受害者房间。如果 A 在 11 点以前离开，看门人会看见他。看门人没有看见他。所以，A 是谋杀嫌犯。解：设 p：A 到过受害者房间， q： A 在 11 点以前离开， r： A 是谋杀嫌犯， s：看门人看见过 A。则前提： ( pq) r ， p ， qs ， s结论： r证明：q s前提引入s前提引入q拒取式p前提引入pq合取引入( pq)r前提引入r假言推理习题四及答案

7、： （ P65-67）5、在一阶逻辑中将下列命题符号化：（ 2）有的火车比有的汽车快。解：设 F(x)： x 是火车， G(y)： y 是汽车， H(x,y)： x 比 y 快；则命题符号化的结果是：x y( F ( x)G ( y)H ( x, y)（ 3）不存在比所有火车都快得汽车。解：设 F(x)： x 是汽车， G(y)： y 是火车， H(x,y)： x 比 y 快；则命题符号化的结果是：x( F ( x)y(G ( y)H ( x, y) 或x( F ( x)y(G( y)H (x, y)9、给定解释I 如下：(a) 个体域为实数集合 R 。(b) 特定元素 a0 。(c) 函数

8、f ( x, y)xy, x, y R 。(d) 谓词 F ( x, y) : xy, G( x, y) : xy, x, yR 。给出以下公式在I 下的解释，并指出它们的真值：（ ） xy( F ( f ( x, y), a)G( x, y)2解：解释是：x y(x y 0x y) ，含义是：对于任意的实数x， y，若 x-y=0 则 x<y。该公式在I 解释下的真值为假。14、证明下面公式既不是永真式也不是矛盾式：（ ）x(F ( x)y(G( y) H ( x, y)1解：取解释 I 如下：个体域为全总个体域，F (x) ： x 是兔子， G ( y) ： y 是乌龟， H ( x

9、, y) ： x 比 y 跑得快 ，则该公式在解释I 下真值是1；取解释 I'如下： H ( x, y) ： x 比 y 跑得慢，其它同上，则该公式在解释 I ' 下真值是0；故公式（ 1）既不是永真式也不是矛盾式。此题答案不唯一，只要证明公式既不是永真式也不是矛盾式的每个解释合理即可。习题五及答案： （ P80-81）15、在自然推理系统N 中，构造下面推理的证明：（ 3）前提：x(F ( x)G (x) ， xG( x)结论： xF ( x)证明：xG( x)前提引入x G ( x)置换G (c)UI 规则x( F (x)G (x)前提引入F (c) G (c)UI 规则F

10、 (c)析取三段论xF ( x)EG 规则22、在自然推理系统N 中，构造下面推理的证明：（ 2）凡大学生都是勤奋的。王晓山不勤奋。所以王晓山不是大学生。解：设 F(x)： x 为大学生， G(x) ：x 是勤奋的， c：王晓山则前提：x(F ( x)G ( x) ，G (c)结论：F (c)证明：x( F (x) G ( x)前提引入F (c) G (c)UI 规则G (c)前提引入F (c)拒取式25、在自然推理系统N 中，构造下面推理的证明：每个科学工作者都是刻苦钻研的，每个刻苦钻研而又聪明的人在他的事业中都将获得成功。王大海是科学工作者， 并且是聪明的。所以， 王大海在他的事业中将获得

11、成功。 （个体域为人类集合）解：设 F(x)：x 是科学工作者， G(x)：x 是刻苦钻研的， H(x) ：x 是聪明的， I(x) ：x 在他的事业中获得成功， c：王大海则前提：x(F ( x)G ( x) ， x(G ( x) H ( x)I ( x) ， F (c) H (c)结论： I (c)证明：F (c)H (c)前提引入F (c)化简H (c)化简x( F (x)G ( x)前提引入F (c)G (c)UI 规则G (c)假言推理G (c)H (c)合取引入x(G( x)H (x)I (x)前提引入G (c)H (c) I (c)UI 规则I (c)假言推理习题六及答案习题七及

12、答案： （ P132-135）*22 、给定 A1,2,3,4，A 上的关系 R1,3 , 1,4 , 2,3 , 2, 4 , 3,4，试（ 1）画出 R 的关系图；（ 2）说明 R 的性质。解：（1）1234R 是反自反的，不是自反的；（2）R 的关系图中每个顶点都没有自环，所以R 的关系图中任意两个顶点如果有边的都是单向边，故R 是反对称的，不是对称的；R 的关系图中没有发生顶点 x 到顶点 y 有边、顶点 y 到顶点 z 有边，但顶点 x到顶点 z 没有边的情况，故 R 是传递的。26 设 A 1,2,3,4,5,6， R 为 A 上的关系， R 的关系图如图 7.13 所示：（ 1）

13、求 R2 , R3 的集合表达式；（ 2）求 r(R), s(R), t(R) 的集合表达式。解：（1）由 R 的关系图可得 R1,5, 2,5, 3,1, 3,3, 4,5所以 R2R R3,1 , 3,3, 3,5， R3R2 R3,1 ,3,3, 3,5，可得 Rn3,1, 3,3, 3,5,当 n>=2 ；（ 2） r(R)=RI A1,5 , 2,5 , 3,1 ,3,3,4,5 , 1,1 , 2,2 ,4,4 ,5,5 , 6,6 ，s(R)RR 11,5 , 5,1 , 2,5, 5,2, 3,1 , 1,3, 3,3,4,5, 5,4t (R)RR2R 3. RR21,

14、5 , 2,5, 3,1,3,3,3,5 , 4,546、分别画出下列各偏序集A, R的哈斯图，并找出 A 的极大元、极小元、最大元和最小元。（ 1） Ra, d , a,c , a, b , a,e , b, e , c, e , d , eI A解：哈斯图如下：ebcdafA 的极大元为 e、 f，极小元为 a、f； A 的最大元和最小元都不存在。48、设A, R和B,S为偏序集，在集合AB 上定义关系T 如下：a1, b1, a2 ,b2AB,a1, b1T a2 ,b2a1Ra2b1Sb2证明 T 为 AB 上的偏序关系。证明：（1）自反性：任取a1,b1AB，则：R为偏序关系，具有自

15、反性，a1Ra1S为偏序关系，具有自反性，b1Sb1a1Ra1b1Sb1又 a1 ,b1 T a2 , b2a1Ra2 b1Sb2，a1, b1T a1 ,b1，故 T具有自反性（ 2）反对称性：任取 a1,b1 , a2 ,b2A B，若 a1 ,b1 T a2 , b2 且 a2 ,b2T a1 ,b1 ，则有：a1 Ra2b1Sb2（1）a2 Ra1b2Sb1（2）a1Ra2a2 Ra1，又 R为偏序关系，具有反对称性，所以a1a2b Sb，又 为偏序关系，具有反对称性，所以bbb SbS122112a1, b1a2, b2 ，故 T具有反对称性（ 3）传递性：任取 a1,b1 , a2

16、 , b2，a3 ,b3A B，若 a1 ,b1 T a2 , b2且 a2 ,b2 T a3, b3 ，则有：a1, b1 T a2 ,b2a1Ra2b1Sb2a2 ,b2 T a3 , b3a2 Ra3b2Sb3a1Ra2 a2 Ra3 , 又 R为偏序关系，具有传递性，所以a1Ra3b1 Sb2b2 Sb3 ,又 S为偏序关系，具有传递性，所以b1Sb3a1Ra3b1Sb3a1, b1Ta3 ,b3，故 T 具有传递性。综合（ 1）（2）（3）知T 具有自反性、反对称性和传递性，故T 为 AB 上的偏序关系。习题九及答案： （ P179-180）8、S=QQ,Q 为有理数集，为S上的二元

17、运算，a,b , x,yS有a,bx,yax,ay+b（ 1） 运算在 S上是否可交换、可结合？是否为幂等的？（ 2） 运算是否有单位元、零元？如果有，请指出，并求出S中所有可逆元素的逆元。解：（1）x, ya,bxa,xb+yax,bx+ya,bx, y运算不具有交换律x, ya,bc,dax,bx+yc,dacx,adx+bx+y而 x, ya,bc,dx, y * ac,ad+bxac,xad+xb+yacx,adx+bx+yx, ya,bc,d运算有结合律任取 a,bs，则有：a,ba,ba2 ,adba,b运算无幂等律（ 2）令 a,b *x, ya,b 对a,bs均成立则有： ax

18、,ay+ba,b对a,bs均成立axaax10对a,b 成立ay bbay0必定有x 10x1y0y0运算的右单位元为， ，可验证 ， 也为运算的左单位元，1 01 0运算的单位元为，1 0令 a,b*x, yx, y ，若存在x, y 使得对 a,bs上述等式均成立，则存在零元，否则不存在零元。由 a,b*x, yx, yax,ay+bx, yaxxa1 x0ay bya 1y+b0由于 a1 y+b0不可能对a,b s均成立，故 a,b *x, yx, y 不可能对a,b s均成立，故不存在零元；设元素a,b的逆元为x, y，则令，a,b * x, y e 1 0ax1x1a（当 a0）a

19、yb 0bya当 a 0时，a,b 的逆元不存在；当 a0时， a,b 的逆元是1 ,baa11、设S，.,10，问下面的运算能否与S构成代数系统S，?12如果能构成代数系统则说明运算是否满足交换律、结合律，并求运算的单位元和零元。（ 3） xy =大于等于 x和y的最小整数 ；解：（3）由 * 运算的定义可知： xy=max(x,y) ，x,yS,有xyS，故运算在 S上满足封闭性，所以运算与非空集合 S能构成代数系统；任取 x,yS,有 xy=max(x,y)=max(y,x)=yx,所以运算满足交换律；任取 x,y,zS,有 ( xy)z=max(max(x,y),z)=max(x,y,

20、z)=max(x,max(y,z)=x (yz), 所以运算满足结合律；任取 xS，有 x 1=max(x,1)=x=max(1,x)=1x,所以运算的单位元是1；任取 xS，有 x10=max(x,10)=10=max(10,x)=10 x,所以运算的零元是10；16、设 V11,2,3, ,1 , 其中 x y表示取x和 y之中较大的数。V25,6 , ,6，其中 xy表示取x和 y之中较小的数。求出V1和 V2的所有的子代数。指出哪些是平凡的子代数，哪些是真子代数。解：（ 1） V1的所有的子代数是：1,2,3,1,1 ,1, 1,2,1, 1,3,1；V1的平凡的子代数是：1,2,3

21、,1,1, ,1；V1的真子代数是：1,1, 1,2,1,1,3,1；（ 2） V2的所有的子代数是：5,6 , ,6 ，6,6 ；V2的平凡的子代数是：5,6 , ,6 ，6, ,6；V2的真子代数是：6,6 。习题十一及答案： （ P218-219）1、图 11.11给出了 6 个偏序集的哈斯图。判断其中哪些是格。如果不是格，说明理由解：（ a）、（ c）、（ f）是格；因为任意两个元素构成的集合都有最小上界和最大下界；（ b）不是格，因为 d,e的最大下界不存在；（ d）不是格，因为 b,c的最小上界不存在；（ e）不是格，因为 a,b 的最大下界不存在。2、下列各集合低于整除关系都构成偏序集，判断哪些偏序集是格。（ 1） L=1 ， 2， 3， 4， 5；（ 2）