离散试题2010-2011A.docVIP

成都信息工程学院考试试卷 2010 ——2011 学年第2 学期 课程名称：离散数学使用班级：2009级信管等各班 试卷形式：开卷 闭卷 √ ． 试题 一 二 三 四 五 总分 得分 一、填空题（每空2分，共10分） 1、设、为真命题，、为假命题，则复合命题的 真值为 。 2、设集合A＝{1,2,3,4}, A上的关系，, 则R1(R2= 。 3、设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。 4、设谓词的定义域为{a, b},将表达式(xR(x)→(xS(x)中量词消去，写成与之对应的命题公式是_________________________________________________________________ 。 5、一个连通的（n,m）平面图，它的面数为k，则m,n,k满足的Euler（欧拉）公式为 ________________。 二、选择题（共5题，每题2分，共0分A={1,2,3},A上的关系则R不具备( ). (A)自反性 (B)传递性 (C)对称性 (D)反对称性 2、下列语句中，( )是命题。 (A)请把门关上 (B)地球外的星球上也有人 (C)x + 5 6 (D)下午有会吗？ 3、下列图中是Euler图的是( ) 4、判断下列为双射函数的是( ) (A) f：N→N，f(x) = x2 ＋ 1 草稿区，此处答题无效 (B) f：Z→Z， f(x) = x mod 3 (C) f：N→N， (D) f：R→R，f(x) = x3 5、设A={1，2，3}，下列关系中( )为等价关系。 （A）R1={1，1，1，2，2，1} （B）R2={1，1， 2，2， 3，3} （C）R3={1，1，1，3， 3，3} （D）R4={2，2，3，2 } 三、（5小题，每小题6分，共30分） 1、设论述域是自然数，表示 “”，表示“”， 用逻辑符号表示下面的断言。 （1）对所有。 （2）0并非小于一切。 2、求公式的主合取范式 3、试画出4个顶点3条边的所有非同构的无向简单图。 4、设集合A＝{1, 2, 3, 4, 6, 8, 9, 12}，R为整除关系。 画出偏序集〈A,R〉的哈斯图； 写出A的子集B = {3,6,9,12}的上界，下界，最小上界，最大下界； 5、设A＝{a, b, c, d}，R和S是A上的二元关系，, . 求R?S, . 四、证明并写出每一步的依据（２小题，每小题6分，共１2分） １、前提：P→Q, R→S, P∨R 结论：Q∨S 草稿区，此处答题无效 前提：(x(F(x)(G(x)) 结论：(xF(x)((xG(x) 五、（4小题，第1题10分，第2，3题各8分，第4题12分，共38分） 1、已知是图的生成树， 1 d a e 2 h 5 f 4 b g c 3 1 d a e 2 5 4 c 3 指出的弦及每条弦对应的基本回路和对应 的基本回路系统。 指出的所有树枝及每条树枝对应的基本割集。 2、求出下面的赋权图的一棵最小生成树T，并计算出T的权。 草稿区，此处答题无效 设R是集合. R是A上的 二元关系, 其中 , 求出r(R), s(R), t(R)； 4、有向图如图所示，求： (1) 它的邻接矩阵， (2) 从v4到的长度为1，2，3，4的路径各有多少条？ (3) 从结点从到的长度不大于4的不同路径的条数. 草稿区，此处答题无效 ——第2页—— ——第1页—— ——第1页—— (D) (C) (B) (A) 密封线内不答题 系名____________班级____________