第六章习题答案
- 格式：doc
- 大小：157.00 KB
- 文档页数：6
第6章习题答案1．列举出从X到Y的关系S的各元素（1）X={0，1，2}，Y={0，2，4}，S={<x，y>|x+y∈X⋂Y}（2）X={1，2，3，4，5}，Y={1，2，3}，S={<x，y>|x=y2，x∈X，y∈Y}解：（1）S={<0，0>，<0，2>，<2，0>}（2）S={<1，1>，<4，2>}2．设P={<1，2>，<2，4>，<3，3>}Q={<1，3>，<2，4>，<4，2>}求dom（P），ran（P），并证明：dom（P⋃Q）=dom（P）⋃dom（Q）解：dom（P）={1，2，3}ran（P）={2，3，4}证明：对于任意xx∈dom（P⋃Q）⇔∃y（<x，y>∈P⋃Q）⇔∃y（<x，y>∈P∨<x，y>∈Q）⇔∃y（<x，y>∈P）∨∃y（<x，y>∈Q）⇔ x∈dom（P）∨x∈dom（Q）⇔ x∈dom（P）⋃dom（Q）所以，dom（P⋃Q）=dom（P）⋃dom（Q）3．若关系R和S自反的，对称的和传递的，证明：R⋂S也是自反的，对称的和传递的。
证明：设R和S是集合A上的关系。
因为R和S是自反的，所以，对于A中的任意元素x，有<x，x>∈R和<x，x>∈S。
因此<x，x>∈R⋂S，即R⋂S是自反的。
因为R和S是对称的，所以对于任意<x，y>，<x，y>∈R⋂S⇔<x，y>∈R∧<x，y>∈S⇔<y，x>∈R∧<y，x>∈S⇔<y，x>∈R⋂S因此，R⋂S是对称的。
因为R和S是传递的，所以对于任意<x，y>和<y，z><x，y>∈R⋂S ∧<y，z>∈ R⋂S⇔<x，y>∈R∧<x，y>∈S∧<y，z>∈ R∧<y，z>∈ S⇔（<x，y>∈R∧<y，z>∈ R）∧（<x，y>∈S ∧<y，z>∈ S）⇔<x，z>∈R∧<x，z>∈ S⇔<x，z>∈R⋂S因此，R⋂S是传递的。
4．判断下列关系是否是传递的。
（1）R1={<1，1>}（2）R2={<1，2>，<2，2>}（3）R3={<1，2>，<2，3>，<1，3>，<2，1>}（4）R4={<1，1>，<2，2>，<3，3>}解：R1、R2、R4是传递的，R3不是传递的。
5．设A={1，2，3}，A上的关系R1，R2，R3，R4，R5分别由图6.17给出，试问：R1，R2，R3，R4，R5各有哪些性质？解：R1：自反、对称、反对称、传递。
R2：对称。
R3：反自反、反对称。
R4：反自反、对称、反对称、传递。
R5：自反、传递。
8．设R1，R2是集合X={0，1，2，3}上的关系，R1={<i，j>|j=i+1或j=i/2}，R2={<i，j>|i=j+2}，求复合关系（1）R1∙R2，（2）R2∙R1，并给出各复合关系的关系矩阵。
解：（1）R1∙R2={<0，1>,<1，2>,<2，3>,<0，0>,<2，1>}∙{<2，0>,<3，1>} ={<1，0>,<2，1>}（2）R2∙R1={<2，0>,<3，1>}∙{<0，1>,<1，2>,<2，3>,<0，0>,<2，1>} ={<2，0>,<2，1>,<3，2>}M R1∙R2=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡11M R2∙R1=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡11111．设R是X上的反对称关系，证明R⋂R-1⊆I X证明：假设R∩R－1/⊆I X，则有x,y∈A，使得〈x,y〉∈R∩R－1,但〈x,y〉∉I X，即〈x,y〉∈R且〈x,y〉∈R－1，〈x,y〉∉I X。
由此得〈x,y〉∈R且〈y,x〉∈R，x≠y。
这与R是反对称的相矛盾。
所以R∩R－1⊆I X。
13．求图6.19各关系的自反、对称、传递闭包的关系图。
R1R2R3R4R5312 3图6.17图6.19R1R2R314．令R 1，R 2是集合A 上的二元关系，并设R 1⊆R 2，试证明下列关系式 （1）r(R 1)⊆r(R 2) （2）s(R 1)⊆s(R 2) （3）t(R 1)⊆t(R 2)证明：首先证明下面两个结论：（a ） 若A ⊆B 且C ⊆D ， 则A ⋃C ⊆B ⋃D （b ） 若11R S ⊆且22R S ⊆，则1212R R S S ⊆ 证明：（a ）已知A ⊆B 且C ⊆D则有A ⋃B=B 且 C ⋃D= D （定理5.11） 因此（A ⋃ C ）⋃（B ⋃D ）=（A ⋃ B ）⋃（ C ⋃D ） （交换律，结合律） = B ⋃ D所以A ⋃C ⊆B ⋃D （定理5.11） （b ）对于任意,x y,x y 21R R ∈),,(21R y z R z x z ∈〉〈∧∈〉〈∃⇔),,(21S y z S z x z ∈〉〈∧∈〉〈∃⇒ （11R S ⊆，22R S ⊆）⇔21,S S y x ∈〉〈所以 1212R R S S ⊆r (R 1) s(R 1) t(R 1)r(R 2)s(R 2)t(R 2)r(R 3)s(R 3) t(R 3)（1）因为R 1⊆R 2， I A ⊆ I A所以R 1 ⋃ I A ⊆ R 2⋃I A （（a ）的证明） 即r(R 1)⊆r(R 2)（2）首先证 R 1-1⊆ R 2-1因为R 1⊆R 2 对于任意<x,y> <x,y>∈ R 1-1⇔< y, x >∈ R 1 ⇒< y, x >∈ R 2⇔<x,y>∈ R 2-1所以 R 1-1⊆ R 2-1因为 R 1⊆R 2 ,R 1-1⊆ R 2-1所以 R 1⋃R 1-1⊆R 2⋃R 2-1 （（a ）的证明） 即 s(R)⊆s(S)(3) 由(b)可得，若S R ⊆，则对于任意1i ≥，有iiS R ⊆ 由（a ）可知，若A ⊆B 且C ⊆D ， 则A ⋃C ⊆B ⋃D ， 又已知R 1⊆R 2，因此有∞=11i iR ⊆ ∞=12i iR即 t(R 1)⊆t(R 2)15．设R 1，R 2是集合A 上的二元关系，试证明 （1） r(R 1 ⋃ R 2)= r(R 1) ⋃r(R 2) （2） s(R 1⋃ R 2)= s(R 1)⋃s(R 2) 证明：（1）r(R 1 ⋃ R 2)= R 1 ⋃ R 2 ⋃ I A= R 1 ⋃ I A ⋃ R 2⋃ I A = r(R 1) ⋃r(R 2) （2）s(R 1⋃ R 2)= R 1⋃ R 2 ⋃(R 1⋃ R 2)-1 = R 1⋃ R 2 ⋃R 1-1⋃ R 2-1 =(R 1 ⋃R 1-1)⋃ (R 2⋃ R 2-1) = s(R 1)⋃s(R 2)18．对于下列集合上的整除关系画出哈斯图。
（1） A={1，2，3，4，6，8，12，24} （2） B={1，2，3，⋯，12} 解：（1）见左图（2）见右图12 247919．对于偏序关系---整除关系画出下列集合的哈斯图，并指出哪些是全序的 （1）A={2，6，24} （2）B={3，5，15}（3）C={1，2，3，6，12} （4）D={2，4，6，8，12} （5）E={3，9，27，54} 解：由上哈斯图可见，（1）和（5）是全序的。
20．图6.21（见书184页）给出了A={1，2，3，4}上的四个偏序关系图，试画出它们的哈斯图，并判别哪一个是全序或良序关系？ 解：由上哈斯图可见，（c ）是全序和良序关系。
25．正整数集合上的关系R 被定义为n i Rn j ⇔n i /n j 能够被表达成2m 的指数形式，其中m 是任意整数。
（1）证明关系R 是等价关系。
（2）等价类是什么？ 解：（1）证明：对于任意正整数x因为x/x=1=20，0是整数，所以有xRx ，R 有自反性。
对于任意正整数x ，y设xRy ，即存在整数m ，使得x/y=2m ，则有y/x=2-m ，-m 是整数，所以有yRx ，R 有对称性。
对于任意正整数x ，y ，z设xRy ，yRz ，即存在整数m ，n ，使得x/y=2m ，y/z=2n ，则有x/z=（x/y ）∙（y/z ）=2m ∙2n =2m+n ，m+n 是整数，所以有xRz ，R 有传递性。
（1）5 （2）（3）3 12 4 6 12 8 （4）3 927 54（5） 2 3（a ）24（b ）2 13 4（c ）21 34（d ）综上所述，关系R是等价关系。
（2）等价类有正奇数个那么多：[1]R，[3]R，[5]R，[7]R⋯对于任意正奇数x，[x]R={y|y是正整数，存在自然数m，使得y=2m x}26．设R是正整数的有序偶集合上的关系，并且〈x，y〉R〈u，v〉当且仅当xv=yu，证明R是等价关系。
证明：对于任意正整数x，因为xx=xx，根据R的定义，有〈x，x〉R〈x，x〉，故R 有自反性。
对于任意正整数x，y，u，v，设〈x，y〉R〈u，v〉，根据R的定义，有xv=yu，即有uy=vx，〈u，v〉R〈x，y〉，因此R有对称性。
对于任意正整数x，y，u，v，s，t，设〈x，y〉R〈u，v〉，〈u，v〉R〈s，t〉根据R 的定义，有xv=yu，ut=vs。
因此v=ut/s，xv=xut/s=yu，xt=ys，根据R的定义，有〈x，y〉R〈s，t〉，故R有传递性。
综上所述，关系R是等价关系。
27．设A={a，b，c，d}，而且π1，π2，π3是A的划分，如果π1={{a，b，c}，{d}}，π2={{a}，{b}，{c}，{d}}，π3={{a，b，c，d}}，请分别列出由划分π1，π2，π3确定的等价关系。
解：由划分π1，π2，π3确定的等价关系分别是：R1={〈a，b〉，〈b，a〉，〈a，c〉，〈c，a〉，〈b，c〉，〈c，b〉}⋃I AR2={〈a，a〉，〈b，b〉，〈c，c〉，〈d，d〉}=I AR3={〈a，b〉，〈b，a〉，〈a，c〉，〈c，a〉，〈a，d〉，〈d，a〉，〈b，c〉，〈c，b〉，〈b，d〉，〈d，b〉，〈c，d〉，〈d，c〉}⋃I A。
