东北农业大学网络教育学院
离散数学复习题
复习题一
一、证明
1、对任意两个集合A和B，证明 ?A?B???A?B??A
答：证明：?A?B???A?B??A?B??A?B??A?B?B?A?E?A
2、构造下面命题推理的证明
如果今天是星期三，那么我有一次英语或数学测验；如果数学老师有事，那么没有数学测验；今天是星期三且数学老师有事，所以我有一次英语测验。 答：符号化为：P?Q?R,S??R,P?S?Q 证明：(1)P?S P (2)P T(1)I (3)S T(1)I (4)P?Q?R P (5) Q?R T(2)(4)I (6) S??R P (7) ?R, T(3)(6)I (8) Q T(5)(7)I
二 、计算
1、(1)画一个有一条欧拉回路和一条汉密顿回路的图。 (2)画一个有一条欧拉回路但没有汉密顿回路的图 (3)画一个没有欧拉回路但有一条汉密顿回路的图 答：三种图如下：
????
?1，2?，求公式： 2、设P?x,y?为x整除y，Q?x?为x?2，个体域为1
??x???y??P?x,y??Q?x??的真值。
??x???y??P?x,y??Q?x?????x???P?x,1??Q?x????P?x,2??Q?x??????P?1,1??Q?1????P?1,2??Q?1??????P?2,1??Q?2????P?2,2??Q?2???答：
???T?T???T?T?????F?F???T?F????T?T???T?F??T?T?T3、一棵树有n2个结点度数为2 ，n3个结点度数为3，? ，nk个结点度数为k ，问它有几个度数为1的结点。
答：设它有n1个度数为1的结点，则：
1*n1＋2*n2＋3*n3＋? ＋k*nk=2*（n1+n2+n3+?+nk-1） 得：n1=n3＋2*n4＋? ＋(k-2)*nk+2
1,2,3,4?,A上的关系 R?1,1,1,2,2,1,2,3,3,4，求出它的自反闭包，对称闭包和4、设集合A??传递闭包。
答：r(R)?1,1,1,2,2,1,2,3,3,4,2,2,3,3,4,4
????s(R)??1,1,1,2,2,1,2,3,3,4,3,2,4,3?
t(R)??1,1,1,2,2,1,2,3,3,4,1,3,2,2,2,4,1,4?
三、设A??1,2,3,5,6,9,15,27,36,45?上的整除关系R?a1,a2a1,a2?A,a1整除a2，
??R是否为A上的偏序关系？若是，
则：1、画出R的哈斯图； 答：R是A上的偏序关系。 R的哈斯图：
2、求?2,9?的最小上界lub?2,9?和最大下界glb?2,9?。 答：?2,9?的最小上界lub?2,9??36,最大下界glb?2,9??1。
2
四、用推导法求公式??P?Q??R?的主析取范式和主合取范式。
??P?Q??R??????P?Q??R????P??Q??R????P?R????Q?R?????P??Q??Q??R????P??P???Q?R??答：
???P?Q?R???P??Q?R????P??Q?R?????P?Q?R???P??Q?R???P??Q??R????P?Q?R????P??Q?R??
五、设实数集R上的关系?＝a,b,c,d证明：?是R上的等价关系。
答：证明：?x,y?R2有x?y?y?x,所以x,y,x,y??
因此?是自反的
22?a,b,c,d?R2,a?d?b?c，
??a,b,c,d??有a?d?b?c,即c?b?d?a,所以c,d,a,b??
因此?是对称的
?a,b,c,d,c,d,e,f??有a?d?b?c,c?f?d?e,??即c?d?a?b?e?f,得a?f?b?e,所以a,b,e,f因此?是传递的。综上：?是R上的等价关系。
2
六、设R和R分别是实数集和正实数集，＋和×分别是普通加法和乘法，定义函数f:R?R?为
?f(r)?2r，证明f是从(R,?)到(R?,?) 的同构映射。
答：证明：?x,y?R,且x?y,有2x?2y,所以f是入射
?z?R?,?r?R使2r?z,即r?log2z,所以f是满射
因此f是双射。
?x,y?R,有f?x?y??2x?y?2x?2y?f?x??f?y?，所以f是从(R,?)到(R?,?) 的同构映射。
七、设R是实数集合，R*?R?{0}，在R?R上定义二元运算?为：?a,b???c,d???ac,bc?d?，试证
*明?R?R,??是一个群。?R?R,??是否阿贝尔群？ 答：证明：
**??a,b?,?c,d??R*?R,有a,b,c,d?R,且a?0,c?0,则：ac?R且ac?0,bc?d?R所以?a,b???c,d???ac,bc?d??R?R*因此，运算是封
闭的
3
??a,b?,?c,d?,?e,f??R*?R??a,b???c,d????e,f???ac,bc?d???e,f???ace,bce?de?f??a,b????c,d???e,f????a,b???ce,de?f???ace,bce?de?f? 所以??a,b???c,d????e,f???a,b????c,d???e,f??因此,运算是可结合的??a,b??R*?R,有?a,b???1,0???1,0???a,b???a,b?,且?1,0??R*?R因此?1,0?是幺元
?1b??1b??1b???a,b??R*?R,有?a,b???,????,????a,b???1,0?,且?,???R*?R?aa??aa??aa?
?1b?因此??a,b?有逆元,逆元为?,???aa?综上：?R*?R,??是一个群。
?R*?R,??不是阿贝尔群。
复习题二
一、设 L??1,2,3,4,12?上的整除关系
??a1,a2a1,a2?L,a1整除a2
完成下列各小题。
??1、 证明?是L上的偏序关系。
答：证明 ?a?L,因为a整除a,所以a,a??，因此?是自反的。
设有a1,a2，a2,a1??，即a1整除a2，a2整除a1，则a1?a2，因此?是反对称的。 即a1,a3??,因此?是传递的。设有a1,a2，a2,a3??，即a1整除a2，a2整除a3，则a1整除a3，综上，?是L上的偏序关系。
2、 画出偏序集?L,??的哈斯图。 答：偏序集?L,??的哈斯图如右图所示。
4
3、 在L上定义两个二元运算?和?：对任意a,b?L，a?b?glb(a,b)，a?b?lub(a,b)。请填空（在
横线上填是或不是）：
①代数系统?L,?,?? 是 格。 ②代数系统?L,?,?? 是 有界格。 ③代数系统?L,?,?? 是 有补格。 ④代数系统?L,?,?? 不是 分配格。 二、求布尔函数的析取范式和合取范式
??x)是布尔代数?{0,1},?,?,??上的一个布尔表达式。设E(x1,x2,x3)?(x1?x2)?(x2?x3)?(x23试写出E(x1,x2,x3)的析取范式和合取范式（用推导法或列函数表的方法均可）。
答：方法1 推导法 析取范式为：
??x) E(x1,x2,x3)?(x1?x2)?(x2?x3)?(x23?))?((x?x)?(x?x?))?((x??x)?(x?x?)?((x1?x2)?(x3?x323112311
???(x?x?x)?(x?x?x)?(x?x?x)?(x?x?x)123123123123??x)?(x??x??x)?(x1?x23123
??????(x1?x2?x3)?(x1?x2?x3)?(x1?x2?x3)?(x1?x2?x3)?(x1?x2?x3)合取范式为：
??x)?(x??x?x) E(x1,x2,x3)?(x1?x2?x3)?(x1?x23123方法2 列函数表法
布尔表达式对应的函数表为： <0,0,0> <0,0,1> <0,1,0> <0,1,1> <1,0,0> <1,0,1> <1,1,0> <1,1,1>
析取范式为：
f 0 1 0 1 0 1 1 1 ??x??x)?(x?x??x)?(x??x?x)?(x?x?x?)?(x?x?x) 合取范式为： E(x1,x2,x3)?(x123123123123123??x)?(x??x?x) E(x1,x2,x3)?(x1?x2?x3)?(x1?x23123
三、画出满足下列要求的图
5