离散数学关系课件

《离散数学关系课件》由会员分享，可在线阅读，更多相关《离散数学关系课件（164页珍藏版）》请在装配图网上搜索。

1、1 第 二 章 关 系 2 在 现 实 生 活 中 , 集 合 与 集 合 之 间 还 存 在 着 某 种联 系 ， 如 同 学 关 系 、 朋 友 关 系 等 。 这 些 关系 正 是 各 门 学 科 所 要 研 究 的 主 要 内 容 。 离散 数 学 从 集 合 出 发 ， 主 要 研 究 集 合 之 间 的关 系 。 本 章 内 容 主 要 研 究 二 元 关 系 。 3 本 章 主 要 内 容 ：n 关 系 的 基 本 概 念n 关 系 的 表 示 方 法 n 关 系 的 运 算 n 关 系 的 性 质 n 关 系 的 闭 包n 等 价 关 系 与 划 分n 偏 序 关 系 4 2.

2、1关 系 的 基 本 概 念为 了 讨 论 关 系 ， 首 先 引 入 有 序 对 和 笛 卡 儿 积 两 个 概 念 。由 两 个 元 素 a, b组 成 的 集 合 a, b中 ， a和 b是 没 有次 序 的 。 有 时 需 要 考 虑 有 次 序 的 两 个 元 素 ， 所 以 需要 由 两 个 元 素 组 成 新 的 东 西 ， 并 且 两 个 元 素 是 有 次序 的 。定 义 2.1两 个 元 素 a, b 有 次 序 地 放 在 一 起 ， 称 为 一 个 有序 对 或 序 偶 ， 记 为 (a, b)。 在 有 序 对 (a, b)中 ， a 称 为第 一 元 素 ， b称

3、为 第 二 元 素 。 且 (a1, b1) = (a2, b2)当且 仅 当 a 1 = a2 且 b1 = b2。 5 定 义 2.2 设 A, B 是 两 个 集 合 ， 集 合 (x, y) | xA 且 yB称 为 A 和 B 的 笛 卡 儿 积 ， 也称 卡 氏 积 ， 记 为 A B。 用 属 于 关 系 来 表 示就 是 ： (x, y)A B 当 且 仅 当 xA 且 yB和 (x, y) A B 当 且 仅 当 x A或 y B。 其中 A 称 为 第 一 集 合 ， B 称 为 第 二 集 合 。 6 例 2.1 设 A=1,2,3, B=a,b， 求 A B。由 笛 卡

4、 儿 积 的 定 义 可 知 有 A = A= 。又 由 有 序 对 的 性 质 可 知 ， 一 般 没 有A BB A。 A B也 是 一 个 集 合 ， 所 以 可以 和 另 一 集 合 C作 笛 卡 儿 积 (A B) C， 类似 地 有 A (B C)。 但 是 ， 一 般 没 有(A B) C=A (B C)， 且 A B中 的 元 素 既不 是 A 中 的 元 素 ， 也 不 是 B中 的 元 素 。 7 定 理 2.1 如 果 B1A1， B2A2， 则B1 B2 A1 A2。 8 证 明 对 (x, y)B1 B2， 有 xB1 且 yB2，又 因 为 B1 A1 ， B2 A

5、2 ， 则 xA1 且yA2， 所 以 (x, y)A1 A2， 即 B1 B2 A1 A2。 9 定 理 2.2 A, B, C 是 任 意 集 合 ， 则 ：(1) A (B C) = (A B) (A C)，(B C) A = (B A) (C A)。(2) A (BC) = (A B)(A C)，(BC) A = (B A)(C A)。(3) A (B -C) = (A B)- (A C)， (B -C) A = (B A) - (C A)。 10 证 明 (1) 对 (x, y)A (B C)， 有 xA 且yB C， 因 此 xA 且 (yB 或 yC)， 当 y B 时 ， 由

6、xA 和 yB 得 (x, y)A B， 当yC 时 ， 由 xA 和 yC 得 (x, y)A C， 所以 (x, y)(A B) (A C)， 即 A (B C) (A B) (A C)。因 为 A A， B B C 和 C B C 得 A B A (B C)和 A C A (B C)， 因 此(A B) (A C) A (B C)。因 此 A (B C) = (A B) (A C)成 立 。同 理 可 证 (B C) A = (B A) (C A)。 11 (2) 对 (x,y)(A B)(A C)， 有 (x,y)A B且(x,y)A C， 所 以 （ xA且 yB） 且 （ xA且

7、yC） 。 由 yB且 yC得 yBC， 由 xA且 yBC 得 (x,y)A (BC)。 因 此(A B)(A C) A (BC)。因 为 A A， BC B和 BC C， 所 以 有A (BC) A B和 A (BC) A C成 立 ，因 此 A (BC) (A B)(A C)。因 此 A (BC)=(A B)(A C)。同 理 可 证 (BC) A=(B A)(C A)。 12 (3) 对 (x,y)A (B-C)， 有 xA且 yB-C， 所 以 xA且yB且 yC。 由 xA且 yB得 (x,y)A B， 由 y C得 (x,y) A C， 所 以 (x,y)(A B)-(A C)。

8、 因 此A (B-C) (A B)-(A C)。对 (x,y)(A B)-(A C)， 有 (x,y)A B且 (x,y) A C，由 (x,y)A B 得 xA且 yB， 由 xA和 (x,y) A C得 y C， 所 以 xA且 yB且 y C。 由 yB且 y C得yB-C， 所 以 (x,y)A (B-C)。 因 此 (A B)-(A C) A (B-C)。因 此 A (B-C)=(A B)-(A C)。同 理 可 证 (B-C) A=(B A)-(C A)。 13 定 义 2.3 任 给 n2， n 个 元 素 a1， , an 有次 序 地 放 在 一 起 ， 称 为 一 个 n

