第四章 二元关系 4.1 二元关系及其表示法 序偶与笛卡尔积

Presentation on theme: "第四章 二元关系 4.1 二元关系及其表示法 序偶与笛卡尔积"— Presentation transcript:

1 第四章 二元关系 4.1 二元关系及其表示法 4.1.1 序偶与笛卡尔积
定义4.1：由两个元素x和y按一定的次序组成的二元组称为有序对或序偶(Ordered)，记作<x, y>，其中x是它的第一元素，y是它的第二元素。 性质4.1：(1)： <x, y>= <y, x>当且仅当x=y； (2)： <x, y>=<u, v>当且仅当x=u, y=v; 例如：平面上的坐标<x, y>，x, y R；<操作码，地址码>等都是序偶。

2 4.1 二元关系及其表示法 定义4.2：设A，B是两个集合，称集合 为集合A与B的笛卡尔积(Descartes Product)。
例：设A={1,2}；B={a, b}则A ×B={<1,a>，<1,b>，<2,a>，<2,b>}；B ×A={<a, 1>，<a, 2>，<b, 1>，<b, 2>}。 性质4.2：(1). | A ×B |=|A|×|B|(A, B为有限集合)； (2) ； (3). 不适合交换律，即A×B ≠B×A(除非A，B= 或A=B)； (4). 不适合结合律，(A×B)×C ≠A×(B×C)(除非 )； (5). 对∪和∩运算满足分配律，

3 4.1 二元关系及其表示法 证明： (6) ，且当 或 时，逆命题成立。

4 4.1 二元关系及其表示法 定义4.3：一个有序n(n≥2)元组是一个有序对，它的第一个元素为有序的n-1元组 ，第二个元素为 ，记为 即：
； 当且仅当 n维空间中的点M的坐标 为有序的n元组 。 定义4.4：设 为n个集合(n ≥2)，称集合 为n维卡氏积或n阶笛卡尔积，记作 ， 当 时简记为 。

5 4.1 二元关系及其表示法 4.1.2 二元关系 定义4.5：若集合F中的全体元素为有序的n(n≥2)元组，则称F为n元关系，特别地，当n=2时，称F为二元关系，简称关系。 对于二元关系F，若 ，常记作 ，反之 ；规定 为n元空关系，也是二元空关系，简称空关系。 定义4.6：设A，B为两集合，A×B的集合子集R称为A到B的二元关系，特别地，当A=B时，称R为A上的二元关系。 例：A={a, b}，B={c}，则A×B的子集有 ，{<a, c>}，{<b, c>}，{<a, c>, <b, c>}，

6 4.1 二元关系及其表示法 A到B上的全部二元关系；而 ，{<c, c>}为B上的二元关系。
一般来说，若|A|=m，|B|=n，A到B上的二元关系共有 个，A上的共有 个二元关系； 特殊的二元关系： (1). 空关系； (2). 全域关系： ； (3). 恒等关系： 。

7 4.1 二元关系及其表示法 定义4.7：设R为二元关系，则 (1). 为R的定义域； (2). 为R的值域； (3). 为R的域。
一般地，若R是A到B上的二元关系，则有 。 例4-1：设A={1,2,3,4,5,6}，B={a, b, c, d}，则R={<2, a>，<2, b>，<3, b>，<4, c>，<6, c>}，那么domR={2,3,4,6}，ranR={a, b, c}。

8 4.1 二元关系及其表示法 4.1.2 关系的表示 1. 集合表示法 由于关系也是一种特殊的集合，所以可以用集合的两种基本的表示方法(枚举法，描述法)来表示关系；如：设A={2}，B={3}，则A到B上的有关系R={<2,3>}；集合N上的“小于等于”关系：R={<x, y>|(x, y) N∧(x ≤ y) }。 2. 关系图法 定义4.8：设集合A={ }到B={ }上的二元关系R，以集合A，B中的元素为顶点，在图中用“ο”表示顶点，若 则可自顶点 向顶点 引有向边 ，其箭头指向 ，用这种方法画出的图称为关系图(Graph of Relation)。

