第4章二元关系与函数

1、第第4章章 二元关系与函数二元关系与函数教学要求：教学要求：1.1.掌握有序对与笛卡儿积的概念和应用；掌握有序对与笛卡儿积的概念和应用； 2. 2.掌握关系的概念；关系的性质；自反闭包、对称掌握关系的概念；关系的性质；自反闭包、对称闭包、传递闭包的概念；闭包、传递闭包的概念； 3. 3.理解等价关系与等价类的概念，偏序关系、偏序理解等价关系与等价类的概念，偏序关系、偏序集的概念及用哈斯图表示；。集的概念及用哈斯图表示；。 4. 4.理解关系矩阵与关系图；理解关系矩阵与关系图； 5. 5.理解函数的概念，单射、满射、双射的概念；复理解函数的概念，单射、满射、双射的概念；复合函数与反函数的概念。合

2、函数与反函数的概念。4.1 集合的笛卡儿集与二元关系集合的笛卡儿集与二元关系一、关系及其定义一、关系及其定义例：设一家庭旅馆有例：设一家庭旅馆有3个房间，每个房间住两个旅客。个房间，每个房间住两个旅客。我们讨论关系：我们讨论关系：“某旅客住在某房间某旅客住在某房间”设：用设：用R表示这种关系，三间房间分别记以表示这种关系，三间房间分别记以1、2、3，六，六个旅客分别记以个旅客分别记以a、b、c、d、e、fa 1bc 2de 3f由图可以很清楚地看出，由图可以很清楚地看出，a与与1间存在关系间存在关系R，记为：记为：aR1，将满足的所有关系列出如下：将满足的所有关系列出如下：aR1，bR1，cR

3、2，dR2，eR3，fR3说明：说明：满足满足pRq的关系可看成是一个有序对（的关系可看成是一个有序对（p，q），），如上面如上面aR1可写成有序对（可写成有序对（a，1）满足满足R的所有关系可看成是一个有序对的集合，这个集的所有关系可看成是一个有序对的集合，这个集合即可叫合即可叫R ，上例中，上例中R既为：既为： R=(a,1), (b,1), (c,2), (d,2) ,(e,3) ,(f,3)上面这种关系叫二元关系，因为它仅牵涉到两个客体间上面这种关系叫二元关系，因为它仅牵涉到两个客体间的关系的关系关系的定义：关系是一些有序对的集合关系的定义：关系是一些有序对的集合v有序对：有序对：P7

4、6定义定义4.1注意注意 有序对强调第一元素与第二元素的顺序有序对强调第一元素与第二元素的顺序v有序有序n元组：元组： P76定义定义4.2二、集合的笛卡儿积与二元关系二、集合的笛卡儿积与二元关系1.笛卡儿积笛卡儿积 ： P76定义定义4.32.笛卡儿积的性质：笛卡儿积的性质：P77 例：例：P77 【例例】4.1 4.23.二元关系：二元关系： P79定义定义4.5.说明：可见用笛卡儿积的一个子集可以表示某个二元关系说明：可见用笛卡儿积的一个子集可以表示某个二元关系 P79定义定义4.64.三种特殊关系（对任何集合三种特殊关系（对任何集合A）：）： P79定义定义4.7 例：例：P79 【例

5、如例如】问题：一个笛卡儿积有多少个子集？问题：一个笛卡儿积有多少个子集？ 如果如果|A|=n，那么那么|AA|=n2，则则AA的子集有的子集有2n25.关系的表示：关系的表示： 集合表达式集合表达式: 例例 P79【例例】4.4 关系矩阵：关系矩阵：P80 图图4-1（a） 关系图关系图: P80 图图4-1（b）4.2 关系的运算关系的运算1.求关系的定义域求关系的定义域 值域值域 域域 P80定义定义4.8 例：例：P80 【例例4.5】2.求关系的逆、合成、限制、像求关系的逆、合成、限制、像 P82定义定义4.9 例：例：P82【例例4.6、例、例4.7、例、例4.8】3.求关系的幂求关

6、系的幂 P84定义定义4.10 例：例：P84【例例4.8】题例分析：题例分析：P106-107 【例例4.27、例、例4.28】作 业：P113-114 【题4.2、题4.3】例题 关系的复合运算设R=， S= =，求：R S S R R R S S R (S R)解： R S =， S R =， R R =， S S =， R (S R) =4.3 关系的性质关系的性质通过前面的学习，我们知道在一个集合上可以定义通过前面的学习，我们知道在一个集合上可以定义2n2个不同的关系，其中有实际意义的关系具有某种个不同的关系，其中有实际意义的关系具有某种性质，这些性质是：自反性、反自反性、对称性、反

7、性质，这些性质是：自反性、反自反性、对称性、反对称性对称性 和传递性和传递性 P86表表4-1举例：举例：1.P86 A=1，2，3，判断，判断R1-R7的性质的性质 2.判断图判断图4-5表示的表示的X=1，2，3上的关系的性质上的关系的性质4.4 关系的闭包关系的闭包1.闭包的概念（某个关系对某个关系的某种性质的闭包）闭包的概念（某个关系对某个关系的某种性质的闭包） 首先看一个例子：设非空集合首先看一个例子：设非空集合A=1，2，3有：有：A上的一个关系上的一个关系R=,，则：则：A上的另一个关系上的另一个关系R= ,，,是自反的是自反的 A上的另一个关系上的另一个关系R”= ,，, 也是

