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

离散数学试卷（十六）102一、判断正误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、可能有某种关系，既是对称的，又是反对称的。（）３、若平面图共有v个结点，e条边和r个面，则v-e+r=2。（）４、任何有向图中各结点入度之和等于边数。（）５、代数系统中一个元素若有左逆元，则该元素一定也有右逆元。（）６、任何一个循环群必定是阿贝尔群。（）二、8%将谓词公式)()())()()()((yRyyQyxPx化为前束析取范式与前束合取范式。三、8%设集合Ａ＝{a,b,c,d,e}上的关系Ｒ＝{a,b,b,c,b,d,d,e}写出它的关系矩阵和关系图，并用矩阵运算方法求出Ｒ的传递闭包。四、10%设G,*是一个群，证明：若对任意的Gba,，都有333)*(*baba，444)*(*baba,555)*(*baba,则G,*是一个阿贝尔群。五、8%根据库拉托夫斯基定理，证明下图为非平面图，要求用两种证法。离散数学试卷（十六）103法（1）是找出与K3，3在2度结点内同构的子图。法（2）是找出与K5在2度结点内同构的子图。六、10%证明：每个结点的度数至少为2的图必包含一个回路。七、12%用ＣＰ规则证明：１、QSPPRRQS,,)(２、)()()()())()()((xQxxPxxQxPx八、12%用推理规则证明下式：前提:)()(,)()(,))())()((()()(xQxxPxxRxQxPxxPx结论：))()()()((yRxPyx九、12%若集合Ｘ＝｛（0，2），（１，２），（2，4），（３，４），（５，６），……｝}|,,,{12212211yxyxyxyxR1、证明R是X上的等价关系。2、求出X关于R的商集。一、填空20%（每小题2分）题目123456（1）（2）（3）（4）（5）离散数学试卷（十六）104答案YNNNYYNYNY二、8%前束合取范式前束析取范式))()(())()()(()()(())())()()(()()(()()())(()()(()()())(()()(()()())()(()()(()()())(()((()()())(()()(((zRyQzRxPzyxzRyQxPzyxzRzyQyxPxyRyyQyxPxyRyyQyxPxyRyyyQxxPyRyyyQxPx三、8%关系矩阵：0000010000000000110000010RM关系图：传递闭包：511)(iiiiRRRt0000000000000001000001100000001000000000011000001000000100000000001100000102RRRMMM离散数学试卷（十六）10500000000000000000000100000000010000000000110000010000000000000000100000110023RRRMMM534000000000000000000000000000000100000000001100000100000000000000000000010000RRRRMMMM000001000000000111001111054321RRRRRMMMMMt(R)={a,b,a,c,a,d,a,e,b,c,b,d,b,e,d,e}。四、10%证明：对G,*中任意元素a和babbababbababbabbabbabaabbaababbabaabbaababbaabbababaabbabababababbaabbaababa***)*()*(*)*(****)*(***)*()*(*)*(***)*()*(*)*()*(*)*(*)*(*)*(*:)*(**)*(**)*(*,)*(*333443333332244444334445553334442221311331333故由于即同样可得即因此可得由可得由同理，即所以G,*是阿贝尔群五、8%法一：离散数学试卷（十六）106法二：六、10%证明:设L是图G中最长路的一条，设其长度为m，这条路的一个端点设为a，考察G中与a关联的那些边，这些边中任何一条边的另一端必在L上，否则，将这个结点加进L中就得一条更长的路。若G中每个结点度数至少为2，则a也要关联于一条不在L上的边e，若e是环，则e本身就是回路，否则，边e的另一端点b（与a不同的点）在L上，而连通L中a到b的子路与边e组成一个回路。七、12%（每小题6分）1、abe离散数学试卷（十六）107①PP②PRP③RT①②I④RQS)(P⑤)(RSRT④E⑥)(QST③⑤I⑦QST⑥E⑧SP(附加前提)⑨QT⑦⑧I⑩QSCP2、①)()(xPxP（附加前提）②)(ePES①③))()()((xQxPxP④)()(eQePUS③⑤)(eQT②④I⑥)()(xQxEG⑤⑦)()()()(xQxxPxCP八、12%⑴))())()()((()()(xRxQxPxxPxP离散数学试卷（十六）108⑵)()(xPxP⑶))())()()(((xRxQxPxT⑴⑵I⑷)(ePES⑵⑸)()(xQxP⑹)(dQES⑸⑺)())()((dRdQdPUS⑶⑻)()(dPdQT⑹I⑼)(dRT⑺⑻I⑽)()(dRePT⑷⑼I⑾))()()((yRePyEG⑽⑿))()()()((yRxPyxEG⑾九、12%（1）自反性：RyxyxyxyxXyx),(),,(,,),(故由于(2)对称性：时当RyxyxXyxyx),(),,(,),(),,(22112211Ryxyxyxyxyxyx),(),,(112221121221有亦即（3）传递性：,),(),,(),,(332211Xyxyxyx时当RyxyxRyxyx),(),,(,),(),,(33222211Ryxyxyxyxyxyxyxyx),(),,(3311133123321221故相加化简得即离散数学试卷（十六）109由等价关系的定义知R是X上的等价关系。2、X/R={[0,2]R,[1,2]R}