《离散数学》课程教学资源（PPT课件讲稿）关系的性质、闭包和等价

关系的性质:对称性 A=a,b, c) M =1Q1 R 011 b

关系的性质：对称性 11

关系的性质:对称性 口R是集合A上的对称关系兮R1=R 口→证明一个集合等式R1=R 若(2b∈R1,则(a∈E由R的对称性可知(2b∈R因此 R∈R同理可得:RR1; 口∈只需证明:对任意的(a26)若(a2b)∈E则(h2∈R

关系的性质：对称性  R 是集合A上的对称关系 R-1=R   证明一个集合等式 R-1=R ◼ 若(a,b)R-1 , 则(b,a)R, 由R的对称性可知(a,b)R, 因此： R-1R; 同理可得：RR-1 ;   只需证明：对任意的(a,b) 若(a,b)R, 则(b,a)R 12

关系的性质:传递性 ●集合A上的关系R是 传递的 transitive:若(a,b)∈R,(bc)∈R,则(a,c)∈R ·设A={1,2,3},RAxA {(1,1)(1,2)(1,3),(2,1),(2,2),(2,3),(3,3)}传递的 (1,2)(2,3)、(3,1)}是非传递的 {(1,3)}? 关系R是传递关系分V(a,b,c)(a,b)∈RA(b,C)∈R)→(a,C)∈R)

关系的性质：传递性 13

关系的性质:传递性 A=a,b,c, 10 R 011

关系的性质：传递性 14

关系的性质:传递性 口关系的复合(乘)运算满足结合律,可以用R表示 RRo…R(m是正整数) 口命题:(ab)∈当且仅当:存在,;t1∈A满足 (a4,,…(t2,tn1),(tn1,b)∈R 口集合A上的关系R是传递关系兮R∈R 口必要性:→任取(4b∈R,根据上述命题以及R的传递性可得(42b∈R 口充分性:←若(ab∈R(b∈R则(∈R,由B可得:(a∈R,则R 是传递关系

 关系的复合(乘)运算满足结合律，可以用Rn 表示 R◦ R◦…◦ R (n是正整数)  命题：(a,b)Rn当且仅当：存在t1 ,t2 ,…,tn-1A, 满足： (a,t 1 ),(t 1 ,t2 ),…,(tn-2 ,t n-1 ),(tn-1 ,b)R。  集合A上的关系R是传递关系 R 2R  必要性：任取(a,b) R2 ,根据上述命题以及R的传递性可得(a,b)R  充分性：若(a,b)R, (b,c)R, 则(a,c)R2 , 由R2R可得： (a,c)R，则R 是传递关系 关系的性质：传递性