9 4.1 二元关系及其表示法 例4-2：求集合A={1,2,3,4}的恒等关系，空关系，全关系和小于关系的关系图。 3. 关系矩阵
定义4.9：设 ，那么R的关系矩阵 为一m×n矩阵，它的第i，j分量 只取0或1，且

10 4.2 关系的运算 1.关系的交，并，补，差运算 定义4.10：设R和S为A到B的二元关系，其并，交，补，差运算定义如下：
例4-3：设A={1,2,3,4}，若R={<x, y>|(x-y)/2是整数，x, y A}，S={<x, y>|(x-y)/3是正整数，x, y A}，求R∪S，R∩S，S-R，~R，R S。 解：R={<1,1>，<1,3>，<2,2>，<2,4>，<3,1>，<3,3>，<4,2>，<4,4>}，

11 4.2 关系的运算 S={<4,1>}， ∴ R∪S={<1,1>，<1,3>，<2,2>，<2,4>，<3,1>，<3,3>，<4,2>，<4,4>，<4,1>}； R∩S= ； S-R= S={<4,1>}； ~R= A×A-R={<1,2>，<1,4>，<2,1>，<2,3>，<3,2>，<3,4>，<4,1>，<4,3>}； R S=(R∪S)-(R∩S)= R∪S. 关系的补运算是对全关系而言的； 关系的并，交，差，补的矩阵可用如下方法求取：

12 4.2 关系的运算 2.关系的逆运算 由于关系是序偶的集合，除了集合的一般运算外，还有一些特有的运算。
定义4.11：设R是A到B的关系，R的逆关系或逆是B到A的关系，记为 ，定义为： 显然对任意 ，有 ； 为R的关系矩阵，则 例： ； A={a, b, c, d}，B={1,2,3}，R={<a, 1>，<c, 2>，<b, 2>，<d, 3>}， ={<1, a>，<2, c>，<2, b>，<3, d>}。

13 4.2 关系的运算 定理4.1：设R和S都是A到B上的二元关系，那么

14 4.2 关系的运算 3.关系的复合运算 定义4.12：设R，S为二元关系，则R与S的复合关系 定义为： ，其中“ ”为复合运算， 也记为 。
例4-4：设集合A={0,1,2,3,4}，R，S均为A上的二元关系，且R={<x, y>|x+y=4}={<0,4>，<4,0>，<1,3>，<3,1>，<2,2>}，S= ={<x, y>|y-x=1}={<0,1>，<1,2>，<2,3>，<3,4>}；求 一般地，

15 4.2 关系的运算 定理4.2：设F，G，H为任意二元关系，则 定理4.3：设R为A上的关系，则 定理4.4：设F，G，H为任意二元关系，则

16 4.2 关系的运算 4.关系的幂运算 定义4.13：设R是集合A上的二元关系，则R的n次幂 定义为：
则 ={<0,0>，<0,1>，<0,3>，<1,1>，<2,4>，<3,3>，<4,4>}； ={<0,0>，<0,1>，<0,3>，<1,3>，<2,4>，<3,1>，<4,4>}； ={<0,0>，<0,1>，<0,3>，<1,1>，<2,4>，<3,3>，<4,4>}=

17 4.2 关系的运算 定理4.5：设R为A上的二元关系，m，n为自然数，则 证(4)：若n=0时，则有 假设n=k时，有 ，则n=k+1时，有
∴命题成立。 定理4.6：设集合A的基数为n，R是A上的二元关系，那么存在自然数i，j使得 证明：我们知道，当|A|=n时，A上的二元关系共计 个，令k= ，因此在 这k+1个关

18 4.2 关系的运算 系中，至少有两个是相同的(鸽巢原理)，即有 定理4.7：设A是有限集合，且|A|=n，R是A上的二元关系，则
证明：显然 ，下面证： 。 而 ，为此，只要证明对任意的k>n ，有 即可。对任意的 ，则由“” 的定义知：存在 ，使得：

