【正文】 值？[解] 由第12題的4） R是反對稱關(guān)系當且反當R∩?IA，及|A|=n可知，在R∩ 的關(guān)系矩陣中非零值最多不超過n個。由于R1和R2和R2都是自反的，因而對任何，都有（x，x）∈R1，（x，x）∈R2。那末R1R2={（a，c）}，就不是A的對稱關(guān)系。20．設R?AA，證明1）（R+）++R+2）=R*[證明] 1）一方面，由于（R+）+是R+的傳遞閉包，所以R+?（R+）+；另一方面，由于R+是R的傳遞閉包，故此R+是傳遞的?，F(xiàn)在來R+R2={（1，4），（2，3），（3，3），（3，4），}（4，3），（4，4）}R3={（1，3），（2，3），（2，4），（3，3），（3，4），（4，3），（4，4）}R4={（1，3），（1，4），（2，3），（2，4），（3，3），（3，4），（4，3），（4，4）}故此R1=R+=R∪R2∪R3∪R4={（1，2），（1，3），（1，4），（2，3），（2，4），（3，3），（3，4），（4，3）（4，4）}（因為|A|=4有限）其關(guān)系圖如下：1124311243R的關(guān)系圖 R1的關(guān)系圖3）能。因為R是AA上的關(guān)系，所以R?（AA）（AA）=。推殖民地的謬論誤在于假設A的每個元素都由R關(guān)聯(lián)著A的某一別的元素。證法二：（a）是自反的：對任何a，a206。(b,a)206。(b,c)206。(b,a)206。[證] 1）證法一：（a）R1∩R2是自反的對任何a∈A，由于R1，R2都是A上的自反關(guān)系，所以（a，a）∈R1（a，a）∈R2，因此（a，a）∈R1∩R2（b）R1∩R2是對稱的對任何的（a，b）∈R1∩R2，就有（a，b）∈R1且（a，b）∈R2，由R1，R2都是A上的對稱關(guān)系，所以（a，b）∈R1且（b，a）∈R2，所以（b，a）∈R1∩R2。R2 (R1，R2都是自反的)222。(a,b)206。(b,a)206。R1199。(b,c)206。(b,c)206。R1199。因為任何少于3個元素的集合上的自反，對稱關(guān)系一定是傳遞的！26．設R是A上的等價關(guān)系，將A的元素按R的等價類順序排列，請指出此等價關(guān)系R的關(guān)系矩陣MR有何特征？[解] 將A的元素按其上的等價關(guān)系R的等價類順序排列，這樣產(chǎn)生的等價關(guān)系R的關(guān)系矩陣MR，經(jīng)過適當?shù)木仃嚪謮K，MR的分塊矩陣將成為準對角陣，準對角陣的對角線上的每一塊都是一個全1方陣，它正好對應于等價關(guān)系R的一個等價塊。1) AA\R12) R1\R23) 4）r（R1\R2） （R1\R2的自反閉包）5）R1R2[解] 1）不是。證法二：一方面，對任何a，b206。($c206。R1222。設A={a，b，c}，R1={（a，a），（b，b），（c，c），（a，b），（b，a），（a，c）（c，a），（b，c），（c，b）}。{{a}，，{c}，nhcuj7d3}型劃分，一個；{{a，b}，{c}，nhcuj7d3}型劃分，六個；{{a，b，}，{c，d}}型劃分，三個；{{a，b，c}，nhcuj7d3}型劃分，四個；{{a，b，c，d}}型劃分，一個。充分性若R是等價關(guān)系，我們來證R是自反的和循環(huán)的。R222。R217。A，(a,b)206。1）∏1∪∏22）∏1∩∏23）∏1\∏24)（∏1∩（∏2\∏1））∪∏1[解] 1）可能。則∏1\∏2=∏1是A的劃分；如果∏1∩∏2≠198。②{2，4，6}的極大元素為4和6；最小素為2；極小元素也為2；上確界為12；下確界為2；③{4，8，12}的極大元素為8，12；最小元素為4；極小元素也為4；下確界為4；沒有最大元素；沒有上確界。（b）R1是反對稱的對任何（a，a）∈R1且（b，a）∈R1，由R1= R∩（AA），故有（a，b）∈R且（b，a）∈R，以及a，b，c∈A。A，所以R1205。A180。R1 (R1的定義)所以，R1是自反的；②R1是反對稱的對任何a,b206。A)217。A180。R217。A) (217。a=b (R是反對稱的)所以，R1是反對稱的；③R1是傳遞的對任何a,b,c206。A)217。A180。R217。A) (217。(a,c)206。[證].證法一：對于任何（a，b）∈AB，就有a∈A及b∈B，從而利用?1及的自反性，可得 （a，a）∈?1且（b，b）∈?2因此由?3的定義，可知（（a，b），（a，b））∈?3。a206。((a,b),(a,b))206。?1217。?1217。a=c217。((a,c)206。((a,c)206。的結(jié)合律、交換律)222。37．對于非空集合A，是否存在這樣的關(guān)系R，它即是等價關(guān)系又是半序關(guān)系？若有，請舉出例子。R222。IA；另一方面，對任何元素a206。1）的（a）的Hasse圖{a，b，c}{a，c}{a，b}{b,c}{c}{a}198。38．對于下列每一種情況，舉出有限集合和無限集合的例子各一個。(a,b)206。則一方面，對任何元素a,b206。?3 (?3的定義)所以，?3是傳遞的；綜合①、②、③，可知?3是A180。(d,f)206。(d,f)206。((c,d), (e,f))206。?2) (217。?2) (?3的定義)222。?3222。(b,b)206。A180。36．設（A，?1）和（A，?2）是兩個半序集合，定義AB上的關(guān)系?3如下：對于a1，a2∈A，b2∈B（a1，b1），（a2，b2）∈?3219。A (R是傳遞的，全關(guān)系A180。(b,c)206。A)222。R217。R199。q222。(b,a)206。A)222。R217。R199。A)222。R217。A)205。 （a）R1是自反的對任何a∈A，由于A205。33．對下列集合上的整除關(guān)系畫出哈斯圖，并對3）中的子集{2，3，6}，{2，4，6}，{4，8，12}找出最大元素，最小元素，極大元素，極小元素，上確界，下確界。 3）可能。(c,a)206。R (R是對稱的)所以，R是傳遞的；綜合（a），（b），（c）可知R是等價關(guān)系；220。R (R是循環(huán)的)所以，R是對稱的；（c）R是傳遞的：對任何a，b，c206。)：（a）R是自反的：已知；（b）R是對稱的：對任何a，b206。（b）R是對稱的對任何（a，b）∈R，由于R是自反的，所以（b，b）∈R，再根據(jù)R是循環(huán)的可得（b，a）∈R。[解] A上的等價關(guān)系共有14個。所以，R1205。R1 ；另一方面，對任何a，b206。(c,b)206。證法一：因R1是等價關(guān)系，因而R1是傳遞的，故此由第12題之5）有= R1R1?R1。 4）A上的最小的等價關(guān)系的秩是n，因為么關(guān)系的每一個元素都自成一個等價塊，每一等價塊中也只有一個元素。但是abcabcabcR1∪R2={（a，a），（b，b），（c，c），（a，b），（b，a）（b，c），（c，b）}都不是A上的等價關(guān)系，因為R1∪R2不傳遞：（a，b）∈R1∪R2且（bc，但（a，c）?R1∪R2；同樣（c，b）∈R1∪R2且（b，a）∈R1∪R2，但（c，a）?R1∪R2。R2 (R1，R2都是傳遞的)222。 ((a,b)206。 ((b,c)206。R2217。(b,a)206。R1199。R1217。 (R是對稱的)所以，是對稱的；綜合（a）、（b）、（c），可知是A上的等價關(guān)系。((c,b)206。A，(a,b)206。A，(a,b)206。（c）是傳遞的對任何（a，b）∈及（b，c）∈，由逆關(guān)系的定義，有（b，a）∈R及（c，b）∈R，根據(jù)R的傳遞性，可得（c，a）∈R，再次由逆關(guān)系的定義，就有（a，c）∈。上述推導正確嗎？請闡明理由。綜合（a）、（b）、（c）、說明R是AA上的等價關(guān)系。[解] 1）由于（1，2）∈R且（2，4）R但（1，4）? R，這說明R不是傳遞的。19．設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）。3）假。5） 如果R1和R2都是傳遞的，那末R1R2是傳遞的。若（ai，aj）∈= R2οR2，則存在著k，使（ai，ak）∈R2且（ak， ai）∈R2，于是由R2的定義，有k=n或者1≤k≤n1。為此，對任何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=。 4）無論從復合關(guān)系圖還是從復合關(guān)系矩陣都可得R1оR1о={（1，1），（1，2），（1，4）} R1 R1 R115）設R1，R2，R3是A上的二元關(guān)系，如果R1?R2，證明1）R1R3?R2R3 2）R3R1?R3R2[證明] 1）對任何（x，y）∈R1R3，由復合關(guān)系之定義，必存在z∈A，使得（x，z）∈R1且（z，y）∈R3，利用R1?R2可知（x，z）∈R2且（z，y）∈R3，再次利用復合關(guān)系之定義，有（x，y）∈R2R3。從而xij∨yij=0。):對任何x,y∈A(x,y)∈R222。(x,y)∈R217。)對任何x，y∈A(x,y)∈R219。(x,x)∈198。的反對稱性，可得 IA199。x=y217。R)所以，R是自反關(guān)系；2)222。證法二：1)222。于是就有（x，y）=（x，x）∈IA，所以R∩?IA。但是（x0，x0）∈IA，從而（x0，x0）198。2）必要性若R是反自反的，則對任何x∈A，都是（x，x）207。性質(zhì)關(guān)系自反的反自反的對稱的反對稱的傳遞的相等關(guān)系YNYYY≤關(guān)系YNNYY＜關(guān)系NYNYY全域關(guān)系YNYNY空關(guān)系NYYYY4） R4是反對稱的，循環(huán)的。[解]：1 0 0 23 0 0 4 1） R1是反對稱的，傳遞的。B）C=（AC）197。所以x∈A\B，或x∈B\A，并且y∈C，故此 x∈A197。對任一（x，y）∈（AC）197。B，或者x207。的結(jié)合律)222。C) (217。的分配律)222。y∈C217。BC222。即x∈A\B，y∈C，故此（x，y）∈（A\B）C。證明如下：對任一（x，y）∈（A\B）C，有x∈A，x207。B）（C197。B）（C197。所以（A197。BD綜合這兩方面，有（A\B）（C\D）205。事實上有：（A\B）（C\D）205。所以（A∪B）（C∪D）=（AC）∪（BD）不成立。 1）（A∪B）（C∪D）=（AC）∪（BD） 2）（A\B）（C\D）=（AC）\（BD） 3）（A197。y∈C)217。證法二：（邏輯法）對任何x,y(x,y)∈(A∩B)(C∩D)222。因而（x，y）∈AC，且（x，y）∈BD，所以（x，y）∈（AC）∩（BD）。B且B205。∨B=198。則存在元素x∈AA，故有y1，y2∈A，使x=（y1，y2），從而y1，y2∈AA，故此有y1，y2，y3，y4，使y1=（y1，y2），y2=（y3，y4），……。A∩B注：自然數(shù)集N取為{1，2，3，……，n，……}習題二（第二章 關(guān)系）1．設A={1，2，3，}，B={a，b}求 1）AB 2）BA 3）BB 4）2BB[解] 1）AB={（1，a），（1，b），（2，a），（2，a），（3，a），（3，b）}2）BA={（a，1），（a，2），（a，3），（b，1），（b，2），（b，3）}3）BB={（a，a），（a，b），（b，a），（b，b）}4）2B={198。Ｃ）０ ０ ００００００ ０ １０１１１０ １ ０１１１１０ １ １１０００１ ０ ０１１０１１ ０ １１０１０１ １０００１０１ １ １０１０１成員表中運算結(jié)果197。C=A（B197。則A197。5） 根據(jù)定理6的1）有A197。因此當A\B=B\A時，有A=B。則有元素a∈A\B，那么，a∈A，而由假設A\B=B\A。由假設可知A=A\198。顯然有A∪B=A∪C，但B≠C。B=B∪198。A∩B′=X′ （零壹律）(3)再證A∩B′=198。A′∪B，即X205。X且B205。B222。9. 設A、B是Ⅹ全集的子集，證明： A205。由為x∈A，x207。所以，x∈（A\B）\C。反之，對任x∈（A\C）\（B\C），可知x∈A\C，x207。2）方法一：（A\B）\C =A\（B∪C） （根據(jù)1）） =A\（C∪B） （并運算交換律） =A\（（C∪B）∩Ⅹ）