《离散数学》期末考试题(E)

浙江工商大学离散数学期末考试题

《离散数学》期末考试题(E)

一、填空题(每小题3分，共15分)

1.设A = {2, {3}, 4, a}, B = {1, 3, 4, {a}}, 则{3}( )A，{a}( )B，{{a}}( )B.

2. 设A = {1, 2, 3, 4, 5}上的关系R = {(1, 2), (3, 4), (2, 2)}, S = {(4, 2), (2, 5), (3, 1), (1, 3)}, 则R S { }, S R { }, R R { }.

3. gcd(36, 48) = ( )，lcm(36, 48) = ( ).

4.任意有限布尔代数(B, , ,,0,1)均与集合代数( )同构，其元素个数为

( ).

5. 不同构的5阶无向树有( )棵，不同构的5阶根树有( )棵.

二、单选题(每小题3分，共15分)

1. 在有理数集合Q上定义运算“*”如下：对于任意x, y Q，x y = x + y – xy，则Q关于*的单位元是( ).

(A)x. (B)y. (C)1. (D)0.

2. 设A = {1, 2, 3}, 下图分别给出了A上的两个关系R和S，则R S 是( )关系.

GR

GS

(A)自反. (B)对称. (C)传递. (D)等价.

3.令T(x): x是火车，B(x): x是汽车，F(x, y): x比y快，则“某些汽车比所有的火车慢”符号化为( ).

(A) y B(y) x T(x) H(x,y) .

(B) y B(y) x T(x) H(x,y) .

(C) x y B(y) T(x) H(x,y) .

浙江工商大学离散数学期末考试题

(D) y B(y) x T(x) H(x,y) .

4. 整数集合Z关于数的加法“+”和数的乘法“ ”构成的代数结构(Z, +, )是( ).

(A)域 (B)域和整环 (C)整环 (D) 有零因子环

5.设G是简单图，G是G的补图，若G G，则称G为自补图. 5阶不同构的自补图个数为( ).

(A)0. (B)1. (C)2. (D)3.

三、判断题(每小题3分，共15分): 正确打“√”，错误打“×”.

1. { , { }} P(P({ })). ( )

2. 非空1元及2元联结词集合的个数为29-1. ( )

3. 群可分为Abel群和非Abel群. ( )

4. 元素个数相同的有限域都是同构的. ( )

5. 设G是简单图，则G或G是连通图. ( )

四、(15分) 设f:A B,g:B C, 若f g是单射，证明f是单射，并举例说明g不一定是单射.

五、(10分) 设A = {a, b, c, d}上的关系R = {(a, b), (b, d), (c, c), (a, c)}, 画出R的关系图，并求出R的自反闭包r(R)、对称闭包s(R)和传递闭包t(R).

六、(10分)用CP规则证明下列推理.

p ( q r),q (r s),p q s.

七、(10分) 求谓词公式( xA(x) yB(y)) (A(x) zC(z))的前束范式.

八、(10分)任意6个人中，一定有3个人彼此认识或有3个人彼此不认识.