二元关系

2019/7/21 15:10:51 人评论 次浏览 分类:学习教程

五种关系的性质:

1.自反

   定义:    \large \forall x(x\in A\rightarrow <x,x>\in R)

   集合表达式: \large I_{A} \subseteq R

   关系矩阵:主对角线都为1

   关系图: 每个顶点都有自环

 

2.反自反

   定义:  \large \forall x(x\in A \rightarrow<x,x>\notin R)

   集合表达式: \large I_{A}\cap R =\varnothing

  关系矩阵:主对角线都为0

  关系图: 所有顶点都没有自环

 

3.对称

   定义: \large \forall x,y(x ,y\in A \wedge <x,y> \in R \rightarrow<y,x>\in R)

   集合表达式: \large R=R^{-1}

   关系矩阵: 矩阵是对称矩阵

   关系图: 所有边都是双向边

 

4.反对称

   定义:   \large \forall x,y(x ,y\in A \wedge <x,y> \in R \wedge <y,x>\in R \rightarrow x=y)

   集合表达式: \large R\cap R^{-1} \subseteq I_{A}

   关系矩阵: \large r_{i,j} 为1 且 \large i\neq j ,则 \large r_{j,i} 为 0

   关系图 :所有的边均为单边(可存在部分自环)

 

5.传递

    定义:

  \large \forall x,y,z(x,y,z\in A \wedge <x,y> \in R \wedge <y,z>\in R \rightarrow <x,z>\in R)

   集合表达式: \large R\cdot R\subseteq R

   关系矩阵: 对于 \large M^{2} 中为1的位置,在\large M中相应位置都为1

   关系图: 如定义描述

 

 

偏序关系

  如果关系R满足 自反性,反对称性,传递性,我们称关系R 为 偏序关系, 记为 \large \preceq

 

全序关系

   如果 A 中的 任意两个元素都是可比 ( \large x\preceq y \vee y\preceq x), 则称关系R为 全序关系

   正例: 小于等于关系   

   反例:整除关系,集合的包含关系

 

哈斯图:

描述偏序关系的关系图

 

覆盖:

 两者的偏序关系最近,中间不能加入别的点

 

最小元: 隐藏和集合中所有元素都可比的条件

极小元:没有和集合中的所有元素都可比的条件

 

拓扑排序: 每次选择极小元,删除极小元之后再次出现极小元

 

 

 

 

 

 

 

相关资讯

    暂无相关的资讯...

共有访客发表了评论 网友评论

验证码: 看不清楚?
    -->