离散数学试卷二次模拟考试.pdfVIP

一、判断正误20%（每小题2分）

1、设A.B.C是任意三个集合。

（1）若A∈B且B⊆C，则A⊆C。（）

（2）若A⊆B且BC，则A⊆C。（）

∈

⊆B且BC，则A∉C。（）

（3）若A∈

（4）A。（）

(B⊕C)=(AB)⊕(AC)

×C=(A×C)-(B×C)。（）

（5）(A–B)

2、可能有某种关系，既不是自反的，也不是反自反的。（）

３、若两图结点数相同，边数相等，度数相同的结点数目相等，则两图是同构的。（）

４、一个图是平面图，当且仅当它包含与Ｋ，或Ｋ在２度结点内同构的子图。（）

335

５、代数系统中一个元素的左逆元并一定等于该元素的右逆元。（）

６、群是每个元素都有逆元的半群。（）

二、8%

将谓词(∀x)(Px()→Qxy(,))→((∃yPy)()∧(∃zQyz)(,))化为前束析取范式与前束

合取范式。

三、8%

设集合Ａ＝{a,b,c,d}上的关系Ｒ＝{a,b,b,a,b,c,c,d}写出它的关系矩阵和关系图，并

用矩阵运算方法求出Ｒ的传递闭包。

四、9%

１、画一个有一条欧拉回路和一条汉密尔顿回路的图。

２、画一个有一条欧拉回路，但没有一条汉密尔顿回路的图。

３、画一个有一条欧拉回路，但有一条汉密尔顿回路的图。

五、10%

证明：若图Ｇ是不连通的，则Ｇ的补图G是连通的。

六、10%

证明：循环群的任何子群必定也是循环群。

七、12%

用ＣＰ规则证明：

１．。

ABCDD∨E→F∧A∨F→,→

２．。

()(()xP(x))Q(x∀)()xP((∨x∀∨∃x)Q(x)

八、10%