14级离散数学A卷.docVIP

郑州大学软件技术学院《离散数学》课程 2014-2015学年第 二学期期末试题（A）卷 （适用专业：14本各专业,考试时间:120分钟） 题号 一 二 三 总分 分数 合分人： 复查人： 一、集合论试题：（共34分） （说明：将答案写在试卷后面的答题纸上） 分数 评卷人 1．设A={a,b,c}，B={1,2}，则 （6分） （1）AB ； （2）A到B上共有 个不同的二元关系。 2．设P表示所有人构成的集合， 表示“父子”关系； 表示“母子”关系； 表示“兄弟”关系。 试通过复合及求逆运算指明： （6分） （1）表示 关系； （2）表示 关系； （3）表示 关系。(是S的逆关系) 3．设 是上的调用关系，求 （10分） （1） （2）的关系图 （3） （4） （5） 4．设X上的关系R是等价关系，试证：R的逆关系也是等价关系。（6分） 5．设A={1，2，3，4，6，8，12}，R是A上的整除关系。 （6分） 1、画出偏序集的哈斯（Hass）图； 2、求B={2，3，6}的最大元素、极小元素、上确界、下界。 二、图论试题 ：（共36分） （说明：将答案写在试卷后面的答题纸上） 分数 评卷人 1．设G是无向简单图，G有21条边，有3个4度点，其余为3度点，求G中的结点数。 （6分） 2．已知下图G是有向图， （6分） （1）求G的可达性矩阵P（须由邻接矩阵运算得出）； （2）找出从V3到V4长度为3的所有通路（路径）。 3．画出5个结点的连通无向图： （6分） （1）是欧拉图、且是哈密尔顿图； （2）非欧拉图、且是哈密尔顿图； （3）是欧拉图、且非哈密尔顿图； （4）非欧拉图、且非哈密尔顿图。 4．指出下列各图的连通性（强连通、单向连通、弱连通）。 （6分） 5．将下面的树改成二元树。 （6分） 6．求下面带权图的最短（小）生成树。 （6分） 三、数理逻辑试题：（共30分） (说明：将答案写在试卷后面的答题纸上) 分数 评卷人 1．写出命题公式的真值表，并求其主析取范式。 （6分） 2．翻译下列两句话，并证明它们逻辑等价。 （6分） 、如果天晴且我有空那么我上街； 、如果天晴那么若我有空则我上街。 3．在全总个体域中翻译：有些火车比所有的卡车都快。 （6分） 4．设，试证明下列等价关系： （6分） （1）； （2）。 5．用蕴含推理证明： P－(Q-S),Q,P∨(R = R-S （6分） 郑州大学软件技术学院《离散数学》课程试卷 答 题 纸 （适用专业： 14本各专业 考试时间： 120 分钟） 合分人： 复查人： 题号 一 二 三 总分 分数 集合论试题：（共34分） 分数 评卷人 二、图论试题 ：（共36分） 分数 评卷人 三、数理逻辑试题：（共30分） 分数 评卷人 第 8 页 共 8 页