哈工大《离散数学》教科书习题答案

故这步推理错误

5.设R,S是X上的满足R?S?S?R的对称关系,证明R?S?S?R.

证1:设(x,z)?S?R,则?y?X,使得(x,y)?S且(y,z)?R。 因为R,S均对称,所以R?R?1,S?S?1 于是(y,x)?S?1?S,(z,y)?R?1?R

从而(z,x)?R?S,(x,z)?(R?S)?1?(S?R)?1?R?1?S?1?R?S 因此S?R?R?S 故S?R?R?S

证2S?R?S?1?R?1?(R?S)?1?(S?R)?1?R?1?S?1?R?S,故S?R?R?S,于是R?S?S?R

6.设R为X上的对称关系,证明:?n?N,Rn是对称关系。

证1(Rn)?1?(R?R???R)?1?R?1?R?1???R?1?R?R??R?Rn,故R对称。 证2?(x,y)?Rn,则?y1,y2,?,yn?1?X,使得

(x,y1)?R,(y1,y2)?R,?,(yn?1,y)?R。因为

R对称,所以

(y,yn?1)?R,(yn?1,yn?2)?R,?,(y2,y1)?R,(y1,x?R),因此(y,x)?Rn,故R对称。

证3用数学归纳法对n进行归纳。 当n=1时,Rn=R显然是对称的。 假设当n=k时,Rk对称。

当n=k+1时,Rk?1?Rk?R?R?Rk。

?(x,y)?Rk?1,则?z?X,使得(x,z)?Rk,(z,y)?R。

因为Rk,R均是对称的,所以(y,z)?R,(z,x)?Rk,于是(y,x)?R?Rk?Rk?1。 因此Rk+1对称。

综上,Rn对n?N都是对称关系。

7.设R1,R2,R3,?是X上的二元关系的一个无穷序列,则当每个Ri是对称关系时,

?Ri还是对称的吗?

i?1? 33

证:则?i0的使得(x,y)?Rio。因为Ri0对称,所以有(y,x)?Rio,?(x,y)??Ri,

i?1?故(y,x)??Ri。因此?Ri还是对称的。

i?1i?1??P98习题

1.设R是X上的二元关系,试证(1)

(R?)??R?,(2)(R*)*?R*,(3)R?R*?R*?R?R?,(4)(R?)*?(R*)??R?。 证:(1)因为R??(R?)?显然成立。

其次,设(a,b)?(R?)?,因为(R?)?是一切包含R?的传递关系的交,而

R??(R?)?且R?是传递的,故(a,b)?R?,即(R?)??R?。

因此(R?)??R?。

(2)因为R??(R?)?显然成立。

其次,设(a,b)?(R?)?,因为(R?)?是一切包含R?的自反传递关系的交,而R?

本身是自反的也是传递的且R??(R?)?,故(a,b)?R?,即(R?)??R?,因此

(R?)??R?。

(3)R?R??R?(R0?R?R2??)?R?R2?R3???R?

R??R?(R0?R?R2??)?R?R?R2?R3???R? (4)先证(R?)??R?

(R?)??(R?)0?(R?)??IX?R??R? 再证(R?)??R?

因为(R?)?是包含R?的一切传递关系的交,又因为R??(R?)?且R?是传递的,所以(R?)??R?。

因此(R?)??(R?)??R?。

2.设X=(a,b,c,d,e),R={(a,b),(b,c),(c,d),(d,e)}试求R?和R?。

34

解:R2?{(a,c),(b,d),(c,e)}

R3?{(a,d),(b,e)}R4?{(a,e)}R5??

故R??R?R1?R2?R3?R4?R5?{(a,b),(b,c),(c,d),(d,e),(a,c),

(b,d),(c,e),(a,d),(b,e),(a,e)}

R??IX?R??{(a,a),(b,b),(c,c),(d,d),(e,e),(a,b),(b,c),(c,d),(d,e),(a,c),(b,d),(c,e),(a,d),(b,e),(a,e)}3.设R,S为X上的二元关系,试证:

(1)(R?S)??R??S? (2)(R?S)??R??S?。 证:(1)因为R?R?S,S?R?S 所以R??(R?S)?,S??(R?S)? 因此R??S??(R?S)? (2)因为R?R?S,S?R?S 所以R??(R?S)?,S??(R?S)?

因此R??S??(R?S)? 〔证毕〕 6.举例说明s(t(R))与t(s(R))确定不相等。

解:设N?{1,2,3,?},在N上定义小于关系“<”,则

s(t(?))?s(?)?“不等关系≠”。 t(s(?))?t(?)?“全关系”。

因此的确不相等。

7.是否可以定义二元关系的反自反闭包与二元关系的反对称闭包?为什么?

解:不可以。

因为二元关系的反自反闭包和反对称闭包是空集,没有多少研究价值。因此不定义二元关系的反自反闭包和反对称闭包。

8.是否存在X(X=n)上的一个二元关系R使得R,R2,?,Rn两两不相等。

35

解:存在。

设X?{1,2,3,?,n},则R是X上的二元关系且R?{(1,2),(2,3),?,(n?1,n)}即可满足要求。

9.证明:若R是对称的,则R+也是对称的。

证:

?(x,y)?R??Ri,则?m?N,使得(x,y)?Rm。因为若R是对称的,所

?i?1?以R也是对称的,因此(y,x)?R??Ri。即R?也是对称的。

mm?i?110.设R1,R2是X上的二元关系,证明:

(1)r(R1?R2)?r(R1)?r(R2) (2)S(R1?R2)?s(R1)?s(R2) (3)t(R1?R2)?t(R1)?t(R2)

证:(1)因为r(R1)和r(R2)都是A上的自反关系,所以r(R1)?r(R2)也A上的自反关系。

由R1?r(R1),R2?r(R2),得R1?R2?r(R1)?r(R2),所以r(R1)?r(R2)是包含

R1?R2的自反关系。由自反闭包的定义可知:r(R1?R2)?r(R1)?r(R2)

又R1?R1?R2,R2?R1?R2,故r(R1)?r(R1?R2),r(R2)?r(R1?R2),因此

r(R1)?r(R2)?r(R1?R2)。从而r(R1?R2)?r(R1)?r(R2) (2)同(1)的证明。

(3)因为R1?R1?R2,R2?R1?R2,故t(R1)?t(R1?R2),t(R2)?t(R1?R2),因此t(R1)?t(R2)?t(R1?R2)。

例:设X?{a,b,c},A上的两个关系R1?{(a,b)},R2?{(b,c)}。于是

t(R1)?{(a,b)},t(R2)?{(b,c)},故t(R1)?t(R2)?{(a,b),(b,c)},但 R1?R2?{(a,b),(b,c)},t(R1?R2)?{(a,b),(b,c),(a,c)}。 因此t(R1?R2)?t(R1)?t(R2)。

36

联系客服:779662525#qq.com(#替换为@)