9、元 有 序 组 ，记 为 (a1， ， an)。 为 了 体 现 n 元 有 序 组的 次 序 ， 规 定 (a1， ， an)= (b1,， ， bn)当 且 仅 当 任 给 1in， 都 有 ai = bi。 n 元有 序 组 可 以 组 成 集 合 ， 特 别 地 有 n 个 集合 的 卡 氏 积 。 14 定 义 2.4 任 给 n2， A1， ， An 是 n 个 集合 ， 集 合 (x1, , xn)| 任 给 1in， 都 有xiAi称 为 A1， ， An 的 卡 氏 积 ， 记 为A1 An。 任 给 1in， Ai 称 为 这 个 卡氏 积 的 第 i 个 集 合 。 15

10、 定 义 2.5 如 果 一 个 集 合 满 足 以 下 条 件 之 一 ：（ 1） 集 合 非 空 ， 且 它 的 元 素 都 是 有 序 对 ；（ 2） 集 合 是 空 集 。则 称 该 集 合 为 一 个 二 元 关 系 ， 记 作 R。 二 元 关 系也 可 简 称 为 关 系 。 对 于 二 元 关 系 R， 如 果(x,y)R， 可 记 作 xRy； 如 果 (x,y)R， 则 记 作xRy。设 A， B为 集 合 ， A B的 任 何 子 集 所 定 义 的 二 元关 系 叫 做 从 A到 B的 二 元 关 系 ， 特 别 当 A=B时 则叫 做 A上 的 二 元 关 系 。 1

11、6 例 2.2 设 集 合 A=0,1， B=1,2,3， 那 么R1=(0,2)， R2=A B， R3= ，R4=(0,1)等 都 是 从 A到 B的 二 元 关 系 ，而 R3和 R4同 时 也 是 A上 的 二 元 关 系 。 17 定 义 2.6笛 卡 尔 积 A1 A2 An的 任 意 一 个 子集 R称 为 A1， A2， ， An上 的 一 个 n元 关 系 。 当A1=A2= =An=A时 ， 称 R为 A上 的 n元 关 系 。定 义 2.7 空 集 上 定 义 一 个 二 元 关 系 ， 简 称 空 关系 ； 若 一 个 n元 关 系 R本 身 是 笛 卡 儿 积A1 A

12、2 An ， 则 称 R为 全 关 系 ， 用 符 号UA表 示 ， 即 UA=(ai， aj)| ai， aj A为 A上 的全 关 系 。 符 号 IA=(x,x)|x A为 A上 的 恒 等 关 系 18 例 2.3 设 A=1,2,3,4， 下 面 各 式 定 义 的 R都 是 A上 的 关 系 ， 试 用 列 元 素 法 表 示 R。(1) R=(x,y)|x是 y的 倍 数 (2) R=(x,y)|(x-y)2A(3) R=(x,y)|x/y是 素 数 (4) R=(x,y)|xy 19 解 ： (1) R=(4,4), (4,2), 4,1),(3,3),(3,1),(2,2),

13、(2,1),(1,1)(2) R=(2,1),(3,2),(4,3),(3,1),(4,2),(2,4),(1,3),(3,4),(2,3),(1,2)(3) R=(2,1),(3,1),(4,2)(4) R=UA-IA =(1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,4),(4,1),(4,2),(4,3) 20 定 义 2.8 RA B中 所 有 的 有 序 对 的 第 一 元素 构 成 的 集 合 称 为 R的 定 义 域 ， 记 为domR。 形 式 化 表 示 为 ： domR=x|x A,y B,使 得 (x,y)R。 RA

14、B中所 有 有 序 对 的 第 二 元 素 构 成 的 集 合 称 为 R的 值 域 ， 记 作 ranR。 形 式 化 表 示 为ranR=y| yB ,xA,使 得 (x,y)R。 21 定 义 2.9 设 R为 二 元 关 系 ， R的 逆 关 系 ， 简 称 R的逆 ， 记 作 R-1,其 中 R-1=(y, x)|(x, y)R。例 2.4 整 除 关 系设 A=2, 3, 4,8, B=3, 4, 5, 6, 7, 定 义 从 A到 B的 二 元 关 系 R: (a, b)Ra整 除 b。 则 R=(2, 4), (2, 6), (3, 3), (3, 6), (4, 4)，Dom

15、 R=2, 3, 4, Ran R=3, 4, 6，R-1=(4, 2), (6, 2), (3, 3), (6, 3), (4, 4) 22 关 系 从 本 质 上 讲 ， 仍 是 集 合 ， 只 是 这 个 集 合 中的 元 素 都 是 以 有 序 对 的 形 式 出 现 。 既 然 关 系是 一 个 集 合 ， 那 么 集 合 的 表 示 方 法 就 可 以 用来 表 示 关 系 ， 又 因 为 关 系 是 一 个 特 殊 的 集 合 ，其 中 的 元 素 均 以 序 偶 的 形 式 出 现 ， 除 了 可 以用 集 合 的 表 示 方 法 外 ， 还 可 以 用 其 他 的 表 示方

16、法 。 这 里 主 要 介 绍 如 下 几 种 表 示 方 法 。 2.2 关 系 的 表 示 方 法 23 1. 用 列 举 法 表 示 二 元 关 系如 果 二 元 关 系 中 的 序 偶 个 数 是 有 限 的 ， 可 以 用 列举 法 将 其 所 包 含 的 全 部 元 素 一 一 列 举 出 来 。例 2.5 设 集 合 A=1,2,3， 在 集 合 A上 定 义 的 小于 等 于 关 系 ， LA=(a,b)|a,bA,ab， 则LA=(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)。 24 2. 用 描 述 法 表 示 二 元 关 系用 确 定 的 条 件