19 4.2 关系的运算 由于|A|=n，所以由鸽巢原理；k+1个元素 中至少有两个元素相同，不妨设为 ，则可 在 中删去 后仍有 由关系的复合运算得： ，其中 ，此时：若 ，则 ；若 ，则重复上述做法，最终总能找到 ，使 得 ，即有 ，由此 有 ，由k的任意性 ，∴

20 4.2 关系的运算 5：集合在关系下的像 定义4.14：设R为二元关系，A是集合 (1)：R在A上的限制 定义为：
(2)：A在R下的像R[A]定义为R[A]=ran( )。 例：R={<a, b>，<a,{a}>，<{a},{a,{a}}>}，则： RΓ{a}={<a, b>，<a,{a}>}；RΓ{{a}}={<{a},{a,{a}}>} ; RΓ{a, {a}}=R； R[{a}]={b,{a}}；R[{a,{a}}]={b,{a},{a,{a}}}；

21 4.2 关系的运算 定理4.8：设F为关系，A，B为集合，则
例4-6：设 ，A={0,1,2}，B={0,-1,-2}。(1)求R[A∩B]和R[A]∩R[B]；(2)求R[A]-R[B]和R[A-B]。 解(1)： R[A∩B]=R[{0}]={0}； R[A]∩R[B] ={0,1,2}∩{0,1,2} ={0,1,2}； (2)： R[A]-R[B] ={0,1,2}- {0,1,2}= ； R[A-B]=R[{1,2}]={1,2}

22 4.3 关系的性质 我们在研究关系的性质时，可以假定关系是某一非空集合上的二元关系，这一假设不失一般性。因此任一A到B上的关系R，即 ，而
，所以关系R总可以看成是A∪B 上的关系，它与原关系R具有完全相同的序偶，对它的讨论代替对R的讨论无损于问题的本质 1.关系的性质 定义4.15：设R是A上的二元关系，即 ，则 (1)若 ，则称R是自反的(Reflexive)； (2)若 ，则称R是反自反的(Irreflexive)；

23 4.3 关系的性质 (3)若 ，则称R是对称的(Symmetric) (4)若 ，则称R是反对称的(Antisymmetric)
(5)若 ，则称R是传递的(Transitive) 例4-7：设A={a, b, c, d} (1):R={<a, a>，<a, d>，<b, b>，<b, d>，<c, c>，<d, d>}是自反的； S={<a, b>，<a, d>，<b, c>，<b, d>，<c, a>，<d, c>}是反自反的； T={<a, a>,<a, b>,<a, c>,<b, d>,<c, a>,<c, c>,<d, c>}既不是自反的也不是反自反的；

24 4.3 关系的性质 在关系图上：关系R是自反的，当且仅当其关系图中的每个节点都有环，关系R是反自反的，当且仅当其关系图中的每个节点上都无环；
例4-8：设A={a, b, c}

25 4.3 关系的性质 关系图上：关系R是对称的当且仅当其关系图中，任何一对节点之间，要么有方向相反的两条边，要么无任何边；关系R是反对称的当且仅当其关系图中，任何一对节点之间，至多有一条边； 关系矩阵上：关系R是对称的当且仅当其关系矩阵是对称矩阵；关系R是反对称的当且仅当其关系矩阵为反对称矩阵。 例4-9：设A={a, b, c, d}

26 4.3 关系的性质 关系图上：关系R是传递的当且仅当其关系图中，任何三个节点x, y, z(可相同)之间，若从x到y，y到z均有一条边，则从x到z一定有一条边存在； 关系矩阵上：关系R是传递当且仅当其关系矩阵中，对任意 2.利用集合运算来判断关系的性质 定理4.9：设R是集合A上的二元关系，则

27 4.3 关系的性质 3.关系性质的保守性 定理4.10：设R，S是A上的二元关系，则
例4-10：设R={<a, b>，<b, c>，<a, c>}， S={<b, a>，<c, b>，<c, a>}是定义在A={a, b, c}上的两个二元关系。

28 4.3 关系的性质 显然R，S是反自反的，反对称的，传递的，则 也是反自反的，反对称的，传递的； 也具备上述的一切性质； (3)R∪S={<a, b>,<b, c>,<a, c>, <b, a>,<c, b>,<c, a>}仅是对称的和反自反的； 则是传递的和对称的。

