下载文档原格式
1二元关系1. 有序对与笛卡尔积定义1.1 两个对象x , y 组成的满足如下性质的二元组(x , y )：(x , y )=(u,v ) 当且仅当x=u , y=v其中x 称为第一元素，y 称为第二元素。
定义1.2 集合A 和B 的笛卡尔积定义为{(,)|,}A B x y x A y B ⨯=∈∈特别地，若A 或者B 是空集，则A ×B 是空集。
例：注意：笛卡尔积不满足结合律和交换律。
2. 二元关系定义2.1 若A 和B 是集合， 则A ×B 的任何子集R 称为从A 到B 的二元关系，简称关系。
若(,)x y R ∈，则称有序对(x , y )满足关系R ，一般记为xRy .定义域dom(R )=值域ran(R )=集合C 在R 下的像：R [C]=例2.2 设集合R ={(a,1),(a,2), (b,2),(b,3)}，则该集合可视为从{a,b}到{1,2,3}的二元关系，其定义域和值域为dom(R )={a,b}ran(R )={1,2,3}定义2.3（关系矩阵）M R 是由真值组成的0-1矩阵。
例2.4关系图：G R 是一个二部图（bipartite ）。
定义2.4 若R 是从集合A 到A 的二元关系，即R A A ⊆⨯，则称R 是A 上的二元关系。
定义2.5 集合A 上的三种特殊关系：（1） 空关系：∅ 其矩阵是0方阵。
（2） 全关系：E A =A ×A 其矩阵是全1方阵。
（3） 恒等关系：{(,)|}A I x x x A =∈，其矩阵是单位矩阵。
23. 二元关系的几种运算我们考虑对于二元关系的如下运算，即并、逆、复合、方幂和限制。
定理3.1 设R ，Q 是从A 到B 的二元关系，则R Q R Q M M M =+U注意：其中的加法是真值加法，即逻辑或，即0+0=0, 1+1=1，1+0=1，0+1=1证明： 证毕定义3.2（二元关系的逆）设R 是从A 到B 的二元关系。
第四章 二元关系学习指导4.1 二元关系一、有序对有序对 设为任意两个集合，元素和b 分别取自和,A B a A B 。
和b 依一定次序组成一对，称为有序对，记为，其中称为它的第一元素，b 称为它的第二元素。
a (,)ab a 两有序对相等 (,当且仅当a )(,)a bcd =c =且b d =。
有序元组 有序元组是一个有序对，它的第一元素为有序元组，第二元素为，记为(3n n .))n (3n n .1n −121(,,,)n a a a − n a 12121(,,,)((,,,),)n n a a a a a a a −= 。
笛卡尔积 设A 和B 为任意的两个集合。
称所有由中元素作为第一元素，A B 中元素作为第二元素的有序对组成的集合为和A B 的笛卡尔积，记作A B ×，即{}(,)A B a b a A b B ×=∈∧∈二、二元关系和元关系n二元关系 设和A B 是任意的两个集合，A B ×的子集R 称为到A B 的一个二元关系。
当时，则称A B =R 为上的二元关系。
二元关系简称为关系。
对于某个关系A R ，如果，那么称和b 有关系(,)a b R ∈a R ，记为；如果aRb (,)a b R ∈，那么称a 与没有关系b R ，记为aRb 。
/空关系 如果，那么称R =∅R 为空关系； 全关系 如果R A B =×，那么称R 为全关系。
恒等关系 {}I (,)A a a a A =∀∈;整数集合上的模ｎ同余关系 设（整数集合），对于给定的正整数ｎ，Ａ上的模ｎ同余关系Ｒ为A ⊆Z {}(,)(,)a bR a b a b a b n n 为整数是的整数倍⎧−⎫==−⎨⎬⎩⎭{}(,)(mod )a b a b n =≡。
定义域和值域 设Ｒ是集合Ａ到Ｂ的二元关系，分别定义Ｒ的定义域dom R 和值域ran R 为：{}{}dom ()((,);ran ()((,))R a b b B a b R R ba a A ab R =∃∈∧∈=∃∈∧∈。
二元关系的矩阵和图表示
两个事物之间的关系称之为二元关系。
在数学上，二元关系指的是这样的一个集合S，它的所有元素都为二元有序对。
它反映的是有序对中第一个元素组成的集合与第二个元素组成的集合之间的关系。
举个例子，集合S={<天秤座,libra>,<狮子座,leo>}就表示了中文集合{天秤座,狮子座}与英文集合{libra,leo}之间的对应关系。
二元关系可以用集合表示，就像我们上面提到的。
而除此之外，还可以用其他数学工具来描述它——矩阵和图。
矩阵的基本元素是数字及其所处的位置。
直觉上，我们很自然的想到用它的下标来体现两个集合中的元素，用数字体现它们是否具有关系。
这便得出了以下定义：【定义】设集合A={x1,x2,…,x m},B={y1,y2,…,y n}，R为A,B之间的二元关系。
称矩阵M(R)=(r ij)m×n为R的关系矩阵，其中
这样我们定义了一个映射，把集合R映射为一个矩阵M。
如此定义，首先保证了R的集合表达式和R的关系矩阵是一一对应的。
其次，这样的定义会带来很多好的性质。
我们可以应用矩阵的语言把整个二元关系的理论重新叙述一遍：(1)关系R的逆，记作R-1，表示的是集合{<x,y>|<y,x>εR}，我们有
M(R-1)=(M(R))T
这样，我们求关系的逆就转化为了求一个矩阵的转置矩阵。
(2)两个关系的合成(复合)，记作R2•R1,表示的是集合
为了用矩阵表示关系的合成，我们可以定义{0,1}中元素的加法为逻辑加法
(0+0=0,0+1=1,1+0=1,1+1=1)，于是便有
M(R2•R1)=M(R1)•M(R2)
这样，关系的合成这一运算就转化为了矩阵的相乘。
(3)同理，R在D上的限制就等价于找M(R)中相应行中为1的元素；D在R下的
象就等价于M(R)中相应行为1的元素的列坐标。
(4)关系R是单根的，指的是对任意的yεranB,存在唯一的xεdomR，使得<x,y>εR。
这意味着M(R)的每一列有且仅有一个1
(5)关系R是单值的，指的是对任意的xεdomR,存在唯一的yεranB，使得<x,y>εR。
这意味着M(R)的每一行有且仅有一个1
特殊的，集合A上的二元关系R指的是A×A={<x,y>|xεA,yεA}。
这样像前面第二条性质就有M(R2)=(M(R))2
(1)自反的二元关系R相应的关系矩阵主对角线元素都为1
(2)反自反的二元关系R相应的关系矩阵主对角线元素都为0
(3)对称的二元关系R相应的关系矩阵也是对称的
(4)反对称的二元关系R相应的关系矩阵也是反对称的(这里定义1的反为0)
(5)对传递的二元关系R，相应的关系矩阵R中若r ij=1,r jk=1，则r ik=1
(以上黑体字的定义有不熟悉的请查阅wiki)
等价关系R(同时具有自反，对称，传递性质的二元关系)可以确定集合A上的一个划分，那么如何从关系矩阵中找出相应的等价类？(如下图)
如何用图来表示等价关系呢？由于关系中的元素是有序对，直觉上，我们很自然的想到用有向图。
于是定义如下：
【定义】设集合A={x1,x2,…,x m},B={y1,y2,…,y n}，R为A,B之间的二元关系。
以A,B中的元素为顶点，若<x i,y j>εR，则从顶点x i向y j引有向边，称所画出的图
G(R)为R的关系图。
这样，我们就可以用图论的语言把整个二元关系的理论重新叙述一遍：
(1)R的逆：只需把图中的箭头反向
(2)两个关系的合成：通过过渡集合把两个图拼接为一个图，然后把长为2的有
向通路变为起点指向终点的长为1的有向通路
(3)R在D上的限制就等价于找G(R)中起点包含在集合D中的部分；D在R下的象就等价于G(R)中包含在集合D中的起点所指向的终点
(4)关系R是单根的，指B中顶点的入度均为1
(5)关系R是单值的，指A中顶点的出度均为1
特殊的，集合A上的二元关系R对应的关系图将为多重图(有重边和环的出现)。
(1)自反的二元关系R相应的关系图每个顶点处都有环
(2)反自反的二元关系R相应的关系图每个顶点处都无环
(3)对称的二元关系R相应的关系图中两个顶点间如果存在有向边，必有两条反向的有向边
(4)反对称的二元关系R相应的关系图中两个顶点间的有向边必是单重的
(5)对传递的二元关系R，相应的关系图中长度为2的有向通路的起点和终点间必存在由起点指向终点的有向线段
如何从关系图中找出一个等价关系所确定的划分？
对于二元关系中的其他一些理论(如闭包和序关系)，用关系矩阵和关系图描述一下试试。
我们经常把一件事物抽象为数学模型来表达。
有时换一种数学工具可能在处理某些运算时给我们带来方便。
用不同的工具思考，能更深刻的理解数学各个分支之间的联系。
参考资料：《集合论与图论》耿素云。
