离散数学试卷及答案(17)

离散数学试卷（十七）110一、判断正误20%（每小题2分）1、设A.B.C是任意三个集合。（1）若AB且BC，则AC。（）（2）若AB且BC，则AC。（）（3）若AB且BC，则AC。（）（4）A)()()(CABACB。（）（5）(A–B)C=(AC)-(BC)。（）2、可能有某种关系，既不是自反的，也不是反自反的。（）３、若两图结点数相同，边数相等，度数相同的结点数目相等，则两图是同构的。（）４、一个图是平面图，当且仅当它包含与Ｋ3，3或Ｋ5在２度结点内同构的子图。（）５、代数系统中一个元素的左逆元并一定等于该元素的右逆元。（）６、群是每个元素都有逆元的半群。（）二、8%将谓词公式)),()()()(()),()()((zyQzyPyyxQxPx化为前束析取范式与前束合取范式。三、8%设集合Ａ＝{a,b,c,d}上的关系Ｒ＝{a,b,b,a,b,c,c,d}写出它的关系矩阵和关系图，并用矩阵运算方法求出Ｒ的传递闭包。四、9%１、画一个有一条欧拉回路和一条汉密尔顿回路的图。２、画一个有一条欧拉回路，但没有一条汉密尔顿回路的图。３、画一个有一条欧拉回路，但有一条汉密尔顿回路的图。离散数学试卷（十七）111五、10%证明：若图Ｇ是不连通的，则Ｇ的补图G是连通的。六、10%证明：循环群的任何子群必定也是循环群。七、12%用ＣＰ规则证明：１．FAFEDDCBA,。２．(()()())()()((xPxxQxPx)()xQx。八、10%用推理规则证明下式：前提:))()()(()),()()(())()()(((yWyMyyWyMyxSxFx结论：)()((xFxS))(x九、13%若集合Ｘ＝｛（１，２），（３，４），（５，６），……｝}|,,,{12212211yxyxyxyxR1、证明R是X上的等价关系。2、求出X关于R的商集。一、填空20%（每小题2分）题目123456离散数学试卷（十七）112（1）（2）（3）（4）（5）答案NNNYYYNNYN二、8%)),()()()(()),()()((zyQzyPyyxQxPx)),()()()(()),()()((zyQzyPyyxQxPx)),()()()(()),()()((zyQzyPyyxQxPx2分)),()()()(()),()()((zyQzuPuyxQxPx4分))),()(()),()()(()()((zyQuPyxQxPzux6分前束析取范式))),(),(())(),(()),()(())()()(()()((zyQyxQuPyxQzyQxPuPxPzux前束合取范式共8分三、8%RM=00001000010100101分关系图2分传递闭包t(R)=1iURi==iiRU414分RRRMMM2=00001000010100100000100001010010=0000000010100101RRRMMM23=00000000101001010000100001010010=0000000001011010离散数学试卷（十七）113RRRMMM34=00000000010110100000100001010010=0000000010100101432RRRRMMMM=00001000111111116分t(R)={a,a,a,b,a,c,a,d,b,a,b,b,b,c,b,d,c,d}共8分四、9%五、10%因为G=V，E不连通，设其连通分支是)2()(,),(1mVGVGm，由于任两个连通分支)(iVG和)()(jiVGj之间不连通，故两结点子集jiVV与之间所有连线都在G的补图G中。Vvu,，则有两种情况：（1）u,v，分别属于两个不同结点子集Vi和Vj，由于G(Vi),G(Vj)是两连通分支，故(u,v)在不G中，故边（u,v）在G中连通。（2）u,v，属于同一个结点子集Vi，可在另一结点子集Vj中任取一点w，故边(u,w)和边(w,v)均在G中，故邻接边(u,w)(w,v)组成的路连接结点u和v，即u,v在G中也是连通。六、10%离散数学试卷（十七）114设G,*是循环群,G=(a)，设S,*是G,*的子群。且GSeS},{，则存在最小正整数m，使得：Sam，对任意Sal，必有0,0,tmrrtml，故：Saaaaaatmltmltmlr)(**即：Saaatmrl)(*所以Sar，任m使Sam的最小正整数，且mr0，所以r=0即：tmlaa)(这说明S中任意元素是ma的乘幂。所以G,*是以ma为生成元的循环群。七、用CP规则证明12%1、(6分)①AP（附加前提）②BAT①I③DCBAP④DCT②③I⑤DT④I⑥EDT⑤I⑦FEDP⑧FT⑥⑦I⑨FACP2、因为)()()()()(xxQxPxxxQxxP本题亦即：)()()())()((xxQxPxxQxPx①)()(xPxP（附加前提）②)()(xPxT①E③)(ePES②④))()((xQxPxP⑤)()(eQePUS④⑥)(eQT③⑤I⑦)()(xQxEG⑥离散数学试卷（十七）115⑧)()()(xxQxPxCP八、10%⑴))()((yWyMyP⑵)()(eWeMES⑴⑶))()((eWeMT⑵E⑷))()((yWyMyEG⑶⑸))()()((yWyMyT⑷E⑹))()()(())()()((yWyMyxSxFxP⑺))()((xSxFxT⑸⑹I⑻))()(()(xSxFxT⑺E⑼))()((aSaFUS⑻⑽)()(aSaFT⑼E⑾)()(aSaFT⑽E⑿))()()((xSxFxUG⑾九、13%（1）自反性：RyxyxyxyxXyx),(),,(,,),(故由于(2)对称性：时当RyxyxXyxyx),(),,(,),(),,(22112211Ryxyxyxyxyxyx),(),,(112221121221有亦即（3）传递性：,),(),,(),,(332211Xyxyxyx时当RyxyxRyxyx),(),,(,),(),,(33222211Ryxyxyxyxyxyxyxyx),(),,(3311133123321221故相加化简得即由等价关系的定义知R是X上的等价关系。2、X/R={[1,2]R}离散数学试卷（十七）116