离散数学试卷（十七）
一、 判断正误 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?(B?C)?(A?B)?(A?C)。 （ ） （5）(A–B)?C=(A?C)-(B?C)。 （ ）
2、可能有某种关系，既不是自反的，也不是反自反的。（ ）
３、若两图结点数相同，边数相等，度数相同的结点数目相等，则两图是同构的。（ ） ４、一个图是平面图，当且仅当它包含与Ｋ3，3或Ｋ5在２度结点内同构的子图。（ ） ５、代数系统中一个元素的左逆元并一定等于该元素的右逆元。（ ） ６、群是每个元素都有逆元的半群。（ ）
二、 8%
将谓词公式(?x)(P(x)?Q(x,y))?((?y)P(y)?(?z)Q(y,z))化为前束析取范式与前束合取范式。
三、 8%
设集合Ａ＝{a,b,c,d}上的关系Ｒ＝{
四、9%
１、画一个有一条欧拉回路和一条汉密尔顿回路的图。 ２、画一个有一条欧拉回路，但没有一条汉密尔顿回路的图。 ３、画一个有一条欧拉回路，但有一条汉密尔顿回路的图。
110
离散数学试卷（十七）
五、10%
证明：若图Ｇ是不连通的，则Ｇ的补图G是连通的。
六、10%
证明：循环群的任何子群必定也是循环群。
七、12%
用ＣＰ规则证明：
１．A?B?C?D,D?E?F?A?F。 ２．(?x)(P(x)?Q(x))?(?x)P(x)?((?x)Q(x)。八、10%
用推理规则证明下式：
前提: ((?x)(F(x)?S(x))?(?y)(M(y)?W(y)),结论：(?x)(F(x)??S(x))
九、13%
若集合Ｘ＝｛（１，２），（３，４），（５，６），……｝R?{??x1,y1?,?x2,y2??|x1?y2?x2?y1}
1、证明R是X上的等价关系。 2、求出X关于R的商集。
111
(?y)(M(y)??W(y))
离散数学试卷（十七）
一、 填空 20%（每小题2分）
1 题目 2 3 4 （1） （2） （3） （4） （5） 答案 N N N Y Y Y N N
二、8%
(?x)(P(x)?Q(x,y))?((?y)P(y)?(?z)Q(y,z))
? ?(?x)(?P(x)?Q(x,y))?((?y)P(y)?(?z)Q(y,z)) ? (?x)(P(x)??Q(x,y))?((?y)P(y)?(?z)Q(y,z)) 2分 ?(?x)(P(x)??Q(x,y))?((?u)P(u)?(?z)Q(y,z)) 4分 ? (?x)(?u)(?z)((P(x)?Q(x,y))?(P(u)?Q(y,z))) 6分 前束析取范式
?(?x)(?u)(?z)((P(x)?P(u))?(P(x)?Q(y,z))?(?Q(x,y)?P(u))?(?Q(x,y)?Q(y,z)))
前束合取范式 共8分
三、8%
?0100? ? MR =?1010???0001? 1分 ??0000?? 关系图
2分
?4 传递闭包t(R) =URi
==URi 4分
i?1i?1?0100??0100??101? ? M = ?1010???010???10R2?MR?MR?0001???1?0001? =?0?000??0000????0000????000 112
5 6 Y N 0?1??0? 0??离散数学试卷（十七）
MR3?MR2?1?0?MR =??0??0?0?1??MR =?0??001001000100001000??0??11???0??0??0??01??0?0??0?1100?0?1??0??010001000010001000??0??01?=?1??0??0??00??1??00?=?1??0??0??010000100010010001??0? 0??0?0??1? 0??0?MR4?MR3?
MR?MR2?MR3?MR4?1?1 =??0??011001??1? 6分 1??0?
t(R)={
五、10%
因为G=< V，E>不连通，设其连通分支是G(V1),?,G(Vm)由于任两个连通分支G(Vi)和G(Vj)有连线都在G的补图G中。
?u,v?V，则有两种情况：
(m?2)，
(i?j)之间不连通，故两结点子集Vi与Vj之间所
（1）u , v，分别属于两个不同结点子集Vi和Vj，由于G(Vi) , G(Vj)是两连通分支，故(u , v)
在不G中，故边（u , v） 在G中连通。
（2）u ,v ，属于同一个结点子集Vi，可在另一结点子集Vj中任取一点w，故边(u , w)和
边 (w , v )均在G中，故邻接边( u ,w ) ( w , v ) 组成的路连接结点u和v，即u , v在G 113
