离散数学期末考试试题(配答案).pdf

第 1 页 共 5 页 广 东 技 术 师 范 学 院 模拟试题 科 目：离散数学 考试形式:闭卷 考试时间：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.在代数系统（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 的边数为(）(A)1(nn（B)1(nn (C)2/)1(nn (D）2/)1(nn 5。无向图 G 是欧拉图,当且仅当（）(A)G 的所有结点的度数都是偶数（B)G 的所有结点的度数都是奇数 第 2 页 共 5 页(C）G 连通且所有结点的度数都是偶数 (D）G 连通且 G 的所有结点度数都是奇数。三计算题（共 43 分）1.求命题公式rqp的主合取范式与主析取范式.(6 分)解：主合取方式：pqr(pqr)(pqr）（pqr）=0。2。4 主析取范式：pqr(pqr)(pqr）(pqr)(pqr）(pqr）=1.3.5.6。7 2.设 集 合dcbaA,上 的 二 元 关 系R的 关 系 矩 阵 为1000000011010001RM,求)(),(),(RtRsRr的关系矩阵，并画出 R，)(),(),(RtRsRr的关系图。（10 分)3 无向图 G 有 12 条边，G 中有 6 个 3 度结点，其余结点的度数均小于 3,问 G 中至少有多少个结点？（10 分）第 3 页 共 5 页 解：G（V,E），|E|=V，d（Vi）3,设至少有 x 个节点，由握手定理得：212=d(Vi）63+(x6)3 2(x-6）=x8 故 G 中至少有 9 个节点。4 求下面两个图的最小生成树。（12 分)5。试判断),(z是否为格？说明理由。（5 分）解：(Z,)是格，理由如下：对于任意 aZ，aa 成立，满足自反性；对于任意 aZ，bZ，若 ab 且 ba,则 a=b，满足反对称性；对于任意 a，b,cZ，若 ab，bc，则 ac,满足传递性；而对于任意 a，bZ，ab，b 为最小上界，a 为最大下界，故（Z,）是格。(注:什么是格？）第 4 页 共 5 页 四证明题（共 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）=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 分）第 5 页 共 5 页 证明：设 G 中至多有 4 个 6 度结点且 5 个 5 度结点，d（Vi)=49 不是偶数，故它不是一个图,矛盾.（下面只供参考，个人答案)4.设平面上有 100 个点，期中任意两点间的距离至少是 1，则最多有 300 对点距离恰好为 1.（7分）证明:设任意两点间的读书和恰好为 1,则满足：d(Vi)=2e d(Vi）6 61002e e300 故最多只有 300 条边，即 300 对点距离恰好为 1.