函数与二元关系
一 基本要求
1. 理解关系的概念：二元关系、空关系、全关系、恒等关系和n元关系。
掌握关系矩阵和关系图及其表示方法，掌握关系的运算(并、交、补、差和对称差)。
2. 了解复合关系和逆关系的概念。
3. 理解关系的性质(自反性和反自反性、对称性和反对称性、传递性)，掌握其判别方法(定义、矩阵或图)
4. 知道关系闭包(自反闭包(r(R))；对称闭包(s(R))；传递闭包(t(R)))概念，会求关系的闭包。
5. 了解等价关系和偏序关系概念，掌握等价类的求法，会作偏序关系的哈斯图。知道极大(小)元，最大(小)元的概念，会求极大(小)元，最大(小)元。
6. 理解函数概念：函数(映射)，函数相等，象与原象，复合函数和反函数。
7. 理解单射、满射和双射等概念，掌握其判别方法。
重点：关系概念与其性质，等价关系和偏序关系，函数。
二、学习辅导
1. 关系的概念
包括定义、运算、矩阵表示、图形表示、
关系的概念是第4章全章的基础，又是第3章集合概念的应用。因此同学应该真正理解并掌握二元关系的概念及关系矩阵、关系图的表示。
二元关系是两种客体之间的联系，例如某学生学习语文、数学、外语，表示为
A＝{语文，数学。外语}
功课的成绩分四个等级，记作
B＝{A，B，C，D}
于是该生成绩的全部可能为A×B
A×B＝{<语文，A>，<语文，B>，<语文，C>，<语文，D>，<数学，A>，<数学，B>，
<数学，C>，<数学，D>，<外语，A>，<外语，B>，<外语，C>， <外语，D>}
那么该生的实际成绩 P＝{<语文，B>，<数学，A>，<外语，D>}
P是A×B的一个子集，它表示了功课与其成绩的一种关系。这是两个集合(客体)之间的二元关系，从A到B的二元关系，也可以是到自身的二元关系，如A＝N，A的两个数之和是偶数，就是从A到A的二元关系。
知识点：
h二元关系的定义
：集合A，B， 
，记作xRy，就是集合。
h二元关系的定义域：Dom(R)
h二元关系的值域：Ran(R)
关系的表示方法：
h集合表示法：关系是集合，有似集合的表示方法――列举法和描述法
h矩阵表示法 R＝A×B，R的矩阵 
，
h图表示法
几个特殊的关系：
h空关系Æ；唯一是任何关系的子集的关系，MÆ是n阶0矩阵。
h全关系 
h恒等关系 
，MI是单位矩阵。
h关系R的逆关系 
， 
h复合关系
，有
(布尔运算)。
例4.1 设集合A＝{a,b},R是P(A)上的包含关系，有
用描述法表示； 
用列举法表示： 
R的关系矩阵 R的关系图(图4－1)
，
例4.2 设A＝{1,2,3},用列举法给出A上的恒等关系IA，全关系EA，A上的小于关系
和A上的整除关系
解 
DA的逆关系 
有 
例4.3 设集合A＝{2,3,4},B={4,6,7},C={8,9,12,14}。R1是由A到B的二元关系，R2是由B到C的二元关系，定义如下：
，
试用关系矩阵表示法求复合关系 
。
解
，
因此
× 
(布尔运算)
＝ 
故 
＝{<2,8>,<2,12>,<3,12>}
2. 关系的性质
自反性与反自反性、对称性与反对称性、传递性
关系的性质既是对关系概念的加深理解和掌握，又是关系的闭包、等价关系和偏序关系的基础。
知识点（二元关系R）
h自反性
；矩阵 
的主对角线元素全为1；关系图的每个结点都有自回路。
h反自反性 
；矩阵 
的主对角线元素全为0；关系图的每个结点都没有自回路。
h对称性 若 
，则 
；矩阵 
是对称矩阵，即
；有向关系图中有向弧成对出现。
h反对称性 若 
， 
，则x=y或若 
，则 
；矩阵 
不出现对称元素；关系图中没有成对弧出现。
h传递性 若 
，则 
；在关系图中，有从a到b的弧，有从b到c的弧，则有从a到c的弧。
二元运算的并、交、补、差、逆、复合具有的性质表
| 运算 |
自反性 |
反自反性 |
对称性 |
反对称性 |
传递性 |
| R－1 |
Ö |
Ö |
Ö |
Ö |
Ö |
| R1ÈR2 |
Ö |
Ö |
Ö |
´ |
´ |
| R1ÇR2 |
Ö |
Ö |
Ö |
Ö |
Ö |
| R1－R2 |
´ |
Ö |
Ö |
Ö |
´ |
| R1×R2 |
Ö |
´ |
´ |
´ |
´ |
对于五个性质的判定，可以根据定义、关系矩阵或关系图进行判定。其中对传递性的判定，难度稍大点，也可以如下方法判定：不破坏传递性的定义，可认为具有传递性。例如空关系可认为具有传递性，同时具有对称性和反对称性，但是不具有自反性；
例4.4 试判断图4－2中关系的性质：
解 图4－2中(a)的关系在集合{1,2,3}上是对称的，因为结点1与2，1与3之间的有向弧是成对出现且方向相反；它不是自反的，也不是反自反的，因为有的结点有自回路，有的结点没有自回路。它也不是传递的，因为<1,2>ÎR，<2,1>ÎR,若是传递关系，应该有<2,2>ÎR，然而结点2处没有自回路。
图4－2中(b)是反自反的，因为每个结点都没有自回路。它也是反对称的，因为两条边都是单向边，它又是传递的，因为不存在结点x,y,zÎ{1,2,3}。使得x到y有边，y到x有边，但x到z没有边。
图4－2中(c)的关系自反的，反对称的、但不是传递的。因为2到1有边，1到3有边，但2到3没有边。
例4.5 设集合A＝{1,2,3,4,5},R是A上的关系。定义为
R＝{<1,1>,<1,2>,<1,3>,<1.4>,<1,5>,<2,2>,<2,3>,<2,4>,<2,5>,
<3,3>,<3,4>,<3,5>,<4,4>,<4,5>,<5,5>}
试判断R是
(1) A上的自反关系； (2) A上的对称关系；
(3) A上的反对称关系； (4) A上的可传递关系。
解
写出关系矩阵，作关系图(图4－3)。
,
(1) 因为 
，或MR的主对角线元素皆为1，或关系图中每个结点都有自回路，故R是自反关系；
(2) 因为 
，或MR不是对称矩阵，或关系图中每对结点都没有成对出现的方向相反的弧，故R不是对称关系；
(3) 因为 
，或MR的主对角线两侧元素对称位置元素1，或0不对称，或关系图中每对结点没有成对的有向弧，故R是反对称关系；
(4) 因为不难验证 
，或关系图中 
。故R是自反的；
3. 关系的闭包与极大(小)元、最大(小)元问题
设R是非空集合A上的二元关系，在关系R的基础上，添加最少的有序对，得到的关系记作R’，使得R’即有关系的某个性质(R却不具有该性质)，R’就是R的闭包，记作r(R)(R’具有自反性)，s(R)(R’具对称性)，t(R)(R’具有传递性)。
在理解和掌握闭包概念的基础上，主要这闭包的求法。关键是记住几个定理的结论：定理12的 
；定理13的 
；定理14的推论： 
。
例4.6 设集合A＝{a,b,c,d},定义R＝{<a,b>,<b,a>,<b,c>,<c,d>},求r(R),s(R),t(R)。
解 求自反闭包，R不具有自反性，由自反性的定义，只需在R上添加IA，于是
r(R)=RÈIA={<a,a>,<a,b>,<b,a>,<b,b>,<b,c>,<c,c>,<c,d>}
其中下画线者为添加元素。
s(R)=RÈ{<c,b>,<d,c>}={ <a,b>,<b,a>,<b,c>,<c,b>,<c,d>,<d,c>}
t(R)=RÈ{<a,a>,<b,b>,<a,c>,<b,d>,<a,d>}
={<a,a>, <a,b>,<a,c>,<a,d>,<b,a>,<b,b>,<b,c>,<b,d>,<c,d>}
4. 常见的特殊关系 等价关系和偏序关系
等价关系和偏序关系是两种最重要的关系。它们具有不同的性质。
等价关系图的特点是：每一个结点都有一个自回路，两个结点间如有有向弧线，则一定是双向弧线，如果从a到b，从b到c各有一条有向弧线，则从a到c一定有有向弧线。
等价类，若R是等价关系，与R中的某个元素等价的所有元素作为整体，就是一个等价类。就可以把R分成若干个等价类(子集)。
偏序关系是第8章偏序格的基础，理解和掌握偏序关系和偏序集概念的关键是哈斯图。哈斯图的画法掌握了，对于确定任一子集的最大(小)元，极大(小)元也就容易了。这里要注意，最大(小)元与极大(小)元只能在子集内确定。而上界与下界可在子集之外的全集中确定，最小上界是所有上界中最小者，最小上界再小也不会小于子集中的任一元素；可以与某一元素相等，最大下界也是同样。
例4.7 和集合A＝{a,b,c,d,e}，定义A上的二元关系
判断R1，R2是否为等价关系？
解 判断等价关系，就是验证是否具有自反性、对称性和传递性。
写出R1的关系矩阵，
由关系的矩阵可知，R1具有自反性和对称性。由关系图(图4－4)可知它具有传递性，故R1是等价关系。
R2不是等价关系，因为
，故R不具有自反性。
注意：自反性，对称性和传递性之一不具备，就是破坏了等价关系的定义。
事实上 
，故R2不具有对称性；
，R2也不具有传递性。
对例4.7的R1进行分类。对于元素a，因为 
所以a生成的等价类 
;
对于元素b，因为 
所以b生成的等价类 
;
对于元素c，因为 
，所以c生成的等价类 
;
对于元素d，因为 
所以d生成的等价类 
;
对于元素e，因为 
所以e生成的等价类 
;
由上可见，不同的元素，可能有相同的等价类。
例4.8 设集合A＝{18的正整数因子}，£为整除关系，求cov(A)
,称为x盖住y，如A＝{1,2,3,4},cov(A)={<1,2>,<1,3>,<2,4>},<1,4>Ïcov(A),因为存在2ÎA，使得1<2<4。
解 先求集合A，18的正整数因子，有A＝{1,2,3,6,9,18}
整除关系：£＝{<1,1><1,2>,<1,3>,<1,6>,<1,9>,<1,18>,<2,2>,<2,6>,<2,18>,
<3,3>,<3,6>,<3,9>,<3,18>,<6,6>,<6,18>,<9,9>,<9,18>,<18,18>}
cov(A)={<1,2>,<1,3>,<2,6>,<3,6>,<3,9>,<6,18>,<9,18>}
则<A,£>是偏序关系。画<A,£>的关系图和哈斯图如下(图4－5)：
集合(cov(A )
cov(A)的最大元是18，极大元是18，最小元、极小元均为1。
子集{2，3，6}的最大元和极大元都是6，无极小元。上界为6，下界为1，上确界为6，下确界为1。
子集{3，6，9，}无最大元，最小元和极小元都是3。上界为18，下界为3，上确界为18，下确界为3。
子集{1,2,3}的上界和上确界只能是6，而不能是9。
5. 函数
函数是一种特殊的关系，集合A×B的任何子集都是关系，但不一定是函数。函数要求对于定义域A中每一个元素a，B中有且仅有一个元素与a对应，而关系没有这个限制。
二函数相等是指：定义域相同，对应关系相同，而且定义域内每个对应值都相同。
知识点：
h函数
h定义域
函数的类型：
h单射 若 
h满射 f(A)=B
h双射 单射且满射。
h非单非满映射
判定的方法除定义外，还可借助于关系图。而实数集的子集上的函数，也可以用直角坐标表示，尤其是初等函数。
h复合函数
一般 
复合函数的性质：
h 如果f,g都是单射的，则f·g是单射的；
h 如果f,g都是满射的，则f·g是满射的；
h 如果f,g都是双射的，则f·g是双射的；
h 如果f·g是单射的，则f是单射的；
h 如果f·g是满射的，则g是满射的；
h如果f·g是双射的，则f是单射的，g是满射的。
h反函数 若f：A®B是双射，则有反函数f－1：B®A，
例4.9 分别确定一下各题的f是否为从A到B的函数，并对其中的函数f：A®B指出它是否为单射，满射或双射？如果不是，请说明理由。
(1) 
(2) A,B同(1), f={<1,8>,<3,10>,<2,6>,<4,9>}
(3) A,B同(1), f={<1,7>,<2,6>,<4,5>,<1,9>,<5,10>}
(4) A,B为实数集，
(5) A,B同(4)，
(6) A,B同(4)，
(7) A,B同(4)，
(8) A,B为正整数集，
(9) A,B同(8)，
(10) A,B为正实数集，
解 (1) f是从A到B函数，但不是单射，因为f(3)=f(5)=9；也不是满射，因为7ÏRan(f)。 (2) f不是从A到B函数，因为Dom(f)={1,2,3,4}¹A。
(3) f不是从A到B函数，因为对于1ÎDom(f)有7和9两个与它对应。
(4) f是从A到B函数，但不是单射，因为f(0)=f(1)=0；也不是满射，因为该函数的最小值是－1/4，所以Ran(f)是 
，不是整个实数集。
(5) f是从A到B的双射函数，因为 
是严格单调，且
。
(6) f不是从A到B函数，因为Ran(f)是[1,+¥)，不是实数集。
(7) f不是从A到B函数，因为0ÏDom(f)。
(8) (8) f是从A到B函数，且f是单射，因为易验证
但f不是满射，因为1ÏRan(f)。
(9) f是从A到B函数，且f是满射，因为
但不是单射，因为f(1)=f(2)=1。
(10) f是从A到B函数，但f不是单射，因为当x®时，f(x)®0，当x®+¥时，也有f(x)®0，
只有当x=1时 ，f(1)=1/2是极大值。所以必存在x1¹x2,0<x1<1<x2,且f(x1)=f(x2)。F也不是 满射，因为Ran(f)是(0,1/2)，不是整个正实数集。
例4.10 图4－6中，定义了函数f,g,h
求：(1) f,g,h的像;
(2) f·g, h·f, g·g;
(3) 指出f,g,h中哪些是单射，满射和双射
(4) f,g,h中哪些函数存在反函数，给出其反函数的表达式。
解 令A＝{1,2,3,4},则f,g,hÎAA。其中若A＝{a,b,c,d},B={1,2,3},那么
＝{<a,1>,<a,2>,<a,3>,<b,1>,<b,2>,<b,3>,<c,1>,<c,2>,<c,3>,<d,1>,<d,2>,<d,3>}。
称为“B上A”。
(1) f(A)={1,2,4}, g(A)=A, h(A)={1,3}
(2) f·g={<1,4>,<2,2>,<3,2>,<4,3>}
h·f={<1,2>,<2,1>,<3,2>,<4,1>}
g·g={<1,4>,<2,3,>,<3,2>,<4,1>}
(3) 只有g是单射，又是满射，即为双射。
(4) 只有g有反函数g－1：A®A，且满足
g－1＝{<1,3>,<2,2,1>,<3,4>,<4,2>}
三、实例
例1 设集合A＝{1,2}，B={a,b,c},C={c,d}, 则A×BÇC)＝( )
(A){<c,1>,<2,c>} (B) {<1,c>,<2,c>} (C){<c,1>,<c,2>} (D){<1,c>,<c,2>}
答案：(B)
解答： 
，故选择(B).
例2 设A＝{0,a},B={1,a,3},则AÈB的恒等关系是( )
(A) {<0,0><1,1>,<3,3>,<a,a>} (B) {<0,0>,<1,1>,<3,3>}
(C) {<1,1>,<a,a>,<3,3>} (D) {<0,1>,<1,a>,<a,3>,<3,0>}
答案：(A)
解答：因为AÈB＝{0,1,3,a},故AÈB的恒等关系IAÈB＝{<0,1>,<1,1>,<,a,a>,<3,3>},应该选择(A)。
例3 设R1，R2是集合A＝{1,2,3,4},其中
R1＝{<1,1>,<1,2>,<2,4>}, R2={<1,4>,<2,3>,<2,4>,<3,2>},
则R1×R2＝
答案：{<1,4>,<1,3>}
解答：由合成的定义：
例4 设集合A＝{a,b,c},A上的二元关系R＝{<a,a>,<b,b>}不具备关系( )性质。
(A) 传递性 (B) 反对称性 (C) 对称性 (D) 自反性
答案：(D)
解答：只有每个结点都有自回路，才具有自反性，R缺少<c,c>。故应选(D)。
例5 设集合 
是从A到B的函数， 
，则s是( )
(A) 双射 (B) 满射但不是单射 (C) 单射但不是满射 (D)非单射也非满射
答案：(B)
解答：因为s(A)=B,故是满射，但是s(a1)=s(a2)=b2,故不是单射。所以应选(B)。
例6 设 
是A上的二元关系，
则R2是R1的 闭包
答案：对称
解答：在R1的基础上添加<c,b>,此时关系矩阵是对称矩阵，故R2是R1的对称闭包
例7 设集合 
判定下列关系，哪些是自反的，对称的，反对称的，传递的？
解答：均不是自反的；R4是对称的；R1，R2，R3，R4，R5是反对称的；R1，R2，R3，R4，R5是传递的。
例8 设A＝{1,2,3,4,5,6},定义A上的二元关系
R＝{<1,1>,<1,4>,<2,2>,<2,3>,<2,6>,<3,2>,<3,3>,<3,6>,
<4,1>,<4,4>,<5,5>,<6,2>,<6,3>,<6,6>}
(1) 判定R是否为等价关系？
(2) 若是等价关系，写出A的关于R的等价类。
解 (1) 是等价关系；
(2) 等价类分别为{2,3,6}, (1,4), {5}
例9 设A＝{1,2,3,4,5},R是A上的二元关系，
R＝{<1,1>,<2,2>,<3,3>,<3,4>,<4,4>,<5,3>,<5,4>,<5,5>}
(1) 试写出R的关系矩阵和关系图；
(2) 证明R是A上的偏序关系，并画出哈斯图；
(3) 若BÍA，且B＝{2,3,4,5},求B的最大元，最小元，极大元极小元最小上界和最大下界。
解 (1) 关系矩阵，关系图如下：
,
(2) 不难验证R具有自反性；由关系图
看出R具有传递性；反对称性的等价定义，
易知R具有反对称性，故<A,R>是偏序关系。
作<A,R>的哈斯图(图4－8)。
(3) 当B＝{2,3,4,5}时，B的极大元为2，
4。极小元为2，5。B无最大元和最小元，
B无上界和下界。