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

离散数学第七章二元关系课后练习习题及答案由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“离散数学第7章习题”。

第七章作业 评分要求：

1.合计100分

2.给出每小题得分(注意: 写出扣分理由).3.总得分在采分点1处正确设置.设R={|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={，，}【2分】(2)domR={0,3,6,9,12}, ranR={0,1,2,3,4}【2分】(3)R◦R={, }【2分】(4)R↾{2,3,4,6}={, }【2分】(5)R[{3}]={3}【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)∀, ∈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(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)∀, ∈R◦(F◦G)⇔ ∃s(∈R∧∈(F◦G))◦定义 ⇔ ∃s(∈R∧∃t(∈F∧∈G)))◦定义 ⇔ ∃s∃t(∈R∧∈F∧∈G)辖域扩张公式 ⇔ ∃t∃s((∈R∧∈F)∧∈G)存在量词交换 ⇔ ∃t(∃s(∈R∧∈F)∧∈G)辖域收缩公式 ⇔ ∃t(∈(R◦F)∧∈G)复合定义 ⇔ ∈(R◦F)◦G 复合定义 得证设F={|x－y+2>0∧x－y－2|x－y+2>0∧x－y－2|－2∈F显然.对称性: ∀, ∈F⇔－2∈F.不具有反自反性: 反例 ∈F 不具有反对称性: 反例 ,∈F, 显然2≠3 不具有传递性: 反例 ,∈F, 但不属于F.设A={a,b,c}, R={,},(1)给出R的关系矩阵;(2)说明R具有的性质(用关系矩阵的判定方法说明理由)【本题合计12分：第（1）小题2分；第（2）小题10分----答对性质得1分，说明理由得1分】 解

(1)R的关系矩阵M(R)为

0 1 1 0 0 0 0 0 0(2)不具有自反性: M(R)的主对角线不是全为1 是反自反的: M(R)的主对角线全为0 不具有对称性: M(R)不是对称的是反对称的: M(R)对称的位置至多有一个1 是传递的: M(R2)如下

0 0 0 0 0 0 0 0 0 显然满足: 如果M(R2)任意位置为1, 则M(R)对应位置也为1 5 设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(理由如下: ∀, ∈(R∪R-1)-1

⇔ ∈R∪R-1(逆运算定义)⇔ ∈R∨∈R-1(∪定义)⇔ ∈R-1∨∈R(逆运算定义)⇔ ∈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)(后者理由如下: ∀, ∈R-1

⇔ ∈R(逆运算定义)

⇒ ∈s(R)

⇒ ∈s(R)(s(R)是对称的)

所以 R-1⊆s(R))⇒ R∪R-1⊆s(R)得证设A={a,b,c,d}, R={，，,}, 用Warshall算法求t(R).【本题合计8分】

解 依次求出W0,W1,W2,W3,W4=t(R)【2分】 W0=M(R)=

【1分】 0 1 1 0 0 0 0 0 0 1 0 10 1 0 W1=

【1分】 W2=

【1分】 W3=

【1分】 0 1 1 0 0 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 11 1 0 1 1 1 0 1 1 1 1 W4= 1 0 1 10 1 10 1 10 1 1 【1分】

即t(R)={，，，，，,}.【1分】 设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分】 得证.设A={1,2,3,4}, 在A×A上定义二元关系R, ∀,∈A×A, R⇔u+y=v+x(1)证明R是A×A上的等价关系;(2)确定由R引起的对A×A的划分.【本题合计10分】 解

(1)自反性: ∀∈A×A, R显然成立.【2分】 对称性: ∀,∈A×A, R⇔x+v=y+u⇔u+y=v+x⇔R【2分】 传递性: ∀，∈A×A, R∧R⇔x+v=y+u∧u+t=v+s⇒x+t=y+s⇔R【2分】 因此R是A×A上的等价关系.(2)根据R的定义, R⇔x+v=y+u⇔x－y=u－v, 因此 []R={|∈A×A∧u－v=x－y},【2分】 所以R引起的划分如下: { { ，,}, {，}, {，}, {,}, {,}, {}, {} }【2分】设R, S是A={1,2,3,4}上的等价关系, 其关系矩阵分别为 【本题合计5分】

11MR00110000100100MS001, 0011001100001.求包含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)即可。

11求解过程：MR00110000100100，MS001***100110011000，01所以MRS11MRMS00111000（指对应元素逻辑或），【2分】 0100。【3分】 01故由Warshall算法，MTMt(RS)设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, 有∈R, 从而

x12+x22+…+xt2 = r,(2)【2分】 根据算术-均方根均值不等式有

x1x2xtt2x12x2xt2

t代入(1)(2)可得 rt  n2 , 得证.【2分】