离散数学试卷（十六） 一、判断正误20% (每小题2分) 1、设A,B,C是任意三个集合。 (1)若AEB且BcC,则AeC。( (2)若ASB且B∈C,则A∈C。( ) (3)若AB且BC,则AEC。( (4)AU(B⊕C)=(AUB)©(AUC).( (5)(A⊕B)xC=(AxC)(BxC)。( 2、可能有某种关系，既是对称的，又是反对称的。（) 3、若平面图共有v个结点，e条边和r个面，则v-e+r=2。() 4、任何有向图中各结点入度之和等于边数。() 5、代数系统中一个元素若有左逆元，则该元素一定也有右逆元。( 6、任何一个循环群必定是阿贝尔群。( ) 二、8% 将谓词公式(3x)P(x)v(y)Oy》→(y)R(y)化为前束析取范式与前束合取范式。 三、8% 设集合A={ab,c,d,e}上的关系R={<a,b>,<b,c>,<b.d,<d,e>}写出它的关系矩阵和关系图， 并用矩阵运算方法求出R的传递闭包。 四、10% 设<G,秒是一个群，证明：若对任意的a,b∈G,都有a*6=(a*b)3, a◆b=(a*b),a3*b=(a*b)5,则<G,)是一个阿贝尔群。 五、8% 根据库拉托夫斯基定理，证明下图为非平面图，要求用两种证法。 102
离散数学试卷（十六） 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 (B C) = (A B) (AC) 。 （ ） （5）(A B) C=(A C) (B C) 。 （ ） 2、可能有某种关系，既是对称的，又是反对称的。（ ） ３、若平面图共有 v 个结点，e 条边和 r 个面，则 v-e+r=2。（ ） ４、任何有向图中各结点入度之和等于边数。（ ） ５、代数系统中一个元素若有左逆元，则该元素一定也有右逆元。（ ） ６、任何一个循环群必定是阿贝尔群。（ ） 二、 8% 将谓词公式 ((x)P(x) (y)Q( y)) → (y)R( y) 化为前束析取范式与前束合取范式。 三、 8% 设集合Ａ＝{a,b,c,d,e}上的关系Ｒ＝{<a,b>,<b,c>,<b,d>,<d,e>}写出它的关系矩阵和关系图， 并用矩阵运算方法求出Ｒ的传递闭包。 四、10% 设 <G,*> 是 一 个 群 ， 证 明 ： 若 对 任 意 的 a,b G ，都有 3 3 3 a *b = (a *b) ， 4 4 4 a *b = (a *b) , 5 5 5 a *b = (a *b) , 则<G,*>是一个阿贝尔群。 五、8% 根据库拉托夫斯基定理，证明下图为非平面图，要求用两种证法
离散数学试卷（十六） 法(1)是找出与K.在2度结点内同构的子图。 法(2)是找出与K在2度结点内同构的子图。 六、10% 证明：每个结点的度数至少为2的图必包含一个回路。 七、12% 用CP规则证明： 1、(SAQ)→R,RVP,P→S→Q 2、(x)(P(x)→Q(x)→(1x)P(x)→（自x)Q(x) 八、12% 用推理规则证明下式： 前提：(3x)P(x)→x(P(x)VQ(x)→R(x),(3x)P(x),(自x)Q(x) 结论：(3x)3y)(P(x)AR(y) 九、12% 若集合X={(0,2),(1,2),(2,4),(3,4),(5,6),.} R={K<x1,乃>，<x2,2>x1+y32=x2+} 1、证明R是X上的等价关系。 2、求出X关于R的商集。 103
离散数学试卷（十六） 103 法（1）是找出与 K3，3 在 2 度结点内同构的子图。 法（2）是找出与 K5 在 2 度结点内同构的子图。 六、10% 证明：每个结点的度数至少为 2 的图必包含一个回路。 七、12% 用ＣＰ规则证明： １、 (S Q) → R ,R P , P S → Q ２、 (x)(P(x) → Q(x)) (x)P(x) → (x)Q(x) 八、12% 用推理规则证明下式： 前提: (x)P(x) → x((P(x) Q(x)) → R(x)) ,(x)P(x) ,(x)Q(x) 结论： (x)(y)(P(x) R( y)) 九、12% 若 集 合 Ｘ ＝ ｛（ 0 ， 2 ），（ １， ２ ），（ 2 ， 4 ），（ ３ ， ４ ），（ ５ ，６ ）， . . ｝ { , , , | } 1 1 2 2 1 2 2 1 R = x y x y x + y = x + y 1、 证明 R 是 X 上的等价关系。 2、 求出 X 关于 R 的商集