大学试卷《离散数学》及答案.docx

一、填空题(本大题共48分，共16小题，每小题3分)

1. --公式为 之充分必要条件是其合取范式之每一合取项中均必同时包 含一命题变元及其否定

2. 无向图G具有是生成树，当且仅当 的，若G为(n,m)连通图，要确 定G的一棵生成树必删掉G的 条边。

3. 一个无向图的欧拉回路要求经过图中 一次且仅一次，汉密顿图要 求经过图中 一次且仅一次。

4. 设P：我生病，Q：我去学校(1)命题“我虽然生病但我仍去学校”符号化 为 o (2)命题“只有生病的时候，我才不去学校”符号化为 o (3)命题\"如果我生病，那么我不去学校”符号化为 o

5. 设有33盏灯，拟公用一个电源，则至少需要5个插头的接线板数

6. 若HlAH2A-AHn是 ,则称Hl, H2, -Hn是相容的，若 HlAH2A-AHn是 ,则称H1.H2, -Hn是不相容的

7. 设 f,g,h 是 N 到 N上的函数(N 为自然数集合),f(n)=n+l;g(n)=2n;h(n)=0；贝lj(fdg)oh=

8. K5的点连通度为 ,边连通度为 o

9. A={1, 2, 3, 4, 5, 6, 8, 10, 24, 36}, R 是 A 上的整除关系。子

B={1, 2, 3, 4},那么B的上界是 ； B的下界是 ； ：6的上确界 是; B的下确界

为

10. 命题公式P-*QAR的对偶式为

11. 设入={1, {2}, },则A的幕集有元素 个。

12. 设 A={0, 1,2, 3}, B={4,6, 7}, C={8, 9, 12, 14}, R1 是由 A 到 B 的关系,R2 是由B到C原关系，分别定义为

Rl={<2, 6>, <3, 4>, <0, 7>} ;R2={<4, 8>, <4, 12>, <6, 12>,〈7, 14〉},

则复合关系

RloR2 为：

13. 设 A= {, (}},贝i]P(A) nP(B)= 。

14. 给定个体域为整数域，若F(x):表示x是偶数，G(x):表示x是奇数；那么

(3X)F(X)A(3X)G(X)：^一个 语句；而Qx) (F(X)AG(X))是一个

______ 语句O

15. 设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度结点， 该图有 个顶点。

16. 设T是一棵完全二元树，有15个结点，其中8个树叶结点，则T分枝结点 数是 , T的所有结点度数之和是 o

二、作图题(本大题共8分，共1小题，每小题8分) 求下图所示带权图的最小生成树：

三、简答题（本大题共4分，共1小题，每小题4分） 判断下图是否欧拉图，若是，找出一个欧拉回路。

四、分析题（本大题共10分，共2小题，每小题5分）

1.设I是整数集，〈，＞,=,-'-f。是I上的二元关系，分别表示小 于、大于、等于、小于等于、大于等于，不等于。那么这些关系会满足什么性 质？试填写下表： 3 V 自反。 反自反。 对称3 反对称- 传递。 3 2 3 2 2 2 3 3 3 3 =3 a 3 2 2 ° 2 3 3 2.设集合A={1,2,3,4,5}上的二元关系R如下图，请判断R是否是A上的等价关系, 若是，

请说明理由并写出各元素的等价类，若不是，请说明理由。

五、证明题(本大题共30分，共5小题，每小题6分) 1. 设G为群，证明e为G中的唯一幕等元。

2. 在命题逻辑中构造下面推理的证明。前提：p-s, q-r, ］〕r, pVq结 论：s

3. 案件涉及甲、乙、丙、丁四个，根据已有的线索，已知：i.若甲、乙均未 作案，则丙、丁也未作案ii.若丙、丁未作案，则甲、乙也未作案iii.若甲 与乙同时作案，则丙与丁有一人且只有一人作案iv.若乙与丙同时作案，则甲 与丁同时作案或同时未作

案。办案人员由此的出结论：甲是作案者。这个结论 是否正确，为什么

4. 设fl, f2都是从代数系统〈&★＞到代数系统〈B,*〉的同态。设g是从A到B 的一个映射，使得对任意aGA,都有g(a)= fl (a)* f2 (a)。证明：如果是 一个可交换半群，那麽g是一个由代数系统〈A, ★〉到代数系统〈B, *〉的同态。

5. 设R是集合A上的自反、传递的二元关系，又设T也是A上的二元关系，且 满足：＜x, y＞《TU＞〈x, y〉GR ' ■ ＜y, x＞GR,求证：T是A上的等价关系。

答案:

一、填空题(48分，共16题，每小题3分)

1.

参考答案： 永真式 解题方案：

答案正确得满分，错误不得分

2.

参考答案： G是连通m_n+l 解题方案： 评分标准：

3.

参考答案：

、每条边；每个顶点 解题方案： 评分标准：

4.

参考答案：

(1) PAQ (2) P—]Q (3)P-»]Q 解题方案：

评分标准：

5.

参考答案：

8

解题方案： 评分标准：

6.

参考答案：

可满足式 永假式(或矛盾式) 解题方案： 评分标准：

答案正确得满分，错误不得分

7.

参考答案：

1

解题方案:

8.

参考答案：

(1)

4 (2) 4

解题方案： 评分标准：

9.

参考答案：

_24, 36_ 1 无 1

解题方案： 评分标准：

10.