17、表 示 某 些 序 偶 是 否 属 于 这 个 关 系 ， 并 把这 个 条 件 写 在 大 括 号 内 表 示 关 系 的 方 法 。 格 式 是 ： LR=(x,y)|xR且 yR且 xy。例 2.6设 A=1， 2， 3， 4， 下 面 两 式 定 义 的 R1和 R2都是 A上 的 关 系 ， 分 别 列 出 R1与 R2的 元 素 如 下 ： (1) R1 =(x,y)|x是 y的 倍 数 (2) R2 =(x,y)|(x-y)2A 25 解 ： (1) R1=(4,4),(4,2),(4,1),(3,3),(3,1),(2,2),(2,1),(1,1)(2) R2=(2,1),(1

18、,2),(3,1),(1,3),(2,3),(3,2),(4,2),(2,4),(3,4),(4,3) 26 3.用 关 系 矩 阵 表 示 关 系定 义 2.10设 A和 B是 两 个 有 限 集 A=a1, , am，B=b1, , bn， R是 从 A到 B的 二 元 关 系 ， 称mn阶 矩 阵 MR=(rij)为 R的 关 系 矩 阵 ， 其 中 rij = 1 ， 当 且 仅 当 (ai, bj)R rij = 0 ， 当 且 仅 当 (ai, bj) R 27 例 2.7 例 2.5中 的 关 系 R的 关 系 矩 阵 为 ：例 2.8 例 2.6中 的 关 系 R1与 R2的

19、关 系 矩 阵 分 别 为 ：RM 100 110 111 1RM 1011 0101 0011 0001 2RM 0110 1011 1101 0110 ， 28 4.用 关 系 图 表 示 二 元 关 系 设 A=a1, , an， R是 A上 的 二 元 关 系 。 A中 每个 元 素 ai用 一 个 点 表 示 ， 称 该 点 为 顶 点 ai 。 R的 关 系 图 是 一 个 有 向 图 ， A中 每 个 元 素 分别 用 一 个 顶 点 表 示 ， 当 且 仅 当 (ai,aj)R时 ， 用 弧 或 线 段 联 结 ai和 aj； 若 (ai,aj) R， 则 在 ai处 画 一

20、条 自 封 闭 的 弧 线 ,其 中1i,jn。 这 样 表 示 R中 关 系 的 图 形 ， 称为 R的 关 系 图 ， 用 GR表 示 。 29 例 2.9设 集 合 A=1,2,3,4， 在 集 合 A上 定 义 关 系R=(1,1)， (1,2)， (2,3)， (2,4)， (4,2)，则 R的 关 系 图 如 图 2.1所 示 。 30 n 关 系 R的 集 合 表 达 式 、 关 系 矩 阵 MR、 关 系图 GR三 者 均 可 唯 一 相 互 确 定 31 定 义 2.11 设 关 系 R和 S是 从 A到 B的 两 个 二 元 关 系 ， 对于 aA， bB， 定 义 ：（

21、1） R S： (a,b)R S (a,b)R或 (a,b)S。（ 2） RS： (a,b)RS (a,b)R且 (a,b)S。（ 3） R-S： (a,b)R-S (a,b)R且 (a,b)S。（ 4） R： (a,b)R (a,b)A B-R。2.3 关 系 的 运 算 32 例 2.10 设 集 合 A=a,b,c， 集 合 B=1,2， 且 R和S是 从 A到 B的 两 个 二 元 关 系 ， R=(a,1),(b,2),(c,1) S=(a,1),(b,1),(c,2) 则 R S=(a,1),(b,2),(c,1),(b,1),(c,2) RS=(a,1) R-S=(b,2),(c

22、,1) R=A B R=(a,2),(b,1),(c,2) 33 因 为 关 系 可 以 用 矩 阵 的 形 式 表 示 ， 当 我 们 用 矩 阵 的 形式 求 关 系 的 并 、 交 、 补 及 对 称 差 的 运 算 时 ， 可 以 用如 下 形 式 表 示 ：MR S=MRMS （ 矩 阵 的 对 应 分 量 做 逻 辑 析 取 运 算 ）MRS=MRMS （ 矩 阵 的 对 应 分 量 做 逻 辑 合 取 运 算 ）MR-S=MRS=MRMS MR=MR （ 矩 阵 的 对 应 分 量 做 逻 辑 非 运 算 ） 34 例 2.11对 例 2.10中 的 关 系 的 运 算 采 用

23、矩 阵 的 形 式 表 示 如 下 ： 根 据 题 意 ， 关 系 R与 S的 关 系 矩 阵 分 别 表 示 为 01 10 01RM 10 01 01SM则 SRSR MMM 11 11 01 SRSR MMM 00 00 01 SRSR MMM 01 10 00 RRBAR MMM 10 01 10 35 定 理 2.3 设 关 系 R、 S是 集 合 A到 集 合 B的 二 元 关 系 ， 则 有下 列 性 质 成 立 ：(1) (R-1)-1=R, (R)=R (双 重 否 定 律 )(2) (R)-1= (R-1), -1 = (可 换 性 ) (3) (R S)-1=R-1 S-

24、1 (分 配 律 ) (RS)-1=R-1S-1 (R-S)-1=R-1-S-1 (4) SR S-1 R-1 (单 调 性 ) SR S R (5)domR-1=ranR， ranR-1=domR(6) (AB)-1= BA 36 证 明 ： 这 里 只 证 明 （ 1） 和 （ 5） 。(1)任 取 (x,y)， 由 逆 的 定 义 有 (x,y)(R-1)-1 (y,x)R-1 (x,y)R。所 以 有 (R-1)-1=R。(5)任 取 x, xdomR-1 y(x,y)R-1) y(y,x)R) xranR 所 以 有 domR-1=ranR。同 理 可 证 ranR -1=domR。

25、 37 合 成 关 系定 义 2.12设 R是 从 集 合 A到 集 合 B的 二 元 关系 ， S是 从 集 合 B到 集 合 C的 二 元 关 系 ， 则R与 S的 复 合 关 系 （ 合 成 关 系 ） RS是 从 A到 C的 关 系 ， 并 且 ，RS=(x,z)|xA且 zC且 存 在 yB使 得(x,y)R,(y,z)S， 运 算 “ ” 称 为 复 合运 算 或 合 成 运 算 。 38 例 2.12 设 A上 的 二 元 关 系 R=(x,y)|x,yA, x是 y的 父 亲 ， S=(x,y)| x,yA, x是 y的 母 亲 (1)说 明 RR， R-1 S1 ， R-1

