2022年2022年离散数学期末练习题 .pdf

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

1、离散数学复习注意事项：1、 第一遍复习一定要认真按考试大纲要求将本学期所学习内容系统复习一遍。2、 第二遍复习按照考试大纲的要求对第一遍复习进行总结。把大纲中指定的例题及书后习题认真做一做。检验一下主要内容的掌握情况。3、第三遍复习把随后发去的练习题认真做一做，检验一下第一遍与第二遍复习情况，要认真理解 , 注意做题思路与方法。离散数学综合练习题一、选择题1下列句子中，（）是命题。A2 是常数。B这朵花多好看呀！C请把门关上！D下午有会吗？2令 p : 今天下雪了， q :路滑， r:他迟到了。则命题 “ 下雪路滑，他迟到了 ” 可符号化为（）。A. pqrB. pqrC. pqrD. pqr

2、3令:p 今天下雪了，:q 路滑，则命题 “ 虽然今天下雪了，但是路不滑” 可符号化为（） 。A.pqB.pqC. pqD. pq4设( )P x:x是鸟，( )Q x:x会飞，命题 “ 有的鸟不会飞 ” 可符号化为（）。A. ()( )( )xP xQ xB. ()( )x P x( )Q xC. ()( )( )x P xQ xD. ()( )xP x( )Q x5.设( )P x:x是整数，( )f x:x的绝对值，( , )L x y：x大于等于y；命题 “ 所有整数的绝对值大于等于0” 可符号化为（）。A. ( )( ),0)x P xL f xB. ( )( ),0)x P xL

3、fxC. ( )( ),0)xP xL f xD. ( )( ),0)xP xL f x6.设( )F x:x是人，( )G x:x犯错误，命题“ 没有不犯错误的人 ” 符号化为（） 。A( )( )x F xG xB( )( )x F xG xC( )( )x F xG xD( )( )x F xG x7.下列命题公式不是永真式的是（） 。A. ()pqpB. ()pqpC. ()pqpD. ()pqp8设( )R x:x 为有理数；( )Q x:x 为实数。命题 “ 任何有理数都是实数 ” 的符号化为（）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - -

