离散数学古天龙-1-4章答案 下载本文

┏ 1 0 0 ┓ ┏ 0 1 1 ┓ MR3o=┃ 0 1 0 ┃ MR3=┃ 0 0 1 ┃ ┗ 0 0 1 ┛ ┗ 0 0 0 ┛

┏ 0 1 1 ┓ ┏ 0 1 1 ┓ ┏ 0 0 1 ┓ MR32=MR3·MR3=┃ 0 0 1 ┃ ·┃ 0 0 1 ┃ =┃ 0 0 0 ┃ ┗ 0 0 0 ┛ ┗ 0 0 0 ┛ ┗ 0 0 0 ┛ ┏ 0 0 1 ┓ ┏ 0 1 1 ┓ ┏ 0 0 0 ┓ MR33=MR32·MR3=┃ 0 0 0 ┃·┃ 0 0 1 ┃= ┃ 0 0 0 ┃ ┗ 0 0 0 ┛ ┗ 0 0 0 ┛ ┗ 0 0 0 ┛

┏ 0 0 0 ┓ ┏ 0 1 1 ┓ ┏ 0 0 0 ┓ MR3的4次方=MR33·MR3=┃ 0 0 0 ┃·┃ 0 0 1 ┃=┃ 0 0 0 ┃ ┗ 0 0 0 ┛ ┗ 0 0 0 ┛ ┗ 0 0 0 ┛

33.对于题29中的关系R和S,求下列各式,并给出所得关系的关系矩阵和关系图。 解: 题29中的关系R和S如下:

R={<1,2>,<2,1>,<2,3>,<3,4>,<4,2>}; S={<3,1>,<4,2>};

IA={<1,1>,<2,2>,<3,3>,<4,4>};

①r(R)=R∪IA={<1,1>,<2,2>,<3,3>,<4,4>,

<1,2>,<2,1>,<2,3>,<3,4>,<4,2>};

②S(R)=R∪R的负一次方={<1,2>,<2,1>,<2,3>,<3,2>, <3,4>,<4,3>,<4,2>,<2,4>};

③t(R)=R∪R2∪R3∪(R的4次方)

┏ 0 1 0 0 ┓ ┏ 0 1 0 0 ┓ ┏ 0 1 0 0 ┓ ┏ 1 0 1 0 ┓ MR=┃ 1 0 1 0 ┃ MR2=MR·MR=┃ 1 0 1 0 ┃·┃ 1 0 1 0 ┃=┃ 0 1 0 1 ┃

┃ 0 0 0 1 ┃ ┃ 0 0 0 1 ┃ ┃ 0 0 0 1 ┃ ┃ 0 1 0 0 ┃ ┗ 0 1 0 0 ┛ ┗ 0 1 0 0 ┛ ┗ 0 1 0 0 ┛ ┗ 1 0 1 0 ┛ ┏ 1 0 1 0 ┓ ┏ 0 1 0 0 ┓ ┏ 0 1 0 1 ┓ MR3=MR2·MR=┃ 0 1 0 1 ┃·┃ 1 0 1 0 ┃ =┃ 1 1 1 0 ┃ ┃ 0 1 0 0 ┃ ┃ 0 0 0 1 ┃ ┃ 1 0 1 0 ┃ ┗ 1 0 1 0 ┛ ┗ 0 1 0 0 ┛ ┗ 0 0 0 1 ┛

┏ 0 1 0 1 ┓ ┏ 0 1 0 0 ┓ ┏ 1 1 1 0 ┓ ┃ 1 1 1 0 ┃ ┃ 1 0 1 0 ┃ ┃ 1 1 1 1 ┃ (MR的4次方)=MR3·MR=┃ 1 0 1 0 ┃·┃ 0 0 0 1 ┃=┃ 0 1 0 1 ┃ ┗ 0 0 0 1 ┛ ┗ 0 1 0 0 ┛ ┗ 0 1 0 0 ┛ ┏ 1 1 1 1 ┓ ┃ 1 1 1 1 ┃