26、S的 含 义 。(2)表 示 以 下 关 系 ：(x,y)|x,yA, y是 x的 外 祖 母 (x,y)|x,yA, x是 y的 祖 母 39 解 ：(1) RR表 示 关 系 (x,y)|x,yA, x是 y的 祖 父 R-1 S1 表 示 关 系 (x,y)|x,yA, y是 x的 祖 母 tA(x,t)R-1 (t,y)S-1)R-1 S表 示 空 关 系 (2)(x,y)|x,yA, y是 x的 外 祖 母 表 示 为 S-1 S1 (x,y)|x,yA, x是 y的 祖 母 表 示 为 SR 40 例 2.13设 Z是 整 数 集 合 ， R， S是 Z到 Z的 两 个 关系 ：R

27、=(x,3x)|xZ； S=(x,5x)|xZ。计 算RS； SR； RR； SS； (RR)R； (RS)R。 41 解RS=(x,15x)|xZ； SR=(x,15x)|xZ； RR=(x,9x)|xZ； SS=(x,25x)|xZ； (RR)R=(x,27x)|xZ； (RS)R=(x,45x)|xZ。 42 定 理 2.4 R为 定 义 在 集 合 A上 的 关系 ,则 RIA=IAR=R 43 证 明 任 取 (x,y)， 有(x,y)RIAt(x,t)R且 (t,y)IA) t(x,t)R且 t=y) (x,y)R又 有(x,y)R (x,y)R且 x,yA (x,y)R且 (y,

28、y)IA (x,y)RIA所 以 ， RIA=R。同 理 可 证 I AR=R。 44 定 理 2.5 设 R1 A1A2 ， R2 A2A3 ， R3 A3A4， 则(1)(R1R2)R3 = R1(R2R3) (2)(R1R2)-1=R2-1R1-1不 满 足 交 换 律 ， 即 R1R2 R2R1 45 证 明 ： (1)任 取 (x,y), (x,y)(R1R2)R3 (tA3) (使 得 (x,t) R1R2且 (t,y)R3) (tA3)(sA2),使 得 (x,s)R1且 (s,t)R2)且(t,y)R3) (tA3) (sA2)(使 得 (x,s)R1且 (s,t)R2且(t,

29、y)R3) (sA2)(使 得 (x,s)R1且 (tA3) (使 得(s,t)R2且 (t,y)R3) (sA2)(使 得 (x,s)R1且 (s,y)R2R3) (x,y)R1(R2R3)所 以 (R1 R2) R3 =R1(R2R3) 46 由 归 纳 法 ， 任 意 n个 关 系 的 合 成 也 是 可 结 合的特 别 ， 当 A1= A2 = =An+1 =A且 R1= R2 = =Rn =R， 合 成 关 系 R R R=Rn 是 集 合 A上 的 一 个 关 系 。 47 （ 2） 任 取 (z,x)(R1R2)-1， 则 （ x,z)R1R2， 由 “ ”的 定 义 知 ，至

30、少 存 一 个 yB， 使 得 (x,y)R1， (y,z)R2， 即 (y,x)R-11，(z,y)R-12。 由 (z,y) R-12和 (y,x) R-11 ， 有 (z,x) R-12 R-11 。 所 以 ， (R1R2)-1 R-12 R-11 。反 之 ， 任 取 (z,x) R-12 R-11 ， 由 “ ”的 定 义 知 ： 则 至 少 存 在一 个 yB， 使 得 (z,y) R-12和 (y,x) R-11 ， 所 以 (x,y)R1，(y,z)R2。由 “ ”知 (x,z)R1R2。 即 有 (z,x)(R1R2)-1。所 以 ， R-12 R-11 (R1R2)-1。

31、由 集 合 的 性 质 知 ： (R1R2)-1= R-12 R-11 。 48 例 2.14 设 A=a,b,c,d,e,f，R=(a,a),(a,b),(b,c),(c,d),(d,e),(e,f)。求 Rn(n=1,2,3,4,) 49 解 ： R1=R； R2=RR=(a,a),(a,b),(a,c),(b,d),(c,e),(d,f)； R3=RRR=R2R=(a,a),(a,b),(a,c),(a,d),(b,e),(c,f)； R4=R3R=(a,a),(a,b),(a,c),(a,d),(a,e),(b,f)； R5=R4R=(a,a),(a,b),(a,c),(a,d),(a

32、,e),(a,f)； R6=R5R=(a,a),(a,b),(a,c),(a,d),(a,e),(a,f)=R5； R7=R6R=R5； Rn=R5（ n 5） 。 50 n 幂 集 Rn的 基 数 |Rn|并 非 随 着 n的 增 加 而 增加 ， 而 是 呈 递 减 趋 势 ， 而 且 ， 当 时 ， 有 AnAi in RR 1 51 2.4关 系 的 性 质有 了 关 系 的 定 义 ， 可 以 来 定 义 关 系 的 某 些特 殊 性 质 ， 这 些 性 质 在 以 后 的 讨 论 中 ，将 起 到 极 其 重 要 的 作 用 。 本 节 主 要 讨 论关 系 的 五 种 性 质 ，

33、 即 自 反 性 、 反 自 反 性 、对 称 性 、 反 对 称 性 和 传 递 性 。 52 自 反 、 反 自 反定 义 2.14设 R为 集 合 A上 的 二 元 关 系 ： （ 1） 若 对 任 意 的 xA， 都 有 (x,x)R， 则 称 关系 R在 集 合 A上 是 自 反 的 或 称 关 系 R具 有 自 反 性 ； 否 则 ， 称 R是 非 自 反 的 。（ 2） 若 对 任 意 的 xA， 都 有 (x,x)R， 则 称 关系 R在 集 合 A上 是 反 自 反 的 或 称 关 系 R具 有 反 自反 性 。自 反 关 系 ： 全 关 系 、 恒 等 关 系 、 小 于

