【文章內(nèi)容簡介】 僅當(dāng)RR?R[證] 1）必要性若R是自反的，則對任何x∈A，都有（x，x）∈R，但是IA={（x，x）|x∈A}，所以IA?R。充分性若IA?A則由IA={（x，x）|x∈A}，可知對任何x∈A，都有（x，x）∈R，所以R是自反的。2）必要性若R是反自反的，則對任何x∈A，都是（x，x）207。R，從而（x，x）∈R′，由IA={（x，x）|x∈A} 可知IA?R′。于是IA∩R?R′∩R=198。，另外198。?IA∩R，所以IA∩R=198。充分性若IA∩R=198。，則R是反自反的。否則，不是反自反的，那么應(yīng)存在某一x0∈A，使得（x0，x0）∈R。但是（x0，x0）∈IA，從而（x0，x0）198。這不可能，矛盾。3）必要性，若R是對稱的，則對任何（x，y）∈R，就有（y，x）∈R。于是根據(jù)逆關(guān)系的定義，可得（x，y）∈，于是R?；對任何（x，y）∈，由逆關(guān)系的定義，可得（y，x）∈R。再次利用R的對稱性有（y，x）∈R，于是?R；綜合兩方面，有R=。充分性若R= ，則對任何（x， y）∈R，由R=可得（x，y）∈。從而由逆關(guān)系的定義，可知（y，x）∈R這說明R是對稱的。4）必要性若R是反對稱的，則對任何（x，y）∈，即有（x， y）∈R及（x，y）∈，從逆關(guān)系的定義，就有（x， y）∈R及（y，x）∈R，因此，利用R的反對稱性，可得x=y。于是就有（x，y）=（x，x）∈IA，所以R∩?IA。充分性若R∩ ?IA，則對任何（x，y）∈R及（y，x）∈R，從逆關(guān)系的定義，可得（x，y）∈R及（x，y）∈，也即（x，y）∈R∩，利用R∩ =IA可得（x，y）∈IA，于是x=y。所以R是反對稱的。5）必要性若R是傳遞的，則對任何（x，y）RоR，由復(fù)合關(guān)系的定義可知，存在著y∈A，使（x，y）∈R且（y，y）∈R，從而利用R的傳遞性，可知（x，y）∈R。所以RоR?R。充分性RоR。從而利用RоR?R可得（x，y）∈R。所以R是傳遞的。證法二：1)222。):對任何x，x∈A222。(x,x)∈IA (IA是幺關(guān)系，因此是自反關(guān)系)222。(x,x)∈R (R是自反關(guān)系)所以 IA205。R ；220。):對任何x∈A，x∈A222。(x,x)∈IA (IA是幺關(guān)系，因此是自反關(guān)系)222。(x,x)∈R (因IA205。R)所以，R是自反關(guān)系；2)222。)首先 198。205。IA199。R ；其次，對任何x，y∈A，若(x,y)∈IA199。R222。(x,y)∈IA217。(x,y)∈R222。x=y217。(x,y)∈R (IA是幺關(guān)系，因此是自反關(guān)系)222。(x,x)∈R則與R是反自反關(guān)系，(x,x)207。R矛盾。故IA199。R205。198。 ；因此，由包含關(guān)系205。的反對稱性，可得 IA199。R=198。 ；220。):對任何x∈A，若(x,x)∈R222。(x,x)∈IA217。(x,x)∈R (IA是幺關(guān)系，因此是自反關(guān)系)222。(x,x)∈IA199。R222。(x,x)∈198。 (因IA199。R=198。)則與空集不含任何元素，(x,x)207。198。矛盾。故對任何x∈A，(x,x)207。R ；所以，R是反自反關(guān)系；3)222。)對任何x，y∈A(x,y)∈R219。(y,x)∈R (R是對稱關(guān)系)219。(x,y)∈所以，R=；220。):對任何x,y∈A(x,y)∈R222。(x,y)∈ (R=)222。(y,x)∈R所以，R是對稱的；4)222。)對任何x，y∈A(x,y)∈R199。222。(x,y)∈R217。(x,y)∈222。(x,y)∈R217。(y,x)∈R222。x=y (R是反對稱關(guān)系)222。 (x,y)∈IA (IA是自反關(guān)系)所以，R199。205。IA ；220。):對任何x,y∈A(x,y)∈R222。(x,y)∈ (R=)222。(y,x)∈R所以，R是對稱的；13．設(shè)A、B為有窮集合，R，S?AB，MR=（xij）mn，MS=（yij）mn1）為了R?S，必須且只須ij（xij≤ yij）2）設(shè)MR∪S=（Zij）mn，那么Zij=xijVyij，I=1，2……，m，j=1，2，……n.3）設(shè)MR∩S=（tij）mn，那么tij=xij^yij i=1，2，……m；j=1，2，……，n.[證] 由于A、B是有窮集合，不妨設(shè)A={a1，a2……，am}，B={b1，b2，……，bn}1）必要性若R?S，則對任何i∈{1，2，……，m}，對任何j∈{1，2，……n}，若（ai，bj）∈R，則R的關(guān)系矩陣MR=（xij）mn中第I行第j列元素xij=1，根據(jù)R?S，可得（ai，bj）∈S，從而得S的關(guān)系矩陣MS=（yij）mn中第I行第j列元素yij=1，由于是1≤1故此xij≤yij；若（ai，bj）207。R，則R的關(guān)系矩陣MR=（xij）mn中第i行第j列元素xij=0，因此由S的關(guān)系矩陣MS=（yij）mn中第j列元素yij≥0，可得xij≤yij?？傊?，有（i）(j)（xij≤yij）。2）充分性若（i）(j)（xij≤yij），則對任何（ai，bj）∈R，就有R的關(guān)系矩陣MR=（xij）mn中第i行第j列元素xij=1，由于xij≤yij，所以yij≥1，故此yij≥1這說明S的關(guān)系矩陣MS=（yij）mn中第i行第j列元素yij為1，因此必有（ai，bj）∈S，所以R?S。2）對任何i∈{1，2，……，m}，對任何j∈{1，2，……，n}若Zij=1，則（ai，bj）∈R∪S，故此（ai，bj）∈R或者（ai，bj）∈S，于是xij=1或者yij=1。從而bj）?S，于是xij=0且yij=0。從而xij∨yij=0。因而Zij=xij∨yij=0；綜合上述兩種情況，就有zji=xij∨yij，i=1，2，……，m，j=1,2,……n。3）對任何i∈{1，2，……m}，對任何j∈{1，2，……，n}。若tij=1，則（ai，bj）∈R∩S，故此（ai，bj）∈S且（ai，bj）∈S，于是xij=1，且yij=1從而xij∧yij=1。因而tij=xij∧yij=1；若tij=0，則（ai，bj）?R∩S，故此（ai，bj）?S，于是xij=0或者yij=0，從而xij∧yij=0。因而tij=xij∧yij=0。綜合上述兩種情況，就有tij=xij∧yij，i=1，2，……，m，j=1，2，……，n。14．設(shè)A={1，2，3，4}，R1，R2為A上的關(guān)系，R1={（1，1），（1，2），（2，4）}，R2={（1，4），（2，3），（2，4），（3，2）}，求R1оR2，R2оR1，R1оR2оR1[解] ，1） 無論從復(fù)合關(guān)系圖還是從復(fù)合關(guān)系矩陣都可得R1оR2={（1，3），（1，4）} R1 R22）無論從復(fù)合關(guān)系圖還是從復(fù)合關(guān)系矩陣都可得R2оR1={（3，4）} R2 R13）無論從復(fù)合關(guān)系圖還是從復(fù)合關(guān)系矩陣都可得R1оR2оR1=198。 4）無論從復(fù)合關(guān)系圖還是從復(fù)合關(guān)系矩陣都可得R1оR1о={（1，1），（1，2），（1，4）} R1 R1 R115）設(shè)R1，R2，R3是A上的二元關(guān)系，如果R1?R2，證明1）R1R3?R2R3 2）R3R1?R3R2[證明] 1）對任何（x，y）∈R1R3，由復(fù)合關(guān)系之定義，必存在z∈A，使得（x，z）∈R1且（z，y）∈R3，利用R1?R2可知（x，z）∈R2且（z，y）∈R3，再次利用復(fù)合關(guān)系之定義，有（x，y）∈R2R3。所以R1R3?R2R3。2）對任何（x，y）∈R3R1，由復(fù)合關(guān)系之定義，必有z∈A，使得（x，z）∈R3且（z，y）∈R1，再由復(fù)合關(guān)系之定義，有（x，y）∈R3R2。所以R3R1?R3R2。16．設(shè)A是有限個元素的集合，在A上確定兩個不同的關(guān)系R1和R2，使得=R1，=R2 因為，令R1=198。，則R1R1=198。，故此=R1=198。令R2=AA，則=R2R2?AA=R2，故需證明R2?R2οR2=。為此，對任何x，y∈A，（x，y）∈AA=R2，一定存在著z∈A（至少有z=x或z=y存在），使（x，z）∈AA=R2且（z，y）∈AA=R2，故此（x，y）R2R2=，所以R2?R2R2=。于是=R2=AA。2）由于A是有限個元素的集合，是不心設(shè)A={a1，a2，……an}令R1={（ai，aj）|ai∈A∧aj∈A∧|≤i≤n∧|≤j≤n|}R2={（an，an）∪R1} 則R1R2，即R1與R1是不同的關(guān)系。我們來證明=R1，=R2，（a）先征=R1若（ai，aj）∈R1，則由R1的定義必定1≤i≤n，1≤i≤n1，并且一定存在著1≤k≤n1（至少有k=j存在），使（ai，ak）∈R1且（ak，aj）∈R1，從而（ai，aj）∈R1R1=。故此R1?。若（ai，aj）∈= R1R1，則存在著k，1≤k≤n1，使（ai，ak）∈R1且（ak，aj）∈R1，于是由R1的定義，必有1≤i≤n，1≤j≤n1，從而根據(jù)R1的定義，有（ai，aj）∈R1。故此= R1綜合兩個方面，可得= R1。（b）次證=R2若（ai，aj）∈R2，則由R2的定義，要么1≤i≤n，1≤j≤n1，要么I=n，j=n 若1≤i≤n，1≤j≤n1，則一定存在著1≤k≤n1（至少有k=j存在），使（ai，ak）∈R2且（ak，aj）∈R2，從而（ai，aj）∈R2οR2=；若i=n，j=n，則（ai，aj）=（an，an）∈R2，那么（an，an）∈R2，所以（ai，aj）=（an，an）∈R2οR2=因此R2=。若（ai，aj）∈= R2οR2，則存在著k，使（ai，ak）∈R2且（ak， ai）∈R2，于是由R2的定義，有k=n或者1≤k≤n1。若k=n，則由（ai，ak）∈R2必有I=n，所以無論1≤j≤n1還是j=n，由R2的定義，有（ai，aj）=（an，aj）∈R2；若1≤k≤n1，則由（ai，ak）∈R2必有1≤j≤n1故此（ai，aj）∈R2總之證得= R2，綜合兩方面，我們證明了= R2。17．設(shè)R是集合A上的反對稱關(guān)系，|A|=h，指了在R∩的關(guān)系矩陣中有多少個非零值？[解] 由第12題的4） R是反對稱關(guān)系當(dāng)且反當(dāng)R∩?IA，及|A|=n可知，在R∩ 的關(guān)系矩陣中非零值最多不超過n個。18．設(shè)R1和R2是集合A上的關(guān)系，判斷下列命題的真假性，并闡明理由。1） 如果R1和R2都是自反的，那么R1R2是自反的。2） 如果R1和R2都是反自反的，那未R1R2是反自反的。3） 如果R1和R2都是對稱的，那末R1R2是對稱的。4） 如果R1和R2都是反對稱的，那末R1R2是反對稱的。5） 如果R1和R2都是傳遞的，那末R1R2是傳遞的。[解] 1）真。由于R1和R2和R2都是自反的，因而對任何，都有（x，x）∈R1，（x，x）∈R2。因此，對任何x∈A，都有（x，x）∈ R1R2。所以R1R2是自反的。2）假。令A(yù)={a，b}，R1={（a，b）}，R2={b，a}。那么R1R2={（a，a）}，它就不是A上的反自反關(guān)系。3）假。令A(yù)={a，b，c}，R1={（a，b），（b，a）}，R2={（b，c），（c，b）}。那末R1R2={（a，c）}，就不是A的對稱關(guān)系。4）假。令A(yù)={a，b，c，d}，R1={（a，c），（b，c）}R2={（c，b），（d，a）}易證R1，R2都是反對稱關(guān)系。但是R1R2={（a，b），（b，a）}就不是A上的反對稱關(guān)系。5）假。令A(yù)={a，b，c}，R1={（a，c），（b，a），（b，c）}，R2={（c，b），（a，c），（a，b）}，易證R1和R2都是傳遞關(guān)系，但R1R2={（a，b），（b，b），（b，c）}就不是A上的傳遞關(guān)系。19．設(shè)A={1，2，3，4，5}，R?AA，R={（1，2），（2，3），（2，5），（3，4），（4，3），（5，5）}用作圖方法矩陣運算的方法求r（R），s（R），t（R）。[解] 1）作圖法：R的關(guān)系圖 （R）的關(guān)系圖51234123455143253241 S（R）的關(guān)系圖 t（R）的關(guān)系圖因此：r（R）={（1，1），（1，2），（2，2），（2，3），（2，5），（3，3），（3，4），（4，3），（4，4），（5，5）}s（R）={（1，2），（2，1），（2，3），（2，5），（3，2），（3，4），（4，3），（5，2），（5，5）}t（R）={（1，2），（1，3），（1，4），（1，5），（2，3），（2，4），（2，5），（3，3），（3，4），（4，3），（4，4），（5，5）}2）矩陣運算法：Mr（R）==MS（R）====MRοR=MRMR===MR=因此r（R），s（R），t（R）與1）作圖法一致。20．設(shè)R?AA，證明1）（R+