29 4.4 关系的闭包 关系的限制于扩充：对于任何一个具备某种性质(如自反、对称、传递)的关系来说，在理论研究与应用上都十分重要，但遗憾的是，许多我们要研究的关系并不具有我们所希望的良好性质。因此，我们往往要在给定的关系中删去一些或添加一些元素，以改变原有关系的性质，即所谓的关系的限制与扩充。 关系的闭包则是关系的扩充。 定义4.16：设R是定义在A上的二元关系，若存在满足：(1) 是自反的(对称的或传递的)；(2). ；(3)对R的任何扩充 是自反的(对称的或传递的)，则 。一般将R的自反、对称、传递闭包记作r(R)，s(R)，t(R)。

30 4.4 关系的闭包 例：定义在N上的“<”关系的自反闭包r(R)为“≤”，对称闭包s(R)为“≠”，传递闭包t(R)为“<”；
例4-11：设集合A={a, b, c}，R={<a, b>，<b, b>，<b, c>}是定义在A上的二元关系，求r(R)，s(R)，t(R)并画出R，r(R)，s(R)，t(R)的关系图，关系矩阵。 解： r(R)={<a, b>,<b, b>,<b, c>,<a, a>,<c, c>}; s(R)={<a, b>,<b, b>,<b, c>,<b, a>,<c, b>}; t(R)={<a, b>,<b, b>,<b, c>,<a, c>};

31 4.4 关系的闭包 利用关系图，关系矩阵求闭包的方法：
(1).求一个关系的自反闭包，即将图中所有的无环节点加上环，矩阵中的对角线上的值全定义为1； (2).求一个关系的对称闭包，则在图中，任何一对节点之间，若仅存在一条边，则加一条反方向的边；矩阵中则为：若 ，则令 ，即 ； (3).求一个关系的传递闭包，则在图中，对任意节点a，b，c，若a到b有一条边，同时b到c也有一条边，则从a到c必增加一条边(当a到c无边时)，在矩阵中，若 。

32 4.4 关系的闭包 定理4.11：设R是A上的二元关系，则 定理4.12：设R是集合A上的关系，则 定理4.14：设R是集合A上的关系，则

33 4.4 关系的闭包 定义4.17：(1)集合A上的关系R的自反对称闭包定义为rs(R)=r(s(R)); (2)集合A上的关系R的自反传递闭包定义为rt(R)=r(t(R)); (3)集合A上的关系R的对称传递闭包定义为st(R)=s(t(R));类似的，可有sr(R)，tr(R)，ts(R)。 定理4.15：设R是集合A上的关系，则

34 4.5 等价关系与划分 4.5.1：集合和划分 定义4.18：设A是一个非空集合， 是A的任意n个非空子集，如果 满足：
则称集合 为集合A的一个划分(Partition)，而 叫做这个划分的块或类。 例如：(1) 构成集合U的一个划分； (2) 构成了U上的一个划分。

35 4.5 等价关系与划分 4.5.2：等价关系 定义4.19：设R为非空集合A上的关系，如果R是自反的，对称的，传递的，则称R为A上的等价关系(Equivalent Relation)。若 ，称x等价于y,记作x~y。 例：(1)一群人，同姓，同年龄，同性别都是等价关系，朋友，同学关系不是等价关系：不传递； (2) 都是A上的等价关系； (3)三角形“相似”，“全等”都是等价关系； (4)幂集上定义的 关系，整数集上定义的≤不是等价关系，不对称。

36 4.5 等价关系与划分 例4-12：设m为正整数，整数集合上的关系 证明关系R是等价关系。 证：(1)对任意 ，有 R自反；
(2)对任意 ，若 ,则 ，即R对称； (3)对任意 ，若 ，即 ，而 ，R传递∴R是Z上的等价关系。

37 4.5 等价关系与划分 考察关系R和集合Z；R将Z分成了如下m个子集： 这m个子集特点是：同一个子集中的元素之间都有关系R，不同子集的元素之间无关系R，每两个子集无公共元素，而所有子集的并正好为Z，构成了Z的一个划分。

