二元关系和函数

二元关系1集合的笛卡儿积2二元关系3关系的性质4等价关系和等价划分5相容关系与最大相容6偏序关系7格与概念格11集合的笛卡儿积和二元关系

有序对笛卡儿积二元关系二元关系的表示2有序对定义由两个客体x和y，按照一定的顺序组成的二元组称为有序对，记作<x,y>实例：点的直角坐标(3,4)有序对性质有序性<x,y><y,x>〔当xy时〕<x,y>与<u,v>相等的充分必要条件是<x,y>=<u,v>x=uy=v例1<2,x+5>=<3y

4,y>，求x,y.解3y

4=2,x+5=y

y=2,x=3

3有序n元组定义一个有序n(n3)元组<x1,x2,…,xn>是一个有序对，其中第一个元素是一个有序n-1元组，即<x1,x2,…,xn>=<<x1,x2,…,xn-1>,xn>当n=1时,<x>形式上可以看成有序1元组.实例n维向量是有序n元组.4笛卡儿积定义设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={<

,

>,<{

},

>}5二元关系的定义定义如果一个集合满足以下条件之一：（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等.6

在日常生活和实际工作中，“关系”这个词的含义如：父子关系，夫妻关系，同学关系，师生关系等。下面采用集合论的观点来描述这类关系。如集合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上的一个关系(父子关系)。这种有序对仅由两个元素组成的关系称为二元关系。7关系的表示表示方式：关系的集合表达式、关系矩阵、关系图关系矩阵：假设A={a1,a2,…,am}，B={b1,b2,…,bn}，R是从A到B的关系，R的关系矩阵是布尔矩阵MR=[rij]mn,其中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上的关系8从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个不同的二元关系.9实例例如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}>}

10A上关系的性质1自反性2反自反性3对称性4反对称性5传递性112等价关系与偏序关系等价关系的定义等价类及其性质商集与集合的划分等价关系与划分的一一对应相容关系偏序关系偏序集与哈斯图偏序集中的特定元素12等价关系和划分定义设R是A上的二元关系，如果〔1〕R是自反的；〔2〕R是对称的；〔3〕R是可传递的。那么称R是A上的等价关系。假设<x,y>∈R,称x等价于y,记做x～y.

