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

离散数学试题 一、单项选择题（每小题3分，本题共15分） 1．若集合A＝{1,2,3}，则下列表述正确的是 ( )． A．{1, 2, 3 }?A B．A ? {1, 2 } C．{1, 2, 3 }?A D．{1, 2}?A 2．已知无向图G 有10条边，则G的结点度数之和为（ ）． A．10 B．20 C．30 D．5 3．无向图G是棵树，边数为10，则G的结点数是（ ）． A． 5 B． 10 C． 9 D． 11 4．设A（x）：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） ES（1）． D．(1) （?x）(F（x）→G（x）） 前提引入 (2) F（y）→G（x） ES（1）． 二、填空题（每小题3分，本题共15分） 6．设A={1，2}，B={ a, b, c }，作f：A→B，则不同的函数个数为 ． 7．有n个结点的无向完全图的边数为 ． 8．设无向图G中存在欧拉回路，则G的奇数度数的结点数为 个． 9．设G是有8个结点的连通图，结点的度数之和为24，则可从G中删去 条边后使之变成树． 10．设个体域D＝{a, b, c}，则谓词公式(?x)A(x)消去量词后的等值式为 ． 三、逻辑公式翻译（每小题6分，本题共12分） 11．将语句“学生的主要任务是学习”翻译成命题公式． 12．将语句“我们下午2点或者去礼堂看电影或者去教室看书．”翻译成命题公式． 四、判断说明题（判断各题正误，并说明理由．每小题7分，本题共14分） 13．不存在集合A与B，使得A?B与A?B同时成立． 14．完全图K4是平面图． 五．计算题（每小题12分，本题共36分） 15．设偏序集A, R的哈斯图如下，B为A的子集，其中B={ a, b, c }，试 （1）写出R的关系表达式； （2）画出关系R的关系图； （3）求出B的最大元素、极小元素、上界． 16．．设图G=V，E，V={ v1，v2，v3，v4，v5}，E={ (v1, v2)，(v1, v4)，(v1, v5)，(v2, v4)，(v3, v5) }，试 （1）画出G的图形表示； （2）写出其邻接矩阵； （3）求出每个结点的度数； （4）画出图G的补图的图形． 17．求P→（Q∧R）的析取范式与主合取范式． 六、证明题（本题共8分） 18．设A，B，C均为任意集合，试证明：A ?( B ? C ) = (A? B ) ?(A ?C )． 离散数学试题 解答一、单项选择题（每小题3分，本题共15分） 1．C 2．B 3．D 4．A 5．C 二、填空题（每小题3分，本题共15分） 6．9 7．n(n-1)/2 8．0 9．5 10．A(a ) ∧A(b) ∧ A(c) 三、逻辑公式翻译（每小题6分，本题共12分） 11．设P：学生的主要任务是学习． （2分） 则命题公式为：P． （6分） 12．设P：我们下午2点去礼堂看电影， Q：我们下午2点去教室看书． （2分） 则命题公式为：?（P