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

一、单项选择题

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．在公式（?

x）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}，与公式(?x)A(x)等价的是( 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．是群； C．是群；

8．下列图是欧拉图的是（ D ）

B．是群；

D．, ,都不是群。

10.下面不满足结合律的运算是( C ) ．．．(a?A.a?b?min(a,b)； B.a?b?max(a,b)； C.a?b?2二、填空题

b)；D.a?b?2ab

12.设f∶R→R,f(x)=x+3,g∶R→R,g(x)=2x+1,则复合函数(f?g)(x)? 2x?4 ,

(g?f)(x)?2x?7

//(f?g)(x)?f(g(x))=f(2x+1)=(2x+1)+3=2x+4 //(g?f)(x)?=g(f(x))=g(x+3)=2(x+3)+1=2x+7

1

//备注：f?g=f?g(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.命题公式P?(P?Q)的成真指派为 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(∈R)},即R中所有有序对的第一元素构成的集合。 关系R的值域：ranR={?y|x(∈R)},即R中所有有序对的第二元素构成的集合。 关系R的域：fldR=domR∪ranR

17. 在根树中，若每一个结点的出度 最多为（或≤）m,则称这棵树为m叉树。如果每一个结点的出度 都为（或=）m或0，则称这棵树为完全m叉树。如果这棵树的叶 都在同一层 ，那么称为正则m叉树。 18．是一个群，其中Zn={0,1,2,……,n-1}，x?

y?(x?y)modn，则在

?>中，1的阶是 6 ，4的阶是 3 。 //单位元是e=0

19. n点完全图记为Kn，那么当 n ≤ 4 时，Kn是平面图，当 n ≥ 5 时，Kn是非平面图。 20. 若图中存在 回路 ，它经过图中所有的结点恰好 一次 ，则称该图为汉密尔顿图(哈密顿图) 。 // 欧拉图

三、计算题

21. 求命题公式(?P?Q)?(?Q?P)的主析取范式。

解：

(?P?Q)?(?Q?P)?(P?Q)?(?Q?P)

??(P?Q)?(?Q?P)?(?P??Q)?(?Q?P)

?(?P??Q)?((P??P)??Q)?(P?(Q??Q))

?(?P??Q)?(P??Q)?(?P??Q)?(P?Q)?(P??Q))

?(?P??Q)?(P??Q)?(P?Q))=m00?m10?m11=?(0,2,3)

22. 设A={1,2,3,4}，给A上的二元关系R={<1,2>,<2,1>,<2,3>,<3,4>}，求R的 传递闭包。

解：由R={<1,2>,<2,1>,<2,3>,<3,4>}，得

?0??1MR??0??0?100?，

?010?001??000?? 从而

?1??02MR??0??0?010?，

?101?000??000???0??13MR??0??0?101??10??010?， ?014MR???00000????000??0010??，于是 01?00??00?? 2

R2={<1,1>,<1,3>,<2,2>,<2,4>}，R3={<1,2>,<1,4>,<2,1>,<2,3>}，

2R4={<1,1>,<1,3>,<2,2>,<2,4>}=R，故

t(R)?R?R2?R3?R4=｛<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中的最大

元、最小元、极大元、极小元。

解：的哈斯图如右图所示：

24.求下图所示格的所有5元子格。

A中的最大元为24、最小元为1、极大元为24、极小元为1。

解：所有

5元子格如下：

26.用矩阵的方法求右图中结点v1，v3之间长度为2的路径的数目。//教材P289、290

所以，图中结点v1，v3之间长度为2的路径的数目有3条。

//备注：邻接矩阵中所有元素之和等于边数。通路（v1->v1,v2,v3,v4…）与回路（v1->v1,v2->v2,v->v3…）

3

四、证明题

27. 在整数集Z上定义：a?b?a?b?1,?a,b?Z，证明：是一个群。

证明：（1）对于?a,b?Z，有a?b（2）对于?a,b,c?Z，有

?a?b?1?Z，所以运算?是封闭的。

(a?b)?c?(a?b?1)?c?a?b?1?c?1?a?b?c?2， a?(b?c)?a?(b?c?1)?a?b??c?1?1?a?b?c?2，

即(a?b)?c?a?(b?c)，故运算?是可结合的。 （3）?1是单位元，因为?a?Z，a（4）?a?Z，由a?(?2?a)?(?1)?a?1?1?a，(?1)?a??1?a?1?a.

?a?2?a?1??1，

(?2?a)?a??2?a?a?1??1，可知 ?2?a是a的逆元。

综上所述，是一个群。

28. 设R为N×N上的二元关系，??a,b?,?c,d证明：因为??a,b??N??N?N，

?a,b?R?c,d??b?d，证明R为等价关系。

?N，b?b，所以?a,b?R?a,b?，故R具有自反性。

??a,b?,?c,d??N?N，若?a,b?R?c,d?，则b?d，即d?b， 故?c,d?R?a,b?，所以R具有对称性。

??a,b?,?c,d?,?e,f??N?N，若?a,b?R?c,d?，?c,d?R?e,f?，

则b?d，d?f从而b?f，故?a,b?R?e,f?，所以R具有对称性。

综上所述，R为等价关系。

五、综合应用题

29．在谓词逻辑中构造下面推理的证明：每个在学校读书的人都获得知识。所以如果没有人获得知识就没有人在学校

读书。（个体域：所有人的集合）

证明：设S（x）:x是 在学校读书的人， G（x）：x是获得知识的人。

前提：（?x）(S(x)?G(x))； 结论：?(?x)G(x)??(?x)S(x) 推理过程如下：

（1）（?x）(S(x)?G(x)) P （2）S(c)?G(c) US（1） （3）?(?x)G(x) P（附加前提） （4）(?x)?G(x) T(3)E (5) (6) (7)

?G(c) US(4) ?S(c) T(2)(5)I

(?x)?S(x) UG(6)

(8) ?(?x)S(x) T(7)E

4