当前位置：首页 > (2014版)离散数学网上作业题
东北农业大学网络教育学院
离散数学复习题
复习题一
一、证明
1、对任意两个集合A和B，证明 ?A?B???A?B??A
证明：对于，有，所以，故是自反的。
若，则，得，所以，故是对称的。
若传递的。 综上：
，，则，得，所以，故是
为等价关系。
2、构造下面命题推理的证明
如果今天是星期三，那么我有一次英语或数学测验；如果数学老师有事，那么没有数学测验；今天是星期三且数学老师有事，所以我有一次英语测验。 解：p：今天是星期三。
q：我有一次英语测验。 r：我有一次数学测验。 s：数学老师有事。
前提：p?(q∨r) , s??r , p∧s 结论：q
证明：①p∧s 前提引入
②p ①化简 ③p?(q∨r) 前提引入
④q∨r ②③假言推理 ⑤s ①化简 ⑥s??r 前提引入
⑦?r ⑤⑥假言推理 ⑧q ④⑦析取三段论 推理正确。
二 、计算
1、(1)画一个有一条欧拉回路和一条汉密顿回路的图。 (2)画一个有一条欧拉回路但没有汉密顿回路的图 (3)画一个没有欧拉回路但有一条汉密顿回路的图
?1，2?，求公式： 2、设P?x,y?为x整除y，Q?x?为x?2，个体域为1
??x???y??P?x,y??Q?x??的真值。
3、一棵树有n2个结点度数为2 ，n3个结点度数为3，? ，nk个结点度数为k ，问它有几个度数为1的结点。
解：设树T中有n1个度数为1的结点，则树中边数m为： m=n1+n2+n3+?+nk-1
又由于任意图中结点度数之和等于边数的2倍，故： n1+2n2+3n3+?+knk=2(n1+n2+n3+?+nk-1) 故： n1= (3-2)n3+(4-2)n4+?+(k-2)nk+2
4、设集合A??1,2,3,4?,A上的关系 R?1,1,1,2,2,1,2,3,3,4，求出它的自反闭包，对称闭包和传递闭包。
答：
三、设A??1,2,3,5,6,9,15,27,36,45?上的整除关系R?a1,a2a1,a2?A,a1整除a2，
????R是否为A上的偏序关系？若是， 则：1、画出R的哈斯图；
2、求?2,9?的最小上界lub?2,9?和最大下界glb?2,9?。
答：1、
是
上的偏序关系。
的哈斯图：
四、用推导法求公式??P?Q??R?的主析取范式和主合取范式。
解：(?P?Q)?(P∨?Q)??(?P?Q)∨(P∨?Q)
??(P∨Q)∨(P∨?Q) ?(?P∧?Q)∨(P∨?Q) ?(?P∨P∨?Q)∧(?Q∨P∨?Q)
2
?(P∨?Q) ?M1 ?m0∨m2∨m3
五、设实数集R上的关系?＝a,b,c,d证明：?是R上的等价关系。 证明：
因此
是自反的
因此
是对称的
22?a,b,c,d?R2,a?d?b?c，
?
因此
?是传递的。综上：是上的等价关系。
六、设R和R分别是实数集和正实数集，＋和×分别是普通加法和乘法，定义函数f:R?R?为
f(r)?2r，证明f是从(R,?)到(R?,?) 的同构映射。
*七、设R是实数集合，R?R?{0}，在R?R上定义二元运算?为：?a,b???c,d???ac,bc?d?，试证
*明?R?R,??是一个群。?R?R,??是否阿贝尔群？
**复习题二
一、设 L??1,2,3,4,12?上的整除关系
??a1,a2a1,a2?L,a1整除a2
完成下列各小题。
??1、 证明?是L上的偏序关系。 2、 画出偏序集?L,??的哈斯图。
3、 在L上定义两个二元运算?和?：对任意a,b?L，a?b?glb(a,b)，a?b?lub(a,b)。请填空（在
横线上填是或不是）：
①代数系统?L,?,?? 格。 ②代数系统?L,?,?? 有界格。
3
本文作者：...共分享92篇相关文档
