在讨论 Lamport 的同步算法时，“partial ordering” 和 “total ordering” 是什么意思？

Question

我的理解是，部分排序和全序是两组规则。

部分排序有三条规则：
(1) 如果a和b是同一进程中的两个事件，并且a在b之前发生，则a -> b。
(2) ...
(3) ...

那么，什么是全序呢？

为什么要这样命名？

- user366312

---

维基百科中的“影响部分”可能会有所帮助。通常，我认为总排序意味着每对元素在排序关系方面是可比较的。 - גלעד ברקן

Answer 1

这些名称源于一个偏序中并非所有元素都可以比较，而在一个全序中，所有元素都可以比较的事实：

对于集合元素的偏序是由三个属性定义的，这些属性必须对于所有元素a，b和c成立：

• 自反性：a ≤ a
• 反对称性：如果a ≤ b并且b ≤ a，那么a = b
• 传递性：如果a ≤ b并且b ≤ c，那么a ≤ c

此定义捕捉了对事物排序的常见直觉本质：每个事物与其本身相同大小，它可以比另一个“更小”，但是然后另一个不比自己“更小”。最后，如果一件事物比另一件事物“更小”，后者比第三件事物“更小”，则它也比第三件事物“更小”。

总序是具有附加属性的偏序：

• Connexity: a ≤ b 或者 b ≤ a

这个定义说明，在一个全序中，任何两个事物都是可比较的。而在偏序中，一个事物不需要比另一个“小”，反之亦然；但在全序中，每个事物要么比另一个“小”，要么比另一个“大”。

- michid

---

如果我正确理解了这个答案，“偏序物可能有两个或更多相等的元素”。然而，我怀疑自己没有正确理解。我是完全误解了这个答案，还是至少在正确的方向上有些接近？ - FreelanceConsultant

@自由职业顾问，部分订单可能有许多元素（或根本没有元素）是相等的。但这不是重点。 部分订单和总订单之间的关键区别在于，在后者中，所有元素都可以互相比较，而在前者中，有些元素与其他元素不可比较。如果将订单可视化为一棵树，其中项目小于其父项，则来自不同分支的项目是无法比较的。 在总订单的情况下，该树仅为一个单一线性分支。 - michid

@自由职业顾问，以时间间隔为例：如果一个时间间隔能够包含另一个时间间隔，则可以说一个时间间隔比另一个小。这是一种偏序关系，因为交叉但无法相互包含的时间间隔无法进行比较。 - michid