离散数学习题答案解析.pdf

《离散数学习题答案解析.pdf》由会员分享，可在线阅读，更多相关《离散数学习题答案解析.pdf（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、WORD 整理版离散数学习题答案离散数学习题答案习题一及答案：习题一及答案：（P14-15P14-15）1414、将下命题符号化：、将下命题符号化：（5 5）辛与末是兄弟）辛与末是兄弟解：设解：设 p p：辛与末是兄弟，则命题符号化的结果是：辛与末是兄弟，则命题符号化的结果是p p（6 6）王强与刘威学过法语）王强与刘威学过法语解：设解：设 p p：王强学过法语；：王强学过法语；q q：刘威学过法语；则命题符号化的结果是：刘威学过法语；则命题符号化的结果是（9 9）只有天下大雨，他才乘班车上班）只有天下大雨，他才乘班车上班解：设解：设 p p：天下大雨；：天下大雨；q q：他乘班车上班；则命题

2、符号化的结果是：他乘班车上班；则命题符号化的结果是q p（1111）下雪，他迟到）下雪，他迟到解：设解：设 p p：下雪；：下雪；q q：；：；r r：他迟到；则命题符号化的结果是：他迟到；则命题符号化的结果是(pq)r1515、设、设 p p：2+3=5.2+3=5.q q：大熊猫产在中国：大熊猫产在中国.r r：太阳从西方升起：太阳从西方升起.求下复合命题的真值：求下复合命题的真值：（4 4）(pqr)(pq)r)解：解：p=1p=1，q=1q=1，r=0r=0，p q(pqr)(110)1，(pq)r)(11)0)(0 0)1(pqr)(pq)r)1111919、用真值表判断下公式的类型

3、：、用真值表判断下公式的类型：（2 2）(p p)q解：出公式的真值表，如下所示：解：出公式的真值表，如下所示：pqpq(p p)(p p)q专业资料学习参考WORD 整理版0 00 01 11 10 01 10 01 11 11 10 00 01 10 01 10 01 11 10 00 01 10 01 11 1由真值表可以看出公式有由真值表可以看出公式有 3 3 个成真赋值，故公式是非重言式的可满足式。个成真赋值，故公式是非重言式的可满足式。2020、求下公式的成真赋值：、求下公式的成真赋值：（4 4）(p q)q解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是：解

4、：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是：(pq)1p 0q 0q 0所以公式的所以公式的成真赋值有：成真赋值有：0101，1010，1111。习题二及答案：习题二及答案：（P38P38）5 5、求下公式的主析取范式，并求成真赋值：、求下公式的主析取范式，并求成真赋值：（2 2）(p q)(qr)解：原式解：原式(p q)qr q r(p p)qr(pqr)(pqr)m3m7，此即公式的主析取范式，此即公式的主析取范式，所以成真赋值为所以成真赋值为 011011，111111。*6*6、求下公式的主合取范式，并求成假赋值：、求下公式的主合取范式，并求成假赋值：（2

5、2）(pq)(p r)解：原式解：原式(pp r)(p q r)(p q r)M4，此即公式的主合取范式，此即公式的主合取范式，专业资料学习参考WORD 整理版所以成假赋值为所以成假赋值为 100100。7 7、求下公式的主析取范式，再用主析取范式求主合取范式：、求下公式的主析取范式，再用主析取范式求主合取范式：（1 1）(pq)r解：原式解：原式 pq(r r)(p p)(q q)r)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)m1m3m5m6m7，此即主析取范式。，此即主析取范式。主析取范式中没出现的极小项为主析取范式中没出

6、现的极小项为m0，m2，m4，所以主合取范式中含有三个极大项所以主合取范式中含有三个极大项M0，M2，M4，故原式的主合取范式，故原式的主合取范式 M0M2M4。9 9、用真值表法求下面公式的主析取范式：、用真值表法求下面公式的主析取范式：（1 1）(p q)(pr)解：公式的真值表如下：解：公式的真值表如下：pqr0 01 10 01 10 01 1pp qp r(p q)(pr)0 00 00 00 01 11 10 00 01 11 10 00 01 11 11 11 10 00 00 00 01 11 11 11 10 01 10 01 10 00 00 01 11 11 11 11

