06级离散数学期末试题A答案

106级离散数学期末试题A答案一、计算题（本题共20分，每小题5分）1、设A={1,2,3,4}，A上的二元关系R定义如下：R={1,2,2,2,2,4,3,4}，求其自反闭包、对称闭包。解：自反闭包(){1,2,2,2,2,4,3,4,1,1,3,3,4,4}rR对称闭包(){1,2,2,2,2,4,3,4,2,1,4,2,4,3}sR2、设N是自然数集合，定义N上的二元关系R={x,y|x∈N，y∈N，x+y是偶数}，求关系R的等价类。解关系R的等价类有[1]R={1,3,5,……}，[0]R={0,2,4,……}3、设集合15,9,5,3A，A上的整除关系212121,,,aaAaaaaR整除，R是否为A上的偏序关系？若是，则：（1）画出R的哈斯图；（2）求A的极大元和A的极小元。解R是A上的偏序关系。（1）R的哈斯图：（2）A的极大元为9，15；极小元为3，5。4、画出五个6阶非同构的无向树解可能的度数列:(1)1,1,1,1,1,5；(2)1,1,1,1,2,4；(3)1,1,1,1,3,3；(4)1,1,1,2,2,3；(5)1,1,2,2,2,2二、判断题（本题共15分，每小题5分）1、对给定的集合A={1,2,3,4,5},B={6,7,8,9,10}和f={1,8,3,9,4,10,2,6,5,9}，判断是否构成能函数f:A→B,如果能，说明是否为满射、单射、双射的；如果不能，说明理由。解：因为A={1,2,3,4,5},B={6,7,8,9,10},f={1,8,3,9,4,10,2,6,5,9}所以能构成函数f:A→B，既不是单射也不是满射2、判断下图是否为欧拉图，是否有欧拉通路，为什么？解：不是欧拉图.因为有入度和出度不同的结点；有欧拉通路，因为有两个结点入度和出度不同，且一个结点的入度比出度大1，另一个结点的入度比出度小1。3、下图中的关系R为A={1，2，3}上的关系，判断其是否具有自反、对称和传递性并写出该关系的集合表示及关系矩阵。(1)(2)(4a)(4b)(5)(3)2解R={1,1,1,2,2,1,1,3,3,1},001001111RM不自反也不反自反；对称,不反对称；不传递.三、（本题共10分，每小题5分）1、设个体域D={a,b,c},消去公式x(F(x)G(x))中的量词:解x(F(x)G(x))(F(a)G(a))(F(b)G(b))(F(c)G(c))2、求Bp(pqr)的主合取范式解因为p(pqr)(pqr)(pqr)(pqr)M4M5M6M7pqrM1得BM1M4M5M6M7(1,4,5,6,7)四、（本题共10分）给定有向图D:如下图所示：求：(1)图D的邻接矩阵；(2)v1到v4,v4到v1长为3的通路各有多少条；(3)v1到自身长为1,2,3的回路各有多少条；(4)长为3的通路共有多少条?其中有多少条回路；(5)长度小于等于3的回路共有多少条?解（1）0100100001000121A1000010010001321A20100100001003421A3（2）v1到v4长为3的通路有3条,v4到v1长为3的通路有0条；（3）v1到自身长为1,2,3的回路各有1条（4）长3为的通路共有13条，其中有1条回路（5）长度小于等于3的回路共有5条五、（本题10分）设R,＊是一个代数系统，＊是R上的一个二元运算，使得对于R中的任意元素a、b有a＊b=a+b+a·b（·为普通的乘法运算）。证明R,＊是独异点并求出其幺元。证明（1）aR，0＊a=0+a+0·a=a；a＊0=a+0+a·0=a，所以，0是幺元。（2）要证明＊运算满足结合律，即a、b、cR(a＊b)＊c=a＊(b＊c)(a＊b)＊c=（a+b+a·b）＊c=（a+b+a·b）+c+（a+b+a·b）·c=a+b+c+ab+ac+bc+abc同理，a＊(b＊c)=a+b+c+ab+ac+bc+abc所以R,＊是独异点。v1v2v3v43六、证明题（本题共30分，每小题10分）1、在自然推理系统中构造下面推理的证明。如果王小红努力学习，她一定取得好成绩。若王小红贪玩或不按时完成作业，她就不能取得好成绩。所以，如果王小红努力学习，她就不贪玩并且按时完成作业。（其中p：王小红努力学习；q：王小红取得好成绩；r：王小红贪玩；s：王小红按时完成作业。）•前提：pq，(r∨s)q•结论：p(r∧s)•证明•①pq前提引入•②(r∨s)q前提引入•③(r∨s)∨q②置换•④q(r∨s)③置换•⑤p(r∨s)①④假言三段论•⑥p(r∧s)⑤置换2、在自然推理系统F中，构造下面推理的证明前提：x(F(x)G(x)∧H(x)),(x)（F(x)∧R（x））结论：(x)（F(x)∧R（x）∧G(x)）证明：(1)(x)（F(x)∧R（x））P(2)F(c)∧R(c)(1),EI(3)x(F(x)G(x)∧H(x))P(4)F(c)G(c)∧H(c)(3),UI(5)F(c)(2),化简(6)G(c)∧H(c)(4),(5),I假言推理(7)R(c)(2),化简(8)G(c)(6),化简(9)F(c)∧R(c)∧G(c)(5),(7),(8),合取(10)(x)（F(x)∧R（x）∧G(x)）(9)EG3、设V=Z,+，aZ，令fa:ZZ，fa(x)=ax，证明fa是V的自同态，当a为何值时fa为自同构。证明因为x,yZ，有fa(x+y)=a(x+y)=ax+ay=fa(x)+fa(y)当a=1时，fa为自同构；除此之外其他的fa都是单自同态.七、证明题（本题5分）设集合}|5{InGn，×是普通乘法，证明：〈G，×〉是一个群。证明（1）对,,Gba设125,5nnab1212555nnnnabG，所以×在G上封闭。（2）对,,,abcG设1235,5,5nnnabc123123()(55)55(55)()nnnnnnabcabc，所以×可结合。（3）0101010,55555nnnaGaaa，所以05为幺元。（4）1110111,55555nnnnnnaGaa，所以115na。综上〈G，×〉是群。