离散数学试卷（十七） 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}上的关系Ｒ＝{
,,,}写出它的关系矩阵和关系图，并用矩阵运算方法求出Ｒ的传递闭包。 四、9% １、画一个有一条欧拉回路和一条汉密尔顿回路的图。 ２、画一个有一条欧拉回路，但没有一条汉密尔顿回路的图。 ３、画一个有一条欧拉回路，但有一条汉密尔顿回路的图。 离散数学试卷（十七） 111 五、10% 证明：若图Ｇ是不连通的，则Ｇ的补图G 是连通的。 六、10% 证明：循环群的任何子群必定也是循环群。 七、12% 用ＣＰ规则证明： １．FAFEDDCBA,。 ２．(()()())()()((xPxxQxPx)()xQx。 八、10% 用推理规则证明下式： 前提: ))()()(()),()()(())()()(((yWyMyyWyMyxSxFx 结论：)()((xFxS ))(x 九、13% 若集合Ｘ＝｛（１，２），（３，４），（５，６），……｝ }|,,,{12212211yxyxyxyxR 1、证明R 是X 上的等价关系。 2、求出 X 关于 R 的商集。 一、 填空 20%（每小题 2分） 题目 1 2 3 4 5 6 离散数学试卷（十七） 112 （1） （2） （3） （4） （5） 答案 N N N Y Y Y N N Y N 二、8% )),()()()(()),()()((zyQzyPyyxQxPx )),()()()(()),()()((zyQzyPyyxQxPx )),()()()(()),()()((zyQzyPyyxQxPx 2分 )),()()()(()),()()((zyQzuPuyxQxPx 4分 ))),()(()),()()(()()((zyQuPyxQxPzux ...
