《关系的性质与闭包》PPT课件.ppt

《《关系的性质与闭包》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、关系的性质与闭包离散数学第4讲上一讲内容的回顾集合的笛卡尔乘积有序对-一种特殊的集合笛卡尔乘笛卡尔乘积的性质二元关系的定关系的运算一般集合运算与定义域或值域有关的运算逆运算复合运算(乘法)二元关系的性质与闭包关系的几类重要性质自反对称传递性质满足的充分必要条件性质与运算之间的关系闭包的定义与存在性计算关系R的传递闭包的Warshall算法自反性集合A上的关系R:自反：定义为：对所有的aA,(a,a)R反自反：定义为：对所有的aA,(a,a)R设A={1,2,3},RAA{(1,1),(1,3),(2,2),(2,1),(3

2、,3)}是自反的{(1,2),(2,3),(3,1)}是反自反的{(1,2),(2,2),(2,3),(3,1)}既不是自反的，也不是反自反的R是A上的自反关系iff.IAR自反关系的关系图和关系矩阵abcA={a,b,c}对称性集合A上的关系R：对称的：定义为：若(a,b)R,则(b,a)R反对称的：定义为：若(a,b)R且(b,a)R，则a=b强反对称的：定义为：若(a,b)R则(b,a)R(注意：反对称和强反对称都不是对称的否定)设A={1,2,3},RAA{(1,1),(1,2),(1,3),(2,1),(3

3、,1),(3,3)}是对称的{(1,2),(2,3),(2,2),(3,1)}是反对称的{(1,2),(2,3),(3,1)}既是反对称的，也是强反对称的{(1,1),(2,2)}既是对称的，也是反对称的是对称关系，也是反对称关系，也是强反对称关系！R是集合A上的对称关系iff.R-1=R对称关系的关系图和关系矩阵abcA={a,b,c}传递性集合A上的关系R：传递的：定义为：若(a,b)R,(b,c)R,则(a,c)R设A={1,2,3},RAA{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(

4、3,3)}传递的{(1,2),(2,3),(3,1)}是非传递的Both{(1,3)}和均为传递关系集合A上的关系R是传递关系iff.RnR对所有n1成立传递关系的关系图和关系矩阵abcA={a,b,c}一些常用关系的性质=<

5、3E自反反自反对称反对称传递正确理解自反关系一个错误的命题及其“证明”:如果R是集合A上的对称，传递关系，则R是A上的自反关系证明:对任意的a,bA,若(a,b)R,根据R的对称性(b,a)R;又根据R的传递性,(a,a)

6、R.所以：R是自反关系逆关系运算对关系性质的保持自反性:x,(x,x)R1(x,x)R1-1反自反性:x,(x,x)R1(x,x)R1-1对称性:x,y,if(x,y)R1-1,then(y,x)R1,sinceR1issymmetric，(x,y)R1,∴(y,x)R1-1强反对称性:x,y,if(x,y)R1-1,(y,x)R1-1,then(y,x)R1,(x,y)R1,sinceR1isantisymmetric，x=y.传递性:x,y,z,if(x,y)R1-1,(y,z)R1-1,

7、then(y,x)R1,(z,y)R1,sinceR1istransitive，(z,x)R1,∴(x,z)R1-1关系的交运算对运算性质的保持自反:x,∵(x,x)R1,(x,x)R2,∴(x,x)R1R2反自反:supposingx,(x,x)R1R2,then(x,x)R1,(x,x)R2,contradiction.对称:x,y,(x,y)R1R2(x,y)R1,(x,y)R2，sinceR1andR2aresymmetric，(y,x)R1,(y,x)R2,∴(y,x)R1R2

8、.反对称:x,y,supposing(x,y)R1R2,(y,x)R1R2,then(x,y),(y,x)R1,and(x,y),(y,x)R2,sinceR1andR2arebothasymmetric，x=y传递:x,y,z,if(x,y)R1R2,(y,z)R1R2,then(x,y),(y,z)R1,and(x,y),(y,z)R2,sinceR1andR2arebothtransitive,(x,z)R1,and(x,z)R2,∴(x,z)R1R2关系的并运算对关系性质的保持自反:x,∵

9、(x,x)R1,(x,x)R2,∴(x,x)R1R2反自反:supposingthatx,(x,x)R1R2,then(x,x)R1or(x,x)R2,butR1andR2areirreflexive对