《离散数学期末考试题(附答案和含解析3).doc》由会员分享，可在线阅读，更多相关《离散数学期末考试题(附答案和含解析3).doc（5页珍藏版）》请在金锄头文库上搜索。
1、离散数学期末考试题(附答案和含解析3)2.设集合A=1；2；3；下列关系R中不是等价关系的是（ D ）A.R=； B.R=；C. R=；D. R=；.3在公式（）F（x；y）（ y）G（x；y）中变元x是（ B ）A自由变元；(前面无或量词) B既是自由变元；又是约束变元；C约束变元；(前面有或量词) D既不是自由变元；又不是约束变元.4设A=1；2；3；4；5；6；7；8；下列选项正确的是（C）A1A； B1；2；3A； C4；5A； DA.5.设论域为l；2；与公式等价的是( A )A.A(1)A(2)； B. A(1)A(2)； C.A(1)A(2)； D. A(2)A(1).6.一棵树
2、有5个3度结点；2个2度结点；其它的都是l度结点；那么这棵树的结点数是( B )A.13； B.14 ； C.16 ； D.17 ./设一度结点数为n；则有：53+22+n=2(5+2+n)-1 解得：n=7； 所以这棵树的结点数为：m=5+2+7=14.7设A是偶数集合；下列说法正确的是（A）A是群；B是群；C是群；D； ；都不是群。8下列图是欧拉图的是（ D ）10.下面不满足结合律的运算是( C )A.； B.； C.；D.二、填空题12.设fRR；f(x)=x+3；gRR；g(x)=2x+1；则复合函数 ； /f(g(x)=f(2x+1)=(2x+1)+3=2x+4/=g(f(x)=g
3、(x+3)=2(x+3)+1=2x+7/备注：fg=fg(x)=g(f(x)13设S是非空有限集；代数系统中；其中P（S）为集合S的幂集；则P（S）对运算的单位元是 ；零元是 S 。14设是格；其中A=1；2；3；4；6；8；12；24；为整除关系；则3的补元是 8 。 /（注：什么是格？ 即任意两个元素有最小上界和最大下界的偏序）15.命题公式的成真指派为 00；01；11 ；成假指派为 10 。16.设A=；B=；那么dom(AB)= 3 ； ran(AB)= 2；3；4；5/关系R的定义域：domR=x|y(R)；即R中所有有序对的第一元素构成的集合。 关系R的值域：ranR=y|x(R
4、)；即R中所有有序对的第二元素构成的集合。 关系R的域：fldR=domRranR17. 在根树中；若每一个结点的出度 最多为（或）m；则称这棵树为m叉树。如果每一个结点的出度 都为（或=）m或0；则称这棵树为完全m叉树。如果这棵树的叶 都在同一层 ；那么称为正则m叉树。18是一个群；其中Zn=0；1；2；n-1；则在中；1的阶是 6 ；4的阶是 3 。 /单位元是e=019. n点完全图记为Kn；那么当 n 4 时；Kn是平面图；当 n 5 时；Kn是非平面图。20. 若图中存在 回路 ；它经过图中所有的结点恰好 一次 ；则称该图为汉密尔顿图(哈密顿图) 。 / 欧拉图三、计算题21. 求命
5、题公式的主析取范式。解： =22. 设A=1；2；3；4；给上的二元关系R=；求R的传递闭包。解：由R=；得； 从而； ；于是=；=；=；=；故=；23.设A=1；2；3；4；6；8；12；24；R为A上的整除关系；试画的哈斯图；并求A中的最大元、最小元、极大元、极小元。 解：的哈斯图如右图所示： A中的最大元为24、最小元为1、极大元为24、极小元为1。24.求下图所示格的所有5元子格。 解：所有5元子格如下：26.用矩阵的方法求右图中结点v1；v3之间长度为2的路径的数目。/教材P289、290 所以；图中结点v1；v3之间长度为2的路径的数目有3条。/备注：邻接矩阵中所有元素之和等于边数
6、。通路（v1-v1；v2；v3；v4）与回路（v1-v1；v2-v2；v-v3）四、证明题27. 在整数集Z上定义：；证明：是一个群。证明：（1）对于；有；所以运算是封闭的。（2）对于；有；即；故运算是可结合的。（3）是单位元；因为；.（4）；由；可知 是的逆元。综上所述；是一个群。28. 设R为NN上的二元关系；证明R为等价关系。证明：因为；所以；故R具有自反性。；若；则；即；故；所以R具有对称性。；若；则；从而；故；所以R具有对称性。综上所述；R为等价关系。五、综合应用题29在谓词逻辑中构造下面推理的证明：每个在学校读书的人都获得知识。所以如果没有人获得知识就没有人在学校读书。（个体域：所有人的集合）证明：设S（x）:x是 在学校读书的人； G（x）：x是获得知识的人。前提：（）；结论：推理过程如下：（1）（） P（2） US（1）（3） P（附加前提）（4） T(3)E (5) US(4)(6) T(2)(5)I(7) UG(6)(8) T(7)E页码 / 总页数
