洪帆《离散数学基础》（第三版）课后习题答案南京廖华答案网

洪帆《离散数学基础》（第三版）课后习题答案下载本文

文章发布时间 : 2024/9/19 19:06:23星期四

第1章集合

1、列举下列集合的元素 (1) 小于20的素数的集合 (2) 小于5的非负整数的集合 (3) {i|i?I,i2?10i?24?0且5?i?15} 答：(1) {1,3,5,7,11,13,17,19}

(2) {0,1,2,3,4} (3) {5,6,7,8,9,10,11}

2、用描述法表示下列集合 (1) {a1,a2,a3,a4,a5} 答：{ai|i?I,1?i?5} (2) {2,4,8,} 答：{2i|i?N} (3) {0,2,4,100}

答：{2i|i?Z,0?i?50}

3、下面哪些式子是错误的？ (1) {a}?{{a}} 答：正确 (2) {a}?{{a}} 答：错误 (3) {a}?{{a},a} 答：正确 (4) {a}?{{a},a} 答：正确

4、已给S?{2,a,{3},4}和R?{{a},3,4,1}，指出下面哪些论断是正确的？哪些是错误的？ (1) {a}?S 错误

(2) {a}?R 正确 (3) {a,4,{3}}?S 正确 (4) {{a},1,3,4}?R 正确 (5)R?S 错误 (6) {a}?S 正确 (7) {a}?R错误 (8) ??R正确 (9) ??{{a}}?R 正确 (10) {?}?S错误 (11) ??R错误 (12) ??{{3},4}正确

5、列举出集合A,B,C的例子，使其满足A?B，B?C且A?C

答：A?{a}，B?{{a}}，显然A?B，C?{{{a}}}，显然B?C，但是A?C。

6、给出下列集合的幂集 (1) {a,{b}}

