离散数学期末考试题(附答案和含解析3).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　）
A．1∈A； B．{1，2，3}A； C．{{4，5}}A； 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.设f∶R→R,f(x)=x+3,g∶R→R,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(A∩B)=
{3} , ran(A∪B)= {2,3,4,5}
//关系R的定义域：domR={∃x|y(<x,y>∈R)},即R中所有有序对的第一元素构成的集合。
关系R的值域：ranR={∃y|x(<x,y>∈R)},即R中所有有序对的第二元素构成的集合。
关系R的域：fldR=domR∪ranR
17. 在根树中，若每一个结点的出度 最多为（或≤）m,则称这棵树为m叉树。如果每一个结点的出度 都为（或=）m或0，则称这棵树为完全m叉树。如果这棵树的叶 都在同一层 ，那么称为正则m叉树。
18．<Zn, >是一个群，其中Zn={0,1,2,……,n-1}，，则在
<Z6, >中，1的阶是 6 ，4的阶是 3 。 //单位元是e=0
19. 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
5