离散数学试题(2007)_c(答案)

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

1、班级：学号：姓名：装订线哈尔滨工程大学试卷考试科目：离散数学C（051121，051131-32）题号一二三四五总分分数评卷人一、填空题（每小题3分，共15分）1.谓词公式Ø("xF(x，y)Ú$yG(x，y))的前束范式为$x"y(ØF(x，u)ÙØG(v，y))．2.设A={1，2，3，4，5}，áP(A)，Åñ构成群，其中Å为集合的对称差．令B={1，4，5}，则由B生成的循环子群áBñ={Æ，B}．3.模加群G=áZ6,Åñ的所有生成元为1，5．4.n阶无向简单图G的D=d=n-1，则G为

2、Kn．5.设áG，＊ñ为群，aÎG且

3、a

4、=m，则

5、a-1

6、=m．二、选择题（每小题3分，共15分）1.命题公式¬(p→q)ÙqÙr的类型是【D】A．重言式．B．非重言式的可满足式．C．简单合取式．D．矛盾式．2.5阶无向完全图的非同构的自补图有【B】A．1个．B．2个．C．3个．D．4个．3.设áA，*ñ是独异点，e是其单位元，若"aÎA，有a*a=e，则áA，*ñ【B】A．是群但不是Abel群．B．是Abel群．C．不是群．D．不是代数系统．4.树T中有3个3度顶点，2个2度顶点,其余顶点都是

7、树叶，则T中树叶片数为【C】A．1　　　B．4C．5　　　　D．65. 对完全二部图Kr，s，当【A】时，Kr，s为哈密尔顿图．A．r=s．B．r¹s．C．rs．三、计算与简答题（每小题10分，共40分）1.利用等值演算法求公式Ø(r®

8、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.设S45表示45的全体正因

9、子（包括1和45）组成的集合，在S45上定义整除关系£：m£nÛm

10、n．（１）画出偏序集áS45，£ñ的哈斯图．（２）求出áS45，£ñ中最大元、最小元和所有可逆元的逆元．（３）áS45，£ñ是否构成格？简要说明理由．15459135（1）S45={1，3，5，9，15，45}．（2）áS45，£ñ中最大元、最小元分别为1和45；元素1和45互为逆元，5和9互为逆元，元素3和15无逆元．（3）áS45，£ñ构成格，因为S45中任意两个元素均有最小上界和最大下界．2.求模15加群G=áZ15，Åñ的

11、所有生成元与所有子群．G=áZ15，Åñ的所有生成元为与15互质的整数有：1，2，4，7，8，11，13，14，它们就是群的生成元．15的所有正因子为1，3，5，15，因此Z15=á1ñ有4个循环子群,　分别为　　á115/1ñ=á115ñ=á15ñ=á0ñ={0}，á115/3ñ=á15ñ=á5ñ={0，5，10}，á115/5ñ=á13ñ=á3ñ={0，3，6，9，12}，á115/15ñ=á1ñ=G．3.设集合Ａ={a，b，c，d}上的二元关系R={áa，bñ，áb，añ，áb，cñ，ác，

12、bñ}，求R的自反闭包r(R)和对称闭包s(R)．r(R)=IAÈR={áa，añ，áa，bñ，áb，añ，áb，bñ，áb，cñ，ác，bñ，ác，cñ，ád，dñ}．s(R)=RÈR-1=R={áa，bñ，áb，añ，áb，cñ，ác，bñ}．v4v14.设有向图D如图，求D中长度为3的通路数，并指出其中的回路数．v3v2有向图D的邻接矩阵为，由于，因此，D中长度为3的通路数为矩阵A3中所有元素之和，为12+8+5+10=35；其中回路数为4+2+2+2=10．第5页共6页第6页共6页班级：学

13、号：姓名：装订线一、证明题（每小题10分，共20分）1.在一阶逻辑中构造下面推理的证明：前提："x(H(x)ÙD(x)®ØS(x))，"x(H(x)®(S(x)ÚF(x)))，$x(H(x)ÙØF(x))结论：$x(H(x)ÙØD(x))．(1)　$x(H(x)ÙØF(x))前提引入(2)　H(a)ÙØF(a))　　　　　EI规则(3)　H(a)　　　　　　　(2)化简(4)　ØF(a)　　　　　　　(2)化简(5)　"x(H(x)®(S(x)ÚF(x)))　前提引入(6)　H(a