【正文】 ?（R*）*；另一方面，由于R*是R的自反傳遞閉包，故此R*是自反的傳遞的。[解] 1）由于（1，2）∈R且（2，4）R但（1，4）? R，這說明R不是傳遞的。22．設(shè)A={1，2，3，4……，9}，定義AA上的關(guān)系如下：（a，b）R（c，d）∷ a+d=b+c1） 證明R是AA上的等價關(guān)系；2） 求[（2，5）]R；3） R?AA對嗎？請闡明理由。綜合（a）、（b）、（c）、說明R是AA上的等價關(guān)系。如果R在A上是對稱的，傳遞的，下面的推導(dǎo)說明R在A上是自反的：對任意的a，b∈A，由于R是對稱的，有： aRb222。上述推導(dǎo)正確嗎？請闡明理由。因而在一個空集上的空關(guān)系都是平凡的對稱和可傳遞，但不是自反的。（c）是傳遞的對任何（a，b）∈及（b，c）∈，由逆關(guān)系的定義，有（b，a）∈R及（c，b）∈R，根據(jù)R的傳遞性，可得（c，a）∈R，再次由逆關(guān)系的定義，就有（a，c）∈。(a,a)206。A，(a,b)206。(a,b)206。A，(a,b)206。((b,a)206。((c,b)206。的交換律)222。 (R是對稱的)所以，是對稱的；綜合（a）、（b）、（c），可知是A上的等價關(guān)系。綜合（a），（b），（c），可知R1∩R2是等價關(guān)系。R1217。R1199。R1199。(a,b)206。(b,a)206。R2所以，R1199。R2217。((a,b)206。 ((b,c)206。((a,b)206。 ((a,b)206。的結(jié)合律、交換律)222。R2 (R1，R2都是傳遞的)222。R2是對稱的；綜合（a）、（b）、（c），可知R1199。但是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。1） 有多少個元素在A上的最大的等價關(guān)系中？2） A上的最大的等價關(guān)系的秩是多少？3） 有多少個元素在A上的最小的等價關(guān)系中？4） A上的最小的等價關(guān)系的秩是多少？[答] 1）A上最大的等價關(guān)系是全關(guān)系R1=AA={（a，b）|a∈A∧b∈A}因此有n2個元素在A上的最大的等價關(guān)系R1中，因為所有n2個二元組都在R1=AA中。 4）A上的最小的等價關(guān)系的秩是n，因為么關(guān)系的每一個元素都自成一個等價塊，每一等價塊中也只有一個元素。就不是A上的等價關(guān)系，因為空關(guān)系不是自反的。證法一：因R1是等價關(guān)系，因而R1是傳遞的，故此由第12題之5）有= R1R1?R1。222。(c,b)206。R1) (R1是傳遞的)222。R1 ；另一方面，對任何a，b206。R1217。所以，R1205。R1\R2={（a，b），（b，a），（b，c），（c，b）}r（R1\R2）={（a，a），（b，b），（c，c），（a，b），（b，a），（b，c），（c，b）}因此r（R1\R2）不是A上的等價關(guān)系，因為r（R1\R2）不是傳遞的，（a，b）∈r（R1\R2）且（b，c）∈r（R1\R2），但是（a，c）?r（R1\R2）。[解] A上的等價關(guān)系共有14個。30．設(shè)A={1，2，3，4，5，6}，確定A上的等價關(guān)系R，使此R能產(chǎn)生劃分{{1，2，3，}，{4}，{5，6}}123564[解] 這樣的R={（1，1），（2，2），（3，3），（1，2），（2，1），（1，3），（3，1），（2，3），（3，2），（4，4），（5，5），（6，6），（5，6），（6，5）} R的關(guān)系圖31．設(shè)R是集合A上的關(guān)系R是循環(huán)∷＝（a∈A）（b∈A）（c∈A）（aRb∧bRc222。（b）R是對稱的對任何（a，b）∈R，由于R是自反的，所以（b，b）∈R，再根據(jù)R是循環(huán)的可得（b，a）∈R。因R是等價關(guān)系，故R是自反的。)：（a）R是自反的：已知；（b）R是對稱的：對任何a，b206。R217。R (R是循環(huán)的)所以，R是對稱的；（c）R是傳遞的：對任何a，b，c206。R222。R (R是對稱的)所以，R是傳遞的；綜合（a），（b），（c）可知R是等價關(guān)系；220。(b,c)206。(c,a)206。就不是A的劃分，因為{a}∩{a，b}={a}≠198。 3）可能。因為∪{c}={b，c}≠A。33．對下列集合上的整除關(guān)系畫出哈斯圖，并對3）中的子集{2，3，6}，{2，4，6}，{4，8，12}找出最大元素，最小元素，極大元素，極小元素，上確界，下確界。[解] A={0，1，2，3，4，5，6}第34題?={（0，0），（0，1），（0，2），（0，3），（0，4），（0，5），（0，6），（1，1），92，20，（2，5），（3，3），（3，5），（4，4），（4，6），（5，5），（6，6）}第34題35．設(shè)R是集合X上的半序關(guān)系，A205。 （a）R1是自反的對任何a∈A，由于A205。證法二：令R1=R199。A)205。A，因此R1是A上的關(guān)系。R217。X)222。A)222。R1217。R199。R199。R217。((b,a)206。A)222。R)217。(b,a)206。((a,b)206。q222。R1217。R199。R199。R217。((b,c)206。A)222。R)217。(b,c)206。((a,c)206。A (R是傳遞的，全關(guān)系A(chǔ)180。(A180。36．設(shè)（A，?1）和（A，?2）是兩個半序集合，定義AB上的關(guān)系?3如下：對于a1，a2∈A，b2∈B（a1，b1），（a2，b2）∈?3219。（c）?3是傳遞的對任何（（a1，b1），（a2，b2））∈?3及（（a2，b2），（a3，b3）））∈?3，由?3的定義，可知（a1，a2）∈?1且（a2，a3）∈?1及（b1，b2）∈?2且（b2，b3）∈?2。A180。b206。(b,b)206。A180。?3222。?2)217。?2) (?3的定義)222。?1)217。?2) (217。(a,b)=(c,d)所以，?3是反對稱的；③?3是傳遞的對任何(a,b)，(c,d)，(e,f)206。((c,d), (e,f))206。(b,d)206。(d,f)206。(c,e)206。(d,f)206。?1217。?3 (?3的定義)所以，?3是傳遞的；綜合①、②、③，可知?3是A180。只有一種，那就是A上的幺關(guān)系IA，它即是等價關(guān)系，又是半序關(guān)系。則一方面，對任何元素a,b206。R217。(a,b)206。IA222。38．對于下列每一種情況，舉出有限集合和無限集合的例子各一個。）為半序集，其中子集B1={{c}，{a，b}}B2={，{a，c}}等均沒有最大元素；（b）半序集（N，≤）的子集B1={x|x=2n∧n∈N} B2={P|P∈N∧P為素數(shù)}等均沒有最。1）的（a）的Hasse圖{a，b，c}{a，c}{a，b}{b,c}{c}{a}198。R (R的自反性)所以，IA205。IA；另一方面，對任何元素a206。R (R的對稱性)222。R222。這個矛盾說明同時為等價關(guān)系和半序關(guān)系的R只能是幺關(guān)系IA。37．對于非空集合A，是否存在這樣的關(guān)系R，它即是等價關(guān)系又是半序關(guān)系？若有，請舉出例子。?2 (?1，?2都是反對稱的)222。的結(jié)合律、交換律)222。((b,d)206。((a,c)206。((c,e)206。((a,c)206。B((a,b), (c,d))206。a=c217。?2217。?1217。?1217。?1217。?3217。((a,b),(a,b))206。(a,a)206。a206。再次利用?3的定義，可得（（a1，b1），（a3，b3）））∈?3。[證].證法一：對于任何（a，b）∈AB，就有a∈A及b∈B，從而利用?1及的自反性，可得 （a，a）∈?1且（b，b）∈?2因此由?3的定義，可知（（a，b），（a，b））∈?3。(a,c)206。(a,c)206。(a,c)206。A) (217。A180。R217。(b,c)206。A180。A) (R1的定義)222。A)217。R1222。a=b (R是反對稱的)所以，R1是反對稱的；③R1是傳遞的對任何a,b,c206。(b,a)206。A) (217。A180。R217。(b,a)206。A180。A) (R1的定義)222。A)217。R1222。R1 (R1的定義)所以，R1是自反的；②R1是反對稱的對任何a,b206。R199。A180。A222。A，所以R1205。A)，由于R199。（b）R1是反對稱的對任何（a，a）∈R1且（b，a）∈R1，由R1= R∩（AA），故有（a，b）∈R且（b，a）∈R，以及a，b，c∈A。[證].證法一：令R1=R∩（AA），則R1204。②{2，4，6}的極大元素為4和6；最小素為2；極小元素也為2；上確界為12；下確界為2；③{4，8，12}的極大元素為8，12；最小元素為4；極小元素也為4；下確界為4；沒有最大元素；沒有上確界。因為（∏1∩（∏2\∏1））∪∏1=198。則∏1\∏2=∏1是A的劃分；如果∏1∩∏2≠198。如果∏1=∏2，則∏1∩∏2是A的劃分；如果，∏1≠∏2，則∏1∩∏2不是A的劃分；例如A={a，b}，∏1={{a}，}，∏2={{a，b}}，∏1∩∏2=198。1）∏1∪∏22）∏1∩∏23）∏1\∏24)（∏1∩（∏2\∏1））∪∏1[解] 1）可能。(a,c)206。A，(a,b)206。R (R是循環(huán)的)222。R217。R (R是自反的)222。R222。由于R是對稱的，（c，a）∈R。充分性若R是等價關(guān)系，我們來證R是自反的和循環(huán)的。[證] 證法一：必要性若R是自反的和循環(huán)的，我們來證R是等價關(guān)系，為此證明（a）R是自反的。{{a}，，{c}，nhcuj7d3}型劃分，一個；{{a，b}，{c}，nhcuj7d3}型劃分，六個；{{a，b，}，{c，d}}型劃分，三個；{{a，b，c}，nhcuj7d3}型劃分，四個；{{a，b，c，d}}型劃分，一個。令A(yù)={a，b，c}，R1={（a，a），（b，b），（c，c），（a，b），（b，a）}，R2={（a，a），（b，b），（c，c），（a，b），（b，a），（b，c），（c，b），（a，c）}不上的等價關(guān)系，因為R1R2不對稱，（a，c）∈R1R2，但（c，a）?R1R2。設(shè)A={a，b，c}，R1={（a，a），（b，b），（c，c），（a，b），（b，a），（a，c）（c，a），（b，c），（c，b）}。R1) (R1是自反的)222。R1222。R1(帶量詞的基本邏輯等價式：($x)p219。($c206。A)((a,c)206。證法二：一方面，對任何a，b206。設(shè)A={（a，b）}并且R1={（a，a），（b，b），（a，b），（b，a）}，R2={（a，a），（b，b）}，則R1，R2都是A上的等價關(guān)系，但是，R1\R2={（a，b），（b，a）}就不是A上的等價關(guān)系，因為R1\R2不自反。1) AA\R12) R1\R23) 4）r（R1\R2） （R1\R2的自反閉包）5）R1R2[解] 1）不是。這是因為A中任何兩個元素都有全關(guān)系R1=AA，因此R1的等價塊包含了A的所有元素，A的所有元素都在同一個等價塊中。因為任何少于3個元素的集合上的自反，對稱關(guān)系一定是傳遞的！26．設(shè)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)過適當(dāng)?shù)木仃嚪謮K，MR的分塊矩陣將成為準(zhǔn)對角陣，準(zhǔn)對角陣的對角線上的每一塊都是一個全1方陣，它正好對應(yīng)于等價關(guān)系R的一個等價塊。2）兩個自反的（對稱的）關(guān)系的并將是自反的（對稱的），但是，兩個傳遞關(guān)系的并卻未必是傳遞的。R1199。R1217。(b,c)206。(b,c)206。(b,c)206。(a,b)206。R1199。A，(a,b)206。(b,a)206。(b,a)206。(a,b)206。R2是自反的；（b）R1∩R2是對稱的：對任何a，b206。R2 (R1，R2都是自反的)222。A222。[證] 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。R (R是傳遞的)222。(b,a)206。(c,b)206。(b,c)206。(b,a)206。(b,a)206。(a,a)206。證法二：（a）是自反的：對任何a，a206。24．設(shè)R是集合A上的等價關(guān)系，證明也是集合A上的等價關(guān)系。推殖民