答：幂集{?,{a},{{b}},{a,{b}} (2) {?,a,{a}}

答：幂集{?,{?},{a},{{a}},{?,a},{?,{a}},{a,{a}},{?,a,{a}}} 7、设A?{a}，给出A和2A的幂集

答：2A?{?,{a}} 22?{?,{?{}}a,{{?}a},{ ,{}}}8、设A?{a1,a2,,a8}由B17和B31所表示的A的子集各是什么？应如何表示子

A集{a2,a6,a7}和{a1,a3} 答：B17?B00010001?{a4,a8}

B31?B00011111?{a4,a5,a6,a7,a8}

{a2,a6,a7}?B01000110?B70，{a1,a3}?B10100000?B160

9、设U?{1,2,3,4,5}，A?{1,4}，B?{1,2,5}，C?{2,4}，确定集合： (1) A?B? (2) (A?B)?C? (3) A?(B?C) (4)(A?B)?(A?C) (5) (A?B)? (6) A??B? (7) (B?C)? (8)B??C? (9) 2A?2C (10)2A?2C 答：(1) B??{3,4}，A?B??{4}

(2) A?B?{1}，C??{1,3,5}，(A?B)?C??{1,3,5} (3) B?C?{2}，A?(B?C)?{1,2,4}

(4) A?B?{1,2,4,5}，A?C?{1,2,4}，(A?B)?(A?C)?{1,2,4} (5) (A?B)??{2,3,4,5} (6) A??{2,3,5}，A??B??{2,3,4,5} (7) B?C?{1,2,4,5}，(B?C)??{3} (8) B??{3,4}，C??{1,3,5}，B??C??{3}

，，4}}，2A?2C?{{1},{1,4}} (9) 2A?{?,{1},{4},{1,4}}，2C?{?,{2},{4}{2(10) 2A?2C?{?,{4}}

10、给定自然数集N的下列子集：

A?{1,2,7,8}，B?{i|i2?50}，C?{i|i可被3整数，0?i?30}

D?{i|i?2k,k?Z,0?k?6}

求下列集合： (1) A?(B?(C?D)) 答：B?{1,2,3,4,5,6,7}，

C?{0,3,6,9,12,15,18,21，,D?{1,2,4,8,16,32,64}

A?(B?(C?D 2))?{0,1,2,3,4,5,6,7,8,9,1224,,1257,,1360,,138,,64}(2) A?(B?(C?D))??

(3) B?(A?C)

解：A?C?{0,1,2,3,6,7,8,9,12,15,18,21,24,27,30}，B?(A?C)?{4,5} (4) (A??B)?D

解：A??B?B?A?{3,4,5,6}，(A??B)?D?{1,2,3,4,5,6,8,16,32,64}

11、给定自然数集N的下列子集

A?{n|n?12}，B?{n|n?8}，C?{n|n?2k,k?N}，D?{n|n?3k,k?N} E?{n|n?2k?1,k?N}

将下列集合表示为由A,B,C,D,E产生的集合：

(1) {2,4,6,8} (2){3,6,9} (3){10} (4){n|n?3或n?6或n?9} (5) {n|n是偶数且n?10或n是奇数且n?9} (6) {n|n是6的倍数}

答：A?{1,2,3,4,5,6,7,8,9,10,11}，B?{1,2,3,4,5,6,7,8}

C?{2,4,6,8,}，D?{3,6,9,12,}，E?{1,3,5,7,} {2,4,6,8}?B?C {3,6,9}=A?D {10}=((A?B)?D)?E

(4){n|n?3或n?6或n?9}?{3}?{6}?{9,10,11,12,}

?{3,6,9,10,11,12,}?(A?D)?B?

(5) {2,4,6,8,10,11,13,15,}?((A?E)?(E?B))?((A?D)?B) (6) {n|n是6的倍数}?{6,12,18,24,30}?C?D

12、判断以下哪些论断是正确的，哪些论断是错误的，并说明理由。 (1) 若a?A，则a?A?B

答：正确，根据集合并的定义 (2) 若a?A，则a?A?B

答：显然不正确，因为根据集合交运算的定义，必须a同时属于A和B (3) 若a?A?B，则a?B 答：正确

(4) 若A?B，则A?B?B 答：错误

(5) 若A?B，则A?B?A 答：正确

(6) 若a?A，则a?A?B 答：错误

(7) 若a?A，则a?A?B 答：正确

13、设A,B,C是任意的集合，下述论断哪些是正确的？哪些是错误的？说明理由

(1) 若A?B?A?C，则B?C

答：不正确，反例，设A??，则不论B,C是什么集合，都有A?B?A?C??，但显然B,C不一定相等。

(2) 当且仅当A?B?B，有A?B；

答：正确，证明如下：若A?B?B，则对?a?A，有a?A?B?B，则有a?B，因此有A?B。反之，若A?B，则A?B?B显然成立。

(3) 当且仅当A?B?A，有A?B

答：正确，证明如下：若A?B?A，则对?a?A，因此a?A?B，则a?B，则有A?B。若A?B，则?a?A，有a?B，因此由a?A，可以得出a?A?B，因此A?A?B，又A?B?A，有A?B?A。

(4) 当且仅当A?C，有A?(B?C)??

答：不正确，因为A?(B?C)?A?B?C?，因此不一定需要满足A?C，而若例如：A?{a,b,c}，B?{d,e}，C?{a,b}，A?(B?C)??A?B??也可以满足。成立，而A?C不成立。

(5) 当且仅当B?C，有(A?B)?C?A

答：不正确，因为若B?C，有(A?B)?C?A成立，但是反之不成立，反例如下:A?{1,2,3,4,5}，B?{1,6}，C?{1,2}，而A?B?{2,3,4,5}，

(A?B)?C?{1,2,3,4,5}，但是B?C不成立。

14、设A,B,C,D是集合，下述哪些论断是正确的？哪些是错误的？说明理由。 (1) 若A?B,C?D，则A?C?(B?D)

答：正确，证明：对?a?A?C，则a?A或a?C，因为A?B,C?D，因此a?B或a?D，因此a?B?D，即A?C?(B?D)成立。 (2) 若A?B,C?D，则A?C?(B?D) 答：正确

(3)若A?B，C?D，则A?C?(B?D) 答：正确

(4) 若A?B,C?D，则A?C?(B?D)

答：不正确。例如若A?B,C?D，但是A?C??，B?D??，则

??A?C?(B?D)??。 15、设A,B是两个集合，问：

(1)如果A?B?B，那么A和B有什么关系？

答：因为A?B?B，而A?B?A?B??B，即对?a?B有a?A,a?B?，因此

A?B??。

(2) 如果A?B?B?A，那么A和B有什么关系？

答：充要条件是A?B。证明：因为A?B?B?A的(A?B)?A?(B?A)?A，从而有A?A?B，即A?B，同理可证明B?A，因此A?B。

16、设A,B是任意集合，下述论断哪些是正确的？哪些是错误的？说明理由。 (1) 2A?B?2A?2B

答：不正确。例如A?{a,b}，B?{b,c}，则A?B?{a,b,c}

2A?B?{?,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}} 2A?{?,{a},{b},{a,b}}，2B?{?,{b},{c},{b,c}}

显然2A?B?2A?2B不成立。 (2) 2A?B?2A?2B

答：成立。证明：对?C?2A?2B，则C?2A且C?2B，则C?A,C?B，则因此C?2A?B。反之，若?C?2A?B，则C?A?则C?A且C?B，C?A?B，B，因此C?2A，且C?2B，因此C?2A?2B，即2A?B?2A?2B。 (3) 2A??(2A)?

答：显然不成立，因为左边集合肯定含有?，而右边不含有。

17、在一个班级的50个学生中，有26人在离散数学的考试中取得了优秀的成

绩；21人在程序设计的考试中取得了优秀的成绩。假如有17人在两次考试中都没有取得优秀成绩，问有多少人在两次考试中都取得了优秀成绩?

答：分别用A,B表示在离散和程序设计的考试中取得优秀成绩的学生集合，U表示全体学生集合：则#(A)?26，#(B)?21，#(A?B)?50?17?33，则两次考试中都取得了优秀成绩的学生人数为26+21-33=14人。

18、设A,B,C是任意集合，运用成员表证明： (1) (A?B)?(A??C)?(A?C)?(A??B) 证明：

A 0 0 0 0 1 1 1 1 B 0 0 1 1 0 0 1 1 C 0 1 0 1 0 1 0 1 A? A??C A?B A?C A??B 左边右边 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 0 1 1 1 1 1 1 0 1 1 1 0 0 1 0 0 0 0 0 1 1 1 0 1 1 0 0 1 0 0 0 0 0 1 1 1 0 1 1 (3) A?(B?C)?(A?B)?(A?C) 证明： A B C A?B A?C (A?B)?(A?C) B?C A?(B?C) 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 0 1 1 1 0 由上得证左右两边相等。

0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1 1 1 0 0 0 0 1 0 0 0 19、由S和T的成员表如何判断S?T？应用成员表证明或否定

?) (A?B)?(B?C??A? B答：先分别给出集合(A?B)?(B?C)?和A?B?的成员表如下： A B C A?B B?C (B?C)? (A?B)?(B?C)? B? A?B? 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0 1 1 0 0 观察上述表格，我们发现(A?B)?(B?C)?所标记的列中，仅在第五列为1，这

意味着当元素u?A,u?B且u?C时，u?(A?B)?(B?C)?，而在其他情形下，元素u?(A?B)?(B?C)?。而集合A?B?所标记的列中，第五和第六行均为1，这意味着u?A,u?B且u?C时，u?A?B?，当u?A,u?B，且u?C时，也有

u?A?B?。所以当元素u?(A?B)?(B?C)?时也有u?A?B?，反之不然，因此(A?B)?(B?C)??A?B?成立。

20、A1,A2,,Ar为U的子集，A1,A2,,Ar至多能产生多少不同的子集？

答：构造由A1,A2,,Ar所产生的集合的成员表，显然该成员表由2r个行所组成。

在该成员表中不同的列可由2r为的二进制数000的列所标记的集合不相同的，因此由A1,A2,合。

21、证明分配律、等幂律和吸收律9? 1分配律 A?(B?C)?(A?B)?(A?C)

0~11111分别表示，而不同

r,Ar至多可以产生22个不同的集

证明：对?a?A?(B?C)，则有a?A且a?B?C，即有a?A，且a?B或a?C，也即有a?A?B或a?A?C，即a?(A?B)?(A?C)，因此左边?右边。对?a?(A?B)?(A?C)，则a?A?B或a?A?C，即a?A且a?B，或a?A且a?C，即有a?A或a?B?C，因此a?A?(B?C)，因此右边?左边。

2 吸收律A?(A?B)?A

证明：A?(A?B)?A显然成立，对?a?A，则显然有a?A?B，因此有

a?A?(A?B)，因此有A?A?(A?B)成立。

22、设A,B,C是任意集合，运用集合运算定律证明： (1) B?((A??B)?A)??U

左边?B?(A??B)??A?证明：?B?(A?B?)?A??B?((A??A)?(A??B))

?B?(U?(A??B))?B?(A??B)?U?右边(2) (A?B)?(B?C)?(C?A)?(A?B)?(B?C)?(C?A)

左边?(B?(A?C))?(C?A)证明：

?((C?A)?B)?((C?A)?(A?C))?(C?B)?(B?A)?((A?C?A)?(A?C?C)?(C?B)?(B?A)?(A?C)?(A?C)?右边

(3) (A?B)?(B?C)?(A?C)?(A?B)?(A??B?C)?(A?B??C)

右边?(B?((A??C)?A))?(A?B??C)?(B?(A??A)?(A?C))?(A?B??C)?(B?(A?C))?(A?B??C)?(B?A)?(B?C)?(A?B??C)?(B?C)?(A?((B??C)?B))?(B?C)?(A?(B??B)?(B?C))?(B?C)?(A?(B?C))?(B?C)?(A?B)?(A?C) 由上题的证明可知左边=右边，得证。

23、用得摩根定律证明(A?B?)?(A??(B?C?))补集是

(A??B)?(A?B?)?(A?C)。

证明：

((A?B?)?(A??(B?C?)))??((A?B?)?)?(A??(B?C?))?证明：?(A??B)?(A?(B?C?)?)

?(A??B)?(A?(B??C))?(A??B)?(A?B?)?(A?C)

24、设Ai为某些实数的集合，定义为

A0?{a|a?1} 1Ai?{a|a?1?}(i?1,2,)i?试证明：

i?1Ai?A0

证明：设a?1Ai，则比存在整数k，使得a?Ak，因此有a?1?，于是a?1,

ki?1??因此a?A0。另一方面，设a?A0，则有a?1，若a?0，则有a?A1，因此a?i?1Ai。

若0?a?1，则令b?1?a，a?1?b?1?11?1?，令k????1，其中表示的整数1b?b?b?1111部分，则有因此a?1?即a?Ak，于是a?Ai，因此得证。 ?，?1?，

11kki?1bb25、设{A1,A2,,Ar}是集合A的一个分划，试证明A1?B,A2?B,,Ar?B中所

有非空集合构成A?B的一个分划。

r证明：因为{A1,A2,,Ar}是集合A的一个分划，因此由分划的定义，可得

i?1Ai?A，

且Ai?Aj??,i?j，而(Ai?B)?(Aj?B)??,i?j，且

rr(Ai?B)?(i?1i?1Ai)?B(分配律)?A?B，因此A1?B,A2?B,,Ar?B中所有非

空集合构成A?B的一个分划。

26、n个元素的集合，有多少中不同的方法可以分划成两块？

12答：当n奇数时有Cn?Cn?12Cn?Cn??Cn2种不同的方法，当n为偶数时有

n?1?1n/2?Cn种不同的方法。

第2章关系

1、若A?{0,1},B?{1,2}，确定集合：

(1)A?{1}?B (2)A2?B (3) (B?A)2 解：A?{1}?B?{(0,1,1),(0,1,2),(1,1,1),(1,1,2)}

A2?B?{((0,0),1),((0,1),1),((1,0),1),((1,1),1),((0,0),2),((0,1),2),((1,0),2),((1,1),2)}

(B?A)2?{((0,1),(0,1)),((0,1),(0,2),((0,1),(1,1)),((0,1),(1,2))((0,2),(0,1)),((0,2),(0,2),((0,2),(1,1)),((0,2),(1,2))

((1,1),(0,1)),((1,1),(0,2),((1,1),(1,1)),((1,1),(1,2))

((1,2),(0,1)),((1,2),(0,2),((1,2),(1,1)),((1,2),(1,2))}

2、在通常的具有X轴和Y轴的笛卡尔坐标系中，若有

3?x?2}X?{x|x?R,?Y?{y|y?R,?2?y?0}试给出笛卡尔积X?Y的几何解释

解：表示横坐标x的范围在?3?x?2，纵坐标y的范围在?2?y?0的二维点集所构成的集合。

3、设A，B，C和D是任意的集合，证明 (1) A?(B?C)?(A?B)?(A?C) (2) A?(B?C)?(A?B)?(A?C) (3) (A?B)?(C?D)?(A?C)?(B?D) 证明：(3) 首先，因为A?B?A，C?D?C，所以 (A?B)?(C?D)?A? C 类似地，(A?B)?(C?D)?B?D，所以有： (A?B)?(C?D)?(A?C)?(B? D 反之，若(x,y)?(A?C)?(B?D)，则(x,y)?(A?C)，(x,y)?(B?D) 则x?A,y?C，且x?B,y?D，即x?A?B，y?C?D 所以，(x,y)?(A?B)?(C?D) 所以(A?C)?(B?D)?(A?B)?(C?D) 所以(A?B)?(C?D)?(A?C)?(B?D)

4、对下列每种情形，列出由A到B的关系?的元素，确定?的定义域和值域，构造?的关系矩阵：

(1) A?{0,1,2},B?{0,2,4},??{(a,b)|ab?A?B} 解：A?B?{0,2}，??{(0,0),(0,2),(0,4),(1,0),(2,0),(1,2)}

?111???关系矩阵 M???110??100? ??(2) A?{1,2,3,4,5},B?{1,2,3},??{(a,b)|a?b2} 解：??{(1,1),(4,2)} 关系矩阵M?= ?10? ?00?00 ??01 ?00?

义域和值域 (1) ??{(i,j)|i?j} 解：图略

0??0?0??0?0??5、设A?{1,2,3,4,5,6}，对下列每一种情形，构造A上的关系图，并确定?的定

??{(1,1),(2,2),(3,3),(4,4),(5,5),(6,6)} 定义域D??A，R??A

(2) ??{(i,j)|i整除j}

解：??{(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(2,2),(2,4),(2,6),(3,3),(3,6),(4,4),(5,5),(6,6)}

定义域D??A，R??A

(3) ??{(i,j)|i是j的倍数}

解： ??{(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(2,1),(3,1)

(4) ??{(i,j)|i?j}

?解： ?{(6,5),(6,4),(6,3),(6,2),(6,1)(5,4),(5,3),(5,2),(5,1)

(4,3),(4,2),(4,1)

(3,2),(3,1)

(2,1)}定义域D??{6,5,4,3,2}，R??{5,4,3,2,1}

(5) ??{(i,j)|i?j}

(4,1),(5,1),(6,1),(4,2),(6,2),(6,3)}定义域D??A，R??A

解：定义域D??{5,4,3,2,1}，R??{6,5,4,3,2}

??{(1,2),(1,3),(1,4),(1,5),(1,6),(2,3),(2,4),(2,5),(2,6)(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)}(6) ??{(i,j)|i?j,ij?10}

解：? ?{(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(2,1),(2,2),(2,3) (2,4),(3,1),(3,2),(3,3),(4,1),(4,2),(5,1),(6,1)}定义域D??{6,5,4,3,2,1}，R??{6,5,4,3,2,1}

(7) ??{(i,j)|i?j,(i?j)2?A}

解： ??{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(2,4),(3,1)

(8) ??{(i,j)|i/j是素数}

解：??{(2,1),(3,1),(5,1),(4,2),(6,3),(6,2)} 定义域D??{2,3,4,5,6}，R??{1,2,3}

6、设?1?{(1,2),(2,4),(3,3)}和?2?{(1,3),(2,4),(4,2)}，试求出?1??2,?1??2，D?2RRD?1， D ( ?1 ? ? ， ? 1 ， ? 和 R ( ?1 ? ?2 )，并证明：D(?1??2)=D?1?D?2 2)2?R? 2 R(?1??2)?R?1(3,2),(3,3),(3,4),(3,5),(4,2),(4,3),(4,4),(4,5)(4,6)，(5,3),(5,4),(5,5),(5,6),(6,4),(6,5),(6,6)}定义域D??A，R??A

解：?1??2?{(1,2),(2,4),(3,3),(1,3),(4,2)}

?1??2?{(2,4)}

D?1?{1,2,3}，D?2?{1,2,4}，R?1?{2,4,3}，R?2?{3,4,2} D(?1??2)?{1,2,3,4} R(?1??2)?{4}

证明：D(?1??2)=D?1?D?2

设x?D(?1??2)，则必存在y，使得(x,y)??1??2，所以(x,y)??1或者

(x,y)??2，x?D?1或者x?D?2，因此，即x?D?1?D?2，所以D(?1??2)?D?1?D?2；

反之，设x?D?1?D?2，则x?D?1或者x?D?2，所以存在y1，使得(x,y1)14

??1，或者存在y2，使得(x,y2)??2，由并集的定义知，(x,y1)??1??2，或者

(x,y2)??1??2，总之有x?D?1??2，故D?1?D?2?D(?1??2)。

证明：R(?1??2)?R?1?R?2

设y?R?1??2，则必存在x，使得(x,y)??1，(x,y)??2，因此b?R?1且

b?R?2，由交集的定义b?R?1?R?1，故R(?1??2)?R?1?R?2。

A1和A2是分别具有基数n1和n2的有限集，7、试问有多少个A1到A2的不同关系？答：A1?A2的所有子集都是A1到A2的一个关系，所以共有2

8、找出集合A?{a1,a2,?,an}上普遍关系和恒等关系的关系矩阵和关系图的特征。

答：A上的普遍关系??A2的关系矩阵是全1矩阵，而恒等关系的关系矩阵是单位矩阵。

9、下列是集合A?{0,1,2,3}上的关系：?1?{(i,j)|j?i?1或者j?i/2}，

#(A1?A2)个不同的关系。

?2?{(i,j)|i?j?2}，试确定如下的复合关系：

（1）?1??2 （2）?2??1 （3）?1??2??1 （4）?13 解：（1）?1?{(0,1),(1,2),(2,3),(0,0),(2,1)}，?2?{(2,0),(3,1)}

?1??2?{(1,0),(2,1)}

（2）?2??1?{(2,1),(2,0),(3,1)} （3）?1??2??1?{(1,1),(1,0),(2,2)} （4）?12?{(0,2),(1,3),(1,1),(0,1),(0,0),(2,2)} ?13?{(0,3),(0,1),(1,2),(0,2),(0,0),(0,1),(2,3),(2,1)}

10、设?1,?2,?3是集合A上的关系，试证明：如果?1??2，则有：（1）?1??3??2??3 （2）?3??1??3??2 （3）?1??2

证明：（1）对?(x,y)??1??3，由复合关系的定义，?z?A，使得，(x,z)??1，

(z,y)??3，因为?1??2，所以(x,z)??2，所以(x,y)??2??3，所以

~~?1??3??2??3

(x,z)??3，(z,y)??1，（2）对?(x,y)??3??1，由复合关系的定义，使得，?z?A，

因为?1??2，所以(z,y)??2，所以(x,y)??3??2，所以?3??1??3??2。

~（3）对?(x,y)??1，有(y,x)??1，因为?1??2，所以(y,x)??2，所以(x,y)??2，

~也即?1??2。

~~?1??2?{(1,3),(1,4),(3,3)}求一个基数最小的关系，11、给定?1?{(0,1),(1,2),(3,4)}，

使满足?2的条件。一般地说，若给定?1和?1??2，?2能被唯一的确定吗？基数最小的?2能被唯一确定吗？

答：?2?{(2,3),(2,4),(4,3)}。一般地说，若给定?1和?1??2，?2不能被唯一的确定。基数最小的?2也不能被唯一确定。

12、给定集合A1,A2,A3，设?1是由A1到A2得关系，?2和?3是由A2到A3得关系，试证明：

（1）?1?(?2??3)=(?1??2)?(?1??3)

证明：根据并集和复合关系的定义，?1?(?2??3)和(?1??2)?(?1??3)都是

A1到A3上的关系，下只需要证明它们由完全相同的序偶组成。

设(a,c)??1?(?2??3)，必存在b?A2，使得(a,b)??1，(b,c)??2??3，所以有(b,c)??2或者(b,c)??3，所以有(a,c)??1??2或者(a,c)??1??3，也即

(a,c)?(?1??2)?(?1??3)，也即?1?(?2??3)?(?1??2)?(?1??3)；反之，若(a,c)?(?1??2)?(?1??3)，也即(a,c)?(?1??2)或者(a,c)?(?1??3)，若(a,c)?(b,c)??2??3，(?1??2)，(b,c)??2，则存在b?A2，使得(a,b)??1，则(a,b)??1，

则(a,c)??1?(?2??3)，若(a,c)?(?1??3)同理可得，因此有(?1??2)?(?1??3)??1?(?2??3)。则?1?(?2??3)=(?1??2)?(?1??3)。（2）?1?(?2??3)?(?1??2)?(?1??3)

证明：设(a,c)??1?(?2??3)，则存在b?A2，使得，(a,b)??1，(b,c)??2??3，则(b,c)??2，且(b,c)??3，所以(a,c)??1??2，且(a,c)??1??3，即

(a,c)?(?1??2)?(?1??3)，所以?1?(?2??3)?(?1??2)?(?1??3)。

13、给定??{(i,j)|i,j?I,j?i?1},?n是什么？

答：I?{?,?3,?2,?1,0,1,2,3,?}，??{?,(?2,?1),(?1,0),(0,1),(1,2),(2,3),(3,4),?}

?2?{?,(?3,?1),(?2,0),(0,2),(1,3),(2,4),(3,5),?}，则?n?{(i,j)|i,j?I,j?i?n}

14、对第9题中的关系，构造关系矩阵（1）M?1 （2）M?1

解：?1?{(0,1),(1,2),(2,3),(0,0),(2,1)} ?2?{(2,0),(3,1)}

M?2?0?0???1??0000??000?000??100??1?0?M?1??0?16 ?0100??010?101??000?

(3) M?2??1

解：?2??1?{(2,1),(2,0),(3,1)}

使得?k??t。

M?2??1?0?0???1??0000??000?100??100?15、设A是有n个元素的有限集，?是A上的关系，试证明必存在两个正整数k,t，证明：因为?是A上的关系，所以对于任意正整数r，?r也是A上的关系，另一方面，因为#(A)?n，所以#(A?A)?n2，#(2A?A)?2#(A?A)?2n，也即A上只有

22n个不同的关系，因此在关系?,?2,?3,?,?2,?2

2n2n2?12中必有两个是相同的，也

即存在两个正整数k,t，使得?k??t，其中1?k?t?2n?1。

16、设?1是由A到B的关系，?2是由B到C的关系，试证明?1??2??2??1。证明：由题设知道?1??2和?2??1都是由C到A的关系，因此只要证明它们由完全相同的序偶组成。设(c,a)??1??2，则(a,c)??1??2，因此必存在元素b?B，

~~~~使得(a,b)??1，(b,c)??2，所以(b,a)??1，(c,b)??2，所以(c,a)??2??1。反之，设(c,a)??2??1，则必存在元素b??B，使得(c,b?)??2，(b?,a)??1，所

~以(a,b?)??1，(b?,c)??2，所以(a,c)??1??2，所以(c,a)??1??2，所以

~~~~~~~~~~~?1??2??2??1。

17、（1）设?1和?2是由A到B的关系，问?1??2??1??2成立吗？答：成立

~一定是自反的吗？（2）设?是集合A上的关系，如果?是自反的，则?~~~~~~答：是的。证明：若?是自反的，则对所有的a?A，有(a,a)??，则一定有

~，则?~也是自反的。 (a,a)??~也是对称的吗？答：是的。（3）若?是对称的，则?~也是可传递的吗？答：是的（4）若?是可传递的，则?证明：若?是可传递的，由定义可知，若(x,y)??，则一定有(x,z)??，(y,z)??，

~，~，(z,y)??~，一定有(z,x)??~也是由逆关系的定义，也即，若(y,x)??，则?可传递的。

18、图2-9给出了集合{1,2,3,4,5,6}上的关系?的关系图，试画出关系?5和?8的图，并利用关系图求出关系?的传递闭包。解：

图2-9

关系??{(1,3),(1,5),(2,5),(4,5),(5,4),(6,3),(6,6)}

?2?{(1,4),(2,4),(4,4),(5,5),(6,3),(6,6)} ?3?{(1,5),(2,5),(4,5),(5,4),(6,3),(6,6)}

?4?{(1,4),(2,4),(4,4),(5,5),(6,3),(6,6)} 因为?4??2，所以?5??3，?8??2

23传递闭包。????????

19、试证明：若?是基数为n的集合A上的一个关系，则?的传递闭包为

????i

i?1??ini?n证明：由定义????，要证明?????，因为?????i，所以只要证明

i?1?i?inini?设(a,b)???，则必存在正整数k，使得(a,b)??k，若k?n，?????即可。

i?1?ii?1i?1i?1i?1则(a,b)???，若k?n，则在A中必存在k?1个元素ai1,ai2,?,aik?1，使得：

i?1i?1nii?1 a?ai1,ai1?ai2,?,aik?1?b

因为k?n，所以在a,ai1,ai2,?,aik?1,b这k?1个元素中必有两个元素air?ait（0?r?t?k，记a为ai0，记b为aik），因此下述关系

a?ai1,?,air?1?air,air?ait?1,?,aik?1?b

成立，这表明a?kb，k1?k?(t?r),k1?k。若k1?n，用类似的方法又可找到

ik2?k1，使a?k2b,?，最后必可找到一正整h，使a?hb且h?n，因此(a,b)? ? ? ，

n故 ? ? ? ? ? 。

i?1i?1?inii?1

20、下列关系中哪一个是自反的、对称的、反对称的或者可传递的？（1）当且仅当|i1?i2|?10(i1,i2?I)时，有i1?i2；

答：是自反的，对称的，非可传递的，例如13?9，9?1，但13?1不成立。（2）当且仅当n1n2?8(n1,n2?N)时，有n1?n2；

答：非自反的，因为1?1不成立，但1?N。对称的，非可传递的，因为1?10，10?2，但是1?2不成立。

（3）当且仅当r1?|r2|(r1,r2?R)时，有r1?r2。

答：自反的，非对称的，非可传递的，因为5?(?8)，?8?1，但是5?1不成立。

21、设?1和?2是集合A上的任意两个关系，判断下列命题是否正确，并说明理由：

（1）若?1和?2是自反的，则?1??2也是自反的；

答：正确。因为?1和?2是自反的，因此对任意a?A，有a?1a,a?2a，因此a?1?2a，所以?1??2也是自反的。

（2）若?1和?2是非自反的，则?1??2也是非自反的；

答：错误；例如A?{a,b,c}，?1?{(a,a),(b,b),(c,a)}，?2?{(a,a),(b,b),(a,c)}，

?1和?2都是非自反的，但是?1??2?{(a,a),(b,b),(c,c)}是自反的。

（3）若?1和?2是对称的，则?1??2也是对称的；

答：错误，设A?{a,b,c}，?1?{(a,b),(b,a)}，?2?{(a,c),(c,a)}，显然?1和?2是对称的，但是?1??2?{(b,c)}是非对称的。（4）若?1和?2是反对称的，则?1??2也是反对称的；

答：错误，设A?{a,b,c}，?1?{(a,b),(c,c)}，?2?{(b,c),(c,a)}，显然?1和?2是反对称的，但是?1??2?{(a,c),(c,a)}不是对称的。（5）若?1和?2是可传递的，则?1??2也是可传递的；

答：错误，设A?{a,b,c}，?1?{(a,b),(b,c),(a,c)}，?2?{(b,c),(c,a),(b,a)}，显然?1?2是可传递的，但是?1??2?{(a,c),(a,a),(b,a)}却是不可传递的。

22、证明若?是对称的，则对任何整数k?1，?k也是对称的。

证明：数学归纳法，当k?2时，若(a,b)??2，则根据复合关系的定义，存在元素c，使得(a,c)??,(c,b)??，因为?是对称的，所以(c,a)??,(b,c)??，所以

(b,a)??2，因此?2是对称的，假设当n?k时成立，则当n?k?1时，若(a,b)??k?1，则存在元素c1，使得(a,c1)??k,(c1,b)??，因为?和?k是对称的，

因此(c1,a)??k,(b,c1)??，所以(b,a)??k?1，因此：

n?k?1 时成立，即得证。

23、已知A?{1,2,3,4}和定义在A上的关系??{(1,2),(4,3),(2,2),(2,1),(3,1)}，试证明?不是可传递的。求出一个关系?1??，使得?1是可传递的，你能求出另一个关系?2??也是可传递的嘛？

答：证明：?显然不是可传递的，因为(1,2)??，(2,1)??，但是(1,1)??。

?1?{(1,2),(4,3),(2,2),(2,1),(3,1),(1,1),(4,1),(4,2)}，能找出另一个关系。

?1?{(1,2),(4,3),(2,2),(2,1),(3,1),(1,1),(4,1),(4,2),(3,3)}。

24、图2-10表示在{1,2,3}上的12个关系的关系图。试对每一个这样的图，确定其表示的关系是自反的还是非自反的；是对称，非对称还是反对称；是可传递的还是不可传递的？答：

自反的、非对称的、非反对称的，非可传递的

自反的、对称的，非反对称的、可传递的

非自反的、非对称的、反对称的、可传递的

自反的、非对称的、反对称的、可传递的

25、图2-11给出了{1,2,3}上的两个关系的关系图，这些关系是等价的吗？答：

(a) (b)

答：图(a)表示的关系??{(1,1),(2,2),(3,3),(1,2),(2,1),(1,3),(3,1)}具有自反性，对称性，但是不具有传递性，因为有(2,1),(1,3)??，但是(2,3)??，因此不是等价关系。

图(b)表示的关系??{(1,1),(2,2),(3,3),(1,2),(2,1)}，具有自反性，对称性，传递性，因此是等价关系。

26、在N上的关系?定义为当且仅当ni/nj可以用形式2m表示时，有ni?nj，这里m是任意整数： (1)证明?是等价关系

证明：对?n?N，n/n?1?20，因此n?n，所以关系?具有自反性。

对i,j?N，若i?j，即存在m，使得i/j?2m，则有j/i?2?m，因此有j?i。所以关系?具有对称性。

对i,j,k?N，若i?j，且j?k，即存在m1,m2，使得i/j?2m1，j/k?2m2，则i/k?2m1?m2，因此有i?k，所以关系?具有传递性。综上可得关系?是等价关系。 (2) 找出?的所有等价类

答：

[1]??{1,2,4,8,16,}?{2k,k?0,1,2,3,4,}

[3]??{3,6,12,24,}?{3?2k,k?0,1,2,3,4,}

[5]??{5,10,20,40,}?{5?2k,k?0,1,2,3,4,}

N???{[1]?,[3]?,[5]?,,[2k?1]?}

27、有人说，集合A上的关系?，如果是对称的且可传递的，则它也是自反的，

其理由是，从ai?aj，由对称性得aj?ai，再由可传递性便得ai?ai。

答：这种说法是错误的。例如，A?{1,2,3}，??{(1,2),(2,1),(1,1)}，显然?是对称的，且?是可传递的，但是它不是自反的。

28、设有集合A和A上的关系?，对于所有的ai,aj,ak?A，若由ai?aj和aj?ak可推得ak?ai，则称关系?是循环的，试证明当且仅当?是等价关系时，?是自反且循环的。证明：先证充分性

若?是等价关系，则?是自反的，对称的，可传递的。对于所有的ai,aj,ak?A，若ai?aj且aj?ak，则ai?ak，由对称性则有ak?ai，因此关系?是循环的。再证必要性

若对于所有的ai,aj,ak?A，若有ai?aj，又由自反性，有aj?aj，则由?是循环的，可得aj?ai成立，即?具有对称性。

若对于所有的ai,aj,ak?A，若由ai?aj和aj?ak，由?是循环的有ak?ai，由对称性可得ai?ak，因此?具有可传递性。又由?是自反的，则?是等价的。

A29、设?1和?2是A上的等价关系，试证明：当且仅当??中的每一等价类都包含1A于??的某一等价类中时，有?1??2。 2证明：先证充分性

AA设??中的每一个等价类都包含于对任一(ai,aj)??1，有??2的某一个等价类中，1ai?1aj，因此ai?[ai]?1,aj?[ai]?1。又由假设必有某元素b?A存在，使得[ai]?1?[b]?2，因此有ai?[b]?2，aj?[b]?2，所以(ai,aj)??2，故有?1??2。

再证必要性：

A设?1??2，并设[ai]?1是??中任一等价类，对任一x?[ai]?1，有ai?1x，即1(ai,x)??1，由假设(ai,x)??2，即x?[ai]?2，故有[ai]?1?[ai]?2。

30、已知?1和?2是集合A上分别有秩r1和r2的等价关系，试证明?1??2也是A上的等价关系，它的秩最多为r1r2，再证明?1??2不一定是A上的等价关系。证明：由交集的定义?1??2?{(a,b)|(a,b)??1且(a,b)??2}

对于?a?A，因为?1,?2都是自反的，所以(a,a)??1，且(a,a)??2，因为

(a,a)??1??2，所以?1??2是自反的。

对于?a,b?A，若(a,b)??1??2，则(a,b)??1，(a,b)??2，由?1和?2的对称性知(b,a)??1，且(b,a)??2，因而有(b,a)??1??2，故?1??2是对称的。

对于?a,b,c?A，若(a,b)??1??2，(b,c)??1??2，则有(a,b)??1，(b,c)??1，

(a,b)??2，(b,c)??2，由?1,?2的传递性知(a,c)??1，(a,c)??2，因而(a,c)??1??2，故?1??2是可传递的。所以?1??2也是A上的等价关系。

对于?1??2，由并集的定义知?1??2?{(a,b)|(a,b)??1或者(a,b)??2} 对于?a?A，因为?1是自反的，所以(a,a)??1，因而(a,a)??1??2，所以?1??2是自反的。对于?a,b?A，若(a,b)??1??2，则(a,b)??1或者(a,b)??2，由于

?1和?2都是对称的，因此有(b,a)??1或者(b,a)??2，因而有(b,a)??1??2，故?1??2也是对称的。

对于任意的a,b,c?A，若(a,b)??1??2，(b,c)??1??2，则(a,b)??1或者

(a,b)??2；(b,c)??1或者(b,c)??2，因为(a,b)和(b,c)不一定能同时属于?1，

也不一定能同时属于?2，所以无法推出(a,c)??1或者(a,c)??2，因而也就无法推出(a,c)??1??2，这说明?1??2的可传递性不一定能成立，因此推不出

?1??2是A上的等价关系。

,(1,3),(3,1)}反例：设A?{1,2,，3A上的关系?1?{(1,1),(2,2),(3,3)，

?2?{(1,1),(2,2),(3,3),(1,2),(2,1)}，显然?1和?2均是等价关系。

?1??2?{(1,1),(2,2),(3,3),(1,3),(3,1),(1,2),(2,1)}，这里?1??2是自反的，对称的，但是不可传递的。

31、设?1是集合A上的一个关系，?2?{(a,b)|存在c,使(a,c)??1且(c,b)??1}。试证明：若?1是一个等价关系，则?2也是一个等价关系。

证明：因为?1是自反的，因此对?a?A，有(a,a)??1，由(a,a)??1，因此有(a,a)??2，故?2是自反的。

对于任意的a,b?A，若(a,b)??2，则必有元素c?A，使得(a,c)??1且

(c,b)??1，由?1的对称性又有(b,c)??1且(c,a)??1，因而有(b,a)??2，故?2是

对称的。

对任意的a,b,c?A，若(a,b)??2，(b,c)??2，则必有元素d,e?A，使得：

(a,d)??1,(d,b)??1 (b,e)??1,(e,c)??1

由?1的可传递性，又有(a,b)??1，(b,c)??2，于是又有(a,c)??2，故?2是可传递的。

由上得证?2是一个等价关系。

32、设A是由4个元素组成的集合，试问在A上可以定义多少个不同的等价关系？

答：根据等价关系与分划一一对应，将A分划为一块：有一种方法，将A分划为

1两块：2+2方式有1/2C42种，1+3方式有C4种

将A分划为三块：只能是1+1+2方式，有C42种将A分划为四块：有一种方法

因此集合A上不同等价关系的个数为15种。

33、设?1和?2是集合A上的等价关系，下列各式哪些是A上的等价关系？为什么？ (1)(A?A)??1

答：不是等价关系，因为不具有自反性 (2) ?1??2

答：不是等价关系，因为不具有自反性 (3) ?12

答：是等价关系，证明如下：?1是自反的，?12显然也是自反的。若(a,b)??12，则有复合关系的定义，存在c?A，使得(a,c)??1，(c,b)??1，由?1的对称性有

(c,a)??1，(b,c)??1，由复合关系的定义有(b,a)??12，因此?12是对称的。若(a,b),(b,c)??12，由复合关系的定义，? d?A,(a,d)??1,(d,b)??1?e?A,(b,e)??1,(e,c)??1

d ) ??由对称性， ( d , a ) ? ? 1,( b , ? 1 ( b ,a ) ? ? 1 ，

(e,b)??1,(c,e)??1?(c,b)??1

所以(c,a)??12，由?12的对称性，(a,c)??12，因此?12具有传递性。因此?12是A上的等价关系。 (4)r(?1??2)

?2?{(1,1),(2,2),(3,3),(2,3),(3,2)}，答：不一定是A上的等价关系。例如A?{1,2,3}，?1为A上的普遍关系，则r(?1??2)?{(1,1),(2,2),(3,3),(1,2),(2,1),(1,3),(3,1)}不具有传递性，因为(2,1),(1,3)?r(?1??2)，但是(2,3)?r(?1??2)。

34、对于下列集合中的’整除’关系，画出次序图： (1) {1,2,3,4,6,8,12,24} 答：

(2) {1,2,3,4,5,6,7,8,9,10,11,12} 答：

35、对于下列集合，画出偏序关系’整除’的次序图，并指出哪些是全序 (1){2,6,24} 答：是全序 (2){3,5,15} 答：非全序 (3){1,2,3,6,12} 答：非全序 (4){2,4,8,16} 答：

是全序 (5) {3,9,27,54} 答：是全序

36、如果?是集合A中的偏序关系，且B?A，试证明：??(B?B)是B上的偏序关系。

证明：对任意的a?B，必有(a,a)?B?B，又因为a?A及?的自反性，所以

(a,a)??，因此(a,a)???(B?B)，故??(B?B)是自反的。

对任意的a,b?B，若(a,b)???(B?B)，且(b,a)???(B?B)，则有(a,b)??，且(b,a)??，由?的反对称性，有a?b，因此??(B?B)是反对称的。对任意的a,b,c?B，若(a,b)???(B?B)，(b,c)???(B?B)，则(a,b)??，且

(b,c)??，由?的可传递性必有(a,c)??，由B?B的定义，(a,c)?B?B，于是(a,c)???(B?B)，因此??(B?B)是可传递的，由上得证??(B?B)是B上的

偏序关系。

37、给出一个集合A的例子，使得包含关系?是幂集2A上的一个全序。答：A?{1,2,3}，2A?{?,{1},{2},{3},{1,2},{2,3},{1,3},{1,2,3}}

2A上的关系??{?,{1},{1,2},{1,2,3}}。

38、给出一个关系，使它既是某一集合上的偏序关系又是等价关系

答：A?{1,2,3}，??{(1,1),(2,2),(3,3)}，显然?具有自反性，对称性，可传递性，还具有反对称性，因此既是A上的；偏序关系，也是等价关系。

39、图2-12表示{1,2,3,4}上的四个偏序关系图。画出每一个的次序图，并指出其中哪些是全序，哪些是良序答：

(a)

??{(1,1),(2,2),(3,3),(4,4),(1,2),(3,2),(3,1),(3,4),(1,4)} 不是全序，也不是良序

(b)

??{(1,1),(2,2),(3,3),(4,4),(1,3),(2,3),(1,4),(2,4)}不是全序也不是良序

(c)

??{(1,1),(2,2),(3,3),(4,4),(3,1),(1,2),(3,2),(1,4),(3,4),(4,2)} 是全序也是良序

(d)

??{(1,1),(2,2),(3,3),(4,4),(3,1),(4,3),(4,1),(4,2)}非全序，也不是良序。

40、一个集合上的自反和对称关的关系称为相容关系

(1) 设A是人的集合，?是集合A上的关系，定义为当且仅当a是b的朋友时，有a?b，试证明?是A上的相容关系。

证明：对?a?A，因为任何的人都是自己的朋友，也就是有a?a，因此?具有自反性，若a?b，也就是a是b的朋友，那么一定有b是a的朋友，则有b?a，因此?是对称的，因此?是A上的相容关系。

(2) ?是正整数集N上的关系，当且仅当两个正整数n1和n2中有相同的数字时，

n1?n2 ，试证明?是一个相容关系；

证明：显然，对?n?N，有n?n，因此?具有自反性；若n1?n2，则表示n1和n2中有相同的数字，因此n2和n1也有相同的数字，因此n2?n1。所以?具有对称性，所以?是N上的一个相容关系。 (3) 再举出一个相容关系的例子

答：等价关系都是相容关系，反之则不成立。

(4) 设?1和?2是A上的两个相容关系，?1??2是相容关系吗？?1??2是相容关系吗？

答：?1??2和?1??2都是相容关系，前题30中证明了若?1和?2是A上的等价关系，则?1??2也是等价关系，而?1??2具有自反性和对称性。

第3章函数

1. 以下关系中哪一个构成函数？ (1) {(n1,n2)|n1,n2?N,n1?n2?10}

答：不构成函数。象的唯一性不能满足，因为(1,2),(1,3)都属于这个集合。而12,13等这样的数在N中无像，所以象的存在性也不能满足。 (2) {(n1,n2)|n1,n2?N,n2?小于n1的素数的个数} 答：是函数，象的唯一性和存在性都能满足。

2. 设A?2U?2U，B?2U，给定由A到B的关系：

S,1?S|1S,? f?{(( U}1,S2)S2)S2f是函数吗？若是的话，f的值域Rf?2U吗？为什么？

答：f是函数。f的值域Rf?2U。因为对?C?2U，则C?U，则对(C,C)，

C?C?C，因此象C的像源为(C,C)。

3. 下列集合能够定义函数吗？如果能，试指出它们的定义域和值域？ (1) {(1,(2,3)),(2,(3,4)),(3,(1,4)),(4,(1,4))}

答：能定义函数。Df?{1,2,3,4}，Rf?{(2,3),(3,4),(1,4)} (2) {(1,(2,3)),(2,(3,4)),(3,(3,2))}

答：能定义函数。Df?{1,2,3}，Rf?{(2,3),(3,4),(3,2)} (3) {(1,(2,3)),(2,(3,4)),(1,(2,4))}

答：不能定义函数。因为有一对多的情况。 (4) {(1,(2,3)),(2,(2,3)),(3,(2,3))}

答：能定义函数。Df?{1,2,3}，Rf?{(2,3)}

4. 设函数f:A?B,S?A，等式f(A)?f(S)?f(A?S)成立吗？为什么？答：不成立。因为f(A)?f(S)?f(A?S)成立，但是f(A?S)?f(A)?f(S)不成立。下面证明f(A)?f(S)?f(A?S)。

设b?f(A)?f(S)，则b?f(A)且b?f(S)，所以必存在a?A使f(a)?b。由于所以a?S，于是a?A?S，因此b?f(A?S)，故fAb?f(S)，()f?S()f?A(S)?f(A?S)?f(A)?f(S)不成立，反例如下：

。

设A?{a1,a2,a3,a4}，S?{a2,a3}，则A?S?{a1,a4}，函数f:A?B的定义为：

f?{(a1,b1),(a2,b1),(a3,b2),(a4,b3)}。显然f(A)?{b,2b,3b，}f(S)?{b1,b2}，1f(A?S)?{b1,b3}，f(A)?f(S)?{b3}，f(A?S)?f(A)?f(S)。由上可知f(A)?f(S)?f(A?S)不成立。

5 设有函数f:A?B，试证明等式f(A?B)?f(A)?f(B)，等式?Cf(A?B)?f(A)? f(成立吗？为什么？B)证明：设c?f(A)?f(B)，则c?f(A)或者c?f(B)。若c?f(A)，则存在a?A使得f(a)?c，因此有a?A?B，所以c?f(A?B)。若c?f(B)，类似地，有

c?f(A?B)，故f(A)?f(B)?f(A?B)。

反之，若c?f(A?B)，则存在b?A?B，使得f(b)?c。由并集的定义b?A或者b?B，因此c?f(A)或者c?f(B)，于是c?f(f(A?B)?f(A)?A)?f(，B)故

。由上得证f(Bf(A?B)?f(A)?f(B)。

f(A?B)?f(A)?f(B)不成立，因为f(A?B)?f(A)?f(B)，反之不成立。

证明：设c?f(A?B)，则存在a?A?B使得f(a)?c。因为a?A且a?B，所以c?f(A)且c?f(B)，因此c?f(A)?f(B)，故f(A?B)?f(A)?f(B)。反例如下：

设A?B?{a,b,e,d}，其中A?{a,e,d}，B?{b,e}，C?{c1,c2,c3}，函数于是：A?B?{e}，f:A?B?C定义为f(a)?f(b)?c1，f(e)?c2，f(d)?c3，

f(A?B)?{c2}，f(A)?{c1,c2,c3}，f(B)?{c1,c2}，f(A)?f(B)?{c1,c2}，这里

元素c1?f(A)?f(B)，但是c1?f(A?B)。

6. 设有函数f:A?B和g:B?C，使得g?f是一个内射，且f是满射。证明g是一个内射。举出一个例子说明，若f不是满射，则g不一定是内射。证明：任取b1,b2?B，并设b1?b2。因为f是满射，所以必有a1,a2?A，使得

f(a1)?b1，f(a2)?b2，根据函数象的唯一性的条件，由b1?b2可得a1?a2。又

因为g是由B到C的函数，所以有c1,c2?C，使得g(b1)?c1，。于是根据复合函数的定义，得：

a)?g(1b)?， g?f(11cg?f(a2)?g(b2)?c2

因为g?f是内射，所以由a1?a2，可知c1?c2。此即g(b1)?g(b2)，故g是内射。例子：

图3-1

图3-1中的例子可说明当f不是满射时，g不一定是内射。

7. 在下列函数中，确定哪些是内射，哪些是满射，哪些是双射。 (1) f1:N?Z,f1(n)?小于n的完全平方数的个数；

答：f1(2)?1,f2(3)?1，因此f1不是内射，是满射，因此不是双射。 (2) f2:R?R,f2(r)?2r?15; 答：是内射，是满射，因此是双射 (3) f3:R?R,f3(r)?r2?2r?15

答：因为f3(?5)?f3(3)?0，所以不是内射，f3(r)?(r?1)2?16。显然对于任意的r?R，f3(r)??16。因此不是满射，因此不是双射。 (4) f4:N2?N,f4(n1,n2)?n1n2

答：因为f4(4,1)?f4(2,2)?41?22?4，所以f4不是内射。

对于任意的n?N，有f4(n,1)?n1?n。即对于任意的n?N，n有像源(n,1)，所以f4是满射，但是不是双射。 (5) f5:N?R,f5(n)?log10n

答：因为n?N，所以n?1，因此log10n?0，因此不是满射。是内射(函数的单调性)。因此不是双射。

(6) f6:N?Z,f6(n)?等于或大于log10n的最小整数；

答：因为f6(3)?1,f6(4)?1，因此不是内射是满射。因此不是双射。(Z是非负整数集合)

(7)f7:(2U)2?(2U)2，f(S1,S2)?(S1?S2,S1?S2)

答：对任意S1,S2?2U,S1?S2，(S1,S2)?(S2,S1)，但是f(S1,S2)?f(S2,S1)，因此不是内射。又(?,U)?(2U)2，但是找不到S1?2U,S2?2U，使得S1?S2??，

S1?S2?U。

因此不是满射，因此也不是双射。

8. 设A,B都是有限集，#A?n,#B?m，问存在着多少个不同的内射f:A?B？存在多少个不同的双射？

答：若要使得函数f:A?B成为内射，必须满足#A?#B，即n?m，否则由Am!n?到B不可能存在内射。当n?m时，由A到B可定义Am个不同的内射。(m?n)!此即为从B的m个元素中取出n个元素的排列数。要使函数f:A?B成为双射，必须满足#A?#B，即n?m。否则，由A?B不可能存在双射。当n?m时，

m?m!个不同的双射。由A到B可定义Am

9. 下列函数中，确定哪些是内射，哪些是满射，哪些是双射。

ii是偶数?2(1) f1:I?I，f1(i)??

?(i?1)/2i是奇数答：因为f1(2)?1,f1(3)?1，因此不是内射。是满射，因此不是双射。 (2) f2:Z7?Z7,f2(x)?res7(3x)

答：res7(3x)表示3x被7除后的非负余数，于是按照函数f2的定义，得：

f2(0)?0,f2(1)?3,f2(2)?6,f2(3)?2,f2(3)?5,f2(4)?5,f2(5)?1,f2(6)?4

显然f2又是内射，又是满射，因此是双射。 (3) f3:Z6?Z6,f3(x)?res6(3x)

答：f3(0)?res6(0)?0，f3(1)?res6(3)?3，f3(2)?res6(6)?0，f3(3)?res6(9)?3，

f3(4)?res6(12)?0，f3(5)?res6(15)?3。因此f3不是内射不是满射，因此也不

是双射。

10. 设A?{a1,a2,,an}，试证明任何从A到A的函数，如果它是内射，则它必

是满射，反之亦真。

答：反证法。已知f:A?A是内射，假设f不是满射，则在A中至少有一个元素没有像源，即集合A中的元素至多只有n?1个像。但是#(A)?n，因此A中至少有两个元素对应同一个像，这与f是内射相矛盾。

反之，已知f:A?A是满射，假设f不是内射，则A中至少有两个元素对应同一个像，即A在A中至多有n?1个像，这与f是满射矛盾，所以f是内射。

11. 设有函数f:A?B，定义函数g:B?2A，使得： g(b)?{x|x?A,f(x?) b试证明如果f是满射，则g是内射；其逆成立吗？

答：设b1,b2?B，b1?b2，因为f是满射，存在x?A，使得f(x)?b1?b2，因此

x?g(b1)，x?g(b2)，因此g(b1)?g(b2)，因此g是内射。其逆不成立。因为当g是内射时，可能有一个元素b，使g(b)??，这意味着元素b?B在A中没有像源，因此f不是满射。举例如下：A?{a1,a2,a3},B?{b1,b2,b3}，函数f和g的定义如下，此时g是内射，但是f不是满射。

图3-2

12. 设函数f:Z?Z?Z，g:Z?Z?Z。这里f(x,y)?x?y，g(x,y)?xy。试证明f和g是满射，但是都不是内射。

答：但是f(x,y)?f(y,x)?x?y，因此f不是内射。但是对?z?Z，(x,y)?(y,x)，有f(z,0)?z?0?z，因此f是满射。同理，(x,y)?(y,x)，但是

g(x,y?)g(y?,x)，因此xyg不是内射，但是对?z?Z，g(z,1)?z?1?z，因此g是满射。

13. 设有函数f:R?R和g:R?R，这里f(x)?x2?2和g(x)?x?4。求出f?g和g?f。并说明这些函数是否是内射，满射或双射。答：f?g?f(g(x))?f(x?4)?(x?4)2?2?x2?8x?14 g?f?g(f(x))?g(x2?2)?x2?2

因为(f?g)(0)?(f?g)(?8)，因此f?g不是内射，又因为(x?4)2?2??2，因此也不是满射。因此不是双射。g?f也不是内射，也不是满射，也不是双射。但是

g(x)?x?4是内射是满射，因此也是双射。f(x)?x2?2不是内射，不是满射，

因此也不是双射。

14. 设有函数f,g,h:R?R，给定为f(x)?x?2，g(x)?x?2，h(x)?3x。试求出g?f，f?g，f?f，f?h，h?g，f?h?g。答：g?f?g(f(x))?g(x?2)?x?2?2?x f?g?f(g()x)? xx?2?2?，

f?f?f(f(x))?f(x?2)?x?4，f?h?f(h(x))?f(3x)?3x?2 h?g?h(g(x))?h(x?2)?3x?6f?h?g?f(h(g(x)))?f(h(x?2))?f(3x?6)?3x?4

15．设A?{1,2,3,4}，定义一个函数f:A?A，使得f?IA，而且是双射，求

f2,f3,f?1，以及f?f?1。能否找到一个双射g:A?A，使得g?IA，但是g2?IA？

答：定义函数f:A?A，使得f(1)?2，f(2)?3，f(3)?4，f(4)?1，显然f?4,f2(3)?1,f2是双射且f?IA。函数f2:A?A,f2(1)?3,f2(2)(4)?；函数2f3:A?A，f3(1)?f2(f(1))?f2(2)?4，类似地f3(2)?1，f3(3)?2,f3(4)?3。

可定义函数g:A?A，使得g(1)?2，g(2)?1，g(3)?4,g(4)?3。显然g?IA，但g2?IA。

16. 设f:R?R，f(x)?x3?2，试求f?1。答：f?1(x)?3x?2

第7章格和布尔代数

1、下列各集合对于整除关系|都构成偏序集。在每个集合中对存在有最大下界和最小上界的元素对，找出它们的最大下界和最小上界；指出各集合中是否有最小元素和最大元素。

(1)L?{1,2,3,4,6,12} (2)L?{1,2,3,4,6,8,12,24} (3)L?{1,2,3,,12}

解：(1)偏序集的次序图如下：

4和6的最大下界为1，最小上界为12；

2和3的最大下界为1，最小上界为6； 3和6的最大下界为3，最小上界为6；该集合的最大元素为12，最小元素为1。 (2)偏序集的次序图如下：

该集合最小元素为1，最大元素为24。任何两个元素的最小

上界为它们的最小公倍数，最大下界为它们的最大公约数。 (3)偏序集的次序图如下：

该集合没有最大元，有最小元素为1。

2、试证明在格中若a?b?c，则有

a?b?b? c (a?b)?(b?c)?(a?b)?(b? c证明：(1)因为a?b，所以a?b?b，又因为b?c，所以b?c?b，所以有

a?b?b?c成立。

(2)因为a?b，所以a?b?a，a?b?b；又因为b?c，所以b?c?b，

b?c?c，所以(a?b)?(b?c)?a?b?b，(a?b)?(b?c)?b?c?b，所以有：

(a?b)?(b?c)?(a?b)?(b?c)成立。

3、试证明在格中对于任意元素a,b,c,d有(a?b)?(c?d)?(a?c)?(b?d) 证明：因为a?b?a，c?d?c，所以由格的保号性(a?b)?(c?d)?a?c

因为a?b?b，c?d?d，所以由格的保号性(a?b)?(c?d)?b?d 因此，(a?b)?(c?d)是a?c和b?d的下界，所以： (a?b)?(c?d)?(a?c)?(b?d)

4、在第一题中，哪一个偏序集构成格？

答：第1和第2个偏序集构成了格，因为该集合中任何两个元素都存在最大下界和最小上界。但是第3个集合中的元素则不满足这个条件。

5、下图给出了三个偏序集的次序图，其中哪些构成格？

不是格，因为最下层两个元素没有下确界。

(a)

(b) 是格，因为任何两个元素都有下确界和上确界。

不是格，因为最上层两个元素没有上确界。

6、设?L,?,??是格，试证明对于所有的a,b,c?L，则有：

(a?b)?(a?(b?c))?b?(a?c))

证明：根据格的分配律，我们有 a?(b?c)?(a?b)?(a? c) 因为a?b，所以a?b?b，所以(a?(b?c))?b?(a?c))。

7、设?L,?,??是一个格，如果对于所有的a,b,c?L，有 (a?b)?(a?(b?c))?b?(a?c))

则称?L,?,??是模式格，下图所给出的格是模式格吗？证明你的结论。

解：不是模式格，因为对于b,d,c这三个元素，b?d，但是b?(d?c)?b?a?b，

而d?(b?c)?d?e?d，并不满足模式格的要求，因此不是模式格。

8、证明具有两个或更多个元素的格中，不会有元素是它自身的补。

证明：因在格中求补元，此格必为有界格，设?L,??为有界格，若#(L)?2，则

L?{0,1}。因为0?0?0,0?0?0,1?1?1,1?1?1,0?1?0,0?1?1，因此0和

1互为补元，即具有两个元素的格中不存在以自身为补元的元素。若#(L)?2，设存在l?L，l?0且l?1，若l以自身为补元，则由补元的定义：

l?l?0?l?l?l?1，可得l?0?1，与假设矛盾。因此不存在以自身为补元的元素。

9、设?L;?,??是一个格，#(L)?1，试证明如果?L;?,??有元素1和元素0，

则这两个元素必定是不相同的。

证明：反证，假设这两个元素是相同的，并记l?0?1，则根据最大元素和最小

元素的定义，我们有对?l1?L，0?l?l1?l?1，则l?l1，因此#(L)?1，这

与条件矛盾。

10、举例说明并非每一有补格都是分配格；并非每个分配格都是有补格。解：由下图(a)表示的格由于元素z无补元，因此不是有补格；但是对任意三个元

素都满足分配等式，因此是分配格。

(a)

下图(b)表示的格中，0和1互为补元， x,y两两互补，因此是有补格。又因为x?(y?z)?x?1?x，(x?y)?(x?z)?0?0?0，即

x?(y?z)?(x?y)?(x?z)

所以不是分配格。

(b)

11、设?L,??是一个格，a,b?L，且a?b(即a?b，但是a?b)，令集合

La? B?{x|x?且证明?B,??也是一个格。

x?} bl1?l2?lub(l1,l2)。，

l2?b(gl,l)证明：因为?L,??是格，所以对任意l1,l2?L，有l1?1l2由B的定义知B?L，a?B，所以B??。对任意x,y?B，由于?L,??是格，所以x?y和x?y在L中存在且唯一。下证x?y?B,x?y?B。

由B的定义知a?x?b，a?y?b。所以a?x且a?y，根据格的保号性及

等幂性有a?a?a?x?y，所以a?x?y。类似地，x?b,y?b得x?y?b，所以

a?x?y?，即bx?y?B。类似地可证明a?x?y?b，即x?y?B。

12、设?L;??是一个格，试证明对于任意的元素a,b,c?L，有下列命题成立： (1) 若a?b?a?b，则a?b

(2) 若a?b?c?a?b?c，则a?b?c (3) a?[(a?b)?(a?c)]?(a?b)?(a?c)

证明：(1) 因为a?a?b?a?b?a，所以a?a?b，同理有b?a?b，因此a?b。

a?a?b?c?a?b?c?a (2) 因为b?a?b?c?a?b?c?b，所以a?b?c?a?b?c?a?b?c。

c?a?b?c?a?b?c?c (3) 由格的分配律

a?[(a?b)?(a?c)]?(a?(a?b))?(a?(a?c))?(a?b)?(a?c)

又因为a?[(a?b)?(a?c)]为(a?b)?(a?c)和a的上确界，因此

a?[(a?b)?(a?c)]?(a?b)?(a?c)

因此得证。

13、设a和b是格?L;??中的两个元素，试证明当且仅当a,b不可比时，。 a?b?a,a?b?b证明：必要性：(反证)已知 a,b不可比，因为一定有a?b?a，所以若a?b?a，

则a?b，因此a,b可比，因此矛盾。

充分性：(反证)假设a,b可比，则由格的性质，a?b?a且a?b?b，矛盾。

14、设集合A?{a,b,c}，集合A上所有分划所构成的集合为P(A)，你能否适当定义P(A)上一个偏序关系?,使得?P(A);??成为一个格？

解：记P(A)?{?i}，其中?i为A的一种分划，定义P(A)上的偏序关系为，若分

划?i是?j的一个细分，则?i??j。显然有，对任意?i?P(A)，?i??i因此具有自反性；若?i??j,?j??i，则?i??j因此具有反对称性；若?i??j,?j??k，则?i??k(根据细分的定义很容易得出)，所以具有可传递性，因此是偏序关

?1?{{a},{b},{c}},?2?{{a,b},{c}}系。A?{a,b,c}中3个元素，共5种：?3?{{a},{b,c}},?4?{{a,c},{b}}

?5?{{a,b,c}} 则对定义二元运算?i??j??i(若?i??j)，?i??j??1(若?i和?j不可比) ?i??j??(j若?i??j)，?i??j??5(若?i和?j不可比) 可以画出该偏序关系的次序图如下：

显然定义的偏序关系是格。

15、试证明在格中对任意元素a,b,c，有

(a?b)?(b?c)?(c?a)?(a?b)?(b?c)?(c?a)

证明:因为a?b?a，b?c?b，c?a?a，所以(a?b)?(b?c)?a?b， (( a?b)?(b?c)?)c(?a)?a(?b?)a?，所以可得：a?b (a?b)?(b?c)?(c?a)?a， ?同理有：b (a?b)?(b?c)?(c?a)?b?，和c(a?b)?(b?c)?(c?a)?a?c 所以(a?b)?(b?c)?(c?a)?(a?b)?(b?c)?(a?c)成立。

16、试证明在格中对于任意元素a,b,c?L，有：

(a?b)?(b?c)?(c?a)?(a?b)?(b?c)?(c?a)

时，格?L,??是分配格。

证明：必要性：设?L,??是分配格，则对于任意a,b,c?L有：

(a?b)?(b?c)?(c?a)?[(a?b)?(b?c)?c)?][a(?b?)b(?c?a?[(a?b)?c]?[b(?c)?a]

?(a?c)?(b?c)?(b?a)?(c?a)?(a?b)?(b?c)?(c?a)充分性：对于任意a,b,c?L，令a??(a?b)?(a?c)，b??b?c，c??a，则

a?,b?,c??L满足等式：

(a??b?)?(b??c?)?(c??a?)?(a??b?)?(b??c?)?(c??a?) (1)

于是式(1)的左边

?[((a?b)?(a?c))?(b?c)]?[(b?c)?a]?a?[(a?b)?(b?c)?(c?a)]?a左边

?[(a?b)?(b?c)?(c?a)]?a?(b?c)?a因为a?a?b，a?a?c，故a?(a?b)?(a?c) 所以a?[(a?b)?(a?c)]?(a?b)?(a?c)。将a?,b?,c?带入(1)的右边得

?[((a?b)?(a?c))?(b?c)]?[(b?c)?a]?[a?((a?b)?(a?c))]?([((a?b)?(a?c))?(b?c)]?[(a?b)?(a?c)])?[(b?c)?a]右边?[(a?b)?(a?c)]?[(a?c)?b]?(a?b)?[(a?c)?((a?c)?b]?(a?b)?(a?c)所以有a?(b?c)?(a?b)?(a?c)。因此是分配格。

第8章图论

1、图1所示之图是否同构于图2

图1 图2

h(v5)?u6,h(v6)?u5，显然h是双射且满足同构的定义。

答：根据点和边的关联关系，构造h:V1?V2,h(vi)?ui,i?1,2,3,4，

2、图3中所给出的两个8结点图是否同构？证明你的回答

图3(a) 图3(b) 答：上述两个图不同构。

证明：因为图3(b)中4个度数为3的结点中每一个均与另外两个度数为3的结点相邻，而图3(a)中的每个度数为3的结点只与另外一个度数为3的结点相邻，所以不同构。

3、证明在任何图中奇次度结点的个数是偶数。

证明：反证，假设图G中存在奇数个奇次度结点，则图中不论偶次度结点的个数是奇数还是偶数，该图的结点总度数为偶数，但是任何图的所有结点度的总和又为边数的两倍，因此必为偶数，矛盾！

4、设G是具有4个结点的完全图，试问： (1)G有多少个子图？ (2)G 有多少个生成子图？

(3)如果没有任何两个子图是同构的，则G的子图个数是多少？请将这些子图构造出来？

12?2个，含有三答：(1)含有一个结点的子图有C4个，含有两个结点的子图有C434?8个，含有4个结点的子图有C4?64个，所以共有112个个结点的子图有C4子图。

(2) G的生成子图包含G的所有结点，因为G有6条边，构成子图时，每条边有被选和不被选择两种情况，因此G生成的子图为26=64种。 (3)G的所有不同构的子图如下：共18个。

5、在图4中找出其所有的真路和环，该图是否包含有割边？

图4

解：真路：v1v2v5cv3v6等。环：v1v2v5v4v1等。其中{v3,v4}是割边，因为该条边不在G的任何环中出现。

6、图G的邻接矩阵为：

?00110?0?00001?1???10000?0 A???

?10000?0?01000?1??01001??0给出，G是否是连通的？

解：直接由邻接矩阵给出图G的一个图解，如下图所示，显然G是不连通的。

7、求下图中图(a)和图(b)的全部断集：

(a)

(b)

S6?{a,e,f,c}，S7?{b,d,e,f}都是边割集。

解：对于图(a)S1?{a,f,d}，S2?{a,e,b}，S3?{b,c,f}，S4?{c,f,d}，S5?{g}，对于图(b)S1?{a,b}，S2?{f,g}，S3?{c,d,e}，S4?{a,c,d,f}都是边割集。

8、证明图G的任一生成树和任一边割集至少有一条公共边。

证明：设图G中若有一个边割S与G的一棵生成树T没有公共边，那么删去S后所得子图G?S必包含T，这意味着G?S仍连通，与S是边割集矛盾，所以一定

有S与T至少有一条公共边，

9、试作出一个连通图G，使之满足等式K(G)??(G)??(G)。解：

上图中由定义可得K(G)??(G)??(G)?2

10、设图G中各结点的度都是3，且结点数n与边数m间有如下关系 2n?3?m 问(1) G中结点数与边数各为多少？ (2) 在同构的意义下G是唯一的吗？

解：(1) 由题知该图的总度数为3n，由握手定理知边数与度数的关系为2m?3n，又由2n?3?m，可以解出边数m?9，结点数n?6。

(2) 在同构的意义下图G不唯一，见第一节的例8中图(b)和图(c)。

11、若图G的补图同构于G，则称G为自补图。试证明下图所示的图是自补图。你能否找到其他5结点的自补图。

证明：上图的补图为

图G与其补图的结点集合之间可以建立一一对应关系，因此两个图是同构的。

12、已知关于人员a,b,c,d,e,f,g的下述事实：

a说英语；b说英语和西班牙语；c说英语、意大利语和俄语；d说日语和西班

牙语；e说德语和意大利语；f说法语、日语和俄语；g说法语和德语，试问上述7人中是否任意两个人都能交谈？如有必要，可由其余5人中所组成的译员链帮忙？

解：设7个人为7个结点，将两个懂同一种语言的人之间连成一条边，即表示他们能直接交谈。这样就得到一个简单图G，问题就转化为G是否连通，G如下图所示，因为G中任意两个结点是连接的，所以G是连通图。因此，上述7个人中任意两个能交谈。

13、试从下图中找出一条欧拉回路：

解：agbhiljklfejcdecba

14、试在下图中找出一条欧拉路：

解：haghbgfecdfcbah。

15、判断下面4个图哪个是欧拉图，哪个是哈密顿图，在各适当情况下指出欧拉回路和哈密顿环。

(a)

解：图(a)是欧拉图，存在一条欧拉回路为abfcbgcdhgfea；图(a)是哈密顿图，存在一个哈密顿环abcdhgfea。

(b)

解：图(b)是欧拉图，具有一条欧拉回路abecfbdca，不是哈密顿图。

(c)

解：图(c)不是欧拉图，是哈密顿图，存在一个哈密顿环abcdhgfea。

(d)

解：图(d)不是欧拉图，也不是哈密顿图。

16、构造下图中图G的闭包，并判断G是否为哈密顿图？如果不用观察的方法，你能说出你判别的根据嘛？

解：先求图G的闭包n=6。因为deg(v5)?deg(v6)?6；deg(v2)?deg(v3)?6，所以连接v5与v6，v2与v3得图G1：

deg(v2)?deg(v4)?6,

因此，连接v2与v4，v1与v5，v4与v6，v1与

在图G1中，因为

deg(v1)?deg(v5)?6,deg(v4)?deg(v6)?6,deg(v1)?deg(v3)?6,v3的图G2：

在图G2 中，因为deg(v1)?deg(v4)?8，因此连接v1与v4得图G3：

且G3是G的闭包，因此G是哈密顿图。

17、某流动售货员居住在a城，打算走销b,c,d城后返回a城。若该四城间的距

离如下图所示，试找出完成该旅行的最短路线。

解：本题要求售货员将4个城市走且仅走一次，形成一个哈密顿环，并使得所走的路线最短。因此满足条件的走法应该是a?b?d?c?a。

18、构造互不同构的所有6结点的树。

解：先画出6个顶点，然后分别考虑顶点的度数最大为2,3,4,5的情况，不同构的树有5个，如下图所示：

19、试证明当且仅当图G中得每一条边均为割边时，图G是树林。

证明：设连通图G的每条边都是割边，则去掉任一条边后得到的子图不连通，这说明G中没有回路，根据树的定义知，G是一棵树。反之，若G是一棵树，根据树的性质，去掉任一条边后就不连通了，所以G的每条边都是割边。

20、证明或反驳下一结论：连通图G的任一边为G的某一生成树的弦。

解：若连通图G含有割边，则e为任何生成树的弦；

若G不含割边，那么对G的任一边e?，e?一定在某个环路?上，用破圈法构成生成树TG时，可在?中删去e?，相对生成树TG，e?一定是弦。

因此该结论当G不含割边时才成立。

21、试证明具有m条边的连通图最多具有m?1个结点。

证明：数学归纳法当m?1时，显然一条边且连通，则只能有两个点，即n?2；假设当m?k时，点数n?k?1，则当m?k?1时，增加的一条边由于连通所以一定去某点相邻接的，因此最多增加一个点，所以点数n?k?2，所以由数学归纳法结论成立。

22、n个结点的完全图的环秩是多少？

n(n?1)22解：n个结点的完全图的边数为 C n ? ，因此其环秩为Cn?(n?1)。

23、一棵树有5个度为2的结点，3个度为3的结点，4个度为4的结点，2个度为5的结点，其余均为度为1的结点，问它有几个度为1的结点？解：设有n个度为1的结点，则总的度数为n+10+9+16+10=n+45

根据树的定义，一棵树的边数等于点数减去1，而总度数又等于边数的两倍，因此有

(n+45)/2=5+3+4+2+n-1=13+n 解得： n=19

Word文档下载：洪帆《离散数学基础》（第三版）课后习题答案.doc

搜索更多:洪帆《离散数学基础》（第三版）课后习题答案