8、自反的也是自反的 这样我们可以推出在这样我们可以推出在29个关系中有若干关系是自反的个关系中有若干关系是自反的,很显很显 然然R中添加的有序对是最少的中添加的有序对是最少的,那么称那么称R是是R的自反闭包的自反闭包, 记为记为:r(R),同理有对称闭包同理有对称闭包s (R),传递闭包传递闭包t (R). 2.闭包的定义闭包的定义 P88定义定义4.113.闭包的构造方法闭包的构造方法 (1) 定理法定理法 P88定理定理4.4 (2) 矩阵法矩阵法P89 (3) 关系图法关系图法 （最直观）（最直观）例：例：P88【例例4.10】可以说关系的闭包其实是对该关系针对某个性质的扩充可以说关系的闭

9、包其实是对该关系针对某个性质的扩充例：例：P88 【例例】4.10例：例：X=a,b,c,R=,，|X|=3, 求求:t(R) RRccbbaaRbccbcaRRR432,t(R)=RR2R3 =,作业 P113 【题4.4】 P116 【题4.14】4.5 等价关系与偏序关系等价关系与偏序关系一一 等价关系等价关系1. 定义定义: P89 定义定义4.12例例:A=1,2,3,8 R= |x,y Axy(mod3) ,我们可以得到下面我们可以得到下面 一个等价关系一个等价关系R,其中包含的有序对有其中包含的有序对有:自反自反:, 对称对称:,传递传递:,2. 等价类等价类xR:设设R是非空集

10、合上的等价关系是非空集合上的等价关系,则则A上互上互相等价的元素构成了相等价的元素构成了A的若干个子集的若干个子集,叫做叫做x关于关于R的等的等价类价类 定义定义: P90 定义定义4.13 性质性质: P91 定理定理4.53. 商集商集A/R: P91 定义定义4.144. 划分与划分块划分与划分块 : P91 定义定义4.15说明说明:由商集和划分的定义不难看出由商集和划分的定义不难看出:即商集就是即商集就是A的的一个划分一个划分,商集是由商集是由R所诱导的划分所诱导的划分. 反过来反过来,也可以由也可以由划分诱导等价关系划分诱导等价关系所以说所以说:集合集合A上的等价关系与集合上的等价

11、关系与集合A的划分是一一对的划分是一一对应的应的例例:设设A=1,2,3,求出求出A上所有的等价关系上所有的等价关系 P92 图图4-8 二二 偏序关系偏序关系1.偏序关系（偏序关系（）的）的 定义定义:P92 定义定义4.162.偏序集（偏序集（或或 ）的定义：）的定义：P93定义定义4.173.可比与盖住的定义：可比与盖住的定义：(描述偏序集合中元素间的层次关系描述偏序集合中元素间的层次关系) P93定义定义4.18 可比可比:若若x y或或yx,则称则称x,y可比可比 盖住盖住:对于任意对于任意x,yA ，当，当 Rxy且没有其他且没有其他 元素元素z满足满足和和,则称元素则称元素y盖住

12、元素盖住元素x4. 全序集全序集: P93 定义定义4.195. 哈斯图哈斯图:用来描述有穷偏序集的关系图用来描述有穷偏序集的关系图在一个集合上，我们常常要考虑元素的次序关系，其中很重要在一个集合上，我们常常要考虑元素的次序关系，其中很重要的一类关系称作偏序关系。的一类关系称作偏序关系。 （2）若）若 Ayx,，且且xy和和 yx，则把则把x画在画在y的下面；的下面； （3）若若y盖住盖住x，则在则在x和和y之间画一条联线，并箭头向上，之间画一条联线，并箭头向上，若若y不盖住不盖住x，但又存在但又存在“”关系，则必定通过关系，则必定通过x和和y之间之间的其它中间结点把的其它中间结点把x和和y联

13、结起来；联结起来；（4）所有边的方向均是向上的，所以实际画时，箭头均可所有边的方向均是向上的，所以实际画时，箭头均可 省去。省去。 画一个偏序集（画一个偏序集（A，）的哈斯图的方法）的哈斯图的方法 （1）用）用“”表示图中的结点，每个节点代表集合表示图中的结点，每个节点代表集合A中的一中的一个个 元素（具有自反性）；元素（具有自反性）；例：设例：设X=2,3,6,12,24,36“”定义为：若定义为：若 XyXxx整除整除y，X，是一偏序集合是一偏序集合,则则xy，其哈斯图为其哈斯图为:考查有序对考查有序对:, ,例：例：(a)设设X=a,b,P(X)= , ,baba),(XP是一偏序关系，

14、是一偏序关系， 其哈斯图为：其哈斯图为： (b)设设X=a,b,c),(XP的哈斯图为：的哈斯图为： 三 关于偏序集的几个概念1.最小元和最大元 见书P93定义4.20（1）、（2）2.极小元和极大元 见书P93定义4.20（3）、（4）作业：P116【题4.16(2)】4.6 函数的定义和性质函数的定义和性质一、函数一、函数(映射映射)定义定义 首先考察下图所表示的映射首先考察下图所表示的映射XYx1x4我们发现，映射建立了从我们发现，映射建立了从X到到Y的一种关系：的一种关系：F=,x2x3x5y1y6y4y2y3y5若关系若关系F满足下列两个条件：满足下列两个条件： (1)对每个对每个xX必存在必存在y Y ，使得使得F (2)对每个对每个xX也只存在一个也只存在一个y Y ，使得使得F（单值性）（单值性）那么则称那么则称F是从是从X到到Y的函数的函数,记为记为:F:XY二二 函数的性质函数的性质 比较下列三个图比较下列三个图x2x3x5y1y2y3y4x1x4满射满射x2x4y1y4y2y3x1x3x2x4y1y4y2y3x1x3y5单射单射双射双射4.7 函数的复合和反函数一 函数的复合 1.复合函数的定义：P98 定理4.6 2.复合函数的性质： P98 定理4.7二 反函数 定义： P99 定理4.81.阅读阅读P100-106的的【例例4.23】、 【例例4