国防科大版离散数学习题答案

精品文档

2. R的所有极大相容类为：{x1, x2, x3}，{x1, x3, x6}，{x3, x4, x5}，{x3, x5, x6}。

3. A上共有2

n2?n2个不相同的相容关系。

习题2.7

1.

a) 不正确；（不自反） b) 不正确；（不自反） c) 不正确；（不自反） d) 不正确；（不传递，< -1, 0 > ? R, < 0, 1 > ? R, 但<-1, 1> ? R） e) 不正确；（不对称） f) 不正确；（不对称） g) 不正确；（不传递） h) 正确； i) 不正确。（不自反，i = 10k时， ? R）

2. 不对。

应加上条件：对于任意x?A，总存在y?A使得 ? R。 3.

证明：

① 已知条件：若 ? R， ? R，则 ? R。

先证对称性：若 ? R，则由于R自反，所以 ? R，由上式有 ? R。 所以R对称。

再证传递性：若 ? R， ? R，则因为R对称，所以 ? R。由已知条件，因为 ? R且 ? R，所以 ? R。 所以R传递。 因此，R时等价关系。

② 已知条件：R是等价关系。 若 ? R， ? R，则因为R对称，所以 ? R。又由于R传递，所以， ?R。 因此，若 ? R， ? R，则 ? R。

习题2.8

1. a) b) c) d)

.

半序；

半序、全序、良序； 无；（不是反对称的） 无；（不是传递的）

精品文档

e) f) g) h) 4. a) b) 6. a) b) c)

半序； 无；（不是传递的） 无；（不是传递的） 拟序。

设R是集合A上的二元关系，证明：

R是A上的半序，当且仅当R ? R-1 = IIA且R = R*。 自反、反对称 ___________ _______传递 R是A上的拟序，当且仅当R ? R-1 = ? 且R = R+。 反自反 ___________ _______传递

断言中为真的有：x4Rx1, x1Rx1。 P的最小元：无；P的最大元：x1 ；

P的极小元：x4和x5；P的极大元：x1 。

{x2, x3, x4}的上界：x1；下界：x4；上确界：x1；下确界：x4。 {x3, x4, x5}的上界：x1, x3；下界：无；上确界：x3；下确界：无。 {x1, x2, x3}的上界：x1；下界：x4；上确界：x1；下确界：x4。

7. a) b) c) d) 8. 9.

< I, ? >中的非空子集I无最小元。 < I+, |>（“|”为整除关系）中的非空子集{x | x >4}无最大元。 中的非空子集(0, 1)由下确界0，但无最小元。 书上例4中的非空子集{4}有上界8和12，但无上确界。 归纳法。 归纳法。

第三章 函数

习题3.1

1. g) h) i) 2. a)

.

不是部分函数；原因：存在<0, 1>, <0, 2> ? f，但1 ? 2 。 部分函数；

不是部分函数。原因：存在<4, 2>, <4, -2> ? f，但2 ? -2 。

部分函数；定义域为：{1, 2, 3, 4}，值域为：{<2, 3>, <3, 4>, <1, 4>}。

精品文档

b) 部分函数；定义域为：{1, 2, 3}，值域为：{<2, 3>, <3, 4>, <3, 2>}。 c) 不是部分函数；

d) 部分函数。定义域为：{1, 2, 3}，值域为：{<2, 3>}。 3. 证明：

证明分两部分：① 部分函数之单值性；② dom f = ?(A) ? ?(A) 。

5.

e) 证明：

对于任意y ? f [A] – f [B]，则y ? f [A] 且 y ? f [B] 。 因为y ? f [A] ，所以存在x ? A 使得 f (x) = y 。 又因为y ? f [B]，所以x ? B。（用反证法，假设x ? B，则f (x) ? f [B]，而y = f (x)，所以y ? f [B]。矛盾）

所以，x ? A - B 。因此，y = f (x) ? f [A-B]。 于是，f [A-B] ? f [A] – f [B]。

“=”不能代替“?”的反例，

令X = { x1, x2 }，Y = { y }，f = { , }。 A = { x1, x2 }，B = { x1 }。

则f [A-B] = {y}，而f [A] – f [B] = ?。 6.

e) f = { <<-1, -1>, 0>, <<-1, 0>, -1>, <<-1, 1>, -2>, <<0, -1>, 1>, <<0, 0>, 0>, <<0, 1>, -1>,

<<1, -1>, 2>, <<1, 0>, 1>, <<1, 1>, 0> }； f) ran f = {-2, -1, 0, 1, 2}；

g) f ?{0, 1}2 = { <<0, 0>, 0>, <<0, 1>, -1>, <<1, 0>, 1>, <<1, 1>, 0> }； h) 参见下题。 7.

a) ① m ? n，Pnm?n !个；② m > n，0个。

(n?m) !b) ① m < n，0个；② n = 0且m ? 0，0个；③ n = 0且m = 0，1个；

1n?1kkm④ m ? n ? 1，第二类Stirling数?(?1)Cn(n?k)。

