二元关系和函数

1二元关系1集合的笛卡儿积2二元关系3关系的性质4等价关系和等价划分5相容关系与最大相容6偏序关系7格与概念格21集合的笛卡儿积和二元关系有序对笛卡儿积二元关系二元关系的表示3有序对定义由两个客体x和y，按照一定的顺序组成的二元组称为有序对，记作x,y实例：点的直角坐标(3,4)有序对性质有序性x,yy,x（当xy时）x,y与u,v相等的充分必要条件是x,y=u,vx=uy=v例12,x+5=3y4,y，求x,y.解3y4=2,x+5=yy=2,x=34有序n元组定义一个有序n(n3)元组x1,x2,…,xn是一个有序对，其中第一个元素是一个有序n-1元组，即x1,x2,…,xn=x1,x2,…,xn-1,xn当n=1时,x形式上可以看成有序1元组.实例n维向量是有序n元组.5笛卡儿积定义设A,B为集合，A与B的笛卡儿积记作AB，即AB={x,y|xAyB}例2A={1,2,3},B={a,b,c}AB={1,a,1,b,1,c,2,a,2,b,2,c,3,a,3,b,3,c}BA={a,1,b,1,c,1,a,2,b,2,c,2,a,3,b,3,c,3}A={},P(A)A={,,{},}6二元关系的定义定义如果一个集合满足以下条件之一：（1）集合非空,且它的元素都是有序对（2）集合是空集则称该集合为一个二元关系,简称为关系，记作R.如x,y∈R,可记作xRy；如果x,yR,则记作xy实例：R={1,2,a,b},S={1,2,a,b}.R是二元关系,当a,b不是有序对时，S不是二元关系根据上面的记法，可以写1R2,aRb,ac等.7在日常生活和实际工作中，“关系”这个词的含义如：父子关系，夫妻关系，同学关系，师生关系等。下面采用集合论的观点来描述这类关系。如集合A={a,b,c,d,e},其中a,b,c,d,e是五个人，a是b的父亲，c是d的父亲，c又是e的父亲。现将这5个人中所有符合父子关系的两个人，用有序对：(a,b),(c,d),(c,e)来表示，如果以这些有序对作为元素构成集合，即R={(a,b),(c,d),(c,e)}那么R就完整地描述了a,b,c,d,e中的父子关系。称R为集合A上的一个关系(父子关系)。这种有序对仅由两个元素组成的关系称为二元关系。8关系的表示表示方式：关系的集合表达式、关系矩阵、关系图关系矩阵：若A={a1,a2,…,am}，B={b1,b2,…,bn}，R是从A到B的关系，R的关系矩阵是布尔矩阵MR=[rij]mn,其中rij=1ai,bjR.关系图：若A={x1,x2,…,xm}，R是从A上的关系，R的关系图是GR=A,R,其中A为结点集，R为边集.如果xi,xj属于关系R，在图中就有一条从xi到xj的有向边.注意：A,B为有穷集，关系矩阵适于表示从A到B的关系或者A上的关系，关系图适于表示A上的关系9从A到B的关系与A上的关系定义设A,B为集合,A×B的任何子集所定义的二元关系叫做从A到B的二元关系,当A=B时则叫做A上的二元关系.例4A={0,1},B={1,2,3},R1={0,2},R2=A×B,R3=,R4={0,1}.那么R1,R2,R3,R4是从A到B的二元关系,R3和R4同时也是A上的二元关系.计数|A|=n,|A×A|=n2,A×A的子集有个.所以A上有个不同的二元关系.例如|A|=3,则A上有=512个不同的二元关系.22n22n10实例例如A={1,2,3},B={a,b},则LA={1,1,1,2,1,3,2,2,2,3,3,3}DA={1,1,1,2,1,3,2,2,3,3}A=P(B)={,{a},{b},{a,b}},则A上的包含关系是R={,,,{a},,{b},,{a,b},{a},{a},{a},{a,b},{b},{b},{b},{a,b},{a,b},{a,b}}11A上关系的性质1自反性2反自反性3对称性4反对称性5传递性122等价关系与偏序关系等价关系的定义等价类及其性质商集与集合的划分等价关系与划分的一一对应相容关系偏序关系偏序集与哈斯图偏序集中的特定元素13等价关系和划分定义设R是A上的二元关系，如果（1）R是自反的；（2）R是对称的；（3）R是可传递的。则称R是A上的等价关系。若x,y∈R,称x等价于y,记做x～y.等价关系是经常使用的重要的二元关系。1、等价关系的定义一、等价关系14例如，我们用a,b,c,d,e,f分别表示6位大学生，其中a,b,c都姓张，d,e,f都姓李。若令集合A={a,b,c,d,e,f}张李R是A上的同姓氏关系（同姓的大学生认为是相关的）容易验证同姓氏关系R是A上的等价关系。（1）因为每一个大学生都和自已是同姓的，所以满足自反性；（2）当(a,b)∈R时有(b,a)∈R，所以满足对称性；（3）当(a,b)∈R和(b,c)∈R时有(a,c)∈R，所以R是可传递的。由此可得同姓氏关系R是等价关系。15又如设集合A的情况同上所述若令集合A={a,b,c,d,e,f}2022其中a,b,c,d都是20岁，e,f都是22岁。如果年龄相同的大学生认为是相关的，那么“同年龄”关系R是等价关系。（1）因为每一个大学生都和自已是同年龄的，所以满足自反性；（2）当(a,b)∈R时有(b,a)∈R，所以满足对称性；（3）当(a,b)∈R和(b,c)∈R时有(a,c)∈R，所以R是可传递的。由此可得同年龄关系R是等价关系。16再如设集合A的情况同上所述若令集合A={a,b,d,c,e,f}同房间同房间其中a,b,d同住一个房间，c,e,f同住另一个房间。如果同住一个房间的大学生认为是相关的，那么“同房间”关系R也是等价关系。（1）因为每一个大学生都和自已是同房间的，所以满足自反性；（2）当(a,b)∈R时有(b,a)∈R，所以满足对称性；（3）当(a,b)∈R和(b,c)∈R时有(a,c)∈R，所以R是可传递的。由此可得同房间关系R是等价关系。17由上述3个例子可知那种同姓氏、同房间、同年龄的关系都是等价关系。如果抽象地讨论，对集合A中的元素按照某种特性分成几个组，每个元素只属于一个组（如按年龄分组，即同年龄人在同一组内；或按姓氏分组，即同姓人在同一组内），并且定义在同一组内的元素是相关的，而不在同一组内的元素是不相关的，那么由此产生的二元关系必然是等价关系。由此可知等价关系所具有的重要特性。由此可见：等价关系实际上是同组关系。18下面将利用表格和关系矩阵来进一步了解等价关系的特征。2、等价关系的表格表示和关系矩阵为了方便将上述3个例子综合如下：（1）a,b,c都姓“张”，d,e,f都姓“李”；（2）a,b,c,d都是20岁，e,f都是22岁；（3）a,b,d同住一个房间，c,e,f同住另一个房间。下面分别画出（1）、（2）、（3）所表示的等价关系的表格和关系矩阵：19abcdefecbafd√√√√√√√√√√√√√√√√√√111000111000111000000111000111000111（1）a,b,c都姓“张”，d,e,f都姓“李”abcdefecbafd易见在描述等价关系的表格中，带有“√”的格子将形成若干个正方形；而在关系矩阵中则有一些小方阵，其元素都是1，而其它元素都是0。20对于（2）所示的等价关系的表格表示和关系矩阵也有上述特征：abcdefecbafd√√√√110000110000001111001111001111001111abcdefecbafd（2）a,b,c,d都是20岁，e,f都是22岁；√√√√√√√√√√√√√√√√21对于（3）所示的等价关系，如果将集合A={a,b,c,d,e,f}中的顺序改为A={a,b,d,c,e,f}也就是把相关的元素排在一起那么所画出的表格也显示上述特征：（3）a,b,d同住一个房间，c,e,f同住另一个房间。abdcefedbafc√√√√√√√√√√√√√√√√√√111000111000111000000111000111000111abdcefedbafc22例1设集合A={1，2，3，4，5，6，7}，R是A上的模3同余关系，试说明此关系是等价关系，并画出表格和关系矩阵。解（1）相同数被3除后余数一定相同，所以R上自反的；显然R也是对称的；又由于A中任意元素a，可写为a=3k+r所以当(a,b)∈R时，有a-b=3k.因此当(a,b)∈R和(b,c)∈R时，即有a-b=3k1，b-c=3k2.于是a-c=a-b+b-c=3(k1-k2)=3k由此可得(a,c)∈R，所以R是可传递的，说明此关系是等价关系。23在集合A中，以相关元素顺序排列，即：A={1,4,7,2,5,3,6}也就是把相关的元素排在一起那么所画出的表格表示和关系矩阵如下：由此可见模3同余关系也是一种分组关系，它是把A中的元素被3除后，余数为1的分为一组（1,4,7），余数为2的分为一组（2,5），余数为3的分为一组（3,6）。11000001100000001100000110000000111000011100001111472536374165214725363741652√√√√√√√√√√√√√√√√√24以上的例子不仅说明集合A上的等价关系实际上是一种“同组”关系。即当集合A确定一种“分组”形式后，也就确定了A上的一种等价关系（只要将同一组的元素认作是相关的）；反之当确定一个A上的等价关系后，也就确定了A上的一种“分组”形式（只要将相关元素合成一组）。为了详细地讨论这一问题，下面介绍等价类和划分这两个概念：25二、等价类定义：设R是A上的等价关系，a∈A，由A中所有与a相关的元素组成的集合称为a关于R的等价类，记作[a]R.例如集合A={1，2，3，4，5，6，7}，R是A上的模3同余关系，显然R是A上等价关系，A中各元素关于R的等价类分别是：[6]R={3，6}[3]R={3，6}[2]R={2，5}[5]R={2，5}[1]R={1，4，7}[7]R={1，4，7}[4]R={1，4，7}显然相关元素的等价类是相同的，所以不同的等价类仅有3个，它们是[1]R，[2]R，[3]R。26又如设集合A={a,b,c,d,e,f,g}其中a,b,c,d,e,f,g分别表示7位大学生，且a,b都是20岁，c,d都是22岁，e,f都是24岁，g是25岁。R是A的同年龄关系，写出A中各元素关于R的等价类。显然[a]R={a,b}[b]R={a,b}[c]R={c,d}[d]R={c,d}[e]R={e,f}[f]R={e,f}[g]R={g}定义：R是A上的等价关系，由R的所有不同的等价类作为元素构成的集合，称为A关于R的商集，记作A/R。27“商”和除法有关，比如把一块蛋糕平均分成四份，从两种不同的角度看这件事：从算术角度看：1用4除,每份1/4,这就是“商”,于是:1=1/4+1/4+1/4+1/4从集合角度看：集合A用模3同余关系R划分，得到三个等价类，所以A{{1,4,7},{2,5,８},{3,6}}={[1]R,[2]R,[3]R}----商集用刀分}{用R分生日日快快乐乐生28思考：1.集合A={1，3，5，7，9}，R是A上的模4同余关系，求R的商集A/R。[3]R=[7]R={3,7}[1]R=[5]R=[9]R={1，5，9}所以A关于R的商集A/R={{1，5，9}，{3，7}}。答案：29答案：有4个是不相同的等价类，