离散数学试卷（十七） 110 一、 判断正误 20% （每小题 2分） 1、设A
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 ))(
