离散数学期末考试题(共5页).doc
精选优质文档-倾情为你奉上一、单项选择题2.设集合A=1，2，3，下列关系R中不是等价关系的是（ D ）A.R=<1,1>,<2,2>,<3,3>； B.R=<1,1>,<2,2>,<3,3>,<3,2>,<2,3>；C. R=<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>；D. R=<1,1>,<2,2>,<3,3>,<1,2 >.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； DÆA.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度结点，其它的都是l度结点，那么这棵树的结点数是( B )A.13； B.14 ； C.16 ； D.17 ./设一度结点数为n,则有：5×3+2×2+n=2(5+2+n)-1 解得：n=7, 所以这棵树的结点数为：m=5+2+7=14.7设A是偶数集合，下列说法正确的是（A）A<A,+>是群；B<A,×>是群；C<A,÷>是群；D<A,+>, <A,×>,<A,÷>都不是群。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)+1=2x+7/备注：fg=fg(x)=g(f(x)13设S是非空有限集，代数系统<P（S），>中，其中P（S）为集合S的幂集，则P（S）对运算的单位元是 ，零元是 S 。14设<A，>是格，其中A=1，2，3，4，6，8，12，24，为整除关系，则3的补元是 8 。 /（注：什么是格？ 即任意两个元素有最小上界和最大下界的偏序）15.命题公式的成真指派为 00，01，11 ，成假指派为 10 。16.设A=<2,2>，<3,4>,<3,5>，B=<1,3>，<2,5>,<3,4>，那么dom(AB)= 3 , ran(AB)= 2,3,4,5/关系R的定义域：domR=x|y(<x,y>R),即R中所有有序对的第一元素构成的集合。 关系R的值域：ranR=y|x(<x,y>R),即R中所有有序对的第二元素构成的集合。 关系R的域：fldR=domRranR17. 在根树中，若每一个结点的出度 最多为（或）m,则称这棵树为m叉树。如果每一个结点的出度 都为（或=）m或0，则称这棵树为完全m叉树。如果这棵树的叶 都在同一层 ，那么称为正则m叉树。18<Zn, >是一个群，其中Zn=0,1,2,n-1，则在<Z6, >中，1的阶是 6 ，4的阶是 3 。 /单位元是e=019. n点完全图记为Kn，那么当 n 4 时，Kn是平面图，当 n 5 时，Kn是非平面图。20. 若图中存在 回路 ，它经过图中所有的结点恰好 一次 ，则称该图为汉密尔顿图(哈密顿图) 。 / 欧拉图三、计算题21. 求命题公式的主析取范式。解： =22. 设A=1,2,3,4，给上的二元关系R=<1,2>,<2,1>,<2,3>,<3,4>，求R的传递闭包。解：由R=<1,2>,<2,1>,<2,3>,<3,4>，得， 从而， ，于是=<1,1>,<1,3>,<2,2>,<2,4>，=<1,2>,<1,4>,<2,1>,<2,3>，=<1,1>,<1,3>,<2,2>,<2,4>=，故=<1,1>,<1,2>,<1,3>,<1,4>,<2,1>,<2,2>，<2,3>，<2,4>，<3,4>23.设A=1，2，3，4，6，8，12，24，R为A上的整除关系，试画<A，R>的哈斯图，并求A中的最大元、最小元、极大元、极小元。 解：<A，R>的哈斯图如右图所示： A中的最大元为24、最小元为1、极大元为24、极小元为1。24.求下图所示格的所有5元子格。 解：所有5元子格如下：26.用矩阵的方法求右图中结点v1，v3之间长度为2的路径的数目。/教材P289、290 所以，图中结点v1，v3之间长度为2的路径的数目有3条。/备注：邻接矩阵中所有元素之和等于边数。通路（v1->v1,v2,v3,v4）与回路（v1->v1,v2->v2,v->v3）四、证明题27. 在整数集Z上定义：，证明：<Z，>是一个群。证明：（1）对于，有，所以运算是封闭的。（2）对于，有，即，故运算是可结合的。（3）是单位元，因为，.（4），由，可知 是的逆元。综上所述，<Z，>是一个群。28. 设R为N×N上的二元关系，证明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专心-专注-专业
