计算机问题求解 – 论题1-9 - 关系及其性质 2018年11月13日.

Presentation on theme: "计算机问题求解 – 论题1-9 - 关系及其性质 2018年11月13日."— Presentation transcript:

1 计算机问题求解 – 论题 关系及其性质 2018年11月13日

2 Part I 二元关系的数学模型

3 问题1： 书上特别用一个例子强调区分“作 为集合元素的集合”与“作为集合 的子集的集合”，你理解其含义吗？
对任何xP(AB), xA, xB

4 问题2： 书上说如下关于“序偶”的定义是 informal，为什么？怎样才能得到 “formal definition”?

5 问题3: 你认为数学中定义的“二元关 系”是否合理，为什么？

6 若A=B, R中存在序列：<x1,x2>, <x2,x3>,…,<xn-1,xn>
二元关系和有向图 有向图 (VD , ED ) 顶点集： VD 有向边集： ED 顶点x,y相邻 图D中存在从 x1 到 xn 的长度为 n-1的通路 关系 RAB 论域：AB 有序对集合 元素x,y满足关系R 若A=B, R中存在序列：<x1,x2>, <x2,x3>,…,<xn-1,xn>

7 用有向图表示的二元关系 Digraph representation is used only for relations on one set. A={1,2,3,4} R={(1,1), (1,2), (2,1), (2,2), (2,3), (2,4), (3,4), (4,1)} 2 1 3 For node 1, the in-degree is 3, out-degree is 2 4

