需要大神们的帮助！！【离散数学吧】_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：5,998贴子：
需要大神们的帮助！！收藏
吉大学年第一学期期末考试《离散数学》大作业一．R，S是集合A上的两个关系。试证明下列等式：（1）(RoS)-1= S-1oR-1（2）(R-1)-1= R二、R，S是集合A上的两个关系。试证明下列等式：（1）(R∪S)-1= R-1∪S-1（2）(R∩S)-1= R-1∩S-1三、设R是非空集合A上的关系，如果1）对任意a?A，都有a R a ；2）若aRb，aRc，则bRc ；四、若集合A上的关系R，S具有对称性，证明：RoS具有对称性的充要条件为RoS= SoR。五、若R是等价关系，试证明R-1也是等价关系。六．对任意集合A，B，证明：(1)A?B当且仅当r(A)? r(B)；(2)r(A)?r(B)?r(A?B)；七．对任意集合A，B，证明：(1)r(A)?r(B)=r(A?B)；(2)r(A-B) ?(r(A)-r(B)) ?{f}。举例说明：r(A)∪r(B)≠r( A∪B)八．设A是m元集合，B是n元集合。问A到B共有多少个不同的二元关系？设A={a，b}，B={1， 2}，试写出A到B上的全部二元关系。九．若非空集合上的非空关系R是反自反的，是对称的，试证明R不是传递的。十. 设A,B,C为任意三个集合，下列各式对否？并证明你的结论。（1）若A?B且B?C，则A?C；（2）若A?B且B?C，则A?C；（3）若A?B且B?C，则A?C；（4）若A?B且B?C，则A?C。
登录百度帐号推荐应用扫二维码下载作业帮
2亿+学生的选择
下载作业帮安装包
扫二维码下载作业帮
2亿+学生的选择
离散数学二元关系，设R和S是集合A上的对称关系，证明：R。S具有对称性，当且仅当R。S＝S。R
扫二维码下载作业帮
2亿+学生的选择
必要性:任取∈R。S，因为R。S具有对称性,故∈R。S,则一定存在y使得∈R,且∈S,又因为R,S有对称性,故有∈S,且∈R,故∈S。R,这就证明了R。S含于S。R,同样地,可证S。R含于R。S,这就证明了S。R=R。S充分性:任取∈R。S,因为S。R=R。S,故∈S。R,则一定存在y使得∈S,且∈R,又因为R S具有对称性,故 ∈R,∈S,故∈R。S,故R。S具有对称性证毕
为您推荐：
扫描下载二维码离散数学课本习题
第二章 二元关系 习题2.1 1、 列出从A到B的关系R中的所有序偶。 a) A={0, 1, 2}，B={0, 2, 4}，R={| x, y ? A∩B } b) A={1, 2, 3, 4, 5}，B={1, 2, 3}，R={| x ?A, y ?B且x =y2} 2、设R1和R2都是从{1, 2, 3, 4}到{ 2, 3, 4}的二元关系，并且 R1={,, } R2={,, } 求R1∪R2, R1∩R2, domR1, domR2, ranR1, ranR2, dom(R1∪R2)和ran(R1∪R2)。 3、设R1和R2都是从集合A到集合B的二元关系。证明 dom(R1∪R2)= domR1∪domR2 ran(R1∩R2)? ranR1∩ranR2 4、用L和D分别表示集合{1, 2, 3, 6}上的普通的小于关系和整除关系，试列出L, D和L∩D中的所有序偶。 5、给出满足下列要求的二元关系的实例： a) 既是自反的，又是反自反的； b) 既不是自反的，又不是反自反的； c) 既是对称的，又是反对称的； d) 既不是对称的，又不是反对称的。 6、试判断下面的论断正确与否。若正确，请加以证明；若不正确，请给出反例。
设R和S都是集合A上的二元关系。若R和S都是自反的(反自反的，对称的，反对称的，或传递的)，则R∩S，R∪S，R－S，R?S也是自反的(反自反的，对称的，反对称的，或传递的)。 7、描述R上的下列二元关系S的性质： a) S={|x, y?R且x? y ＞0}； b) S={|x, y?R，4整除|x－y|且|x－y|＜10}； c) S={|x, y?R，x2 =1且y ＞0}； d) S={|x, y?R，4 |x|?1且| y|?1}。 8、设n, m?I+。若集合A恰有n个元素，则在A上能有多少个不同的m元关系？证明你的结论。 9、设?和?都是由从集合A到集合B的二元关系构成的集类，并且? ??。证明 a) dom(∪?)=∪{domR|R??}；
b) ran(∪?)=∪{ranR|R??}； c) dom(∩?)?∩{domR|R??}； d) ran(∩?)?∩{ranR|R??}； 10、设R为集合A上的一个二元关系。如果R是反自反的和传递的，则R一定是反对称的。 11、设R为集合A上的一个二元关系，若令fldR=domR∪ranR则fldR=∪(∪R)。 12、若R为集合A上的一个二元关系，则R也是∪(∪R)上的二元关系。
习题 2.2 1. 设集合A={1,2,3,4,5,6}上的二元关系R为 R={,,,,,,,,,,,,,} 试画出R的关系图GR，求出R的关系矩阵MR,并指出R所具有的性质。 2. 对图2.2.3给出的集合A={1,2,3}上的十二个二元关系的关系图，写出相应的关系矩阵，并指出各个关系所具有的性质。 3. 对习题2.1种第4题所给的二元关系L,D和L?D，画出它们的关系图，并写出它们的关系矩阵。 4. 设A为恰有n个元素的有限集。 a) 共有多少个A上的不相同的自反关系？ a) 共有多少个A上的不相同的反自反关系？ b) 共有多少个A上的不相同的对称关系？ c) 共有多少个A上的不相同的反对称关系？ d) 共有多少个A上的不相同的既是对称又反对称的关系？ 习题2.3 1. 设R为非空有限集A上的二元关系。如果R是反对称的，则R?R-1的关系矩阵MR?R-1中最多能有多少个元素为1？ 2. 设R为集合A上的二元关系，则R?R-1为A上包含R的最小对称关系，R?R-1为A上的包含在R中的最大对称关系。 3. 设IA为集合A上的恒等关系，即IA={|x?A}。则对A上的任意二元关系R，A上的二元关系IA?R?R-1必是自反的和对称的。 4. 设R为任意的二元关系。证明 a) domR-1=ranR; b) ranR-1=domR。
1、 设集合{a, b, c, d}上的二元关系R1和R2为R1={,,}；R2={,,,}。试求R2oR1，R1o R2，R1及R2。 3、若R为任意集合A上的空关系或全关系，则R2=R。 4、举出使R1o(R2∩R3)? (R1oR2)∩(R1oR3), (R2∩R3)o R4? (R2oR4)∩(R3oR4) 成立的二元关系R1，R2，R3和R4的实例。 5、设R1和R2都是集合A上的二元关系。证明或用反例推翻以下的论断： a) 如果R1和R2都是自反的，则R1oR2也是自反的； b) 如果R1和R2都是反自反的，则R1oR2也是反自反的； c) 如果R1和R2都是对称的，则R1oR2也是对称的； d) 如果R1和R2都是传递的，则R1oR2也是传递的； 6、设A={0，1，2，3}上的二元关系R1和R2为R1={| j=i+1或j =i/2}；R2={|i=j+2}；试求MR1，MR2，MR1?R2，MR1?R2?R1及MR3。 1228、设R为集合A上的二元关系，s，t?N，s<t且Rs=Rt。证明 a) 若k?N，则Rs+k=Rt+k； b) 若k, i?N，则Rs+kp+i=Rs+ i； c) 若k?N，则Rk?{R0,R1,?,Rt-1}。其中p=t-s。 9、设IA为集合A上的恒等关系，R为A上的任意二元关系。证明 a) R是自反的，当且仅当IA?R； b) R是反自反的，当且仅当R∩IA=?； c) R是对称的，当且仅当R =R-1； d) R是反对称的，当且仅当R? R-1= IA； e) R是传递的，当且仅当RoR?IA。 10、如果集合A上的二元关系R既是自反的，又是传递的，则R2=R。 11、设R1为从集合A到集合B的二元关系，R2为从集合B到集合C的二元关系。试求dom(R1oR2)和ran(R1oR2)。 12、设R为从集合A到集合B的二元关系，且对每个X?A，皆令R (X)={ y?B|有x?X使＜x，y＞?R}。若X1?A且X2?A，则有 i) R (X1∪X2)= R (X1)∪R (X2)； ii) R (X1∩X2)? R (X1)∩R (X2)； iii) R (X1X2)?R (X1)R (X2)； 13、设R1为从集合A到集合B的二元关系，R2为从集合B到集合C的二元关系。若X?A，则(R1oR2) (X)= R2(R1 (X))。 习题2.5
2、设R1和R2都是集合A上的二元关系，试证明： a) r(R1∪R2)=r(R1)∪r(R2)； b) s(R1∪R2)=s(R1)∪s(R2)； c) t(R1∪R2)?t(R1)∪t(R2)。 4、设R1和R2都是集合A上的二元关系，试证明： a) r(R1∩R2)=r(R1)∩r(R2)； b) s(R1∩R2)?s(R1)∩s(R2)； c) t(R1∩R2)?t(R1)∩t(R2)。 并分别给出使s(R1)∩s(R2)?s(R1∩R2)和t(R1)∩t(R2)?t(R1∩R2)不成立的R1和R2的具体实例。 6、给出一个二元关系R使 st(R)≠ts (R)。 7、设R为集合A上的二元关系，试证明： a) RoR*= R+= R*oR； b) (R+)+= R+； c) (R*)*= R*；
1、设R1和R2都是集合A上的相容关系。证明或用反例推翻下列命题： a) R1∩R2是A上的相容关系； b) R1∪R2是A上的相容关系； c) R1－R2是A上的相容关系； d) R1?R2是A上的相容关系； e) R1oR2是A上的相容关系； f) R12是A上的相容关系； 3、如果A为恰含n个元素的有限集，则A上有多少个不同的相容关系？ 习题2.7 1、试判断下列I上的二元关系是不是I上的等价关系，并说明理由。 a) {| i, j?I且i?j >0}； b) {| i, j?I且i?j?0且i与j不同时为0}； c) {| i, j?I且i?0 }； d) {| i, j??I且i?j?0 }； e) {| i, j?I且i| j }； f) {| i, j?I且有x?I使10x?i?j?10(x +1)}； g) {| i, j?I且| i－j |?10 }； h) {| i, j?I且有x, y?I使10x?i?10(x+1)及10 y?j?10(y +1)}； i) {| i, j?I且有x?I使10x< i <10(x +1)}； 2、 有人说：“如果集合A上的二元关系R是对称的和传递的，则R必是自反的”。并给出了如下的证明：如果?R，则由R是对称的可知?R，从而由R是传递的得到?R和?R。因此R是自反的。请你想一想，他的看法和证明对吗？为什么？ 3、 设集合A上的二元关系R是自反的。证明R为等价关系的充要条件是：若,?R,则?R. 4、 如果集合A上的二元关系R满足：若,?R，则?R。就称R为循环的。试证明集合A上的二元关系R为A上的等价关系，当且仅当R是自反的和循环的。 5、 设R1和R2都是集合A上的等价关系。试判断下列A上的二元关系是不是A上的等价关系，为什么？ a) A2－R1； b) R1－R2； c) R12； d) r(R1－R2)； e) R2oR1； f) R1∪R2； g) t(R1∪R2) ； h) t(R1∩R2) ； 6、设∏1和∏2都是集合A的划分。试判断下列集类是不是A的划分，为什么？ a) ∏1∪∏2； b) ∏1∩∏2； c) ∏1－∏2； d) (∏1∩(∏2－∏1) ) ∪∏1； 7、如果R1和R2都是集合A上的等价关系，则R1=R2当且仅当A/R1=A/R2。 8、设∏1和∏2都是集合A的划分，若对每个S1∈∏1，皆有S2?∏2使S1?S2，就称∏1和∏2的加细，记为∏1?∏2且∏1≠∏2，就称∏1为∏2的真加细，并记为∏1<∏2。
设R1和R2都是集合A上的等价关系，证明： a) R1?R2当且仅当A/R1?A/R2。 b) R1?R2当且仅当A/R1＜A/R2。 9、设A和B都是非空集，{A1,A2,?,An}为A的划分。试证明{ A1∩B,A2∩B,?,An∩B}并不总是集合A∩B的划分。 10、若R为集合A上的等价关系，则称n(A/R)为R的秩。如果i,j?I+且集合A上的等价关系R1与R2的秩分别为i和j，则R1∩R2也A上的等价关系且max{i,j}?n(A/( R1∩R2))?i?j。 11、设A为恰含n个元素的非空有限集，则有多少个不同的A上的等价关系？其中秩为2的又有多少？ 12、如果n,m∈I+，则I/≡n为/ I≡m的加细当且仅当m|n。 习题2.8 2、画出下列集合上的整除关系的哈斯图。 a) {1,2,3,4,6,8,12,24}； b) {i|i?I且1?i?14}； c) {i|i?I且5?i?20}； 3、设R为集合A上的二元关系且S?A，证明或用反例推翻下述断言： a) 若R是A上的半序，则R|s是S上的半序； b) 若R是A上的拟序，则R|s是S上的拟序； c) 若R是A上的全序，则R|s是S上的全序； d) 若R是A上的良序，则R|s是S上的良序； 4、设R是集合A上的二元关系。证明： a) 若R是A上的半序，当且仅当R∩R-1=IA且R=R*； b) 若R是A上的拟序，当且仅当R∩R-1=?且R=R+；
5、证明： a) 半序关系的逆关系仍然是半序关系； b) 全序关系的逆关系仍然是全序关系； c) 良序关系的逆关系未必是良序关系； 7、举出满足下列条件的半序结构的实例。 a) 为全序结构，且A的某些非空子集无最小元。 b) 不是全序结构，且A的某些非空子集无最大元。 c) A的某些非空子集有下确界，但无最小元。 d) A的某些非空子集有上界，但无上确定界。 8、设为半序结构。证明A的每个非空有限子集都至少有一个极小元和极大元。 9、设为全序结构。证明A的每个非空有限子集都有一个最大元和最小元。 10、试判断下列定义在二维欧氏空间R×R上的二元关系T是不是R×R上的拟序，半序，全序和良序？R×R的每个有下界的非空子集(关于拟序或半序T)是否与下确界？并给出证明。 a) 若x1, x2, y1, y2?R，则T当且仅当x 1?x2且y1?y2； b) 若x1, x2, y1, y2?R，则T当且仅当x 1?x 2； c) 若x1, x2, y1, y2?R，则T当且仅当x1＜x2或者x1=x2且y1?y2； d) 若x1, x2, y1, y2∈R，则T当且仅当x1＜x2。 11、设R为集合S上的全序关系。证明R和R-1同时为S上的良序，当且仅当S为有限集。 12、I+在上定义二元关系R如下：
当且仅当 f(n)< f(m),或f(n)= f(m) 且n?m 其中f(n)表示n的不同素因子的个数。
证明为良序结构。
联系客服：cand57</二元关系和函数_西安电子科技大学出版社：离散数学_ppt_大学课件预览_高等教育资讯网
西安电子科技大学出版社：离散数学：第4章
二元关系和函数
分类： 格式： 日期：日
第 4章 二元关系和函数第 4章 二元关系和函数4.1 序偶与笛儿积4.2 关系及表示4.3 关系的运算4.4 关系的性质4.5 关系的闭包4.6 等价关系和划分4.7 序关系4.8 函数的定义和性质4.9 函数的复合和反函数4.10 集合的基数4.11 例题选解习 题 四第 4章 二元关系和函数4.1 序偶与笛卡儿积定义 4.1.1(有序对 (或序偶 ),ordered pairs) 由两个元素 x和 y（允许 x=y）按一定次序排列组成的二元组｛｛ x｝,｛ x,y｝｝称为一个有序对或序偶,记作〈 x,y〉,其中 x是它的第一元素,y是它的第二元素。注意,第一,二元素未必不同。第 4章 二元关系和函数如平面直角坐标系中的任意一点坐标 （ x,y） 均是序偶,而全体这种实数对的集合{(x,y） |x∈ R∧ y∈ R} 就表示整个平面 。有序对 〈 x,y〉 具有以下性质：(1) 当 x≠y 时,〈 x,y〉 ≠〈 y,x〉 。(2) 〈 x,y〉 =〈 u,v〉 的充要条件是 x=u 且 y=v。(3) 〈 x,x〉 也是序偶 。第 4章 二元关系和函数这些性质是二元集 ｛ x,y｝ 所不具备的 。 例如当x≠y 时有 {x,y}={y,x},原因是有序对中的元素是有序的,而集合中的元素是无序的 。 再例如,｛ x,x｝={x},原因是集合中的元素是互异的 。由性质 (２ )可推出 〈 x,y〉 =〈 y,x〉 的充要条件是 x=y。 有序对的概念可以进一步推广到多元有序组 。第 4章 二元关系和函数定义 4.1.2(n元有序组 ) 若 n∈ N且 n＞ 1,x1,x2,…,xn 是 n 个元素,则 n 〈 x1,x2,…,xn〉 定义为：当 n=2时,二元组是有序对 〈 x1,x2〉 ；当 n≠2时,〈 x1,x2,…,xn〉=〈〈 x1,x2,…,x n-1 〉,xn〉本质上,n元有序组依然是序偶。第 4章 二元关系和函数n元有序组有如下性质：〈 x1,x2,…,xi,…,xn〉 =〈 y1,y2,…,yi,…,yn〉 的充要条件是x1=y1,x2=y2,…,xi=yi,…,xn=yn。前面提到,一个序偶 〈 x,y〉 的两个元素可来自不同的集合,若第一元素取自集合 A,第二元素取自集合 B,则由 A,B中的元素,可得若干个序偶,这些序偶构成的集合,描绘出集合 A与 B的一种特征,称为笛卡儿乘积 。 其具体定义如下：第 4章 二元关系和函数定义 4.1.3 设 Α,Β 为集合,用 Α中元素为第一元素，Β中元素为第二元素构成有序对。所有这样的有序对组成的集合称为集合 Α和 Β的笛卡儿积 (cartesian product),又称作直积,记作 Α× Β。Α和 Β 的笛卡儿积的符号化表示为A× B={〈 x,y〉 |x∈ A∧ y∈ B}第 4章 二元关系和函数定义 4.1.4 (n阶笛卡儿积 (cartesian product)) 若 n∈ N，且 n＞ 1,A1,A2,…,An是 n 个集合,它们的 n 阶笛卡儿积记作 A1× A2× … × An,并定义为,A1× A2× … × An={〈 x1,x2,…,xn〉 |x1∈ A1∧ x2∈ A2,…,xn∈ An}当 A1=A2=…= An=A时,A1× A2× … × An简记为 A n。第 4章 二元关系和函数【 例 4.1.1】 设 A=｛ 1,2｝,B=｛ a,b,c｝,C=｛ ｝,R为实数集,则（ 1） A× B=｛ 〈 1,a〉,〈 1,b〉,〈 1,c〉,〈 2,a〉,〈 2,b〉,〈 2,c〉 ｝B× A＝ ｛ 〈 a,1〉,〈 b,1〉,〈 c,1〉,〈 a,2〉,〈 b,2〉,〈 c,2〉 ｝× A=第 4章 二元关系和函数（ 2） A× B× C=(A× B)× C=｛ 〈 1,a,〉,〈 1,b,〉,〈 1,c,〉,〈 2,a,〉,〈 2,b,〉,〈 2,c,〉 ｝A× (B× C)=｛ 〈 1,〈 a,〉〉,〈 1,〈 b,〉〉,〈 1,〈 c,〉〉,〈 2,〈 a,〉〉,〈 2,〈 b,〉〉,〈 2,〈 c,〉〉 ｝（ 3） A 2={〈 1,1〉,〈 1,2〉,〈 2,1〉,〈 2,2〉 }(4) B 2={〈 a,a〉,〈 a,b〉,〈 a,c〉,〈 b,a〉,〈 b,b〉,〈 b,c〉,〈 c,a〉,〈 c,b〉,〈 c,c〉 }第 4章 二元关系和函数（ 5） R 2=｛ 〈 x,y〉 |x,y是实数｝,R 2为笛卡儿平面。 显然 R 3为三维笛卡儿空间。显然 A× B与 B× A所含元素的个数相同 （ A,B是有限集合 ）,但 A× B≠B× A。定理 4.1.1 若 A,B是有穷集合,则有|A× B|=|A|·|B| (·为数乘运算 )该定理由排列组合的知识不难证明 。第 4章 二元关系和函数定理 4.1.2 对任意有限集合 A1,A2,…,An,有|A1× A2× … × An|＝ |A1|·… ·| An| (·为数乘运算 )这是十分直观的,可用归纳法证明之 。第 4章 二元关系和函数定理 4.1.3 (笛卡儿积与 ∪,∩,～运算的性质 ) 对任意的集合 A,B 和 C,有（ 1） A× (B∪ C)=(A× B)∪ (A× C)（ 2） A× (B∩C)=(A× B)∩(A× C)（ 3） (B∪ C)× A=(B× A)∪ (C× A)（ 4） (B∩C)× A=(B× A)∩(C× A)（ 5） A× (B-C)＝ (A× B)-(A× C)（ 6） (B-C)× A＝ (B× A)-(C× A)第 4章 二元关系和函数证明 我们仅证明 （ 1） 和 （ 5）,其余完全类似 。（ 1） 对任意 x,y,有〈 x,y〉 ∈ A× (B∪ C) x∈ A∧ y∈ (B∪ C)x∈ A∧ (y∈ B∨ y∈ C)(x∈ A∧ y∈ B)∨ (x∈ A∧ y∈ C)〈 x,y〉 ∈ A× B∨ 〈 x,y〉 ∈ A× C〈 x,y〉 ∈ (A× B)∪ (A× C)第 4章 二元关系和函数为证 （ 5） 式,设 〈 x,y〉 为 A× (B-C)中任一序偶,那么 x∈ A,y∈ B,y C,从 〈 x,y〉 ∈ A× B，〈 x,y〉 A× C,即 〈 x,y〉 ∈ A× B-A× C,A× (B-C)(A× B)-(A× C) 得证 。 另一方面,设 〈 x,y〉 为(A× B)-(A× C)中任一序偶,那么 〈 x,y〉 ∈ A× B,〈 x,y〉 A× C,从而 x∈ A,y∈ B,y C（ 否则由于 x∈ A，〈 x,y〉 ∈ A× C ）,y∈ B-C,〈 x,y〉∈ A× (B-C),于是 (A× B)-(A× C) A× (B-C)得证 。这就完成了 A× (B-C)＝ (A× B)-(A× C)的证明 。第 4章 二元关系和函数定理 4.1.4( 1) 对任意的集合 A,B 和 C,若 C≠,则(A B) (A× C B× C) (C× A C× B)该定理中的条件 C≠ 是必须的,否则不能由A× C B× C或 C× A C× A推出 A B。定理 4.1.5( 2) 对任意的集合 A,B,C和 D,有(A× B C× D) (A C∧ B D)这两个定理留给读者自己完成证明 。第 4章 二元关系和函数定理 4.16 对任意非空集合 A,B,有(A× B) P(P(A∪ B))证明 设 〈 x,y〉 为 A× B中任一序偶,即 x∈ A，y∈ B。 现需证〈 x,y〉 =｛｛ x｝,｛ x,y｝｝ ∈ P(P(A∪ B))由于 x∈ A,故 ｛ x｝ ∈ P(A∪ B)； 又由于 x∈ A，y∈ B,故 ｛ x,y｝ ∈ P(A∪ B)。 因此,有｛｛ x｝,｛ x,y｝｝ P(A∪ B)即 ｛｛ x｝,｛ x,y｝｝ ∈ P(P(A∪ B))。事实上,结论对 A,B为空集时也真 。第 4章 二元关系和函数4.2 关 系 及 表 示关系是客观世界存在的普遍现象,它描述了事物之间存在的某种联系 。 例如,人类集合中的父子,兄弟,同学,同乡等,两个实数间的大于,小于,等于关系,集合中二直线的平行,垂直等等,集合间的包含,元素与集合的属于 …… 都是关系在各个领域中的具体表现 。 表述两个个体之间的关系,称为二元关系； 表示三个以上个体之间的关系,称为多元关系 。我们主要讨论二元关系 。第 4章 二元关系和函数我们常用符号 R表示关系,如个体 a与 b之间存在关系 R,则记作 aRb,或 〈 a,b〉 ∈ R,否则 a b 或 〈 a,b〉R。 R只是关系的一种表示符号,至于是什么关系，需要时需附注。 同时关系并不限于同一类事物之间，也存在于不同物体之间。 如旅客住店,张,王,李、赵四人,1,2,3号房间,张住 1号,李住 1号,王住2号,赵住 3号。 若分别以 a,b,c,d 表示四人,R表示住宿关系,则有 R={〈 a,1〉,〈 c,1〉,〈 b,2〉,〈 d,3〉 }。 因此我们看到住宿关系 R是序偶的集合。R第 4章 二元关系和函数定义 4.2.1 任何序偶的集合,确定了一个二元关系，并称该集合为一个二元关系,记作 R 。 二元关系也简称关系。 对于二元关系 R,如果 〈 x,y〉 ∈ R,也可记作 xRy。定义并不要求 R中的元素 〈 x,y〉 中的 x,y取自哪个个体域 。 因此,R={〈 2,a〉,〈 u,狗 〉,〈 钱币,思想 〉 }也是一个二元关系 。 因为它符合关系的定义,但是无意义,显然对毫无意义的关系的研究也无甚意义 。 若规定关系 R中序偶 〈 x,y〉 的 x∈ A,y∈ B,如上面的住店关系,这样的序偶构成的关系 R,称为从 A到B的一个二元关系 。 由 A× B的定义知,从 A到 B的任何二元关系,均是 A× B的子集,因此有下面的定义 。第 4章 二元关系和函数定义 4.2.2 R称为集合 A1,A2,…,An-1 到 An上的 n元关系（ n array relations）,如果 R是A1× A2× … × An-1× An的一个子集。 当 A1＝ A2＝ …＝ An-1＝ An时,也称 R为 A上的 n元关系。 当 n=2时,称R为 A1到 A2的二元关系。 n元关系也可视为A1× A2× … × An-1 到 An的二元关系。由于关系是集合 （ 只是以序偶为元素 ）,因此,所有规定集合的方式均适用于关系的确定 。第 4章 二元关系和函数当 A,B均是有限集合时,因为 |A× B|=|A|·|B|,而其子集的个数恰是幂集 P(A× B)的元素个数,|P(A× B)|=2 |A|·|B|,所以由 A到 B共有 2 |A|·|B| 个不同的二元关系 。下面介绍一些特殊的二元关系 。 设 R是 A到 B的二元关系：A× B,A到 B的空关系 。A× B A× B,称 A× B 为 A到 B的全域关系 。IA=｛ 〈 x,x〉 |x∈ A｝,称为 A上的恒等关系 。第 4章 二元关系和函数若 A是实数集合或其子集,R是 A上的二元关系,可定义下面几种常见的二元关系：若 R={〈 x,y〉 |x∈ A∧ y∈ B∧ x≤y },则称 R为小于等于关系,常记为 ≤。若 R={〈 x,y〉 |x∈ A∧ y∈ B∧ x|y },则称 R为整除关系,常记为 |,其中 x|y是 x整除 y。第 4章 二元关系和函数若 A是任意集合,R是 A上的二元关系,下面的关系也常见：若 R={〈 x,y〉 |x∈ P(A)∧ y∈ P(B)∧ x y},则称 R为包含关系,。若 R={〈 x,y〉 |x∈ P(A)∧ y∈ P(B)∧ x y},则称 R为真包含关系,。第 4章 二元关系和函数定义 4.2.3 设 R是 A到 B的二元关系 。（ 1） 用 xRy表示 〈 x,y〉 ∈ R,意为 x,y有 R关系（ 为使可读性好,我们将分场合使用这两种表达方式中的某一种 ） 。 x y表示 〈 x,y〉 R。（ 2） 由 〈 x,y〉 ∈ R的所有 x组成的集合称为关系 R的定义域 （ domain） 记作 DomR,即Dom R=｛ x|x∈ A∧ y(y∈ A∧ 〈 x,y〉 ∈ R)｝R?第 4章 二元关系和函数（ 3） 由 〈 x,y〉 ∈ R的所有 y组成的集合称为关系 R的值域 （ range）,记作 Ran R,即Ran R＝ {y|y∈ B∧ x(x∈ A∧ 〈 x,y〉 ∈ R)｝（ 4） R的定义域和值域的并集称为 R的域,记作Fld R。 形式化表示为：Fld R=Dom R∪ Ran R一般地,若 R是 A到 B的二元关系,则有 DomR A,Ran R B。第 4章 二元关系和函数【 例 4.2.1】 设 A=｛ 1,2,3,4,5,6｝,B＝ ｛ a,b,c,d｝,则R＝ ｛ 〈 2,a〉,〈 2,b〉,〈 3,b〉,〈 4 c〉,〈 6,c〉 ｝那么如图 4.2.1所示：Dom R＝ ｛ 2,3,4,6｝,Ran R=｛ a,b,c｝Fld R={2,3,4,6,a,b,c}各箭头分别表示 2Ra,2Rb,3Rb,4Rc,6Rc。第 4章 二元关系和函数图 4.2.1234615abcd第 4章 二元关系和函数在此引入关系的表示法 。因为关系是一种特殊的集合,所以关系仍然能使用集合的表示方法 。 如集合的列举法和描述法 。 除此之外,有限集合的二元关系亦可用图形来表示,这就是关系图 。第 4章 二元关系和函数定义 4.2.4 设集合 A={x1,x2,…,xm}到 B={y1,y2,…,ym}上的一个二元关系为 R,以集合 A,B中的元素为顶点,在图中用,,&表示顶点 。 若 xiRyj,则可自顶点 xi向顶点 yj引有向边 〈 xi,yj〉,其箭头指向 yj。 用这种方法画出的图称为关系图 （ graph of relation） 。如图 4.2.1就表示了例 4.2.1中的关系 R。如关系 R是定义在一个集合 A 上,即 R A× A,只需要画出集合 A中的每个元素即可 。 起点和终点重合的有向边称为环 （ loop） 。第 4章 二元关系和函数【 例 4.2.2】 求集合 A=｛ 1,2,3,4 ｝ 上的恒等关系,空关系,全关系和小于关系的关系图 。解 恒等关系IA={〈 1,1〉,〈 2,2〉,〈 3,3〉,〈 4,4〉 }={ }全关系 A× A={〈 1,1〉,〈 2,2〉,〈 3,3〉,〈 4,4〉,〈 1,2〉,〈 2,1〉,〈 3,1〉,〈 4,1〉,〈 1,3〉,〈 2,3〉,〈 3,2〉,〈 4,2〉,〈 1,4〉,〈 2,4〉,〈 3,4〉,〈 4,3〉,}第 4章 二元关系和函数小于关系 LA={〈 1,2〉,〈 1,3〉,〈 2,3〉,〈 1,4〉,〈 2,4〉,〈 3,4〉 }其关系图分别见图 4.2.2,图 4.2.3,图 4.2.4,图 4.2.5。第 4章 二元关系和函数图 4.2.2 图 4.2.31 23 41 23 4第 4章 二元关系和函数图 4.2.4 图 4.2.513 421 23 4第 4章 二元关系和函数当 A中元素的次序标定后,对于任何关系 R,R的关系图与 R的集合表达式是可以唯一相互确定的 。 我们也可看出关系图直观清晰,是分析关系性质的方便形式,但是对它不便于进行运算 。 关系还有一种便于运算的表示形式,称为关系矩阵 （ matrix of relation） 。定义 4.2.5 设 R A× B,A=｛ a1,a2,…,am｝,B=｛ b1,b2,…,bn｝,那么 R的关系矩阵 MR为一 m× n矩阵,它的第 i,j分量 rij 只取值 0或 1,而10ijr当且仅当 aiRbj当且仅当ija Rb第 4章 二元关系和函数例如,图 4.2.1所示关系 R的关系矩阵为00001 1 0 00 1 0 00 0 1 000000 0 1 0RM第 4章 二元关系和函数例 4.2.2中的图 4.2.2,图 4.2.3,图 4.2.4,图 4.2.5所示关系的关系矩阵分别是1 0 0 0 0 0 0 00 1 0 0 0 0 0 00 0 1 0 0 0 0 00 0 0 1 0 0 0 01 1 1 1 0 1 1 11 1 1 1 0 0 1 11 1 1 1 0 0 0 11 1 1 1 0 0 0 0AAIA A IMMMM第 4章 二元关系和函数关系 R的集合表达式与 R的关系矩阵也可以唯一相互确定,因此 R的集合表达式,关系图,关系矩阵三者均可以唯一相互确定,并且它们各有各的特点,可以根据不同的需要选用不同的表达方式 。第 4章 二元关系和函数4.3 关 系 的 运 算A到 B的二元关系 R是 A× B的子集,亦即关系是序偶的集合。 故在同一集合上的关系,可以进行集合的所有运算。 作为集合对关系作并,交,差,补运算是理所当然的,但为了运算结果作为关系的意义更明确,我们也要求运算对象应有相同的域,从而运算结果是同一域间的关系。 同前所述,这一要求也不是本质的。 因此,在讨论关系运算时,我们有时忽略它们的域。第 4章 二元关系和函数定义 4.3.1 设 R和 S为 A到 B的二元关系,其并,交,差,补运算定义如下：R∪ S＝ ｛ 〈 x,y〉 |xRy∨ xSy｝R∩S＝ ｛ 〈 x,y〉 |xRy∧ xSy｝R-S＝ ｛ 〈 x,y〉 |xRy∧?xS y｝～ R＝ A× B-R＝ ｛ 〈 x,y〉 |?xR y｝第 4章 二元关系和函数【 例 4.3.1】 设 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〉 }S={〈 4,1〉 }R∪ S={〈 1,1〉,〈 1,3〉,〈 2,2〉,〈 2,4〉,〈 3,1〉,〈 3,3〉,〈 4,2〉,〈 4,4〉,〈 4,1〉 }第 4章 二元关系和函数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={〈 1,1〉,〈 1,3〉,〈 2,2〉,〈 2,4〉,〈 3,1〉,〈 3,3〉,〈 4,2〉,〈 4,4〉,〈 4,1〉 }第 4章 二元关系和函数关系并,交,差,补的矩阵可用如下方法求取：M R∪ S = M R∨ M S（ 矩阵对应分量作逻辑析取运算 ）M R∩S = M R∧ M S（ 矩阵对应分量作逻辑合取运算 ）M R-S = M R∩～ S = M R∧ M ～ SM ～ S =～ ( M S)（ 矩阵各分量作逻辑非运算 ）第 4章 二元关系和函数定义 4.3.2 设 R是 A到 B的关系,R的逆关系或逆（ converse）是 B到 A的关系,记为 R -1,规定为R -1 =｛ 〈 y,x〉 |xRy｝由定义很显然,对任意 x∈ A,y∈ B,有xRy yR -1 x若 M R为 R的关系矩阵,那么（ M′表示矩阵 M的转置矩阵 ）1 RRMM第 4章 二元关系和函数【 例 4.3.3】 设 R表示父子关系,即 〈 x,y〉 ∈ R说明x是 y的父亲,R R就表示祖孙关系 。【 例 4.3.4】 设 R表示朋友关系,S表示直接后门关系,R S就表示间接后门关系 。第 4章 二元关系和函数【 例 4.3.5】 设 A＝ ｛ 0,1,2,3,4,5｝,B＝ ｛ 2,4,6｝,C＝ ｛ 1,3,5｝,R A× B,SB× C，R＝ ｛ 〈 1,2〉,〈 2,4〉,〈 3,4〉,〈 5,6〉 ｝,S＝ ｛ 〈 2,l〉,〈 2,5〉,〈 6,3〉 ｝R S。解R.S＝ ｛ 〈 l,l〉,〈 1,5〉,〈 5,3〉 ｝ A× C用图表示 R S,如图 4.3.1所示 。第 4章 二元关系和函数图 4.3.1012345135246A B CR SR S第 4章 二元关系和函数【 例 4.3.6】 设集合 A＝ ｛ 1,2,3,4,5｝,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〉 ｝求 Sο S,SοR,Rο R,Sο S,(Rο S)ο R,Rο (Sο R)。第 4章 二元关系和函数解 Rο S＝ ｛ 〈 4,l〉,〈 1,4〉,〈 3,2〉,〈 2,3〉 ｝＝ ｛ 〈 x,z〉 |x+z＝ 5｝Sο R＝ ｛ 〈 0,3〉,〈 1,2〉,〈 2,1〉,〈 3,0〉 ｝＝ ｛ 〈 x,z〉 |x+z＝ 3｝Rο R＝ ｛ 〈 0,0〉,〈 4,4〉,〈 1,1〉,〈 3,3〉,〈 2,2〉 ｝ ＝ ｛ 〈 x,z〉 |x-z＝ 0｝第 4章 二元关系和函数Sο S＝ ｛ 〈 0,2〉,〈 1,3〉,〈 2,4〉 ｝ ＝ ｛ 〈 x,z〉 |z-x＝ 2｝(Rο S)ο R ＝ ｛ 〈 4,3〉,〈 1,0〉,〈 3,2〉,〈 2,1〉 ｝Rο (Sο R) ＝ ｛ 〈 4,3〉,〈 3,2〉,〈 2,1〉,〈 1,0〉 ｝从上例已可看出,一般地 Rο S≠Sο R。复合运算的性质由下面两个定理介绍 。第 4章 二元关系和函数定理 4.3.2 设 IA,IB为集合 A,B上的恒等关系,R A× B,那么（ 1） IAο R=Rο IB=R（ 2） Φο R=RοΦ=Φ第 4章 二元关系和函数证明 （ 1） 为证 IAο R R,〈 x,y〉 ∈ IAο R。〈 x,y〉 ∈ IAο R u(u∈ A∧ 〈 x,u〉 ∈ IA∧ 〈 u,y〉 ∈ R)u(u∈ A∧ x=u∧ 〈 u,y〉 ∈ R)〈 x,y〉 ∈ R所以 IAο R R得证 。第 4章 二元关系和函数（ 2) 显然 Φ Φο R,下证 Φο R Φ。〈 x,y〉 ∈ Φο R。〈 x,y〉 ∈ Φο R u(u∈ A∧ 〈 x,u〉 ∈Φ∧ 〈 u,y〉 ∈ R)〈 x,u〉 ∈ Φ说明命题的前件为假,整个蕴含式为真,所以Φο R Φ。 因此 Φο R=Φ。 同理可证 Rο Φ =Φ。第 4章 二元关系和函数定理 4.3.3 设 R,S,T均为 A上二元关系,那么（ 1） Rο (S∪ T)=(Rο S)∪ (Rο T)（ 2） (S∪ T)ο R=(Sο R)∪ (Tο R)（ 3） Rο (S∩T) (Rο S)∩(Rο T)（ 4） (S∩T)ο R (Sο R)∩(Tο R)（ 5） Rο (Sο T)=(Rο S)ο T（ 6） (Rο S) -1 =S -1ο R -1第 4章 二元关系和函数证明 我们仅证明 （ 1）,（ 4）,（ 5）,另外三式的证明留给读者完成 。（ 1） 对任意 x,y∈ A〈 x,y〉 ∈ Rο (S∪ T) u (〈 x,u〉 ∈ R∧ 〈 u,y〉 ∈ S∪ T)u(〈 x,u〉 ∈ R∧ (〈 u,y〉 ∈ S∨ 〈 u,y〉 ∈ T))u((〈 x,u〉 ∈ R∧ 〈 u,y〉 ∈ S)∨ (〈 x,u〉 ∈ R∧ 〈 u,y〉 ∈ T))第 4章 二元关系和函数u(〈 x,u〉 ∈ R∧ 〈 u,y〉 ∈ S)∨ u(〈 x,u〉 ∈ R∧ 〈 u,y〉 ∈ T)〈 x,y〉 ∈ Rο S∨ 〈 x,y〉 ∈ Rο T〈 x,y〉 ∈ Rο S∪ Rο T故 Rο (S∪ T)=(Rο S)∪ (Rο T)。第 4章 二元关系和函数（ ４ ） 对任意 x,y∈ A〈 x,y〉 ∈ (S∩T)ο R u(〈 x,u〉 ∈ (S∩T)∧ 〈 u,y〉 ∈ R)u(〈 x,u〉 ∈ S∧ 〈 x,u〉 ∈ T∧ 〈 u,y〉 ∈ R)u(〈 x,u〉 ∈ S∧ 〈 u,y〉 ∈ R∧ 〈 x,u〉 ∈ T∧ 〈 u,y〉 ∈ R)u(〈 x,u〉 ∈ S∧ 〈 u,y〉 ∈ R)∧ u∈ 〈 x,u〉 ∈ T∧ 〈 u,y〉 ∈ R)〈 x,y〉 ∈ (Sο R)∧ 〈 x,y〉 ∈ (Tο R)〈 x,y〉 ∈ (Sο R)∩(Tο R)故 (S∩T)ο R (Sο R)∩(Tο R)。第 4章 二元关系和函数定义 4.3.4 设 R是 A上的关系,n个 R的复合称为 R的n次幂。 由于关系复合运算有结合律,因此用“幂”表示集合上关系对自身的复合是适当的，R n= Rο … ο R,规定 R 0＝ IA（ R为 A上二元关系）。R n满足下列性质。定理 4.3.4 设 R为 A上二元关系,m,n为自然数,那么(1) R n+1 =R nο R=Rο R n=R mο R n-m+1(2) R mο R n＝ R m+n(3) (R m) n＝ R mn(4) (R -1 ) n=(R n) -1第 4章 二元关系和函数【 例 4.3.7】 设 A={0,1,2,3,4},R={〈 0,0〉,〈 0,1〉,〈 1,3〉,〈 2,4〉,〈 3,1〉,〈 4,4〉 }解 R 2={〈 0,0〉,〈 0,1〉,〈 0,3〉,〈 1,1〉,〈 2,4〉,〈 3,3〉,〈 4,4〉 }R 3={〈 0,0〉,〈 0,1〉,〈 0,3〉,〈 1,3〉,〈 2,4〉,〈 3,1〉,〈 4,4〉 }第 4章 二元关系和函数R 4={〈 0,0〉,〈 0,1〉,〈 0,3〉,〈 1,1〉,〈 2,4〉,〈 3,3〉,〈 4,4〉 }=R 2R,R 2,R 3,R 4的关系图如图 4.3.2所示 。R,R 2,R 3,R 4所对应的关系矩阵为第 4章 二元关系和函数23 2 4 31 1 0 0 0 1 1 0 1 00 0 0 1 0 0 1 0 0 00 0 0 0 1 0 0 0 0 10 1 0 0 0 0 0 0 1 00 0 0 0 1 0 0 0 0 11 1 0 1 0 1 1 0 1 00 0 0 1 0 0 1 0 0 00 0 0 0 1 0 0 0 0 10 1 0 0 0 0 0 0 1 00 0 0 0 1 0 0 0 0 1M M M MM M M M M M第 4章 二元关系和函数图 4.3.201342R01342R201342R3013 42R4第 4章 二元关系和函数定理 4.3.5 设集合 A的基数为 n,R是 A上二元关系,那么存在自然数 i,j使得证明 我们知道,当 |A|=n时,A上不同二元关系共个,令,因此,在 R 0,R 1,R2,…,R K这 K+l个关系中,至少有两个是相同的 （ 鸽巢原理 ）,即有 i,j(0≤i＜ j≤ ),使 R i＝ R j 。ijRR?22n 22nK?22n第 4章 二元关系和函数定义 4.3.5 设 R为 A到 B的二元关系,A在 R下的像 R［ A］ 为集合R［ A］ ={y|( x)(x∈ A∧ 〈 x,y〉 ∈ R)}集合在关系下的像的性质：定理 4.3.6 R是 X到 Y的关系和集合 A,B,则（ 1） R［ A∪ B］ =R［ A］ ∪ R［ B］（ 2） R［ ∪ A ］ =∪ {R［ B］ |B∈ A}（ 3） R［ A∩B］ R［ A］ ∩R［ B］（ 4） R［ ∩A ］ ∩{R［ B］ |B∈ A} (A≠Φ)（ 5） R［ A］ -R［ B］ R［ A-B］第 4章 二元关系和函数4.4 关 系 的 性 质本节总假定关系是某一非空集合上的二元关系,这一假定不失一般性 。 因为任一 A到 B的关系 R,即R A× B,A× B (A∪ B)× (A∪ B),所以关系 R总可看成是 A∪ B上的关系,它与原关系 R具有完全相同的序偶,对它的讨论代替对 R的讨论无损于问题的本质 。第 4章 二元关系和函数定义 4.4.1 设 R是 A上的二元关系,即 R A× A。（ 1） 称 R是自反的 （ reflexive）,如果对任意 x∈ A，均有 xRx。 即 R在 A x(x∈ A→xRx)。（ 2） 称 R是反自反的 （ irreflexive）,如果对任意x∈ A,xRx均不成立 。 即 R在 A 上是反自反的当且仅当x(x∈ A→ xRx)。第 4章 二元关系和函数（ 3） 称 R是对称的（ Symmetric）,如果对任意x∈ A,y∈ A,xRy蕴涵 yRx。 即 R在 A 上是对称的当且仅x y(x∈ A∧ y∈ A∧ xRy→yRx)。（ 4） 称 R是反对称的（ antisymmetric）,如果对任意 x∈ A,y∈ A,xRy且 yRx蕴涵 x＝ y。即 R在 Ax y(x∈ A∧ y∈ A∧ xRy∧ yRx→x=y)。 反对称性的另一种等价的定义为,R在 Ax y(x∈ A∧ y∈ A∧ xRy∧ x≠y→〈 y,x〉 R)。第 4章 二元关系和函数（ 5） 称 R是传递的（ transitive）,如果对任意x∈ A,y∈ A,z∈ A,xRy且 yRz蕴涵 xRz 。 即 R在 A 上是x y z(x∈ A∧ y∈ A∧ z∈ A∧ xRy∧ yRz→xRz)。第 4章 二元关系和函数【 例 4.4.1】 设 A=｛ a,b,c｝,以下各关系Ri（ i＝ 1,2,…,8） 均为 A上二元关系 。（ 1） R1＝ ｛ 〈 a,a〉,〈 a,c〉,〈 b,b〉,〈 c,c〉 ｝ 是自反的,而 R2＝ ｛ 〈 a,c〉,〈 c，a〉 ｝ 不是自反的,是反自反的 。 存在既不自反也不反自反的二元关系,例如 R3＝ ｛ 〈 a,a〉 ｝ 。 显然 A上的 Φ关系是反自反的,不是自反的 。 可是值得注意的是,当 A＝ Φ时 （ 这时 A上只有一个关系 Φ）,A上空关系既是自反的,又是反自反的,因为 A＝ Φ使两者定义的前提总为假 。第 4章 二元关系和函数（ 2） R 4＝ ｛ 〈 a,b〉,〈 b,a〉 ｝ 是对称的；R5＝ ｛ 〈 a,c〉,〈 c,a〉,〈 a,b〉,〈 a,a〉 ｝不是对称的； R6＝ ｛ 〈 a,b〉,〈 a,c〉 ｝ 是反对称的 。 其实 R5既不是对称的,也不是反对称的 。 特别有意思的是,存在既对称又反对称的二元关系,例如A上的恒等关系 IA。（ 3） R7＝ ｛ 〈 a,b〉,〈 b,c〉,〈 a,c〉,〈 c,c〉 ｝ 是传递的,但 R7-｛ 〈 a,c〉 ｝ 便不是传递的了 。 应当注意,A上的空关系 Φ，R8＝ ｛ 〈 a,b〉 ｝ 等是传递的,因为传递性定义的前提对它们而言均为假 。第 4章 二元关系和函数（ 4） 任何非空集合上的空关系都是反自反,对称,反对称,传递的； 其上的相等关系是自反,对称,反对称,传递的； 其上的全关系是自反,对称,传递的 。(5) 三角形的相似关系,全等关系是自反,对称,传递的 。（ 6） 正整数集合上的整除关系是自反,反对称,传递的； 但整数集合上的整除关系只有传递性 。 判断一个关系是否具有上述某种的性质,除直接用定义,还有下面的充要条件 。第 4章 二元关系和函数定理 4.4.1 设 R为集合 A上二元关系,即 R A× A,则（ 1） R是自反的当且仅当 IA R。（ 2） R是反自反的当且仅当 IA∩R=Φ。（ 3） R是对称的当且仅当 R=R -1 。（ 4） R是反对称的当且仅当 R∩R -1 IA。（ 5） R是传递的当且仅当 Rο R R。第 4章 二元关系和函数证明 （ 1） 先证必要性,因为 R是自反的,设对任意的〈 x,y〉 ∈ IA x ∈ A∧ y∈ A∧ x=y 〈 x,y〉 ∈ R。再证充分性,任取 x∈ A,有 〈 x,x〉 ∈ IA,因为 IA( R,所以 〈 x,x〉 ∈ R,因此 R是自反的 。第 4章 二元关系和函数（ 2） 先证必要性,用反证法 。假设 R∩IA≠Φ,必存在 〈 x,y〉 ∈ R∩IA 〈 x,y〉 ∈ IA,由于 IA是 A上的恒等关系,从而有 x=y,所以〈 x,x〉 ∈ R,这与 R 在 A上是反自反的相矛盾 。再证充分性,任取 x∈ A,则有 x∈ A 〈 x,x〉 ∈ IA〈 x,x〉 R(由于 IA∩R=Φ),从而证明了 R在 A上是反自反的 。第 4章 二元关系和函数（ 3） 先证必要性,设 R对称,那么对任意 x,y∈ A,有〈 x,y〉 ∈ R 〈 y,x〉 ∈ R （ 因为 R在 A上对称 ）〈 x,y 〉 ∈ R -1故 R=R -1 。再证充分性,任取 〈 x,y〉 ∈ R,由 R=R -1,有〈 x,y〉 ∈ R 〈 x,y〉 ∈ R -1〈 y,x〉 ∈ R所以 R在 A上是对称的 。第 4章 二元关系和函数（ 4） 先证必要性,设 R反对称,那么对任意 x,y∈ A,有〈 x,y〉 ∈ R∩R -1 〈 x,y〉 ∈ R∧ 〈 x,y〉 ∈ R -1〈 x,y〉 ∈ R∧ 〈 y,x〉 ∈ Rx=y （ R反对称 ）〈 x,y〉 ∈ IA因此 R∩R -1 IA。第 4章 二元关系和函数再证充分性,设 R∩R -1 IA。 为证 R反对称,又设 〈 x,y〉 ∈ R∧ 〈 y,x 〉 ∈ R,由 R∩R -1 IA,有〈 x,y〉 ∈ R∧ 〈 y,x〉 ∈ R 〈 x,y〉 ∈ R∧ 〈 x,y〉 ∈ R -1〈 x,y〉 ∈ R∩R -1〈 x,y〉 ∈ IA因而 x=y。 所以 R在 A上是反对称的,得证 。第 4章 二元关系和函数（ 5） 先证必要性,设 R传递,那么对任意 x,y∈ A,有〈 x,y〉 ∈ Rο R u(u∈ A∧ 〈 x,u〉 ∈ R∧ 〈 u,y 〉 ∈ R)u(u∈ A∧ 〈 x,y〉 ∈ R) （ R是传递的 ）〈 x,y〉 ∈ R故 Rο R R。第 4章 二元关系和函数再证充分性,设 Rο R R。 为证 R传递,设有〈 x,y〉 ∈ R,〈 y,z〉 ∈ R。〈 x,y〉 ∈ R∧ 〈 y,z〉 ∈ R 〈 x,z〉 ∈ Rο R〈 x,z〉 ∈ R (Rο R R)所以 R在 A上是传递的,得证 。关系的基本性质与关系图,关系矩阵有怎样的联系呢？ 表 4.4.1详解之 。第 4章 二元关系和函数表 4.4.1第 4章 二元关系和函数【 例 4.4.2】 设 Ri是 A={1,2,3}上的二元关系（如图4.4.1所示）,判断它们各具有什么性质？ 并说明理由。解 根据关系图的特征,我们可判断下列各关系具有的性质。 R1具有反自反性,对称性,反对称性、传递性。 因为每一结点处均无环,既无双边又无单边，既无双边又无三角形。第 4章 二元关系和函数R2具有自反性,对称性,反对称性,传递性 。因为每一结点处有一环,既无双边又无单边,既无双边又无三角形 。R3具有自反性,对称性,传递性 。 因为每一结点处有一环,有边就有双边,有双边又有双环,有三角形就是向量三角形 。R4具有反对称性,传递性 。 因为无双边,无三角形 。R5具有对称性 。 因为无单边 。第 4章 二元关系和函数R6具有反自反性,反对称性 。 因为每一结点处均无环 。R7具有自反性,对称性,反对称性,传递性 。 因为每一结点处有一环,有三角形,且是向量三角形 。R8具有反自反性,传递性 。 因为每一结点处均无环,有三角形,且是向量三角形 。R9均不具备 。第 4章 二元关系和函数图 4.4.112 312 312 312 3R1R2R3R412 3 2 312 3R7R5R612 3R812 3R91第 4章 二元关系和函数关系是序偶的集合,可作交,并,差,逆,复合运算 。 如果已知某些关系具有某一性质,经过关系运算后的结果是否仍具有这一性质,是一个令人关注的问题 。 如果是,我们称该性质对这一运算封闭 。 现在我们来讨论五大特性对基本运算的封闭性 。第 4章 二元关系和函数定理 4.4.2 设 R1,R2是 A上的自反关系,则 R -11、R1∩R2,R1∪ R2,R1ο R2也是 A上的自反关系 。 证明留给读者 。定理 4.4.3 设 R1,R2是 A上的对称关系,则 R -11,R1∩R2,R1∪ R2,R1-R2也是 A上的对称关系 。第 4章 二元关系和函数证明 仅证对称性对并运算封闭 。设 R1,R2对称,要证 R1∪ R2对称 。 任取 〈 x,y〉∈ R1∪ R2,那么 〈 x,y〉 ∈ R1或 〈 x,y〉 ∈ R2。 由 R1，R2对称知 〈 y,x〉 ∈ R1或 〈 y,x〉 ∈ R2,因而 〈 y,x〉∈ R1∪ R2。 R1∪ R2对称性得证 。第 4章 二元关系和函数定理 4.4.4 设 R1,R2是 A上的传递关系,则R -11,R1∩R2是 A上的传递关系。 但 R1∪ R2不一定是传递的。证明 (1) 证传递性对求逆运算封闭 。设 R1传递,要证 R -11传递,设有 〈 x,y〉 ∈ R -11,〈 y,z〉 ∈ R -11,那么 〈 y,x 〉 ∈ R1,〈 z,y〉 ∈ R1。 由R1具有传递性可得 〈 z,x〉 ∈ R1,即 〈 x,z〉 ∈ R -11 。R -11在 A上是传递的,得证。第 4章 二元关系和函数(2) 证传递性对交运算封闭 。设 R1,R2传递,要证 R1∩R2传递 。 设有 〈 x,y〉∈ R1∩R2,〈 y,z〉 ∈ R1∩R2,那么 〈 x,y〉 ∈ R1,〈 x,y〉∈ R2,〈 y,z〉 ∈ R1,〈 y,z〉 ∈ R2。 由 R1,R2具有传递性,可得 〈 x,z〉 ∈ R1,〈 x,z〉 ∈ R2,从而 〈 x,z〉∈ R1∩R2。 故 R1∩R2在 A上是传递的,得证 。第 4章 二元关系和函数定理 4.4.5 设 R1,R2是 A上的反对称关系,则R-11,R1∩R2,R1-R2是 A上的反对称关系 。 但 R1∪ R2不一定是反对称的 。证明 仅证反对称性对差运算封闭 。设 R1,R2反对称,要证 R1-R2反对称 。设 〈 x,y〉 ∈ (R1-R2)且 〈 y,x〉 ∈ (R1-R2),因而 〈 x,y〉∈ R1,〈 y,x〉 ∈ R1,从而由 R1的反对称性得 x=y。 这就完成了 R1-R2反对称的证明 。第 4章 二元关系和函数定理 4.4.6 设 R1,R2是 A上的反自反关系,则R -11,R1∩R2,R1∪ R2,R1-R2是 A上的反自反关系 。证明留给读者 。我们举例说明反自反性,对称性,反对称性,传递性对合成运算均不封闭。第 4章 二元关系和函数【 例 4.4.3】 A={a,b,c},讨论在下列各种情况下 Rο S具有的性质 。(1) R={〈 a,b〉 },S={〈 b,a〉 },R,S是反自反的 。(2) R={〈 a,b〉,〈 b,a〉 },S={〈 b,c〉,〈 c,b〉 },R,S是对称的 。(3) R={〈 a,b〉,〈 b,c〉 },S={〈 b,b〉,〈 c,a〉 },R,S是反对称的 。(4） R={〈 a,b〉,〈 b,c〉,〈 a,c〉 },S={〈 b,a〉,〈 b,c〉,〈 c,a〉 },R,S是传递的 。第 4章 二元关系和函数解（ 1） Rο S={〈 a,a〉 },所以 Rο S不是反自反的 。（ 2） Rο S={〈 a,c〉 },所以 Rο S不是对称的 。（ 3） Rο S={〈 a,b〉,〈 b,a〉 },所以 Rο S是对称的 。（ 4） Rο S={〈 a,a〉,〈 a,c〉,〈 b,a〉 },因为 〈 b,a〉∈ Rο S,〈 a,c〉 ∈ Rο S,但 〈 b,c〉 Rο S,所以 Rο S不是传递的 。第 4章 二元关系和函数4.5 关 系 的 闭 包闭包运算是关系运算中一种比较重要的特殊运算,是对原关系的一种扩充 。 在实际应用中,有时会遇到这样的问题,给定了的某一关系并不具有某种性质,要使其具有这一性质,就需要对原关系进行扩充,而所进行的扩充又是 &最小 &的 。 这种关系的扩充就是对原关系的这一性质的闭包运算 。第 4章 二元关系和函数【 定义 4.5.1】 设 R是非空集合 A 上的关系,如果 A上有另一个关系 R′满足：（ 1） R′是自反的 （ 对称的或传递的 ） ；（ 2） R R′；（ 3） 对 A上任何自反的 （ 对称的或传递的 ） 关系 R″,若 R R″,均有 R′ R″,则称 R′为 R的自反 （ 对称或传递 ） 闭包 。第 4章 二元关系和函数一般将 R的自反闭包记作 r(R),对称闭包记作 s(R)，传递闭包记作 t(R)。 它们分别是具有自反性或对称性传递性的 R的 &最小 &超集合 。 称 r,s,t为闭包运算,它们作用于关系 R后,分别产生包含 R的,最小的具有自反性,对称性,传递性的二元关系 。 这三个闭包运算也可由下述定理来构造 。第 4章 二元关系和函数定理 4.5.1 设 R是集合 A上的二元关系,那么（ 1） r(R)=IA∪ R（ 2） s(R)=R∪ R -1（ 3）1() iit R R第 4章 二元关系和函数证明（ 1） IA∪ R自反且 R IA∪ R是显然的 。 为证 IA∪ R为自反闭包,还需证它的 &最小性 &。 为此,令 R′自反,且 R R′,欲证 IA∪ R R′。 由于 R′自反,据定理 4.4.1,IA R′,连同 R R′，即得 IA∪ R R′。（ 2） 本式证明留给读者 。（ 3）1iiRR是显然的。第 4章 二元关系和函数【 例 4.5.1】 设 A＝ {1,2,3},R1={〈 1,2〉,〈 2,1〉,〈 1,3〉,〈 1,1〉 },R2={〈 1,2〉,〈 2,1〉 },R3={〈 1,2〉 },求它们的闭包 。解 r(R1)=IA∪ R={〈 1,1〉,〈 2,2〉,〈 3,3〉,〈 1,2〉,〈 2,1〉,〈 1,3〉 }s(R1)=R∪ R -1={〈 1,2〉,〈 2,1〉,〈 1,3〉,〈 3,1〉,〈 1,1〉 }第 4章 二元关系和函数t(R1)={〈 1,2〉,〈 2,1〉,〈 1,1〉,〈 2,2〉,〈 1,3〉,〈 2,3〉 }r(R2)=IA∪ R={〈 1,1〉,〈 2,2〉,〈 3,3〉,〈 1,2〉,〈 2,1〉 }s(R2)=R∪ R -1 ={〈 1,2〉,〈 2,1〉 }=R2t(R2)={〈 1,2〉,〈 2,1〉,〈 1,1〉,〈 2,2〉 }r(R3)=IA∪ R={〈 1,2〉,〈 1,1〉,〈 2,2〉,〈 3,3〉 }s(R3)=R∪ R -1 ={〈 1,2〉,〈 2,1〉 }t(R3)={〈 1,2〉 }=R3第 4章 二元关系和函数【 例 4.5.2】 设 R是集合 A={a,b,c,d}上的二元关系,R={〈 a,b〉,〈 b,a〉,〈 b,c〉,〈 c,d〉 }。 求 R的闭包：r（ R）,s（ R）,t（ R）,并画出对应的关系图 。解 r(R)={〈 a,b〉,〈 b,a〉,〈 b,c〉,〈 c,d〉,〈 a,a〉,〈 b,b〉,〈 c,c〉,〈 d,d〉 }s(R)={〈 a,b〉,〈 b,a〉,〈 b,c〉,〈 c,d〉,〈 c,b〉,〈 d,c〉 }t(R)={〈 a,b〉,〈 b,a〉,〈 b,c〉,〈 c,d〉,〈 a,a〉,〈 a,c〉,〈 b,b〉,〈 b,d〉,〈 a,d〉 }其对应的关系图分别如图 4.5.1(a),(b),(c)所示 。第 4章 二元关系和函数图 4.5.1a b c d( a )a b c d a b c d( b )( c )第 4章 二元关系和函数从以上讨论可以看出,传递闭包的求取是很复杂的 。 但是,当集合 A为有限集时,A上二元关系的传递闭包的求取便可大大简化 。推论 A为非空有限集合,|A|=n。 R是 A上的关系,则存在正整数 k≤n,使得t(R)=R +=R∪ R 2∪ … ∪ R k第 4章 二元关系和函数下列算法是求取 R +的有效算法 。Warshall(沃夏尔 ) 算法,设 R为有限集 A上的二元关系,|A|=n,M为 R的关系矩阵,可如下求取 R +的关系矩阵 W。（ 1） 置 W为 M。（ 2） 置 i=1。（ 3） 对所有 j,1≤j≤n,做第 4章 二元关系和函数① 如果 W［ j,i］ =1,则对每一 k=1,2,…,n,置W［ j,k］ 为 W［ j,k］ ∨ W［ i,k］,即当第 j行,第 i列为 1时,对第 j行每个分量重新置值,取其当前值与第 i行的同列分量之析取 。② 否则对下一 j值进行 ① 。（ 4） 置 i为 i+1。（ 5） 若 i≤n,回到步骤 （ 3）,否则停止 。第 4章 二元关系和函数【 例 4.5.3】 设 A={1,2,3,4,},R={〈 1,1〉,〈 1,2〉,〈 2,3〉,〈 3,4〉,〈 4,2〉 },则R 2={〈 1,1〉,〈 1,2〉,〈 1,3〉,〈 2,4〉,〈 3,2〉,〈 4,3〉 }R 3={〈 1,1〉,〈 1,2〉,〈 1,3〉,〈 1,4〉,〈 2,2〉,〈 3,3〉,〈 4,4〉 }R 4={〈 1,1〉,〈 1,2〉,〈 1,3〉,〈 1,4〉,〈 2,3〉,〈 3,4〉,〈 4,2〉 }第 4章 二元关系和函数因此 R +=R∪ R 2∪ R 3∪ R 4={〈 1,1〉,〈 1,2〉,〈 1,3〉,〈 1,4〉,〈 2,2〉,〈 2,3〉,〈 2,4〉,〈 3,2〉,〈 3,3,〉,〈 3,4〉,〈 4,2〉,〈 4,3〉,〈 4,4〉 }现用 Warshall算法求取 R +。显然，1 1 0 00 0 1 00 0 0 10 1 0 0M第 4章 二元关系和函数以下使用 Warshall算法求取 W。（ 1） W以 M为初值 。（ 2） 当 i＝ 1时,由于 W中只有 W［ 1,1］ ＝ l,故需将第一行各元素与其本身作逻辑和,并把结果送第一行 。 即重新置值为 W［ 1,k］ ∨ W［ 1,k］ = W［ 1,k］,但 W 事实上无改变 。（ 3） 当 i=2时,由于 W ［ 1,2］ ＝ W ［ 4,2］ ＝ 1，故需将第一行和第四行各分量重新置值为 W ［ 1,k］∨ W［ 2,k］ 和 W ［ 4,k］ ∨ W ［ 2,k］ 。 于是有：第 4章 二元关系和函数1 1 1 00 0 1 00 0 0 10 1 1 0W第 4章 二元关系和函数（ 4） 当 i=3时,由于 W ［ 1,3］＝ W ［ 2,3］ ＝ W ［ 4,3］ =1,故需将第一,二,四行各分量重新置值,分别为 W ［ 1,k］ ∨ W ［ 3,k］＝ W ［ 1,k］,W ［ 2,k］ ∨ W ［ 3,k］ =W ［ 2，k］,W ［ 4,k］ ∨ W ［ 3,k］ = W ［ 3,k］ 。 于是有：1 1 1 10 0 1 10 0 0 10 1 1 1W第 4章 二元关系和函数（ 5） 当 i＝ 4时,由于 W ［ 1,4］ ＝ W ［ 2,4］ =W ［ 3,4］ = W ［ 4,4］ =1,故需将第一,二,三,四行各分量重新置值,分别为 W ［ 1,k］ ∨ W ［ 4,k］＝ W ［ 1,k］,W ［ 2,k］ ∨ W ［ 4,k］ = W ［ 2，k］,W ［ 3,k］ ∨ W［ 4,k］ = W ［ 3,k］,W［ 4,k］ ∨ W［ 4,k］ = W ［ 4,k］ 。 最终 W 为1 1 1 10 1 1 10 1 1 10 1 1 1W第 4章 二元关系和函数故 R +＝ {〈 1,1〉,〈 1,2〉,〈 1,3〉,〈 1,4〉,〈 2,2〉,〈 2,3〉,〈 2,4〉,〈 3,2〉,〈 3,3,〉,〈 3,4〉,〈 4,2〉,〈 4,3〉,〈 4,4〉 }。第 4章 二元关系和函数下面几个定理给出了闭包的主要性质 。定理 4.5.2 设 R是集合 A上任一关系,那么（ 1） R自反当且仅当 R=r(R)。（ 2） R对称当且仅当 R=s(R)。（ 3） R传递当且仅当 R=t(R)。第 4章 二元关系和函数证明 （ 1）,（ 3） 的证明留给读者,现证 （ 2） 。（ 2） 的充分性由 s(R)定义立得 。为证必要性,设 R对称,那么 R＝ R-1 （据定理4.4.1）。 另一方面,s(R)=R∪ R-1 =R∪ R=R,故s(R)=R。定理 4.5.3 对非空集合 A上的关系 R1,R2若 R1 R2，则（ 1） r(R1) r(R2)（ 2） s(R1) s(R2)（ 3） t(R1) t(R2)第 4章 二元关系和函数证明 （ 1） 和 （ 2） 的证明留作练习,下面仅证明 （ 3） 。因为 t(R2)传递,且 t(R2) R2,但 R1 R2，故 t(R2) R1。因 t(R1)是包含 R1的最小传递关系,所以 t(R1) t(R2)。第 4章 二元关系和函数定理 4.5.4 对非空集合 A上的关系 R1,R2,则（ 1） r(R1)∪ r(R2)=r(R1∪ R2)（ 2） s(R1)∪ s(R2)=s(R1∪ R2)（ 3） t(R1)∪ t(R2) t(R1∪ R2)?第 4章 二元关系和函数证明 (1） 和 （ 2） 的证明留作练习,下面仅证明 （ 3） 。因为 R1∪ R2 R1,由定理 4.5.3知t(R1∪ R2) t(R1)同理 t(R1∪ R2) t(R2)所以 t(R1∪ R2) t(R1)∪ t(R2)第 4章 二元关系和函数定理 4.5.5 设 R是集合 A上任意二元关系,则（ 1） 如果 R是自反的,那么 s(R)和 t(R)都是自反的 。（ 2） 如果 R是对称的,那么 r(R)和 t(R)都是对称的 。（ 3） 如果 R是传递的,那么 r(R)是传递的 。第 4章 二元关系和函数证明（ 1） 是显然的 。（ 2） 由于r(R) -1 =(IA∪ R) -1 =I -1A∪ R -1 =IA∪ R=r(R),故 r(R)是对称的。另外,由于对任意自然数 n，(R n) -1 =(R -1 ) n（ 据定理 4.3.4）,又由于 R对称,故 (R n) -1 =R n。 因此,对任意 〈 x,y〉 ∈ t(R),总有 i使 〈 x,y〉 ∈ R i,从而 〈 y,x〉 ∈ (R i) -1 =R i,即 〈 y,x〉 ∈ t(R)。 故 t(R)对称 。第 4章 二元关系和函数（ 3） 本式证明留给读者。 请注意,R传递并不保证 s(R)传递。 例如,R={〈 a,b〉 }是传递的,但是s(R)={〈 a,b〉,〈 b,a〉 }却不是传递的。第 4章 二元关系和函数定理 4.5.6 设 R为集合 A上的任一二元关系,那么（ 1） rs(R)＝ sr(R)（ 2） rt(R)＝ tr(R)（ 3） st(R) ts(R)证明（ 1） sr(R) =s(IA∪ R)=IA∪ R∪ (IA∪ R) -1=IA∪ R∪ R -1 =IA∪ s(R)=rs(R)第 4章 二元关系和函数（ 2） 易证1() niAAiI R I R对一切正整数 n均成立 （ 见本章习题 24）,于是11 1 1 11( ) ( ) ( )( ) ( )( ) ( )iAAijjAAi j i jiAiAtr R t I R I RI R I RIRI t R rt R第 4章 二元关系和函数（ 3） 由定理 4.5.3可知,任一闭包运算 Δ和任意二元关系 R1,R2,如果 R1 R2,那么 Δ(R1) Δ(R2)； 又据闭包定义,对任意二元关系 R有 R s(R),故 t(R)ts(R),st(R) sts(R) 。 由于 ts(R) 是对称的 （ 据定理4.5.5）,由定理 4.5.2知 sts(R)＝ ts(R)。 于是可得到st(R) ts(R)第 4章 二元关系和函数【 例 4.5.4】 设 R是集合 X上的二元关系,X={a,b,c}，R={〈 a,b〉,〈 b,c〉 }。 求 st(R)和 ts(R),并画出关系图 。解 t（ R） ={〈 a,b〉,〈 b,c〉,〈 a,c〉 }st(R)={〈 a,b〉,〈 b,c〉,〈 a,c〉,〈 b,a〉,〈 c,b〉,〈 c,a〉 }s(R)={〈 a,b〉,〈 b,c〉,〈 b,a〉,〈 c,b〉 }ts(R)={〈 a,b〉,〈 b,c〉,〈 b,a〉,〈 c,b〉,〈 a,c〉,〈 a,a〉,〈 b,b〉,〈 c,a〉,〈 c,c〉 }st(R)和 ts(R)的关系图分别如图 4.5.2(a),(b)所示。第 4章 二元关系和函数图 4.5.2ab c( b )ab c( a )第 4章 二元关系和函数4.6 等价关系和划分本节的目的就是要研究可用以对集合中元素进行分类的一种重要二元关系 --等价关系 。定义 4.6.1 设 R是非空集合 A上的二元关系,如果 R是自反的,对称的和传递的,则称 R 为 A 上的等价关系（ equivalent relation）。第 4章 二元关系和函数【 例 4.6.1】（ 1) 人类集合中的 &同龄 &,&同乡 &关系都是等价关系 。（ 2） 三角形集合的相似关系,全等关系都是等价关系 。（ 3） 住校学生的 &同寝室关系 &是等价关系 。（ 4） 命题公式间的逻辑等价关系是等价关系 。（ 5） 对任意集合 A,A上的恒等关系 IA和全域关系 A× A是等价关系。第 4章 二元关系和函数【 例 4.6.2】 设 A={1,2,3,4} 且 R={〈 1,1〉,〈 1,2〉,〈 2,1〉,〈 2,2〉,〈 3,4〉,〈 4,3〉,〈 3,3〉,〈 4,4〉 }。 我们易证 R是一个等价关系 。【 例 4.6.3】 整数集合 I中的二元关系R={〈 x,y〉 |m|(x-y),m∈ I+},其中 &|&表示整除关系,证明 R是等价关系 。第 4章 二元关系和函数证明（ 1） x∈ I,因为 x-x=0,所以 m|(x-x),因此 〈 x,x〉∈ R,R是自反的 。（ 2） x,y∈ I,设 〈 x,y〉 ∈ R,则 m|(x-y),即xy kImy x x y kImm故 〈 y,x〉 ∈ R,所以 R是对称的。第 4章 二元关系和函数（ 3） x,y,z∈ I,设 〈 x,y〉 ∈ R且 〈 y,z〉 ∈ R,则xy kIm yx lIm因而x z x y y z k l Imm故 〈 x,z〉 ∈ R,所以 R是传递的。因此,R是一个等价关系。第 4章 二元关系和函数定义 4.6.2 设 R为集合 A上的等价关系 。 对每一a∈ A,令 A中所有与 a 等价的元素构成的集合记为［ a］ R,即形式化为［ a］ R=｛ x|x∈ A∧ xRa｝称 ［ a］ R为 a的关于 R所生成的等价类 （ equivalentclass）,简称 a的等价类,简单地记为 ［ a］,a称为［ a］ R的代表元素 。第 4章 二元关系和函数【 例 4.6.4】 设 R是 X={0,1,2,3,4}上的二元等价关系,R={〈 x,y〉 |x,y(X且 (x-y)/2是整数 }。(1) 给出关系矩阵；(2) 画出关系图；(3) 求出等价类 。第 4章 二元关系和函数解 （ 1） R的关系矩阵为 1 0 1 0 10 1 0 1 01 0 1 0 10 1 0 1 01 0 1 0 1RM（ 2） R的关系图如图 4.6.1所示 。（ 3） ［ 0］ R=［ 2］ R=［ 4］ R={0,2,4}［ 1］ R=［ 3］ R={1,3}第 4章 二元关系和函数【 例 4.6.５ 若在例 4.6.2中取 m=4,即设 R为整数集上的 ≡4关系,它有四个不同的等价类；［ 0］ =｛ …,-12,-8,-4,0,4,8,12,…｝ =｛ x|4整除 x｝［ 1］ =｛ …,-11,-7,-3,1,5,9,13,…｝ =｛ x|4除 x余 1｝［ 2］ =｛ …,-10,-6,-2,2,6,10,14,…｝ =｛ x|4除 x余 2｝［ 3］ =｛ …,-9,-5,-1,3,7,11,15,…｝ =｛ x|4除 x余 3｝下面几个定理介绍等价类的性质 。第 4章 二元关系和函数定理 4.6.1 设 R是非空集合 A上的等价关系 。（ 1） 对任意的 a∈ A,［ a］ R≠Φ,且 ［ a］ R A,［ a］ R是 A的非空子集 。（ 2） ∪ {［ a］ |a∈ A}=A(∪ S表示集合 S中的元素做并运算所构成的集合 )。证明 （ 1） 对任意的 a∈ A,因为 R自反,aRa所以恒有 a∈ ［ a］ R。第 4章 二元关系和函数(2) 先证 ∪ {［ a］ |a∈ A} A。 任取 x,有x∈∪ {［ a］ |a∈ A} y(y∈ A∧ x∈ ［ y］ )x∈ A (因为 ［ y］ A)从而有 ∪ {［ a］ (a∈ A} A。再证 A ∪ {［ a］ |a∈ A}。 任取 x,有x∈ A x∈ ［ x］ ∧ x∈ Ax∈∪ {［ a］ (a∈ A}所以 A ∪ {［ a］ (a∈ A}成立 。因此 ∪ {［ a］ |a∈ A}=A。第 4章 二元关系和函数定理 4.6.2 设 R是集合 A上的等价关系,那么,对任意 a,b∈ A,有 aRb 当且仅当 ［ a］ R=［ b］ R证明 设 aRb。 为证 ［ a］ R ［ b］ R,又设x∈ ［ a］ R,那么 xRa。 又据 aRb及 R的传递性,有xRb,从而 x∈ ［ b］ R。 ［ a］ R∈ ［ b］ R得证 。同理可证 ［ b］ ［ a］ 。 于是 ［ b］ =［ a］ 得证 。反之,设 ［ a］ R=［ b］ R。 由于 a∈ ［ a］ R,故a∈ ［ b］ R,因而 aRb。第 4章 二元关系和函数定理 4.6.3 设 R是集合 A上的等价关系,那么,对任意 a,b∈ A,或者［ a］ R=［ b］ R或者［ a］ R∩［ b］ R=Φ。证明 设 ［ a］ R∩［ b］ R≠Φ,那么有x∈ ［ a］ R∩［ b］ R,从而有 xRa,xRb。 据 R的对称性又有 aRx,xRb。 再用 R的传递性,得 aRb。 由定理4.6.2 知 ［ a］ R=［ b］ R。第 4章 二元关系和函数由定理 4.6.2,定理 4.6.3知,对任何集合 A上的等价关系 R，有对任何 a,b∈ A，aRb［ a］ R=［ b］ R［ a］ R∩［ b］ R≠Φ关于等价类有下面十分显然的事实：（ 1） 对任何集合 A,IA有 ( A (个不同的等价类,每个等价类都是单元素集 。（ 2） 对任何集合 A,A(A只有一个等价类 为 A（ 即每个元素的等价类全为 A） 。（ 3） 同一等价类可以有不同的表示元素,或者说,不同的元素,可能有相同的等价类 。第 4章 二元关系和函数定义 4.6.3 当非空集合 A的子集族 π（ π P(A)） 满足下列条件时称为 A的一个划分 （ partitions）,（ 1） 对任意 B∈ π,B≠Φ。（ 2） 对任意 B∈ π,B A。（ 3） ∪ π＝ A。（ 4） 对任意 B,B′∈ π,B≠B′时,B∩B′=Φ。则称 π中元素为划分的划分块 。第 4章 二元关系和函数【 例 4.6.6】 设 A＝ {0,1,2,3,4 },则π1={{1,3},{0,2,4}}π2={{0,1,3},{2,4}}π3={{3},{0,l,2,4}}π4={{0,l,2,3,4}}均为 A的划分,且 π1中的元素恰是例 4.6.3的等价类 。第 4章 二元关系和函数定理 4.6.4 设 R为集合 A上的等价关系,那么 R对应的 A划分是 {［ x］ R|x(A}。该定理的证明留作练习 。定理 4.6.5 设 π是集合 A的一个划分,则如下定义的关系 R为 A上的等价关系：R=｛ 〈 x,y〉 | (B(B∈ π∧ x∈ B∧ y∈ B)｝称 R为 π对应的等价关系 。证明是极为容易的,请读者自己完成 。第 4章 二元关系和函数定理 4.6.6 设 π是集合 A的划分,R是 A上的等价关系,那么,对应 π的等价关系为 R,当且仅当 R对应的划分为 π。证明 A=Φ时,只有 Φ划分和等价关系 Φ,结论显然成立 。 下文设 A≠Φ。先证必要性 。 设对应 π的等价关系为 R,R对应的划分为 π′,欲证 π=π′。 为此对任一元素 a∈ A,设 B，B′分别是 π,π′中含 a的单元 。 那么,对 A中任一元素 b，有第 4章 二元关系和函数b∈ B aRb （ R是对应的等价关系 ）b∈ ［ a］ Rb∈ B′ （ π′是 R对应的划分 ）这就是说 B=B′。 由于 a是 A中任意元素,故可断定 π=π′。第 4章 二元关系和函数再证充分性 。 设 R对应的划分为 π,π对应的等价关系为 R′,欲证 R=R′。 为此考虑对 A中任意元素 a,b，有aRb b∈ ［ a］ RB(B∈ π∧ ［ a］ R=B∧ b∈ B)(π为 R对应的划分 )B(B∈ π∧ a∈ B∧ b∈ B)aR′b（ R′为 π对应的等价关系 ）故 R=R′。第 4章 二元关系和函数【 例 4.6.7】 设 A 是一个集合且 |A|=4,则 A 上共有多少种不同的等价关系？解 本题利用划分与等价关系的一一对应,用划分求等价关系,具体求解见表 4.6.1。第 4章 二元关系和函数表 1.6.1第 4章 二元关系和函数定义 4.6.4 设 R为集合 A上的等价关系,那么称 A的划分 {［ a］ R|a∈ A}为 A关于 R的商集（ quotient sets），记为 A/R。例 4.6.8 设关系 R是例 4.6.2中定义的,计算 A/R。解 从该例子中,我们有［ 1］ R={1,2}=［ 2］ R,同时 ［ 3］ R={3,4}=［ 4］ R。 所以 A/R={{1,2},{3,4}}。第 4章 二元关系和函数【 例 4.6.9】 在例 4.6.3中的等价关系中,取 m=2。求 A/R。解［ 0］ ={…,-6,-4,-2,0,2,4,6,8,…},即由偶整数组成,因为它们整除 2的余数是 0。［ 1］ ={…,-5,-3,-1,1,3,5,7,…},即由奇整数组成,因为它们整除 2的余数是 1。 因此 A/R是由偶整数集合和奇整数集合组成的集合 。第 4章 二元关系和函数由上两个例子我们有对有穷集合 A如何求 A/R的步骤：(1) 从集合 A中任意选一个元素 a,并计算 a所在的等价类 ［ a］ 。(2) 如果 ［ a］ ≠A,选另一个元素 b,b∈ A且 b［ a］,计算 ［ b］ 。(3) 如果 A不与上面计算的所有等价类的并相等,则在 A中选不在这些等价类中的元素 x且计算 ［ x］ 。(4) 重复 (3)直到集合 A与所有等价类的并相等,则结束 。第 4章 二元关系和函数定义 4.6.5 设 π1,π2为集合的两个划分 。 称 π1细分π2,如果 π1的每一划分块都包含于 π2的某个划分块 。π1细分 π2表示为 π1≤π2。 π1≤π2且 π1≠π2,则表示为 π1＜ π2,读作 π1真细分于 π2。第 4章 二元关系和函数【 例 4.6.10】 当 A=｛ a,b,c,d｝ 时,π1=｛｛ a,b｝,｛ c｝,｛ d｝｝ 细分 π2=｛｛ a,b,c｝,｛ d｝｝,π3=｛｛ a｝,｛ b｝,｛ c｝,｛ d｝｝ 细分所有划分 。 而所有划分均细分 π4=｛｛ a,b,c,d｝｝ 。 并且,π1真细分 π2,π3真细分 π1。第 4章 二元关系和函数定理 4.6.7 设 R1,R2为集合 A上的等价关系,π1,π2分别是 R1,R2所对应的划分,那么R1 R2 当且仅当 π1≤π2证明 当 A=Φ时命题显然真 。 以下设 A≠Φ。先证必要性。 设 R1 R2,B1为 π1中任一划分块，令 B1=［ a］ R1,a∈ A。 考虑［ a］ R2 =B2∈ π2。 对任一 b∈ B1,即 b∈ ［ a］ R1,有 bR1a,从而有 bR2a（因R1 R2）,故 b∈ ［ a］ R2 =B2。 这就是说 B1 B2,因而 π1≤π2。第 4章 二元关系和函数再证充分性。 设 π1≤π2,对任意 x,y,若 xR1y,那么有 π1中划分块 B1＝［ x］ R,使 x,y∈ B1。 由于 π1≤π2，故有 π2中划分块 B2,使 B1 B2,从而 x,y∈ B2,即 x，y属同一个 R2等价类,因此 xR2y。 至此我们证得 R1 R2。本定理表明,越 &小 &(含有较少序偶 )的等价关系对应越细的划分,反之亦然。 很明白,最小的等价关系是相等关系,它对应于最细的划分（每一划分块恰含一个元素）,最大的等价关系是全关系,它对应于最粗的划分（只有一个划分块）。第 4章 二元关系和函数4.7 序 关 系序关系是关系的一大类型,它们的共同点是都具有传递的,因此可根据这一特性比较集合中各元素的先后顺序 。 事物之间的次序常常是事物群体的重要特征,决定事物之间次序的还是事物间的关系 。 本节的目的则是要研究可用以对集合中元素进行排序的关系 --序关系 。 其中很重要的一类关系称作偏序关系 。 偏序的作用是用来排序 （ 称偏序是因为 A上的所有元素不一定都能按此关系排序,所以又称为半序,部分序 ） 。第 4章 二元关系和函数定义 4.7.1 设 R是非空集合 A上的二元关系,如果 R是自反,反对称,传递的,称 R为 A上的偏序关系（ partial ordered relations）,。 如果集合 A上有偏序关系 R,则称 A为偏序集 （ ordered sets）,用序偶 〈 A,R〉 表示之 。 若 〈 x,y〉 ∈,常记作 x y,读作 &x小于或等于 y&,说明 x在偏序上排在 y的前面或者相同 。 为简明起见,系,从而 〈 A,〉 表示一般的偏序集 。第 4章 二元关系和函数【 例 4.7.1】（ 1） 设 A是集合 S的子集为元素所构成的集合,包含关系 & &是 A 上的一个偏序关系,因此 〈 A,〉 是一个偏序集 。（ 2） 实数集 R上的 &≤&即小于等于关系为一偏序关系,〈 R,≤〉 表示偏序集 。 实数集 R上的 &≥&即大于关系也是偏序关系,〈 R,≥〉 也表示一个偏序集 。 7≥6，可以写作 7 6,理解为在大于等于偏序关系中,7排在 6的前面,或说 7比 6大 。第 4章 二元关系和函数定义 4.7.2 设 R为非空集合 A上的偏序关系,（ 1） x,y∈ A,若 x y或 y x,则称 x与 y可比 。（ 2） x,y∈ A,若 x y且 x≠y,则称 x y,读作 x小于 y。 这里所说的小于是指在偏序中 x排在 y的前边 。由上面的定义可知,A中任取两个元素 x和 y,可能有下述几种情况发生：x y（或 y x）,x=y,x与 y不是可比的。第 4章 二元关系和函数例如,实数集合上的小于等于关系是偏序关系且任意两个数均是可比的 。 而正整数上的整除关系也是偏序关系,但不是任意两个数都可比,如 2与 3不可比,因为 2不能整 除 3。我们可对偏序关系的关系图作简化 。 由于偏序关系自反,各结点处均有环,约定全部略去 。第 4章 二元关系和函数由于偏序关系反对称且传递,关系图中任何两个不同结点之间不可能有相互到达的边或通路,因此可约定边的向上方向为箭头方向,省略全部箭头 。 最后由于偏序关系具有传递性,我们还可将由传递关系可推定的边也省去 。 经过这种简化的具有偏序关系的关系图称为哈斯 （ Hasse） 图 。 哈斯图既表示一个偏序关系,又表示一个偏序集 。第 4章 二元关系和函数【 例 4.7.2】 表示集合 {a,b}的幂集 P(｛ a,b｝ )上的子集包含关系的关系图,可如图 4.7.1作简化 。为了说明哈斯图的画法,首先定义“覆盖”的性质。定义 4.7.3 设偏序集 〈 A,,如果 x,y∈ A,x y,x≠y,且不存在元素 z∈ A,使得 x z 且 z y,则称 y覆盖 x。 A上的覆盖关系 cov A定义为cov A={〈 x,y〉 |x∈ A∧ y∈ A∧ y盖住 x}第 4章 二元关系和函数图 4.7.1{ a }{ b }{ a,b }{ a } { b }{ a,b }( a ) ( b )第 4章 二元关系和函数【 例 4.7.3】 设 A是正整数 m=12的因子的集合,并设为整除的关系,求 cov A。解cov A={〈 1,2〉,〈 1,3〉,〈 2,4〉,〈 2,6〉,〈 3,6〉,〈 4,12〉,〈 6,12〉 }第 4章 二元关系和函数【 例 4.7.4】 例 4.7.2中,cov P({a,b})={ 〈 (,{a}〉,〈 (,{b}〉,〈 {a},{a,b}〉,〈 {b},{a,b}〉 }。定的偏序集 〈 A,〉,它的覆盖关系是唯一的,所以可用覆盖的性质画出偏序集合图,又称为哈斯图,其作图法为：(1) 以 &ο &表示元素 ;(2) 若 x y,则 y画在 x的上层 ;(3) 若 y覆盖 x,则连线 ;(4) 不可比的元素,可画在同一层 。第 4章 二元关系和函数【 例 4.7.5】 画出下面几个偏序集的哈斯图：（ 1） 〈 S8,|〉,其中 S8表示 8的所有因子作元素构成的集合 。（ 2） 〈 ｛ 2,3,6,12,24,36｝,|〉,其中 &|&是集合上的数之间的整除关系 。（ 3） 〈 S 30,|〉,其中 S 30 表示 30 的所有因子作元素构成的集合。第 4章 二元关系和函数解 先分别求出其覆盖 。（ 1） S8={1,2,4,8}cov{S8}={〈 1,2〉,〈 2,4〉,〈 4,8〉 }（ 2） cov{2,3,6,12,24,36}= {〈 2,6〉,〈 3,6〉,〈 6,12〉,〈 12,24〉,〈 12,36〉 }第 4章 二元关系和函数（ 3） S 30 ={1,2,3,5,6,10,15,30}cov S 30 ={〈 1,2〉,〈 1,3〉,〈 1,5〉 〈 2,6〉,〈 2,10〉 〈 3,6〉,〈 3,15〉,〈 5,10〉,〈 5,15〉,〈 6,30〉,〈 10,30〉,〈 15,30〉 }画出其哈斯图,如图 4.7.2所示,（ a）,（ b）,（ c） 分别表示上述各偏序集 。第 4章 二元关系和函数（ 3） S 30 ={1,2,3,5,6,10,15,30}cov S 30 ={〈 1,2〉,〈 1,3〉,〈 1,5〉 〈 2,6〉,〈 2,10〉 〈 3,6〉,〈 3,15〉,〈 5,10〉,〈 5,15〉,〈 6,30〉,〈 10,30〉,〈 15,30〉 }画出其哈斯图,如图 4.7.2所示,（ a）,（ b）、（ c）分别表示上述各偏序集。第 4章 二元关系和函数图 4.7.2842124 361262 330103126515( a ) ( b ) ( c )第 4章 二元关系和函数【 例 4.7.6】 由图 4.7.3所示的哈斯图,写出对应的偏序关系,关系矩阵 。解 A={a,b,c,d,e}={〈 a,a〉,〈 b,b〉,〈 c,c〉,〈 d,d〉,〈 e,e〉,〈 c,a〉,〈 c,b〉,〈 d,e〉,〈 d,a〉,〈 d,b〉 }第 4章 二元关系和函数图 4.7.3a bc ed第 4章 二元关系和函数关系矩阵1 0 0 0 00 1 0 0 01 1 1 0 01 1 1 1 00 0 0 0 1M偏序集中链和反链的概念是十分重要的。第 4章 二元关系和函数定义 4.7.4 设偏序集 〈 A,〉,B A。(1) 如果对任意的 x,y∈ B,x和 y 都是可比的,则称 B为 A上的链 （ chain）,B中元素个数称为链的长度 。(2) 如果对任意的 x,y∈ B,x和 y 都不是可比的,则称 B 为 A上的反链 （ antichain）,B中元素个数称为反链的长度 。我们约定,若 A的子集只有单个元素,则这个子集既是链又是反链。第 4章 二元关系和函数【 例 4.7.7】 图 4.7.4中的哈斯图表示一偏序集,举例说明链及反链 。长度为 5的链有 {a,c,e,h,m },{a,b,e,i,n}等 。长度为 4的链有 {b,d,g,m},{c,e,h,k},{c,d,f,j}等 。长度为 3的链有 {b,e,i},{f,d,c},{n,i,e}等 。长度为 2的链有 {d,f},{m,h}等 。长度为 1的链有 {m},{n}等 。长度为 4的反链只有 {b,c,d,e}和 {n,m,k,i}。长度为 3的反链有 {j,k,i},{f,g,e},{d,h,i}等 。长度为 2的反链有 {d,e},{b,c},{g,h},{f,e}等 。长度为 1的反链有 {a},{e}等 。第 4章 二元关系和函数图 4.7.4cabdfjgk m nh ie第 4章 二元关系和函数定义 4.7.5 设偏序集 〈 A,〉,如果 A是一个链,A上的全序关系,或称线序关系 。并称 〈 A,〉 为全序集 (totally ordered)。 全序集〈 A,〉 意味着对任意 x,y∈ A,或者有 x y或者有 y x成立 。例如,实数集合上的小于等于关系是偏序关系且任意两个数均是可比的,所以也是全序关系 。 利用偏序关系可对有序集合中元素进行比较或排序 。 在哈斯图中,各元素都处在不同的层次上,有的元素的位置特殊,它们是偏序集合中的特殊元素,了解这些元素有助于我们对偏序集合进行深入分析 。第 4章 二元关系和函数定义 4.7.6 设 〈 A,〉 为偏序集,B A。（ 1） 如果 b∈ B且对每一 x∈ B,b x,称 b为 B的最小元 （ least element） 。 即 b为 B的最小元b∈ B∧ x(x∈ B→b x)第 4章 二元关系和函数（ 2）如果 b∈ B，并且对每一 x∈ B,x b，称 b为 Bgreatest element ）。即 b为 B的最大元b∈ B∧ x( x∈ B→x b)（ 3）如果 b∈ B，并且没有 x∈ B,x≠b，使得 x b，称 b为 B minimal element ）。即b为 B b∈ B∧ x(x∈ B∧ x≠b∧ x b)第 4章 二元关系和函数（ 4）如果 b∈ B，并且没有 x∈ B,x≠b，使得 b x，称 b为 B maximalelement ）。即b为 B b∈ B∧
x(x∈ B∧ x≠b∧ b x)?第 4章 二元关系和函数从以上定义可以看出，最小元与极小元是不一样的。最小元是 B中最小的元素，它与 B中其它元素都可比；而极小元不一定与 B中元素都可比，只要没有比它更小的元素，它就是极小元，同理最大元是 B中最大的元素，它与 B中其它元素都可比；而极大元不一定与 B中元素都可比，只要没有比它更大的元素，它就是极大元。第 4章 二元关系和函数【 例 4.7.8】 偏序集 〈 {1,2,3,4,5,6,7,8},，由图4.7.5所示哈斯图给出。（ 1） B={1,2,3,5}B的最大元为 5。B的极大元为 5。B的最小元为 1。B的极小元也为 1。第 4章 二元关系和函数图 4.7.587531246第 4章 二元关系和函数（ 2） B={2,3,4,5,6,7}B无最大元和最小元。B的极大元是 6,7，极小元是 2,3。（ 3） B={4,5,8}B的最大元是 8，无最小元。B的极大元为 8，极小元为 4,5。（ 4） B={4,5}B无最大元，也无最小元。B的极大元是 4,5，极小元也是 4,5。第 4章 二元关系和函数从例 4.7.8中可知，最大元、最小元未必存在，若存在则必唯一。极大元、极小元虽存在，但却不唯一，它们之间不可比，并处在子集哈斯图的同一层次上，极大元在最高层，极小元在最低层。关于这些，有下面的定理。第 4章 二元关系和函数定理 4.7.1 设 〈 A,为偏序集,B A。（ 1）若 b为 B的最大（最小）元，则 b为 B的极大（极小）元。（ 2）若 B有最大（最小）元，则 B的最大（最小）元唯一。（ 3）若 B为有限集，则 B的极大元、极小元恒存在。第 4章 二元关系和函数当 n=1时,B中仅有一个元素，它既是极大元，也是极小元。当 n=2时，设 B={b1,b2}。那么,b1 b2时 b1为极小元,b2为极大元； b2 b1时 b2为极小元,b1为极大元；
b2 b1时,b1,b2同为极大元，也同为极小元。第 4章 二元关系和函数设 n=k时命题为真。若 n=k+1,B={b1,b2,…,bk,bk+1}。据归纳假设,{b1,b2,…,bk}有极大元 bi，极小元 bj。考虑{bi,bk+1}，若 bi bk+1,bk+1 显然是 B的极大元；若bk+1 bi，或两者不可比较，则 bi是 B的极大元。同理可证,bj或 bk+1 是 B的极小元。归纳完成，（ 3）得证。第 4章 二元关系和函数【 例 4.7.9】 在例 4.7.5中的（ 3）题中设子集B={15,5,6}，则子集 B的极大元,15,6；极小元,5,6；最大元：无；最小元：无。在例 4.7.6中,A的极大元是 a,b； A的极小元是d,e;A无最大元；也无最小元。定理 4.7.2(偏序集的分解定理 ) 设 〈 A,为一有限的偏序集，且 A中最长链的长度为 n，则将 A中元素分成不相交的反链，反链个数至少是 n。即 A有一划分，使划分有 n个划分块，且每个划分块为一反链。第 4章 二元关系和函数证明 对 n进行归纳。当 n=1时,A因此 A本身既为一链，又为一反链，因此划分 {A}即满足要求。设 n=k时命题成立。现令 n=k+1。第 4章 二元关系和函数设 M为 A中所有极大元素的集合。由于 A为有限集，因此 M必为一非空的反链（极大元之间是不可比较的）。考虑有序集 〈 A-M 〉,它不可能有长度为 n的链（否则 A中链的长度将超过 n，关于这一点请读者思考），因而 〈 A-M 〉 中最长链的长度应当为 n-1=k。据归纳假设,A-M有 k个划分块的划分，且每个划分块为一反链。这 k个反链连同反链 M，恰构成 A的 k+1个划分块组成的划分。所以归纳完成。第 4章 二元关系和函数定理 4.7.3 设 〈 A,为一偏序集,|A|=mn+1，那么,A中或者存在一条长度为 m+1的反链，或者存在一条长度为 n+1的链。证明 若 A中链的长度不超过 n，那么据定理 4.7.2,A中必有长度为 m+1个划分块的反链，否则 |A|≤mn。第 4章 二元关系和函数定义 4.7.7 设 〈 A,为偏序集,B A。（ 1）如果 a∈ A，且对每一 x∈ B,x a，称 a为 B的upperbound ）。即a为 B a∈ A∧ x(x∈ B→x a)（ 2）如果 a∈ A，且对每一 x∈ B,a x,a称为 B的lowerbound ），即a为 B a∈ A∧ x(x∈ B→a x)（ 3）如果 C是 B的所有上界的集合，即 C={y|y是 B的上界 }，则 C的最小元 a称为 B的最小上界或上确界leastupperbound ）。第 4章 二元关系和函数（ 4）如果 a是 B的所有下界的集合，即 C={y|y是 B的上界 }，则 C的最大元 a称为 Bgreatestlowerbound ）。从以上定义可知,B的最小元一定是 B的下界，同时也是 B的最大下界。同样地,B的最大元一定是 B的上界，同时也是 B的最小上界。但反过来不一定正确，B的下界不一定是 B的最小元，因为它可能不是 B中的元素。同样地,B的上界也不一定是 B第 4章 二元关系和函数【 例 4.7.10】 设偏序集 〈 A,如图 4.7.4所示，考虑集合 B={h,i}，它有上界 j,k，但无最小上界；它有下界 f,g等，但没有最大下界。当 B={b,c,d,e}时，它有上界 h,i等，无最小上界；它没有下界和最大下界。再设偏序集 〈 A,如图 4.7.5所示。（ 1）当 B={2,3,4,5,7}时,B有上界 7,8,下界 1；最小上界 7，最大下界 1。第 4章 二元关系和函数（ 2）当 B={2,5,4,6}时,B有上界 8，下界 2,1；最小上界 8，最大下界 2。第 4章 二元关系和函数定理 4.7.4 设 〈 A,为偏序集,B A。（ 1）若 b为 B之最大元（最小元），则 b必为 B最小上界（最大下界）。（ 2）若 b为 B之上（下）界，且 b∈ B，则 b必为 B的最大（最小）元。（ 3）如果 B有最大下界（最小上界），则最大下界（最小上界）唯一。证明略。第 4章 二元关系和函数定义 4.7.8 设 〈 A,为偏序集，如果 A的任何非空子集都有最小元,well foundedrelation ）,称 〈 A,为良序集 ( well ordered set )。第 4章 二元关系和函数【 例 4.7.11】 设 I n={1,2,…}及 N={1,2,3,…},对于小于等于关系来说是良序集合，即 〈 I n,是良序集合。定理 4.7.5 一个良序集一定是全序集。证明 设 〈 A,为良序集合，则对任意两个元素x,y∈ A可构成子集 {x,y},必存在最小元素，这个最小元素不是 x就是 y,因此一定有 x y或 y x。所以 〈 A,为全序集合。第 4章 二元关系和函数定理 4.7.6 一个有限的全序集一定是良序集。证明 设 A={a1,a2,…,an},令 〈 A,是全序集合。用反证法，假定 〈 A,不是良序集合，则必存在一个非空子集 B A,在 B中不存在最小元素，由于 B是一个有限集合，故一定可以找出两个元素 x与 y是无关〈 A,是全序集,x,y∈ A,所以 x,y必有关系，得出矛盾，故 〈 A,必是良序集合。第 4章 二元关系和函数上述结论对于无限的全序集合不一定成立。例如，大于 0小于 1的全部实数，按大小次序关系是一个全序集合，但不是良序集合，因为集合本身就不存在最小元素。定理 4.7.8（良序定理） 任意的集合都是可以良序化的。第 4章 二元关系和函数4.8 函数的定义和性质函数概念是最基本的数学概念之一，也是最重要的数学工具。初中数学中函数定义为 &对自变量每一确定值都有一确定的值与之对应 &的因变量；高中数学中函数又被定义为两集合元素之间的映射。第 4章 二元关系和函数现在，我们要把后一个定义作进一步的深化，用一个特殊关系来具体规定这一映射，称这个特殊关系为函数，因为关系是一个集合，从而又将函数作为集合来研究。离散结构之间的函数关系在计算机科学研究中也已显示出极其重要的意义。我们在讨论函数的一般特征时，总把注意力集中在离散结构之间的函数关系上，但这并不意味着这些讨论不适用于其它函数关系。第 4章 二元关系和函数定义 4.8.1 设 X,Y为集合，如果 f为 X到 Y的关系（ f X× Y），且对每一 x∈ X，都有唯一的 y∈ Y，使〈 x,y〉 ∈ f，称 f为 X到 Y functions ），记为 f,X→Y X=X1× X2× …× Xn 时，称 f为 n元函mapping ）。第 4章 二元关系和函数换言之，函数是特殊的关系，它满足（ 1）函数的定义域是 X，而不能是 X的某个真子集。（ 2）若 〈 x,y〉 ∈ f,〈 x,y′〉 ∈ f，则 y＝ y′（单值性）。由于函数的第二个特性，人们常把 〈 x,y〉 (f或 xfy这两种关系表示形式，在 f为函数时改为 y=f(x)。这时称x为自变元,y为函数在 x处的值；也称 y为 x的像点,x为y的源点。一个源点只能有唯一的像点，但不同的源点允许有共同的像点。注意，函数的上述表示形式不适用于一般关系。（因为一般关系不具有单值性。）第 4章 二元关系和函数【 例 4.8.1】 设 A={a,b},B={1,2,3}，判断下列集合是否是 A到 B的函数。F1={〈 a,1〉,〈 b,2〉 },F2={〈 a,1〉,〈 b,1〉 }，F3={〈 a,1〉,〈 a,2〉 },F4={〈 a,3〉 }解F1,F2是函数,F3,F4不是函数，但若不强调是 A到 B的函数，则 F4是函数，其定义域为 {a}。第 4章 二元关系和函数【 例 4.8.2】 下列关系中哪些能构成函数？（ 1） {〈 x,y〉 |x,y∈ N,x+y〈 10}（ 2） {〈 x,y〉 |x,y∈ N,x+y=10}（ 3） {〈 x,y〉 |x,y∈ R,|x|=y}（ 4） {〈 x,y〉 |x,y∈ R,x=|y|}（ 5） {〈 x,y〉 |x,y∈ N,|x|=|y|}第 4章 二元关系和函数解 只有（ 3）能构成函数。由于函数归结为关系，因而函数的表示及运算可归结为集合的表示及运算，函数的相等的概念、包含概念，也便归结为关系相等的概念及包含概念。第 4章 二元关系和函数定义 4.8.2 设 f:A→B,g:C→D，如果 A=C,B＝ D，且对每一 x∈ A，有 f(x) g(x) f等于 g,记为f=g。如果 A C,B＝ D，且对每一 x∈ A，有 f(x) g(x) f包含于 g，记为 f g。事实上，当不强调函数是定义在哪个集合上的时候，由于函数是序偶的集合（特殊的关系），所以 f=g的充分必要条件是 f g且 g f。第 4章 二元关系和函数【 例 4.8.3】 设 A={a,b},B={1,2,3}。由 A→B能生成多少个不同的函数？由 B→A能生成多少个不同的函数？解 设 fi:A→B(i=1,2,…,9),gi:B→A(i=1,2,…,8)第 4章 二元关系和函数f1={〈 a,1〉,〈 b,1〉 } g1={〈 1,a〉,〈 2,a〉,〈 3,a〉 }f2={〈 a,1〉,〈 b,2〉 } g2={〈 1,a〉,〈 2,a〉,〈 3,b〉 }f3={〈 a,1〉,〈 b,3〉 } g3={〈 1,a〉,〈 2,b〉,〈 3,a〉 }f4={〈 a,2〉,〈 b,1〉 } g4={〈 1,a〉,〈 2,b〉,〈 3,b〉 }f5={〈 a,2〉,〈 b,2〉 } g5={〈 1,b〉,〈 2,a〉,〈 3,a〉 }f6={〈 a,2〉,〈 b,3〉 } g6={〈 1,a〉,〈 2,a〉,〈 3,b〉 }f7={〈 a,3〉,〈 b,1〉 } g7={〈 1,b〉,〈 2,a〉,〈 3,b〉 }f8={〈 a,3〉,〈 b,2〉 } g8={〈 1,b〉,〈 2,b〉,〈 3,b〉 }f9={〈 a,3〉,〈 b,3〉 }第 4章 二元关系和函数定理 4.8.1 设 |A|=m,|B|=n，那么 {f|f:A→B}的基数为 nm，即共有 nm个 A到 B的函数。证明 设 A={a1,a2,…,am},B={b1,b2,…,bn}，那么每一个f:A→B由一张如下的表来规定,a a1 a2 … amf(a) bi1 bi2 … bin第 4章 二元关系和函数其中 b i1,b i2,…,b im 为取自 b1,b2,…,bn的允许元素重复的排列，这种排列总数为 n m个。因此，上述形式的表恰有 n m张，恰对应全部 n m个 A到 B的函数。由于上述缘故，当 A,B是有穷集合时，我们以 B A记所有 A到 B的全体函数的集合：B A={f|f:A→B}则 |B A|=|B| |A| 。特别地 A A表示 A上函数的全体。目前在计算机科学中，也用 A→B替代 B A。第 4章 二元关系和函数例 4.8.2中,B A={f1,f2,…,f9},|B A|=9，A B={g1,g2,…,g8},|A B|=8。该定理当 X或 Y中至少有一个集合是空集时，可分成下面两种情况：(1)当 X X到 Y的空关系为一函数，称为空函数，即 Y X= ={ }。(2)当 X≠ 且 Y= 时,X到 Y的空关系不是一个函数，即 Y X= X= 。关于函数有下列术语和记号。X第 4章 二元关系和函数定义 4.8.3 设 f:X→Y,A X，称 f(A)为 Aimage ），定义为f(A)={y| x(x∈ A∧ y=f(x))}显然，此时 f为 P(X)到 P(Y)的函数，且f( )=,f(X)= Ran (f)，此时 f(X)称为函数的像,f({x})={f(x)}(x∈ A)。在这里请注意区别函数值和像两个不同的概念。函数值 f(x)∈ Y,而像 f(A) Y。关于像有下列性质。第 4章 二元关系和函数定理 4.8.2 设 f:X→Y，对任意 A X,B X，有（ 1） f(A∪ B)=f(A)∪ f(B)（ 2） f(A∩B) f(A)∩f(B)（ 3） f(A)-f(B) f(A-B)第 4章 二元关系和函数证明 （ 1）对任一 y∈ Yy∈ f(A∪ B) x(x∈ A∪ B∧ y=f(x))x((x∈ A∧ y=f(x))∨ (x∈ B∧ y=f(x)))x(x∈ A∧ y=f(x))∨ x(x∈ B∧ y=f(x))y∈ f(A)∨ y∈ f(B)y∈ f(A)∪ f(B)因此 f(A∪ B)=f(A)∪ f(B)。（ 2）、（ 3）的证明请读者完成。注意，（ 2）、（ 3）中的包含符号不能用等号代替。我们举例说明。第 4章 二元关系和函数【 例 4.8.4】 设 X={a,b,c,d},Y={1,2,3,4,5},f:X→Y,如图 4.8.1所示。那么，f ({a})={2},f ({b})={2},f ({a})∩f({b})={2}f ({a})
