第4章 关系.doc

习题41设A=0，1，2，3，A上的两个关系：R = （a，b）a=b+1或a=b/2, S = (a,b)b=a+2 求(1)RS； (2) SR。（3）若B=a,b,求出AB及BA。解：R=(1,0),(2,1),(3,2),(0,0),(1,2)，S=(0,2),(1,3)(1) RS=(1,2),(2,3),(0,2)(2) SR=(0,1),(1,2)(3) AB=(0,a),(0,b),(1,a),(1,b),(2,a),(2,b),(3,a),(3,b)，BA=(a,0),(a,1),(a,2),(a,3),(b,0),(b,1),(b,2),(b,3)。2举出一个集合上关系的例子，分别适合于自反，对称，传递中的两个且仅适合两个。解：设A=1,2,3,4，R为A上关系。R自反、对称：R=,；R自反、传递：R=,；R对称、传递：R=,。3设1,2,3,4,5,6，B=1,2,3，从到B的关系x,y|x=y2，求(1)R (2)R-1。解：(1)R=；(2) R-1=。4如果关系R和S是自反的，对称的和传递的，证明RS也是自反的，对称的和传递的。解：参见第8题(2),(6),(10)。5设S=,，上的关系1,2，2,1，2,3，3,4求(1)RR (2)R-1。解：RR=,，R-1=,。6设R1和R2是A上的二元关系，说明以下命题的真假：a) 若R1和R2是自反的，则R1 o R2是自反的;b) 若R1和R2是反自反的，则R1 o R2是反自反的;c) 若R1和R2是对称的，则R1 o R2是对称的;d) 若R1和R2是传递的，则R1 o R2是传递的。解：a),c),d)参见第8题(7),(11),(3)。b) F。R1=(1,2),(2,3)，R2=(2,2),(3,1)，R1 o R2=(1,2),(2,1)8是非判断：设R和S是A上的二元关系，确定下列命题是真还是假。如果命题为真，则证明之；如果命题为假，则给出一个反例。（1）若R和S是传递的，则RS是传递的。解：F。R(1,2)，S=(2,3)，RS=(1,2),(2,3)。（2）若R和S是传递的，则RS是传递的。解：T。证明：(x,y),(y,z) RS(x,y),(y,z)R(x,y),(y,z)S(x,z)R(x,z) S(x,z)RS。（3）若R和S是传递的，则RoS是传递的。解：F。R=(1,2),(3,4)，S=(2,3),(4,4)，RoS=(1,3),(3,4)（4）若R是传递的，则R-1是传递的。解：T。证明：x R-1y,yR-1zyRx,zRyzRxxR-1z（5）若R和S是自反的，则RS是自反的。解：T。证明：(a,a)R(a,a)S(a,a)R(a,a)S(a,a)RS。（6）若R和S是自反的，则RS是自反的。解：T。证明：(a,a)R(a,a)S(a,a)RS。（7）若R和S是自反的，则RoS是自反的。解：T。(a,a)R(a,a)S(a,a)RoS。（8）若R是自反的，则R-1是自反的。解：T。证明：(a,a)R(a,a) R-1。（9）若R和S是对称的，则RS是对称的。解： T。证明：(x,y) RS(x,y)R(x,y) S(y,x)R(y,x) S(y,x)RS。（10）若R和S是对称的，则RS是对称的。解： T。证明：(x,y) RS(x,y)R(x,y) S(y,x)R(y,x) S(y,x)RS。（11）若R和S是对称的，则RoS是对称的。解：F。R=(1,2),(2,1)，S=(2,3),(3,2)，RoS=(1,3)（12）若R是对称的，则R-1是对称的。解： T。证明：(x,y)R-1(y,x)R(x,y)R(y,x)R-1。（13）若R和S是反对称的，则RS是反对称的。解：F。R=(1,2)，S=(2,1)，RS=(1,2),(2,1)（14）若R和S是反对称的，则RS是反对称的。解：T证明：若xy，(x,y) RS(x,y)R(x,y) S(y,x)R(y,x) S(y,x)RS（15）若R和S是反对称的，则RoS是反对称的。解：F。R=(3,1),(2,2)，S=(1,2),(2,3)，RoS=(3,2),(2,3)（16）若R是反对称的，则R-1是反对称的。解：T。证明：若xy，(x,y)R-1(y,x)R(x,y)R(y,x)R-19设R1和R2是集合A上的二元关系，t(R1)t(R2) t(R1R2)。证明：R1 (R1R2)，R2 (R1R2)，故 t(R1) t(R1R2)，t(R2) t(R1R2)，进而 t(R1)t(R2) t(R1R2)。 10设A=a,b,c,d，A上的二元关系R=(a,b), (b,a), (b,c), (c,d)，试求t(R)，并画出它的关系图。解：R=(a,b), (b,a), (b,c), (c,d), (a,a), (a,c), (a,d), (b,b), (b,d)ad4bc11确定下列各式是不是A=1,2,3,4,5上的等价关系，如果是等价关系，请写出它的等价类。(1)(1,1),(2,2),(3,3),(4,4),(5,5),(1,3),(3,1),(1,5),(5,1),(3,5),(5,3)解：14523由关系图易见，该关系具有自反性、对称性和传递性，故是等价关系。等价类：1=3=5=1,3,5，2=2，4=4。(2)(1,1),(2,2),(3,3),(4,4),(5,5),(1,3),(3,1),(3,4),(4,3)；解：(1,3)和(3,4)属于该关系，而(1,4)不属于该关系，故该关系不具有传递性，不是等价关系。(3)(1,1),(2,2),(3,3),(4,4)；解：(5,5)不属于该关系，故该关系不具有自反性，不是等价关系。(4)(a,b)|4整除a-b, a,bA；解：,145234个等价类：1=5=1,5，2=2，3=3，4=4。(5)(a,b)|3整除a+b,a,bA；解：,不满足自反性和传递性，不是等价关系。(6)(a,b)|a整除2-b,a,bA。解：,不满足自反性、对称性和传递性（和属于该关系，而不属于该关系），不是等价关系。12（1）设A=1,2，R=AA，S=IA，问RS是不是自反的？解：R=(1,1),(1,2),(2,1),(2,2)，S=(1,1),(2,2)R-S=(1,2),(2,1)，是自反。（2）A=1,2，B=(1,1),(2,2)，问AAB是不是自反的？解：AA=(1,1),(1,2),(2,1),(2,2)，AAB(1,2),(2,1)，是自反。（3）A=1,2，B=(1,2),(2,1)，问AAB是不是反自反的？解：AAB(1,1),(2,2)，不是反自反。（4）A=1,2，R=(1,2)，S=(2,1)，问RS是不是反对称的？解：RS=(1,2),(2,1)，不是反对称。（5）A=1,2,3，B=(1,1),(2,2),(3,3),(1,2) 问AAB是不是反对称的？解：AAB(1,3),(2,1),(2,3),(3,1),(3,2)，不是反对称的。（6）A=1,2，R=(1,2)，S=(2,1)，问RS是不是传递的？解：RS=(1,2),(2,1)，不是传递的。（7）举出集合A上的既是等价关系又是偏序关系的一个例子。解：IA。13集合A上的等价关系的三个性质是什么？解：自反性、对称性和传递性。14集合A上的偏序关系的三个性质是什么？解：自反性、反对称性和传递性。15集合A=1,2,10上的关系R=|x+y=10,x,yA，则R的性质为（ ）。(1)自反的(2)对称的(3)传递的，对称的 (4)传递的解：(2)16设1，2，3，4，5，6，是A上的整除关系，求R的闭包。解：R=,，xxR自反闭包r(R)=R；对称闭包s(R)= ,；xy, yz，则xzR具有传递性传递闭包t(R)=R。17设R是一个二元关系,设S=(a,b)|存在某个c,使(a,c)R且(c,b)R。证明如果R是一个等价关系，则S也是一个等价关系。证明：R是等价关系，则R具有自反性、对称性、传递性。自反性：a (a,a)Ra(a,a)R(a,a)R) a (a,a)S对称性：(a,b)Sc(a,c)R(c,b)R)c(c,a)R(b,c)R)(b,a)S传递性：(a,d)S(d,e)Sc1(a,c1)R(c1,d)R)c2(d,c2)R(c2,e)R) (a,d)R(d,e)R (a,e)S故S具有自反性、对称性、传递性，是一个等价关系。18设R是A上的一个自反关系, 证明R是一个等价关系当且仅当若(a,b)R,(a,c)R则(b,c)R。证明：(1)充分性。若R是一个等价关系，(a,b)R(a,c)R(b,a)R(a,c)R(b,c)R(2)必要性。若(a,b)R(a,c)R(b,c)R对称性：(a,b)R(a,b)R(a,a)R(b,a)R传递性：(a,b)R(b,c)R(b,a)R(b,c)R(a,c)R故R是一个等价关系。19设A=1,2,3,4,5上的关系R=|x+y=5,x,yA,S=|xy ,x,yA,求RS。解：R=,S=,RS=,20同室4人，每人都有一些爱好如下：A爱好游泳、跳舞、下棋；B爱好游泳、跳舞；C爱好打球、跳舞；D爱好游泳、下棋。有相同爱好者必能谈得来，试给出哪些人在一起时他们会谈得来。解：设集合S=A，B，C，D，S上的关系R=|x,y属于A，且 x和y有相同爱好，R是相容关系，其关系图如下：ABCDR产生的最大相容类为A,B,C,A,B,D。故A,B,C在一起，或者A,B,D在一起，会谈得来。21.请举一个相容关系的例子。解：设R为定义在集合A上的二元关系，其中： A= cat, teacher, cold, desk, knife, by R= | x,y属于A，且