34、等 于 关 系 、整 除 关 系 、 包 含 关 系反 自 反 关 系 ： 小 于 关 系 、 真 包 含 关 系 53 例 2.15 设 A=1,2,3， R1=(1,1),(2,2)，R2=(1,1),(2,2),(3,3),(1,2)，R3=(1,3)， 说 明 R1， R2， R3是 否 为 A上自 反 的 关 系 。 54 解 ： 只 有 R2是 A上 自 反 的 关 系 ， 因 为 IA R2； 而 R1和 R3都 不 是 A上 的 自 反 关 系 ，因 为 (3,3)R1 ， 所 以 R1不 是 自 反 的 ， 而(1,1),(2,2),(3,3)都 不 属 于 R3 ， 因 此

35、 R3不是 自 反 的 。关 系 R是 否 为 自 反 关 系 是 相 对 集 合 A来 说 的 。同 一 个 关 系 在 不 同 的 集 合 上 具 有 不 同 的性 质 。 55 例 2.16设 A=a,b,c,d， 在 集 合 A上 定 义 如下 三 个 二 元 关 系 R,S,T分 别 如 下 ： R=(a,a),(a,d),(b,b),(b,d),(c,c),(d,d)S=(a,b),(a,d),(b,c),(b,d),(c,a),(d,c)T=(a,a),(a,b),(a,c),(b,d),(c,a),(c,c),(d,c)说 明 R,S,T在 A上 的 自 反 性 与 反 自 反

36、 性 。 56 解 ： 因 为 A中 每 个 元 素 x， 都 有 (x,x)R， 所 以 R在 A具 备 自 反 性 。因 为 A中 每 个 元 素 x， 都 有 (x,x)S， 所 以 S在 A具备 反 自 反 性 。因 为 A中 有 元 素 b， 使 (b,b)T， 所 以 T在 A上 不 具备 自 反 性 ； 因 为 A中 有 元 素 a， 使 (a,a)T， 所以 T在 A上 也 不 具 备 反 自 反 性 。任 何 不 是 自 反 的 关 系 未 必 一 定 是 反 自 反 的 关 系 ，反 之 亦 然 。 即 存 在 既 不 是 自 反 的 也 不 是 反 自 反的 关 系 。

37、57 定 理 2.6 设 R是 定 义 在 集 合 A上 的 二 元 关 系 ， R是自 反 的 当 且 仅 当 IA R。 58 证 明 （ 1） 必 要 性 设 R在 A上 是 自 反 的 ， 则 IA R。根 据 恒 等 关 系 的 定 义 ， 对 任 意 的 xA有 (x,x)IA， 又因 为 R在 A上 是 自 反 的 ， 即 对 于 任 意 的 xA有(x,x)R， 因 此 IA R 。 （ 2） 充 分 性 设 IA R， 则 R在 A上 是 自 反 的 。对 任 意 的 xA有 (x,x)IA， 而 IA R ， 因 此 对 任 意 的xA有 (x,x)R， 即 R在 A上 是

38、 自 反 的 。 59 定 理 2.7 设 R是 定 义 在 集 合 A上 的 二 元 关 系 ，R是 反 自 反 的 当 且 仅 当 RIA=。 60 证 明 （ 1） 必 要 性 设 R在 A上 是 反 自 反 的 ， 则RIA=。 假 设 RIA， 比 如 存 在 （ x， y） RIA， 即 （ x，y） R且 （ x， y） IA ， 也 即 （ x， y） R且x=y， 即 （ x， x） R， 与 R在 A上 是 反 自 反 的 相矛 盾 。 因 此 RIA=。充 分 性 设 RIA=， 则 R在 A上 是 反 自 反 的 。对 任 意 的 xA， 有 ( x, x) IA ，

39、由 于 RIA=，因 此 ( x, x)R， 即 R在 A上 是 反 自 反 的 。 61 对 称 、 反 对 称定 义 2.15 设 R为 A上 的 关 系 。 (1) 若 对 任 意 的 x与 y， 都 有 x,yA且 (x,y)R， 则 有(y,x)R， 则 称 R为 A上 对 称 关 系 ； 否 则 ， 称 R是 非 对称 的 。(2) 若 对 任 意 的 x与 y， 都 有 x,yA且 当 (x,y)R，(y,x)R时 ， 有 x=y， 则 称 R为 A上 的 反 对 称 关 系 。对 称 ： 全 关 系 、 恒 等 关 系 、 空 关 系反 对 称 ： 恒 等 关 系 、 空 关

40、系 62 例 2.17 设 A=a,b,c， 定 义 A上 的 二 元 关 系 如下 ： R=(a,a),(b,b)S=(a,a),(a,b),(b,a)T=(a,c),(a,b),(b,a)试 说 明 R， S， T是 否 是 A上 的 对 称 关 系 和 反 对 称关 系 。 63 解 ： 根 据 定 义 R上 A上 的 对 称 关 系 与 反 对 称 关 系 。S是 A上 的 对 称 关 系 。 S不 是 A上 的 反 对 称 关 系 ， 因 为(a,b)与 (b,a)都 是 S中 的 元 素 ， 但 是 ab， 所 以 S不 是A上 的 反 对 称 关 系 。T既 不 是 A上 的 对

41、 称 关 系 ， 也 不 是 A上 的 反 对 称 关 系 。因 为 (a,c)是 T中 的 元 素 ， 但 是 (c,a)不 是 T中 的 元 素 ，因 此 不 满 足 对 称 性 ， 又 因 为 (a,b)与 (b,a)都 是 T中 的元 素 ， 但 是 ab， 因 此 也 不 满 足 反 对 称 性 。 64 定 理 2.8 设 R是 A上 的 二 元 关 系 ， R是 对 称 的 当 且 仅 当 R=R-1。 65 证 明 (1)必 要 性 设 R是 对 称 的 ， 则 R=R-1。(x， y)R(y， x)R(x， y) R-1 R=R-1。(2)充 分 性 设 R=R-1， 则 R

42、是 对 称 的 。(x， y)R(y， x) R-1(y， x)R， 因 此 R是 对称 的 。 66 定 理 2.9 设 R是 A上 的 二 元 关 系 ， R是反 对 称 的 当 且 仅 当 RR-1IA。 67 证 明 (1)必 要 性 设 R是 反 对 称 的 ， 则 RR-1IA。(x， y)RR-1(x， y)R且 (x， y)R-1（ x， y） R且 (y， x)R， 因 为 R是 反 对 称 的 ， 根 据 反 对 称 的 定 义 ，则 x=y， 因 此 (x， y)=(y， x)=(x， x) IA， 所 以 RR-1IA。(2)充 分 性 设 RR-1IA， 则 R是 反

