离散数学第二版答案(6-7章)

?g[Xa]?g[Xb]?g[Xa*Xb]

?Xa,Xb?X1，又??X1,*?是?X,*?的子代数

故X1对*运算封闭

?Xa*Xb?X1

?g[Xa*Xb]?g[X1]，即a?b?g[X1] ?g[X1]对?运算满足封闭性。

由(1),(2),(3)可知, ?g[X1],??为?Y,??的子代数。

6.3第141页

1．解：

解：首先，判断?m是否是等价关系。任取x?I，由于x?x?0?m，因此x是自反的；任取x,y?I，若x?mx，?m?my，即x?y?a?m，若x（a?I），则y?x??a?m，

y?mx，因此?m是对称的；任取x,y,z?I（a?I），y?z?my,y?mz，则x?y?a?m?b?m（b?I），于是x?z?(x?y)?(y?z)?(a?b)?m，

a?b?I，因此x?mz，可知?m是可传递的。因此，?m是等价关系。

其次，判断?m关于*是否满足代换性质。 任取x,y?I，若x?my，即存在某个p?I，满足x?y?p?m

*(x)?xk(modm) *(y)?yk(modm)

则

*(x)?(y?p?m)k(modm)1k?1?Ck0yk?Cky(p?m)1?Ck2yk?2(p?m)2?1k?1?yk?p?m?(Cky?Ck2yk?2(p?m)1??Ckky0(p?m)k

?Ckky0(p?m)k?1)于是

1k?1*(x)?*(y)?p?m?(Cky?Ck2yk?2(p?m)1??Ckky0(p?m)k?1)?Cy(p?m))?mk?k0(C?kkk0k?1?p?(Cy由于

1k?1p?(kCy?1kk?1?Cy2kk?2(p?m)?1

k2k?1C(y2?)p?m?y)，p)因?m此，I*(x)?m*(y)，?m关于*是满足代换性质。

综上所述，?m是U上的同余关系。

2. 解：

（1）对于+运算，在二元运算下，任取

x1,x2,y1,y2?I，验证下式是否成立

x1Ry1x2Ry2?取

??2行?

x1?x2Ry1?y211，2x1?1,x2?2,y1?1,y2??2，可知满足xRyxRy2，但|x1?x2|?|y1?y2|，

即x1?x2Ry1?y2。可知对于运算+，R不满足代换性质。

x1,x2,y1,y2?I， y1|,|x2|?|y2|

（2）对于?运算，在二元运算下，任取

若x1Ry1，x2Ry2，则必然满足|x1|?|于是|x1?x2|?|x1|?|x2|?|y1|?|y2|?|y1?y2|

y2。

可得x1?x2Ry1?由x1,x2,y1,y2取值的任意性可知，对于运算?，R满足代换性质。

3．证明：

(1) 对于?x1,x2,y1,y2，有x1Ry1,x2Ry2

由于R对?3具有代换性质，所以有(x1?x1)R(y1?y1) 由此可知：

(x1?3x1?3...?3x1)R(y1?3y1?3...?3y1)?x1?3x2Ry1?3x2??????????????????x2个x1同理可知：

x2个y1(x2?3x2?3...?3x2)R(y2?3y2?3...?3y2)?y1?3x2Ry1?3y2??????????????????y1个x2y2个y1因R是等价关系，故是可传递的，所以有x1?3x2Ry1?3y2 所以R对?3具有代换性质。

(2) S?{?0,0?,?1,1?,?2,2?,?1,2?,?2,1?}对?3具有代换性质，

但对?3不具有代换性质，因?2,2??3?1,2???0,1??S

4．设代数系统V??G,??，R1,R2为同余关系。 (1)即证：R1?R2为同余关系 证明：R1?R2为等价关系

若w??对任意

a1,b1,a2,b2,...anw,bnw?G

?R2)bnw 有a1(R1?R2)b1,a2(R1?R2)b2,…anw(R1 则a1R1b1， a2R1b2，…

anwR1bnw

a1R2b1， a2R2b2，…

?R1?R2为同余关系

anwR2bnw?w(?a1,a2,...anw?)R1w(?b1,b2,...bnw?) ?w(?a1,a2,...anw?)R2w(?b1,b2,...bnw?) ?w(?a1,a2,...anw?)R1?R2w(?b1,b2,...bnw?)

所以R1?R2为同余关系。 (2) R1?R2为等价关系

若w??对任意

a1,b1,a2,b2,...anw,bnw?G

w 有a1(R1?R2)b1, a2(R1?R2)b2,…anw(R1?R2)bn 未必有a1R1b1， a2R1b2，…

anwR1bnww

a1R2b1， a2R2b2，…

因此，可能不满足代换性质

anwR2bn

所以R1?R2未必是同余关系。

5．

（1）xRy,当且仅当(x?0?y?0)?(x?0?y?0) 解：R不是?I,??上的同余关系，取x1但是x1?0,y1?3,x2??1,y2??2,则x1Ry1,x2Ry2，

?x2??1?0，y1?y2?1?0，因此x1?x2Ry1?y2，不满足代换性质。

（2）xRy, 当且仅当x?y?10 解：R不是?I,??上的同余关系，取

x?0,y?9,z?15，则xRy，yRz，但

|x?z|?15?1，0xRz，R不满足可传递性，不是等价关系。

（3）xRy,当且仅当(x?y?0)?(x?0?y?0) 解：R不是?I,??上的同余关系，取取x1但是x1??3,y1?2,x2?3,y2?2,则x1Ry1,x2Ry2，

?x2?0，y1?y2?4?0，因此x1?x2Ry1?y2，不满足代换性质。

（4）xRy,当且仅当x?y

解：R不是?I,??上的同余关系，取x?9,y足对称性，不是等价关系。

?8，则xRy，但y?x，即yRx，R不满

6.4第143页

1.