《软件数学基础学习辅导—— 二元关系》由会员分享，可在线阅读，更多相关《软件数学基础学习辅导—— 二元关系（9页珍藏版）》请在金锄头文库上搜索。
1、1软件数学基础学习辅导 二元关系一、主要内容一、主要内容 1.序偶与迪卡尔积 2.关系的概念和性质：二元关系、关系矩阵与关系图。 3.复合关系与逆关系 4.关系的自反性、对称性与反对称性、传递性。 5.等价关系与等价类。 6.偏序关系、偏序集、哈斯图、序关系、序集。 7.函数、复合函数、反函数、单射、满射、双射。 二、学习要求二、学习要求 1.理解序偶与迪卡尔积的概念。 2.理解关系的概念,练掌握关系矩阵与关系图。 3.理解复合关系与逆关系的概念，掌握其求法。 4.熟练掌握等价关系的概念；会判断等价关系。 5.了解偏序关系、偏序集的概念，会用哈斯图表示； 6.了解函数、复合函数与反函数的概念；
2、掌握单射、满射、双射的判断方 法。7.知道序关系与序集的概念。三、学习重点三、学习重点1. 知道关系的三种不同的表示方式, 会求给定关系的关系矩阵和关系图.2. 会判断给定关系是否具有某种特殊性质.3. 能熟练判断给定集合 A 上的二元关系是否为等价关系.4. 会由等价关系确定划分, 也会由划分决定等价关系.5. 掌握偏序集合的概念, 会画偏序关系的 Hasse 图, 也会由 Hasse 图给出偏序关系.四、重、难点解析四、重、难点解析(一) 集合的笛卡尔积设 A, B 是两个集合, 称集合(x, y) | xA, yB 为集合 A 与 B 的笛卡尔积笛卡尔积, 记作 AB, 集合 AB 中的
3、元素叫做有序对有序对. 笛卡尔积有如下简单性质:(1) 如果用|A|来表示集合 A 所含元素的个数, 那么| AB |=|A| |B|. (2) A=, A=.(3) AB= BAA=B 或者 A, B 之中至少有一个为空集.(4) 笛卡尔积对并和交运算都满足分配律:A(BC) = (AB)(AC), (BC)A = (BA)(CA), A(BC) = (AB)(AC), (BC)A = (BA) (CA). (5) 如果 AC, BD, 那么 ABCD.请自己给出上述性质的证明. 尤其是应该给出最后一个命题的逆命题不成立的例子.2(二) 集合上的二元关系我们主要研究给定集合 A 上的二元关系
4、二元关系. 所谓集合 A 上的一个二元关系, 说通俗一点就是给定一个法则 R, 对于 A 中任意两个元素 a, b, 利用这个法则可以判定 a 与 b 是否具有关系 R. 如果使用更数学化的语言来叙述, 就是: R 就是 AA 的一个子集. 比较平凡的关系有: 空关系空关系, 恒等关系恒等关系, 全关系全关系. 我们要研究关系所具备的一些常见性质. 这类似于我们研究函数的常见性质. 所有这些研究, 必须建立在对关系有一个比较方便的表示方式. 下面就是关系最常用的三种表示方式: 集合集合、关系矩阵关系矩阵和关系图关系图, 其中关系矩阵和关系图只能用来表示有限集合 A 上的关系. 1. 集合表示法
5、集合表示法因为集合 A 上的关系 R 就是 AA 的一个子集, 这样作为集合的 R 当然也就可以用列举法和描述法来加以表示. 例如例如 A=2, 3, 4, 6, 对于 A 上的整除关系 R, 我们可以用描述法也可以用列举法来表示这个关系:R=(a, b) | a, bA 且 a 整除 b 或 R=(2, 2), (2, 4), (2, 6), (3, 3), (3, 6), (4, 4), (6, 6).2. 矩阵表示法矩阵表示法设 R 是从有限集合 A=a1, a2, , am上的一个关系, 可以按照如下方式定义一个 m 阶矩阵:( )Rijm mMr1,;0,ij ij ia Rara
6、R若若( ,1,.,).,ji jmb 矩阵 MR为 R 的关系矩阵关系矩阵. 用关系矩阵来表示二元关系, 非常方便. 上面例 1 中集合 A=2, 3, 4, 6上的整除关系 R 的矩阵为:10110101.00100001RM 需要注意的是关系矩阵并不是绝对唯一的, 与集合 A 的元素次序有关系.矩阵表示法最大的优点是, 很容易判定关系是否满足自反性, 对称性, 反对称性. 对于传递性, 也可以通过计算关系矩阵的乘积来判定, 但是多少有点麻烦.3. 有向图表示法有向图表示法设 R 是从有限集合 A=a1, a2, , am上的二元关系, 以 A 的元素为顶点, 用一个从 a 到 b 的箭头
7、来表示 aRb, 则可以得到一个有向图, 称为 R 的关系图.例如例如 设 A=1, 2, 3, 4, R=(1, 1), (1, 2) , (1, 3), (2, 3), (2, 4), (3, 4), (4, 2), 3则 R 的关系图为:(三三) 关系的运算关系的运算既然关系可看作 AA 的子集, 因此可以说关系也是集合. 所以, 对于同一个集合 A 上的关系, 可以进行交、并、差、补等运算. 但是, 对于关系而言, 最重要的两种运算是逆运算和复合运算. 这两种运算可以帮助判断给定关系是否具有某种特殊的性质. 逆运算逆运算: 设 RAA 是集合 A 上的关系, 则 R1=(x, y) |
8、 (y, x)R称为 R 的逆关系逆关系.复合运算复合运算: 设 RAA, SAA 是二元关系, 则T=(x, z)|yB 使得(x, y)R 且(y, z)S称为 R 与 S 的复合关系复合关系, 记作 T=RS 或 T=RS. 逆关系十分容易确定. 考虑一下, 关系与其逆关系 R1关系矩阵和关系图有什么关系? 下面用一个简单例子来说明如何进行关系的复合运算. 例如例如 设 A=a, b, c, d, 定义 A 上的关系 R 如下:R=(a, a) , (a, b), (b, d), (c, a), (d, c), 求复合关系 R2=RR.分析分析: 计算复合关系 RR 一般有三种方法, 可
9、以根据不同的情况选取不同的计算, 下面我们只采用其中一种, 其余见书中有关例题.解解 根据关系 R 中所包含的有序对, 按照复合关系 RR 的定义: (a,b), (b, c)R(a,c)R2. 由此可得R2=(a, a) , (a, b), (a, d), (b, c), (c, a), (c, b), (d, a).(四) 关系的常见性质对于集合 A 上的二元关系 R, 我们最关系的性质有:自反性自反性: 若对于任意的都有, 则称是 A 上的一个自反关系自反关系. xAxRxR4对称性对称性: 若对于任意的都有“xRyyRx”, 则称 R 是 A 上的一个对称对称, x yA关系关系.传递
10、性传递性: 若对于任意的都有“xRy, yRzxRz”, 则称 R 是 A 上的一, ,x y zA个传递关系传递关系.反对称性反对称性: 若对于任意的都有“xRy, yRxx=y”, 则称 R 为集合 A 上, x yA的一个反对称关系反对称关系. 如何判断给定的二元关系是否具有上述某个性质? 可以根据关系的不同表示方式来加以考察. 1. 利用定义考察关系利用定义考察关系 R 的性质的性质自反性自反性: 对于任意 aA, R 必须包含(a, a). 即: IAR.对称性对称性: 若 R 包含(a, b), 则 R 必须同时包含(b, a). 即: R1=R.传递性传递性: 若 R 包含(a,
11、 b), (b, c), 则 R 必须同时包含(a, c). 即: R2R.反对称性反对称性: 若 R 包含(a, b), 而且 ab, 则 R 不能同时包含(b, a). 即: RR1 IA.2. 利用关系矩阵利用关系矩阵 MR考察关系考察关系 R 的性质的性质自反性自反性: MR主对角线元素必须都是 1.对称性对称性: MR必须是对称矩阵. 即: MRT=MR.传递性传递性: MRMR2不出现负数.反对称性反对称性: 若 ij, (i, j)位置与(j, i)位置不能同时为 1(但是可以同时为 0).3. 利用关系图考察关系利用关系图考察关系 R 的性质的性质自反性自反性: 每个顶点必须有
12、环.对称性对称性: 若从 a 到 b 有有向边, 则从 b 到 a 也必须有有向边.传递性传递性: 若从 a 到 b 有有向边, 从 b 到 c 有有向边, 则必须有从 a 到 c 的有向边.反对称性反对称性: 若 ab, 从 a 到 b 有有向边, 则不能有从 b 到 a 的有向边.以上方法可以说各有好处. 第一种容易理解, 第二种容易计算, 第三种比较直观. 如果所使用的计算机编程能力比较强, 不妨自己编写程序, 让计算机来判断关系是否具有某种性质. (五) 等价关系与集合的划分等价关系等价关系: 若集合 A 上的二元关系 R 具有自反性、对称性、传递性, 则称其为等价关系等价关系.等价关
13、系是最常用也是最重要的二元关系. 我们熟悉的: 数的相等关系、直线的平行关系都是等价关系. 但是, 实数的小于等于关系、集合的包含关系都不5是等价关系.划分划分: : 若集合的一个非空子集族满足A( )|,AAAAAI 且（1）; IAA U（2）, AA I则称是的一个划分划分.( )AA设 R 是 A 上的等价关系, aA, 集合aR=xA | (x, a)R称为 a 所在的等价类等价类.设 R 是 A 上的等价关系, 则(1) ( , ) ;(2) ( , ) .RRRRx yRxyx yRxy 集合上的一个等价关系可以唯一确定的一个划分：ARA; ( ) |RRAaaA集合的一个划分也
14、可以唯一确定上的一个等价关系：A( )AAA.( , )|Rx yxAyA使得且认清等价关系与划分本质是一回事是理解这两个概念的关键.例如例如 考虑整数集合 Z 上模 5 同余关系 R5. 这是一个等价关系, 即R5=(x, y) | x y (mod 5).这个等价关系刚好有下列 5 个等价类:0, 10, 5,0,5,10,1, 9, 4,1,6,11,2, 8, 3,2,7,12,3, 7, 2,3,8,13,4, 6, 1,4,9,14,LLLLLLLLLL(五) 偏序关系偏序关系偏序关系: 若集合 A 上二元关系具有自反性、传递性、反对称性, 则称 R为集合 A 上的一个偏序关系偏序
15、关系, 称 A 为带有偏序关系 R 的偏序集偏序集, 记作(A, ).偏序集合的偏序关系 “”, 也读作“小于等于”. 之所以采用这样的符号和名称, 是因为偏序关系和小于等于关系具有完全相似的性质. 集合的包含关系也是偏序关系. 设(A, )是偏序集, 则 A 中的任何两个元素 a, b 只可能出现如下四种情况之一:6a = b, a b, b a, a 与 b 不可比较.顺便提一下, 如果一个偏序集合当中任意两个元素都可以比较, 就称为全序全序 集集. 偏序关系的重要性不亚于等价关系. 对于这种特殊的关系, 我们也采用特殊 的方式来表示, 这种表示方式就是 Hasse 图表示法图表示法. 设有偏序集(A, ), 则其 Hasse 图构造法如下： S1. 以“点”表示 A 中的元素; S2. 若 y 是 x 的直接后继, 则 y 在 x 的上方; S3. 在 x 和 x 的直接后继间连线.例如例如 设 A 是正整数 12 的全部正整数因子组成的集合, 并设偏序关系为整除关系“|”, 则这个偏序关系的 Hasse 图如下: 五、五、 典型例题典型例题例例 1 设 A=2, 3, 6, 12, R 是 A 上的整除关系.（
