离散数学试卷B答案

北华大学07-08学年离散数学试卷B 答案

一、 回答下列问题(25分,每小题5分)

1、 若 f 是集合A 到集合B 的一个映射，当x ≠y 时，有f(x)

≠f(y),?x,y ∈A, 就说

f 是A 到B 的一个单射。

２、如果集合A 上的关系R 是自反的，非对称的和传递的，则称R 为A 上的偏序或称R 是A 上的偏序关系。

３、设(S,ο)是一个代数系统，其中“ο”是二元运算，若“ο”是可结合的，则称(S,ο)为半群。含有单位元素的半群称为独异点。 ４、? ∧ ∨ → ? 5、()m v n

i i 2deg 1=∑=.3分

因为每条边有两个次数,所以m 条边有2m 个次数.2分 二、计算（20分，每小题10分） 1、

(){}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}

4,3,2,1,4,3,1,4,3,2,4,2,1,3,2,1,4,3,4,2,3,2,4,1,3,1,2,1,4,3,2,1,Φ=A ρ5分

B 中无最大元素，1分 . 最小元素是Φ，1分.

B 中极大元素是{}4,3,2，{}4,2,1 ，2分. 极小元素是Φ，1分. 2、()()()

C A C B B A →→→∧→

()()()C A C B B A ∨?→∨?∧∨?? 2分 ()()()()C A C B B A ∨?∨∨?∧∨??? 1分

()()()C A C B B A ∨?∨?∧∨?∧? 1分 ()()()()C C B A B A ∨?∧∨?∨?∧? 2分

()()()()()()C C C B A B A A ∨?∧∨∨?∨?∧?∨? 2分 ()()C B B A ∨∨?∨??

C B B A ∨∨?∨??

C A ∨∨??1 1分 1? 1分

三、证明（30分，每小题10分）

1、证明：设次数为偶数的结点有1n 个，记为i

E v ()1,2,1n i Λ= 2分，

次数为奇数的结点有2n 个，记为i

F v ()2,,2,1n i Λ= 1分，

因为

()()

()

∑∑∑===+==n

i F n

i E n

i i i i v v v m 1

1

1

deg deg deg 2 3分

因为次数为偶数的各结点次数之和为偶数，故()∑=n

i E i

v 1

deg 是偶数，2

分

若2n 是奇数，则()∑=n i F i

v 1

deg 为奇数，于是()∑=n

i i v 1

deg 是奇数，2分

这是矛盾的，故2n 必为偶数. 1分 2、证明：

(1) 运算封闭：?x,y ∈S,x+y ∈S,则S 对“+”满足运算封闭. 2分 (2)结合律： ?1k ，2k ，3k ∈Z ，则

()()()m k k m k m k k k m k m k m k 321321321++=++=++ 3分 (3)单位元素0=e ：?Z k ∈,

km km km =+=+00 2分 (4)逆元km - ?Z k ∈-，有S km ∈-

()0==+-=-+e km km km km 2分 故，()是群+,S . 1分

3、证明：反证法，假设R 不是对称的，则至少有两个元素A y x ∈,，使当()R y x ∈,，必有()R x y ∈,.由于R 是拟序，故它是传递的。因此有

()R x x ∈,，这与R 是非自反的矛盾，故R 是非对称的.

四、（10分）解： A: π是无理数 1分

B: 3是无理数 1分 C: 2也是无理数 1分 D: 6能被2整除 1分 E: 6才能被4整除 1分 ()()D E C B A →∧→∧ 5分 五、证明：

设图G 有r 个区域，则围城这个区域所用的边数为kr 个， 1分 因为每条边在这些区域中最多出现两次 1分

所有围城这些区域的边之和m kr 2<, 1分 再由欧拉定理有

2=+-r m n ? m n r +-=2 3分

()m m n k 22<+- 1分

()()22-<-n k m k 1分

,3

2--<∴k n k m . 2分

六、证明：设p

q

为有理数，记q p +为该有理数的高，对有理数进行如下排队， 1分

11 →

12 13 → 14 15

→ (1)

n …

↙ ↗ ↙ ↗ ↙ 2

1 2

2 2

3 2

4 2

5 (2)

n

… ↓ ↗ ↙ ↗ ↙

3

1 3

2 3

3 3

4 3

5 (3)

n

… ↙ ↗ ↙ ↗

41 42 43 44 45 …… 4n

… ↓ ↗ ↙ ↗

51 52 → 53 54 55 (5)

n

… 8分 按照这样的顺序将有理数与自然数建立一个一一对应关系，则有理数集与自然数集对等，因此，有理数集是可数集合. 1分