離散數(shù)學(xué)-二元關(guān)系課后練習(xí)習(xí)題及答案

1、第七章作業(yè)評(píng)分要求：1 .合計(jì)100分2 .給出每小題得分(注意：寫出扣分理由).3 .總得分在采分點(diǎn)1處正確設(shè)置.1設(shè)R=<x,y>|x,yCN且x+3y=12.【本題合計(jì)10分】(1)求R的集合表達(dá)式(列元素法);(2)求domR,ranR;(3)求R?R;(4)求R?2,3,4,6;(5)求R3;解(1) R=<0,4>,<3,3>,<6,2>,<9,1>,<12,0>【2分(2) domR=0,3,6,9,12,ranR=0,1,2,3,4【2分】R?R=<3,3>,<0,4>【2分(4)R

2、?2,3,4,6=<3,3>,<6,2>【2分R3=3【2分】2設(shè)R,F,G為A上的二元關(guān)系.證明：(1)R?(FUG)=R?FUR?G(2)R?(FnG)?R?nR?G(3)R?(F?G)=(R?F)?G.【本題合計(jì)18分：每小題6分，證明格式正確得3分，錯(cuò)一步扣1分】證明？<x,y>,<x,y>£R?(FUG)?t(xRtAt(FUG)y)復(fù)合定義?t(xRtA(tFyVtGy)U定義?t(xRtAtFy)V(xRtAtGy)八對(duì)V分配律?t(xRtAtFy)V?t(xRtAtGy)?對(duì)V分配律?x(R?F)yVx(R?G)y復(fù)合定

3、義?x(R?FUR?G)yU定義得證(2)?<x,y>,x(R?(FAG)y?t(xRtAt(FnG)y)復(fù)合定義?t(xRtA(tFyAtGy)n定義?t(xRtAtFy)A(xRtAtGy)A哥等律，A交換律，A結(jié)合律?t(xRtAtFy)A?t(xRtAtGy)補(bǔ)充的量詞推理定律?x(R?F)yAx(R?G)y復(fù)合定義?x(R?FUR?G)yU定義得證？<x,y>,<x,y>£R?(F?G)?s(<x,s>CRA<s,y>C(F?G)覺義?s(<x,s>CRA?t(<s,t>FA<t,y&

4、gt;6G)出義?s?t(<x,s>CRA<s,t>CFA<t,y>CG)轄域擴(kuò)張公式?t?s(<x,s>CRA<s,t>CF)A<t,y>CG)存在量詞交換?t(?s(<x,s>RA<s,t>CF)A<t,y>CG)轄域收縮公式?t(<x,t>(R?F)A<t,y>£G)復(fù)合定義?<x,y>6(R?F)?G復(fù)合定義得證3設(shè)F=<x,y>|xy+2>0Axy2<0是實(shí)數(shù)集R上的二元關(guān)系，問F具有什么性質(zhì)并說(shuō)明理由.【本

5、題合計(jì)10分：每種性質(zhì)2分-答對(duì)得1分，正確說(shuō)明理由得1分】解F=<x,y>|x-y+2>0Ax-y-2<0=<x,y>|-2<x-y<2自反性：？xer,<x,x>ef顯然.對(duì)稱性：?<x,y>,<x,y>CF?2<xy<2?2<yx<2?<y,x>CF.不具有反自反性：反例<2,2>CF不具有反對(duì)稱性：反例<2,3>,<3,2>F,顯然2W3不具有彳遞性：反例<2,3.5>,<3.5,5>F,但<2,5&g

6、t;不屬于F.4設(shè)A=a,b,c,R=<a,b>,<a,c>,(1)給出R的關(guān)系矩陣；(2)說(shuō)明R具有的性質(zhì)(用關(guān)系矩陣的判定方法說(shuō)明理由)【本題合計(jì)12分：第(1)小題2分；第(2)小題10分-答對(duì)性質(zhì)得1分，說(shuō)明理由得1分】解(1)R的關(guān)系矩陣M(R)為011000000(2)不具有自反性：M(R)的主對(duì)角線不是全為1是反自反的：M(R)的主對(duì)角線全為0不具有稱性：M(R)不是對(duì)稱的是反對(duì)稱的：M(R)對(duì)稱的位置至多有一個(gè)1是傳遞的：M(R2)如下000000000顯然滿足：如果M(R2)任意位置為1,則M(R)對(duì)應(yīng)位置也為15設(shè)Aw?,R?AXA,證明r(R)=R

7、UIa_一i(2) s(R)=RUR【本題合計(jì)12分，每小題6分-證明格式正確得2分，過程錯(cuò)誤一步扣1分】證明(1)只要證明r(R)?RUIa和RUIa?r(R)即可先證r(R)?RUIa:Ia?RUIa?RUIa自反(自反性的充要條件)?r(R)?RUIa(自反閉包的最小性)再證RUIa?r(R):R?r(R)AIa?r(R)(自反閉包的性質(zhì)及自反性的充要條件)?RUIa?r(R)得證(2)只要證明s(R)?RUR-1及RUR-1?s(R)即可先證s(R)?RUR-1：(RUR-1)-1=RUR-1(理由如下：？<x,y>,<x,y>£(RUR-1)-1?&

8、lt;y,x>erur-1(逆運(yùn)算定義)?<y,x>RV<y,x>CR-1(U定義)?<x,y>CR-1V<x,y>CR(逆運(yùn)算定義)?<x,y>CRUR-1(U定義，U交換律)所以(RUR-1)-1=RUR-1)?RUR-1是對(duì)稱的(對(duì)稱性的充要條件)?s(R)?RUR-1(對(duì)稱閉包白最小性)再證RUR-1?s(R):R?s(R)(閉包定義)AR-1?s(R)(后者理由如下：?<x,y>,-1<x,y>£R?<y,x>CR(逆運(yùn)算定義)?<y,x>Cs(R)?<x

9、,y>Cs(R)(s(R)是對(duì)稱的)所以R-1?s(R)?RUR-1?s(R)得證6設(shè)A=a,b,c,d,R=<a,d>,<b,a>,<b,c>,<c,a>,<c,d>,<d,c>,用Warshall算法求t(R).【本題合計(jì)8分】解依次求出W0,W1,W2,W3,W4=t(R)【2分】Wo=M(R)=0001101010010010【1分】W1=0100011110010010【1分】W2=0001101110010010【1分】W3=0001101110011011【1分】W4=1011101110111011【

10、1分】即t(R)=<a,a>,<a,c>,<a,d>,<b,a>,<b,c>,<b,d>,<c,a>,<c,c>,<c,d>,<d,a>,<d,c>,<d,d>.1分7設(shè)R為A上的自反和傳遞的關(guān)系,證明RAR-1是A上的等價(jià)關(guān)系.【本題合計(jì)10分】證明自反性：？xCA,xRxAxR-1x?x(RnR-1)x【3分】對(duì)稱性：？x,yCA,x(RAR-1)y?xRyAxR-1y?yR_1xAyRx?y(RnR-1)x【3分】傳遞性:?x,y,zCA,x(R

11、AR-1)yAy(RAR-1)z?xRyAxR_1yAyRzAyR-1z?(xRyAyRz)A(xR-1yAyR_1z)?xRzAxR_1z?x(RnR-1)z【4分】得證.8設(shè)A=1,2,3,4,在AXA上定義二元關(guān)系R,?<u,v>,<x,y>CAXA,<u,v>R<x,y>?u+y=v+x證明R是AXA上的等價(jià)關(guān)系；(2)確定由R引起的對(duì)AXA的劃分.【本題合計(jì)10分】解(1)自反性：？<x,y>AXA,<x,y>R<x,y>顯然成立.【2分】對(duì)稱性：?<x,y>,<u,v>AXA

12、,<x,y>R<u,v>?x+v=y+u?u+y=v+x?<u,v>R<x,y>2分】傳遞性：?<x,y>,<u,v>,<s,t>CAXA,<x,y>R<u,v>A<u,v>R<s,t>?x+v=y+uAu+t=v+s?x+t=y+s?<x,y>R<s,t>2分】因此R是AXA上的等價(jià)關(guān)系.(2)根據(jù)R的定義,<x,y>R<u,v>?x+v=y+u?xy=uv,因此<x,y>R=<u,v>|&

13、lt;u,v>AXAAuv=xy,【2分】所以R引起的劃分如下：<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,3>,<3,4>,<2,1>,<3,2>,<4,3>,<1,3>,<2,4>,<3,1>,<4,2>,<1,4>,<4,1>【2分】9設(shè)R,S是A=1,2,3,4上的等價(jià)關(guān)系，其關(guān)系矩陣分別為【本題合計(jì)5分】MrMSS求包含R與S的最小的等價(jià)關(guān)系分析：設(shè)包含R與S的最小等

14、價(jià)關(guān)系為T,則R-T,S工T,根據(jù)等價(jià)關(guān)系的定義，T應(yīng)該具有自反性、對(duì)稱性和傳遞性。所以R.SIT.而T是等價(jià)關(guān)系,由于R與S是等價(jià)關(guān)系，具有上述三個(gè)性質(zhì)，由第四節(jié)關(guān)系運(yùn)算與關(guān)系性質(zhì)的關(guān)系知，不一定有傳遞性。為此，需要使R=S有傳遞性。又題目要求R-S具有自反性、對(duì)稱性，但T是包含R=S的最小等價(jià)關(guān)系，所以，T應(yīng)是包含R，S且具有傳遞性的最小關(guān)系，從而由傳遞閉包的定義，T應(yīng)是R=S的傳遞閉包，即T=t(R_S)。如此，只需求出Mt=Mt(R/)即可。求解過程：MR所以M1J<01JRS=MR二MSRSRS($指對(duì)應(yīng)元素邏輯或)，【2分】?！?分】<0故由Warshall算法，MT=Mt(R.x_S)1J10設(shè)R是集合A上的等價(jià)關(guān)系，|A|=n,|R|=r,|A/R|=t,證明：rt&g