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