参考答案： IPA(QVR) 解题方案： 评分标准：

11.

参考答案：

8

解题方案： 评分标准：

12.

参考答案：

{<2, 12>, <3,8>, <3, 12>, <0, 14>}

解题方案： 评分标准：

13.

参考答案： 解题方案： 评分标准：

14.

参考答案： 永真；永假 解题方案： 评分标准：

15.

参考答案：

4

解题方案： 评分标准：

16.

参考答案：

7, 28

解题方案： 评分标准：

二、作图题（8分，共1题，每小题8分）

0.

参考答案：

解题方案: 评分标准:

三、简答题（4分，共1题，每小题4分）

0.

参考答案：

是；欧拉回路为：

v 1 rvO —>v5—>vl TV4

解题方案： 评分标准：

TV2TV3TV4 TV2 —>vl

四、分析题（IO分，共2题，每小题5分）

1.

参考答案: 自反。 反自反3 对称2 反对称G 传递。 V £ •山 山 =2 也 X'' V ° £ V a •\\L 解题方案:

评分标准：

2.

参考答案：

R是A上的等价关系。（因为同时满足自反性、对称性、传递性）

[1]K=[2]R=[3]R=[1]R={1,2,3}

解题方案：

R是A上的等价关系。（因为同时满足自反性、对称性、传递性）

[1]R=[2]R=[3]R=[1]R={1, 2, 3}

评分标准：

5

5

五、证明题（30分，共5题，每小题6分）

1.

参考答案：

设e（）6G也是幕等元，则e0=eo=e0e,由消去率可知e0=eo

解题方案： 评分标准:

2

2.

参考答案：

证明：(1)匚I P。

(2) Tr P・ (3) 〕q (4) pVq

T(l)(2> P。

(5) p T(3)(4)『 (6) p—s P*J (7) s T(5)(6)。

解题方案： 评分标准：

3.

参考答案：

对于问题中的四个简单命题，用pl,p2,p3,p4分别表示甲、乙、丙、丁作案, 对于问题中的四个简单命题，用pl,p2,p3,p4分别表示甲、乙、丙、丁作案, 则办案人员的推理可形式化如下：

前提(1 ) ( 1 pl 人 1 p2)—( 1 p3 A p4)

(2) ( ] p3 △] p4)—( ] pl △] p2)

(3) (pl A p2)—(p3 A! p4) V ( 1 p3 A p4) (4) (p2 A p3)—(pl A p4) v ( 1 pl A! p4) 结论：pl

由于：((]pl 人]p2)—( 1 p3 A p4) ) A ( ( ] p3 △] p4)—( ] pl △] p2)) A ( (pl A p2)一'(p3 △] p4) v ( 1 p3 A p4) ) A ((p2 A p3)—>(pl A p4) v ( ] pl △] p4) ) —pl

上金不是永真式，如取pl=0,p2=l,p3=0,p4=l时，上式的真值为假。 故pl不是前提(1)( 2 ) ( 3 ) ( 4 )的有效结论。

即甲是作案者的结论是不正确的。

解题方案：

对于问题中的四个简单命题，用pl,p2,p3,p4分别表示甲、乙、丙、丁作案, 对于问题中的四个简单命题，用pl,p2,p3,p4分别表示甲、乙、丙、丁作案, 则办案人员的推理可形式化如下：

前提(1 ) ( 1 pl 人1 p2)—( 1 p3 A p4)

(2) ( ] p3 △] p4)—( ] pl △] p2)

(3) (pl A p2)—(p3 △] p4) v ( 1 p3 A p4) (4) (p2 A p3)—(pl A p4) v ( 1 pl A! p4) 结论：pl

由于：((]pl 人 1 p2)—( 1 p3 A p4) ) A ( ( ] p3 △] p4)—( ] pl △] P2))

A ( (pl A p2)—>(p3 A! p4) v ( 1 p3 A p4) ) A

((p2 A p3)—(pl A p4) v ( 1 pl A! p4) ) —pl

上式不是永真式，如取pl=0,p2=l,p3=0,p4=l时，上式的真值为假。 故pl不是前提(1)( 2 ) ( 3 ) ( 4 )的有效结论。

即甲是作案者的结论是不正确的。 评分标准：

111112 111 4.

参考答案：

因为对于任意的 a, bGA,都有 g(a^b)= fl(a*b)* f2 (a^b) = fl (a)* fl (b)

* f2 (a) * f2 (b) =g(a) *g(b)所以，g 是由到的同态。

解题方案： 评分标准：

5.

参考答案： 证明：(1)自反性。

由于R是A上的自反关系，则对于A集合上的所有元素X,有丘R,因为：

c R A £ R 有：UT,故T是 A上的自反关系。“

(2) 对称性“

对于A上的元素％x，若eT,则有：〈豪勺盗〉WR, “ 由于：FRA 丘R。£RA eRo eT” 所以T是A上的对称关系。\"

(3) 传递性“

对于A上的元素耘以，若GT,并且勺藻〉丘匚有一

w R △ 丘 R 并且 u R △ 丘 因为R是A上的传递关系，有冬y>eRA勺思〉eRn〈旧〉eR“

并且 e RA U R^* 仁 2 v^^FvW* 由 RA R^> vwvw-

因此由eT,并且eT=>£T,故T是A上传递关系。。 综上所述，T满足自反、对称、传递性，故T是等价关系° “

解题方案： 评分标准: