\(f_S=\sum_{T}g_{S\cup T}h_T\)
\[\begin{aligned}
f_S&=\sum_{T}g_{S\cup T}h_T\\
&=\sum_{T}\sum_{A}g_{A}h_T[S\cup T=A]\\
&=\sum_{S\subseteq A}\sum_{T\subseteq A}g_{A}h_T[S\cup T=A]\\
&=\sum_{S\subseteq A}\sum_{T\subseteq A}g_{A}h_T[A-S\cup T=\varnothing]\\
&=\sum_{S\subseteq A}\sum_{T\subseteq A}g_{A}h_T\sum_{B\subseteq A-S\cup T}(-1)^{|B|}\\
&=\sum_{S\subseteq A}\sum_{T\subseteq A}g_{A}h_T\sum_{S\cup T\subseteq B\subseteq A}(-1)^{|B|-|S\cup T|}\\
&=\sum_{S\subseteq A}\sum_{T\subseteq A}g_{A}h_T\sum_{S\cup T\subseteq B\subseteq A}(-1)^{|B|-|A|}\\
&=\sum_{S\subseteq B}(-1)^{|B|}\sum_{B\subseteq A}g_{A}(-1)^{|A|}\sum_{T\subseteq B}h_T\\
\end{aligned}
\]
推导过程使用了 \([S=\varnothing]=\sum_{T\subseteq S}(-1)^{|T|}\)。
\((-1)^{|B|-|S\cup T|}\) 可以改成 \((-1)^{|B|-|A|}\) 的原因是这样不影响 \(S\cup T\neq A\) 的项互相抵消成 0，唯一不会被抵消的是 \(S\cup T=A\) 的情况，显然不会有影响。
\(f_S=\sum_T g_{S\cap T}h_T\)
\[\begin{aligned}f_S&=\sum_{T}g_{S\cap T}h_T\\&=\sum_{T}\sum_{A}g_{A}h_T[S\cap T=A]\\&=\sum_{A\subseteq S}\sum_{A\subseteq T}g_{A}h_T[S\cap T=A]\\&=\sum_{A\subseteq S}\sum_{A\subseteq T}g_{A}h_T[S\cap T-A=\varnothing]\\&=\sum_{A\subseteq S}\sum_{A\subseteq T}g_{A}h_T\sum_{B\subseteq S\cap T-A}(-1)^{|B|}\\&=\sum_{A\subseteq S}\sum_{A\subseteq T}g_{A}h_T\sum_{A\subseteq B\subseteq S\cap T}(-1)^{|B|-|A|}\\&=\sum_{B\subseteq S}(-1)^{|B|}\sum_{A\subseteq B}g_{A}(-1)^{|A|}\sum_{B\subseteq T}h_T\\\end{aligned}
\]
\(f_S=\sum_{T}g_{S\cap T}h_{S\cup T}\)
\[\begin{aligned}
f_S&=\sum_{T}g_{S\cap T}h_{S\cup T}\\
&=\sum_{U\subseteq S}g_{U}\sum_{S\subseteq A}h_A
\end{aligned}
\]
对于每对 \((U,A)\) 都有唯一的 \(T = U \cup (A\setminus S)\) 与之对应。