《关系习题解析》PPT课件.ppt

1,关系习题解析 经典习题,2,1. 设A = a, b, B = 0,1, 求: A2 B ， P(),解: (1) A2B =(a, a),(a, b),(b, a),(b, b)0,1 = (a, a, 0), (a, b, 0), (b, a, 0), (b, b, 0), (a, a, 1), (a, b, 1), (b, a, 1), (b, b, 1) (2) AP(A)=(a, ), (a, a), (a, b), (a, a,b), (b, ), (b, a), (b, b), (b, a,b),3, 设R是集合A上的关系 （1）R是自反的，则RR是自反的； （2）R是对称的，则RR是对称的； （3）R是反自反和传递的，则R是反对称的；,4,/*证明思想：根据定义给出的性质证明*/ 证明： （1）证明思想与（2）和（3）相同 （2）设(a, b)RR, 则存在c, (a, c)R, (c, b)R; 因为R是对称的，所以(b, c)R, (c, a)R; 所以(b, a)RR。则RR是对称的。 （3）假设(a, b)R, (b, a)R。因为R是传递的，所以(a, a)R，(b, b)R；因为R是反自反的，所以导致矛盾。,5,3 设R是A上的关系，若R是自反的和传递的，则RR=R。 证明思想： 证明：1）证明RRR； 2） 证明RRR：,6,证明： 1）证明RRR： 设(a, b)RR，存在cA, 使得(a, c)R, (c, b)R，因为R是传递的，所以(a, b)R；则RRR； 2） 证明RRR： 设(a, b)R，R是自反的，(b, b)R，所以(a, b)RR；则RRR。 所以RR=R。,7,4 举出A=1, 2, 3上关系R的例子，使其具有下述性质： a) 既是对称的，又是反对称的； b) 既不是对称的，又不是反对称的； c) 是传递的。,8,解：a) R=(1, 1), (2, 2), (3, 3) b) R=(1, 2), (2, 1), (2, 3) c) R=(1, 2), (2, 1), (1, 1), (2, 2), (3, 3),9,5 举出一个集合上关系的例子，分别适合于自反、对称、传递中的两个且仅适合两个。,10,解：A=a, b, c A) R=(a, a)对称，传递, 不自反； B) R=(a, a), (b, b), (c, c), (a, b)自反，传递，不对称； C) R=(a, a), (b, b), (c, c), (a, b), (b, c), (b, a), (c, b)自反，对称，不传递,11,6 如果关系R和S是自反的、对称的和传递的，证明RS也是自反的、对称的和传递的。 证明：a）因为R和S是自反的，对任意的aA，(a, a)R并且(a, a)S，则(a, a)RS。 b）对任意的a, bA, ab，如果(a, b)RS，因为(a, b)RS，所以(a, b)R并且(a, b)S; 因为R和S是对称的，所以(b, a)R并且(b, a)S。则(b, a)RS。 c）任意的(a, b)RS，(b, c) RS，则 (a, b) R，(a, b)S，(b, c)R，(b, c) S，因为R和S是传递的，因此(a, c)R，(a, c)S。所以(a, c) RS。,12,7 是非判断：设R和S是A上的二元关系，确定下列命题是真还是假。如果命题为真，则证明之；如果命题为假，则给出一个反例。 (1)若R和S是传递的，则RS是传递的。 (2)若R和S是传递的，则RS是传递的。 (3)若R是传递的，则R-1是传递的。 (4)若R和S是对称的，则RS是对称的。 (5)若R是对称的，则R-1是对称的。 (6) 若R和S是反对称的，则RS是反对称的。 (7) 若R和S是反对称的，则R S是反对称的。 (8) 若R是反对称的，则R-1是反对称的。,13,(1)假。R=(1, 2), S=(2, 3)。 (2)假。R=(1, 4), (2, 5), S=(4, 2), (5, 3)。 (3)真。任意(a, b)R-1, (b, c)R-1。所以(c,b)R, (b, a)R；又因为R是传递的，所以(c, a)R。因此(a, c)R-1。 (4)假。R=(1, 2), (2, 1), S=(2, 3), (3, 2)。则RS=(1, 3)。,14,(5)真。根据对称的性质证明。对于任意的 (a, b) R-1， (b, a)R； 因为R是对称的， 则(a, b)R，所以(b, a) R-1。则R-1是对称的。 (6) 假。R=(1, 2)，S=(2, 1)，则RS=(1, 2), (2, 1)。 (7) 假。R=(1, 3), (2, 4), S=(3, 2), (4, 1), 则RS=(1, 2), (2, 1)，不是反对称的。 (8) 真。反证法证明。设R-1不是反对称的。则存在(a, b) R-1, (b, a) R-1, ab。则(a, b)R, (b, a)R, 与R是反对称的矛盾。,15,8 设R是A上的传递和自反关系, 设T是A上的二元关系：(a,b)T当且仅当(a,b)和(b,a)都属于R, 证明T是一个等价关系。,16,证明:(注意,T是A上的二元关系.) （1）自反: 对任意aA,(关键证明(a,a)T)；因为R是A上的自反关系, 所以(a,a)R, (a,a)R, 因此根据T的定义,有(a,a)T. （2）对称:若(a,b)T,则(a,b)和(b,a)都属于R, 因此(b,a)和(a,b)都属于R, 所以(b,a)T.,17,（3）传递: 若(a,b)T,(b,c)T(关键证明(a,c)T,即要证明(a,c)R,(c,a)R)。由于(a,b)T,(b,c)T,则(a,b)和(b,a)都属于R,(b,c)和(c,b)都属于R, 因为R传递,所以当(a,b)和(b,c)都属于R时,有(a,c)属于R, 同样当(b,a)和(c,b)都属于R时,有(c,a)属于R。因为(a,c)R,(c,a)R, 所以(a,c)T。,18,9 设A=a,b,c,d,A上的二元关系R:R=(a,b), (b,a), (b,c),(c,d) 试求t(R), 并画出它的关系图。,19,20,10. 给定R=a, b,b, c,d, e，RS =b, d,b, b,b,e，求一个满足条件的基数最小的关系S 。一般地，若给定R和RS，S能被惟一地确定吗？基数最小的S能被惟一地确定吗？,解: S = c, d, c, b, c, e。 一般地, 若给定R和RS, S不能被惟一地确定。 如 S = c, d, c, b, c, e, a, b也满足条件。 基数最小的S不能被惟一地确定。 例如, R = a, b, a, c, RS = a, a, 基数最小的 S = b, a 或 S = c, a。,21,11. 下列关系中哪一个是自反的、对称的、反对称的或传递的? (1) 当且仅当|i - k|8(m, nN)时, 有mRn; (3) 当且仅当ik(i, kN)时, 有iRk。,解: (1) 是自反的|i - i| 8, 53 8 23 8, 不可传递的。 (3) 是自反的ii, 反对称58, 但85, 58, 818, 518, 可传递的。,22,特殊关系,12 设S=1, 2, 3, 4，并设A=SS，在A上定义关系R为：(a, b)R(c, d)当且仅当a+b=c+d。 （1）证明R是等价关系； （2）计算出A/R。,23,（1）证明： 1）对于任意的(a, b)SS，因为a+b=a+b，所以(a, b) R (a, b)，即R是自反的。 2） 如果(a, b) R (c, d)，则a+b=c+d，那么有c+d=a+b； 所以(c, d) R (a, b)，即R是对称的。 3） 如果(a, b) R (c, d)， (c, d) R (e, f)，则a+b=c+d，c+d= e+f；所以a+b= e+f，得(a, b) R (e, f)，即R是传递的。 （2）如果(a, b) R (c, d)，则a+b=c+d，所以根据和的数来划分。,24,13 设R、S是A上的等价关系，证明：RS是A上的等价关系当且仅当RS=SR。,25,证明思想： 1）RS是A上的等价关系RS=SR； 证明(i)RSSR； (ii)SRRS； 2） RS=SR RS是A上的等价关系； 证明RS是(i)自反的；(ii)对称的；(iii)传递的；,26,证明： 1）RS是A上的等价关系RS=SR： 如果(a, b)RS, 因为RS是对称的，所以(b, a)RS, 所以存在cA, 使得(b, c)R, (c, a)S；因为R和S是对称的，所以(c, b)R, (a, c)S； 则(a, b)SR； 同理，SR RS；,27,2）自反性：由于R、S自反，因此RS自反。 对称性：任意(a,b)RS，因RS=SR，因此(a,b)SR，则存在cA, 使得(a, c)S, (c,b)R；由R、S的对称性，得(c, a)S, (b,c)R，所以(b,a)RS。,28,传递性：（方法一）因为R,S为A上的等价关系，所以RRR，SSS. 下面证(RS)(RS)RS 利用已知条件(RS=SR) ，所以 （RS)(RS)=(RS)(SR)=RSSR 因SSS，所以RSSRRSR=SRR 因RRR，所以SRRSR =RS 即(RS)(RS)RS，因此传递性得证。,29,传递性：（方法二） 任意的(a,b)RS ，(b,c)RS，又RS=SR，所以(a,c)(RS) (RS)=(RS) (SR) 则存在kA，使得(a,k)RS，(k,c)SR； 则存在m，nA，使得(a,m)R，(m,k)S，(k,n)S，(n,c) R； 由S等价，因此(m,n) S，那么(a,c)RSR=RRS； 则存在p，qA，使得(a,p)R，(p,q)R，(q,c)S； 由R等价，因此(a,q)R； 所以(a,c)RS。 传递性得证。,30,14 设R是一个二元关系,设S=(a,b)|存在某个c,使(a,c)R且(c,b)R。证明：如果R是一个等价关系，则S也是一个等价关系。 证明: (1) 自反:对任意aA, (证明(a,a)S)。因为R是A上的自反关系, 所以(a,a)R, (a,a)R, 因此根据S的定义,有(a,a)S. (2) 对称:若(a,b)S,则存在cA,使得(a,c)和(c,b)都属于R, 因为R对称, 因此 (b,c)和(c,a)都属于R, 故根据S的定义,有(b,a)S,31,(3) 传递: 若(a,b)S,(b,c)S(关键证明(a,c)S,即要证明存在dA,使得(a,d)和(d,c)都属于R)。由于(a,b)S, 所以存在eA,使得(a,e)和(e,b)都属于R, 同样因为(b,c)S, 所以存在fA,使得(b,f)和(f,c)都属于R, 因为R传递, 所以当(a,e)和(e,b)属于R时,有(a,b)R, 当(b,f)和(f,c)属于R时,有(b,c)R, 现在(a,b)和(b,c)属于R, 根据S的定义,有(a,c)S。,32,15 设R是A上的一个自反关系，证明：R是一个等价关系当且仅当若(a,b)R，(a,c)R则(b,c)R。 证明:(1) R是一个等价关系，则当(a,b)R，(a,c)R必有(b,c)R。 因为R对称，所以当(a,b)R时，有(b,a)R， 因为R传递，所以当(b,a)R，(a,c)R时有(b,c)R。,33,(2) R是A上的一个自反关系，当(a,b)R，(a,c)R必有(b,c)R，证明R是等价关系。 自反:条件已知； 对称:若(a,b)R,因为R自反,故(a,a)R, 现在(a,b)R,(a,a)R,则根据条件(b,a)R； 传递: 若(a,b)R,(b,c)R (关键证明(a,c)R,注意与条件不同, 当(a,b)R,(a,c)R必有(b,c)R,而要证明的是(a,b)R,(b,c)R导出(a,c)R) 证明:因为(a,b)R,(b,c)R, 而R对称,所以(b,a)R, 现在(b,a)R,(b,c)R, 所以根据条件有(a,c)R,34,16 确定下列各式是不是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) (2)(1,1),(2,2),(3,3),(4,4),(5,5),(1,3),(3,1),(3,4),(4,3); (3)(1,1),(2,2),(3,3),(4,4); (4)(a,b)|4整除a-b,a,bA; (5)(a,b)|3整除a+b,a,bA; (6)(a,b)|a整除2-b,a,bA。,35,(1) 是，等价类为: 1=3=5=1,3,5 2=2 4=4 (2)不是.因为(1,3),(3,4)R,而(1,4)R. (3)不是. 因为A=1,2,3,4,5,而(5,5)R (4)是，等价类为: 1=5=1,5,2=2,3=3,4=4 (5)不是. 因为A=1,2,3,4,5,而1+1不能被3整除,故(1,1)R (6)不是. 因为A=1,2,3,4,5,而5不能整除2-5=-3,故(5,5)R,36,证明: 由题设 Rj=(x, y)|x=y(mod j) R