复旦大学：《离散数学》课程教学讲义（集合论）第二章 关系（主讲：吴永辉）

证明两个关系相等 (3)基本法证明: ab(R1R24→②a(R1尺2)(b dR1且(a∈R2园bR1a b∈R2。所以,(R2R2)4=R (1)(2)同理,证明见书 (4)同理

证明两个关系相等  (3) 基本法证明：  (a, b)(R1R2)-1  (b, a) (R1R2)  (b, a) R1且 (b, a) R2  (a, b) R1-1且(a, b) R2-1。所以，(R1R2)-1= R1-1 R2-1 。  (1), (2)同理, 证明见书。  (4)同理

(5)反证法。 设≠x,则存在(a,那么(a ∈2.导致矛盾 (6),(7),(8)基本法或公式法证明

 (5)反证法。  设-1，则存在(a, b)-1 , 那么(b, a) . 导致矛盾。  (6), (7), (8)基本法或公式法证明

2.3关系的运算 定理2.2 展是A上的二元关系,则R是对称的R=R1。 证明: 是对称的→R=R:(证明两个集合相等 问abeR因为R是对称的,所以②叫ER则(a b∈R所以RR。同理,RcR。则R=Rz R=R1→R是对称的:(证明满足某一性质) 如果(abR因为R=R,所以b∈R,则(b a)∈R。所以R是对称的。(根据对称的定义)

2 .3 关系的运算  定理2.2 R是A上的二元关系，则R是对称的R=R-1。 证明： R是对称的  R=R-1：（证明两个集合相等） (a, b)R, 因为R是对称的，所以(b, a)R, 则(a, b)R-1 ; 所以RR-1。同理， R-1R。则R=R-1。 R=R-1  R是对称的：（证明满足某一性质） 如果(a, b)R, 因为R=R-1，所以(a, b)R-1，则(b, a)R。所以R是对称的。（根据对称的定义）

2.3关系的运算 二复合运算 定义28(复合关系)设R是从A到B 的二元关系,R是从刷C的二元关系 则从A到C的二元关系记为R1°R2,定 义为R1°R2=CaAC∈C且存 在bbR(的R2称为R1 和R的复合关系

2 .3 关系的运算  二 复合运算  定义2.8（复合关系） 设R1是从A到B 的二元关系， R2是从B到C的二元关系， 则从A到C的二元关系记为R1°R2，定 义为R1°R2 ={(a, c) | aA, cC, 且存 在bB使(a, b) R1, (b, c) R2}称为R1 和R2的复合关系

2.3关系的运算 ■定理23(结合律) R,°R)°R2=R°(R2°R 1 证明方法: 采用基本法,证明两个关系相等。 即:(ad∈(R1°R2)°Rad)∈R°(R2°R3) 则(R1°R2)°R∈R1°(R2Ry); ad∈R1°(R2°R d)∈(R°R2)°R 则R1(R2°R3∈(R1°R2)°R 具体证明步骤见书中证明 不满足交换律,即R1°R2≠R2°R

2 .3 关系的运算  定理2.3（结合律） (R1°R2)°R3 = R1°(R2°R3)  证明方法： 采用基本法，证明两个关系相等。 即：(a, d) (R1°R2)°R3(a, d)R1°(R2°R3)， 则(R1°R2)°R3  R1°(R2°R3) ； (a, d)  R1°(R2°R3)  (a, d)  (R1°R2)°R3 ， 则R1°(R2°R3)  (R1°R2)°R3 。 具体证明步骤见书中证明。  不满足交换律，即R1°R2  R2°R1