离散数学试卷二试题与答案

试卷二试题与答案

一、填空

1、 设P：你努力，Q：你失败。

2、 “除非你努力，否则你将失败”的符号化为； 3、 “虽然你努力了，但还是失败了”的符号化为 。 2、论域D={1，2}，指定谓词P

则公式 x yP(y,x)真值为 。

3设A={2，3，4，5，6}上的二元关系R { x,y |x y x是质数}，则

（列举法）。

R的关系矩阵MR=

。 4、 设A={1，2，3}，则

A上既不是对称的又不是反对称的关系R= ； A上既是对称的又是反对称的关系R= 。 5、设代数系统<A，*>，其中A={a，b，c},

则幺元是 ；是否有幂等 性 ；是否有对称性 。

6、4阶群必是 群或

群。

7、下面偏序格是分配格的是 。

8、n个结点的无向完全图Kn的边数为 。 二、选择

1、在下述公式中是重言式为（ ）

A．(P Q) (P Q)；B．(P Q) ((P Q) (Q P))；

C． (P Q) Q； D．P (P Q)。

2、命题公式 ( P Q) ( Q P) 中极小项的个数为（ ），成真赋值的个数为（ ）。

A．0； B．1； C．2； D．3 。

S

3、设S { ,{1},{1,2}}，则 2 有（ ）个元素。

A．3； B．6； C．7； D．8 。 4、设S { 1, 2, 3 }，定义S S上的等价关系

R { a,b , c,d | a,b S S, c,d S S,a d b c}则由 R产 生的S S上一个划分共有（ ）个分块。

A．4； B．5； C．6； D．9 。 5、设S { 1, 2, 3 }，S上关系R的关系图为

则R具有（ ）性质。

A．自反性、对称性、传递性； B．反自反性、反对称性； C．反自反性、反对称性、传递性； D．自反性 。

6、设 , 为普通加法和乘法，则（ ） S, , 是域。 A．S {x|x a bC．S {x|x 2n 1,

3,

a,b Q} B．S {x|x 2n,a,b Z}

n Z} D．S {x|x Z x 0}= N 。

7、下面偏序集（ ）能构成格。

8、在如下的有向图中，从V1到V4长度为3 的道路有（ ）条。

A．1； B．2； C．3； D．4 。 9、在如下各图中（ ）欧拉图。

10、

10、设R是实数集合，“ ”为普通乘法，则代数系统<R ，×> 是（ ）。

A．群； B．独异点； C．半群 。

三、证明

1、设R是A上一个二元关系，

S { a,b |(a,b A) (对于某一个c A,有 a,c R且 c,b R)}

试证明若R是A上一个等价关系，则S也是A上的一个等价关系。 2、 用逻辑推理证明：

所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。 3、若无向图G中只有两个奇数度结点，则这两个结点一定连通。

m

4、设G是具有n个结点的无向简单图，其边数四、计算

12

(n 1)(n 2) 2

，则G是Hamilton图。

1、 1、设A={1，2，3，4}，S={{1}，{2，3}，{4}}，为A的一个分划，求由S导出的等价关系。 （4分）

2、 设Ｚ为整数集，关系R { a,b |a,b Z a b(modk)}为Z上等价关系，求R的模K等

价关系的商集Z/R，并指出R有秩。（5分）

3、 设A={1，2，3，4，5}，A上的偏序关系为

求A的子集{3，4，5}和{1，2，3}，的上界，下界，上确界和下确界。（6分）

4、权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。

试卷二参考答案：

一、 填空

1、 P Q；P Q 2、T

3、R={<2,2>,<2,3>,<2,4>,<2,5>,<2,6>,<3,2>,<3,3>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>,

<5,2>,<5,3>,<5,4>,<5,5>,<5,6>}；

4、R={<1,2>,<1,3>,<2,1>}；R={<1,1>,<2,2>,<3,3>} 5、a ；否；有

6、Klein四元群；循环群 7、 B

1 1 0 1 0

11010

11010

11110

1 1 1 1 0

1

8、2

n(n 1)

；图中无奇度结点且连通

二、选择

三、证明1、

1、设R是A上一个二元关系，

S { a,b |(a,b A) (对于某一个c A,有 a,c R且 c,b R)}

试证明若R是A上一个等价关系，则S也是A上的一个等价关系。

（1） （2）

S自反的 S对称的

a A，由R自反， ( a,a R) ( a,a R)， a,a S

a,b A

a,b S ( a,c R) ( c,b R)

( a,c R) ( c,b R) b,a S

（3）

S传递的

S定义 R对称 R传递

a,b,c A

a,b S b,c S

( a,d R) ( d,b R) ( b,e R) ( e,c R) ( a,b R) ( b,c R) a,c S

由（1）、（2）、（3）得；S是等价关系。 2、

证明：设P(x)：x 是个舞蹈者； Q(x) ：x很有风度； S(x)：x是个学生； a：王华 上述句子符号化为：

前提： x(P(x) Q(x))、S(a) P(a) 结论： x(S(x) Q(x)) 3分

①S(a) P(a) ② x(P(x) Q(x)) ③P(a) Q(a) ④P(a) ⑤Q(a).

P P US② T①I T③④I

R传递 S定义

⑥S(a) ⑦S(a) Q(a) ⑧ x(S(x) Q(x)

T①I T⑤⑥I EG⑦

11分

３、证明 ： b1,b2 B,(b1 b2) f满射 a1,a2 A

使f(a1) b1,f(a2) b2,且f(a1) f(a2),由于f是函数, a1 a2 又g(b1) {x|(x A) (f(x) b1)},g(b2) {x|(x A) (f(x) b2)}

a1 g(b1),a2 g(b2)

但a1 g(b2),a2 g(b1) g(b1) g(b2)

由b1,b2任意性知

,

g为单射。

4、证明：设G中两奇数度结点分别为u 和v，若 u，v不连通，则G至少有两个连通分支G1、G2 ，使得u和v分别属于G1和G2，于是G1和G2中各含有1个奇数度结点，这与图论基本定理矛盾，因而u，v一定连通。

5、证明： 证G中任何两结点之和不小于n。

反证法：若存在两结点u，v 不相邻且d(u) d(v) n 1,令V1 {u,v}，则G-V1是具有n-2

m

个结点的简单图，它的边数

'

12

(n 1)(n 2) 2 (n 1)

,可得

m

'

12

(n 2)(n 3) 1

，这与G1=G-V1为n-2个结点为简单图的题设矛盾，因而G中任何两个

相邻的结点度数和不少于n。

所以G为Hamilton图.

四、 计算

1、设A={1，2，3，4}，S={{1}，{2，3}，{4}}，为A的一个分划，求由S导出的等价关系。

（4分）

1、（4分）R={< 1 , 1 > , < 2 , 2> , < 2, 3 > , < 3 , 2 > , < 3 , 3 > < 4 , 4 > } 。 2、（5分）Z/R={[0]，[1]， ，[k-1]} ，所以R秩为k。

3、（6分）{3，4，5}：上界：1，3；上确界：3；下界：无；下确界：无；

{1，2，3}：上界：1；上确界：1；下界：4；下确界：4。

4.