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

发布时间：2020-03-02 17:55:20 来源：范文大全收藏本文下载本文手机版

第七章作业评分要求：

1.合计100分

2.给出每小题得分(注意: 写出扣分理由). 3.总得分在采分点1处正确设置.

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分】

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 复合定义得证

3 设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.

4 设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) 得证

6 设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 1

1 0 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 1

1 1 1 0 1 1 1 0 1 1 1 1 W4= 1 0 1 1

1 0 1 1

1 0 1 1 【1分】

即t(R)={,,,,,,,,,,,}.【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, ∀,∈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分】

9 设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01110111011100110011001100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)

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, 有∈R, 从而

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

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

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