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

1 / 5 最新离散数学期末考试题(附答案和含解析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 ．是群；

B ．是群；

C ．是群；

D ．， ，都不是群.

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

10.下面不满足．．．

结合律的运算是( C ) A.),min(b a b a = ； B.),max(b a b a = ； C.)(2b a b a +=

；D.ab b a 2= 二、填空题

12.设f ∶R →R ，f(x)=x+3，g ∶R →R ，g(x)=2x+1，则复合函数=))(g (f x 42+x ， =)x )(f (g 72+x

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

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

//备注：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.命题公式)(Q P P ∧→的成真指派为 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 叉树.如果每一个结点的出度 都

或0，则称这棵树为完全m 叉树.如果这棵树的叶 都在同一层 ，那么称为正则m 叉树.

>是一个群，其中Zn={0，1，2，……，n-1}，n y x y x mod )(+=⊕

，则在 中，1的阶是 6 ，4的阶是 3 . //单位元是e =0

19. n 点完全图记为K n ，那么当 n ≤ 4 时，K n 是平面图，当 n ≥ 5 时，K n 是非平面图.

20. 若图中存在 回路 ，它经过图中所有的结点恰好 一次 ，则称该图为汉密尔顿图(哈密顿图) . // 欧拉图

三、计算题

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

解： )()(P Q Q P ∨?→→??)()(P Q Q P ∨?→∨

?)()(P Q Q P ∨?∨∨??)()(P Q Q P ∨?∨?∧?

?))(())(()(Q Q P Q P P Q P ?∨∧∨?∧?∨∨?∧?

?))()()()()(Q P Q P Q P Q P Q P ?∧∨∧∨?∧?∨?∧∨?∧?

?))()()(Q P Q P Q P ∧∨?∧∨?∧?=111000m m m ∨∨=∑)3,2,0(

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>}，得

??????? ??=0000100001010010R M ， 从而??????

? ??=00000000101001012MR ，

3 / 5 ??????? ??=00000000010110103MR ， ??????

? ??=00000000101001014MR ，于是 2R ={<1，1>，<1，3>，<2，2>，<2，4>}，3R ={<1，2>，<1，4>，<2，1>，<2，3>}，

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

432)(R R R R R t ==｛<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 中的最大

元、最小元、极大元、极小元.

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

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

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

解：所有5元子格如下：

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

4 /

5 所以，图中结点v 1，v 3之间长度为2的路径的数目有3条.

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

四、证明题

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

证明：（1）对于Z b a ∈?,，有Z 1∈++=b a b

a ，所以运算 是封闭的.

（2）对于Z c b a ∈?,,，有 2c b a 1c 1b a c )1()(+++=++++=++= b a c b a ，

2c b a 11c b a )1()(+++=+++++=++=c b a c b a ，

即)()(c b a c b a =，故运算 是可结合的.

（3）1-是单位元，因为Z a ∈?，a a a

=+-=-11)1( ，a a a =++-=-11)1( . （4）Z a ∈?，由112)2(-=+--=--a a a a ，

112)2(-=++--=--a a a a ，可知 a --2是a 的逆元.

综上所述，是一个群.

28. 设R 为N ×N 上的二元关系，N N d c b a ?>∈<>

d b d c R b a =>?<><,,，证明R 为等价关系.

证明：因为N N b a ?>∈<>∈<><>

故><>

N N f e d c b a ?>∈<><><><><>

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

五、综合应用题

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

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

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

前提：（x ?）))()((x G x S →；

结论：→??)()(x G x )()(x S x ??

推理过程如下：

（1）（x ?）))()((x G x S → P

（2）)()(c G c S → US （1）

5 / 5 （3）)()(x G x ?? P （附加前提）

（4）)()(x G x ?? T(3)E

(5)

)(c G ? US(4) (6)

)(c S ? T(2)(5)I (7) )()(x S x ?? UG(6)

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