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

第七章作业评分要求：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+20∧x－y－20}是实数集R上的二元关系,问F具有什么性质并说明理由.【本题合计10分：每种性质2分----答对得1分，正确说明理由得1分】解F={x,y|x－y+20∧x－y－20}={x,y|－2x－y2}自反性:∀x∈R,x,x∈F显然.对称性:∀x,y,x,y∈F⇔－2x－y2⇔－2y－x2⇔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∪IA和R∪IA⊆r(R)即可先证r(R)⊆R∪IA:IA⊆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-1⊆s(R))⇒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分】W2=0001101110010010【1分】W3=0001101110011011【1分】W4=1011101110111011【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,vRx,y⇔u+y=v+x(1)证明R是A×A上的等价关系;(2)确定由R引起的对A×A的划分.【本题合计10分】解(1)自反性:∀x,y∈A×A,x,yRx,y显然成立.【2分】对称性:∀x,y,u,v∈A×A,x,yRu,v⇔x+v=y+u⇔u+y=v+x⇔u,vRx,y【2分】传递性:∀x,y,u,v,s,t∈A×A,x,yRu,v∧u,vRs,t⇔x+v=y+u∧u+t=v+s⇒x+t=y+s⇔x,yRs,t【2分】因此R是A×A上的等价关系.(2)根据R的定义,x,yRu,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分】1100110000100001RM,1000011001100001SM.求包含R与S的最小的等价关系.分析:设包含R与S的最小等价关系为T，则RT,ST,所以RST.而T是等价关系，根据等价关系的定义，T应该具有自反性、对称性和传递性。由于R与S是等价关系，具有上述三个性质，由第四节关系运算与关系性质的关系知，RS具有自反性、对称性，但不一定有传递性。为此，需要使RS有传递性。又题目要求T是包含RS的最小等价关系，所以，T应是包含RS且具有传递性的最小关系，从而由传递闭包的定义，T应是RS的传递闭包，即T=t(RS)。如此，只需求出MT=Mt(RS)即可。求解过程：1100110000100001RM，1000011001100001SM，所以1100111001100001RSRSMMM（指对应元素逻辑或），【2分】故由Warshall算法，()1110111011100001TtRSMM。【3分】10设R是集合A上的等价关系,|A|=n,|R|=r,|A/R|=t,证明:rt≥n2.【本题合计5分】证设A/R={B1,B2,…,Bt},|B1|=x1,|B2|=x2,…,|Bt|=xt,显然有1xin,xi∈N,1it.由于A/R是A的划分,因此x1+x2+…+xt=n,(1).【1分】根据Bi是等价类,对任意s,t∈Bi,有s,t∈R,从而x12+x22+…+xt2=r,(2)【2分】根据算术-均方根均值不等式有txxxtxxxtt2222121代入(1)(2)可得rtn2,得证.【2分】