8 用矩阵表示二元关系/有向图 A={a1, a2, a3} B={b1, b2, b3, b4} R={(a1, b1), (a1, b4),
(ai, bj)R if and only if: mi,j=1

9 问题4： 你觉得下面的表示“奇怪”吗？ 自然数集合上: “<”  “=” = “” 自然数集合上: “”  “” = “=”
自然数集合上: “<”  “=” = “” 自然数集合上: “”  “” = “=” 自然数集合上: “<”  “>” = 

10 关系的“复合”运算 关系的复合运算 运算法则： 如果R1AB, R2BC, 则： R1与 R2的复合关系R1°R2  AC
且： R1°R2 = {<x,z>|xA, zC, 且存在 yB，使得<x,y> R1, <y,z>R2}

11 关系的复合运算：例子 设A={a,b,c,d}, R1, R2为A上的关系，其中： 则：
R1 = {<a,a>,<a,b>,<b,d>} R2 = {<a,d>,<b,c>,<b,d>,<c,b>} 则： R1 R2 = {<a,d>,<a,c>,} R2 R1, = {<c,d>} R12 = {<a,a>,<a,b>,<a,d>} R23 = {<b,a>,<c,c>,<b,c>,<b,d>,<c,b>} 很容易证明：关系的复合运算满足结合律。 “乘幂”的定义： R1=R, Rn=Rn-1◦R

12 问题5： 你是否能从集合的角度解释关系的“性质”？

13 自反性 集合A上的关系R: 设 A={1,2,3}, RAA 自反：定义为：对所有的 aA, (a,a)R
注意区分”非”与”反” 设 A={1,2,3}, RAA {(1,1),(1,3),(2,2),(2,1),(3,3)} 是自反的 {(1,2),(2,3),(3,1)} 是反自反的 {(1,2),(2,2),(2,3),(3,1)} 既不是自反的，也不是反自反的

14 对称性 集合A上的关系R： 对称的：定义为：若 (a,b)R, 则 (b,a)R
反对称的：定义为：若(a,b)R 且(b,a)R ，则a=b 强反对称的：定义为：若 (a,b)R 则 (b,a)R 设 A={1,2,3}, RAA {(1,1),(1,2),(1,3),(2,1),(3,1),(3,3)} 是对称的 {(1,2),(2,3),(2,2),(3,1)} 是反对称的 {(1,2),(2,3),(3,1)} 既是反对称的，也是强反对称的

15 传递性 集合A上的关系R： 设 A={1,2,3}, RAA
传递的：定义为：若 (a,b)R, (b,c)R, 则 (a,c) R 设 A={1,2,3}, RAA {(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,3)} 传递的 {(1,2),(2,3),(3,1)} 是非传递的 {(1,3)}和  均为传递关系

16 问题6： 向一个关系中添加元素， 对其性质有什么影响？

17 Part II 等价关系与偏序关系

18 问题7： 可能在初等数学中你遇到最多的 关系是“等于”和“不大于”。 你能归纳一下它们各自满足的性 质吗？

19 等价关系的定义 满足性质：自反、对称、传递 “等于”关系的推广 例子 对3同余关系: RZZ， xRy 当且仅当 是整数。
RNN， xRy 当且仅当 存在正整数k,l，使得xk=yl。 自反: 若x是任意正整数，当然xk=xk ; 对称：若有k,l, 使xk=yl；也就有l,k, 使yl=xk； 传递：若有k,l, 使xk=yl；并有l,m, 使yl=zm；则有k,m, 使xk=zm

20 等价类 R是非空集合A上的等价关系，xA，等价类[x]R={y|yA  xRy} 每个等价类是A的一个非空子集。 例子：对3同余关系: RZZ， xRy 当且仅当 　　　　 是整数。 ３个等价类：[0]={…, -6, -3, 0, 3, 6, 9, …}; [1]={…, -5, -2, 1, 4, 5, 7, …}; [2]={…, -4, -1, 2, 5, 8, 11, …}

21 等价类的代表元素 对于等价类[x]R={y|yA  xRy}，x称为这个等价类的代表元素．
其实，该等价类的每个元素都可以做代表元素：若xRy，则[x]=[y] 证明：对任意元素t, 若t[x], 则xRt, 根据R的对称性与传递性，且xRy, 可得yRt, 因此 t[y], [x][y]; 同理可得[y][x]

22 (a, b)R(c,d) 当且仅当 a+d=b+c
商集 R是非空集合A上的等价关系，xA，则其所有等价类的集合称为商集，A/R 集合A={a1,a2, …, an}上的恒等关系IA是等价关系，商集A/IA={{a1}, {a2},…, {an}} 定义自然数集的笛卡儿乘积上的关系R:　 (a, b)R(c,d) 当且仅当 a+d=b+c 证明这是等价关系，并给出其商集．

23 集合的划分 A 集合A的 分划 , , 是A的一组非空子集的集合，即 (A), 且满足： A6
1. 对任意 xA, 存在某个 Ai, 使得 xAi. A A6 A1 A5 A2 A4 2. 对任意 Ai, Aj, 如果 ij, 则： A3

24 由等价关系定义的分划 假设R是集合A上的等价关系，给定aA, R(a)是由R 所诱导的等价类。 Q={R(x)|xA}是相应的商集。
对任意 a,bA (a,b) R 当且仅当 R(a)=R(b), 同时 (a,b) R 当且仅当 R(a)R(b)=

25 商集即分划 – 证明 不相等的等价类必然不相交。换句话说，有公共元素的任意两个等价类必然相等。 证明：
假设R(a)R(b)Ø, c是任一公共元素。 根据等价类的定义，<a,c>R, <b,c>R 对任意xR(a), <a,x>R, 由R的传递性和对称性，可得<c,x>R, 由此可知<b,x>R, 即xR(b), R(a)R(b) 同理可得：R(b)R(a)。因此: R(a)=R(b)

26 根据一个分划定义等价关系 A 给定 A 上一个分划，可以如下定义A 上的等价关系 R : A6 x,yA, (x,y)R 当且仅当:
Ex. (x,y)R (y,z)R (x,z)R (x,x)R etc. A6 A1 A5 A2 x A4 y 显然，关系 R 满足自反性、对称性、传递性。因此：R 是等价关系。 z A3

27 问题8： 你能否总结一下：等价关系与 集合的分划之间有什么联系？

28 等价关系与划分：一个例子 建立1000个集合, 每个集合包括1至2000之间的一个奇数以及该奇数与2的k次幂的乘积, 但最大不超过2000。可以证明这1000个集合的集合是{1,2,3,..., 2000} 的一个划分。注意任意两个1到2000之间的正整数x,y在同一划分块中当且仅当x/y=2k。(k为整数)。 定义集合{1,2,3,..., 2000}上的一个关系R，任意x,y，xRy当且仅当x/y=2k。易证这是一个等价关系。其商集即上面的划分。

29 问题9: 等价关系的关系图以及 关系矩阵有什么特征?

30 问题10： 你能否用等价关系以及偏序关 系的概念来解释一下数学中的 “推广”和“特例”个含义？

31 用哈斯图表示偏序 {a,b,c} {a,c} {b,c} {a,b} {a} {c} {b} 

32 连续与离散 实数集上的“不大于”关系 离散集合上的偏序 任意两个元素均可比； 任何开区间没有极大元；
任何闭区间有唯一极大/小元， 那也是最大/小元； 对任意实数a,b(a<b), [a,b], [a,b), (a,b], (a,b)都有上界、下界、最 小上界、最大下界 最小上界、最大下界一定是唯 一的。 离散集合上的偏序 3和4不可比； 有2个“极大元” 任何有限的偏序集 一定有极大/小元； 对任意的非空子集，上界、 下界、最小上界、最大下 界都可能有，也可能没有 如果有最小上界、最大下 界，一定是唯一的。 8 4 6 2 12 1 3

33 问题11: 你是否能用次序关系中“最 小上界”的概念来解释有理 数和实数的差别？

34 问题12： 已经证明了任何两个不相等的 实数之间必有有理数，是否任 何两个不相等的有理数之间必 有无理数？如果是，你有什么 联想吗？

35 问题13： 在偏序集中是否有可能讨论某 种子集，象等价关系下的分划 那样？

36 问题14： 有没有什么关系，既是等价 关系，又是偏序关系？

37 课外作业 UD 10.2, 10.4, 10.5, 10.8; UD 11.3, ; UD 12.10, 12.3(b), 12.16, 12.20, 补充题：对于集合A上的关系R, 证明下列结论： R是自反的 iff. IAR; (IA={(a,a)|aA}, 称为A上的“恒等关系”） R是对称的 iff. R=R-1; (R-1={(a,b)|(b,a)R}, 称为R的“逆关系”) R是传递的 iff. RnR UD project 27.4(选做)