偏序关系

作者: madao756 | 来源:发表于2019-11-09 14:18 被阅读0次

偏序关系
离散数学
偏序(cdq bitset)
事务si和ssi隔离级别
Dilworth定理
JVM 先行发生原则（happens-before）
格
Happens-Before规则与DCL失效原因分析
220103 心理测评练习
人工智能学习笔记-Day07

前言：到了二元关系中最后一部分，非常非常抽象，但是理解了就还好，我们一步一步来

0X00 「偏序关系」的基本定义

我们先回到最初的定义：

假设 R 是集合 A 上的关系，如果R是自反的、反对称的和传递的，则称 R 是 A 上的一个偏序，记做 $\leqslant$ 。设 $\leqslant$ 为偏序关系，如果 $<x, y> \in \leqslant$ ，则记做 $x \leqslant y$ ，读作 x 小于等于 y。

这个非常抽象，我们举个例子：

假设我们有这样的集合 $A = \{1, 2, 3\}$ R 是 A 上的小于等于关系也就是 $R = \{<x, y>| x ,y \in A \wedge x \leq y\}$

所以 $R = \{<1, 2>, <2, 3>, <1, 3>, <1, 1>, <2, 2>, <3, 3>\}$

我们画出他的关系图：

显然他是自反的（环）、反对称的（无双向边）、传递的

不知道大家看到这里的大家有没有理解到偏序关系的本质：

偏序关系定义了一种方向，只能正着，反证就不行！

比如这里的小于等于就是只有一种方向，可以 $1 \leq 2$ 就不能 $2 \leq 1$

至此，我们引出下一个定义可比：

存在这种偏序关系的就叫做可比

由于这种顺序结构，我们可以用哈斯图来表示偏序关系

假设 $A = \{1, 2, 3\}, \leqslant 是 A 上的「小于等于」关系，则有$

$\leqslant \ = \{<1, 2>, <1, 3>, <2, 3>, <1, 1>, <2, 2>, <3, 3>\}$

画出哈斯图：

这种自底向上的图就是哈斯图

0X01 「偏序集」的基本定义

理解了偏序关系的基本定义以后，我们就很容易理解偏序集

我们把集合 A 和 A 上的偏序关系 $\leqslant$ 一起称作偏序集，记做 $<A, \leqslant>$

0X02 「偏序集」中的特殊元素

最小元和最大元

我们看到这张图片，最大元就是 $a, b, c\$ 最小元就是 $\emptyset$

所以直观来说最大元 就是“最大”的那个，在哈斯图中最上面的

相反最小元就是“最小”的那个，在哈斯图图中最小的

而在这张图中：

而这张图就不存在最大元只存在最小元因为 11 9 12 8 10 7 之间就不可比

极小元与极大元

搞清楚了最大元和最小元，我们继续，还是回到这张图上：

里面的极大元是 11 9 12 8 10 7，极小元只有 1。

极大元的意思就是在可比的那一条链中最大的，极小元的意思就是在可比的那一条链中最小的

上界与下界

之前的概念只在一个集合中，而谈到上下界就必须涉及到两个集合了，现在我们给出定义：

设 $<A, \leqslant> 为偏序集，B \subseteq A, y \in A$

若 $\forall x (x \in B \rightarrow x \leqslant y)$ 则 y 是 B 的上界
若 $\forall x(x \in B \rightarrow y \leqslant x)$ 则 y 是 B 的下界

假设 $A = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12\}\ B = \{2, 3, 6\}$ ，定义了一个偏序关系并有以下哈斯图：

则 B 的上界就是 $\6, 12\$

由于 2, 3 之间不可比，所以B 的下界只有 $1$

上确界与下确界

如果能够理解上界和下界的话，上确界与下确界就更好理解了，简单来说

上确界就是上界中“最小”的那个
下确界就是下界中“最大”的那个

还是上面那个例子，B 的上界是 $6, 12$ , 其中“最小”的就是 6。所以 B 的上确界就是 6。

反之 B 的下确界就是 1。

二元关系就结束了。。。

偏序关系
前言：到了二元关系中最后一部分，非常非常抽象，但是理解了就还好，我们一步一步来 0X00 「偏序关系」的基本定义 ...
离散数学
偏序：在整数集中定义偏序：若a能整除b，我们就记为a≺b显然它满足序公理。但整数集中，不是任何两个数都存在整除关系...
偏序(cdq bitset)
题目链接:三维偏序 cdq分治: 题目链接:五维偏序
事务si和ssi隔离级别
rr隔离级别：有幻读但无写偏虚 si快照隔离级别：有写偏序但无幻读，写偏序问题的规避留给应用避免，应用使用sele...
Dilworth定理
狄尔沃斯定理(Dilworth's theorem)亦称偏序集分解定理，其定义是：对于任意有限偏序集，其最大反链中...
JVM 先行发生原则（happens-before）
1. 什么是先行发生原则（happens-before）先行发生是Java内存模型中定义的两项操作之间的偏序关系...
格
一, 格的基本定义和性质定义偏序集定义: 偏序集中对任意两个元a, b, 在L中都存在一个元是他们...
Happens-Before规则与DCL失效原因分析
先行发生是Java内存模型中定义的两项操作之间的偏序关系，如果操作A先行发生于操作B，其实就是说在发生操作B之前，...
220103 心理测评练习
从始至终，我们认真回答的只有一套问卷：生活本身。除此之外，所有量表都太过扁平，并追求不可及的偏序关系。每一次抽象和...
人工智能学习笔记-Day07
链式偏导每条关系链的偏导之和。链式法则复杂关系链演示x的偏导简单的链式举例链式举例梯度算符，拉普拉斯算法偏...