2022年2022年离散数学习题答案 .pdf

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

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

2、()(110)1pqr，()( 11)0)(00)1pqr()()111pqrpqr19、用真值表判断下列公式的类型：（ 2）()ppq解：列出公式的真值表，如下所示：pqpq()pp()ppq0 0 1 1 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 0 1 由真值表可以看出公式有3 个成真赋值，故公式是非重言式的可满足式。20、求下列公式的成真赋值：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 15 页 - - - - - - - - -

3、 （4）()pqq解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是：()10pqq00pq所以公式的成真赋值有： 01，10，11。习题二及答案： （P38）5、求下列公式的主析取范式，并求成真赋值：（2）()()pqqr解：原式()pqqrqr()ppqr()()pqrpqr37mm，此即公式的主析取范式，所以成真赋值为011，111。*6、求下列公式的主合取范式，并求成假赋值：（2）()()pqpr解：原式()()pprpqr()pqr4M，此即公式的主合取范式，所以成假赋值为100。7、求下列公式的主析取范式，再用主析取范式求主合取范式：（1）()pqr解：原式()

4、()()pqrrppqqr()()()()()(pqrpqrpqrpqrpqrpqr()()()()(pqrpqrpqrpqrpqr13567mmmmm，此即主析取范式。主析取范式中没出现的极小项为0m，2m，4m，所以主合取范式中含有三个极大项0M，2M，4M，故原式的主合取范式024MMM。9、用真值表法求下面公式的主析取范式：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 15 页 - - - - - - - - - （1）()()pqpr解：公式的真值表如下：pq

5、rppqpr()()pqpr0 0 0 1 0 0 0 0 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 1 1 1 1 1 0 0 0 1 0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 1 1 1 1 0 1 0 1 由真值表可以看出成真赋值的情况有7 种，此 7 种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式1234567mmmmmmm习题三及答案： （P52-54）11、填充下面推理证明中没有写出的推理规则。前提：,pqqr rs p结论： s 证明： p 前提引入pq前提引入 q 析取三段论qr前提引入 r 析取三段论 rs前提引入 s 假言

6、推理15、在自然推理系统P 中用附加前提法证明下面推理：（2）前提：()(),()pqrsstu结论： pu证明：用附加前提证明法。 p 附加前提引入名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 15 页 - - - - - - - - - pq附加()()pqrs前提引入 rs假言推理 s 化简st附加()stu前提引入 u 假言推理故推理正确。16、在自然推理系统P 中用归谬法证明下面推理：（1）前提： pq，rq， rs结论：p证明：用归谬法 p 结论的否定引入p

7、q前提引入q假言推理rq前提引入r析取三段论 rs前提引入 r 化简 rr合取由于0rr，所以推理正确。17、在自然推理系统P 中构造下面推理的证明：只要 A 曾到过受害者房间并且11点以前没离开， A 就是谋杀嫌犯。 A 曾到过受害者房间。如果 A 在 11点以前离开，看门人会看见他。看门人没有看见他。所以，A 是谋杀嫌犯。解：设 p：A 到过受害者房间， q：A 在 11 点以前离开， r：A 是谋杀嫌犯， s：看门人看见过 A。则前提：()pqr， p ，qs，s结论： r证明： qs前提引入s前提引入q拒取式p前提引入名师资料总结 - - -精品资料欢迎下载 - - - - - - -

8、 - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 15 页 - - - - - - - - - pq合取引入()pqr前提引入r假言推理习题四及答案： （P65-67）5、在一阶逻辑中将下列命题符号化：（2）有的火车比有的汽车快。解：设 F(x)：x 是火车， G(y)：y 是汽车， H(x,y)：x 比 y 快；则命题符号化的结果是：( )( )( , )x y F xG yH x y（3）不存在比所有火车都快的汽车。解：方法一：设 F(x)：x 是汽车， G(y)：y 是火车， H(x,y)：x 比 y 快；则命题符号化的结果是：( )

9、( )( ,)x F xy G yH x y或( )( )( , )x F xy G yH x y方法二：设 F(x)：x 是火车， G(y)：y 是汽车， H(x,y)：x 比 y 快；则命题符号化的结果是：( )( )( , )x G xy F yH x y或( )( )( , )x y G xF yH x y9、给定解释I 如下：(a) 个体域为实数集合R。(b) 特定元素0a。(c) 函数( ,), ,f x yxy x yR。(d) 谓词( , ) :,( , ) :, ,F x yxy G x yxy x yR。给出以下公式在I 下的解释，并指出它们的真值：（2）( , ), )(

10、 ,)x y Ff x yaG x y解：解释是：(0)x y xyxy，含义是：对于任意的实数x，y，若 x-y=0 则 x=2nR当；（2）Ar(R)=RI1,5 , 2,5 , 3,1 , 3,3 , 4,5 , 1,1 , 2, 2 , 4,4 , 5,5 , 6,6，1()R1,5 , 5,1 , 2,5 , 5,2 , 3,1 , 1,3 , 3,3 , 4,5 , 5, 4s RR232()RR.R1,5 , 2,5 , 3,1 , 3,3 , 3,5 , 4,5t RRR41 、 设A=1 ， 2 ， 3 ， 4 ， R为 AA上 的 二 元 关 系 ，,a bc dAA，,a

11、 bRc dabcd（1）证明 R 为等价关系；（2）求 R 导出的划分。（1）只需证明 R 具有自反性、对称性和传递性即可，证明过程如下：（a）任取,a bAA，有abab，,a bRa b，所以 R 具有自反性；（b）任取,a bc dAA，若,a bRc d，则有abcd，cdab，,c dRa b，所以 R 具有对称性；（c）任取,a bc de fAA，若,a bRc d且,c dRe f，则有abcd且cdef，abef，,a bRe f，所以 R 具有传递性，综合（ a） （b） （ c）可知： R 为集合AA上的等价关系；（2）先求出集合AA的结果：1,1, 1,2,1,3,1

12、,4,2,1 ,2,2,2,3,2,4,3,1 ,3,2,3,3,3,4,4,1 ,4,2,4,3,4,4AA再分别求集合AA各元素的等价类，结果如下：1,1 1,1 ,R1,22,1 1,2,2,1 ,RR名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 15 页 - - - - - - - - - 1 2 4 3 1,32,23,11,3,2,2,3,1 ,RRR1,42,33,24,1 1,4,2,3,3,2,4,1 ,RRRR2,43,34,22,4,3,3,4,2

13、,RRR3,44,33,4,4,3,RR4,44,4R。等价关系R 导出的划分就是集合A 关于 R 的商集/AR，而集合A 关于 R 的商集/AR是由 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,446、分别画出下列各偏序集,A R的哈斯图， 并找出 A 的极大元、极小元、最大元和最小元。（1）A,IRa da ca ba eb ec ed e解：哈斯图如下：A 的极大元为 e、f，极小元为 a、f；A 的最大元和最小元都不存在。*22、给

14、定1,2,3, 4A，A 上的关系1,3 , 1,4 , 2,3 , 2,4 , 3,4R，试（1）画出 R 的关系图；（2）说明 R 的性质。解： （1）（2）R 的关系图中每个顶点都没有自环，所以R 是反自反的，不是自反的；R 的关系图中任意两个顶点如果有边的都是单向边，故R 是反对称的，不是对e a b c d f 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 15 页 - - - - - - - - - 称的；R 的关系图中没有发生顶点x 到顶点 y 有边、顶

15、点 y 到顶点 z 有边，但顶点x到顶点 z 没有边的情况，故R 是传递的。*48、设,B,SA R 和为偏序集，在集合 AB上定义关系 T 如下：112211221212,AB,a baba b Taba Rab Sb证明 T 为 AB 上的偏序关系。证明： （1）自反性：1111111111112212121111,ABRRSb SbRb Sb,Ta baaaaa b T aba RabSba b T a b任取，则：为偏序关系，具有自反性，为偏序关系，具有自反性，又，故具有自反性（2）反对称性：112211222211121221211221121221121122,AB,RSbb,Ta

16、 ba ba b T aba bT a ba Rab Sba Rab Sba Raa Raaab Sbb Sba ba b任取，若且，则有：（1）（2），又为偏序关系，具有反对称性，所以，又为偏序关系，具有反对称性，所以，故具有反对称性（3）传递性：11223311222233112212122233232312231312231313131133,AB,R,Sb Sbb Sb,Ta ba ba ba b T a bab T a ba b T a ba Rab Sba bT a ba Rab Sba Raa Raa Rab Sbb Sba Raa b T a b任取，若且，则有：又为偏序关系，

17、具有传递性，所以又 为偏序关系，具有传递性，所以，故具有传递性。综合（ 1） （2） （3）知 T 具有自反性、反对称性和传递性，故T 为 AB上的偏序关系。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 15 页 - - - - - - - - - 习题九及答案： （P179-180）8、S=QQ,QSa,b , x,ya,bx,yax,ay+bS为有理数集，为上的二元运算，有（1）S运算在上是否可交换、可结合？是否为幂等的？（2）S运算是否有单位元、零元？如果有，请

18、指出，并求出中所有可逆元素的逆元。解： （1）,a,bxa,xb+yax,bx+ya,b,x yx y运算不具有交换律,a,bc,dax,bx+yc,dacx,adx+bx+y,a,bc,d,* ac,ad+bxac,xad+xb+yacx,adx+bx+y,a,bc,dx yx yx yx y而运算有结合律2a,bsa,ba,ba ,a,babb任取，则有：运算无幂等律（2）a,b *,a,ba,bsax,ay+ba,ba,bsaxaa x10a,baybbay0 x10 x1y0y01 01 01 0 x y令对均成立则有：对均成立对成立必定有运算的右单位元为， ，可验证， 也为运算的左单

19、位元，运算的单位元为，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 15 页 - - - - - - - - - a,b *,a,bsa,b *,ax,ay+b,a1 x0axxa1 y+b0aybya1 y+b0a,bsa,b *,a,bsx yx yx yx yx yx yx yx y令，若存在使得对上述等式均成立，则存在零元，否则不存在零元。由由于不可能对均成立，故不可能对均成立，故不存在零元；a,b,a,b *,e101xax1aaayb0byaa0a,b1b

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

21、x(yz),任取有(所以运算满足结合律；xSx 1=max(x,1)=x=max(1,x)=1x,任取，有所以运算的单位元是1；xSx 10=max(x,10)=10=max(10,x)=10 x,任取，有所以运算的零元是10；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 15 页 - - - - - - - - - 16、1212V1,2,3 , ,1 ,xyV5,6 , ,6xyVVx yxy设其中表示取和 之中较大的数。，其中表示取和 之中较小的数。求出和的所有

22、的子代数。指出哪些是平凡的子代数，哪些是真子代数。1111V1 V1,2,3 , ,1 ,1 , ,1 ,1,2 , ,1 ,1,3 , ,1 V1,2,3 , ,1 ,1 , ,1 V1 , ,1 ,1,2 , ,1 ,1,3 , ,1解：（ 1）中 运算的单位元是，的所有的子代数是：；的平凡的子代数是：；的真子代数是：；2222V6V5,6 , ,66 , ,6 V5,6 , ,66 , ,6 V6 , ,6（2）中运算的单位元是，的所有的子代数是：，；的平凡的子代数是：，；的真子代数是：。习题十一及答案： （P218-219）1、图 11.11给出了 6 个偏序集的哈斯图。判断其中哪些是

23、格。如果不是格，说明理由解： （a） 、 （c） 、 （f）是格；因为任意两个元素构成的集合都有最小上界和最大下界；（ b）不是格，因为d,e的最大下界不存在；（ d）不是格，因为b,c的最小上界不存在；（ e）不是格，因为a,b的最大下界不存在。2、下列各集合低于整除关系都构成偏序集，判断哪些偏序集是格。（ 1） L=1 ，2，3， 4，5；（ 2） L=1 ，2，3， 6，12；解：画出哈斯图即可判断出：（1）不是格，（2）是格。4、设 L 是格，求以下公式的对偶式：（ 2）()()()abcabac解：对偶式为：()()()abcabac，参见 P208 页定义 11.2。6、设 L 为

24、格，, ,a b cL，且abc，证明abbc。证明：,ababb,bcbcbabbc名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 15 页 - - - - - - - - - 9、针对图11.11中的每个格，如果格中的元素存在补元，则求出这些补元。解：（ a）图： a,d 互为补元，其中a 为全下界， d为全上界， b 和 c都没有补元；（ c）图： a,f 互为补元，其中a 为全下界， f 为全上界， c 和 d 的补元都是b 和 e，b 和 e 的补元都是c 和

25、d；（f）图： a,f 互为补元，其中a 为全下界， f 为全上界， b 和 e互为补元， c和 d 都没有补元。10、说明图11.11中每个格是否为分配格、有补格和布尔格，并说明理由。解：（ a）图：是一条链，所以是分配格，b 和 c 都没有补元，所以不是有补格，所以不是布尔格；（ c）图： a,f 互为补元， c和 d 的补元都是b 和 e，b 和 e的补元都是c 和 d，所以任何元素皆有补元，是有补格；(),cbdcac()()cbcdfdd()()()cbdcbcd，所以对运算不满足分配律，所以不是分配格，所以不是布尔格；（f）图：经过分析知图（f）对应的格只有2 个五元子格： L1=a,c,d,e,f, L2=a,b,c,d,f 。画出L1 和 L2的哈斯图可知L1 和 L2 均不同构于钻石格和五角格，根据分配格的充分必要条件（见 P213 页的定理11.5）得图（ f）对应的格是分配格；c 和 d 都没有补元，所以不是有补格，所以不是布尔格。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 15 页 - - - - - - - - -