等价关系是经常使用的重要的二元关系。1、等价关系的定义一、等价关系13例如，我们用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是等价关系。14又如设集合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是等价关系。15再如设集合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是等价关系。16由上述3个例子可知那种同姓氏、同房间、同年龄的关系都是等价关系。如果抽象地讨论，对集合A中的元素按照某种特性分成几个组，每个元素只属于一个组〔如按年龄分组，即同年龄人在同一组内；或按姓氏分组，即同姓人在同一组内〕，并且定义在同一组内的元素是相关的，而不在同一组内的元素是不相关的，那么由此产生的二元关系必然是等价关系。由此可知等价关系所具有的重要特性。由此可见：等价关系实际上是同组关系。17下面将利用表格和关系矩阵来进一步了解等价关系的特征。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〕所表示的等价关系的表格和关系矩阵：18abcdefecbafd√√√√√√√√√√√√√√√√√√〔1〕a,b,c都姓“张”，d,e,f都姓“李”abcdefecbafd易见在描述等价关系的表格中，带有“√”的格子将形成假设干个正方形；而在关系矩阵中那么有一些小方阵，其元素都是1，而其它元素都是0。19对于〔2〕所示的等价关系的表格表示和关系矩阵也有上述特征：abcdefecbafd√√√√abcdefecbafd〔2〕a,b,c,d都是20岁，e,f都是22岁；√√√√√√√√√√√√√√√√20对于〔3〕所示的等价关系，如果将集合A={a,b,c,d,e,f}中的顺序改为A={a,b,d,c,e,f}也就是把相关的元素排在一起那么所画出的表格也显示上述特征：〔3〕a,b,d同住一个房间，c,e,f同住另一个房间。abdcefedbafc√√√√√√√√√√√√√√√√√√abdcefedbafc21例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是可传递的，说明此关系是等价关系。22在集合A中，以相关元素顺序排列，即：A={1,4,7,2,5,3,6}也就是把相关的元素排在一起那么所画出的表格表示和关系矩阵如下：由此可见模3同余关系也是一种分组关系，它是把A中的元素被3除后，余数为1的分为一组〔1,4,7〕，余数为2的分为一组〔2,5〕，余数为3的分为一组〔3,6〕。1472536374165214725363741652√√√√√√√√√√√√√√√√√23以上的例子不仅说明集合A上的等价关系实际上是一种“同组”关系。即当集合A确定一种“分组”形式后，也就确定了A上的一种等价关系〔只要将同一组的元素认作是相关的〕；反之当确定一个A上的等价关系后，也就确定了A上的一种“分组”形式〔只要将相关元素合成一组〕。为了详细地讨论这一问题，下面介绍等价类和划分这两个概念：24二、等价类定义：设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。25又如设集合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。26“商”和除法有关，比方把一块蛋糕平均分成四份，从两种不同的角度看这件事：从算术角度看：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分生日日快快乐乐生27思考：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}}。答案：28答案：有4个是不相同的等价类，它们是{a,b}，{c,d,e,f}，{g}，{h}。2.A={a,b,c,d,e,f,g,h},A上的等价关系R如下图：所以A关于R的商集为A/R={{a,b}，{c,d,e,f}，{g}，{h}}。abcdefghfcbagedh√√√√√√√√√√√√√√√√√√√√√√写出A关于R的商集。29三、集合的划分定义：设A是集合，A1，A2，…An，是A的子集，如果A1∪A2∪…∪An=A，且Ai∩Aj=Ø〔i≠j,i=1,2,…n,j=1,2,…n〕.由以A1，A2，…An作为元素构成的集合S={A1，A2，…An}称为A的一个划分，每一个子集Ai称为块。例如A={a,b,c,d,e,f},A2={{a,d,e}，{b,c,f}}A1={{a,b}，{c,d}，{e,f}}A3={{a,f}，{b,d,e}，{c}}那么A1,A2,A3都是A的划分；在A1中{a,b}，{c,d}，{e,f}是块。30思考：设A＝{a,b,c,d},给定π1,π2,π3,π4,π5,π6如下：

π1={{a,b,c},{d}}，π2={{a,b},{c},{d}}

π3={{a},{a,b,c,d}},π4={{a,b},{c}}

π5={

,{a,b},{c,d}},π6={{a,{a}},{b,c,d}}问哪些是A的划分,哪些不是A的划分？

答案：π1和π2是A的划分,其他都不是A的划分.

31由此可知，如果R是A上的等价关系，那么商集A/R就是A上的一个划分，等价类就是块。定理：集合A上的一个划分能确定一个A上的等价关系，反之确定了A上的一个等价关系也能确定A上的一个划分。例如A={a,b,c,d,e},A={{a}，{b,c,d,e}}那么它所确定的等价关系的表格表示如下图：abcde√√√√√√√√√√√√√√√√√ebadc32又如A={a,b,c,d,e},R为A上的等价关系，其表格表示如下图：那么由R确定的划分为A={{a,b},{c},{d,e}}。abcde√√√√√√√√√ebadc由此可知，集合A上的等价关系与划分可以建立1-1对应关系。33四、相容关系定义：设R是A上的二元关系，如果满足：〔1〕R是自反的；〔2〕R是对称的。那么称R是A上的相容关系。易知，等价关系是一种特殊的相容关系，即具有传递的相容关系。在人际关系中朋友关系是相容关系，但它不是等价关系，因为它满足自反性、对称性、但它不满足可传递性。34设A={boy,root,cat,beer,and},R是A上的二元关系，其定义为：当两个单词至少有一个字母相同时，那么认为是相关的。显然R是自反的，对称的，所以R是A上的相容关系。但它不是等价关系，因为它不是可传递的。如(boy,root)∈R,(root,cat)∈R,而(boy,cat)

