# 识别符号格: 补充解法

## 所有上确界加最小元

这个判据来自出题人，Codex（GPT-6）整理了 C++17 程序并补充有限格的证明。见 [alternative.cpp](alternative.cpp)，符号等价类与上确界扫描见[主题解](solution.zh.md)。

先检查反身性、传递性及任意两个符号的上确界。然后寻找一个全一行：它代表一个不大于所有元素的最小元。以上条件全部满足即输出 `Y` ，无需再逐对检查下确界。

若输入表示一个有限非空格，对全部元素依次取下确界即可得到全局最小元，所有二元上确界也当然存在，故条件必要。

反过来，在符号等价类构成的有限偏序中，考虑任意两个元素 $x,y$ .它们的共同下界集合非空，因为至少包含最小元。将所有这些共同下界依次取上确界。每一步的结果仍不大于 $x$ 和 $y$ ：它们都是被合并元素的共同上界，而上确界不大于任何共同上界。最后得到的元素既是共同下界，又不小于所有共同下界，因此是下确界。于是所有二元下确界存在，偏序是格。这里的有限性和非空下界集合缺一不可。

上确界检查为 $O(n^3)$ ，寻找全一行为 $O(n^2)$ ，总时间 $O(n^3)$ 、空间 $O(n^2)$ .省去对偶的逐对扫描会减少实际工作量，实测也更快，但渐进复杂度不变。