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

第七章作业 评分要求 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 0 是实数集 R 上的二元关系 问 F 具有什么性质并说 明理由 本题合计本题合计 10 分 每种性质分 每种性质 2 分分 答对得答对得 1 分 正确说明理由得分 正确说明理由得 1 分分 解 F x y 2 0 x y 2 0 2 x y 2 自反性 x R F 显然 对称性 F 2 x y 2 2 y x 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 为 011 000 000 2 不具有自反性 M R 的主对角线不是全为 1 是反自反的 M R 的主对角线全为 0 不具有对称性 M R 不是对称的 是反对称的 M R 对称的位置至多有一个 1 是传递的 M R2 如下 000 000 000 显然满足 如果 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 0001 1010 1001 0010 1 分 W1 0001 1011 1001 0010 1 分 W2 0001 1011 1001 0010 1 分 W3 0001 1011 1001 1011 1 分 W4 1011 1011 1011 1011 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 分 1100 1100 0010 0001 R M 1000 0110 0110 0001 S M 求包含 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 即可 即可 求解过程 求解过程 1100 1100 0010 0001 R M 1000 0110 0110 0001 S M 所以 指对应元素逻辑或 2 分 1100 1110 0110 0001 RSRS MMM 故由 Warshall 算法 3 分 1110 1110 1110 0001 Tt RS MM 10 设 R 是集合 A 上的等价关系 A n R r A R t 证明 rt n2 本题合计 5 分 证 设 A R B1 B2 Bt B1 x1 B2