第七节 关系的性质 定义7.1(自反性) 设R是集合A上一个二 元关系, 如果对每个xA, 都有xRx, 则称R在 A上是自反的. 即R在A上自反的(x)(xAxRx).例如 实数集的“”关系是自反的.此外,从关系的关系矩阵以及关系图也很容易对自 反性加以判断.一个关系有自反性的充分必要条 件是它的关系矩阵的主对角线的元素全都是1;一 个关系有自反性的充分必要条件是它的关系图中 每个顶点(即集合的每个元素对应画出的小圆圈) 都有一条自回路(也称为一个环，即出发点和终 点是同一个点的边).定义7.2(反自反性) 设R是集合A上一个二元 关系, 如果对每个xA, 都有R, 则称 R在A上是反自反的.R在X上是反自反的(x)(xXR).反自反性也很容易从关系矩阵和关系图中看出来.一个关系有反自反性的充分必要条件是它的关系 矩阵的主对角线上所有的元素全都是0;一个关系有反自反性的充分必要条件是它的关系图中每个顶 点都没有自回路.定义7.3(对称性) 设R是集合A上一个二元 关系, 如果对每一对元素x, yA,当xRy时, 就有yRx, 则称R在A上是对称的.即R在A上是对称的 (x)(y)(xA)(yA)(xRy)yRx).对称性很容易从关系矩阵和关系图中看出来.一个关系有对称性的充分必要条件是它的关系矩阵是 一个对称阵;一个关系有对称性的充分必要条件是它的关系图中任意两个结点之间要么没有有向边 相连,要么恰有一对方向相反的有向边相连.定义7.4 (反对称性)设R是集合A上的二元 关系,如果对每一对x, yA, 当xRy和yRx同时 成立时, 必有x=y, 则称R在A上是反对称的.即R在X上是反对称的 (x)(y)(xX)(yX)(xRy)(yRx)(x=y).反对称性也很容易从关系矩阵和关系图中看出来.一个关系有反对称性的充分必要条件是它的关系 矩阵中关于主对角线对称的任何一对元素要么两 个数都是0,要么一个数是0而另一个数是1,或者换 句话说:关于主对角线对称的任意一对数中至多 只能有一个元素是1;类似地,一个关系有反对称性的充分必要条件是它的关系图中任意两个结点之 间至多只有一条有向边相连.定义7.5(传递性) 设R是集合A上的二元关系, 如果对每个x, y, zX, 当xRy且yRz 时就有xRz, 则 称R在A上是可传递的. R在X上是可传递的 (x)(y)(z)(xXyXzXxRyyRzxRz);例如, 实数集的关系“, , , , (不可传递) R2=, , , (可传递) R3=, (可传递) R4=(可传递)要想通过关系矩阵或者关系图来判断一个给 定的关系有没有传递性是比较困难和复杂的.(注) (1)有自反性的关系一定没有反自反性,有反自反性 的关系也一定没有自反性,这说明自反性与反自 反性不可能共存于同一个关系之中.但是有这样 的关系存在,它既不是自反的,也不是反自反的. (2)对称性和反对称性有可能共存于同一个关系之 中.同时也存在这样的关系,它既不是对称的,也不 是反对称的.请读者举出相应的例子来说明上面注解中的 结论.例1. 给定一个非空集合A,试讨论集合A上的全域关 系AA以及空关系的性质. 解: (1)全域关系显然有自反性、对称性和传递性.但显 然没有反自反性.至于反对称性,要看集合的元素个 数而定.情形一.如果|A|=1,那么显然它上面的全域关系 有反对称性.情形二.如果|A|1,那么显然它上面的全域关系 没有反对称性. (2)因为A是非空集合,所以容易验证A上的空关系有 对称性、传递性、反自反性、反对称性,但没有自 反性.例2给定一个非空集合A=a,b,c,d,试计算 (1)A上所有有自反性的二元关系的个数; (2)A上所有有反自反性的二元关系的个数; (3)A上所有有对称性的二元关系的个数. 解:(1)有自反性的关系必须含有 , 这四个序偶,而16-4=12, 所以A上所有有自反性的二元关系的个数等于. (2)有反自反性的关系必须不含有,这四个序偶中的任何一个,所以A上所有有反自反 性的二元关系的个数同样等于212.(3)除了,这四个序偶之外 (任何有对称性的关系可以不含这四个序偶中的 任何一个,也可以含有这四个序偶中的任意个数), 对AA中剩下的16-4=12个序偶,一个有对称性的 关系在含有其中任何一个序偶的同时,必须 同时含有序偶.所以这12个剩下的序偶必须 两两分成6对,每一对视为一个不可分割的整体,这 样可以将AA中全部16个序偶视为4+6=10个独立 的“元素体”,一个有对称性的关系可以含有这10 个“元素体”中任意多个,从而一共有210个有对称 性的二元关系.第八节关系的运算, 复合关系和逆关系从现在起,我们要陆续介绍关系的各种运算. 首先,关系是一种集合,因而可以对关系运用集合 的各种运算.例如,如果R1和R2是同一个集合A上 的两个二元关系,那么它们就都是集合AA的子 集合.我们可以对它们作以前介绍过的集合之间 的任何一种运算(例如集合的并、交、差、对称 差等等),显然得到的结果仍然是集合AA的子集 合,从而仍然是A上的一个二元关系.请看下面的 例子:例1.在第6节的例1中,我们分别取模k=4和k=6 ,得到 整数集合上分别关于模4和模6的两个不同的同余 关系,分别记这两个关系为R1和R2.问题:试计算R1R2. 解:根据关于模k同余的一般性定义有(参见第6节例 1)xy(modk) k|(x-y).分别取k=4和k=6我们得到:(1)在关系R1中R1 4|(x-y). (2)在关系R2中R2 6|(x-y).合起来得到R1 R2 12|(x-y). 我们还有如下更加一般的结果:定理8.1 整数集合关于模k1的同余 关系与整数集合关于模k2的同余关系的 交正好就是整数集合关于模k1,k2的同 余关系，这里k1,k2表示k1和k2的最小 公倍数.一.逆关系定义8.1(逆关系) 设R是从集合A到集合B的二 元关系, 则称关系RC=|R为R的逆关 系.例如, 在实数集上的关系“”, 设A=1, 2, 3, 4, B=a, b, c, 则A到B的关系R=, , 的逆关系: RC=, , , 逆关系有如下重要的性质:定理8.2 假设R,R1,R2是从集合A到集合B的二元关 系,RC是关系R的逆关系,而 则是关 系 的逆关系.那么 (1) (2)(3) ,这里 , .(4) (5)(6) (7) (注)这几个结论显然成立,我们只给出(4)和(6)的证明.(4)的证明:(6)的证明:再利用(3)和(5)就得到 于是又有二、复合关系定义8.2 (复合关系) 设R为A到B的关系, 设T为B到C的关系, 则称关系 |xAzC(y)(yBRT)为R和S的复合关系, 记为: RS, 即RS=|xAzC(y)(yBRT).R: AB T: BCA B Ca1 b1 c1a2 b2 c2a3 b3 c3a4 b4 c4a1 c1a2 c2 a3 c3 a4 c4 RT: AC 例2.给定集合A=a,b,c,d上的两个二元关系如下:R=,T=,. 试求复合关系R(2),RT和TR.注意R(2)这里定义为 R(2)= RR. 解:由此可以看出,复合运算一般不满足交换律.复合关系有如下性质(以下出现的集合均取为非 空集合): 定理8.3 (1)设R是从集合A到集合B的一个二元关系,则有RIB=R, IAR=R,其中IA和IB分别是集合A和集合B上的恒等关系. (2)(结合律)设A,B,C,D是四个集合,R1,R2,R3分别是 从A到B,从B到C以及从C到D的二元关系,那么就 有(R1R2)R3 = R1(R2R3)(3)设A是一个集合,R是A上的一个二元关系.定义, 那么，对任意正整数m,n就有1 ; 2 . (4)设A,B,C,D是四个集合,R1,R2,R3分别是从A到B, 从B到C以及从C到D的二元关系,那么就有 1(复合运算关于并的分配律).2(复合运算关于并交的分配律)(5)设A,B,C是三个集合,R1,R2分别是从A到B以及从 B到C的二元关系,那么就有. 证明:我们只给出(5)的证明.利用关系的序偶表示法直接计算复合关系的 做法比较繁琐,且稍不注意,很容易遗漏某些项.下 面给出一个利用关系矩阵来计算复合关系的关系 矩阵的方法.为此首先介绍0和1这两个数的逻辑 加法以及逻辑乘法(也称为Boole加法和Boole乘法 )以及有关0-1矩阵的某些新运算.定义8.3(0和1的Boole加法和Boole乘法)00=0, 01=10=1, 11=1. 00=01=10=0, 11=1.定义8.4(0-1矩阵的Boole加法和Boole乘法)设 与 都是 阶0-1矩 阵,称 阶0-1矩阵 和 分别为 与 的Boole 和以及Boole乘积,这里.定义8.5(0-