二元关系, 数学上, 英語, binary, relation, 或简称关系, 用於讨论两种物件的连系, 诸如算术中的, 大於, 等於, 几何学中的, 相似, 或集合论中的, 之元素, 之子集, 目录, 定义, 集合的關係, 特殊的, 关系矩阵, 关系图, 运算, 性质, 闭包, 参见定义, 编辑實際上是以列舉二元有序对的方式去定義二元關係, displaystyle, nbsp, 也就是一個集合滿足, 對所有的, displaystyle, nbsp, 存在, displaystyle, nbsp, 且存在, d. 数学上 二元关系 英語 Binary relation 或简称关系 用於讨论两种物件的连系 诸如算术中的 大於 及 等於 几何学中的 相似 或集合论中的 为 之元素 为 之子集 目录 1 定义 2 集合的關係 3 特殊的二元关系 4 关系矩阵 5 关系图 6 运算 7 性质 8 闭包 9 参见定义 编辑實際上是以列舉二元有序对的方式去定義二元關係 R displaystyle R nbsp 也就是一個集合滿足 對所有的 r R displaystyle r in R nbsp 存在 x displaystyle x nbsp 且存在 y displaystyle y nbsp 使 r x y displaystyle r x y nbsp 或是以正式的邏輯符號表述為 r R x y r x y displaystyle forall r in R exists x exists y r x y nbsp 例一 有四件物件 球 糖 车 枪 及四个人 甲 乙 丙 丁 若甲擁有球 乙擁有糖 丙一無所有但丁擁有车 则 擁有 的二元关系可以寫為 R displaystyle R nbsp 球 甲 糖 乙 车 丁 其中二元有序对的第一项是被擁有的物件 第二项是擁有者 例二 實數系 R displaystyle mathbb R nbsp 上的 大於關係 可定義為 gt a b R 2 r R a b r r 0 displaystyle gt a b in mathbb R 2 exists r in mathbb R a b r wedge r neq 0 nbsp 由於習慣上 a b gt displaystyle a b in gt nbsp 通常都是寫為 a gt b displaystyle a gt b nbsp 更一般來說 不引起混淆的話會把 x y R displaystyle x y in R nbsp 簡寫成 x R y displaystyle xRy nbsp 集合的關係 编辑集合X displaystyle X nbsp 与集合Y displaystyle Y nbsp 上的二元关系則定義為 R X Y G R displaystyle R X Y G R nbsp 当中 G R X Y displaystyle G R subseteq X times Y nbsp 請參見笛卡儿积 称为 R displaystyle R nbsp 的图 若 x y G R displaystyle x y in G R nbsp 则称 x displaystyle x nbsp 与 y displaystyle y nbsp 有关系 R displaystyle R nbsp 并记作 x R y displaystyle xRy nbsp 或 R x y displaystyle R x y nbsp 但经常地我们把关系与其图等价起来 即若 R X Y displaystyle R subseteq X times Y nbsp 则 R displaystyle R nbsp 是一个关系 话虽如此 我们很多時候索性把集合間的關係 R displaystyle R nbsp 定义为 G R displaystyle G R nbsp 而 有序对 x y G R displaystyle x y in G R nbsp 即是 x y R displaystyle x y in R nbsp 特殊的二元关系 编辑设A displaystyle A nbsp 是一个集合 则 空集 displaystyle varnothing nbsp 称作A displaystyle A nbsp 上的空关系 E A A A displaystyle E A A times A nbsp 称作A displaystyle A nbsp 上的全域关系 完全關係 I A x x x A displaystyle I A x x x in A nbsp 称作A displaystyle A nbsp 上的恒等关系关系矩阵 编辑设X x 1 x 2 x n displaystyle X x 1 x 2 ldots x n nbsp 及Y y 1 y 2 y m displaystyle Y y 1 y 2 ldots y m nbsp R displaystyle R nbsp 是X displaystyle X nbsp 和Y displaystyle Y nbsp 上的关系 令 r i j 1 x i y j R 0 x i y j R displaystyle r ij begin cases 1 amp x i y j in R 0 amp x i y j notin R end cases nbsp 则0 1矩阵 r i j r 11 r 12 r 1 m r 21 r 22 r 2 m r n 1 r n 2 r n m displaystyle r ij begin bmatrix r 11 amp r 12 amp cdots amp r 1m r 21 amp r 22 amp cdots amp r 2m vdots amp vdots amp vdots amp vdots r n1 amp r n2 amp cdots amp r nm end bmatrix nbsp 称为R displaystyle R nbsp 的关系矩阵 记作M R displaystyle M R nbsp 关系图 编辑设A x 1 x 2 x n displaystyle A x 1 x 2 ldots x n nbsp R displaystyle R nbsp 是A displaystyle A nbsp 上的关系 令图G V E displaystyle G V E nbsp 其中顶点集合V A displaystyle V A nbsp 边集合为E displaystyle E nbsp 且对于任意的x i x j V displaystyle x i x j in V nbsp 满足 x i x j E displaystyle x i x j in E nbsp 当且仅当 x i x j R displaystyle x i x j in R nbsp 则称图G displaystyle G nbsp 是关系R displaystyle R nbsp 的关系图 记作G R displaystyle G R nbsp 运算 编辑关系的基本运算有以下几种 设R displaystyle R nbsp 为二元关系 R displaystyle R nbsp 中所有有序对的第一元素构成的集合称为R displaystyle R nbsp 的定义域 记作dom R displaystyle mbox dom R nbsp 形式化表示为dom R x y x y R displaystyle mbox dom R x exists y x y in R nbsp 设R displaystyle R nbsp 为二元关系 R displaystyle R nbsp 中所有有序对的第二元素构成的集合称为R displaystyle R nbsp 的值域 记作ran R displaystyle mbox ran R nbsp 形式化表示为ran R y x x y R displaystyle mbox ran R y exists x x y in R nbsp 设R displaystyle R nbsp 为二元关系 R displaystyle R nbsp 的定义域和值域的并集称作R displaystyle R nbsp 的域 记作fld R displaystyle mbox fld R nbsp 形式化表示为fld R dom R ran R displaystyle mbox fld R mbox dom R cup mbox ran R nbsp 设R displaystyle R nbsp 为二元关系 R displaystyle R nbsp 的逆关系 简称R displaystyle R nbsp 的逆 记作R 1 displaystyle R 1 nbsp 其中R 1 p x y x y R p y x displaystyle R 1 p exists x exists y x y in R wedge p y x nbsp 设F G displaystyle F G nbsp 为二元关系 G displaystyle G nbsp 與F displaystyle F nbsp 的合成關係记作F G displaystyle F circ G nbsp 其中F G x y t x t F t y G displaystyle F circ G x y exists t x t in F wedge t y in G nbsp 设R displaystyle R nbsp 为二元关系 A displaystyle A nbsp 是一个集合 R displaystyle R nbsp 在A displaystyle A nbsp 上的限制记作R A displaystyle R upharpoonright A nbsp 其中R A x y x y R x A displaystyle R upharpoonright A x y x y in R wedge x in A nbsp 设R displaystyle R nbsp 为二元关系 A displaystyle A nbsp 是一个集合 A displaystyle A nbsp 在R displaystyle R nbsp 下的像记作R A displaystyle R A nbsp 其中R A ran R A displaystyle R A mbox ran R upharpoonright A nbsp 设R displaystyle R nbsp 为A displaystyle A nbsp 上的二元关系 在右复合的基础上可以定义关系的幂运算 R 0 I A displaystyle R 0 I A nbsp R n 1 R n R displaystyle R n 1 R n circ R nbsp 性质 编辑关系的性质主要有以下五种 自反性 x A x x R displaystyle forall x in A x x in R nbsp 在集合X上的关系R 如对任意x X displaystyle x in X nbsp 有 x x R displaystyle x x in R nbsp 则称R是自反的 非自反性 自反性的否定的強型式 x A x x R displaystyle forall x in A x x notin R nbsp 在集合X上的关系R 如对任意x X displaystyle x in X nbsp 有 x x R displaystyle x x notin R nbsp 则称R是非自反的 对称性 x y A x y R y x R displaystyle forall x y in A x y in R implies y x in R nbsp 在集合X上的关系R 如果有 x y R displaystyle x y in R nbsp 且x y displaystyle x neq y nbsp 必有 y x R displaystyle y x in R nbsp 则称R是对称的 反对称性 不是對稱性的否定 x y A x y R y x R x y displaystyle forall x y in A x y in R wedge y x in R implies x y nbsp 非對稱性 對稱性的否定的強型式 x y A x y R y x R displaystyle forall x y in A x y in R implies y x notin R nbsp 非對稱性是 滿足非自反性的反對稱性 传递性 x y z A x y R y z R x z R displaystyle forall x y z in A x y in R wedge y z in R implies x z in R nbsp 设R displaystyle R nbsp 为集合A displaystyle A nbsp 上的关系 下面给出R displaystyle R nbsp 的五种性质成立的充要条件 R displaystyle R nbsp 在A displaystyle A nbsp 上自反 当且仅当I A R displaystyle I A subseteq R nbsp R displaystyle R nbsp 在A displaystyle A nbsp 上非自反 当且仅当R I A displaystyle R cap I A emptyset nbsp R displaystyle R nbsp 在A displaystyle A nbsp 上对称 当且仅当R R 1 displaystyle R R 1 nbsp R displaystyle R nbsp 在A displaystyle A nbsp 上反对称 当且仅当R R 1 I A displaystyle R cap R 1 subseteq I A nbsp R displaystyle R nbsp 在A displaystyle A nbsp 上非對稱 当且仅当R R 1 displaystyle R cap R 1 emptyset nbsp R displaystyle R nbsp 在A displaystyle A nbsp 上传递 当且仅当R R R displaystyle R circ R subseteq R nbsp 闭包 编辑设R displaystyle R nbsp 是非空集合A displaystyle A nbsp 上的关系 R displaystyle R nbsp 的自反 对称或传递 闭包是A displaystyle A nbsp 上的关系R displaystyle R nbsp 满足 R displaystyle R nbsp 是自反的 对称的或传递的 R R displaystyle R subseteq R nbsp 对A displaystyle A nbsp 上任何包含R displaystyle R nbsp 的自反 对称或传递 关系R displaystyle R nbsp 有R R displaystyle R subseteq R nbsp 一般将R displaystyle R nbsp 的自反闭包记作r R displaystyle r R nbsp 对称闭包记作s R displaystyle s R nbsp 传递闭包记作t R displaystyle t R nbsp 下列三个定理给出了构造闭包的方法 r R R R 0 displaystyle r R R cup R 0 nbsp s R R R 1 displaystyle s R R cup R 1 nbsp t R R R 2 R 3 displaystyle t R R cup R 2 cup R 3 cup cdots nbsp 对于有限集合A displaystyle A nbsp 上的关系R displaystyle R nbsp 存在一个正整数r displaystyle r nbsp 使得 t R R R 2 R r displaystyle t R R cup R 2 cup cdots cup R r nbsp 求传递闭包是图论中一个非常重要的问题 例如给定了一个城市的交通地图 可利用求传递闭包的方法获知任意两个地点之间是否有路相连通 可以直接利用关系矩阵相乘来求传递闭包 但那样做复杂度比较高 好一点的办法是在计算矩阵相乘的时候用分治法降低时间复杂度 但最好的方法是利用基于动态规划的Floyd Warshall算法来求传递闭包 参见 编辑有序对 二元集合 笛卡儿积 偏序关系 等价关系 相容关系 取自 https zh wikipedia org w index php title 二元关系 amp oldid 72673988 关系图, 维基百科,wiki,书籍,书籍,图书馆,