离散数学试题b(附标准答案)

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

1、班级：学号：姓名：装订线哈尔滨工程大学试卷考试科目：离散数学B（051121，051131-32）考试时间：2007.07.0314:00-16:00题号一二三四五总分分数评卷人一、填空题（每小题3分，共15分）1.谓词公式"xF(x，y)®Ø$yG(x，y)的前束范式为$x"y(F(x，u)®ØG(v，y))．2.设R是集合A={1，2，3，4，5，6，7，8，9，10}上的模3同余关系，则A关于R的商集为{{1，4，7，10}，{2，5，8}，{3，6，9}}．矚慫润厲钐瘗睞枥庑赖。3.无向树T中有2个4度顶点，3个3

2、度顶点，其余顶点都是树叶，则T中有6片树叶．4.设G是n阶无向简单完全图，则n与边数m的关系为m=Cn2=n(n-1)/2．5.设无向图G为n(n³3)阶极大平面图，R是G的一个面，则deg(R)=3．二、选择题（每小题3分，共15分）1.令F(x)：x是火车，G(y)：y是汽车，H(x，y)：x比y跑得快．在一阶逻辑中将“所有的火车都比某些汽车跑得快”符号化为【A】聞創沟燴鐺險爱氇谴净。A．"x(F(x)®$y(G(y)ÙH(x，y)))．B．"x$y((F(x)ÙG(y))®H(x，y))．C．"x$y(F(x)®(G

3、(y)®H(x，y)))．D．"x(F(x)Ù$y(G(y)ÙH(x，y)))．2.4阶无向完全图的非同构的生成子图有【B】A．1个．B．2个．C．3个．D．4个．3.下列图中是欧拉图的有【C】A．K2，3．B．K4．C．K7．D．K3，3．4.设无向连通图G有6个顶点9条边，T为G的生成树，对应T的基本回路系统中的基本回路个数为【C】残骛楼諍锩瀨濟溆塹籟。A．5．B．6．C．4．D．9．5.下列图中是哈密尔顿图的是【D】A．K1，1．B．K3，4．C．K2．D．K5．三、计算与简答题（每小题8分，共40分）1.求Ø(r®

4、p)Ú(qÙ(pÚr))的主析取范式，并给出成真赋值．Ø(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、011、110和111．第5页共6页第6页共6页班级：学号：姓名：装订线1.设有偏序集áA，Dñ，其中A={1，2，3，6，9，5

5、4}，D为A上的整除关系，(1)画出偏序集áA，Dñ的哈斯图．(2)求A的极大元，极小元，最大元，最小元．(3)求B={3，6，9}的最小上界和最大下界．(4)áA，Dñ是否构成格？说明理由．9541236（１）偏序集áA，Dñ的哈斯图如右图．（２）A的极大元是54，极小元是1；它们分别是A的最大元和最小元是．（3）B的最小上界是54；最大下界3．（4）áA，Dñ构成格，因为A中任意两个元素均有最小上界和最大上界．2.设R={áx，yñ

6、x，yÎZ+Ùx+3y=12}，其中Z+表示全体正整数集合，求R的传递闭包t(R)．酽

7、锕极額閉镇桧猪訣锥。R={áx，yñ

8、x，yÎZ+Ùx+3y=12}={á3，3ñ，á6，2ñ，á9，1ñ}，R2={á3，3ñ}，显然，R2ÍR，即R是传递关系，因此，t(R)=R={á3，3ñ，á6，2ñ，á9，1ñ}．3.设G=，A={a，b，c}，*的运算表为：*abcaabcbbcaccab（1）找出G的单位元；（2）找出G的幂等元；（3）求G中所有可逆元的逆元．（1）G的单位元是a．（2）G的幂等元是a．（3）G中每个元素都可逆，且a-1=a，b-1=c，c-1=b．v1v44.设有向图D如图，v3v

9、2求D中长度为3的通路数，并指出其中的回路数．有向图D如的邻接矩阵为，易得D中长度为3的通路数有13条，其中的回路数有3条．第5页共6页第6页共6页班级：学号：姓名：装订线一、证明题（共20分）1.在一阶逻辑中构造下面推理的证明前提：."x(F(x)®ØG(x)),"x(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(

10、x))前提引入(7)F(a)®ØG(a)(6)UI规则(8)ØF(a)(5)(7)拒取式(9)$xØF(x)(8)EG规则2.设R，S为一非空集合A上的传递关系，证明R∩S也是A上的传递关系．对任意a，b，cÎA，若áa，bñÎR∩S，áb，cñÎR∩S，则áa，bñÎR，áb，cñÎRÞáa，cñÎR