发布时间 : 星期四 文章离散数学更新完毕开始阅读
4.4关系的闭包
[定理1]：设R是A上的二元关系，则R∪IA一定是自反的，而且是包含R，具有自反性的最小关系。（其中IA是A上的恒等关系）。
[定义1]：称R∪IA是R的自反闭包，记为r(R)。
证明：对?x∈A，
[推论1]：当且仅当R是自反闭包，R具有自反性。 证明：
(1)R是自反闭包，R=IA∪R?IA ?R； (2)R具有自反性，IA ?R，R∪IA=R. [定理2]：设R是A上的二元关系，则R∪R-1是对称的，包含R的最小关系。 （其中R-1是R的逆关系）。
[定义2]：称R∪R-1是R的对称闭包，记为s(R)。
证明：(1)若
(2)若R’为包含R，且对称的二元关系，
则对?
[推论2]：当且仅当R是对称闭包时，R具有对称性。
证明：(1)R具有对称性，
若
即?
?R-1?R?R∪R-1＝R；
(2)R是对称闭包时，R＝R∪R-1?R具有对称性。
[定理3]：传递闭包t(R)＝R∪R2∪R3∪… 例6：
设A={1,2,3}，R={<1,1>,<1,2>,<2,3>}，求t(R) 。
?110??111???2??3解： R＝001,R＝000＝R ???????000???000???111???23故 t(R)＝R∪R∪R＝001 ????000??t(R)＝｛<1，1>，<1，2>，<1，3>，<2，3>｝
4.5等价关系和偏序关系
[定义1] 等价关系： A上的二元关系R，如果R是(1) 自反的;(2) 对称的;(3) 传递的,称R为等价关系。若
注：等价关系R把Ａ的元素分为若干类，各类之间没有公共元素。确定的R是对集合Ａ进行的划分。 [定义3] 集合的划分：把集合A分为若干子集A1,A2 ,… ,满足：
(1) 当 i ≠ j 时，Ai∩Aj＝? (2) ?x∈A，?i，
使x∈Ai (i＝１，２，…)，
则集合? = {A1，A2，…，An，…} 称为Ａ的一个划分。 注：
(1) ? ? P(A)（A的幂集）；
(2) 当且仅当A = ?，? = P(A)={?}； (3) A非空时，?? P(A). [定理1]：
A在等价关系R下的等价类正是A的一种划分，A的任一种划分，也必有A上的一个等价关系R与之对应。 证明：
R是等价关系， ?x∈A，由R的自反性，
1
y(对称性), 由Ｒ传递性，x～y.由x，y的任意性，故Ai＝Aj与Ai和Aj 为不同的等价类矛盾。 故Ai∩Aj = ?,所以，R完成了等价类的划分。
若A已进行了划分，则构造二元关系R。 (1) ?x∈A，使
(2) 分别对每一等价类内所有两个不同元素x，y，
A＝｛52张扑克｝
R1＝｛
例2：
A＝｛0，1，2，3，4，5｝
R＝｛<0，0>，<1，1>，<2，2>，<3，3>，<1，2>，<1，3>，<2，1>，<2，3>，<3，1>，<3，2>，<4，4>，<4，5>，<5，4>，<5，5>｝
R是等价关系，但不直观，用关系图表示。
三个不连通的图
二元关系R是自反的，对称的，传递的，且把Ａ分成了三个等价类，｛0｝，｛1，2，3｝，｛4，5｝
[定义] 商集：等价关系R将A分成若干等价类，每个类选个代表组成新的集合称为A关于R的商集，表示为A/R。
例：在上例中 A/R＝｛［0］，［1］，［4］｝
[定义] 商集的元素个数（即A在R下的等价类个数）称为R的秩。 例3：
R＝｛
(1) x≡x(mod 3). 自反性
(2) 若x≡y(mod 3)，则y≡x(mod 3). 对称性
(3) 若x≡y(mod 3)，y≡z(mod 3)， 则x≡z(mod 3). 满足传递性。 故R是等价关系。 商集：Z／R＝｛［0］，［1］，［2］｝ 其中，［0］＝｛…，-6，-3，0，3，6，…｝ ［1］＝｛…，-5，-2，1，4，7，…｝ ［2］＝｛…，-4，-1，2，5，8，…｝ [定义] 偏序关系：
Ｒ是Ａ上的二元关系，如果Ｒ满足： (1) 自反的 (2) 反对称的 (3) 传递的 则称Ｒ是Ａ上偏序关系，简称偏序。记作?。 例：
Ａ＝｛１，２，３，４，５，６，７，８，９｝
Ｂ＝｛ａ，ｂ，ｃ｝
Ｒ1＝｛
Ｒ3＝｛
Ｒ={
（1）用矩阵表示偏序关系，不能明显看到 二元关系的特征。
（2）用简化的关系图表示较适合。 简化的关系图：
(1)自反性：每个顶点都有自回路，省去。 (2)反对称性：两个顶点间只可能有一个箭头
从左→右，或从下→上的方向， 从小到大安置顶点，可省略箭头。 (3)传递性：由于有
故只画
2
[定义]：Hasse图
设?是A上的一个偏序关系，如果x?y，则将x画在y下面，且不?z，使x?z，z?y，则x，y间用直线连接。并符合简化的关系图的绘制，称这样得到的关系图为Hasse图。
上例中偏序关系的Hasse图如下：
[定义] 全序：
Ａ上偏序关系Ｒ，如果?x，y∈Ａ，都有x?y，或y?x，则称Ｒ为Ａ上的全序关系。 注：
(1) 全序的含义：Ａ中每两个元素均能比大小，即任何两个元素都相关。 (2) 偏序则是部分有序。
(3) 上例中，Ｒ1是全序，Ｒ2，Ｒ3都是偏序。
如：Ｒ2中，｛１，２，６｝，｛１，２，４，８｝，｛１，３，９｝都排成了序，但２与３，５与７，７与９…，在整除的意义上来说无法排出大小来。 [定义] 偏序集：
集合Ａ及Ａ上的一个偏序关系Ｒ组成的二元组<Ａ，Ｒ>，称为偏序集，记为<Ａ，?Ｒ>或<Ａ，?>。
注： 同一集合上的两个不同的偏序关系，所构成的是两个偏序集， 如：Ｒ1和Ｒ2都定义在Ａ＝｛１，２，３，４，５，６，７，８，９｝上，但<Ａ，Ｒ1>与<Ａ，Ｒ2>显然不是一样的偏序集。 [定义] 全序集：
偏序集<Ａ，?Ｒ>中的偏序关系?Ｒ是Ａ上的全序，则此<Ａ，?Ｒ>称为全序集。 <Ａ，Ｒ1>是全序集。显然，全序
3
集是偏序集的特例。又如：（－∞，＋∞）实数全体，在?下是全序集；<Ｎ，?>当然也是全序集。
[定义] 极大元与极小元：
设
B＝｛２，３，４，５，６，７，８，９｝ 则B中极大元：８，６，９，５，７ 极小元：２，３，５，７
注：极大元，极小元并不要求唯一，且同一元素，可以既是极大元，又是极小元，如５，７。 注：
极大元，极小元必须是子集B中的元素。 [定义] 最大元与最小元：设
结论：
子集B中是不存在最大元（最小元）的。 例： A＝｛ａ，ｂ，ｃ｝,
Ｒ3＝｛
结论：B存在最小元? ，没有最大元。 注：最大元（最小元）本身应属于子集B，且与B中任一元素都有关系。
[定义] 上界与下界：
设
(1) 上例中，B无最大元，但存在B的上界｛ａ，ｂ，ｃ｝。
(2) ?为B的最小元，也是B的下界。 (3) 最大（小）元是B的一个上（下）界。 (4) 上（下）界可以不唯一，也可以不存在。 [定义] 上确界与下确界：
设
如果存在上（下）确界，则上（下）确界一定是唯一的。 例：
{ｂ，ｃ}与{ａ，ｂ，ｃ}是B’的上界，{ｂ，ｃ}是B’的上确界。 *注：存在上（下）界，并不一定存在上（下）确界。
例：ｐ＝｛ａ，ｂ，ｃ，ｄ，ｅ｝ Ａ＝｛ａ，ｂ，ｃ｝，<ｐ，?>
一的y?ranF使xFy成立，则称F为函数。
1、设A,B为集合，若f 为函数，且domf =A，ranf ?B，则称f 为从A到B的函数，记作f :A→B.
A的子集A’的象:
设f :A?B, A’?A, 则A’在f下的象是 F (A’)={f (x)| x?A’}.
当A’=A时，称f (A’)=f (A)=ranf 是函数的象。
2、设A,B为集合，所有从A到B的函数构成集合BA，读做“B上A”，即
BA ={f | f :A→B}.一般的，若|A|=m, |B|=n, m,n不全是0，则|BA|=nm。 如，A={0, 1, 2}, B={a, b}，
BA= {f 1, f 2, f 3, f 4, f 5, f 6, f 7, f 8 }.
3、 设函数f :A?B，若ranf =B，则称f 是满射的（或映上的）。
例：设函数f :A?B，其中A={a, b, c, d}, B={1, 2, 3}，f (a)=3, f (b)=2, f (c)=1, f (d)=3. 问：f 是满射的吗？
a c f
结论：
(1)ｄ，ｅ是Ａ的上界。
(2)ｄ与ｅ无法比大小，不存在上确界。 (3)Ａ的下界不存在，不存在下确界。
4.6函数的定义和性质
设F为二元关系，若?x?domF都存在唯
4
4、设函数f :A?B，若对于任何的x1, x2?A, x1?x2, 都有f (x1) ?f (x2)，则称f 是单射的（或一对一的）。 例： 设函数f :A?B，其中A={a, b, c, d}, B={1, 2, 3, 4, 5}，f(a)=4, f(b)=5, f(c)=1, f(d)=3. 问：f是单射的吗？
· ··b ·· 1 2 3