43、 对 称 的 。(x， y)R且 (y， x)R (x， y)R 且 (x， y)R-1 (x，y)RR-1因 为 RR-1IA， 所 以 (x， y) IA， 顾 x=y，因 此 R是 反 对 称 的 。 68 传 递定 义 2.16 设 R为 A上 的 关 系 ， 若 对 任 意 的 x， y，z有 x,y,zA且 当 (x,y)R， (y,z)R时 ， 有(x,z)R,则 称 R是 A上 的 传 递 关 系 ， 否 则 称 R是 非 传 递 关 系 。传 递 关 系 ： 全 关 系 、 空 关 系 、 小 于 、 包 含 69 例 2.18 设 A=1,2,3， R1=(1,1)，R2=

44、(1,3),(2,3)， R3=(1,1),(1,2),(2,3)，说 明 R1， R2， R3是 否 为 集 合 A上 传 递 的 关 系 。 70 解 ： 根 据 定 义 2.16， R1， R2是 A上 传 递 的 关 系 ； 但 R3不 是 传 递 的 ， 因 为 (1,2)R3，(2,3)R3， 而 (1,3)R3， 由 传 递 关 系 的 定 义知 R3不 是 传 递 的 关 系 。 71 定 理 2.10 设 R是 集 合 A上 的 二 元 关 系 ， 则 R是 传 递 的 当 且 仅 当 R.RR 72 证 明 (1） 必 要 性 设 R是 传 递 的 ， 则 R.RR。设 (

45、x， y)R.R， zA， 使 得 (x， z) R且 (z， y) R。 因 为 R是 传 递 的 ， 所 以 (x， y) R， 即 有R.RR。(2)充 分 性 设 R.RR， 则 R是 传 递 的 。(x， y) R且 (y， z) R。 由 复 合 关 系 的 定 义 可 得(x， z) R.R， 因 为 R.RR， 所 以 (x， z) R，即 R是 传 递 的 。 73 2.4.2关 系 性 质 的 证 明在 二 元 关 系 中 ， 除 了 对 一 个 具 体 的 关 系 判 断 它 具 有 哪 些 性 质外 ， 更 多 的 是 针 对 一 个 抽 象 的 关 系 ， 利 用 它

46、 的 特 点 来 证 明它 具 有 某 个 性 质 。 由 于 关 系 性 质 的 定 义 全 部 都 是 按 “ 如果 那 么 ”来 描 述 的 ， 在 证 明 这 类 问 题 时 ， 一 般 采 用按 照 定 义 证 明 的 方 法 。 这 种 证 明 问 题 的 方 法 在 于 ： 证 明 时不 能 仅 仅 利 用 题 目 所 给 的 已 知 条 件 ， 还 要 同 时 结 合 定 义 中的 “ 已 知 ” ， 并 且 推 出 的 并 非 整 个 定 义 ， 而 是 定 义 中 的 结论 。另 外 ， 由 于 关 系 是 特 殊 的 集 合 ， 当 用 集 合 的 手 段 来 描 述 关

47、 系的 性 质 时 ， 其 证 明 的 方 法 也 是 按 集 合 中 的 按 定 义 证 明 方 法来 证 。 74 例 2.19设 R1， R2是 定 义 在 集 合 A上 的 两 个 关 系 ， 并且 R1， R2具 有 传 递 性 ， 则 R1R2也 具 有 传 递 性 。 75 证 明 ： 对 任 意 x,yA， 则 若(x,y) R1R2且 (y,z) R1R2 (x,y)R1且 (x,y)R2且 (y,z)R1且 (y,z)R2 (x,y)R1且 (y,z)R1)且 (x,y)R2 且 (y,z)R2)又 因 为 R1， R2具 有 传 递 性 ， 因 此 (x,y)R1且 (y

48、,z)R1)且 (x,y)R2且 (y,z)R2) (x,z)R1且 (x,z)R2 (x,z)R1R2根 据 定 义 2.16， R1R2具 有 传 递 性 。 76 关 系 性 质 与 集 合 运 算运 算 性 质自 反 性 反 自 反 性 对 称 性 反 对 称 性 传 递 性R S RS R-S R -1 RS 77 2.5关 系 的 闭 包对 于 在 非 空 集 合 上 定 义 的 关 系 R不 一 定 具 备 某 种 性 质 或 某几 种 性 质 ， 而 这 些 性 质 对 研 究 某 些 具 体 的 问 题 时 又 非常 重 要 ， 这 时 就 需 要 构 造 一 个 基 于 此

49、 关 系 的 新 关 系 ，使 其 具 备 所 需 要 的 性 质 ， 即 往 该 关 系 中 添 加 一 些 适 量的 元 素 以 改 变 原 有 关 系 的 性 质 ， 得 到 新 的 关 系 ， 使 得新 关 系 具 有 所 需 要 的 性 质 ， 但 又 不 希 望 新 关 系 与 R相 差太 多 ， 也 就 是 说 ， 要 尽 可 能 少 地 来 添 加 有 序 对 ， 满 足这 些 要 求 的 新 关 系 就 称 为 R的 闭 包 。 本 节 介 绍 关 系 的 自反 、 对 称 和 传 递 闭 包 。 78 定 义 2.17设 R是 非 空 集 合 A上 的 关 系 ， R的 自

50、 反 （ 对 称或 传 递 ） 闭 包 是 A上 的 关 系 Rc， 使 得 Rc满 足 以 下 条件 ： (1) Rc是 自 反 的 （ 对 称 的 或 传 递 的 ） ； (2) R Rc； (3) 对 A上 任 何 包 含 R的 自 反 （ 对 称 或 传 递 ） 关 系 Rp有Rc Rp。一 般 将 R的 自 反 闭 包 记 作 r(R)， 对 称 闭 包 记 作 s(R)，传 递 闭 包 记 作 t(R)。 79 定 理 2.11 设 R为 定 义 在 非 空 集 合 A上 的 二元 关 系 ， 则 有（ 1） r（ R） = R IA（ 2） s（ R） = R R-1（ 3） t

