离散数学(第三版)课后习题答案 下载本文

精品文档

2){2,3,6,12,24,36}

3){1,2,3,4,5,6,7,8,9,10,11,12} [解]

24

4

3 2 1 12

6 2

3 36

1)的Hasse图 2)的Hass图

在3)的Hasse图中可以看出, ①{2,3,6}的最大元素为6;极大元

8 12 素也为6;极汴元素为2和3;上确界为6;下确界为1;没有最小元素。

9 10 4 6 ②{2,4,6}的极大元素为4和6;最小 素为2;极小元素也为2;上确界为12; 下确界为2;

③{4,8,12}的极大元素为8,12;最小元素为4;极小元素也为4;下确界为4;没有最大元素;没有上确界。

7 5 2 3 11 1 3)的Hasse图

性质 集合 最大元 最小元 极大元 极小元 上界 下界 上确界 下确界 6 无 无 无 2 4 6 4,6 8,12 2,3 2 4 6,12 12 无 1 1,2 1,2,4 6 12 无 1 2 4 {2,3,6} {2,4,6} {4,8,12}

3)的特殊元素表

5 6 34.对下面半序集合(A,?)的哈斯图,写出集合A及半

.

1

2 3 4 精品文档

序关系?的所有元素。 [解] A={0,1,2,3,4,5,6}

?={(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(1,1),

第34题

92,20,(2,5),(3,3),(3,5),(4,4),(4,6),(5,5),(6,6)}第34题

35.设R是集合X上的半序关系,A?X,证明R∩(A×A)是A上的半序关系。 [证].证法一:令R1=R∩(A×A),则R1?A×A,所以R1是A上的关系,我们只需

证明在A上R是自反的,反对称的,传递的即可。 (a)R1是自反的

对任何a∈A,由于A?X,所以a∈X,由于R在X上是自反的,故此(a,a)∈R;由于a∈A,显然(a,a)∈A×A;所以(a,a)∈R∩(A×A),即(a,a)R1。 (b)R1是反对称的

对任何(a,a)∈R1且(b,a)∈R1,由R1= R∩(A×A),故有(a,b)∈R且(b,a)∈R,以及a,b,c∈A。利用R的传递性,可得(a,c)∈R,利用a,c∈A可得(a,c)∈A×A,所以(a,c)∈R∩(A×A),即(a,c)∈R1。

证法二:令R1=R?(A?A),由于R?(A?A)?A?A,所以R1?A?A,因此R1是A上的关系。

①R1是自反的 对任何a, a?A

?(a,a)?R?(a,a)?A?A (R是X上的自反关系及A?X) ?(a,a)?R?(A?A)

?(a,a)?R1 (R1的定义)

所以,R1是自反的; ②R1是反对称的 对任何a,b?A

(a,b)?R1?(b,a)?R1

?(a,b)?R?(A?A)?(b,a)?R?(A?A) (R1的定义) ?((a,b)?R?(a,b)?A?A)?((b,a)?R?(b,a)?A?A)

?((a,b)?R?(b,a)?R)?((a,b)?A?A?(b,a)?A?A) (?的结合律、交换律)

.

精品文档

?((a,b)?R?(b,a)?R) (基本逻辑蕴涵式:p?q?p) ?a=b (R是反对称的) 所以,R1是反对称的; ③R1是传递的 对任何a,b,c?A

(a,b)?R1?(b,c)?R1

?(a,b)?R?(A?A)?(b,c)?R?(A?A) (R1的定义) ?((a,b)?R?(a,b)?A?A)?((b,c)?R?(b,c)?A?A)

?((a,b)?R?(b,c)?R)?((a,b)?A?A?(b,c)?A?A) (?的结合律、交换律) ?((a,c)?R?(a,c)?A?A (R是传递的,全关系A?A是传递的) ?(a,c)?R?(A?A)

?(a,c)?R1 (R1的定义) 所以,R1是传递的;

综合①、②、③,可知R1是A上的半序关系。

36.设(A,?1)和(A,?2)是两个半序集合,定义A×B上的关系?3如下:对于

a1,a2∈A,,b2∈B

(a1,b1),(a2,b2)∈?3?(a1,a2)∈?1∧(b1,b2)∈?2 证明?3是A×B上的半序关系。

[证].证法一:对于任何(a,b)∈A×B,就有a∈A及b∈B,从而利用?1及的自反性,可得 (a,a)∈?1且(b,b)∈?2因此由?3的定义,可知((a,b),(a,b))∈?3。 (b)?3是反对称的

对任何((a1,b1),(a2,b2))∈?3及((a2,b2),(a1,b1))∈,由?3的定义,可知(a1,a2)∈?1且(a2,a1)∈?1及(b1,b2)∈?2且(b2,b1)∈?2利用?1及?2的反对称性,可得a1=a2及b1=b2,因此(a1,b1)=(a2,b2)。 (c)?3是传递的

对任何((a1,b1),(a2,b2))∈?3及((a2,b2),(a3,b3)))∈?3,由?3

的定义,可知(a1,a2)∈?1且(a2,a3)∈?1及(b1,b2)∈?2且(b2,b3)∈?2。利用?1及?2的传递性,可得(a1,a3)∈?1及(b1,b3)∈?2。再次利用?3的定义,可得((a1,b1),(a3,b3)))∈?3。 证法二: ① ?3是自反的