38 4.5 等价关系与划分 4.5.3：等价类与商集 定义4.20：设R是非空集合A上的等价关系，对任意 ，称集合 为x关于R的等价类(Equivalence Class)，其中x称为 的生成元，由于 中的任何两个元素a，b均相互等价，一般记作a~b。 例4-13：设A={1,2,3,4,5,8}，考虑R是A上的以3为模的同余关系，求其等价类。 解：从例4-12知，R是一个等价关系，则

39 4.5 等价关系与划分 定理4.11：设R为非空集合A上的等价关系，则 证：(1) ，R是等价关系，则R自反，因此 即 (2)

40 4.5 等价关系与划分 同理： (3)若 ，则存在 ，即：
(3)若 ，则存在 ，即： 定义4.21：设R是集合A上的等价关系，由R确定的一切等价类的集合，称为集合A上关于R的商集(Quotient Set)，记为A/R，即

41 4.5 等价关系与划分 定理4.12：设R是非空集合A上的等价关系，则A上的关于R的商集A/R是A的一个划分，称之为由R导出的等价划分。
证：由定理4.11知，命题成立。 定理4.13：设∏(A)是非空集合A的一个划分，则A上的关系 是A上的等价关系，称之为由∏(A)所导出的等价关系。 证明：(1) 为A的一个划分， 使得 ，即x和x同属于∏(A)的一个划分块， ∴R是自反的；

42 4.5 等价关系与划分 (2) ，则x和y同属于∏(A)的一个划分块，即y和x同属于一个划分块， ，R是对称的；
(3) ，则x，y同属于∏(A)的一个划分块 ，y，z同属于∏(A)的一个划分块 ， ，而由于不同划分块的交集为空， ，即x和z属于同一划分块， ∴R是传递的； ∴R为等价关系。 若设 ，则

43 4.5 等价关系与划分 有定理4.12,4.13知，集合A上的等价关系与集合A的划分是一一对应的，因此可以说：划分与等价关系这两个不同的概念本质上是相同的，即是同一个概念的两种不同的表达方式。 例4-14：设A={1,2,3}，求A上的所有等价关系。 解：先求A的划分：只有一个划分块的划分为{1,2,3}；具有2个划分块的划分为 {{1}，{2,3}}， {{2}，{1,3}}， {{3}，{1,2}}，具有3个划分块的划分为 {{1}，{2}，{3}}； 相应的等价关系为：

44 4.5 等价关系与划分 例4-15：设R是集合A上的一个关系，对任意a，b，c A，若
那么称R为A上的循环关系。试证明R是A上的一个等价关系的充要条件是R是循环关系和自反关系。 证明：必要性：若R是等价关系；(1)R等价=>R自反 (2) ，R等价∴R对称 ∴ ，即R是循环关系； 充分性：若R自反且循环：(1)自反性显然； (2) ，R是自反，得 ，因R是循环的 ，即R是对称的；

45 4.5 等价关系与划分 (3) ，则由R对称得 ，由R循环， 得 ， ∴R是传递的； ∴R等价。

46 4.6 次序关系 在一些研究中，需要把研究的对象排出次序，因此，集合的元素之间还有一种重要关系，称为“先后次序”关系，即偏序关系。
定义4.21：(1)设R为非空集合A上的关系，如果R是自反的，反对称的，传递的，则称R为A上的偏序关系(Partial Order relation)。记作“≤”,读作“小于等于”； (2)设R为非空集合A上的关系，如果R是反自反的，反对称的，传递的，则称R为A上的拟序关系(Quasi Order relation)。记作“<”；读作“小于”。 偏序关系的逆关系 也是一个偏序，用“≥”表示，读作“大于等于”；拟序关系的逆关系 也是一个拟序，用“>”表示，读作“大于”。

47 4.6 次序关系 例：(1)集合A上的幂集ρ(A)上定义的“ ”和“ ”分别是偏序关系和拟序关系；
(2)实数集合R上定义的数的“小于等于”关系，“小于”关系，分别是偏序关系和拟序关系； (3)自然数集合N上定义的“整除”关系，也是一个偏序集合。 定义4.22：设<A, ≤>是一个偏序集，对 ，x ≤y或y ≤x，则称x与y是可比的(Comparable),若x与y是可比的，x<y，且不存在 ，使得x<y<z，则称y覆盖(Overlay)x。

