离散数学 关系性质

既不是 自反的，
图 ３ 对称性与反对称性 的关 系在文氏图上的反应
ｉ＼／ √ ＼ ．ｌ Ｉ・ ｌ ｛． ＼ Ｉ ／ ＼ 。 ’
Ｉ像 ＼ Ｉ
图 ４ 对 称 性 与 反 对 称 性在 关 系 矩阵 Ｅ的反 应
图 １ 自反性与反 自 反性 的关 系在数轴上的反应
２１ 年 ０１
第 ３ 期 ３
Ｓ ＩＮ Ｅ Ｅ Ｈ Ｏ Ｏ ＹＩＦ Ｒ Ａ Ｉ Ｎ ＣＥ Ｃ ＆Ｔ Ｃ Ｎ Ｌ Ｇ Ｏ Ｍ Ｔ Ｏ Ｎ
Ｏ高校讲坛 。
科技信． １ Ｉ
《 离散数学》 教学中关系性质的探讨
张 琳 （ 南京邮电大学计算机学院 江苏
【 摘
南京
２ ０ ） １ ０ ３ ０
针对二元关系 ， ３ 有 种表达形式 ： 序偶法 、 系矩 阵和关 系图。下 关 面借助关系矩阵来探讨关系的自反性与反 自 反性的性质 ， 如图 ２ 所示。 其 中 ． 于关 系的对称性与反对称 性只需要关注上三角 区域和下 对 现将关系矩阵分成 ３ 部分 ： 上三角 、 下三角和对称轴 。 对于关 系的 三角区域 ， 而对称轴处 的元素的取值 可以任 意。 自 反性与反 自 反性只需要关注对称轴上 的元素 ， 为其支撑 学科的 离 数学变得越 来越重要 。 作 散 结合教学经验 ， 对集合论 中关系的性质展开 了深入研
究． 并总结 出了一些学习经验 。
【 关键词】 集合论 ； 系的性质 ； 反性 ； 关 自 对称性
０ 引言
离散数学是计 算机专业 的基础课 ．它有别于其他公共课类数学 ， 如高等数学 、 线性代数等 。 是和计算机科学有着密切关系的学科 。 具有 这样 的两个 特点 ：） １ 以离散量 为研 究对象 ， 以讨 论离散量的结构和相 互之 间的关系为主要 目 ． 标 这些对象一般是有 限个或可数个元素 ， 充 分描 述了计算机科学离 散性的特点 ，与公共课类 数学形成 了鲜 明对 比。２ 它是 数学中的一个分支 ， ） 因而它有数学 的味道 ， 比如用一些符 号、 引进一些定义 、 运用定 理推导等等 。因而学 习离散数学 ， 对提高学 生的抽象能力 ， 归纳能力 、 逻辑推理能力将有很大帮助。 图 ２ 自反性与反 自反性在 关系矩 阵上的反应 作为教学科研型的南京邮电大学而言 ． 离散数学一直是计算机 专 业的基础课而被受到足够多的重视 。近些年 。 学校 为计算机学 院引进 若 对称轴 上的元素全 为 １ 则可判 断该 二元关 系是 自反 的 ； ， 若全 了多位 曾经攻读过数学专业的计算 机硕士 、 士来扩充《 博 离散 数学》 课 为 ０ 则可判 断为反 自反 的： ， 若果对 称轴上既有 ０又有 １ 则说明既不 ， 程的教师资源 笔者承担的是计算机科学与技术专业 的离散数学教 学 是 自反的也不是反 自 反的 ． 和图 Ｉ 中的情况相吻合 。 工作 ． 结合 自己的教学 经验 ， 本文对离散数学第 二部分集合论 中的关 ２２ 对称性 与反对称性 ． 系的性 质展开 了讨论 用这种类 比的方法总结完 自反性与反 自反性之后 ． 留给学生课后 总结对称性与反对称 性的关系 ． 然后 ． 下一节课开始上课 的时候就跟 １ 关 系性 质 的 相 关 概 念 学生～起再来 总结一下 设 Ｒ是集合 ｘ上的二元关 系， Ｒ的性质 主要有 ５种 ： 反性 、 则 自 仍 然用 举实 例 的方 法来 总结 这 两种 性 质 ．同样 还 是集 合 Ａ＝ 对称性 、 传递性 、 自 反 反性 、 反对称性 。 ｛， ３ 上 的关系 ． １ ，） ２。 自反性 ： ∈Ｘ， Ｖ 有 ，＞ＥＲ Ｓ ＝｛ ，＞＜ ，＞，３３ Ｉ ＜１２ ，２ １ ＜ ，＞） 对称性 ： ∈ ， ＞ Ｒ 若＜ ， Ｒ 则＜ ∈ ｓ＝ ＜ ， ， ， ， ， ｝ ２ ｛ １ ＞ ３１ ＜ ３ ２＜ ＞ ３＞ 传递性 ： 若 ∈Ｒ且 ： Ｒ， ＞∈ 则 在 ＞ ∈Ｒ Ｓ ＝｛ ， ＞ ＜ ， ＞， ３ １ ３ ＜１２ ， ２ １ ＜ ， ＞】 反 自反性 ： ∈ ， Ｖ 有 ， Ｒ ＞ ｓ＝ ＜ ， ，２２ ） ４ ｛ ｌ１ ＜ ，＞ ＞ 反对称 性 ： 若 ， ∈ ｙ Ｒ且 ≠ ， ＞ Ｒ ＞ Ｙ 则＜ 隹 由定义知 ， ｓ是对 称的 ，， Ｊ 反对称的 ， ｓ Ｓ 既不是 对称的也不是反 对 经过几年 的教学发 现 ． 多数 同学对这 ５ 种性质搞不清楚 ． 概念 对 的认识模棱两可 ． 不清彼此之 间的关 系和区别 ． 了避免该类 问题 称的 ， 分 为 Ｓ 既是对称 的也是反对称 的。 的出现 ． 下文对这 些性质进行 了总结 ， 并将其应用到教学 中， 达到 了较 对于这两 种性 质之间 的关 系可以借助文 氏图给学 生形象化 的进 好的教学效果 行总结 ， 共分为 ４个区域 ， 具体如图 ３ 所示。