.

精品文档

对任何(a,b),(a,b)?A?B

?a?A?b?B

?(a,a)??1?(b,b)??2 (?1,?2都是自反的) ?((a,b),(a,b))??3 (?3的定义)

所以,?3是自反的; ②?3是反对称的 对任何(a,b),(c,d)?A?B

((a,b), (c,d))??3?((c,d), (a,b))??3

?((a,c)??1?(b,d)??2)?((c,a)??1?(d,b)??2) (?3的定义) ?((a,c)??1?(c,a)??1)?((b,d)??2?(d,b)??2) (?的结合律、交换律) ?a=c?b=d (?1,?2都是反对称的) ?(a,b)=(c,d)

所以,?3是反对称的; ③?3是传递的

对任何(a,b),(c,d),(e,f)?A?B

((a,b), (c,d))??3?((c,d), (e,f))??3

?((a,c)??1?(b,d)??2)?((c,e)??1?(d,f)??2) (?3的定义) ?((a,c)??1?(c,e)??1)?((b,d)??2?(d,f)??2) (?的结合律、交换律) ?(a,e)??1?(b,f)??2 (?1,?2都是反对称的)

.

精品文档

?((a,b), (e,f))??3 (?3的定义) 所以,?3是传递的;

综合①、②、③,可知?3是A?B上的半序关系。

37.对于非空集合A,是否存在这样的关系R,它即是等价关系又是半序关系?若有,

请举出例子。

[解] 有。只有一种,那就是A上的幺关系IA,它即是等价关系,又是半序关系。

证法一:否则,如果有a∈A及b∈A且a≠b,使得(a,b)∈R,那么由R是对我的就将有(b,a)∈R,再由R是反对称的,就得到a=b,矛盾。这个矛盾说明同时为等价关系和半序关系的R只能是幺关系IA。 证法二:设R即是一等价关系,又是一半序关系。则 一方面,对任何元素a,b?A,

(a,b)?R?(a,b)?R?(b,a)?R (R的对称性)

?a=b (R的反对称性) ?(a,b)?IA

所以,R?IA;

另一方面,对任何元素a?A,

(a,a)?IA?(a,b)?R (R的自反性) 所以,IA?R;

综合这两方面,有 R=IA 。

38.对于下列每一种情况,举出有限集合和无限集合的例子各一个。

1) 非空半序集合,其中某些子集没有最大元素;

2) 非空半序集合,其中有一子集存在最大下界,但没有最小元素; 3) 非空序集合,其中有一子集存在上界,但没有最小上界。 [解] 1)(a)令A={a,b,c},则(2A,?)为半序集,其中子集

B1={{c},{a,b}} B2={{b},{a,c}} 等均没有最大元素; (b)半序集(N,≤)

{c} {a} {b} {a,c} {b,c} {a,b} {a,b,c}

.

? 1)的(a)的Hasse图