1、3-5.1 列 出 所 有 从 X=a,b,c到 Y=s的 关 系 。 解 ： Z1= Z2= Z3= Z4=, Z5=, Z6=, Z7=, 3-5.2 在 一 个 有 n个 元 素 的 集 合 上 ， 可以 有 多 少 种 不 同 的 关 系 。 解 因 为 在 X中 的 任 何 二 元 关 系 都 是 XX的 子 集 ， 而 XX=X2中 共 有 n2个 元 素 ， 取 0个 到 n2个 元 素 ， 共 可 组成 2n个 子 集 ， 即 |)(|。 3-5.3 设 A 6： 00， 6： 30,7： 30， , 9： 30,10： 30表 示 在 晚 上 每 隔 半 小 时的 九 个 时
2、 刻 的 集 合 ， 设 B=3,12,15,17表 示 本 地 四 个 电 视 频 道 的 集 合 ,设 R1和 R2是 从 A到 B的 两 个 二 元 关 系 ， 对于 二 无 关 系 R1， R2， R1 R2， R1 R2，R1R2和 R1-R2可 分 别 得 出 怎 样 的 解释 。 解 ： AB表 示 在 晚 上 九 个 时 刻 和 四 个电 视 频 道 所 组 成 的 电 视 节 目 表 。 R1和 R2分 别 是 AB的 两 个 子 集 ，例 如 R1表 示 音 乐 节 目 播 出 的 时 间 表 ，R2是 戏 曲 节 日 的 播 出 时 间 表 ， 则 R1R2表 示 音 乐
3、 或 戏 曲 节 目 的 播 出 时 间表 ， R1 R2表 示 音 乐 和 戏 曲 一 起 播 出的 时 间 表 ， R1R2表 示 音 乐 节 目 表 以及 戏 曲 节 目 表 ， 但 不 是 音 乐 和 戏 曲 一起 的 节 日 表 ， R1-R2表 示 不 是 戏 曲 时 间的 音 乐 节 目 时 间 麦 。 3-5.4 设 L表 示 关 系 “小 于 或 等 于 ”， D表 示 整 除 ”关 系 ,L和 D刀 均 定 义 于1,2,3,6， 分 别 写 出 L和 D的 所 有 元素 并 求 出 L D. 解 ： L=, , D=, L D= , 3-5.5对 下 列 每 一 式 ，
4、给 出 A上 的 二 元关 系 ， 试 给 出 关 系 图 ： a)|0 x y 3， 这 里A=1,2,3,4； b)|2 x,y 7且 x除 尽 y,这里 A n|n N n 10 c) |0 x-y|x,y是 互 质 的 ， 这 里A=2,3,4,5,6 解 ： a) R=, , , , 其 关 系 图 b) R=, , , , , , 3-6.1 分 析 集 合 A=1， 2， 3上 的 下 述五 个 关 系 ： （ 1） R= 1， 1 ， 1， 2 ， 1，3 ， 3， 3 ； （ 2） S= 1， 1 ， 1， 2 ， 2，1 ， 2， 2 ， 3， 3 ； （ 3） T= 1，
5、 1 ， 1， 2 ， 2，2 ， 2， 3 ； （ 4） =空 关 系 ； （ 5） AA=全 域 关 系 。 判 断 A中 的 上 述 关 系 是 否 为 a） 自 反 的 ，b） 对 称 的 ， c） 可 传 递 的 ， d） 反 对 称的 。 解 （ 1） R是 可 传 递 和 反 对 称 的 。 （ 2） S是 自 反 ， 对 称 和 可 传 递 的 。 （ 3） T是 反 对 称 的 。 （ 4） 空 关 系 是 对 称 ， 可 传 递 和 反 对 称的 。 （ 5） 全 域 关 系 是 自 反 ， 对 称 和 可 传 递的 。 3-6.2给 定 A=1， 2， 3,4， 考 虑
6、a上的 关 系 R,若 R= 1， 3 ， 1， 4 ， 2， 3 ， 2， 4 ， 3， 4 a) 在 AA的 坐 标 图 上 标 出 R， 并 绘 出它 的 关 系 图 ； b) R是 )自 反 的 ） 对 称 的 )可 传递 的 ， iv) 反 对 称 的 吗 ？ 解 a） R是 可 传 递 的 的 和 反 对 称 的 ； 但 不 是 自反 的 和 对 称 的 。 3-6.3 举 出 A=1， 2， 3上 关 系 R的例 子 ， 使 其 具 有 下 述 性 质 ： a） 既 是 对 称 的 ， 又 是 反 对 称 的 ； b） R既 不 是 对 称 的 ， 又 不 是 反 对 称 的 ；
7、 c） R是 可 传 递 的 。 解 a） R= 1， 1 ， 2， 2 ， 3， 3 b） R= 1， 2 ， 2， 1 ， 2， 3 c) R= 1， 2 ， 2， 1 ， 1， 1 ， 2， 2 ， 3， 3 3-6.4 如 果 关 系 R和 S是 自 反 的 ， 对称 的 和 可 传 递 的 ， 证 明 R S也 是 自 反 ，对 称 和 可 传 递 的 。 证 明 设 R和 S是 X上 的 自 反 的 ， 对 称的 和 可 传 递 的 关 系 。 1） 对 任 意 x X， 有 x， x R和 x， x S， 所 以 x， x R S，即 R S在 X上 是 自 反 的 。 2） 对
8、 任 意 的 x， y R S， 有 x，y R x， y S， 因 为 R和 S是 对 称 的 ， 故 必 有 y， x R y， x S。 即 y， x R S，所 以 R S在 X上 是 对 称 的 。 3） 对 任 意 的 x， y R S y， z R S， 则 有 x， y R x， y S y，z R y， z S 因 为 R和 S是 传 递 的 ， 故 得 x， z R x， z S， 即 x， z RS， 所 以 R S在 X上 是 传 递 的 。 3-6.5给 定 S=1， 2， 3， 4和 S上 关系 ： R= 1， 2 ， 4， 3 ， 2， 2 ， 2， 1 ， 3，
9、 1 说 明 R是 不 可 传 递 的 ， 找 出 关 系 R1R，使 得 R1是 可 传 递 的 ， 还 能 找 出 另 一 个1 2 4 3 3-7.1设 R1和 R2是 A上 的 任 意 关 系 ，说 明 以 下 命 题 的 真 假 并 予 以 证 明 。a） 若 R1和 R2是 自 反 的 ， 则 R1R2也 是自 反 的 ； b） 若 R1和 R2是 反 自 反 的 ， 则 R1R2也是 反 自 反 的 ； c） 若 R1和 R2是 对 称 的 ， 则 R1R2也 是对 称 的 ； d） 若 R1和 R2是 传 递 的 ， 则 R1R2也 是传 递 的 。 证 明 a） 对 任 意
10、a A， 设 R1和 R2是 自反 的 ， 则 a， a R1， a， a R2 所 以 ， a， a R1R2， 即 R1R2也 是自 反 的 。 b） 假 。 例 如 ： 设 A=a， b， 有 R1=a， b 与 R2= b， a R1和 R2是 反 自 反 的 。 但 R1R2= a， a ， 所 以 R1R2在 A上 不 是 反 自 反 的 。 c)假 。 例 如 ： 设 A=a， b， c， 有 R1= a， b ， b， a ， c， c ，R2= b， c ， c， b R1和 R2是 对 称 的 ， 但 R 1R2= a， c ， c， b 所 以 ， R1R2不 是 对 称
11、 的 。 d） 假 。 例 如 ： 设 A=a， b， c， 有 R1= a， b ， b， c ， a， c ，R2= b， c ， c， a ， b， a 则 R1， R2都 是 传 递 的 。 但 R 1R2= a，c ， a， a ， b， a 所 以 ， R1R2不 是 传 递 的 。 3-7.2 证 明 若 S为 集 合 X上 的 二 元 关系 ： a） S是 传 递 的 ， 当 且 仅 当 （ SS） S； b） S是 自 反 的 ， 当 且 仅 当 IXS； c） 证 明 定 理 3-7.3（ b） （ 即 S是 反 对称 的 ， 当 且 仅 当 S ScIX） 。 证 明 a
12、） 设 S为 传 递 的 ， 若 x， z SS， 则 存 在 某 个 y X， 使 得 x， y S， 且 y， z S。 若 S是 传 递 的 ， x， z S， 所 以 （ SS）S。 反 之 ， 设 （ SS） S ， 假 定 x， y S且 y， z S， 则 x， z SS。因 为 （ SS） S， 故 x， z S， 得到 S是 传 递 的 。 b） 设 S是 自 反 的 ， 令 x， y IX，则 x=y。 但 x， x S， 因 此 x， y = x， x S， 得 IXS。 反 之 ， 令 IXS， 设 任 意 x X， x， x IX， 故 x， x S， 因 此 S是
13、自反 的 。 c） 设 S是 反 对 称 的 。 假 定 x， y S Sc， 则 x， y S x， y Sc x， y S y， x S 因 为 S是 反 对 称 的 ， 故 x y， 所 以 x， y x， x IX， 即 SScIX。 反 之 ， 若 S ScIX， 设 x， y S且 y， x S， 则 x， y S x， y Sc x， y S Sc x， y IX 故 x y， 即 S是 反 对 称 的 。 3-7.3 设 S为 X上 的 关 系 ， 证 明 若 S是 自 反 和 传 递 的 ， 则 SS=S， 其 逆 为 真吗 ？ 证 明 若 S 是 X 上 传 递 关 系 ，
14、 由 习 题3-7.2a） 可 知 （ SS） S， 令 x， y S， 根 据 自 反 性 ， 必 有 x， x S， 因 此 有 x， y SS，即 SSS。 得 到 S=SS. 这 个 定 理 的 逆 不 真 。 例 如 X=1， 2， 3，S= 1， 2 ， 2， 2 ， 1， 1 ，3-8.1 根 据 图 3-8.1中 的 有 向 图 ， 写 出 邻 接 矩 阵 和 关 系 R， 并 求 出 R的 自 反 闭 包 和 对 称 闭 包 。 解 MR= R= a， a ， a， b ， b， c ， c， b r（ R） = R IX = a， a ， b， b ， c， c ， a，
15、b ， b， c ， c， b s（ R） = R RC= a， a ， a， b ， b， a ， b， c ， c， b 3-8.2 设 集 合 A=a， b， c， dA上 的 关 系 R= a， b ， b， a ， b， c ， c， d a） 用 矩 阵 运 算 和 作 图 方 法 求 出 R的 自 反 、 对 称 、 传 递 闭 包 ； b） 用 Warshall算 法 ， 求 出 R的 传 递 闭 包 。 解 a） MR= R的 关 系 图 如 图 所 示 。 MR+MIA= r（ R） = R IA = a， a ， a， b ， b， a ， b， b ， b， c ， c
16、， c ， c， d ， d， d （ 图 （ a） ） MR+MRc= 1 1 0 0 0 1 0 1 0 0 1 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 + 0 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 + 0 0 1 0 a b c 图 3-8.1 a b d c a b d c 图 （ a） 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 1 = 0 1 0 0 1
17、0 1 0 0 1 0 1 0 0 1 0 = 3-9.1 4个 元 素 的 集 合 共 有 多 少 不 同 的 划 分 。 解 整 数 4可 划 分 为 ： 4， 1+3， 1+1+2， 2+2， 1+1+1+1。 1+C41+C42+12 C42+1=15（ 种 ） 3-9.2 设 A1， A2， ， Ak是 集 合 A的 一 个 划 分 ， 我 们 定 义 A上 的 一 个 二 元 关 系 R， 使 a,b R当 且 仅 当 a和 b在 这 个 划 分 的 同 一 块 中 。 证 明 R是 自 反 的 ， 对 称 的 ， 和 传 递 的 。 证 明 设 对 任 意 a A， 则 必 存
18、在 Ai， 使 a Ai， 因 a与 a必 可 看 作 在 同 一 块 中 ， 故 有 a,a R。 即 R是 自 反 的 。 设 a,b A， 若 有 a,b R， 则 a与 b必 在 同 一 块 ， 故 b与 a亦 在 同 一 块 ， b, a R， 即 R是 对 称 的 。 对 任 意 a,b,c A， a,b R b,c R （ i） （ a Ai b Ai） （ j） （ b Aj c Aj） （ i） （ j） （ a Ai c Aj b Ai Aj） （ i） （ j） （ a Ai c Aj Ai Aj ） （ i） （ j） （ a Ai c Aj i=j） （ i jAi
19、Aj= ） a,c在 同 一 块 a,c R R传 递 3-10.1 设 R和 R 是 集 合 A上 的 等 价 关 系 ， 用 例 子 说 明 ： R R 不 一 定 是 等 价 关 系 。 证 明 设 A=1， 2， 3， S=R R R= 1， 1 ， 2， 2 ， 3， 3 ， 3， 1 ， 1， 3 R = 1， 1 ， 2， 2 ， 3， 3 ， 3， 2 ， 2， 3 则 R R = 1， 1 ， 2， 2 ， 3， 3 ， 3， 1 ， 1， 3 ， 3， 2 ， 2， 3 因 为 如 2， 3 S 3， 1 S， 但 2， 1 S， 故 R R 不 是 传 递 的 ， 即 R
20、 R 不 是A上 的 等 价 关 系 。 3-10.2 试 问 由 4个 元 素 组 成 的 有 限 集 上 所 有 等 价 关 系 的 个 数 为 多 少 ？ 解 因 为 集 合 X上 的 等 价 关 系 与 X的 划 分 是 一 一 对 应 的 ， 所 以 4个 元 素 的 有 限 集 上 等 价 关 系的 数 目 ， 与 4个 元 素 集 合 进 行 划 分 的 数 目 是 相 同 的 ， 由 习 题 3-9.1可 知 共 有 15个 不 同 的 等价 关 系 。 3-10.3 给 定 集 合 S=1， 2， 3， 4， 5， 找 出 S上 的 等 价 关 系 R， 此 关 系 R能 产
21、 生 划 分 1，2， 3， 4， 5， 并 画 出 关 系 图 。 解 我 们 可 用 如 下 方 法 产 生 一 个 等 价 关 系 ： R1=1， 21， 2= 1， 1 ， 1， 2 ， 2， 1 ， 2， 2 R2=33= 3， 3 R3=4， 54， 5= 4， 4 ， 4， 5 ， 5， 4 ， 5， 5 R= R1 R2 R3= 1， 1 ， 1， 2 ， 2， 1 ， 2， 2 ， 3， 3 ， 4， 4 ， 4， 5 ， 5， 4 ， 5， 5 关 系 图 如 图 。 3-10.4 设 R是 一 个 二 元 关 系 ， S= a， b 对 于 某 一 c， 有 a， c R
22、 c， b R，证 明 若 R是 一 个 等 价 关 系 ， 则 S也 是 一 个 等 价 关 系 。 证 明 设 R是 A上 的 等 价 关 系 ： （ 1） 对 任 一 x A， 因 为 R在 A上 自 反 ， 所 以 x， x R。 由 S定 义 ， x， x S，所 以 S是 自 反 的 。 （ 2） 对 任 意 x,y A， 若 x， y S， 则 存 在 某 个 c， 使 得 x， c R c， y R， 因 为 R是 对 称 ， 故 有 ： y， c R c， x R， 由 S的 定 义 ， 可 知 y， x S， 所 以 S是 对 称 的 。 （ 3） 对 任 意 x,y,z
23、A， 若 x， y S， 及 y， z S， 则 必 存 在 某 个 c1， 使 x，c1 R， c1， y R。 由 R的 传 递 性 ， 可 知 x， y R， 同 理 存 在 c2， 使 y， c2 R c2， z R， 由 R传 递 ， 可 知 y， z R。 再 由 S定 义 ， 得 x，z S。 故 S是 传 递 的 。 3-10.5 设 正 整 数 的 序 偶 集 合 A， 在 A上 定 义 二 元 关 系 R如 下 ： x,y , u,v R，当 且 仅 当 xv=yu， 证 明 R是 一 个 等 价 关 系 。 证明 ：设 A 上定义的二元关系 R 为：x,y, u,vR =
24、xyuv 对任意x,yA，因为 = ，所以xyxyx,y, x,yR即 R 是自反的。 设x,yA，u,vA，若x,y, u,vR = = u,v,x,yRxyuv uvxy即 R 是对称的。 设任意x,yA，u,vA，w,sA，对x,y, u,vRu,v, w,sR（ = ） （ = ） =xyuv uvws xywsx,y , w,s R故 R 是传递的，于是 R 是 A 上的等价关系。3-10.6 设 R 是集合 A 上的对称和传递关系，证明如果对于 A 中的每一个元素 a,在 A 中同时也存在 b，使在 R 之中，则 R 是一个等价关系。证明 ：对任意 aA，必存在一个 bA，使得a,
25、bR.因为 R 是传递的和对称的，故有：a,bRb, cRa, cR c,a R由a,cRc, aRa,aR所以 R 在 A 上是自反的，即 R 是 A 上的等价关系。3-10.7 设 R1和 R2是非空集合 A 上的等价关系，试确定下述各式，哪些是 A 上的等价关系，对不是的式子，提供反例证明。a） （AA）-R 1；b）R 1-R2；c）R 12；d) r（R 1-R2） （即 R1-R2的自反闭包） 。解 a） （AA）-R 1不是 A 上等价关系。例如：A=a,b，R 1=a,a，b,bAA=a,a，a,b，b,a，b,b（AA）-R 1=a,b，b,a所以（AA）-R 1不是 A 上
26、等价关系。b）设 A=a,b,cR1=a,b，b,a，b,c，c,b，a,c，c,a，a,a，b,b，c,cR2=a,a，b,b，c,c，b,c，c,bR1-R2=a,b，b,a，a,c，c,a所以 R1和 R2是 A 上等价关系，但 R1-R2不是 A 上等价关系。c）若 R1是 A 上等价关系，则a,aR 1a,a R 1R 1所以 R12是 A 上自反的。若a,bR 12则存在 c，使得a, cR 1c,bR 1。因 R1对称，故有b, cR 1c,aR 1b, aR 12即 R12是对称的。若a,bR 12b, cR 12,则有a,bR 1R 1b, cR 1R 1（e 1） （a,
27、e 1R 1e 1, bR 1) （e 2） （b, e 2R 1e 2, cR 1）a,bR 1b, c R 1（R 1传递）a,cR 12即 R12是传递的。故 R12是 A 上的等价关系。d）如 b）所设，R 1和 R2是 A 上的等价关系，但r（R 1-R2）=（R 1-R2）I A=a,b, b,a, a,c，c,a，a,a，b,b, c,c不是 A 上的等价关系。3-10.8 设 C*是实数部分非零的全体复数组成的集合， C*上的关系 R 定义为：(a+bi)R(c+di)ac0,证明 R 是等价关系，并给出关系R 的等价类的几何说明。证明：(1)对任意非零实数 a，有 a20(a
28、+bi)R(a+bi)故 R 在 C*上是自反的。(2) 对任意(a+bi)R(c+di)ac0,因 ca=ac0(c+di)R(a+bi),所以 R 在 C*上是对称的。(3)设(a+bi)R(c+di) ，(c+di)R(u+vi)，则有 ac0cu0若 c0，则 a0u0 au0若 c0所以(a+bi)R(u+vi)，即 R 在 C*上是传递的。关系 R 的等价类，就是复数平面上第一、四象限上的点，或第二、三象限上的点，因为在这两种情况下，任意两个点(a,b)，(c,d)，其横坐标乘积 ac0。3-10.9 设 和 是非空集合 A 上的划分，并设 R 和 R分别为由 和 诱导的等价关系，
29、那么 细分 的充要条件是 R R。证明：若 细分 。由假设 aRb，则在 中有某个块 S，使得 a,bS ，因 细分 ，故在 中，必有某个块 S，使 S S，即a,bS，于是有 aRb,即 R R。反之，若 R R，令 S为 H的一个分块，且 aS，则 S=aR=x|xRa但对每一个 x，若 xRa，因 R R，故 xRa，因此x|xR a x|xRa即a R aR设 S=aR,则 S S这就证明了 细分 。3-10.10 设 Rj是表示 I 上的模 j 等价关系，R k是表示 I 上的模 k 等价关系，证明 I/Rk细分 I/Rj当且仅当 k 是 j 的整数倍。证明：由题设 Rj=|xy(modj)Rk=|xy(modk)故R jx-y=cj (对某个 cI)R kx-y=dk (对某个 dI)a)假设 I/Rk细分 I/Rj，则 Rk Rj因此R kR j故 k-0=1k=cj (对某个 cI)于是 k 是 j 的整数倍。b)若对于某个 rI，有 k=rj 则：R kx-y=ck (对某个 cI) x-y=crj (对某个 c,rI)R j因此，R k Rj，于是 I/Rk细分 I/Rj