R。35定义：设R是A上的相容关系，B是A的子集，而且在B中任意两个元素都是相关的，那么称B为由相容关系R产生的相容类。36例如设A={134，345，275，347，348，129}，R是A上的二元关系，其定义为：a,b∈A;且a和b至少有一个数码相同，那么〔a,b〕∈R.显然R是相容关系。A的子集：{134，347，348}，{275，345}，{134，129}等都是相容类。对于前两个相容类，都能添加新的元素组成新的相容类。如在相容类{134，347，348}中添加新的元素345，可组成新的相容类：{134，347，348，345}；在相容类{275，345}中添加新的元素347，可组成新的相容类：{275，345，347}。而对于第三个相容类：{134，129}，添加任意一个新元素就不再组成相容类，称这样的相容类为最大相容类。37对于最大相容类还可以这样认定：R是A上的相容关系，B是相容类，在差集A—B中没有元素能和B中所有元素都是相关的，那么称B为最大相容类。利用相容关系的图形表示可以很方便地确定相容类和最大相容类。38134129348347275345如下图中，完全多边形的顶点集合就是相容类。所谓完全多边形是指每个顶点都与其它顶点有边联结的多边形。例如三角形是完全多边形，一个四边形加上两条对角线也是完全多边形。由于顶点134,348,347构成了一个三角形，所以{134,348,347}是相容类；同理{275，345，347}是相容类；{134，347，348，345}也是相容类。如39由此可见，图中最大的完全多边形的顶点集合就最大相容类。这里的“最大”是这样的含义：如果一个完全多边形，在添加任何新的顶点就不再成为完全多边形，那么称此完全多边形是最大的完全多边形。如由顶点134，347，348，345构成的完全多边形是最大完全多边形；由顶点345，275，347构成的完全多边形也是大完全多边形。易见，在该图中，有四个最大相容类，它们是：{192，134}，{129，275}，{345，275，347}，{134，345，347，348}。13412934834727534540定义：A是集合，A1,A2,…，An都是它的非空子集，令S={A1,A2,…，An},如果A1∪A2∪…∪An=A，那么称S为A的覆盖。例如A={1，2，3，4，5}，S={{1，2}，{2，3，4}，{1，3，5}}，那么S是A的覆盖。41定义：S={A1,A2,…，An}是集合A的覆盖，且对于S中任意元素Ai,不存在S中的其它元素Aj，使得Ai是Aj的子集，那么称S为A的完全覆盖。例如A={a,b,c,d,e}S1={{a,b},{b,c,d},{d,e}}S2={{a,b},{a,b,c},{a,d,e}}其中S1是A的覆盖又是完全覆盖，而S2是A的覆盖但不是完全覆盖，因为{a,b}是{a,b,c}的子集。42相容关系和覆盖之间的关系：如果R是A上的相容关系，对于A中的任意元素a，集合{a}是一个相容类，并且可以对此集合不断地添加新的元素，直到使它成为最大相容类。因此，A中的每一个元素都将是某一个最大相容类的元素。由此可见，相容关系R产生的所有最大相容类构成的集合是A的一个覆盖；又由最大相容类的定义可知，一个最大相容类决不是另一个最大相容类的子集。所以由最大相容类构成的集合是A的一个完全覆盖。由此可得下面的结论：R是A上的相容关系，R能确定一个A上的完全覆盖；反之，当给定A的一个完全覆盖时，那么能确定A上的相容关系R，使R产生的最大相容类构成的集合就是这个完全覆盖。43例.A={1，2，3，4，5，6}，R为A上的相容关系，其图形表示如下图，求R所确定的完全覆盖。123456解：由图可知，R产生的最大相容类为：{1，2，6}，{1，4，5}，{3，6}。所以R确定的完全覆盖S={{1，2，6}，{1，4，5}，{3，6}}。44例.

