离散数学古天龙-1-4章答案(2)

14.设A={a,b,c,d,e,f,g},其中a,b,c,d,e,f和g分别表示7人，且a,b和c都是18岁，

d和e都是21岁，f,和g都是23岁，试给出A上的同龄关系，并用关系矩阵和关系图表示 解：

R＝{,,,,,,

,,,,,, ,,,} ┏ 1 1 1 0 0 0 0 ┓

┃ 1 1 1 0 0 0 0 ┃ c ┃ 1 1 1 0 0 0 0 ┃ MR＝┃ 0 0 0 1 1 0 0 ┃

┃ 0 0 0 1 1 0 0 ┃ a b ┃ 0 0 0 0 0 1 1 ┃ ┗ 0 0 0 0 0 1 1 ┛

g

g P69

15.判断集合A={a,b,c}上的如下关系所具有的性质。 ① R1={,,,,,} 自反性、反对称性、传递性

④ R4={,,,,} 自反性、对称性、传递性

⑤ R5=A×A

对称性、自反性、传递性

⑥ R6=

自反性、对称性、传递性

16.判断集合A={3,5,6，7,10,12}上的如下关系所具有的性质。 ① A上的小于等于关系

自反性、反对称性、传递性

② A上的恒等关系

自反性、对称性、反对称性、传递性

e f

19.对于图2.16中给出的集合A={1，2,3}上的关系，写出相应的关系表达式和关系矩阵，并分析他们各自具有的性质。

R2={<1,1>,<3,3>,<1,2>,<2,1>,<2,3>,<3,2>,<1,3>,<3,1>} ┏ 1 1 1 ┓ 1 MR2= ┃ 1 0 1 ┃ ┗ 1 1 1 ┛ 2 （对称性） 3 R2

R11={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<2,3>,<3,2>}

1 ┏ 1 1 0 ┓ MR11= ┃ 1 1 1 ┃ ┗ 0 1 1 ┛ 2 3 （自反性、对称性 ） 25.对于集合A={a,b,c}到集合B={1,2}的关系； R={,,}和S={,,} 求R∪S,R∩S,R﹣S,S﹣R,~R和~S。 解：

R∪S={,,,,}; R∩S={,}; R﹣S={}; S﹣R={};

~R=A×B－R={,,}; ~S=A×B－S={,,}.

27.对于集合A={1,2,3,4,5,6}上的关系R={|(x-y)2∈A}，S={|y是x的倍数}和 T={|x整除y，y是素数}，试写出各关系中的元素，各关系的关系矩阵和关系图， 并计算下列各式。 解：

R={<1,3>,<2,1>,<1,2>,<2,3>,<2,4>,<3,1>,<3,2>, <3,4>,<3,5>,<4,2>,<4,3>,<4,5>,<4,6>, <5,3>,<5,4>,<5,6>,<6,4>,<6,5>}; S={<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>};

T={<1,1>,<1,2>,<1,3>,<1,5> ,<2,2>,<3,3>,<5,5>}

┏ 0 1 1 0 0 0 ┓ R的关系图： ┃ 1 0 1 1 0 0 ┃ 1 2 MR=┃ 1 1 0 1 1 0 ┃ ┃ 0 1 1 0 1 1 ┃

┃ 0 0 1 1 0 1 ┃ 6 ┗ 0 0 0 1 1 0 ┛

4 3 5

其余略；

① R·S={<1,2>,<1,4>,<1,6>,<1,3>,

<2,1>,<2,2>,<2,3>,<2,4>,<2,5>,<2,6>, <3,1>,<3,2>,<3,3>,<3,4>,<3,5>,<3,6>, <4,2>,<4,4>,<4,3>,<4,5>,<4,6>, <5,3>,<5,6>,<5,4>, <6,4>,<6,5>} ④ (R∩T)·S

R∩T={<1,2>,<1,3>}

(R∩T)·S={<1,2>,<1,4>,<1,6>,<1,3>}

32.对于集合A={a,b,c}上的如下关系，求各个关系的各次幂。 ① R1={,,}

R1o={,,} ┏ 1 0 0 ┓ MR1o=┃ 0 1 0 ┃ ┗ 0 0 1 ┛

┏ 1 0 0 ┓ ┏ 1 0 0 ┓ ┏ 1 0 0 ┓

MR1= ┃ 1 0 0 ┃ MR12=MR1·MR1=┃ 1 0 0 ┃=┃ 1 0 0 ┃=MR1 ┗ 0 0 0 ┛ ┗ 0 0 0 ┛ ┗ 0 0 0 ┛ ┏ 1 0 0 ┓

┃ 0 1 0 ┃ （n=0） ┗ 0 0 1 ┛ MR1的n次方=┏ 1 0 0 ┓

┃ 1 0 0 ┃ (n≥1) ┗ 0 0 0 ┛

③ R3={,,};

┏ 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,传递性成立。