离散数学 关系的性质.ppt

《离散数学 关系的性质.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、14.3关系的性质关系的性质及特点关系性质的充要条件关系性质的证明运算和性质的关系21.自反的二元关系(1).定义：R是Ａ上的二元关系，若x(x∈A→R),则称R在A上是自反的二元关系。例如Ａ＝｛a,b,c｝,R={(a,a),(b,b),(c,c),(a,b)}，则Ｒ是自反的。又如Ａ＝｛1,2,3｝,R是Ａ上的整除关系，显然，Ｒ是自反的，因为（1,1）,（2,2）,（3,3）都属于R。即如果对于Ａ中的每一个元素a,都有(a,a)∈R，则称Ｒ为自反的二元关系。一、关系的性质及特点3注意，在关系的自反性定义中，要求对于A

2、中的每一个元素a都有(a,a)∈R。所以当A={a,b,c}，而R={(a,a),(b,b)}时，R并不是自反的，因为(c,c)R。又如A={1,2,3}，R是A上的二元关系，当a,b∈A，且a和b都是素数时，(a,b)∈R。可见Ｒ＝{(2,2),(3,3),(2,3),(3,2)}，Ｒ也不是自反关系，因为(1,1)R。4(2).关系矩阵的特点：关系矩阵中主对角线上的元素全为1。(3).关系图的特点：关系图中每个顶点都有环。实例：A上的全域关系EA,恒等关系IA，小于等于关系LA,整除关系DA都是自反关系：52．反自反的二元关系

3、(1).定义：R是Ａ上的二元关系，若x(x∈A→R),则称R在A上是反自反的二元关系.例如Ａ＝｛a,b,c｝,R={(a,b),(b,c),(b,a)}，则Ｒ是反自反的。又如Ａ＝｛1,2,3｝,R是Ａ上的小于关系，即当a

4、于Ａ中的每一个元素a,都有(a,a)R，则称Ｒ为反自反的二元关系。6实例：实数集上的小于关系，空关系，幂集上的真包含关系都是反自反关系。(2).关系矩阵的特点：关系矩阵中主对角线上的元素全为0。(3).关系图的特点：关系图中每个顶点都没有环。7例1A={1,2,3},R1,R2,R3是A上的关系,其中R1＝{<1,1>,<2,2>}R2＝{<1,1>,<2,2>,<3,3>,<1,2>}R3＝{<1,3>}R1既不是自反也不是反自反的R2为自反关系,R3为反自反关系。83.对称的二元关系(1).定义:R是Ａ上的

5、二元关系，若x，y(x,y∈A∧∈R→∈R),则称R为A上对称的二元关系.例如Ａ={a,b,c,d},R={(a,a),(a,b),(b,a),(b,d),(d,b)}则Ｒ是对称的二元关系。又如Ａ={1,2,3,4,5},对于Ａ中元素a和b,如果a,b是模3同余关系，则(a,b)∈Ｒ,易见Ｒ是对称关系。即如果(a,b)∈R,就一定有(b,a)∈R,则称Ｒ为对称的二元关系。9实例：A上的全域关系EA,恒等关系IA和空关系都是对称关系。(2).关系矩阵的特点：关系矩阵为对称矩阵。(3).关系图的特点：关系图中如果

6、两个顶点之间有边一定是一对方向相反的边。104．反对称的二元关系即R是Ａ上的二元关系，每当有(a,b)∈Ｒ和有(b,a)∈Ｒ时，必有a=b,则称Ｒ是反对称的二元关系。反对称的定义也可写为：Ｒ是Ａ上的二元关系，当a≠b时，如果(a,b)∈Ｒ,则必有(b,a)R,称Ｒ为反对称的二元关系。例如Ａ={1,2,3},R是Ａ上的小于关系，即a

7、x,y>∈R∧∈R→x=y),则称R为A上的反对称关系.11注意，“对称的”和“反对称的”这两个概念并非相互对立，相互排斥的。存在着既不是对称的又不是反对称的二元关系，也存在着既是对称的又是反对称的二元关系。又如A={a,b,c},R={(a,a)},可知Ｒ是对称的，又是反对称的。因为虽有(a,b)∈R,(b,a)∈R，但(c,d)∈R时(d,c)R,因此R不是对称的，例如A={a,b,c,d}R={(a,b),(b,a),(c,d)}这里R既不是对称的，也不是反对称的。因为有(a,b)∈R和(b,a)∈R，因此R不是反对

8、称的。12实例：恒等关系IA，空关系都是A上的反对称关系。(2).关系矩阵的特点：关系矩阵中以主对角线对称的元素不能同时为1。(3).关系图的特点：关系图中如果两个顶点之间有边一定是一条有向边。13例2设A＝{1,2,3},R1,R