A={a,b,c,d,e,f,g},A的完全覆盖S={{a,b},{b,c,f,g},{c,d,e}},写出S所确定的相容关系R。abcdfeg解由S容易得到R的图形表示，如图，所以S所确定的相容关系：R={(a,a),(b,b),(a,b),(b,a),(c,c),(f,f),(g,g),(b,c),(c,b),(b,f),(f,b),(b,g),(g,b),(c,f),(f,c),(c,g),(g,c),(f,g),(g,f),(d,d),(e,e),(c,d),(d,c),(c,e),(e,c),(d,e),(e,d)}。45思考：1、集合A={a1,a2,a3,a4,a5,a6},R是A上的相容关系，其关系矩阵为：求R的所有最大相容类。2、集合A={111，122，341，456，795，893}R是A上的二元关系，当a,b∈A，且a和b至少有一个数码相同，那么〔a,b〕∈R.试画出R的关系图。并写出R的所有最大相容类。463、集合A={a,b,c,d,e,f,g}.完全覆盖S={{a,b,c,d},{c,d,e},{d,e,f},{f,g}},写出S所确定的相容关系R。47偏序关系定义4.22非空集合A上的自反、反对称和传递的关系，称为A上的偏序关系，记作≼.设≼为偏序关系,如果<x,y>∈≼,那么记作x≼y,读作x“小于或等于”y.

实例集合A上的恒等关系IA是A上的偏序关系.小于或等于关系,整除关系和包含关系也是相应集合上的偏序关系.48相关概念定义4.23x与y可比设R为非空集合A上的偏序关系,

x,yA,x与y可比x≼y∨y≼x.

结论：x,yA，下述几种情况发生其一且仅发生其一.

x≺y,y≺x,x＝y,x与y不是可比的

定义4.25全序R为非空集合A上的偏序,x,yA,x与y都可比，那么称R为全序.定义4.26覆盖x,y∈A,如果x≺y且不存在zA使得x≺z≺y,那么称y覆盖x.实例：数集上的小于或等于关系是全序关系整除关系不是正整数集合上的全序关系{1,2,4,6}集合上的整除关系,2覆盖1,4和6覆盖2.但4不覆盖1.49偏序集与哈斯图定义4.27集合A和A上的偏序关系≼一起叫做偏序集,记作<A,≼>.

实例：整数集和数的小于等于关系构成偏序集<Z,≤>幂集P(A)和包含关系构成偏序集<P(A),R>.哈斯图：利用偏序自反、反对称、传递性简化的关系图特点：每个结点没有环两个连通的结点之间的序关系通过结点位置的上下表示，位置低的元素的顺序在前具有覆盖关系的两个结点之间连边50哈斯图实例例6<{1,2,3,4,5,6,7,8,9},R整除><P({a,b,c}),R

>51例7偏序集<A,R>的哈斯图如以下图所示,试求出集合A和关系R的表达式.

哈斯图实例〔续〕A={a,b,c,d,e,f,g,h}

R={<b,d>,<b,e>,<b,f>,<c,d>,<c,e>,<c,f>,<d,f>,<e,f>,<g,h>}∪IA

52偏序集的特定元素定义4.28设<A,≼>为偏序集,BA,y∈B.

(1)假设x(x∈B→y≼x)成立,那么称y为B的最小元.

(2)假设x(x∈B→x≼y)成立,那么称y为B的最大元.

(3)假设x(x∈B∧x≼y→x=y)成立,那么称y为B的极小元.

(4)假设x(x∈B∧y≼x→x=y)成立,那么称y为B的极大元.

性质：对于有穷集，极小元和极大元必存在，可能存在多个.最小元和最大元不一定存在，如果存在一定惟一.最小元一定是极小元；最大元一定是极大元.孤立结点既是极小元，也是极大元.

53定义4.29设<A,≼>为偏序集,BA,yA.〔1〕假设x(x∈B→x≼y)成立,那