二元关系(syzhang II)

二元关系（Cont.）关系的闭包闭包的定义闭包的构造方法闭包的性质闭包的相互关系闭包的定义定义设R是非空集合A上的关系，R的自反（对称或传递）闭包是A上的关系R′，使得R′满足以下条件：（1）R′是自反的（对称的或传递的）（2）RR′（3）对A上任何包含R的自反（对称或传递）关系R″有R′R″。一般将R的自反闭包记作r(R)，对称闭包记作s(R)，传递闭包记作t(R)。闭包的构造方法定理设R为A上的关系，则有（1）r(R)＝R∪R0（2）s(R)＝R∪R-1（3）t(R)＝R∪R2∪R3∪…设A={a,b,c,d},R={a,b,b,a,b,c,c,d},则R和r(R),s(R),t(R)分别是什么？r(R)=R∪R0={a,b,b,a,b,c,c,d,a,a,b,b,c,c,d,d}s(R)=R∪R-1={a,b,b,a,b,c,c,d,c,b,d,c}t(R)=R∪R2∪R3∪…R={a,b,b,a,b,c,c,d}R2={a,a,a,c,b,b,b,d}R3={a,b,a,d,b,a,b,c}R4=R2;R5=R3。∴t(R)=R∪R2∪R3t(R)={a,b,b,a,b,c,c,d，a,a,a,c,b,b,b,d,a,d}通过关系矩阵求闭包的方法设关系R，r(R)，s(R)，t(R)的关系矩阵分别为M，Mr，Ms和Mt，则Mr＝M＋E对角线上的值都改为1Ms＝M＋M′若aij＝1，则令aji＝1Mt＝M＋M2＋M3＋…沃舍尔算法其中E是和M同阶的单位矩阵，M′是M的转置矩阵。注意在上述等式中矩阵的元素相加时使用逻辑加。等价关系与划分(Equivalence&Partition)定义设R为非空集合上的关系。如果R满足自反性、对称性和传递性，则称R为A上的等价关系。设R是一个等价关系，若x,y∈R，称x等价y，记做x～y。举例(1)平面上三角形集合中，三角形的全等、相似关系。(2)正整数集合中的整除关系不是等价关系。例设A＝{1,2,…,8}，如下定义A上的关系R：R＝{x，y|x，y∈A∧x≡y(mod3)}其中x≡y(mod3)叫做x与y模3同余，即x除以3的余数与y除以3的余数相等。不难验证R为A上的等价关系，因为x∈A，有x≡x(mod3)x,y∈A，若x≡y(mod3)，则有y≡x(mod3)x,y,z∈A，若x≡y(mod3)，y≡z(mod3)，则有x≡z(mod3)等价类定义设R为非空集合A上的等价关系，x∈A，令[x]R={y|y∈A∧xRy}称[x]R为x关于R的等价类，简称为x的等价类，简记为[x]x的等价类是A中所有与x等价的元素构成的集合。上例中的等价类是：[1]＝{1,4,7}=[4]＝[7][2]＝{2,5,8}=[5]＝[8][3]＝[6]＝{3,6}整数集合Z上的模n等价关系设x是任意整数，n为给定的正整数，则存在唯一的整数q和r，使得x＝qn+r其中0≤r≤n-1，称r为x除以n的余数。例如n＝3，那么－8除以3的余数为1，因为-8＝-3×3+1对于任意的整数x和y，定义模n的同余关系～为x～yx≡y(modn)不难验证它是整数集合Z上的等价关系。将Z中的所有整数根据它们除以n的余数分类如下：0的数，其形式为kn，k∈Z余数为1的数，其形式为kn+1，k∈Z…余数是n-1的数，其形式为kn+(n-1)，k∈Z以上构成了n个等价类，使用等价类的符号可记为[i]＝{kn+i|k∈Z}，i=0，1，…，n-1等价类的性质定理设R是非空集合A上的等价关系，则1）x∈A，[x]是A的非空子集。2）x,y∈A，如果xRy，则[x]＝[y]。3）x,y∈A，如果x,yR，则[x]与[y]不交。4）∪{[x]|x∈A}＝A。证明略商集定义设R为非空集合A上的等价关系，以R的所有等价类作为元素构成的集合称为A关于R的商集记做A/R，即A/R={[x]R|x∈A}上例中的商集为A/～={[0],[1],[2]}={{1,4,7},{2,5,8},{3,6}}整数集合Z上模n同余等价关系的商集是Z/～={[0],[1],…,[n-1]}Zn={0,1,…,n-1}划分定义设A为非空集合，若A的若干子集A1,A2,…满足下面的条件：（1）非空:Ai≠;2）两两不交:Ai∩Aj＝(i≠j);3）覆盖：∪Ai=A则称A1,A2,…是A的一个划分。说明设集合π是A的非空子集的集合，若这些非空子集两两不相交，且它们的并等于A，则称π是集合A的划分。例设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的划分π1和π2是A的划分，其它都不是A的划分。因为π3中的子集{a}和{a,b,c,d}有交，∪π4≠A，π5中含有空集，而π6根本不是A的子集族。商集与划分商集就是A的一个划分，并且不同的商集将对应于不同的划分。反之，任给A的一个划分π，如下定义A上的关系R：R={x,y|x,y∈A∧x与y在π的同一划分块中}则不难证明R为A上的等价关系，且该等价关系所确定的商集就是π。由此可见，A上的等价关系与A的划分是一一对应的。例给出A＝{1,2,3}上所有的等价关系这些划分与A上的等价关系之间的一一对应是：π1对应于全域关系EA，π5的对应于恒等关系IA，π2，π3和π4分别对应于等价关系R2，R3和R4。其中R2={2,3,3,2}∪IAR3={1,3,3,1}∪IAR4={1,2,2,1}∪IA例题问集合A＝{a,b,c,d}上有多少个不同的等价关系？解答只要求出A上的全部划分，即为等价关系。划分为一个块的情况：1种，即{a,b,c,d}划分为两个块的情况：7种，即{{a,b},{c,d}}，{{a,c},{b,d}}，{{a,d},{b,c}}{{a},{b,c,d}}，{{b},{a,c,d}}，{{c},{a,b,d}}，{{d},{a,b,c}}划分为三个块的情况：6种，即{{a,b},{c},{d}}，{{a,c},{b},{d}}，{{a,d},{b},{c}},{{a},{b},{c,d}}，{{a},{c},{b,d}}，{{a},{d},{b,c}}划分为四个块的情况：1种，即{a},{b},{c},{d}}因此，共有15种不同的等价关系。偏序关系(PartialOrder)定义设R为非空集合A上的关系。如果R满足自反性、反对称性和传递性，则称R为A上的偏序关系，记作≤。设≤为偏序关系，如果x,y∈≤，则记作x≤y，读作“x小于或等于y”。注意这里的“小于或等于”不是指数的大小，而是在偏序关系中的顺序。x“小于或等于”y的含义是：依照这个序，x排在y的前边或者x就是y。根据不同偏序的定义，对序有着不同的解释。偏序关系举例集合A上的恒等关系IA小于或等于关系整除关系包含关系可比定义设R为非空集合A上的偏序关系，定义(1)x,y∈A，x＜yx≤y∧x≠y。(2)x,y∈A，x与y可比x≤y∨y≤x。其中x＜y读作x“小于”y。这里所说的“小于”是指在偏序中x排在y的前边。在具有偏序关系的集合A中任取两个元素x和y，可能有下述几种情况发生：x＜y(或y＜x)，x＝y，x与y不可比。例如A＝{1，2，3}，≤是A上的整除关系，则有1＜2，1＜3，1=1，2=2，3=3，2和3不可比。全序关系定义设R为非空集合A上的偏序关系，如果x,y∈A，x与y都是可比的，则称R为A上的全序关系(或线序关系Linearorder)。例如数集上的小于或等于关系是全序关系，因为任何两个数总是可比大小的。整除关系一般来说不是全序关系，如集合{1,2,3}上的整除关系就不是全序关系，因为2和3不可比。偏序集（Poset）定义集合A和A上的偏序关系≤一起叫做偏序集，记作A,≤。例如整数集合Z和数的小于或等于关系≤构成偏序集Z,≤集合A的幂集P(A)和包含关系构成偏序集P(A),。覆盖定义设A,≤为偏序集。x,y∈A，如果x＜y且不存在z∈A使得x＜z＜y，则称y覆盖x。例如{1,2,4,6}集合上的整除关系，有2覆盖1，4和6都覆盖2。但4不覆盖1，因为有1＜2＜4。6也不覆盖4，因为4＜6不成立。哈斯图(HasseDiagram)利用偏序关系的自反性、反对称性和传递性所得到的偏序集合图，称为哈斯图。画偏序集A，≤的哈斯图的方法(1)用小圆圈代表元素。(2)x,y∈A，若x＜y，则将x画在y的下方。(3)对于A中的两个不同元素x和y，如果y覆盖x，就用一条线段连接x和y。例画出偏序集{1,2,3,4,5,6,7,8,9}，整除关系和P({a,b,c}),的哈斯图。{a}例已知偏序集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偏序集中的特殊元素定义设A，≤为偏序集，BA，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的极大元。363242126B最大元最小元极大元极小元{2,3,6,12,24,36}{6,12}{2,3,6}{6}无无24,262,31261266无62,36666特殊元素的性质最小元是B中最小的元素，它与B中其它元素都可比。极小元不一定与B中元素可比，只要没有比它小的元素，它就是极小元。对于有穷集B，极小元一定存在，但最小元不一定存在。最小元如果存在，一定是唯一的。极小元可能有多个，但不同的极小元之间是不可比的（无关系）。如果B中只有一个极小元，则它一定是B的最小元。哈斯图中，集合B的极小元是B中各元素中的最底层。例设偏序集A,≤如右图所示，求A的极小元、最小元、极大元、最大元。解答极小元：a,b,c,g极大元：a,f,h。没有最小元与最大元说明哈斯图中的孤立顶点既是极小元也是极大元。上界、下界定义设A，≤为偏序集，BA，y∈A。（1）若x(x∈B→x≤y)成立，则称y为B的上界。（2）若x(x∈B→y≤x)成立，则称y为B的下界。（3）令C＝{y|y为B的上界}，则称C的最小元为B的最小上界或上确界。（4）令D＝{y|y为B的下界}，则称D的最大元为B的最大下界或下确界。上界与下界举例363242126B上界下界上确界下确界{2,3,6,12,24,36}{6,12}{2,3,6}{6}无无无无12,24,362,3,61266,12,24,36无6无6,12,24,362,3,666考虑右图中的偏序集。令B＝{b，c，d}，则B的下界和最大下界都不存在，上界有d和f，最小上界为d。上界与下界的性质B的最小元一定是B的下界，同时也是B的最大下界。B的最大元一定是B的上界，同时也是B的最小上界。B的下界不一定是B的最小元，因为它可能不是B中的元素。B的上界也不一定是B的最大元。B的上界、下界、最小上界、最大下界都可能不存在。如果存在，最小上界与最大下界是唯一的。作业习题：1.4.162.P.109:证明例题4.29给出的关系是S×S上的等价关系。习题设R是复数集合C上的关系，且满足xRyx-y＝a+bi，a和b为给定的非负整数，试确定R的性质并证明之。解答（1）当a