离散数学考试b

《离散数学考试b》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、班级：学号：姓名：装订线哈尔滨工程大学试卷考试科目：离散数学B（041121，041131-32）考试时间：2007.01.1614:00-16:30题号一二三四五总分分数评卷人一、填空题（每小题3分，共15分）1.谓词公式"xF(x)ÚØ$xG(x)的前束范式为．2.设V1=áR,+ñ,V2=áR,×ñ，其中+和×为普通加法和乘法，令j:R®R,j(x)=ex,则j是从V1到V2的．矚慫润厲钐瘗睞枥庑赖。3.设无向连通图G有6个顶点9条边,T为G的生成树，对应T的基本割集系统中的基本割集个数为，基本回路系统中的基本回

2、路个数为．聞創沟燴鐺險爱氇谴净。4.设N为自然数集，D为其上的整除关系，则áN,Dñ的全下界为，其全上界为．5.n阶无向简单图G的D=d=n-1，则G为．二、选择题（每小题3分，共15分）1.命题公式¬(pÙq)↔(¬pÚ¬q)的类型是【】A．重言式．B．非重言式的可满足式．C．矛盾式．D．简单析取式．2.无向树T中有4度，3度，2度顶点各1个，其余顶点都是树叶，则T中树叶片数为【】A．1．B．8．C．7．D．5．3.下列图中是哈密尔顿图的是【】A．K3，4．B．K5．C．K2．D．K1，1．4.下列图中那一个是欧拉图

3、【】A．K4，4．B．K4．C．K3，4．D．K3，3．5.有理数集上定义二元运算*为a*b=a+b-ab，运算*的零元【C】A．b．B．a．C．1．D．0．三、计算与简答题（每小题8分，共40分）1.求Ø(r®p)Ú(qÙ(pÚr))的主析取范式，并给出成真赋值．第5页共6页第6页共6页班级：学号：姓名：装订线1.设A={1,2,3,4,6,8,12,24}，B={1,2,3,4}，D为整除关系．(1)画出偏序集áA,Dñ的哈斯图．(2)求B的极大元、极小元、最大元、最小元、最小上界，最大下界．(3)áA,Dñ是否构

4、成格？说明理由．2.设集合Ａ={a,b,c,d}上的二元关系R={áa，bñ，áb，añ，áb，cñ，ác，dñ}，用关系矩阵求R的传递闭包t(R)．残骛楼諍锩瀨濟溆塹籟。3.设G=，A={a，b，c}，*的运算表为：*abcaabcbbcaccab（1）找出G的单位元；（2）找出G的幂等元；（3）求b的逆元b-1和c的逆元c-1．（4）G是否为群？是否为阿贝尔群？（5）求G的生成元群和所有子群．v4v14.设有向图D如图，v3v2求（1）D中v1到自身长度小于或等于3的回路数；（2）D中v1到v3长度小于或

5、等于3的通路数；（3）D中长度为3的通路数，并指出其中的回路数；（4）利用图的邻接矩阵求其可达矩阵．第5页共6页第6页共6页班级：学号：姓名：装订线一、证明题（共20分）1.在一阶逻辑中构造下面推理的证明前提：."x(F(x)®ØG(x)),"x(G(x)ÚR(x)),$xØR(x)结论：$xØF(x)2.设áG，*ñ是群，áH，*ñ为áG，*ñ的子群，在G上定义关系R："a，bÎG，áa，bñÎRÛ$hÎH，使得a=b*h，证明R是G上的等价关系．酽锕极額閉镇桧猪訣锥。3.设R，S为一非空集合A上的反对称关系，证明R

6、∩S也是A上的反对称关系．二、应用题（10分）57324BCD6AA，B，C，D四个旅游点之间的距离如下图所示，某游客现在位于A处，求他游完其余3个旅游点最后再到达A处的最短线路．彈贸摄尔霁毙攬砖卤庑。第5页共6页第6页共6页