离散数学(第三版)课后习题答案 下载本文

精品文档

6)

1??23??1?1 R6???1??4?1111?111?? 111??111?R6是自反的,对称的,传递的,循环的。从而是等价关系。 7)

1??23??0?0 R7???0??4?0000?000?? 000??000?R7是反自反的对称的,传递的,循环的,反传递的,反对称的。

12.设A是A上的关系,证明 1)R是自反的当且反当IA?R

2)R是反自反的当且仅当IA∩R=?

?3)R是对称的当且反当R=R

?4) R是反对称的当且仅当R∩R?IA 5)R是传递的当且仅当R?R?R

[证] 1)必要性

若R是自反的,则对任何x∈A,都有(x,x)∈R,但是IA={(x,x)|x∈A},所以IA?R。

充分性

若IA?A则由IA={(x,x)|x∈A},可知对任何x∈A,都有(x,x)∈R,所以R是自反的。 2)必要性

若R是反自反的,则对任何x∈A,都是(x,x)?R,从而(x,x)∈R′,由IA={(x,x)|x∈A} 可知IA?R′。于是IA∩R?R′∩R=?,另外??IA∩R,

.

精品文档

所以IA∩R=?。

充分性

若IA∩R=?,则R是反自反的。否则,不是反自反的,那么应存在某一x0

∈A,使得(x0,x0)∈R。但是(x0,x0)∈IA,从而(x0,x0)?。这不可能,矛盾。 3)必要性,

若R是对称的,则对任何(x,y)∈R,就有(y,x)∈R。于是根据逆关系的定义,可得(x,y)∈R,于是R?R;对任何(x,y)∈R,由逆关

????系的定义,可得(y,x)∈R。再次利用R的对称性有(y,x)∈R,于是R?

?R;综合两方面,有R=R。

充分性

若R= R,则对任何(x, y)∈R,由R=R可得(x,y)∈R。从而由逆关系的定义,可知(y,x)∈R这说明R是对称的。 4)必要性

???∈R,从逆关系的定义,就有(x, y)∈R及(y,x)∈R,因此,利用R的

?若R是反对称的,则对任何(x,y)∈R,即有(x, y)∈R及(x,y)

??反对称性,可得x=y。于是就有(x,y)=(x,x)∈IA,所以R∩R?IA。

充分性

若R∩R ?IA,则对任何(x,y)∈R及(y,x)∈R,从逆R关系的定义,可得(x,y)∈R及(x,y)∈R,也即(x,y)∈R∩R,利用R∩R =IA可得(x,y)∈IA,于是x=y。所以R是反对称的。 5)必要性

若R是传递的,则对任何(x,y)RоR,由复合关系的定义可知,存在着y∈A,使(x,y)∈R且(y,y)∈R,从而利用R的传递性,可知(x,y)∈R。所以

RоR?R。

充分性

RоR。从而利用RоR?R可得(x,y)∈R。所以R是传递的。 证法二: 1)?):对任何x,

x∈A

?(x,x)∈IA (IA是幺关系,因此是自反关系)

?????.

精品文档

?(x,x)∈R (R是自反关系) 所以 IA?R ; ?):对任何x∈A,

x∈A

?(x,x)∈IA (IA是幺关系,因此是自反关系) ?(x,x)∈R (因IA?R) 所以,R是自反关系; 2)?)首先 ??IA?R ;

其次,对任何x,y∈A,若 (x,y)∈IA?R ?(x,y)∈IA?(x,y)∈R

?x=y?(x,y)∈R (IA是幺关系,因此是自反关系) ?(x,x)∈R

则与R是反自反关系,(x,x)?R矛盾。故IA?R?? ; 因此,由包含关系?的反对称性,可得 IA?R=? ; ?):对任何x∈A,若

(x,x)∈R

?(x,x)∈IA?(x,x)∈R (IA是幺关系,因此是自反关系) ?(x,x)∈IA?R

?(x,x)∈? (因IA?R=?) 则与空集不含任何元素,(x,x)??矛盾。 故对任何x∈A,(x,x)?R ; 所以,R是反自反关系; 3)?)对任何x,y∈A