n !k?0 8.

a) 证明：f (99) = f ( f (110) ) = f (100) = f ( f (111) ) = f (101) = 91。 b) 证明：

① f (100) = f (99) = 91；

② ? i ? {1, 2, …, 9}，f (89 + i) = f (90 + i)，所以f (89) = f (90) = … = f (99) = 91。 f (89 + i) = f ( f (89 + i + 11) ) = f (90 + i)。

.

精品文档

③ 假设当k+1 ? x ? 100时，f (x)均等于91。(0 ? k ? 89)

则当x = k ( k ? 0 ) 时，则有 f (k) = f ( f (k+11) )。

而0 ? k ? 89，所以 k+1 ? k+11 ? 100，由归纳假设有f (k+11) = 91，即f (k) = f (91) = 91。

所以，f (x) = 91对于0 ? k ? 89也成立。

习题3.2

4. 归纳法。 5. 证明：

① 因为f : A?A为满射，所以? a ? A . ? xa ? A使得f ( xa ) = a。

又因为f ? f = f，所以f (a) = f ( f ( xa ) ) = f ? f ( xa ) = f ( xa ) = a ，即 f (a) = a。 所以 II A ? f 。 ② 对于任意 ? f ，因为II A ? f ，所以 ? f 。 而f为部分函数，即“单值”，于是，x = y 。 所以 = ? II A 。 所以f ? II A 。 ② 另证

下面要证明II A ? f不可能。用反证法，假设II A ? f，则 存在a? ? a使得f (a?) = a。 因为f为满射，所以必存在x a? ? A使得f (x a?) = a?。

因为f ? f = f，所以a? = f (x a?) = f ? f (x a?) = f ( f (x a?) ) = f (a? ) = a ，即 a? = a。 这与a? ? a矛盾。

所以假设不成立，即II A ? f不可能。 由①②可知II A = f 。 6.

证明：首先，dom (g ? f ) = f -1 [dom g]。 因为ran f ? dom g ，所以dom f = f –1 [ ran f ] ? f –1 [ dom g ]。

又因为dom g ? Y，而f -1 [Y] = domg f，所以f –1 [ dom g ] ? f –1 [ Y ] = dom f。 所以，dom (g ? f ) = dom f 。 8.

a) 因为f ? f = f ，所以对于任意i ? A，均有f (f (i) ) = f (i) 。即若f (i) = j ( j ? i )，则f (j) =

i。设m为集合{ i | i ? A且f (i) = i }的元素个数，即m为f中对应到自身的二元序偶个

数。则对m求累加和得到满足f ? f = f的函数个数为

?Cm?1nmnmn?m个。

b) f ? f = II A，所以f为双射，并且对于任意i ? A，均有f (f (i) ) = i（即若?f且i?j，

则?f ）。（特征：未对应到自身的二元序偶个数必为偶数个。）设k为集合{ i | i ? A

.

精品文档

且f (i) = i }的元素个数/2，即2k为f中对应到自身的二元序偶个数。则对k求累加和得到满足f ? f = II A的函数个数： 当n为偶数时，有

?Ck?0n/22kn?(n?2k?1)?(n?2k?3)???1个；

(n?1)/2当n为奇数时，有

?Ck?02k?1n?(n?2k?2)?(n?2k?4)???1个。

c) f ? f ? f = II A ，所以f为双射，因此满足f ? f ? f = II A的函数个数：

(n?1)/3当n = 3k+1 ( k ? N ) 时，有个；

?Ck?03k?1n?((n?3k?2)?(n?3k?3)?1)???(2?1?1)(n?2)/3当n = 3k+2 ( k ? N ) 时，有个；

当n = 3k ( k ? N ) 时，有

?Ck?03kn3k?2n?((n?3k?3)?(n?3k?4)?1)???(2?1?1)?Ck?0n/3?((n?3k?1)?(n?3k?2)?1)???(2?1?1)个。

9.

a) 证明：因为g ? f 为满射，所以g为满射。而g又是内射，所以g为双射。

假设f不是满射，则存在y ? Y使得 y ? ran f。 而g是双射，所以g (y) ? Z，又g ? f 为满射，所以ran (g ? f ) = Z。即g (y) ? ran (g ? f )。 所以存在x ? X使得 g (y) = g ? f (x) = g ( f (x) )。

因为g为内射，所以y = f (x)。因此，y ? ran f。这与y ? ran f矛盾。 所以假设不成立，即f 是满射。

b) 证明：因为g ? f 为内射，所以f为内射。而f又是满射，所以f为双射。

假设g不是内射，则存在y1, y2 ? Y使得 y1 ? y2并且 g (y1) = g (y2) 。

因为f为双射，所以存在x1, x2 ? X使得 x1 ? x2并且 f (x1) = y1，f (x2) = y2 。 而g ? f 为内射，则 g ? f (x1) ? g ? f (x2) ，即 g (y1) ? g (y2)。 这与g (y1) = g (y2)矛盾。

所以假设不成立，即g 是内射。

.