Mt(R)=┃ 1 1 1 1 ┃=A×A. ┗ 1 1 1 1 ┛

37.对于集合{0,1,2,3}上的如下关系,判定哪些关系式等价关系。 ① {<0,0>,<1,1>,<2,2>,<3,3>}; 是等价关系。

④ {<0,0>,<1,1>,<1,3>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}; 自反性、对称性成立;

传递性不成立,因为<1,3>∈R,<3,2>∈R,但<1,2>?R.

38.对于人类集合上的如下关系,判定哪些是等价关系。 ①{|x与y有相同的父母}; 是等价关系。

∈R,满足自反性;

对称性:若∈R,则∈R,对称性成立。

传递性:若∈R∈R,则∈R,传递性成立。 ②{|x与y有相同的年龄} 是等价关系。

39.设R和S是集合A上的等价关系,判定下列各式中哪些是等价关系。 ① R∪S 解:

R∪S仍具有自反性和对称性,但不一定具备传递性,故不是等价关系。 ∵任意x∈A,有∈R,∈S,∴∈R∪S. 自反性成立。

对任意∈R∪S,则∈R或∈S.

由于R·S是等价关系,∴∈R或∈S,则∈R 对称性成立。

传递性不成立,反例:A{1,2,3}

R={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>},S={<1,1>,<2,2>,<3,3>,<3,2>,<2,3>} ② R∩S

自反性:因为任意x∈A,有∈R,且∈S, 所以∈R∩S,自反性成立。

对称性:任取∈R∩S,故∈R,且∈S,由于R和S是等价关系, 故∈R且∈S,所以∈R∩S。

传递性:任取∈R∩S,∈R∩S,即∈R且∈S,∈R且∈S, 由于R和S是等价关系,所以∈R,且∈S, 所以∈R∩S,传递性成立。 ∴综上所述,R∩S是等价关系。

41.对于正整数集合上的关系R={<,>|a·b=c·d},试证明R是等价关系。 自反性:任取a∈Z﹢,b∈Z+,∵ a·b=a·b, ∴<,>∈R,自反性成立。

对称性:任取<,>∈R,即a·b=c·d,c·d=a·b,故<,>∈R, 对称性成立。

传递性:任取<,>∈R,<,>∈R, ∴a·b=c·d,c·d=e·f,∴a·b=e·f, ∴<,>∈R,传递性成立。

45.对于题

37中的等价关系R,求集合A中各元素的等价类和

A的商集

解:

①[0]R={0} [1]R={1} [2]R={2} [3]R={3} A/R={{0}{1}{2}{3}}

④不是等价关系

47.对于集合A={a,b,c,d,e,f,g}的划分S={{a,c,e}{b,d,}{f,g}}求划分S所对应的等价关系

解:

R={a,c,e}×{a,c,e}U{b,d}×{b,d}U{f,g}×{f,g}

=

,,,,,,,,,,,,,,,,

52.画出如下集合A上整除关系的哈斯图

解:

①A={1,2,3,4,5,6,7,8}

R={| x,y∈A,且x能被y整除}

8

4

2 1

②A={1,2,3,5,7,11,13}

6

5 7

3 2 3 5 7 11 13

1

53.对于题52中关系①和②,求子集{1,2,3,5}和子集{2,3,7}的上

界,下界,上确界和下确界

解:

① 集合 {1,2,3,5} {2,3,7} ②

上界 无 无 下界 1 无 上确界 无 无 下确界 1 无 集合

上界 无 无 下界 1 无 上确界 无 无 下确界 1 无 {1,2,3,5} {2,3,7} 56.对于如图所示的集合A上的偏序关系所对应的哈斯图,求集合A的极大值,极小值,最大值和最小值

解:

h e

g f c b

极大值 a 极小值 最大值 最小值 b

a b a