例如，集合X上的全域关系EX、 恒等关系IX都不是X上的反 自反关系.
2）若关系R不是反自反的，关系R也不一定是自反的，反之也 成立.
XZ-{0}时，整除关系 R2={<x,y>x,yX∧x整除y}. 都是自反关系.
(3) 数集X上的小于关系 R3= {<x,y>x,yX∧xy}. 不是自反的.
若集合X上的二元关系R是自反的充要条件： • 1） R是自反的恒等关系IX R. • 2） R是自反的关系R的关系矩阵MR的主对角线全是1. • 3） R是自反的关系R的关系图中每个结点都有上的二元关系,如果对于每 个x∈X，有<x,x>R，则称二元关系R是反自反的.
R在X上反自反 (x)(xX <x,x>R ). 例如，数集X上的小于关系 R3={<x,y>x,yX∧xy} 空关系 ，均为反自反关系.
若集合X上的二元关系R是反自反的充要条件： • 1） R是反自反的恒等关系IX R= . • 2） R是反自反的关系R的关系矩阵MR的主对角线全是0. • 3） R是反自反的关系R的关系图中每个结点都没有自回路.
设 X={1,2,3}, R1={<1,1>,<2,2>,<3,3>,<1,2>} 是X上的自反关系; R2={<1,3>} 是X上的反自反关系; R3 ={<1,1>,<1,2>,<2,2>,<2,3>} 既不是自反的，也不是反自反的.
注意：
1）一个关系R如果是自反的，一定不是反自反的；如果是反自 反 的，则一定不是自反的.
关系的性质
一、关系的性质
关系的性质主要有5种：自反性、反自反性、对称性、反对 称性、传递性.

7
4.3.1 关系性质的定义和判别
对称性与反对称性（续）
例2 设A＝{a,b,c}, R1, R2, R3和R4都是A上的关系, 其中 R1＝{<a,a>,<b,b>}， R2＝{<a,a>,<a,b>,<b,a>} R3＝{<a,b>,<a,c>}， R4＝{<a,b>,<b,a>,<a,c>} R1 对称 R2 对称 R3 对称 ？ ？ ？ 反对称 反对称 反对称 ？ ？ ？
12
4.3.1 关系性质的定义和判别
传递性（续）
例3 设A＝{a, b, c}, R1, R2, R3是A上的关系, 其中 R1＝{<a,a>,<b,b>} R2＝{<a,b>,<b,c>} R3＝{<a,c>}
R1 和 R3 是A上的传递关系, R2 不是A上的传递关系.
13
4.3.1 关系性质的定义和判别
R∘RR 对MR2中1所在 位置, MR中相 位置都是1
如果顶点xi到 xj有边, xj到xk 有边,则从xi到 xk也有边
20
主对角 主对角 线元素 线元素 全是1 全是0
每个顶 点都有 环
每个顶 点都没 有环
注意：IA是对称关系也是反对称关系
4.3.1 关系性质的定义和判别
实例
例8 判断下图中关系的性质, 并说明理由
18
4.3.1 关系性质的定义和判别
传递性证明
证明模式 证明 R 在 A上传递 任取<x, y>，<y, z> <x, y>R<y, z>R …..………. <x, z>R 前提 推理过程 结论

