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

《离散数学试卷及答案(17)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、离散数学试卷（十七）一、判断正误20%（每小题2分）1、设A.B.C是任意三个集合。（1）若AB且BC，则AC。（）（2）若AB且BC，则AC。（）（3）若AB且BC，则AC。（）（4）A。（）（5）(A–B)C=(AC)-(BC)。（）2、可能有某种关系，既不是自反的，也不是反自反的。（　　）３、若两图结点数相同，边数相等，度数相同的结点数目相等，则两图是同构的。（）４、一个图是平面图，当且仅当它包含与Ｋ3，3或Ｋ5在２度结点内同构的子图。（）５、代数系统中一个元素的左逆元并一定等于该元素的右逆元。（）６、群是每个元素都有逆元的半群。（）二、8%将谓词公式化为前束析取

2、范式与前束合取范式。三、8%设集合Ａ＝{a,b,c,d}上的关系Ｒ＝{,,,}写出它的关系矩阵和关系图，并用矩阵运算方法求出Ｒ的传递闭包。四、9%１、画一个有一条欧拉回路和一条汉密尔顿回路的图。２、画一个有一条欧拉回路，但没有一条汉密尔顿回路的图。３、画一个有一条欧拉回路，但有一条汉密尔顿回路的图。116离散数学试卷（十七）五、10%证明：若图Ｇ是不连通的，则Ｇ的补图是连通的。六、10%证明：循环群的任何子群必定也是循环群。七、12%用ＣＰ规则证明：　　１．。　　２．。八、10%用推理规则证明下式：前提:结论：S九、13%若集合Ｘ

3、＝｛（１，２），（３，４），（５，６），……｝1、证明R是X上的等价关系。2、求出X关于R的商集。一、填空20%（每小题2分）题目123456116离散数学试卷（十七）（1）（2）（3）（4）（5）答案NNNYYYNNYN二、8%2分4分6分前束析取范式前束合取范式共8分三、8%=1分关系图2分传递闭包t(R)=Ri==4分====116离散数学试卷（十七）===6分t(R)={,,,,,,,,}共8分四、9%五、10%因为G=不连通，设其连通分支是，由于任两个连通分支和

4、之间不连通，故两结点子集之间所有连线都在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%116离散数学试卷（十七）设是循环群,G=(a)，设是的子群。且，则存在最小正整数m，使得：，对任意，必有，故：即：所以，任m使的最小正整数，且，所以

5、r=0即：这说明S中任意元素是的乘幂。所以是以为生成元的循环群。七、用CP规则证明12%1、(6分)①P（附加前提）②T①I③P④T②③I⑤T④I⑥T⑤I⑦P⑧T⑥⑦I⑨CP2、因为本题亦即：①P（附加前提）②T①E③ES②④P⑤US④⑥T③⑤I⑦EG⑥116离散数学试卷（十七）⑧CP八、10%⑴P⑵ES⑴⑶T⑵E⑷EG⑶⑸T⑷E⑹P⑺T⑸⑹I⑻T⑺E⑼US⑻⑽T⑼E⑾T⑽E⑿UG⑾九、13%（1）自反性：(2)对称性：（3）传递性：由等价关系的定义知R是X上的等价关系。2、X/R={[<1,2>]R}116离散数学试卷（十七）116