4、- - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 20 页 - - - - - - - - - A()( )( )x R xQ xB()( )( )xR xQ xC()( )( )xR xQ xD( )( )x R xQ x9.设个体域 , Da b，与公式( )xA x等价的命题公式是 ( ) A( )( )A aA bB( )( )A aA bC( )( )A aA bD( )( )A bA a10.下列等价式不正确的是（） 。A( )( )( )( )x P xQ xxP xxQ xB( )( )( )( )x P xQ xxP xxQ xC( ( )

5、( )( )( )x P xQ xxP xxQ xD( ( )( )x P xQxP xQ11. 设个体域 , Da b，与公式( )xA x等价的命题公式是 ( ) A( )( )A aA bB( )( )A aA bC( )( )A aA bD( )( )A bA a12.设 X=, ,aa，则下列陈述正确的是（） 。A. aXB. ,aXC.,aXD.X13.有向图 D 是连通图 ，当且仅当（） 。A. 图 D 中至少有一条通路B. 图 D 中有通过每个顶点至少一次的通路C. 图 D 的连通分支数为一D. 图 D 中有通过每个顶点至少一次的回路14.设 A=a,b,c ，则下列是集合 A

6、 的划分的是 ( ) A., ,b ccB. , ab cC., , a ba cD. , ,a bc15.下列谓词公式中是前束范式的是（） 。A( )()( )xF xx G xB( )( )xF xyG yC( ( )( , )x P xyQ x yD( ( )( , )x y P xQ x y16.设12|( )0,|( )0MxfxNx fx，则方程12( )( )0fxfx的解为（） 。AM NBM N CMN CM-N 17.设,GA是群，则下列陈述不正确的是（） 。A. 11()aaB. nmn ma aaC. 111()aba bD. 11()nna baa b a18.在整数

7、集合Z上，下列定义的运算满足结合律的是（） 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 20 页 - - - - - - - - - A. 1a bbB. 1a baC. 1a babD. 1a bab19. 设简单图 G 所有结点的度数之和为50，则 G 的边数为（） 。( ) A. 50 B. 25 C. 10 D. 5 20.设简单无向图 G 是一个有 5 个顶点的 4正则图，则 G 有（）条边。A. 4 B. 5 C. 10 D. 20 21.设集合1,2,

8、3,4A, A上的等价关系1,1 ,3,2,2,3,R4,4 AIU，则对应于 R的划分是（） 。A. 1,2,3,4B. 1,3,2,4C. 1,3,2,4D. 1 ,2,3,422.设集合1,2,3,4A, A上的等价关系1,3,3,1,2,4,R4,2 AIU，则对应于R的划分是（） 。A. 1,2,3,4B. 1,3,2,4C. 1,3,2,4D. 1 ,2,3,423.设,GA是群，则下列陈述不正确的是（） 。A. 11()aaB. 111()aba bC. nmn ma aaD. 11()nna baa b a24.1,2,10AL，下列定义的运算关于集合A是不封闭的是（） 。A.

9、 max , xyx y，即, x y的较大数B. min, xyx y，即, x y的较小数C. gcd , xyx y，即, x y的最大公约数D. , xylcm x y，即,x y的最小公倍数25. 设1,2,3 , , , , ,1,2,3,XYa b c dfabc，则f是( )。A从 X 到 Y 的双射B从 X 到 Y 的满射，但不是单射C从 X 到 Y 的单射，但不是满射D从 X 到 Y 的二元关系，但不是从X 到 Y 的映射26.设简单无向图 G 是一个有 6 个顶点的 5正则图，则 G 有( )条边。A. 5 B. 6 C. 15 D. 30 27.图 G 如下图所示，以下

10、说法正确的是( )。Aa 是割点Bb,c是点割集Cb,d是点割集Dc 是割点dbca名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 20 页 - - - - - - - - - 28.格 L 是分配格的充要条件是L 不含与下面哪一个选项同构的子格（） 。A链B钻石格C五角格D. 五角格与钻石格29.下列图是 欧拉图 的是（D） 。30.给定一个有 n 个结点的无向树，下列陈述不正确的是（） 。A所有结点的度数 2B无回路但若增加一条新边就会变成回路C连通且1ev，其中 e

11、 是边数， v 是结点数D无回路的连通图31. 设A有 5 个元素，则其幂集()P A的元素总个数为（） 。A. 32 B.25 C. 50 D. 5 32若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是（） 。A. (1,2,2,3,4,5) B. (1,2,3,4,5,5) C. (1,1,1,2,3) D. (2,3,3,4,5,6) 33. 设 , , Aaaaa则其幂集()P A的元素总个数为（） 。A. 3 B. 4 C. 8 D. 16 34. 在实数集合 R 上，下列定义的运算中不可结合的是（） 。A. 2a bababB. a babC. a bababD. a

12、bab35. 无向图 G 是欧拉图，当且仅当（） 。A. G 的所有结点的度数全为偶数B. G 中所有结点的度数全为奇数C. G 连通且所有结点度数全为奇数D. G 连通且所有结点度数全为偶数36.下列不一定是树的是（）A. 无回路的连通图 D 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 20 页 - - - - - - - - - B. 有 n 个结点， n-1 条边的连通图C. 每对结点之间都有通路的图D. 连通但删去一条边则不连通的图37. 设简单图 G 所有结

13、点的度数之和为48，则 G 的边数为( ) A. 48 B. 24 C. 16 D. 12 38下面既是哈密顿图又是欧拉图的图形是（B） 。39.下列必为欧拉图的是（）A.有回路的连通图B.不可以一笔画的图C.有 1 个奇数度结点的连通图D.无奇数度结点的连通图40.二部图3,3K是（） 。A.欧拉图B. 哈密顿图C.平面图D. 完全图41下列所示的哈斯图所对应的偏序集中能构成格的是（C） 。A.B.C.D.42.设简单无向图 G 是一个有 6 个顶点的 3正则图，则 G 有( )条边。A. 3 B. 6 C. 9 D. 18 名师资料总结 - - -精品资料欢迎下载 - - - - - -

14、- - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 20 页 - - - - - - - - - 43下列式子为矛盾式的是（） 。A()ppqB ppC ppD()pqpq44.设集合 , , Aa b c，A 上的关系,Ra aa cc a，则 R 是（）A自反的B对称的C传递的D反对称的45设12,R R是集合 , , , Aa b c d上的两个关系，其中1,Ra ab b,b cd d，2,Ra ab bc bb cd d，则2R是1R的（）闭包。A自反B对称C传递D自反、对称且传递闭包46. 下列公式是 前束范式 的是（） 。A(

15、)()( , )( )xyF z xG yB()( )()( )( )x F xy G yH zC()( ,)()( )x F x yy G yD()( , )()( , )xF x yy G x y47. 设 R 为实数集，函数:fRR，2( )25f xxx，则f是（） 。A单射而非满射B满射而非单射C双射D既不是单射，也不是满射48下列各图中既是欧拉图，又是汉密尔顿图的是（C ） 。ABCD49下列四个格，是分配格的是（C ） 。50设集合 A=a,b, c 上的关系如下，具有传递性的是（） 。A R=, B R=, C R=, D R= 名师资料总结 - - -精品资料欢迎下载 - -

16、 - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 20 页 - - - - - - - - - 参考答案：（若有问题，可以到1#402或打电话问）一、选择题AAAAB DACAA CCDBD BCDBC ABBDC CBDDA ACCDD BBBDB CCCBB ADCCD 二、填空题1命题公式()pq的成真指派为10 ，成假指派为 _00，01，11_。2. 命题公式()pqp的成真指派为 00 10 11，成假指派为 _01_。3命题公式()ppq的成真指派为 00 01 11 , 成假指派为 _ 10_。4公式()

17、()( )( , )() ( ,)xyP yQ x zy R x y约束变元为x,y ，自由变元为x,z 。5公式( ( )( )( , )x P xyR yQ x z约束变元为 _x,y_，自由变元为 _x,z_ 。6设 , , Aa ba b， , Ba b，则BA， ABa,b。7设1,2,3A， A上的关系1,2,2,1 R，则对称闭包()s R,，传递闭包()t R,。8. 设*是集合 S上的二元运算，若运算 *满足_结合律 _，并且存在 _单位元_，则称,*S为独异点。9 设 , , Aa ba b，, , Ba b c，则 AA， ABa,b,c。10. 一棵无向树的顶点数n与边

18、数m的关系是m=n-1。6 阶无向连通图至多有6 棵不同构的生成树。11设( )1f xx，2( )g xx，则复合函数()( )fgxo=2(1)x,()( )gfxo =21x。12. ,nZ是一个群，其中0,1, 2,1nZnL，()modxyxyn， 则当n=6时，在6,Z中，2 的阶为 _3_, 3 的阶为 _ 2。13设是格，其中 A=1, 3,4，6，8，12，24， 为整除关系，则 1的补元是_24 _，3的补元是 _8_。14设 A= ， ， ， B= ,那么dom()ABU=1,3,4,5ran()ABI= 3,5 。15. 设A=l,2,3,4, A上的二元关系 R=,

19、，S=, ，则RSo, ,1()RSo,。16设=,R和=,S是集合=1,2,3,4,5A上的两个关系 ，则 R So= , ，11SRo= , 。17 设A=2, 4, 6 ，A上的二元运算 *定义为： a*b=maxa,b ，则在独异点 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 20 页 - - - - - - - - - 中，单位元是2 ，零元是6 。18一棵无向树的顶点数n 与边数 m 关系是 m= n-1 。设 G 是具有 8 个顶点的树，则 G 中增加

20、_21_条边才能把 G 变成完全图。19设复合函数 g f 是从 A 到 C 的函数，如果 g f 是满射，那么 _ g_必是满射，如果 g f 是单射，那么 _f _必是单射。20 设是格，其中A=1, 3, 5, 9, 45， 为整除关系， 则1的补元是 _45_，3的补元是 _ 5 _。21给出 A=l ，2上的一个等价关系_, _，并给出其对应的划分_1,2_ _。22设 , , , Aa b c d，A上的二元关系,Ra ba db b，则 R的自反闭包()r RARIU，传递闭包()t RR23命题公式()pqp的成真赋值为01 10 11，成假赋值为00 。24公式()()pqp

21、q的成真赋值是00,11。成假赋值01 1025公式()()pqpq的成真赋值是01 11。成假赋值00 1026公式()()pqpq的成假赋值是01 10。成假赋值00 1127设个体域是实数集， 命题)3(xxx的真值为1；命题2(10)x x的真值为0 。28.设 fRR,f(x)=x+3,g RR,g(x)=2x+1,则复合函数(fg)( )x =o2x+4, (gf )(x) =o2x+7。29.给定集合 A=1,2,3,4,5 ，在集合 A 上定义两种关系： R=, S=,，则 R S=o,。30设 A=0 ，1，2，3，6，,| ,(mod3)Rx yx yAxyxy则domR=

22、 0， 3，6_ ，ranR=_0， 3，6，31 设6,Z为模 6 加群，其中60,1, 2,3, 4,5Z，则 2-3= 0 ，4-2= 4 。32一个结点为 n 的无向完全图，其边的数目为n(n-1)/2 ，顶点的度为n-1 。33. 已知n阶无向简单图 G 有m条边，则 G 的补图G中有 m- n(n-1)/2 条边。参考答案：1_10_，00，01，11 2. 00 10 11， 01_ 3. _00 01 11, 10 4. _x,y ，x,z_ 5. _x,y ，x,z_ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - -

23、 - 名师精心整理 - - - - - - - 第 8 页，共 20 页 - - - - - - - - - 6., a,b 7.1,2,2,1 ，1,2,2,1,1,1 ,2,28. 结合律 ，单位元9, a,b ，c 10.n-1, 6 11.2(1)x,21x12.3 , 2 13. _24_,_8_ 14. 1,3,4,5，_315. , 16. 1,1 ,3,5，1,1 ,5,317. 2 , 6 18. m= n-1, _21 19. _g , _f_ 20. 45 , _5_ 21. 1,1 ,2,2, 1 ,222. ARIU, R23. 01 10 11，00 24. 00，

24、11 ,01，10 25. 01，11 ,00，10 26. 01 10 , 00 11 27. 1 , 0 28. 24x+,27x+29. , 30. 0， 3，6, 0， 3，6 31. 0 , 4 32. n(n-1)/2, n-1 33. m- n(n-1)/2 三、计算题（仅给出部分题目的解题思路，未给出答案自己完成）1. 已知命题公式()()pqpr名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 20 页 - - - - - - - - - （1）构造真值表

25、（2）求出公式的主析取范式解题思路：（1）真值表p q r p()pqpr()()pqpr0 0 0 1 0 0 1 0 0 1 1 0 0 1 0 1 0 1 1 0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 0 1 0 1 0 1 1 1 1 1 0 0 1 0 0 1 1 1 0 1 1 1 （2）()()pqpr0157()()()()pqrpqrpqrpqrmmmm2.已知命题公式()()pqpr（1）构造真值表；（2）用等值演算法求公式的主析取范式。解： （1）真值表p q r pqpr()pr()()pqpr0 0 0 0 0 1 1 0 0 1 0 1 0 1 0

26、 1 0 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 0 0 1 0 1 1 1 0 0 1 1 0 1 1 0 0 1 1 1 1 1 0 0 （2）主析取范式名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 20 页 - - - - - - - - - 012()()()()()()()()()r)()()(r)(r)pqprpqprpqprpqrrpqqpqrpqrpqpqmmm3求公式()()prpqp的主合取范式及主析取范式。4构造命题公式(

27、 p)r()pq的真值表。5. 一棵（无向）树有 2 结点的度为 2， 1 个结点的度为 3，3 个结点的度为 4, 其余都是叶结点，问该树有几个叶结点？解：在一个有限图中，各结点的度数总和是边数的2 倍；而树中的边数为结点数减 1。根据这两点，可知树中各结点的度数总和=2*（树中点数 -1），设树叶有 x个，于是， 2*2+3+3*4+x=2* （2+1+3+x-1）得 x=9。6.一棵无向树 T 有 5 片树叶， 3 个 2 度分支点，其余的分支点都是3 度顶点，问T 有几个顶点？提示：类似上题求解。7. 设2:,( )2fRR f xx，:,( )4g RR g xx,3:, ( )1h

28、 RR h xx，其中 R 表示实数集。（1）求函数fgo，gfo；（2）, ,f g h哪些函数有反函数？如果有，求出这些反函数。解： （1）22( )( )(4)(4)2814gf xf g xf xxxxo22( )( )(2)2fg xg f xg xxo（2）g和 h有反函数，11:,( )4gRR gxx；113:,( )1hRR hxx8. 设Aa，b，c ，R是A上的二元关系，且 R，求r(R)、s(R)和t(R)。解：r(R)=RIA=, s(R)=RR-1=, t(R)= RR2R3=， 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - -

29、- - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 20 页 - - - - - - - - - 9. 设1,2,3,4,6,9,24,54A，为整除关系。（1）画出偏序集 的哈斯图；（2）求 A 中的极大元；（3）求子集 B=3, 6, 9的上确界与下确界。解： （1）哈斯图（2）A 中的极大元为24，54；极小元为 1；最大元：无；最小元： 1 （3）求子集 B=3, 6, 9的上确界为 54，下确界为 3。10. 设有向图 D 如图所示，用邻接矩阵完成以下计算。（1）1v到4v长度小于或等于4 的通路数；（2）1v到自身长度小于或等于4 的回路数；（3

30、）求出 D 的可达矩阵，并说明D 的连通性。有向图的邻接矩阵为1210001000010010A，21231000100100001A31243001000010010A，41264000100100001A（1）v1到 v4长度小于或等于 4 的通路数为4( )14101348iia1 6 2 3 4 24 9 54 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 20 页 - - - - - - - - - （2）v1到自身长度小于或等于4 的回路数为4( )111

31、1 1 114iia（3）11110111()00110011P D由可达矩阵可知 D 是单向连通的。11设0,1,2A，给出幂集合()P A对称差运算的运算表。12设60,1, 2,3, 4,5Z，给出模 6 加运算的运算的运算表。参看教材 P167例 9.4 与 9.5 14. 设A1 ，2，3，4，5，R是A上的二元关系，且 R，求r(R)、s(R)和t(R)。解：r(R)=RIA s(R)=RR-1 t(R)= ，,（2,2, 15. 下图为一连通赋权图，计算该图的最小生成树和权值。四、简答题1.设集合654321，A上的关系(1,1,1,3,1,6,2,2,R= 2,5,3,1,3,

32、3,3,6,4,4,5,2,5,5,6,1,6,3),6,6 （1）画出 R 的关系图，并写出 R的关系矩阵；（2） R是否为等价关系？若是，写出R的所有等价类。解： （1）R 的关系图为名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 20 页 - - - - - - - - - （2）R的关系矩阵1010001001101000001001001由关系图可以看出R是等价关系。等价类为：1361,3,6,22,5,44或写为： A/R=1,3,6,2,5,4 2. 设1

33、,3,(1,4,2,2,3,1 ,3,3),4,1 R是 A=1,2,3,4上的二元关系。（1）画出 R的关系图；（2）写出 R的关系矩阵；（3）讨论 R的性质。解： （1）R的关系图（2）R的关系矩阵0011010010001000（3）R非自反、非反自传、对称、非反对称、非传递的（4）R 不是函数，不满足函数单值性的要求。3设 A=1,2,3,4,5,6,7,8,9,10，R 是 A 上的二元关系，R=|x,yA x+y=10 说明 R 具有哪些性质。解：R=, , , , , , , 4 2 3 1 1 2 3 6 5 4 名师资料总结 - - -精品资料欢迎下载 - - - - - -

34、 - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 20 页 - - - - - - - - - 易知 R 既不是自反也不是反自反的R 是对称的R 不是反对称的R 不是传递的。4 判断下图是否为二部图？若是， 找出它的互补结点子集。 它是否为哈密顿图？若是，找出一条哈密顿回路。5.判断下图G 是否是二部图？若是，找出它的互补结点子集。它是否为哈密顿图？若是，找出一条哈密顿回路。6. 设1,3,5,9,45A =，为 A 上的整除关系。（1）,A是否为偏序集，若是，画出其哈斯图；（2）,A是否为格？说明理由；解： （1）,A是偏序集。哈斯

35、图为：（2）,A是格。因为偏序集中的任意两个元素均有上、下确界。四、证明题1用一阶逻辑的推理理论证明：前提：( )( )x F xG x，( )( )x F xH x，( )xH x结论：( )x G x证明： （1）( )( )x F xH x前提引入hfigabecdj1v2v6v7v5v8v3v1 3 5 9 45 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 20 页 - - - - - - - - - （2）( )( )F xH x（1）（3）( )x H

36、x前提引入（4）( )H x（3）（5）( )F x（2） （4）析取三段论（ 4 分）（6）( )( )x F xG x前提引入（7）( )( )F xG x（6）（8）( )G x（5） （7）假言推理（9）( )G x（8）（ 3 分）2设A是非空集合 ,F是所有从A到A的双射函数的集合 , o是函数的复合运算。证明：,F o是群。证明：由于集合A是非空的，AIF，,因此F非空 。(1),f gF,因为f和g都是A到A的双射函数，故fgo也是A到A的双射函数，从而集合F关于运算是封闭的。(2) , ,f g hF,由函数复合运算的结合律有()()fghfghoooo， 故运算o是可结合的

37、。(3)A上的恒等函数AI也是A到A的双射函数即AIF,且fF有AAIffIoo, 故AI是,F o中的幺元。(4) fF,因为f是双射函数，故其逆函数是存在的， 也是A到A的双射函数，且有11AffffIoo,因此1f是f的逆元由此上知,F o是群3设代数系统6,VZ，60,1,2,3, 4,5Z，为模6加法。证明：6Z关于运算构成群。证明：集合6Z显然非空。(1)6,a bZ,6abZ,从而集合6Z关于运算是封闭的。(2) 6, ,a b cZ,有()()abcabc，故运算是可结合的。(3)6aZ, 0aa,故 0 是6,Z中的幺元。(4) 6aZ,因为(6)0aa,因此6a是a的逆元由

38、此上知6,Z是群4设A是集合， P(A)是A的幂集合，是对称差运算，证明构成群。提示：参考 2、3证明题完成。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 20 页 - - - - - - - - - 5 设,| ,Ax yx y为正整数， 在 A上定义二元关系 R如下：,x yRu v当且仅当xyuv。证明： R是一个等价关系。证明：任取, x y,x yAxyxyx yRx y所以 R自反的。任取,x yu v,x yRu vxyuvuvxyu vRx y所以 R

39、是对称的。任取,x yu vs t,x yRu vu vRs txyuvuvst,xystx yRs t所以 R是传递的。因此， R 是等价关系。6.设 R 是 A 上的关系，如果R 满足以下两条件：（1）对于任意的 aR， 都有 aRa，（2）若 aRb, aRc, 则有 bRc，证明： R 是等价关系证明：任取, ,a b cR（1）由已知条件（ 1）得,a aR,所以 R 是自反的。（2）由已知条件（ 1） 、 （2）得,a bRa aRb aR所以 R是对称的。（3）由已知条件（ 1） 、 （2）得,a bRb cRb aRc bR,b cRb aRc aR所以 R是传递的。五、应用题

40、（仅给出第7 题的参考答案 ,未给出参考答案的自己完成）1. 构造下列推理的证明。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 20 页 - - - - - - - - - 如果今天是星期一，则要进行英语或离散数学考试。如果英语老师有会，则不考英语。今天是星期一，英语老师有会，所以进行离散数学考试。2. 构造下列推理的证明。小王是理科学生，则他的数学成绩很好。如果小王不是文科学生，则他一定是理科学生。小王的数学成绩不好, 所以小王是文科学生。3如果甲是冠军，则乙或丙将

41、得亚军；如果乙得亚军，则甲不能得冠军；如果丁得亚军，丙不能得亚军；事实是甲已得冠军。因此丁不能得亚军。参照作业： P54 17,18 4. 用一阶逻辑推理证明每个喜欢步行的人都不喜欢骑自行车，每个人或喜欢骑自行车或者喜欢乘汽车。有的人不喜欢乘汽车，所以，有的人不喜欢步行（个体域为人类集合）解: 令( ) :F xx喜欢步行 ,( ):G xx喜欢骑自行车 ,( ) :H xx喜欢乘汽车前提：( )( )x F xG x，( )( )x F xH x，( )xH x结论：( )x G x证明： （1）( )( )x F xH x前提引入（2）( )( )F xH x（1）（3）( )x H x前

42、提引入（4）( )H x（3）（5）( )F x（2） （4）析取三段论（6）( )( )x F xG x前提引入（7）( )( )F xG x（6）（8）( )G x（5） （7）假言推理（9）( )G x（8）5 今 有 于, , , ,a b c d e f7 个 人 ， 已 知 下 列 事 实 ：a会 讲 英 语 ；b 会讲英语和汉语；c 会讲英语、意大利语和俄语；d 会讲日语和汉语；e 会讲德国和意大利语； f 会讲法语、日语和俄语；g 会讲法语和德语。试问这七个人应如何排座位，才能使每个人都能和他身边的人交谈？解：用结点表示人， 用边表示连接的两个人能讲同一种语言，构造出图 G如下

43、：abcdefg英英英汉俄法德意日名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 20 页 - - - - - - - - - 在 G中存在着一条哈密顿回路如下，根据这条回路安排座位， 就能够使每个人都能和他身边的人交谈。6 一次学术会议的理事会共有20 个人参加，他们之间有的互相认识但有的互相不认识。但对任意两个人，他们各自认识的人的数目之和不小于20。问能否把这 20 个人排在圆桌旁， 使得任意一个人认识其旁边的两个人？根据是什么？7. 设有 7 个城市1v，2v，

44、7v，任意两个城市之间直接通信线路及通信线路预算造价如带权图所示，试给出一个设计方案，使得各城市间能够通信，而且总造价最低。写出求解过程，并计算出最低总造价。解：带权图中边表示通信路， 边上的数字表示修建该通信线路所需费用，于是求解此题便成为求权图中的最小生成树问题。按避圈算法，对图中各边的权值按由小到大的顺序排序，112233444555英英汉意法德日abfgdec5v4v3v2v1311v0v226v52v3v4v112455543321v0v40v46v5v名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 -

45、- - - - - - 第 19 页，共 20 页 - - - - - - - - - 取12(,)v vT,45(,)v vT，34(,)vvT，04(,)vvT02(,)v vT，16(,)v vT则求解最小生成树如下图所示：图中最小生成树的权为 :12(,)w v v+45(,)w vv+34(,)w v v+04(,)w vv+02(,)w vv+16(,)w v v=1+1+2+2+3+5= 14 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 20 页 - - - - - - - - -