一、关系的基本概念及其性质
1、关系的概念
二元关系：
定义：设A和B是两个集合，A×B的任一子集R称为从A到B的一个二元关系。
如果(a,b)∈R，则a与b符合关系R，记为aRb；
如果(a,b) R，则a与b不符合关系R，记为aRb。
如果A=B，则称R为A上的二元关系。
性质： 若|A|=m，|B|=n，则|A×B|=m×n，A×B共有2m×n个子集，所以从A到B的二元关系共有2m×n个。
A×B也是从A到B的二元关系（全域关系）。
A×A上的任意子集都是A上的一个关系
若|A|=n，则A上的关系有2n2个
空集Φ称为从A到B的空关系。
集合{(a,a)|a∈A}//代码效果参考：http://www.ezhiqi.com/bx/art_1509.html称为A上的恒等关系或相等关系，记为IA。
全域关系：EA=A×A
RC=A×A-R
序对（a,b）=(c,d)的充要条件是a=c,b=d
定义：设二元关系R?A×B，集合{x|x∈A且?y∈B使(x,y)∈R}称为R的定义域，并记为dom(R)；集合{y|y∈B且 ?x∈A使(x,y)∈R}称为R的值域，并记为ran(R)。
一般地，dom(R)?A，ran(R)?B。
n元关系：
定义：设A1，A2，…，An是n个集合，A1×A2×…×An的一个子集R称为A1，A2，…，An间的一个n元关系，每个Ai称为R的一个域。
2、关系矩阵和关系图
关系矩阵
定义：设有穷集合A={a1，a2，…，an}和B={b1，b2，…，bm}，R是从A到B的一个二元关系，R的关系矩阵定义为一个矩阵M=(mij)，其中
从有穷集合A到有穷集合B的二元关系R用图表示时，首先用点表示A和B的元素，并在旁边标注元素的名字，然后用从点x到点y的矢线表示R中的序对(x,y)。若(x,x)∈R，则画一条从点x指向自身的线，称为环。这样由点和线组成的有向图称为R的关系图。
关系的并、交、差、余：
集合的并、交、差、余运算的性质对关系运算也成立。
作为关系时，余运算是对全域关系而言的，即将A×B作为全集E
3、偏序的性质
自反
定义：集合A上的二元关系R称为自反的，如果?x∈A，有xRx。
说明： 在这个定义中要求A的每个元素x，都有xRx，即(x,x)∈R， 这并不排斥某个序对(x,y)，当x≠y时，仍有(x,y)∈R。 显然，R是自反的，当且仅当IA?R。（R-1也是自反的）
反自反
定义：集合A上的二元关系R称为反自反的，如果?x∈A，有xRx都不成立。
R是反自反的，则IA∩R=?
说明：非空集合上的一个二元关系是自反的，必不是反自反的，反之亦然。 一个二元关系不是自反的，未必是反自反的，反之亦然。 即存在既不是自反的，也不是反自反的二元关系。
对称
定义：集合A上的二元关系R，如果?x，y∈A，只要xRy就有yRx，则称R是对称的。（R-1=R）
反对称
定义：集合A上的二元关系R，对?x，y∈A，如果xRy且yRx，则x=y，则称R是反对称的。（如果xRy，则yRz,除非x=y时有yRx成立）（R∩R-1?IA）
关于对称与反对称的说明： 二元关系的对称性和反对称性不是矛盾的 存在既是对称的，也是反对称的二元关系
传递
定义：集合A上的二元关系R，对? x，y，z∈A，如果xRy且yRz，则xRz，那么称R是传递的。
具有某种性质的关系的关系矩阵、关系图的特点
关系矩阵
(1)R是自反的，当且仅当M的对角线上的全部元素均为1。
(2)R是反自反的，当且仅当M的对角线上的全部元素为0。
(3)R是对称的，当且仅当M是对称矩阵。
(4)R是反对称的，当且仅当i≠j时M中元素mij与mji不同时为1。
(5)R是传递的，当且仅当M中的元素mij=1且mjk=1时必有mik=1。
关系图
(6)R是自反的，当且仅当G的每个顶点上均有一个环。
(7)R是反自反的，当且仅当G中没有环。
(8)R是对称的，当且仅当G中任两不同的顶点之间如果有矢线，则必有两条方向相反的矢线。
(9)R是反对称的，当且仅当G中任两顶点之间最多有一条矢线。
(10)R是传递的，当且仅当G从某顶点i沿矢线方向经两条矢线可到达另一顶点j，则必有从顶点i到顶点j的矢线。
4、复合关系和逆关系
复合关系：
定义：设R是A到B的二元关系，S是B到C的二元关系，则R与S的复合关系为一个从A到C的二元关系，记为R?S。 R?S={(x,z)|x∈A，z∈C， ?y∈B使xRy且yRz}
关系的复合运算不满足交换律，也不满足幂等律，但是关系的复合运算满足结合律。
设R，S，T分别是集合A到B，B到C，C到D的二元关系，则(R?S)?T=R?(S?T)。
幂的定义：设R是A上的一个二元关系，递归地定义R的非负整数次幂为：
R0=IA，R1=R，Rn+1=Rn?R
定理：设R是A上的一个二元关系，对任意的非负整数m，n，有 Rm?Rn=Rm+n，(Rm)n=Rmn
设A是一个有限集且|A|=n，R是A上的一个二元关系，则存在非负整数s，t，使0≤s＜t≤2n2 且Rs=Rt。
定理：设R是A到B的二元关系，则 IA?R=R?IB=R
定理：设R1是A到B的二元关系，R2和R3是B到C的二元关系，R4是C到D的二元关系，则
(1)R1?(R2∪R3)=(R1?R2)∪(R1?R3)
(2)R1?(R2∩R3)=(R1?R2)∩(R1?R3)
(3)(R2∪R3)?R4=(R2?R4)∪(R3?R4)
(4)(R2∩R3)?R4=(R2?R4)∩(R3?R4)
复合运算的矩阵实现
设R和S都是A到B的二元关系，其关系矩阵分别为MR和MS，R∪S与R∩S的关系矩阵分别记为MR∪S和MR∩S，易证明： MR∪S=MR∨MS，MR∩S=MR∧MS。
设R是A到B的二元关系，S是B到C的二元关系，其关系矩阵分别为MR和MS，R?S的关系矩阵MR?S，易证明： MR? S=MR?MS。
集合A上的关系R具有传递性的充要条件是R○R?R
逆关系
定义：设R是从A到B的二元关系，则从B到A的二元关系R-1={(y,x)|(x,y)∈R}称为R的逆关系。
定理：设R是A到B的二元关系，则(R-1)-1=R。
定理：设R和S分别是A到B、B到C的二元关系，则 (R?S)-1= R-1?S-1
逆运算的矩阵实现
关系R-1的关系矩阵 是关系R的关系矩阵MR的转置矩阵，即 =(MR)T。
关系的闭包
传递闭包
定义：设R是A上的一个二元关系，A上一切包含R的传递关系的交称为R的传递闭包，记为R+。
说明：R+是包含R的那些传递关系中最小的那个关系。
定理：二元关系R的传递闭包R+是传递关系。
定理：设R是A上的一个二元关系，则
定理：设A是n元集，R是A上的一个二元关系，则
传递闭包的矩阵运算实现，即：
自反传递闭包
定义：设R是A上的一个二元关系，A上包含R的所有自反且传递的二元关系的交称为R的自反传递闭包，记为R。
定理：设R是A上的一个二元关系，则 R=R0∪R+
自反闭包
定义：A上包含R的所有自反关系的交，记为r(R)，易知 r(R)=R0∪R 而且R是自反的，当且仅当r(R)=R。
对称闭包
定义：A上包含R的所有对称关系的交，记为s(R)，易知 s(R)=R∪R-1 而且R是对称的，当且仅当s(R)=R。
