离散数学古天龙-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