7、1专业资料学习参考WORD 整理版1 11 11 11 10 01 10 00 01 11 10 00 01 11 1由真值表可以看出成真赋值的情况有由真值表可以看出成真赋值的情况有 7 7 种，此种，此 7 7 种成真赋值所对应的极小项的析取即为主析种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式取范式，故主析取范式 m1m2m3m4m5m6m7习题三及答案：习题三及答案：（P52-54P52-54）1111、填充下面推证明中没有写出的推规则。、填充下面推证明中没有写出的推规则。前提：前提：p q,q r,r s,p结论：结论：s s证明：证明：p p前提引入前提引入p q前提引入

8、前提引入 q q析取三段论析取三段论q r前提引入前提引入 r r析取三段论析取三段论r s前提引入前提引入 s s假言推假言推1515、在自然推系统、在自然推系统P P 中用附加前提法证明下面推：中用附加前提法证明下面推：（2 2）前提：）前提：(pq)(r s),(st)u专业资料学习参考WORD 整理版结论：结论：p u证明：用附加前提证明法。证明：用附加前提证明法。p p附加前提引入附加前提引入p q附加附加(p q)(r s)前提引入前提引入r s假言推假言推 s s化简化简st附加附加(st)u前提引入前提引入 u u假言推假言推故推正确。故推正确。1616、在自然推系统、在自然推

9、系统P P 中用归谬法证明下面推：中用归谬法证明下面推：（1 1）前提：）前提：p q，r q，rs结论：结论：p证明：用归谬法证明：用归谬法 p p结论的否定引入结论的否定引入p q前提引入前提引入q假言推假言推r q前提引入前提引入r析取三段论析取三段论rs前提引入前提引入 r r化简化简专业资料学习参考WORD 整理版r r合取合取由于由于r r 0，所以推正确。，所以推正确。1717、在自然推系统、在自然推系统P P 中构造下面推的证明：中构造下面推的证明：只要只要 A A 曾到过受害者房间并且曾到过受害者房间并且 1111 点以前没离开，点以前没离开，A A 就是谋杀嫌犯。就是谋杀嫌

10、犯。A A 曾到过受害者房间。如曾到过受害者房间。如果果 A A 在在 1111 点以前离开，看门人会看见他。看门人没有看见他。所以，点以前离开，看门人会看见他。看门人没有看见他。所以，A A 是谋杀嫌犯。是谋杀嫌犯。解：设解：设 p p：A A 到过受害者房间，到过受害者房间，q q：A A 在在 1111 点以前离开，点以前离开，r r：A A 是谋杀嫌犯，是谋杀嫌犯，s s：看门人看见过：看门人看见过A A。则前提：则前提：(pq)r，p，q s，s结论：结论：r证明：证明：q s前提引入前提引入s前提引入前提引入q拒取式拒取式p前提引入前提引入p q合取引入合取引入(pq)r前提引入前