10
结论
R是A上的关系，则： （1）R是自反关系的主要条件是IAA （2）R是反自反关系的主要条件是R∩IA=Ф。
11
(3) 若x y(x,y∈A ∧<x,y> ∈R <y,x> ∈R),则称R 在A上是对称的。 也就是说, 对RAA, 对A中每个x和y, 若xRy, 则yRx, 称 R是对称的, 即
7
例子
例3：N上的互质关系是反自反关系。 证明：x∈N，x与x是不互质的， ∴<x,x>R，∴R具有反自关系。 其他的例实数上的＜，＞关系,人与人的父子 关系,均是反自反关系。
8
关系矩阵的特点
自反关系的关系矩阵的对角元素均为1， 反自反关系的关系矩阵的对角元素均为0。
9
关系图的特点
自反关系的关系图，每个结点均有自回路， 而反自反关系的关系图的每个结点均没有 自回路。
22
说明:
该定义的等价说法： a,b∈A,如a≠b,<a,b>∈R, 则必有<b,a>R。即两个不同点结点间不允许有两 条弧。 该定义的否命题说法并不成立,如 “a≠b,<a,b>R,则<b,a>∈R”并不成立, 即反对称关系的关系图允许两个不同点间没有弧。
23
有些关系既是对称的又是反对称的
设 R 是 A 上的关系，R 的性质主要有以下 5 种 (2) 若x(x ∈A <x,x> ∈R),则称 R 在 A 上是反自反的 也就是说，对RAA，若A中每个x，有xRx，则称R是 反自反的，即 A上关系R是反自反的x(xAxRx) 该定义表明了，一个反自反的关系R中，不应包括有任 何相同元素的有序对。 例如：设A={1,2,3}，R 是 A 上的关系， R={<2,3>,<3,2>} R是反自反的

3-7 关系的性质
例 设R，S是X上的二元关系，证明 ⑴ 若R,S是自反的，则R∪S和R∩S也是自反的。 ⑵ 若R,S是对称的，则R∪S和R∩S也是对称的。 ⑶ 若R,S是传递的，则R∩S也是传递的。 证明：⑴ 设R,S是自反的,由定理4.3.1知,IX⊆R,IX⊆S,所以 IX⊆R∪S,IX⊆R∩S,再由定理4.3.1知,R∪S和R∩S也是自反的。 ⑵ 设R,S是对称的，由定理4.3.3知，R=RC，S=SC，根据定理4.2.8， R∪S=RC∪SC=(R∪S)C，R∩S=RC∩SC=(R∩S)C,再由定理4.3.3知,R∪S 和R∩S也是对称的。 ⑶ 设R,S是传递的,由定理4.3.5知,R∘R⊆R,S∘S⊆S,据定理4.2.4, (R∩S)∘(R∩S)⊆(R∘R)∩(R∘S)∩(S∘R)∩(S∘S)⊆(R∘R)∩(S∘S)⊆R∩S 即(R∩S)∘(R∩S)⊆R∩S，再由定理4.3.5，R∩S是传递的。
Байду номын сангаас
3-7 关系的性质
设R是X上的反对称关系，由定义4.3.4知，在R的关系矩 阵MR中以主对角线为轴的对称位置上不能同时为1(主对角线 除外)。在R的关系图中每两个不同的结点间不能有方向相反 的两条边。 设X=⎨1,2,3⎬，X上的二元关系 R=⎨<1,2>,<2,3>,<3,3>⎬，R是反对称的。它的关系图如图 4.8所示，关系矩阵如下：
⎛0 ⎜ M R= ⎜ 1 ⎜0 ⎝
1 0 0
0⎞ ⎟ 0⎟ 1⎟ ⎠
3-7 关系的性质
例 设A=⎨1,3,5,7⎬，定义A上的二元关系如下： R=⎨<a,b>|(a－b)/2是整数⎬ 试证明R在A上是自反的和对称的。 证明：∀a∈A，(a-a)/2=0，0是整数，所以 <a,a>∈R。即R是自反的。 ∀a∈A，∀b∈A，<a,b>∈R，(a-b)/2是整数，因为整数的相反数也是 整数，所以(b-a)/2=-(a-b)/2是整数，<b,a>∈R。即R是对称的。 定理3-7.3 设R是X上的二元关系, R是对称的当且仅当R=RC。 证明：设R是对称的，下证R =RC。 <x,y>∈R⇔<y,x>∈R⇔<x,y>∈RC , 所以 R =RC。 设R =RC，下证R是对称的。 <x,y>∈R⇒<y,x>∈RC⇒<y,x>∈R, 所以R是对称的。

