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

。

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

（列举法）。

R的关系矩阵MR=

。

5、设A={1，2，3}，则A上既不是对称的又不是反对称的关系

R= ；A上既是对称的又是反对称的关系R= 。

6、设代数系统，其中A={a，b，c},

* a b c a b c a b c b b c c c b

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

7、4阶群必是 群或 群。 8、下面偏序格是分配格的是 。

9、n个结点的无向完全图Kn的边数为 ，欧拉图的充要条件是 。 10、公式(P?(?P?Q))?((?P?Q)??R的根树表示为

。 二、选择 20% （每小题2分）

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?b3,C．S?{x|x?2n?1,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、

设R是实数集合，“?”为普通乘法，则代数系统 是（ ）。

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

三、证明 46%

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

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

明若R是A上一个等价关系，则S也是A上的一个等价关系。（9分）

2、 用逻辑推理证明：

所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。（11分）

3、 若f:A?B是从A到B的函数，定义一个函数g:B?2对任意b?B有

Ag(b)?{x|(x?A)?(f(x)?b)}，证明：若f是A到B的满射，则g是从B到 2

A的单射。（10分）

4、 若无向图G中只有两个奇数度结点，则这两个结点一定连通。（8分）

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

Hamilton图（8分）

m?1(n?1)(n?2)?22，则G是

四、计算 14%

1、 设是一个群，这里+6是模6加法，Z6={[0 ]，[1]，[2]，[3]，[4]，[5]}，

试求出的所有子群及其相应左陪集。（7分）

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

试卷三试题与答案

一、 填空 20% （每空 2分）

1、 设 f，g是自然数集N上的函数?x?N,f(x)?x?1,g(x)?2x，

则f?g(x)? 。

2、 设A={a，b，c}，A上二元关系R={< a, a > , < a, b >,< a, c >, < c, c>} ,

则s（R）= 。

3、 A={1，2，3，4，5，6}，A上二元关系T?{?x,y?|x?y是素数}，则用列举

法

T= ； T的关系图为

； T具有 性质。 4、 集

合

A?{{?,2},{2}}的幂集

2A= 。

5、 P，Q真值为0 ；R，S真值为1。则wff(P?(R?S))?((P?Q)?(R?S))的

真值为 。 6、 wff?((P?Q)?R)?R的

主

合

取

范

式

为 。

7、 设 P（x）：x是素数， E(x)：x 是偶数，O(x)：x是奇数 N (x,y)：x可以整数y。

则谓词wff?x(P(x)??y(O(y)?N(y,x)))的自然语言是

。 8、 谓词wff?x?y(?z(P(x,z)?P(y,z))??uQ(x,y,u))的前束范式为

。