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

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

1、班级：学号：姓名：装订线哈尔滨工程大学试卷考试科目：离散数学（051121，051131-32）考试时间：　2007.07.0314:00-16:00题号一二三四五总分分数评卷人一、填空题（每小题3分，共15分）1.谓词公式"xF(x)®Ø$yG(x，y)的前束范式为$x"y(F(x)®ØG(z，y))．2.设有群áZ12，Åñ和áZ3，Åñ，令j：Z12®Z3，j(x)=(x)mod3，则j是áZ12，Åñ到áZ3，Åñ的满同态映射．3.5个顶点，7条边的连通平面图中共有4个面．4.有理数集上定义二元运算*为a*b=a+b-ab，则运算*的单位元为0，零元为1．5.设无向连通图G有6个

2、顶点9条边，T为G的生成树，对应T的基本割集系统中的基本割集个数为5，基本回路系统中的基本回路个数为4．二、选择题（每小题3分，共15分）1.命题公式¬(pÙq)↔(p®¬q)的类型是【A】A．重言式．　　　　B．非重言式的可满足式．C．矛盾式．　　D．简单析取式．2.无向树T中有4度，3度，2度顶点各1个，其余顶点都是树叶，则T中树叶片数为【D】A．1．　　B．8．C．7．　　D．5．3.素数阶群一定是　【B】A．无限群．　B．循环群，也是Abel群．C．非交换群．　　D．循环群．4.下列图中那一个是欧拉图【A】A．K4，4．B．K4．C．K3，4．D．K3，3．5.下列图中是哈密尔顿

3、图的是【B】A．K3，4．B．K5．C．K2．D．K1，1．三、计算与简答题（每小题8分，共40分）1.利用等值演算方法求命题公式((pÚq)Ù(p®q))«(q®p)的主析取范式；利用该主析取范式求公式的主合取范式，并指出该公式的成真赋值和成假赋值．((pÚq)Ù(p®q))«(q®p)Û((pÚq)Ù(ØpÚq))«(ØqÚp)Ûq«(ØqÚp)Û(q®(ØqÚp))Ù((ØqÚp)®q)ÛØqÚ(ØqÚp)ÙØ(ØqÚp)ÚqÛ(ØqÚp)Ù((qÙØp)Úq)Û(ØqÚp)ÙqÛ(ØqÙq)Ú(pÙq)ÛpÙqÛm3原公式的主析取范式为m3；主合取范式为M0ÙM1ÙM2；原公式的

4、成真赋值为11；　　　　成假赋值为00，01，10．第5页共8页第6页共8页班级：学号：姓名：装订线1.求群áZ20，Åñ的所有生成元和子群，画出áZ20，Åñ的子群格，指出该子群格的全下界、全上界和有补元，并求其补元．á2ñá1ñá5ñá0ñá10ñá4ñ群áZ20，Åñ的所有生成元为与20互质的正整数：1，3，7，9，11，13，17，19．20的所有正因子为1，2，4，5，10，20，所以，Z20=á1ñ有6个循环子群，分别为á120/1ñ=á120ñ=á0ñ={0}，á120/2ñ=á110ñ=á10ñ={0，10}，á120/4ñ=á15ñ=á5ñ={0，5，10，15}，á1

5、20/5ñ=á14ñ=á4ñ={0，4，8，12，16}á120/10ñ=á12ñ=á2ñ={0，2，4，6，8，　　10，12，14，16，18}，á120/20ñ=á11ñ=á1ñ=Z20．该子群格的全下界为á0ñ，全上界为á1ñ．元素á0ñ和á1ñ互为补元；á4ñ和á5ñ互为补元，其它元素均无补元．2.设集合Ａ={a，b，c，d}上的二元关系R={áa，bñ，áb，añ，áb，cñ，ác，dñ}，求R的传递闭包t(R)．R2={áa，añ，áa，cñ，áb，bñ，áb，dñ}，R3={áa，bñ，áa，dñ，áb，añ，áb，cñ}，R4={áa，añ，áa，cñ，áb，bñ，áb

6、，dñ}=R2，R5=R3，从而，t(R)=R∪R2∪R3∪R4={áa，añ，áa，bñ，áa，cñ，áa，dñ，áb，añ，áb，bñ，áb，cñ，áb，dñ，ác，dñ}．另：R的关系矩阵为3.(1)给出具有4个顶点的所有自补图．(2)给出具有5个顶点的所有自补图．　　（1）cbdacbda（2）4.设áL，£ñ是一个格，对任意a，b，cÎL，化简公式((aÙb)Ú(aÙc))Ù((aÙb)Ú(bÙc))．aÙb£a，aÙc£a，(aÙb)Ú(aÙc)£a，aÙb£b，bÙc£b，(aÙb)Ú(bÙc)£b，((aÙb)Ú(aÙc))Ù((aÙb)Ú(bÙc))£aÙb；(aÙb)

7、Ú(aÙc)³aÙb，(aÙb)Ú(bÙc)³aÙb，((aÙb)Ú(aÙc))Ù((aÙb)Ú(bÙc))³aÙb；第5页共8页第6页共8页班级：学号：姓名：装订线((aÙb)Ú(aÙc))Ù((aÙb)Ú(bÙc))=aÙb．一、证明题（每小题10分，共20分）1.在一阶逻辑中构造下面推理的证明前提："x(F(x)®G(x))，Ø"x(F(x)®H(x))结论：$x(F(x)ÙG(x)ÙØH(x))(1)Ø"x(F(x)®H(x