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

离散数学-第七章二元关系课后练习习题及答案第七章作业评分要求：1.合计100分2.给出每小题得分(注意:写出扣分理由).3.总得分在采分点1处正确设置.1设R={<x,y>|x,y∈N且x+3y=12}.【本题合计10分】(1)求R的集合表达式(列元素法);(2)求domR,ranR;(3)求R◦R;(4)求R↾{2,3,4,6};(5)求R[{3}];解(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分】(3)R◦R={<3,3>,<0,4>}【2分】(4)R↾{2,3,4,6}={<3,3>,<6,2>}【2分】(5)R[{3}]={3}【2分】2设R,F,G为A上的二元关系.证明:(1)R◦(F∪G)=R◦F∪R◦G(2)R◦(F∩G)⊆R◦F∩R◦G(3)R◦(F◦G)=(R◦F)◦G.【本题合计18分：每小题6分，证明格式正确得3分，错一步扣1分】证明(1)∀<x,y>,<x,y>∈R◦(F∪G)⇔∃t(xRt∧t(F∪G)y)复合定义⇔∃t(xRt∧(tFy∨tGy)∪定义⇔∃t((xRt∧tFy)∨(xRt∧tGy))∧对∨分配律⇔∃t(xRt∧tFy)∨∃t(xRt∧tGy)∃对∨分配律⇔x(R◦F)y∨x(R◦G)y复合定义⇔x(R◦F∪R◦G)y∪定义得证(2)∀<x,y>,x(R◦(F∩G))y⇔∃t(xRt∧t(F∩G)y)复合定义⇔∃t(xRt∧(tFy∧tGy))∩定义⇔∃t((xRt∧tFy)∧(xRt∧tGy))∧幂等律,∧交换律,∧结合律⇒∃t(xRt∧tFy)∧∃t(xRt∧tGy)补充的量词推理定律⇔x(R◦F)y∧x(R◦G)y复合定义⇔x(R◦F∪R◦G)y∪定义得证(3)∀<x,y>,<x,y>∈R◦(F◦G)⇔∃s(<x,s>∈R∧<s,y>∈(F◦G))◦定义⇔∃s(<x,s>∈R∧∃t(<s,t>∈F∧<t,y>∈G)))◦定义⇔∃s∃t(<x,s>∈R∧<s,t>∈F∧<t,y>∈G)辖域扩张公式⇔∃t∃s((<x,s>∈R∧<s,t>∈F)∧<t,y>∈G)存在量词交换⇔∃t(∃s(<x,s>∈R∧<s,t>∈F)∧<t,y>∈G)辖域收缩公式⇔∃t(<x,t>∈(R◦F)∧<t,y>∈G)复合定义⇔<x,y>∈(R◦F)◦G复合定义得证3设F={<x,y>|x－y+2>0∧x－y－2<0}是实数集R上的二元关系,问F具有什么性质并说明理由.【本题合计10分：每种性质2分----答对得1分，正确说明理由得1分】解F={<x,y>|x－y+2>0∧x－y－2<0}={<x,y>|－2<x－y<2}自反性:∀x∈R,<x,x>∈F显然.对称性:∀<x,y>,<x,y>∈F⇔－2<x－y<2⇔－2<y－x<2⇔<y,x>∈F.不具有反自反性:反例<2,2>∈F不具有反对称性:反例<2,3>,<3,2>∈F,显然2≠3不具有传递性:反例<2,3.5>,<3.5,5>∈F,但<2,5>不属于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设A≠ø,R⊆A×A,证明(1)r(R)=R∪IA(2)s(R)=R∪R-1【本题合计12分，每小题6分----证明格式正确得2分，过程错误一步扣1分】证明(1)只要证明r(R)⊆R∪I先证r(R)⊆R∪IA:⊆r(R)即可A和R∪IAIA⊆R∪IA⇒R∪IA自反(自反性的充要条件)⇒r(R)⊆R∪IA(自反闭包的最小性)再证R∪IA⊆r(R):R⊆r(R)∧IA⊆r(R)(自反闭包的性质及自反性的充要条件)⇒R∪IA⊆r(R)得证(2)只要证明s(R)⊆R∪R-1及R∪R-1⊆s(R)即可先证s(R)⊆R∪R:-1(R∪R-1)-1=R∪R-1(理由如下:∀<x,y>,<x,y>∈(R∪R-1)-1⇔<y,x>∈R∪R-1(逆运算定义)⇔<y,x>∈R∨<y,x>∈R-1(∪定义)⇔<x,y>∈R-1<x,y>R(∨∈逆运算定义)⇔<x,y>∈R∪R-1(∪定义,∪交换律)所以(R∪R-1)-1=R∪R-1)⇔R∪R-1是对称的(对称性的充要条件)⇒s(R)⊆R∪R-1(对称闭包的最小性)再证R∪R-1⊆s(R):R⊆s(R)(闭包定义)∧R-1⊆s(R)(后者理由如下:∀<x,y>,<x,y>∈R-1⇔<y,x>∈R(逆运算定义)⇒<y,x>∈s(R)⇒<x,y>∈s(R)(s(R)是对称的)所以R⊆s(R))-1⇒R∪R-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分】W0=M(R)=0001101010010010【1分】W1=0001101110010010【1分】W=00012101110010010【1分】W=00013101110011011【1分】W=10114101110111011【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上的自反和传递的关系,证明R∩R-1是A上的等价关系.【本题合计10分】证明自反性:∀x∈A,xRx∧xR-1x⇒x(R∩R-1)x【3分】对称性:∀x,y∈A,x(R∩R-1)y⇔xRy∧xR-1y⇔yR-1x∧yRx⇒y(R∩R-1)x【3分】传递性:∀x,y,z∈A,x(R∩R-1)y∧y(R∩R-1)z⇔xRy∧xR-1y∧yRz∧yR-1z⇔(xRy∧yRz)∧(xR-1y∧yR-1z)⇒xRz∧xR-1z⇔x(R∩R-1)z【4分】得证.8设A={1,2,3,4},在A×A上定义二元关系R,∀<u,v>,<x,y>∈A×A,<u,v>R<x,y>⇔u+y=v+x(1)证明R是A×A上的等价关系;(2)确定由R引起的对A×A的划分.【本题合计10分】解(1)自反性:∀<x,y>∈A×A,<x,y>R<x,y>显然成立.【2分】对称性:∀<x,y>,<u,v>∈A×A,<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>∈A×A,<x,y>R<u,v>∧<u,v>R<s,t>⇔x+v=y+u∧u+t=v+s⇒x+t=y+s⇔<x,y>R<s,t>【2分】因此R是A×A上的等价关系.(2)根据R的定义,<x,y>R<u,v>⇔x+v=y+u⇔x－y=u－v,因此[<x,y>]R={<u,v>|<u,v>∈A×A∧u－v=x－y},【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分】1100110010000110MM01100010RS,.00010001求包含R与S的最小的等价关系.分析:设包含R与S的最小等价关系为T，则RT,ST,所以RST.而T是等价关系，根据等价关系的定义，T应该具有自反性、对称性和传递性。由于R与S是等价关系，具有上述三个性质，由第四节关系运算与关系性质的关系知，RS具有自反性、对称性，但不一定有传递性。为此，需要使RS有传递性。又题目要求T是包含RS的最小等价关系，所以，T应是包含RS且具有传递性的最小关系，从而由传递闭包的定义，T应是RS的传递闭包，即T=t(RS)。如此，只需求出M=MTt(RS)即可。11001000011001100001求解过程：，，M1100MS0010R00011100111001100001所以（指对应MMMRSRS元素逻辑或），【2分】1110111011100001故由Warshall算法，。【3分】MMt(RS)T10设R是集合A上的等价关系,|A|=n,|R|=r,|A/R|=t,证明:rt≥n2.【本题合计5分】证设A/R={B1,B2,…,B},|B|=x,|B|=x2,…,t11