51、（ R） = R R2 R3 80 证 明 （ 1） 令 R=R IA， 则 有 IA R IA ， 而 R IA =R， 因 此 R是 自 反 的 。 R R IA ， 而 R IA =R， 因 此 R R。 假 设 R是 A上 的 任 意 自 反 关 系 并 且 R R， 因 为R是 自 反 的 ， 所 以 IAR， 因 此 有 R=R IA R。由 自 反 闭 包 的 定 义 ， R=R IA是 R的 自 反 闭 包 ， 即r(R)=R=R IA 。 81 （ 2） 令 R= R R-1 (R) -1=(R R-1)-1= R-1 (R-1) -1= R-1 R= R R-1= R,因

52、此 R是 对 称 的 。 R R R-1， 而 R R-1= R， 因 此 R R。 设 R是 A上 的 任 意 对 称 关 系 并 且 R R， 又 (x，y) R-1(y， x) R(y， x) R， 从 而 有 R= R R-1 R。因 此 R是 R的 对 称 闭 包 ， 即 s(R)= R R-1。 （ 3） 分 两 部 分 来 证 所 要 的 结 论 。 先 证 R R2 R3 t（ R）用 数 学 归 纳 法 来 证 ， 对 任 意 自 然 数 i， 有 Ri t（ R） 当 i=1时 ， 由 传 递 闭 包 的 定 义 ， R1=R t（ R） 。 假 设 当 i=n时 ， Rn

53、 t（ R） ,下 证 Rn+1 t（ R） 。对 任 意 的 (x,y)Rn+1， 存 在 cA， 使 得 (x,c)Rn且 (c,y)R， 即存 在 cA， 使 得 (x,c)t(R)且 (c,y)t(R)， 则 (x,y)t(R)。即 Rn+1 t(R)， 因 此 ， R R2 R3 t(R)。再 证 明 t(R) R R2 R3 。显 然 ， 有 R R R2 R3 成 立 ， 下 证 R R2 R3 是 传 递的 。(x,y) R R2 R3 t(R)且 (y,z) R R2 R3 tA， 使 得 (x,y)R t且 sA， 使 得 (y,z)Rs (x,z)RtRs=Rt+s R

54、R2 R3 (x,z) R R2 R3 由 传 递 关 系 的 定 义 ， R R2 R3 是 传 递 的 。综 上 所 述 ， R R2 R3 是 包 含 R的 传 递 关 系 。 而 R的 传 递 闭 包是 包 含 R的 最 小 传 递 关 系 ， 因 此 t(R) R R2 R3 。即 t(R)= R R2 R3 成 立 。 83 推 论 设 R是 有 限 集 合 A上 的 关 系 ， |A|=n， 此 时t（ R） =R R2 R3 Rn有 。 84 例 2.20设 集 合 A=a, b, c， R是 A上 的 二 元关 系 ， 且 R=(a, b), (b, c), (c, a)，

55、求 出关 系 R的 自 反 、 对 称 和 传 递 闭 包 。 85 解 ： r(R)=R IA=(a,a),(b,b),(c,c),(a,b),(b,c),(c,a)s(R)=R R-1=(a,b),(b,c),(c,a),(b,a),(c,b),(a,c)R2=(a,c),(b,a),(c,b)R3=(a,a),(b,b),(c,c)R4=(a,b),(b,c),(c,a)因 此 ， 有R=R4R2=R5R3=R6t(R)=R R 2 R3 =R R2 R3 =(a,a),(b,b),(c,c),(a,b),(b,c),(c,a),(a,c),(b,a),(c,b) 86 例 2.21设

