离散数学试题A(答案).doc

《离散数学试题A(答案).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、哈尔滨工程大学试卷考试科目：离散数学A（061121，061131）考试时间：　2008.07.099:00-11:00题号一二三四五总分分数评卷人一、填空题（每小题3分，共15分）1.谓词公式"xF(x)∧Ø$xG(x)的前束范式为"x(F(x)∧ØG(x))．2.设V1=áR,+ñ,V2=áR,×ñ，其中+和×为普通加法和乘法，令j:R®R,j(x)=ex,则j是从V1到V2的单同态映射．3.设无向连通图G有6个顶点9条边,T为G的生成树，对应T的基本割集系统中的基本割集个数为5，基本回路系统中的基本回路个数为4．4.设A={1，2，3，4，5}，áP(A)，Åñ构成群，其

2、中Å为集合的对称差，则B={1，4，5}的逆为B．5.n阶无向简单图G的D=d=n-1，则G为Kn．二、选择题（每小题3分，共15分）1.命题公式¬(pÙq)↔(¬pÚ¬q)的类型是【A】A．重言式．　　　　B．非重言式的可满足式．C．矛盾式．　　D．简单析取式．2.无向树T中有4度，3度，2度顶点各1个，其余顶点都是树叶，则T中树叶片数为【B】A．1．　　B．5．C．7．　　D．8．3.下列图中是哈密尔顿图的是【D】A．K1，1．B．K2．C．K3，4．D．K5．4.下列图中那一个是欧拉图【D】A．K3，3．B．K3，4．C．K4．D．K4，4．5.有理数集上定义二元运算*为

3、a*b=a+b-ab，运算*的零元【C】A．0．B．a．C．1．D．b．三、计算与简答题（每小题10分，共50分）1.求Ø(r®p)Ú(qÙ(pÚr))的主析取范式，并给出成真赋值．解　　A=Ø(r®p)Ú(qÙ(pÚr))　　ÛØ(ØrÚp)Ú(qÙp)Ú(qÙr)　　Û(ØpÙr)Ú(pÙq)Ú(qÙr)　　Û((ØpÙr)Ù(ØqÚq))Ú((pÙq)Ù(ØrÚr))Ú((qÙr)Ù(ØpÚp))　　Û(ØpÙØqÙr)Ú(ØpÙqÙr)Ú(pÙqÙØr)Ú(pÙqÙr)　　Ûm1Úm3Úm6Úm7公式的成真赋值为001，010，110，111．12624841231.设

4、A={1,2,3,4,6,8,12,24}，B={1,2,3,4}，D为整除关系．　(1)画出偏序集áA,Dñ的哈斯图．　(2)求B的极大元、极小元、最大元、最小元、最小上界，最大下界．　(3)áA,Dñ是否构成格？说明理由．解　（１）偏序集áA,Dñ的哈斯图如下图．（２）B的极大元是3和4；极小元是1；无最大元；最小元是1；无最小上界；最大下界1．（３）áA,Dñ构成格，因为A中任意两个元素均有最小上界和最大上界．2.设集合Ａ={a，b，c，d}上的二元关系R={áa，bñ，áb，añ，áb，cñ，ác，dñ}，用关系矩阵求R的传递闭包t(R)．，，，，因此，从而R的传递闭包

5、为t(R)={áa，añ，áa，bñ，áa，cñ，áa，dñ，áb，añ，áb，bñ，áb，cñ，áb，dñ，ác，dñ}．3.设G=，A={a，b，c}，*的运算表为：*abcaabcbbcaccab（1）找出G的单位元；　　　　　　　　　　（2）找出G的幂等元；（3）求b的逆元b-1和c的逆元c-1．（4）G是否为阿贝尔群？（5）求G的生成元和所有子群．解　（１）G的单位元为a．（２）G的幂等元为a．（３）b的逆元b-1=c和c的逆元c-1=b．（４）G是阿贝尔群，因为运算表是对称的．（５）由于b0=a，b1=b，b2=c；c0=a，c1=c，c2=b，因此，b和

6、c都是G的生成元．G的生成元群是和，即G==．根据拉格朗日定理，G的子群只能是一阶和三阶群，从而G的子群是只有={a}和G．v4v14.设有向图D如图，v3v2求（1）D中v1到自身长度小于或等于3的回路数；（2）D中v1到v3长度小于或等于3的通路数；（3）D中长度为3的回路数．解　有向图D如的邻接矩阵为，易得（1）D中v1到自身长度小于或等于3的回路数有7条；（2）D中v1到v3长度小于或等于3的通路数有6条；（3）D中长度为3的回路数有10条．一、证明题（共20分）1.在一阶逻辑中构造下面推理的证明前提：."x(F(x)®ØG(x)),"x(

7、G(x)ÚR(x)),$xØR(x)结论：$xØF(x)证明(1)$xØR(x)前提引入(2)ØR(a)(1)EI规则(3)"x(G(x)ÚR(x))前提引入(4)G(a)ÚR(a)(3)UI规则(5)G(a)(2)(4)析取三段论(6)"x(F(x)®ØG(x))前提引入(7)F(a)®ØG(a)(6)UI规则(8)ØF(a)(5)(7)拒取式(9)$xØF(x)(8)EG规则　2.设áG，*ñ是群，áH，*ñ为áG，*ñ的子群，在G上定义关系R："a，bÎG，áa，bñÎRÛ$hÎH，使