离散数学试卷（十七）一、 判断正误 20% （每小题 2分）1、设A.B. C是任意三个集合。 （1）若AB且BC，则AC。 （ ） （2）若AB且BC，则AC。 （ ）（3）若AB且BC，则AC。 （ ）（4）A。 （ ）（5）(AB)C=(AC)-(BC)。 （ ）2、可能有某种关系，既不是自反的，也不是反自反的。（ ）、若两图结点数相同，边数相等，度数相同的结点数目相等，则两图是同构的。（ ）、一个图是平面图，当且仅当它包含与3，3或5在度结点内同构的子图。（ ）、代数系统中一个元素的左逆元并一定等于该元素的右逆元。（ ）、群是每个元素都有逆元的半群。（ ）二、 8% 将谓词公式化为前束析取范式与前束合取范式。三、 8%设集合a,b,c,d上的关系,写出它的关系矩阵和关系图，并用矩阵运算方法求出的传递闭包。四、9%、画一个有一条欧拉回路和一条汉密尔顿回路的图。、画一个有一条欧拉回路，但没有一条汉密尔顿回路的图。、画一个有一条欧拉回路，但有一条汉密尔顿回路的图。五、10% 证明：若图是不连通的，则的补图是连通的。六、10%证明：循环群的任何子群必定也是循环群。七、12%用规则证明：。八、10% 用推理规则证明下式：前提: 结论：S九、13%若集合（，），（，），（，），1、证明R是X上的等价关系。2、求出X关于R的商集。一、 填空 20%（每小题2分）题目123456（1）（2）（3）（4）（5）答案NNNYYYNNYN二、8% 2分 4分 6分 前束析取范式 前束合取范式 共8分三、8% = 1分 关系图2分 传递闭包t(R) =Ri= 4分 = = = = = 6分t(R)=, 共8分四、9%五、10%因为G=不连通，设其连通分支是，由于任两个连通分支和之间不连通，故两结点子集之间所有连线都在G的补图中。，则有两种情况：（1）u , v，分别属于两个不同结点子集Vi和Vj，由于G(Vi) , G(Vj)是两连通分支，故(u , v)在不G中，故边（u , v） 在中连通。（2）u ,v ，属于同一个结点子集Vi，可在另一结点子集Vj中任取一点w，故边(u , w)和边 (w , v )均在中，故邻接边( u ,w ) ( w , v ) 组成的路连接结点u和v，即u , v在中也是连通。六、10%设是循环群,G=(a)，设是的子群。且，则存在最小正整数m，使得：，对任意，必有，故： 即：所以，任m使的最小正整数，且，所以r=0即：这说明S中任意元素是的乘幂。 所以是以为生成元的循环群。七、用CP规则证明12%1、(6分)P（附加前提）TIPTITITIPTICP2、因为本题亦即：P（附加前提）TEESPUSTIEGCP八、10%PESTEEGTE PTITEUSTETEUG九、13%（1）自反性：(2) 对称性：（3）传递性：由等价关系的定义知R是X上的等价关系。2、X/R=R116