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

试卷二十试题与答案

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

1．n 个命题变元有 个互不等价的极小项。

n?A1??A2????An?2．按De-Morgan定理，??A= 。

ii?13．公式P?(?Q?R)的主析取范式为 。

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

。

?1???1?1?0111??0?1??，则

MR5．设X?{a,b,c}，X上的关系R的关系矩阵是 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}n对（ ）运算封闭。

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

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%逻辑推理：

符号化命题“有些病人相信医生，但是没有病人相信法轮功，因此医生都不信法轮功”。用演绎法证明其结论。（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和g:Y?Z是映射且使得g?f是满射，若g是入射，证明f是满射。

六、图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%

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

八、道路的基本性质10%

设u ，v是树T的两个不同的结点，从u至v的基本通路（结点不同的道路）是T中最长的基本道路，证明：d(u)=d(v)=1。

九、子群12%

若H是G的子群，a,b?G，则 b答案

?1?a?H?aH?bH?? 。

一、填空20%

n 1、2； 2、

n?(?Ai)i?1；

(?P??Q??R)?(?P??Q?R)?(?P?Q??R)?(?P?Q?R)3、

?(P??Q??R)?(P??Q?R)?(P?Q?R)??0,1,2,3,4,5,7；

?111????111??111??x?y(P(x)?Q(y)?R(x,y))?； 6、n-1 ； 4、；5、?7、?(G)??(G)??(G)； 8、m?3n?6； 9、x?y10、含幺元，可交换，无零因子。

?1?H；

二、选择10%

题号 答案 1 C 2 B 3 C 4 D 5 B 三、12% 解：前提：?x(P(x)??y(D(y)?L(x,y)) 结论：?y(D(y)??Q(y)) 演绎推理：

（1）?x(P(x)??y(D(y)?L(x,y)) （2）P(e)??y(D(y)?L(e,y)) P

,?x(P(x)??y(L(x,y)??Q(y)))

ES(1)

（3）?x(P(x)??y(L(x,y)??Q(y))) P （4）P(e)??y(L(e,y)??Q(y)) US(3) （5）P(e) T(2)I （6）?y(L(e,y)??Q(y)) T(4)(5)I

（7）L(e,c)??Q(c) US(6) （8）?y(D(y)?L(e,y)) （9）D(c)?L(e,c) T(2)I

US(8)

（10）D(c)??Q(c) T(9)(7)I （11）?y(D(y)??Q(y)) UG(10)

四、解：

① A中最大元为x1，最小元不存在； ② {x3,x4,x5}上界x1,x3，上确界x1；下界无，下确界无。

五、解：

证：?y?Y，因g是映射，故必存在z?Z使g(y)?z，由于g?f(x)?z即 g(f(x))?z?g(y)，因g是单射，所以 f(x)?y 说明?y?Y，必有 x?X使得f(x)?y，故f(x)是满射。

六、解：

证：因为G是结点数n?3的简单连通平面图，所以 m?3n?6，又由于m?2且

连通简单平面图的每个面至少有3条边围成，于是3r?2m?2(3n?6)，所以 r?2n?4 。

七、解：

用100乘各频率得权数：

w1=35， w2=20， w3=15， w4=10， w5=10， w6=5， w7=5 将其由小到大排列用 Huffman算法可求得最优树。 5 5 10 10 15 20 35 10 10 10 15 20 35 20 10 15 20 35 20 25 20 35 40 25 35

40

100

最优二叉树为

60

编码树为：

前缀码：a：11； b：01； c：101； d：100； e：001；f：0000；g：0001

八、解：

设l为T中最长的基本道路且以u 为起点，v 为终点，即l?uv1v2?vkv

u v 如果d(u)?1，则u 的邻接点除了v1之外还有一点，

v1 vk

l上，否则 不妨设为u1，而u1不在T中存在回路uv1v2?u1u即 与T为树矛盾。于是得到一条l??u1uv1v2?vkv是比l更长的基本道路，这与l是最长的道路矛盾，故d(u)?1。同理可证 d(v)?1 。

u v1

u1

vk

v

九、证：

\?\

因为 b?1?1?a?H所以（b?1?1?a）?a?1?1?b?H，

又 b?(a?a a?(b?b)?b?a?(a)?a?b?(b?b)?a)??b?aH a?bH

?1?1?x?aH?x?a?h1?(b?h)?h1?b?(h?h1)?bH ?aH?bH

同理可证 bH?aH 所以 故 aH?bH?aH??

\?\

aH?bH

若 aH?bH?? 设 x?aH?bH 则

?h1,h2?H 使 x?a?h1?b?h2 可得：b

?1?a?h2?h1?H。

?1