离散数学2015年1月份试题.docVIP

离散数学试题 一、单项选择题（每小题3分，本题共15分） 1．若集合A＝{b, c, d}，则下列表述正确的是( )． A．{ b, c, d }(A B． A ( {c, d } C．{ b, c, d }(A D．{b, c}(A 2．已知无向图G的邻接矩阵为 ，则G有（ ）． A．6点，10边 B．5点，12边 C．6点，5边 D．5点，6边 3．无向图G是个棵树，结点数为10，则G的边数是（ ）． A．9 B．10 C．11 D．12x）：x是人，B（x）：x是工人，则命题“有人是工人”可符号化为（ ）． A．(x)(A(x)∧B(x)) B．┐((x)(A(x) →B(x)) C．(x)(A(x)∧B(x)) D．┐(x)(A(x)∧┐B(x)) 5．下面的推理正确的是（ ）． A．(1) （(x）F（x）→G（x） 前提引入 (2) F（y）→G（y） US（1）． B．(1) （(x）（F（x）→G（x）） 前提引入 (2) F（y）→ G（y） US（1）． C．(1) （(x）F（x）→G（x） 前提引入 (2) F（y）→G（y） US（1）． D．(1) （(x）(F（x）→G（x）） 前提引入 (2) F（y）→G（x） ES（1）． 二、填空题（每小题3分，本题共15分） 6．设A={a，b，c}，B={1，2，3}，作f：A→B，则不同的函数个数为 ． 7．任一无向图中，度数为奇数的结点的个数为 ． 8．设G是汉密尔顿图，S是其结点集的一个子集，若S的元素个数为6，则在G -S中的连通分支数不超过 ． 9．设G是有8个结点的连通图，结点的度数之和为28，则可从G中删去 条边后使之变成树． 10．设个体域D＝{1, 2}，则谓词公式((x)P(x) ∨（(x）Q（x）消去量词后的等值式为 ． 三、逻辑公式翻译（每小题6分，本题共12分） 11．将语句“小张小李都可以完成这项工作”翻译成命题公式． 12．将语句“a是偶数当且仅当a能被2整除．”翻译成命题公式． 四、判断说明题（每小题7分，本题共14分） 判断下列各题正误，并说明理由． 13．存在集合A与B，使得A(B与A(B同时成立． 14．完全图K5是平面图． 五计算题（每小题12分，本题共36分） 15．设A={2,3,6,12,24,36}，B为A的子集，其中B={6,12}，R是A上的整除关系，试 （1）写出R的关系表达式； （2）说明R为偏序关系； （3）画出关系R的哈斯图； （4）求出B的最大元素、极大元素、上确界． 16．．设图G=V，E，V={ v1，v2，v3，v4，v5}，E={ (v1, v2)，(v1, v3)，(v1, v5)，(v2, v3)，(v2, v4)，(v2, v5)，(v3, v4)，(v3, v5)，(v4, v5) }，试 （1）画出G的图形表示； （2）写出其邻接矩阵； （3）求出每个结点的度数； （4）画出图G的补图的图形． 17．求P→（Q∧R）的合取范式与主合取范式． 六、证明题（本题共8分） 18．对任意集合A，B和C，若有C ( (，则有：A(B的充分必要条件是C( A ( C(B． 离散数学试题 解答 一、单项选择题（每小题3分，本题共15分） 1．D 2．D 3．A 4．C 5．B 二、填空题（每小题3分，本题共15分） 6．27 7．偶数 8．6 9．7 10．(P (1)∧P (2)) ∨(Q（1）∨Q（2)) 三、逻辑公式翻译（每小题6分，本题共12分） 11．设P：小张可以完成这项工作，Q：小李可以完成这项工作． （2分） 则命题公式为：P∧Q．