离散数学试题(2008)_C(答案)

1、班级： 学号： 姓名： 装 订 线哈尔滨工程大学试卷考试科目：离散数学（061121，061131）题号一二三四五总分分数评卷人一、 填空题（每小题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.

2、 已知n阶无向简单图g有m条边，则g的补图有n(n-1)/2-m条边4. 有理数集上定义二元运算*为a*b=a+b-ab，则运算*的单位元为 0 ，零元为 1 5. 设无向连通图g有6个顶点10条边，t为g的生成树，对应t的基本割集系统中的基本割集个数为 5 ，基本回路系统中的基本回路个数为 6 二、 选择题（每小题3分，共15分）1. 命题公式¬(pÙq)(p®¬q)的类型是 【a】a重言式 b非重言式的可满足式c矛盾式 d简单析取式2. 无向树t中有4度，3度，2度顶点各1个，其余顶点都是树叶，则t中树叶片数为 【d】a1 b8c7 d53. 素数阶

3、群一定是 【b】a无限群 b循环群，也是abel群c非交换群 d循环群4. 下列图中那一个是欧拉图 【a】ak4，4 bk4ck3，4 dk3，35. 下列图中是哈密尔顿图的是 【b】ak3，4 bk5ck2 dk1，1三、 计算与简答题（每小题10分，共50分）1. 利用等值演算方法求命题公式(pÚq)Ù(p®q)«(q®p)的主析取范式；并指出该公式的成真赋值和成假赋值(pÚq)Ù(p®q)«(q®p)Û(pÚq)Ù(ØpÚq)«(

4、Ø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

5、ÙqÛm3原公式的主析取范式为m3；原公式的成真赋值为11；成假赋值为00，01，102. 求群áz20，Åñ的所有生成元和子群á2ñá1ñá5ñá0ñá10ñá4ñ群áz20，Åñ的所有生成元为与20互质的正整数：1，3，7，9，11，13，17，1920的所有正因子为1，2，4，5，10，20，所以，z20=á1ñ有6个循环子群，分别为á120/1ñ=&

6、#225;120ñ=á0ñ=0，á120/2ñ=á110ñ=á10ñ=0，10，á120/4ñ=á15ñ=á5ñ=0，5，10，15，á120/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

7、ñ=á1ñ=z203. 设集合=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ñ，

8、5;b，bñ，áb，dñ=r2，r5=r3，从而，t(r)=rr2r3r4=áa，añ，áa，bñ，áa，cñ，áa，dñ，áb，añ，áb，bñ，áb，cñ，áb，dñ，ác，dñ4. (1) 给出具有4个顶点的所有自补图(2) 给出具有5个顶点的所有自补图（1）cbdacbda（2） 5. 若r1，r2均是非空集合a上的等价关系，那么r1，r2的交r1r2、并r1r2和复合r1 r2

9、也是a上的等价关系吗？简要说明理由r1r2是a上的等价关系事实上，(1)因r1，r2是a上的自反关系，有iaÍr1，iaÍr2，因此，iaÍr1r2，即r1r2是a上的自反关系(2)因r1，r2是a上的对称关系，有r1r1-1，r2r2-1，而(r1r2)-1=r1-1r2-1=r1r2，因此，r1r2是a上的对称关系(3)因r1，r2是a上的传递关系，有r12Ír1，r22Ír2，而(r1r2)2=(r1r2)o(r1r2)=r12r22r1or2r2or1Ír12r22Ír1r2，因此，r1r2是a上的传递关系r1r2并

10、不一定满足传递性，例如：设a=a，b，cr1=áa，bñ，r2=áb，cñ，则r1r2=áa，bñ，áb，cñ不是a上的传递关系四、 证明题（每小题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) 前提引入(2) $xØ(f(x)®h(x)

11、(1)置换(3) Ø(f(c)®h(c) (2)ei规则(4) f(c)ÙØh(c) (3)置换(5) f(c) (4)化简(6) "x(f(x)® g(x) 前提引入(7) f(c)® g(c) (7)ui规则(8) g(c) (5)(8)假言推理(9) f(c)Ùg(c)ÙØh(c) (4)(8)合取(10) $x(f(x) Ùg(x) ÙØh(x) (9)eg规则2. 设h£g，"a，bÎg，定义áa，bñ&#

12、206;rÛab-1Îh，证明r是g上的等价关系，求出等价关系r的等价类自反性："aÎg, aa-1=eÎhÞáa, añÎr对称性："a，bÎg，áa，bñÎrÞab-1ÎhÞ(ab-1)-1Îh=ba-1ÎhÞáb，añÎr传递性："a，b，cÎg，áa，bÎñr，áb，cÎñrÞab-1Îh， bc-1Îh=ab-1bc-1ÎhÞac-1Îh