48 4.6 次序关系 例：(1)集合A={a，b，c}，则偏序集<ρ(A), ≤>中，{a}与{a，b}是可比的； {a}与{b，c}是不可比的； {a，b}覆盖{a}； {a，b，c}不覆盖{a}。 (2)偏序集{R，≤}，对 ，x与y都是可比的，但x不覆盖y，y也不覆盖x。 (3)偏序集{Z，≤}，对 ，x与y都是可比的，x覆盖x-1。 (4)偏序集<N，|>中，2与3不是可比的，2与6是可比的，并且6覆盖2,2与8可比，但8不覆盖2。

49 4.6 次序关系 4.6.2：偏序集的哈斯图 由于偏序关系本身具有自反，反对称，传递的性质，在用关系图来描述偏序关系且不引起混淆，可以对其进行简化，得到的图叫做偏序图或哈斯图(Hasse)。 哈斯图的作图方法如下： (1):用小圆圈或点表示A中的元素，省掉关系图中的所有环(因自反性)； (2):对 ，若x<y则将x画在y的下方，可省掉关系图中所有边的箭头； (3):对 ，若y覆盖x，则在x与y之间连条线，否则无线相连。

50 4.6 次序关系 按(1)，(2)，(3)所作成的图称为哈斯图。
例4-16：设A={2,3,6,12,24,36}，“≤”是A上的整除关系，画出其一般关系图和哈斯图。 例4-17：设集合A={a}，B={a，b}，C={a，b，c}分别画出集合A，B，C之幂集上定义的“ ”的哈斯图。

51 4.6 次序关系 4.6.3：偏序集中的特殊元素 定义4.23：设<A, ≤>为偏序集，
最小元与极小元不一样，最小元是B中最小的元素，它与B中其它元素都是可比的，而极小元不一定与B中的元素都可比，只要没有比它小的元素，它就是极小元； 对于有穷集，极小元一定存在，但最小元不一定存在；

52 4.6 次序关系 如果最小元存在，最小元唯一，但极小元可以有多个； b是B的最小元<=>b是B中的唯一极小元；
反之，极大元亦然。 定义4.24：设<A, ≤>为偏序集，

53 4.6 次序关系 例4-18：设集合A={a，b，c}，求偏序集 的子集的子集
的最大元，最小元，极大元，极小元，上界，下界，上确界，下确界。 解：画图 集合 最大元 最小元 极大元 极小元 上界 下界 上确界 下确界 无 {a，b}，{b，c} {a，b，c} {a，c} {a}，{c} {a，c}，{a，b，c}

54 4.6 次序关系 例4-19：设A={a，b，c，d}，A上定义偏序集<A， ≤>的哈斯图如图所示，求B={a，b}和
C={c，d}的最大元，最小元，极大元 ，极小元，上下 界，上下确界。 解： a b c d 集合 最大元 最小元 极大元 极小元 上界 下界 上确界 下确界 B 无 a，b c，d C

55 4.6 次序关系 上(下)界存在，并不一定存在最小上(下)界； b是B的最大元=>b是B的极大元，上界，上确界；
a是B的上确界∧ =>a是B的最大元； a是B的下确界∧ =>a是B的最小元； 若B存在上确界，则其上确界唯一； 若B存在下确界，则其下确界唯一。

56 4.6 次序关系 4.6.4：全序与良序 定义4.25：设<A, ≤>是一个偏序集，若对 x与y都是可比的，则称关系“≤”为全序关系(Total Order Relation)，或称线序关系，简称全序或线序，称<A, ≤>为全序集或线序集或链。 例：(1)集合A={a，b，c}，上定义的关系≤={<a，a>，<b，b>，<c，c>，<a，b>，<b，c>，<a，c>}是一个全序关系； (2)实数集合R上定义的“≤”是全序关系， <R, ≤>