名 业 学 专 学 姓 院 、业 班 姓 系 班 级 号 号 名学院、学系专级山东轻工业学院 *******学年第***学期《离散数学》期末考试试卷
(A卷) （本试卷共6 页）
得分 卷人 ···············································································································密·密封·封线·线 题号 得分 一 二 三 四 五 总分 一、填空题（每空2分，共20分）
1．有n个顶点的完全图Kn，它的边数m= 。 2．集合A有n个元素，那么幂集P(A)的元素个数为 。
3．若p：2<1,q：3<2，可把命题 “2<1仅当3<2”符号化为 。 4．笛卡尔积的符号化表示为A?B= 。 5．在任何无向图中，所有顶点度数之和等于 。 6．有2个命题变项的公式A?m1∨m2,它的主合取范式为： 。 7．“王栋生于1992年或1993年。”中的“或”是 （相容或、排斥或）。
8．无向图G是欧拉图当且仅当G是连通图且 。 9．集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={
10．函数f:N?N, f(x)=x2+2，是 （满射、单射、双射）。
得分 阅卷人 二、名词解释（共10分）。 1．（2分）命题：
2．（2分）无向树
3．（3分）n阶完全图：
1
4．（3分）等价关系：
得分 阅卷人 三．计算题（共40分）
1．（3分）设p、q的真值为0；r、s的真值为1，求公式：
(p?r)∧(﹁q∨s)的真值。
2．（3分）给出{1,2,3}集合上的所有等价关系。
3.（3分）在全总个体域下符号化“有的人登上过月球。”
4．(3分) 设集合A＝{?,{1}, a, {1, a }}，B={{1}, {a}, {1, a }}，求B?A。
5．(4分) 求空集?的幂集P(?),以及空集幂集的幂集P(P(?))。
6．(4分)用等值演算法判断公式? (p∧q→q)的类型
7．(5分)集合A?{1,2,3,4}上的关系R如右图所示 (1) 写出R的集合形式
2
学院、系 专业班级 学号 姓名 (2)R不具有什么性质。 ··································································································密·封·线· 8．(5分)一棵树T中，有3个2度顶点，一个3度顶点，其余结点都是树叶。
问：T中有几个顶点？
9．(5分)设集合A={a,b,c}，A上的二元关系：
R={,
10．(5分)设A={1,2,?,10},下列哪个是A的划分？若是划分，则它们诱导的等价关系是什么？
(1) B={{1,3,6},{2,8,10},{4,5,7}} (2) C={{1,5,7},{2,4,8,9},{3,5,6,10}} (3) D={{1,2,7},{3,5,10},{4,6,8},{9}}
3
得分 阅卷人 四.画图题(每小题5分共20分，画在空白处，标明题号）
1．画出(p→q)→?q的真值表。 2．画彼德松（Peterson）图。
3．设A={1,2,3,4,5},作出A上整除关系R的哈斯图 4．画一棵权为3,4,5,6,7,8,9的最优二叉树并计算它的权重。
得分 阅卷人 五、（10分）在自然推理系统P中构造下列推理的证明 如果小张和小王去看电影，则小李也去看电影；小赵不去看电影或小张去看电影；小王去看电影。所以，当小赵
去看电影时，小李也去看电影。
4