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

第七章作业 评分要求：

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={<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)?, ∈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<0}是实数集R上的二元关系, 问F具有什么性质并说明理由.

【本题合计10分：每种性质2分----答对得1分，正确说明理由得1分】 解 F={|x－y+2>0∧x－y－2<0}={|－2∈F显然. 对称性: ?, ∈F?－2∈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={,}, (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