(x,y)∈R

?(y,x)∈R (R是对称关系) ?(x,y)∈R 所以,R=R; ?):对任何x,y∈A

(x,y)∈R

?(x,y)∈R (R=R) ?(y,x)∈R

????.

精品文档

所以,R是对称的; 4)?)对任何x,y∈A

(x,y)∈R?R

??(x,y)∈R?(x,y)∈R ?(x,y)∈R?(y,x)∈R

?x=y (R是反对称关系) ? (x,y)∈IA (IA是自反关系) 所以,R?R?IA ; ?):对任何x,y∈A

(x,y)∈R

?(x,y)∈R (R=R) ?(y,x)∈R 所以,R是对称的;

13.设A、B为有穷集合,R,S?A×B,MR=(xij)m×n,MS=(yij)m×n

1)为了R?S,必须且只须?i?j(xij≤ yij)

2)设MR∪S=(Zij)m×n,那么Zij=xijVyij,I=1,2……,m,j=1,2,……n. 3)设MR∩S=(tij)m×n,那么tij=xij^yij i=1,2,……m;j=1,2,……,n. [证] 由于A、B是有穷集合,不妨设

A={a1,a2……,am},B={b1,b2,……,bn} 1)必要性

若R?S,则对任何i∈{1,2,……,m},对任何j∈{1,2,……n},若(ai,bj)∈R,则R的关系矩阵MR=(xij)m×n中第I行第j列元素xij=1,根据R?S,可得(ai,bj)∈S,从而得S的关系矩阵MS=(yij)m×n中第I行第j列元素yij=1,由于是1≤1故此xij≤yij;若(ai,bj)?R,则R的关系矩阵MR=(xij)m×n中第i行第j列元素xij=0,因此由S的关系矩阵MS=(yij)m×n中第j列元素yij≥0,可得xij≤yij。总之,有(?i)(?j)(xij≤yij)。 2)充分性

若(?i)(?j)(xij≤yij),则对任何(ai,bj)∈R,就有R的关系

矩阵MR=(xij)m×n中第i行第j列元素xij=1,由于xij≤yij,所以yij≥1,故此yij≥1这说明S的关系矩阵MS=(yij)m×n中第i行第j列元素yij为1,因此必

????.

精品文档

(ai,bj)∈S,所以R?S。

2)对任何i∈{1,2,……,m},对任何j∈{1,2,……,n}若Zij=1,则(ai,bj)∈R∪S,故此(ai,bj)∈R或者(ai,bj)∈S,于是xij=1或者yij=1。从而 bj)?S,于是xij=0且yij=0。从而xij∨yij=0。因而Zij=xij∨yij=0; 综合上述两种情况,就有zji=xij∨yij,i=1,2,……,m,j=1,2,……n,。 3)对任何i∈{1,2,……m},对任何j∈{1,2,……,n}。若tij=1,则(ai,bj)∈R∩S,故此(ai,bj)∈S且(ai,bj)∈S,于是xij=1,且yij=1从而xij∧yij=1。因而tij=xij∧yij=1;若tij=0,则(ai,bj)?R∩S,故此(ai,bj)?S,于是xij=0或者yij=0,从而xij∧yij=0。因而tij=xij∧yij=0。

综合上述两种情况,就有tij=xij∧yij,i=1,2,……,m,j=1,2,……,n。 14.设A={1,2,3,4},R1,R2为A上的关系,R1={(1,1),(1,2),(2,4)},

R2={(1,4),(2,3),(2,4),(3,2)},求R1оR2,R2оR1,R1оR2оR1R1

3[解] MR1?1?0???0??0100??0?0001?? ,MR??2?0000???000??0001010100?1?? 0??0?1)

MR?R?MR121?11?00?MR2??00??0000??0001??0?0011??001???????00??0100??0????00??0000??0010001?00?? 00??00?1?2?

3?3?3?4?4?4?R1 R2

1?2?1?2?无论从复合关系图还是从复合关系矩阵 都可得R1оR2={(1,3),(1,4)}

.