离散数学-二元关系课后练习习题及答案

1、第七章作业评分要求：1 .合计100分2 .给出每小题得分(注意：写出扣分理由).3 .总得分在采分点1处正确设置.1设R=<x,y>|x,yCN且x+3y=12.【本题合计10分】(1)求R的集合表达式(列元素法);(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设R,F,G为A上的二元关系.证明：(1)R?(FUG)=R?FUR?G(2)R?(FnG)?R?nR?G(3)R?(F?G)=(R?F)?G.【本题合计18分：每小题6分，证明格式正确得3分，错一步扣1分】证明？<x,y>,<x,y>£R?(FUG)?t(xRtAt(FUG)y)复合定义?t(xRtA(tFyVtGy)U定义?t(xRtAtFy)V(xRtAtGy)八对V分配律?t(xRtAtFy)V?t(xRtAtGy)?对V分配律?x(R?F)yVx(R?G)y复合定

3、义?x(R?FUR?G)yU定义得证(2)?<x,y>,x(R?(FAG)y?t(xRtAt(FnG)y)复合定义?t(xRtA(tFyAtGy)n定义?t(xRtAtFy)A(xRtAtGy)A哥等律，A交换律，A结合律?t(xRtAtFy)A?t(xRtAtGy)补充的量词推理定律?x(R?F)yAx(R?G)y复合定义?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)辖域扩张公式?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)复合定义?<x,y>6(R?F)?G复合定义得证3设F=<x,y>|xy+2>0Axy2<0是实数集R上的二元关系，问F具有什么性质并说明理由.【本

5、题合计10分：每种性质2分-答对得1分，正确说明理由得1分】解F=<x,y>|x-y+2>0Ax-y-2<0=<x,y>|-2<x-y<2自反性：？xer,<x,x>ef显然.对称性：?<x,y>,<x,y>CF?2<xy<2?2<yx<2?<y,x>CF.不具有反自反性：反例<2,2>CF不具有反对称性：反例<2,3>,<3,2>F,显然2W3不具有彳递性：反例<2,3.5>,<3.5,5>F,但<2,5&g

6、t;不属于F.4设A=a,b,c,R=<a,b>,<a,c>,(1)给出R的关系矩阵；(2)说明R具有的性质(用关系矩阵的判定方法说明理由)【本题合计12分：第(1)小题2分；第(2)小题10分-答对性质得1分，说明理由得1分】解(1)R的关系矩阵M(R)为011000000(2)不具有自反性：M(R)的主对角线不是全为1是反自反的：M(R)的主对角线全为0不具有称性：M(R)不是对称的是反对称的：M(R)对称的位置至多有一个1是传递的：M(R2)如下000000000显然满足：如果M(R2)任意位置为1,则M(R)对应位置也为15设Aw?,R?AXA,证明r(R)=R

7、UIa_一i(2) s(R)=RUR【本题合计12分，每小题6分-证明格式正确得2分，过程错误一步扣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)(自反闭包的性质及自反性的充要条件)?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,x>RV<y,x>CR-1(U定义)?<x,y>CR-1V<x,y>CR(逆运算定义)?<x,y>CRUR-1(U定义，U交换律)所以(RUR-1)-1=RUR-1)?RUR-1是对称的(对称性的充要条件)?s(R)?RUR-1(对称闭包白最小性)再证RUR-1?s(R):R?s(R)(闭包定义)AR-1?s(R)(后者理由如下：?<x,y>,-1<x,y>£R?<y,x>CR(逆运算定义)?<y,x>Cs(R)?<x

9、,y>Cs(R)(s(R)是对称的)所以R-1?s(R)?RUR-1?s(R)得证6设A=a,b,c,d,R=<a,d>,<b,a>,<b,c>,<c,a>,<c,d>,<d,c>,用Warshall算法求t(R).【本题合计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设R为A上的自反和传递的关系,证明RAR-1是A上的等价关系.【本题合计10分】证明自反性：？xCA,xRxAxR-1x?x(RnR-1)x【3分】对称性：？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设A=1,2,3,4,在AXA上定义二元关系R,?<u,v>,<x,y>CAXA,<u,v>R<x,y>?u+y=v+x证明R是AXA上的等价关系；(2)确定由R引起的对AXA的划分.【本题合计10分】解(1)自反性：？<x,y>AXA,<x,y>R<x,y>显然成立.【2分】对称性：?<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上的等价关系.(2)根据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设R,S是A=1,2,3,4上的等价关系，其关系矩阵分别为【本题合计5分】MrMSS求包含R与S的最小的等价关系分析：设包含R与S的最小等

14、价关系为T,则R-T,S工T,根据等价关系的定义，T应该具有自反性、对称性和传递性。所以R.SIT.而T是等价关系,由于R与S是等价关系，具有上述三个性质，由第四节关系运算与关系性质的关系知，不一定有传递性。为此，需要使R=S有传递性。又题目要求R-S具有自反性、对称性，但T是包含R=S的最小等价关系，所以，T应是包含R，S且具有传递性的最小关系，从而由传递闭包的定义，T应是R=S的传递闭包，即T=t(R_S)。如此，只需求出Mt=Mt(R/)即可。求解过程：MR所以M1J<01JRS=MR二MSRSRS($指对应元素逻辑或)，【2分】。【3分】<0故由Warshall算法，MT=Mt(R.x_S)1J10设R是集合A上的等价关系，|A|=n,|R|=r,|A/R|=t,证明：rt&g