无对称的偶对。
表示关系矩阵的主对角线两侧各有一个1且 对称，即有一个对称的偶对。
C1
n(n＋1) 2
n(n＋1) C 2 n(n＋1) 2
表示关系矩阵的主对角线两侧全为1，
C1 ＋ n(n＋ ＋…＋ 2
n(n＋1) C 2 n(n＋1) 2
于是
C0 n(n＋1) 2 ＝
2
n(n＋1) 2
四、反对称性 ⒈ 定义： 若xy(x∈A∧y∈A∧xRy∧yRx→x=y)， 称R是反对称的。 例：设A={ a , b , c , d } R={ < a , b > , < a , c > , < b , b > , <b,d>,<c,c>,<c,d>, < d , d >}
⒉自反关系的关系矩阵的特征
R的关系矩阵的主对角线上的元素均为
1 ，则该关系就不具有自反性；
主对角线上有一个元素不为1，则该关
系就不具有自反性。
⒊ 自反关系的图的特征 自反关系的关系图中，每个顶点都有 自回路，则该关系具有自反性。
二、反自反性 ⒈ 定义：若x（x∈A xRx）则该关系是 反自反的。 ⒉ 具有反自反性的关系的关系矩阵的主对角
2 t1× t2 × … ×tn
五、关系的表示法-----通常有三种表示方法
⒈ 集合表示法： 因为关系也是集合，所以也可以用集合 的表示方法
例：A={ 2, 3,4,6 ,9,12 }上的整除关系
用特征描述法表示为
R＝{ < x , y > | x∈A ∧ y∈A ∧ x|y }
用穷举法表示为
R={ < 2 , 2 > , < 2 , 4 > , < 2 , 6 > ,

当n=3时，25(mod 3)，57(mod 3)。
例3：设X是一个集合，集合的包含于“”是2X上的二 元关系。
8/25
集合与图论 二元关系到n元关系的推广
定义3 设A1,A2,...,An是n个集合，一个 A1A2...An的子集R称为A1,A2,...,An间的n元关系。
每个Ai称为R的一个域。
23/25
集合与图论 关系幂运算的定义及性质
定理6 设X是一个有限集合且X=n，R为X上的任 一二元关系，则存在非负整数s,t使得0≤s<t≤2n2且Rs=Rt。
定理7 设R是X上的二元关系。如果存在非负整 数s,t，s<t，使得Rs=Rt，则
(1)Rs+k=Rt+k，k为非负整数； (2)Rs+kp+i=Rs+i，其中p=t-s，而k,i为非负整数； (3)令S={R0,R,R2,...,Rt-1}，则对任意的非负的整数 q有RqS。
例15：设R,S是集合X上的两个传递关系，问R∪S 是否是传递关系呢？
17/25
集合与图论
运算与性质的关系
自反性 反自反性 对称性 反对称性 传递性
R11
√
√
√
√
√
R1∩R2 √
√
R1∪R2 √
√
R1R2 ×
√
√
√
√
√ ××
√
√×
R1∘R2 √
×
×
××
18/25
集合与图论 3 关系的合成
定义1 设R是A到B的二元关系，S是B到C的二元 关系。R与S的合成是A到C的一个二元关系，记成RS， 并且
显然：R是传递的，当且仅当 ？。 例11： Z上的模n同余关系是不是传递关系？

6
实例
例3 设A＝{1,2,3}, R1, R2, R3是A上的关系, 其中 R1＝{<1,1>,<2,2>}
R2＝{<1,2>,<2,3>}
R3＝{<1,3>} R1 和 R3 是A上的传递关系
R2不是A上的传递关系
7
关系性质的充要条件
设R为A上的关系, 则 (1) R在A上自反当且仅当 IA R (2) R在A上反自反当且仅当 R∩IA= (3) R在A上对称当且仅当 R=R1 (4) R在A上反对称当且仅当 R∩R1IA (5) R在A上传递当且仅当 RRR
11
反对称性证明
证明模式 证明R在A上反对称 任取<x, y> <x,y>R<y,x>R ………..………. x=y 前提 推理过程 结论 例6 证明若 R∩R1IA , 则R在A上反对称. 证 任取<x,y> <x,y>R <y, x>R <x,y>R <x,y>R 1 <x,y>R∩R 1 <x,y>IA x=y 因此 R 在 A 上是反对称的.
15
闭包定义
定义 设R是非空集合A上的关系, R的自反（对 称或传递）闭包是A上的关系R, 使得R满足以 下条件： （1）R是自反的（对称的或传递的） （2）RR （3）对A上任何包含R的自反（对称或传递） 关系 R 有 RR.
一般将 R 的自反闭包记作 r(R), 对称闭包记作 s(R), 传递闭包记作 t(R).
10
对称性证明
证明模式 证明R在A上对称 任取<x, y> <x,y>R ……………..….……. <y,x>R 前提 推理过程 结论 例5 证明若 R=R1 , 则R在A上对称. 证 任取<x,y> <x,y>R <y,x>R 1 < y, x >R 因此 R 在 A 上是对称的.