11、提引入r假言推假言推习题四及答案：习题四及答案：（P65-67P65-67）5 5、在一阶逻辑中将下命题符号化：、在一阶逻辑中将下命题符号化：（2 2）有的火车比有的汽车快。）有的火车比有的汽车快。专业资料学习参考WORD 整理版解：解：设设 F(x)F(x)：x x 是火车，是火车，G(y)G(y)：y y 是汽车，是汽车，H(x,y)H(x,y)：x x 比比 y y 快；则命题符号化的结果是：快；则命题符号化的结果是：xy(F(x)G(y)H(x,y)（3 3）存在比所有火车快的汽车。）存在比所有火车快的汽车。解：方法一：解：方法一：设设 F(x)F(x)：x x 是汽车，是汽车，G(y

12、)G(y)：y y 是火车，是火车，H(x,y)H(x,y)：x x 比比 y y 快；则命题符号化的结果是：快；则命题符号化的结果是：x(F(x)y(G(y)H(x,y)或或x(F(x)y(G(y)H(x,y)方法二：方法二：设设 F(x)F(x)：x x 是火车，是火车，G(y)G(y)：y y 是汽车，是汽车，H(x,y)H(x,y)：x x 比比 y y 快；则命题符号化的结果是：快；则命题符号化的结果是：x(G(x)y(F(y)H(x,y)或或xy(G(x)(F(y)H(x,y)9 9、给定解释、给定解释 I I 如下：如下：(a)(a)个体域为实数集合个体域为实数集合 R R。(b

13、)(b)特定元素特定元素a 0。(c)(c)函数函数f(x,y)x y,x,yR。(d)(d)谓词谓词F(x,y):x y,G(x,y):x y,x,yR。给出以下公式在给出以下公式在 I I 下的解释，并指出它们的真值：下的解释，并指出它们的真值：（2 2）xy(F(f(x,y),a)G(x,y)y 0 x y)，含义是：对于任意的实数，含义是：对于任意的实数 x x，y y，x-y=0 x-y=0 则则 xyx=2；（2 2）r(R)=Rs(R)Rt(R)RIA1,5,2,5,3,1,3,3,4,5,1,1,2,2,4,4,5,5,6,6，R11,5,5,1,2,5,5,2,3,1,1,3

14、,3,3,4,5,5,4R2R3.RR21,5,2,5,3,1,3,3,3,5,4,54141、设设A=1A=1，2 2，3 3，44，R R为为A A上 的 二 元 关 系，a,b,c,d A A，a,b R c,d ab cd（1）证明 R 为等价关系；（2）求 R 导出的划分。（1 1）只需证明）只需证明 R R 具有自反性、对称性和传递性即可，证明过程如下：具有自反性、对称性和传递性即可，证明过程如下：（a）任取 a,b A A，有a b a b，a,b R a,b，所以 R 具有自反性；（b）任取 a,b,c,d A A，a,b R c,d，则有a b c d，c d a b，c,d

15、 R a,b，所以 R 具有对称性；（c）任取 a,b,c,d,e,f A A，a,b R c,d 且 c,d R e,f，则有a b c d且cd e f，ab e f，a,b R e,f，所以 R 具有传递性，综合（a）（b）（c）可知：R 为集合A A上的等价关系；（2）先求出集合A A的结果：A A 1,1,1,2,1,3,1,4,2,1,2,2,2,3,2,4,3,1,3,2,3,3,3,4,4,1,4,2,4,3,4,4 再分别求集合A A各元素的等价类，结果如下：1,1R1,1,专业资料学习参考WORD 整理版1,2 R 2,1R1,2,2,1,1,3 R 2,2 R3,1R1,

16、3,2,2,3,1,1,4 R 2,3 R3,2 R 4,1R1,4,2,3,3,2,4,1,2,4 R3,3 R 4,2 R 2,4,3,3,4,2,3,4 R 4,3 R3,4,4,3,4,4 R 4,4。等价关系 R 导出的划分就是集合 A 关于 R 的商集A/R，而集合 A 关于 R 的商集A/R是由 R 的所有等价类作为元素构成的集合，所以等价关系R 导出的划分是：1,1,1,2,2,1,1,3,2,2,3,1,1,4,2,3,3,2,4,1,2,4,3,3,4,2,3,4,4,3,4,4 4646、分别画出下各偏序集、分别画出下各偏序集A,R的哈斯图，的哈斯图，并找出并找出 A A

17、 的极大元、的极大元、极小元、最大元和最小元。极小元、最大元和最小元。（1 1）Ra,d,a,c,a,b,a,e,b,e,c,e,d,e解：哈斯图如下：解：哈斯图如下：eIAbcdafA A 的极大元为的极大元为 e e、f f，极小元为，极小元为 a a、f f；A A 的最大元和最小元存在。的最大元和最小元存在。*22*22、给定、给定A1,2,3,4，A A 上的关系上的关系R 1,3,1,4,2,3,2,4,3,4，试，试（1 1）画出）画出 R R 的关系图；的关系图；（2 2）说明）说明 R R 的性质。的性质。专业资料学习参考WORD 整理版解：解：（1 1）1234（2 2）R

18、 R 的关系图中每个顶点没有自环，所以的关系图中每个顶点没有自环，所以R R 是反自反的，是自反的；是反自反的，是自反的；R R 的关系图中任意两个顶点如果有边的是单向边，故的关系图中任意两个顶点如果有边的是单向边，故R R 是反对称的，是对称是反对称的，是对称的；的；R R 的关系图中没有发生顶点的关系图中没有发生顶点 x x 到顶点到顶点 y y 有边、顶点有边、顶点y y 到顶点到顶点 z z 有边，但顶点有边，但顶点x x 到到顶点顶点 z z 没有边的情况，故没有边的情况，故 R R 是传递的。是传递的。*48*48、设设A,R 和 B,S为偏序集，在集合为偏序集，在集合AB上定义关

19、系上定义关系 T T 如下：如下：a1,b1,a2,b2AB,a1,b1T a2,b2 a1Ra2b1Sb2证明证明 T T 为为AB上的偏序关系。上的偏序关系。证明：证明：（1 1）自反性：）自反性：任取 a1,b1AB，则：R为偏序关系，具有自反性，a1Ra1S为偏序关系，具有自反性，b1Sb1a1Ra1 b1Sb1又 a1,b1T a2,b2 a1Ra2b1Sb2，a1,b1T a1,b1，故T具有自反性（2 2）反对称性：）反对称性：专业资料学习参考WORD 整理版任取 a1,b1,a2,b2AB，若 a1,b1T a2,b2且 a2,b2T a1,b1，则有：a1Ra2b1Sb2a2

20、Ra1b2Sb1（1）（2）a1Ra2 a2Ra1，又R为偏序关系，具有反对称性，所以a1 a2b1Sb2b2Sb1，又S为偏序关系，具有反对称性，所以b1 b2 a1,b1 a2,b2，故T具有反对称性（3 3）传递性：）传递性：任取 a1,b1,a2,b2，a3,b3AB，若 a1,b1T a2,b2且 a2,b2T a3,b3，则有：a1,b1T a2,b2 a1Ra2b1Sb2a2,b2T a3,b3 a2Ra3b2Sb3a1Ra2 a2Ra3,又R为偏序关系，具有传递性，所以a1Ra3b1Sb2b2Sb3,又S为偏序关系，具有传递性，所以b1Sb3a1Ra3 b1Sb3 a1,b1T

21、 a3,b3，故T具有传递性。综合（综合（1 1）（2 2）（3 3）知）知 T T 具有自反性、反对称性和传递性，故具有自反性、反对称性和传递性，故 T T 为为AB上的偏序关系。上的偏序关系。专业资料学习参考WORD 整理版习题九及答案：习题九及答案：（P179-180P179-180）8 8、S=Q Q,Q 为有理数集，为S上的二元运算，a,b,x,y S有a,b x,y ax,ay+b（1 1）运算在S上是否可交换、可结合？是否为幂等的？（2 2）运算是否有单位元、零元？如果有，请指出，并求出 S中所有可逆元素的逆元。解：解：（1 1）x,y a,b xa,xb+y ax,bx+y a

22、,b x,y运算不具有交换律x,y a,b c,d ax,bx+y c,d acx,adx+bx+y而 x,y a,b c,d x,y*ac,ad+b xac,xad+xb+y acx,adx+bx+yx,y a,b c,d运算有结合律任取 a,b s，则有：a,b a,b a2,ab b a,b运算无幂等律（2 2）专业资料学习参考WORD 整理版令 a,b*x,y a,b 对 a,b s均成立则有：ax,ay+b a,b 对 a,b s均成立ax 1 0ax a对a,b成立ayb bay 0 x 1 0 x 1必定有y 0y 0运算的单位元为 1，0运算的右单位元为 1，0，可验证 1，0

23、 也为运算的左单位元，令 a,b*x,y x,y，若存在 x,y 使得对 a,b s上述等式均成立，则存在零元，否则不存在零元。由 a,b*x,y x,y ax,ay+b x,yax xa 1x 0ayb ya 1y+b 0由于a 1y+b 0不可能对 a,b s均成立，故 a,b*x,y x,y 不可能对 a,b s均成立，故不存在零元；设元素 a,b 的逆元为 x,y，则令 a,b*x,y e 1，01x ax 1a（当a 0）ayb 0y ba当a 0时，a,b 的逆元不存在；当a 0时，a,b 的逆元是1b,aa1111、设S1，2，.,10，问下面的运算能否与S构成代数系统 S，?如

24、果能构成代数系统则说明运算是否满足交换律、结合律，并求运算的单位元和零元。（3 3）xy=大于等于x和y的最小整数；解：解：（3 3）由）由*运算的定义可知：运算的定义可知：xy=max(x,y)，专业资料学习参考WORD 整理版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,z)=max(x,max(y,z)=x(yz),所以运算满足结合律；任取xS，有x1=max(x,1)=x=max(1,x)=

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

26、代数是：5,6,6，6,6；V2的真子代数是：6,6。习题十一及答案：习题十一及答案：（P218-219P218-219）1 1、图、图 11.1111.11 给出给出6 6 个偏序集的哈斯图。判断其中哪些是格。如果是格，说明由个偏序集的哈斯图。判断其中哪些是格。如果是格，说明由解：解：（a a）、（c c）、（f f）是格；因为任意两个元素构成的集合有最小上界和最大下界；）是格；因为任意两个元素构成的集合有最小上界和最大下界；（b b）是格，因为）是格，因为d,ed,e的最大下界存在；的最大下界存在；专业资料学习参考WORD 整理版（d d）是格，因为）是格，因为b,cb,c的最小上界存在；

27、的最小上界存在；（e e）是格，因为）是格，因为a,ba,b的最大下界存在。的最大下界存在。2 2、下各集合低于整除关系构成偏序集，判断哪些偏序集是格。、下各集合低于整除关系构成偏序集，判断哪些偏序集是格。（1 1）L=1L=1，2 2，3 3，4 4，55；（2 2）L=1L=1，2 2，3 3，6 6，1212；解：画出哈斯图即可判断出：解：画出哈斯图即可判断出：（1 1）是格，）是格，（2 2）是格。）是格。4 4、设、设 L L 是格，求以下公式的对偶式：是格，求以下公式的对偶式：（2 2）a(bc)(ab)(ac)解：对偶式为：解：对偶式为：a(bc)(ab)(ac)，参见，参见 P

28、208P208 页定义页定义 11.211.2。6 6、设、设 L L 为格，为格，a,b,cL，且a b c，证明ab bc。证明：a b,ab b,b c,bc b,ab bc9 9、针对图、针对图 11.1111.11 中的每个格，如果格中的元素存在补元，则求出这些补元。中的每个格，如果格中的元素存在补元，则求出这些补元。解：解：（a a）图：）图：a,da,d 互为补元，其中互为补元，其中 a a 为全下界，为全下界，d d 为全上界，为全上界，b b 和和 c c 没有补元；没有补元；（c c）图：）图：a,fa,f 互为补元，其中互为补元，其中 a a 为全下界，为全下界，f f

29、为全上界，为全上界，c c 和和 d d 的补元是的补元是b b 和和 e e，b b 和和 e e 的补元是的补元是c c和和 d d；（f f）图：）图：a,fa,f 互为补元，其中互为补元，其中 a a 为全下界，为全下界，f f 为全上界，为全上界，b b 和和 e e 互为补元，互为补元，c c 和和 d d 没有补元。没有补元。1010、说明图、说明图 11.1111.11 中每个格是否为分配格、有补格和布尔格，并说明由。中每个格是否为分配格、有补格和布尔格，并说明由。解：解：（a a）图：是一条链，所以是分配格，）图：是一条链，所以是分配格，b b 和和 c c 没有补元，所以是

30、有补格，所以是布尔格；没有补元，所以是有补格，所以是布尔格；（c c）图：）图：a,fa,f 互为补元，互为补元，c c 和和 d d 的补元是的补元是b b 和和 e e，b b 和和 e e 的补元是的补元是c c 和和 d d，所以任何元素皆有补元，是，所以任何元素皆有补元，是有补格；有补格；c(bd)c a c,(cb)(c d)f d d c(bd)(cb)(c d)，所以，所以对对运算满足分配，所以是分配格，所以是布尔格；运算满足分配，所以是分配格，所以是布尔格；（f f）图：经过分析知图（）图：经过分析知图（f f）对应的格只有）对应的格只有 2 2 个五元子格：个五元子格：L1=a,c,d,e,f,L2=a,b,c,d,fL1=a,c,d,e,f,L2=a,b,c,d,f。画出。画出 L1L1和和 L2L2 的哈斯图可知的哈斯图可知 L1L1 和和 L2L2 均同构于钻石格和五角格，根据分配格的充分必要条件（见均同构于钻石格和五角格，根据分配格的充分必要条件（见P213P213 页的定页的定11.511.5）得图（）得图（f f）对应的格是分配格；）对应的格是分配格；c c 和和 d d 没有补元，所以是有补格，所以是布尔格。没有补元，所以是有补格，所以是布尔格。专业资料学习参考