离散数学期末考试题(附答案和含解析2).doc

《离散数学期末考试题(附答案和含解析2).doc》由会员分享，可在线阅读，更多相关《离散数学期末考试题(附答案和含解析2).doc（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流离散数学期末考试题(附答案和含解析2).精品文档.一填空题1. 谓词公式的前束范式是 xyP(x)Q(y) 2. 设全集 E=1,2,3,4,5,A=1,2,3,B=2,5, 则AB = 2 ， 4,5 ， 1,3,4,5 。3. 设，则_c,a,c,b,c,a,b,c_，_。4. 在代数系统（N，+）中，其单位元是0，仅有 单位元0 有逆元。 /x+y=0,x的逆元= -x,即x=05如果连通平面图G有个顶点，条边，则G有_e+2-n_个面。 /点面-边=23 无向图G有12条边，G中有6个3度结点，其余结点的度数均小于3，问G中至少有 9

2、 个结点？ /因为至少，所以 63+2n=122 解得n=3 总结点m=6+3=9二选择题1. 与命题公式等价的公式是（ ）（A） （B） （C） （D）3. 在图中,结点总度数与边数的关系是( C )(A) (B) (C)(D) 4. 设D是有n个结点的有向完全图,则图D的边数为( A )(A) (B) (C) (D)5. 无向图G是欧拉图,当且仅当( C )(A) G的所有结点的度数都是偶数 (B)G的所有结点的度数都是奇数(C)G连通且所有结点的度数都是偶数 (D) G连通且G的所有结点度数都是奇数。三计算题1. 求命题公式的主合取范式与主析取范式。（6分）解：主合取方式：pqr (pq

3、)r (pr)(qr) (p(qq)r)(pp)qr) (pqr)(pqr)(pqr)= M0M2M4主析取范式：pqr (pq)r (pq(rr)(pp)r) (pqr)(pqr)(pr)(pr) (pqr)(pqr)(p(qq)r)(p(qq)r) (pqr) (pqr) (pqr) (pqr) (pqr)= m1m3m5m6m75. 试判断是否为 格 ？说明理由。（5分）解：（Z,）是格，理由如下：对于任意aZ，aa成立，满足自反性；对于任意aZ，bZ，若ab且ba，则a=b，满足反对称性；对于任意a，b，cZ，若ab，bc，则ac，满足传递性；而对于任意a，bZ，ab，b为最小上界，a

4、为最大下界，故（Z，）是格。（注：什么是格？ 即任意两个元素有最小上界和最大下界的偏序）四证明题2. 设R是实数集，。求证：都是满射，但不是单射。（10分）证明：要证f是满射，即yR,都存在（x1，x2）RR，使f（x1，x2）=y，而f（x1，x2）=x1+x2，可取x1=0，x2=y，即证得；再证g是满射，即yR，,都存在（x1，x2）RR，使g（x1，x2）=y，而g（x1，x2）=x1x2，可取x1=1，x2=y，即证得；最后证f不是单射，f（x1，x2）=f（x2，x1）取x1x2，即证得，同理：g（x1，x2）=g（x2，x1），取x1x2，即证得。3. 无向图G有9个结点，每个结点的度数不是5就是6，求证：G中至少有5个6度结点或6个5度结点。（10分）证明：设G中至多有4个6度结点且5个5度结点，d（Vi）=49不是偶数，故它不是一个图，矛盾。（注：结点总个数=边数2，即为偶数。当且仅当6度结点个数为：1,3,5,7,9（或5度结点个数为：0,2,4,6,8）时成立。 当6度结点个数为：1,3时，5度结点个数为：8,6）4. 设平面上有100个点，期中任意两点间的距离至少是1，则最多有300对点距离恰好为1。（7分）证明：设任意两点间的读书和恰好为1，则满足：d（Vi）=2ed（Vi）661002e e300故最多只有300条边，即300对点距离恰好为1.