离散数学试卷（十七） 一、 判断正误20%（每小题2分） 1、设A.B.C是任意三个集合。 (1)若AEB且BCC,则ACC。() (2)若A三B且B∈C,则A三C。( (3)若AsB且BeC,则AEC。() (4)A∩(B⊕C)=(AnB)⊕(A∩C).( (5)(A-B)xC=(AxC)-(BxC). 2、可能有某种关系，既不是自反的，也不是反自反的。() 3、若两图结点数相同，边数相等，度数相同的结点数目相等，则两图是同构的。() 4、一个图是平面图，当且仅当它包含与K,或K:在2度结点内同构的子图。( 5、代数系统中一个元素的左逆元并一定等于该元素的右逆元。() 6、群是每个元素都有逆元的半群。( 二、8% 将谓词公式((P(x)→Q(x,y》→（③y)Py)A(z)Qy,》化为前束析取范式与前束 合取范式。 三、8% 设集合A={ab,cd}上的关系R={<a,b>,<b,a>,b,心，<cd}写出它的关系矩阵和关系图，并 用矩阵运算方法求出R的传递闭包。 四、9% 1、画一个有一条欧拉回路和一条汉密尔顿回路的图。 2、画一个有一条欧拉回路，但没有一条汉密尔顿回路的图。 3、画一个有一条欧拉回路，但有一条汉密尔顿回路的图。 110
离散数学试卷（十七） 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 (B C) = (A B) (AC) 。 （ ） （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}上的关系Ｒ＝{<a,b>,<b,a>,<b,c>,<c,d>}写出它的关系矩阵和关系图，并 用矩阵运算方法求出Ｒ的传递闭包。 四、9% １、画一个有一条欧拉回路和一条汉密尔顿回路的图。 ２、画一个有一条欧拉回路，但没有一条汉密尔顿回路的图。 ３、画一个有一条欧拉回路，但有一条汉密尔顿回路的图
离散数学试卷（十七） 五、10% 证明：若图G是不连通的，则G的补图G是连通的。 六、10% 证明：循环群的任何子群必定也是循环群。 七、12% 用CP规则证明： 1.AVB→CAD,DVE→F→A→F. 2.(xP(xvQ(x》→(x)P(x)v(3xQx)。 八、10% 用推理规则证明下式： 前提：(3xF(x)AS(x)→(y(My)→Wy,(yMy)A一Wy》 结论：(x(F(x)→一S(x) 九、13% 若集合X=(1,2),(3,4),(5,6),.】 R={<x,y>,<x2,乃2>x+2=2+} 1、证明R是X上的等价关系。 2、求出X关于R的商集
离散数学试卷（十七） 111 五、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)), (y)(M ( y) W ( y)) 结论： (x)(F(x) → S (x)) 九、13% 若集合Ｘ＝｛（１，２），（３，４），（５，６），.｝ { , , , | } 1 1 2 2 1 2 2 1 R = x y x y x + y = x + y 1、证明 R 是 X 上的等价关系。 2、求出 X 关于 R 的商集