离散数学期末复习

离散数学

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

1．若对命题P赋值1，Q赋值0，则命题P?Q的真值为 。 2．命题“如果你不看电影，那么我也不看电影”（P：你看电影，Q：我看电影）的符号化为 3．公式?(P?Q)?(P??(Q??S))的对偶公式为

4．图 的对偶图为

5．若关系R是等价关系，则R满足 性质。 6．关系R的传递闭包t (R) = 。 7．代数系统?A,??是群，则它满足 8．设?A,?,??和?B,?,??是两代数系统，f是从?A,?,??到?B,?,??的同态映射，则f具有 性质。 9．树T的边数e与点数v有关系 。 二、选择10%（每小题2分）：

1．如果解释I使公式A为真，且使公式A?B也为真，则解释I使公式B为（ ）。

A、真； B、假； C、可满足； D、与解释I无关。

2．设A??a,b?，则P（A）×A = （ ）。 A、A ； B、P（A）；

C、???,a?,??,b?,?{a},a?,?{a},b?,?{b},a?,?{b},b?,?A,a?,?A,b?? ；

D、

??a,??,?b,??,?a,{a}?,?b,{a}?,?a,{b}?,?b,{b}?,?a,A?,?b,A??。

3．设集合A，B是有穷集合，且A?m,B?n，则从A到B有（ ）个不同的双射函数。 A、n ； B、m ； C、n! ； D、m! 。

4．设K = {e , a , b , c}，?K,??是Klein四元群，则元素a的逆元为（ ）。 A、e ； B、a ； C、b ； D、c。 5．一个割边集与任何生成树之间（ ）。

A、没有关系； B、割边集诱导子图是生成树； C、有一条公共边； D、至少有一条公共边。

123

离散数学

三、逻辑推理12%：

符号化命题“每个学术会的成员都是工人并且是专家，有些成员是青年人，所以有的成员是

青年专家”；并用演绎方法证明上面推理。（F(x)：x是学术会成员；H(x)：x是工人；G(x)：x是专家；R(x)：x是青年人） 四、8%：

求集合An??x0?x?五、12%：

在实数平面上，画出关系，并判定关系的特殊性质。 七、10%：

求图中的一棵最小生成树。 八、10%：

求图 的邻接矩阵和可达矩阵。 九、10%：

证明：如果G是无向简单图且??2，则G包含一条长度不小于??1的基本回路。 一、填空20%（每空2分）

1．n 个命题变元有 个互不等价的极小项。 2．按De-Morgan定理，?A1??A2????An?3．公式P?(?Q?R)的主析取范式为 。

4．设P(x)：x是大象，Q(x)：x是老鼠，R(x,y)：x比y重，则命题“大象比老鼠重”的符号化为

??1??(n?1,2,3,?)的并与交。 n???A = 。

ii?1n 124

离散数学

?101??? 5．设X?{a,b,c}，X上的关系R的关系矩阵是MR??110?，则

?111??? MR?R?

。

6．在具有n个结点的有向图中，任何基本通路的长度都不超过 。

7．任何图的点连通度?(G)，边连通度?(G)，最小点度?(G)的关系为

8．结点数n（n?3）的简单连通平面图的边数为m，则m与n的关系为 。 9．群G的非空子集H是G的子群当且仅当若x , y?H 则 。 10．代数系统?A,?,??是环，若对运算“· ”还满足 则?A,?,??是整环。 二、选择10%（每小题2分）

1．集合A?{xx?2,n?N}对（ ）运算封闭。

A、加法； B、减法； C、乘法； D、x?y 。

2．设I为整数集合，m是任意正整数，Zm是由模m的同余类组成的同余类集合，在Zm上定义

运算[i]?[j]?[(i?j)modm]，则代数系统?Zm,?m?最确切的性质是（ ）。 A、封闭的代数系统； B、半群； C、独异点； D、群。

3．设?N,??是偏序格，其中N是自然数集合，“≤”是普通的数间“小于等于” 关系，则 ?a,b?N有a?b?（ ）。

A、a ； B、b ； C、max(a，b) ； D、min(a，b)。

4．连通非平凡的无向图G有一条欧拉回路当且仅当图G ( )。

A、只有一个奇度结点； B、只有两个奇度结点； C、只有三个奇度结点； D、没有奇度结点。

5．设无向图G??V,E?是连通的且V?n,E?m 若（ ）则G是树。 A、M=N+1 ； B、n=m+1 ； C、m?3n?6 ； D、n?3m?6 。 三、12%逻辑推理：

n 125

离散数学

符号化命题“有些病人相信医生，但是没有病人相信法轮功，因此医生都不信法轮功”。用演绎法证明其结论。（P(x)：x是病人，D(x)：x是医生，Q(x)：x是法轮功练习者，L(x , y)：x相信y） 四、序关系8%：

设A?{x1,x2,x3,x4,x5}，偏序集?A,R?的Hass图为

求 ① A中最小元与最大元； ② {x3,x4,x5}的上界和上确界，下界和下确界。 五、函数8%

设f:X?Y和六、图8%

设G是连通简单平面图，结点数为n（n?3），边数为m，面数为r，则r?2n?4 。 七、树的应用12%

设7个符号在通讯中使用的频率如下：

a：35% ，b：20% ，c：15% ，d：10% ， e：10% ，f：5% ，g ：5%

编一个相应的二元前缀码，使通讯中出现的符号尽可能地减少，并画出对应的二叉树及求二叉树的过程。 九、子群12%

若H是G的子群，a,b?G，则 b一、问答10%

已知定义在集合{a,b,c,d}上的运算*如下表： *

a b c d a a b c d b b a d c c c d b a d d c a b ?1g:Y?Z是映射且使得g?f是满射，若g是入射，证明f是满射。

?a?H?aH?bH?? 。

试问：1）?{a,b,c,d},??是代数系统否？（ ）

2）?{a,b,c,d},??是子群否？（ ） 3）?{a,b,c,d},??是群否？（ ）

126

离散数学

4）?{a,b,c,d},??有单位元否？（ ） 5）?{a,b,c,d},??满足交换律否？（ ）

二、填空10%

下表中的运算均定义在实数集上，请在相应的空格中打“√”或填上具体实数（不满足或无该项者不填）

结合律 交换律 幺元（含左、右幺元） 零元（含左、右零元）

三、有向图的矩阵表示应用15%

+ - × v1?0?v2?0已知某有向图的邻接矩阵如下：A??v31?v4??1路径的条数。 四、图的同构15%

v1 v2 v3 v4

001011000??1? 试求：v3到v1的长度为4的有向?1?0??下面两图是否同构，若是给出点集间的同构映射。

127

本文来源：https://www.bwwdw.com/article/17kv.html