DOC《离散数学试题与答案试卷一》

a , c>

, , , <

b ,b >

, <

b , c . >

, <

b , d >

, <

c , d >

} 解: 用库斯克(Kruskal)算法求产生的最优树.算法略.结果如图: 树权C(T)=23+1+4+9+3+17=57即为总造价. 试卷二试题与答案

一、填空 20% (每小题2分) P:你努力,Q:你失败. 除非你努力,否则你将失败 的翻译为 ;

虽然你努力了,但还是失败了 的翻译为 .

2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式真值为 . 设S={a1 ,a2 ,…,a8},Bi是S的子集,则由B31所表达的子集是 . 设A={2,3,4,5,6}上的二元关系,则R= (列举法). R的关系矩阵MR= .

5、设A={1,2,3},则A上既不是对称的又不是反对称的关系R=A上既是对称的又是反对称的关系R= * a b c a b c a b c b b c c c b

6、设代数系统,其中A={a,b,c}, 则幺元是 ;

是否有幂等 性 ;

是否有对称性 .

7、4阶群必是 群或 群.

8、下面偏序格是分配格的是 .

9、n个结点的无向完全图Kn的边数为 ,欧拉图的充要条件是 .

10、公式的根树表示为 .

二、选择 20% (每小题2分)

1、在下述公式中是重言式为( A.;

B.;

C.;

D..

2、命题公式 中极小项的个数为( ),成真赋值的个数为( ). A.0;

B.1;

C.2;

D.3 .

3、设,则有( )个元素. A.3;

B.6;

C.7;

D.8 . 设,定义上的等价关系 则由 R产 生的上一个划分共有(个分块. A.4;

B.5;

C.6;

D.9 .

5、设,S上关系R的关系图为 则R具有(性质. A.自反性、对称性、传递性;

B.反自反性、反对称性;

C.反自反性、反对称性、传递性;

D.自反性 .

6、设 为普通加法和乘法,则(是域. A. B. C. D.= N .

7、下面偏序集( )能构成格.

8、在如下的有向图中,从V1到V4长度为3 的道路有(条. A.1;

B.2;

C.3;

D.4 .

9、在如下各图中( )欧拉图.

10、设R是实数集合, 为普通乘法,则代数系统 是( A.群;

B.独异点;

C.半群 .

三、证明 46% 设R是A上一个二元关系, 试证明若R是A上一个等价关系,则S也是A上的一个等价关系.(9分) 用逻辑推理证明: 所有的舞蹈者都很有风度,王华是个学生且是个舞蹈者.因此有些学生很有风度.(11分) 若是从A到B的函数,定义一个函数对任意有,证明:若f是A到B的满射,则g是从B到 的单射.(10分) 若无向图G中只有两个奇数度结点,则这两个结点一定连通.(8分) 设G是具有n个结点的无向简单图,其边数,则G是Hamilton图(8分)

四、计算 14% 设是一个群,这里+6是模6加法,Z6={[0 ],[1],[2],[3],[4],[5]},试求出的所有子群及其相应左陪集.(7分) 权数1,4,9,16,25,36,49,64,81,100构造一棵最优二叉树.(7分) 试卷二答案: 填空 20%(每小题2分)

1、;

2、T

3、

4、R={,,

,,

,,

,,

,,

,,

,,

,,

};

5、R={,,

};

R={,,

}

6、a ;

否;

有

7、Klein四元群;

循环群

8、 B

9、;

图中无奇度结点且连通

10 、 选择 20%(每小题 2分) 题目

1 2

3 4

5 6

7 8

9 10 答案 B、D D;

D D B D A B B B B、C 证明 46%

1、(9分) S自反的 ,由R自反,,

S对称的 S传递的 由(1)、(2)、(3)得;

S是等价关系.

2、11分 证明:设P(x):x 是个舞蹈者;

Q(x) :x很有风度;

S(x):x是个学生;

a:王华 上述句子符号化为: 前提:、 结论: ……3分①P②P③US② ④ T①I ⑤ T③④I ⑥ T①I ⑦ T⑤⑥I ⑧ EG⑦ ……11分

3、10分 证明 : .

4、8分 证明:设G中两奇数度结点分别为u 和v,若u,v不连通,则G至少有两个连通分支G