离散数学期末考试试题[1].pdf

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

1、 离 散 数 学 期 末 考 试 试 题(配 答案)1 (总 6 页)-本页仅作为文档封面，使用时请直接删除即可-内页可以根据需求调整合适字体及大小-2 广东技术师范学院 模拟试题 科 目：离散数学 考试形式：闭卷 考试时间:120 分钟 系别、班级：姓名：学号：一填空题（每小题 2 分，共 10 分）1.谓词公式)()(xxQxxP的前束范式是_ xyP(x)Q(y)_。2.设全集,5,2,3,2,1,5,4,3,2,1BAE则 AB=_2_，A_4,5_，BA _ 1,3,4,5 _ 3.设 baBcbaA,，则)()(BA_ c,a,c,b,c,a,b,c _，)()(AB_。4.在代数

2、系统（N，+）中，其单位元是 0，仅有 _1_ 有逆元。5如果连通平面图 G有n个顶点，e条边，则 G有_e+2-n_个面。二选择题（每小题 2 分，共 10 分）1.与命题公式)(RQP等价的公式是（）（A）RQP)(（B）RQP)(（C）)(RQP（D）)(RQP 2.设集合cbaA,A上的二元关系bbaaR,不具备关系()性质（A）(A)传递性 (B)反对称性 (C)对称性 (D)自反性 3.在图EVG,中,结点总度数与边数的关系是()(A)Evi2)deg(B)Evi)deg(C)VviEv2)deg(D)VviEv)deg(4.设 D是有 n个结点的有向完全图,则图 D的边数为()3

3、(A)1(nn(B)1(nn (C)2/)1(nn (D)2/)1(nn 5.无向图 G是欧拉图,当且仅当()(A)G的所有结点的度数都是偶数(B)G 的所有结点的度数都是奇数(C)G连通且所有结点的度数都是偶数 (D)G 连通且 G的所有结点度数都是奇数。三计算题（共 43 分）1.求命题公式rqp的主合取范式与主析取范式。（6分）解：主合取方式：pqr(pqr)(pqr)(pqr)=主析取范式：pqr(pqr)(pqr)(pqr)(pqr)(pqr)=设集合dcbaA,上的二元关系 R 的关系矩阵为1000000011010001RM,求)(),(),(RtRsRr的关系矩阵，并画出R，)

4、(),(),(RtRsRr的关系图。（10分）4 3 无向图 G有 12 条边，G中有 6 个 3度结点，其余结点的度数均小于 3，问 G中至少有多少个结点？（10 分）解：G（V,E），|E|=V，d（Vi）3,设至少有 x 个节点，由握手定理得：212=d（Vi）63+(x-6)3 28 故 G 中至少有 9 个节点。4 求下面两个图的最小生成树。（12分）5 5.试判断),(z是否为格？说明理由。（5 分）解：（Z,）是格，理由如下：对于任意 aZ，aa 成立，满足自反性；对于任意 aZ，bZ，若 ab 且 ba，则 a=b，满足反对称性；对于任意 a，b，cZ，若 ab，bc，则 ac

5、，满足传递性；而对于任意 a，bZ，ab，b 为最小上界，a 为最大下界，故（Z，）是格。（注：什么是格？）6 四证明题（共 37 分）1.用推理规则证明DDACCBBA)(,)(,。（10 分）证明：编号 公式 依据（1）（BC）C 前提（2）BC，C （1）（3）B （2）（4）AB （3）（5）A （3）（4）（6）（AD）前提（7）AD （6）（8）D （5）（6）2.设 R 是实数集，babafRRRf),(,:，abbagRRRg),(,:。求证：gf和都是满射，但不是单射。（10分）证明：要证f是满射，即yR,都存在（x1，x2）RR，使f（x1，x2）=y，而f（x1，x2）=

6、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，即证得。7 3.无向图 G有 9 个结点，每个结点的度数不是 5 就是 6，求证：G中至少有 5 个 6度结点或 6个 5 度结点。（10 分）证明：设 G 中至多有 4 个 6 度结点且 5 个 5 度结点，d（Vi）=49 不是偶数，故它不是一个图，矛盾。（下面只供参考，个人答案）4.设平面上有 100 个点，期中任意两点间的距离至少是 1，则最多有 300 对点距离恰好为 1。（7分）证明：设任意两点间的读书和恰好为 1，则满足：d（Vi）=2e d（Vi）6 61002e e300 8 故最多只有 300 条边，即 300 对点距离恰好为 1.