2023年7月19日发(作者：)

武汉大学2009-2010学年第一学期考试试卷

《离散数学》 （A卷）

（36学时用）

学院： 学号： 姓名： 得分： ______

一、 选择题（10×2分=20分）

1、下面的句子中是命题的有（ ）。

A、明天是晴天； B、请关门；C、请不要吸烟！D、2x35。

2、在下述公式中是重言式的是（ ）。

A．pC．p(pq)； B．(p(qr))((pq)(pr))q)q；

(((pq)p)q)； D．(p 。

3、设R，S是集合A上的关系，则下列说法正确的是（ ）

A．若R，S是自反的，则RS是自反的；

是反自反的； B．若R，S是反自反的，则R C．若R，S是对称的，则R D．若R，S是传递的，则R4、下面命题成立的有（ ）。

SSS是对称的；

是传递的

A、 若ACBC，则AB； B、若ACBC，则AB；

C、 若A5、集合BCBC，则AB； D、若AB，则AB。

{,{},{,{}}}的幂集为（ ）。

A、{{},{{},},}；

{,{},{{}},{{,{}}},{,{}},{,{,{}}},{{},{,{}}},B}；B、

C、{,{},{{}},{,{}},{,{}},{,{,{}}},{{},{,{}}},B}；

{}}},{{},{,{}}},,B} D、{{}{,{}},{,{，6、下面四组数能构成无向图的度数列的有（ ）。

A、 2,3,4,5,6,7； B、 1,2,2,3,4；

C、 2,1,1,1,2； D、 3,3,5,6,0。

7、图 的邻接矩阵为（）。

10001111011010A、0101；B、1111011010；C、011011；D、011101001101000111110101008、在（ ）下有ABA。

A、AB；B、BA；C、AB；D、A或B

9、设GV,E为无向图，V7,E23，则G一定是（ ）。

A、完全图； B、树； C、简单图； D、多重图。

10、图 中 从v1到v3长度为3 的通路有（ ）条。

A． 1； B． 2； C． 3； D． 4。

二、 证明（本题40分）

1、（6分）用等值演算法证明q(pr)(pq)r。

2、（10分）用主析取范式判断下列公式的类型，并求出成真赋值。(1)、(pr)rq

(2)、(pq)(qp)

01。

10 3、（8分）在自然推理系统P中，利用归谬法证明下面推理。

前提：pq,pr,qs

结论：sr

4、（8分）在自然推理系统F中，构造用自然语言描述的推理的证明：

每个喜欢步行的人都不喜欢骑自行车。每个人或者喜欢骑自行车或者喜欢乘汽车。有的人不喜欢乘汽车，所以有的人不喜欢步行。（个体域为人类集合）

5、（8分）证明：在6个结点12条边的连通平面简单图中，每个面的面度都是3。

三、综合（本题共40分）

1、（6分）求前束范式：

(x1F(x1,x2)x2G(x1,x2))x3H(x1,x2,x3)

2、（8分）设二元关系R={,<{a},b>,<{Ø},{Ø}>,<Ø,{Ø}>}

（1）、求domR，ranR;

（3）、求R

R,R1R1。

3、（8分）在下面3个图中，哪个是欧拉图？对不是欧拉图的说明理由，对是欧拉图的，用Fleury算法求一条欧拉回路。

（第3题）

4、（5分）画出下图中的无向树的所有非同构的树。

（第4题）

5、（5分）对于下图，求其最小生树及相应的长度

第5题

6、在二叉树中

（1）、求带权为2，3，5，7，8的最优二叉树T。（5分）

（2）、求T对应的二元前缀码。（5分）