离散数学习题集(十五套)

有回路。(否则G为k棵树构成的森林,每棵树的顶点数为ni,边数mi,则

mi?ni?1,i?1?k ,

kk ?ni?n?11,?mi?mi?1i?1kk

?28?m??mi??(ni?1)?n?k?11?ki?1i?1 矛盾)

下面用反证法证明G为非平面图。

假设G为平面图,由于G中有回路且G为简单图,因而回路长大于等于3 。于是G

的每个面至少由g (g?3)条边围成,由点、边、面数的关系

m?g(n?k?1)g?2,得:

28?m?g3(11?k?1)?(11?(k?1))?3(11?(1?1))?3?11?3?2?27g?23?1

而 28?27矛盾,所以G为非平面图。

''(2)当n>11时,考虑G的具有11个顶点的子图G,则G或G必为非平面图。

'如果G为非平面图,则G为非平面图。 如果G为非平面图,则G为非平面图。 4、 (15分)

1)[{0,1},+,·]是环 ①[{0,1},+]是交换群

乘:由“+”运算表知其封闭性。由于运算表的对称性知:+运算可交换。 群: (0+0)+0=0+(0+0)=0 ;(0+0)+1=0+(0+1)=1;

(0+1)+0=0+(1+0)=1 ;(0+1)+1=0+(1+1)=0; (1+1)+1=1+(1+1)=0 ?? 结合律成立。

幺:幺元为0。

逆:0,1逆元均为其本身。所以,<{0,1},+>是Abel群。 ②<{0,1},·>是半群 乘:由“· ”运算表知封闭

群: (0·0)·0=0·(0·0)=0 ;(0·0)·1=0·(0·1)=1;

(0·1)·0=0·(1·0)=1 ;(0·1)·1=0·(1·1)=0; (1·1)·1=1·(1·1)=0 ;? ③·对+的分配律 对?x,y?{0,1}

Ⅰ 0·(x+y)=0=0+0=(0·x)+(0·y) Ⅱ 1·(x+y)

''当x=y (x+y)=0 则

?0?0??(1?0)?(1?0)?1?(x?y)?1?0?0???????(1?x)?(1?y)?1?1??(1?1)?(1?1)?

当x?y(x?y?1)则

?1?0??(1?1)?(1?0)?1?(x?y)?1?1?1???????(1?x)?(1?y)0?1(1?0)?(1?1)????

所以?x,y,z?{0,1}均有z?(x?y)?(z?x)?(z?y) 同理可证:(x?y)?z?(x?z)?(y?z) 所以·对+ 是可分配的。

由①②③得,<{0,1},+,·>是环。 (2)<{0,1},+,·>是域

因为<{0,1},+,·>是有限环,故只需证明是整环即可。 ①乘交环: 由乘法运算表的对称性知,乘法可交换。 ②含幺环:乘法的幺元是1 ③无零因子:1·1=1≠0

因此[{0,1},+,·]是整环,故它是域。

二十三、

树的应用 20%

1、(10分)解: 用库斯克(Kruskal)算法求产生的最优树。算法略。结果如图:

树权C(T)=23+1+4+9+3+17=57即为总造价 五、(10分)

由二叉树知

H、A、P、Y、N、E、W、R对应的

编码分别为

000、001、010、011、100、101、110、111。 显然{000,001,010,011,100,101,110,111}为前缀码。 英文短语HAPPY NEW YEAR 的编码信息为 000 001 010 010 011 100 101 001 001 101 001 111

六、5%

可结合性 可交换性 存在幺元 存在零元

试卷九试题与答案

Max Y Y N N Min Y Y N N + Y Y Y N 一、 填空 30% (每空 3分)

1、 选择合适的论域和谓词表达集合A=“直角坐标系中,单位元(不包括单位圆周)

的点集”则A= 。 2、 集合A={?,{?}}的幂集P(A) = 。 3、 设A={1,2,3,4},A上二元关系R={<1,2>,<2,1>,<2,3>,<3,4>}画出R

的关系图

。 4、 设A={<1,2>,<2 , 4 >,<3 , 3 >} , B={<1,3>,<2,4>,<4,2>},

则A?B= 。

A?B= 。

5、 设|A|=3,则A上有 个二元关系。

6、 A={1,2,3}上关系R= 时,R既是对称的又是反对称的。

7、 偏序集?A,R??的哈斯图为

R?= 。

8、 设|X|=n,|Y|=m则(1)从X到Y有 个不同的函数。

(2)当n , m满足 时,存在双射有 个不同的双射。 9、 2是有理数的真值为 。 10、

Q:我将去上海,R:我有时间,公式(Q?R)?(R?Q)的

为 。 11、

公式(Q?P)?(?P?Q)的 主

是 。 12、 则

若S?{S1 ,S2 ,?, Sm}是集合A的一个分划,

足 。

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

1、 设全集为I,下列相等的集合是( )。

}; B、B?{x|? y(y?I?x?2y)}; A、A?{x|x是偶数或奇数C、C?{x|? y(y?I?x?2y?1)}; D、D?{x|0,1,?1,2,?2,3,?3,4,?4,?}。 2、 设S={N,Q,R},下列命题正确的是( )。 A、2?N,N?S 则2?S; B、N?Q,Q?S 则N?S; C、N?Q,Q?R 则N?R; D、??N,??S 则??N?S。

S与?S?3、 设C={{a},{b},{a,b}},则分别为( )。

S?CS?CA、C和{a,b};B、{a,b}与?;C、{a,b}与{a,b};D、C与C 4、 下列语句不是命题的有( )。

A、 x=13; B、离散数学是计算机系的一门必修课; C、鸡有三只脚; D、太阳系以外的星球上有生物; E、你打算考硕士研究生吗? 5、 (P?Q)?R的合取范式为( )。

A、(P??Q)?R ;B、(P?R)?(?Q?R) ; C、

(P??Q?R)?(P??Q??R)?(P?Q?R)?(P??Q?R)?(?P?Q?R)?(?P??Q?R)

联系客服:779662525#qq.com(#替换为@)