离散数学期末考试题(附答案和含解析3)

1、一、单项选择题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.一棵树有5个3度结点，2

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(x+3)=2(x

3、+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),即R中

4、所有有序对的第二元素构成的集合。 关系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是获得知