作者并不是很懂线性代数相关的一些术语，所以可能本文很多东西说法并不是很标准，不过从逻辑上应该是足够严谨的。
符号约定：
- 本文线性基均指 异或线性基。
- 本文向量均指 \(01\) 向量。
- 一个大小为 \(n\) 线性基为 \(n\) 个大小为 \(n\) 的向量构成。
- 一个向量 \(p_i=(p_{i,1},p_{i,2},\cdots,p_{i,n})\)，\(p_{i,j}\in\{0,1\}\)。
- 一个线性基 \(P=(p_i,p_2,\cdots p_n)\)。特别的，我们认为：
- 若 \(p_{i,i}=0\)，则 \(\forall j\in[1,n]\) 有 \(p_{i,j}=0\)。
- 若 \(p_{i,i}=1\)，则 \(\forall j\in[1,i)\) 有 \(p_{i,j}=0\)。
- 记 \(S_B\) 表示线性基 \(B\) 长成空间中所有元素的集合。
- 对于向量 \(a,b\)，我们称 \(a<b\) 当且仅当：
- 存在 \(k\in[1,n]\) 使得 \(a_k<b_k\) 且 \(\forall i\in[1,k)\) 有 \(a_i=b_i\)。
- 定义向量异或运算 \(\oplus\) 为：
- \(a\oplus b=(a_1\oplus b_1,a_2\oplus b_2,\cdots,a_n\oplus b_n)\)。
- 记 \(F_{\max,B}(x)\) 表示 \(\max\limits_{y\in S_B}{x\oplus y}\)。
- 记 \(F_{\min,B}(x)\) 表示 \(\min\limits_{y\in S_B}{x\oplus y}\)。
- \(\operatorname{not}(x)=(\neg x_1,\neg x_2,\cdots,\neg x_n)\)。
结论：
- \(F_{\max,B}(x\oplus y)=F_{\max,B}(x)\oplus F_{\min,B}(y)\)。
证明：
考虑一个我们求 \(F_{\max,B}(x)\) 的过程：
- 令 \(i\gets 1\)。
- 若 \(x_i=0\)，则令 \(x\gets x\oplus B_i\)。
- \(i\gets i+1\)，若 \(i=n\) 则停止，否则回到第二步。
这里有一个非常棘手的操作是：我们进行第二步操作后，\(x\) 后面的值会发生变化！也就是存在某个 \(j\) 最初 \(x_j=1\)，后来变成了 \(x_j=0\)，也就是我们没法在最开始就确定每个位置是否会进行操作！
但是我们断言：必然存在一个线性基 \(B'\) 满足：
- \(S_B=S_{B'}\)。
- 对于任意 \(1\le i<j\le n\) 且 \(B'_{i,j}=1\) 满足 \(B'_{j,j}=0\)。
也就是我们对于线性基 \(B'\) 可以在最初确定哪些位置需要进行操作（所有 \(x_i=0\) 的位置）。
尝试给出构造性证明，考虑归纳：
- 对于 \(i=n\) 显然满足条件。
- 当前对于 \(i=k+1\sim n\) 满足条件，考虑取出所有 \(B'_{i,j}=1\) 的位置 \(j\)，令 \(B'_i\gets B'_i\oplus B'_j\) 即可。
最终得到的 \(B'\) 显然满足条件。
且 \(F_{\max,B}(x)=F_{\max,B'}(x)=x\oplus(\overset{n}{\underset{1\le i\le n,x_i=0}{\oplus}} B'_{i})\)。
我们记 \(H_{\max,B}(x)=\overset{n}{\underset{1\le i\le n,x_i=0}{\oplus}} B_{i}\)，同理有 \(H_{\min,B}(x)=\overset{n}{\underset{1\le i\le n,x_i=1}{\oplus}} B_{i}\)。
即得 \(F_{\max,B}(x)=x\oplus H_{\max,B'}(x)\) 和 \(F_{\min,B}(x)=x\oplus H_{\min,B'}(x)\)。
考虑刻画 \(F_{\max,B}(x\oplus y)\)：
\[\begin{aligned} & F_{\max,B}(x\oplus y)\\ & = (x\oplus y)\oplus H_{\max,B}(x\oplus y)\\ & = (x\oplus y)\oplus H_{\min,B}(\operatorname{not}(x\oplus y))\\ & = (x\oplus y)\oplus H_{\min,B}(\operatorname{not}(x)\oplus y)\\ & = (x\oplus y)\oplus \color{red}{H_{\min,B}(\operatorname{not}(x))\oplus H_{\min,B}(y)}\\ & = (x\oplus H_{\min,B}(\operatorname{not}(x)) \oplus (y\oplus H_{\min,B}(y))\\ & = (x\oplus H_{\max,B}(x) \oplus (y\oplus H_{\min,B}(y))\\ & = F_{\max,B}(x)\oplus F_{\min,B}(y) \end{aligned} \]故证毕！
注意其中标红的部分，手玩一下真值表可以说明，而 \(H_{\max,B}\) 就没有这样好的性质，这也就是我们强行扯出了 \(\min\) 的意义。
标签：le,min,基的,max,异或,线性,oplus,operatorname From： https://www.cnblogs.com/lsj2009/p/18539747