56、集 合 A=a,b,c， R是 A上 的 二 元 关 系 ， 且R=(a,b),(b,c),(c,a)， 用 关 系 矩 阵 求 关 系 R的 自 反 、 对 称和 传 递 闭 包 。 87 解 关 系 的 关 系 矩 阵 为 ： 001 100 010RM 010 001 100001 100 010001 100 0102 RRR MMM 111 111 111)( 32 RRR MMMRt 100 010 001001 100 010010 001 10023 RRR MMM 88 定 理 2.12 设 R是 非 空 集 合 A上 的 关 系 ，（ 1） 若 R是 自 反 的 ， 则 s

57、(R)与 t(R)也 是 自 反 的 。（ 2） 若 R是 对 称 的 ， 则 r(R)与 t(R)也 是 对 称 的 。（ 3） 若 R是 传 递 的 ， 则 r(R)是 传 递 的 ， 而 s(R)不一 定 传 递 。 证 明 (1)若 R是 自 反 的 ， 则 有 IA R。 又 因 为 Rs(R)，且 Rt(R)， 所 以 IAs(R)且 IA t(R)， 因 此 s(R)与 t(R)是 自 反 的 。(2)因 为 R对 称 ， 有 R=R-1。 由 于 r(R)=R IA ， 而 (r(R) -1=(R IA)-1= R-1 IA-1= R IA= r(R),因 此 r(R)对称 。

58、因 为 R对 称 ， 因 此 (Ri)-1=(R-1)i= Ri。 由 于 t(R)= R R2 R3 ,于 是(t(R)-1=(R R2 R3 )-1= R-1 (R2)-1 (R3)-1 = R R2 R3 =t(R)所 以 t(R)也 对 称 。 90 (3)因 为 R传 递 ， 所 以 R.RR， 而 r(R)=R IA ， 则 有r(R).r(R)=( R IA)( R IA) =R.( R IA) IA. ( R IA) = R .R R IA IA. ( R IA) = R .R R ( R IA) R R ( R IA) = R IA = r(R)即 r(R)具 有 传 递 性

59、 。 91 下 面 举 一 个 反 例 来 说 明 s(R)不 具 备 传 递 性 。假 设 集 合 A=1,2,3， R=(1,2)是 定 义 在集 合 A上 的 且 具 有 传 递 性 ， 而s(R)=(1,2),(2,1)却 不 具 备 传 递 性 。 92 定 理 2.13 设 R1,R2A A， 且 R1R2， 则r(R1)r(R2) s(R1)s(R2)t(R1)t(R2) 93 证 明 ：(1)因 为 R1R2， 因 此 R1 IA R2 IA ， 所 以 r(R1)r(R2)。反 证 法 ：假 设 (x, y)r(R1), 但 (x, y)r(R2)， 则 r(R1) (x,

60、y)也 是自 反 的 ， 即 xy; 如 果 (x, y)R1， 则 (x, y)R2， 那 么 (x, y)r(R2)， 导 致 矛 盾 ， 因 此 (x, y) R1， 所 以 R1 r(R1) (x, y)， 那 么 r(R1)不 是 R1的 自 反 闭 包 ， 矛 盾 。 因 此 (x, y) r(R2)。所 以 r(R1) r(R2)。 94 (2)因 为 R1R2， R2s(R2)， 因 此 R1s(R2)。 由s(R1)是 包 含 R1的 最 小 对 称 关 系 ， 所 以s(R1)s(R2)。(3)因 为 R1R2， R2t(R2)， 因 此 R1t(R2)。 由t(R1)是

61、包 含 R1的 最 小 传 递 关 系 ， 所 以t(R1)t(R2)。 95 定 理 2.14 设 R1和 R2是 集 合 A上 的 关 系 ， 则 以下 各 式 成 立 。（ 1） r（ R1 R2 ） =r（ R1 ） r（ R2 ）（ 2） s（ R1 R2 ） =s（ R1 ） s（ R2 ）（ 3） t（ R1 ） t（ R2 ） t（ R1 R2 ） 96 证 明 ： （ 1） r(R1 R2)=IA (R1 R2)=(IA R1) (IA R2)=r(R1) r(R2)（ 2） s(R1 R2)=(R1 R2) (R1 R2)-1=(R1 R2) (R-11 R-12)=(R1

62、 R-11) (R2 R-12)=s(R1) s(R2)（ 3） 因 为 R1R1 R2 ， R2 R1 R2 ， 所 以 t(R1) t(R1 R2)， t(R2) t(R1 R2)， 得 出 t(R1) t(R2) t(R1 R2)。一 般 地 ， t(R1) t(R2)t(R1 R2)。 97 例 2.22 设 集 合 A=1,2,3， R1=(1,2),(2,3)，R2=(3,2)， 有t(R1)=(1,2),(1,3),(2,3) t(R2)=(3,2)而t(R1 R2)=(1,2),(1,3),(2,2),(2,3),(3,2),(3,3)t(R1) t(R2)=(1,2),(1,

63、3),(2,3),(3,2)由 此 可 见 t(R1) t(R2)t(R1 R2)。 98 定 理 2.15 设 R是 集 合 A上 的 关 系 ， 则（ 1） rs(R)=sr(R)；（ 2） rt(R)=tr(R)；（ 3） st(R)ts(R)。 99 证 明 （ 1） )()( AIRsRsr 1)()( AA IRIR )()( 1 AA IRIR AIRR 1 AIRs )( )( Rrs 100 (2) )()( AIRtRtr iAi IR )(1 1 1i ij Aj IR 11 1 i Ai ij j IR 1i Ai IR AIRt )( )(Rrt 101 (3)若 R

64、S， 则 显 然 有 s(R)s(S)， t(R)t(S)。 根据 对 称 闭 包 的 定 义 ， R s(R)， 于 是t(R)ts(R)st(R) sts(R)若 s(R)对 称 ， 则 ts(R)也 对 称 。 所 以 ， 由 (1)可 得 sts(R)=ts(R)，即 st(R) ts(R)。 102 例 2.23设 A=1,2， R=(1,2)， 求 st(R)与 ts(R)。 103 例 2.23设 A=1,2， R=(1,2)， 求 st(R)与 ts(R)。解 ： st(R)=s(t(R)=s(1,2)=(1,2),(2,1)ts(R)=t(s(R)=t(1,2),(2,1)=

65、(1,2),(2,1),(1,1),(2,2) 104 2.6等 价 关 系 与 划 分在 日 常 生 活 中 或 者 在 数 学 等 学 科 中 ， 常 常 需 要 对某 个 集 合 上 的 元 素 按 照 某 种 方 式 进 行 分 类 ， 即集 合 的 划 分 ， 这 是 一 个 非 常 重 要 的 而 且 应 用 十分 广 泛 的 概 念 ， 集 合 的 划 分 与 一 种 重 要 的 关系 等 价 关 系 密 切 相 关 。 利 用 等 价 关 系 ， 可以 将 集 合 中 的 元 素 分 类 ， 将 一 个 大 的 集 合 分 成若 干 个 等 价 类 ， 其 主 要 意 义 在

66、于 它 证 实 了 应 用抽 象 的 一 般 原 理 的 正 确 性 ， 即 在 某 方 面 等 价 的个 体 产 生 等 价 类 ， 对 全 体 的 等 价 类 进 行 分 析 常常 比 对 全 体 本 身 进 行 分 析 更 简 单 。 105 2.6.1等 价 关 系定 义 2.18设 R为 非 空 集 合 A上 的 关 系 。 如 果R是 自 反 的 、 对 称 的 和 传 递 的 ， 则 称 R为A上 的 等 价 关 系 。 设 R是 一 个 等 价 关 系 ，若 (x， y)R， 称 x等 价 于 y， 记 做 x y。 106 例 2.24以 下 关 系 是 等 价 关 系 ： (1) 集 合 A上 的 恒 等 关 系 、 全 域 关 系 是 等 价关 系 。(2) 三 角 形 的 全 等 关 系 、 三 角 形 的 相 似 关 系是 等 价 关 系 。(3) 在 一 个 班 级 里 “ 年 龄 相 等 ” 的 关 系 是 等价 关 系 。 107 例 2.25设 关 系 R是 定 义 在 有 理 数 集 Q上 的 关系 ， 并 且 (x,y)R， 当 且 仅 当 x-y