离散数学第3章(7-8)(新教材).ppt

第七节 关系的性质 定义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)(yBR T). R: AB T: BC A B C a1 b1 c1 a2 b2 c2 a3 b3 c3 a4 b4 c4 a1 c1 a2 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-1矩阵的乘法运算) 设 与 分别是 阶和 阶0-1矩阵,定义 和 的乘法运算 的结果是一个 阶矩阵 , 其中 , 不难由复合关系的定义以及关系矩阵的定义推 出如下的结果: 定理8.4 设A,B