# 识别符号格: 题解

## 思路与贡献

标准程序保留出题人的反身性、传递性及逐对检查上确界和下确界的方法。Codex（GPT-6）整理 C++17 实现，用转置矩阵复用上下界检查，并补全符号别名与候选扫描的证明。程序见 [std.cpp](std.cpp)。出题人的另一种判据见[所有上确界加最小元](solution-alternative.zh.md)。

不能直接要求符号关系反对称：不同符号可以表示同一元素。首先检查 $A_{i,i}=1$ ，以及对于所有三元组，若 $A_{i,j}=A_{j,k}=1$ ，则 $A_{i,k}=1$ .这是反身性与传递性。

## 为什么可以不显式合并符号

对满足以上两条的关系，定义 $i\sim j$ 当且仅当 $A_{i,j}=A_{j,i}=1$ .这是等价关系。传递性保证等价符号对所有其他符号的入关系和出关系一致，因此等价类上的关系有良好定义，并且满足反对称性，构成偏序。

任何合法表示都必须把互相关联的两个符号映射为同一元素；映射为同一元素的两个符号也必定互相关联。因此这些等价类正好就是所需元素。可以直接在符号矩阵上检查界，不必显式建立商集。一个上确界可能有多个符号代表，这不影响元素意义上的唯一性。

## 对一对符号寻找上确界

固定 $i,j$ ，扫描所有共同上界 $k$ ，即 $A_{i,k}=A_{j,k}=1$ .维护候选 $c$ ：没有候选时取 $k$ ；若 $A_{k,c}=1$ ，就把候选改为 $k$ .

如果上确界 $u$ 存在，扫描到它时，它不大于当前候选，所以会成为候选。此后能替换它的共同上界只能与它等价。因此最后的候选一定代表上确界。

但在没有上确界时，扫描仍可能留下一个候选，所以必须再次扫描并检查 $A_{c,k}=1$ 对每个共同上界 $k$ 都成立。若没有共同上界，或者这个检查失败，就判为非法。若检查通过，候选本身是共同上界并且不大于所有共同上界，恰好满足定义。

下确界完全对偶。将矩阵转置后，用同一个函数检查所有上确界，相当于检查原偏序的所有下确界。两种界都存在才输出 `Y` .

## 复杂度

反身性检查 $O(n)$ ，传递性检查 $O(n^3)$ ；每对符号用两次线性扫描检查上确界，下确界同理，因此总时间 $O(n^3)$ 、空间 $O(n^2)$ .多组总时间为 $O(T+\sum n^3)$ .全一矩阵会被正确识别为只有一个元素的格。