识别符号格: 补充解法¶

所有上确界加最小元¶

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

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

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

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

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