是否存在算术/布尔函数F、G满足(A + C)&(B + C) = F(A,B)+G(C)

反证法推导过程 #

• 先固定A=0、B=0，原式左侧变为(0 + C) & (0 + C) = C，代入等式可得：

  C = F(0,0) + G(C)
  

  其中F(0,0)是仅由A、B取值决定的常数，因此可推导出G(C) = C - K，K为固定常数（K=F(0,0)）。
• 再取另一组固定A、B值验证，比如A=1、B=2，此时原式应为：

  (1 + C) & (2 + C) = F(1,2) + G(C)
  

  把上面得到的G(C)代入，整理可得：

  (1 + C) & (2 + C) - C = F(1,2) - K
  

  等式右侧是和C完全无关的定值，我们代入不同C值验证左侧：
  • C=0时，左侧为1 & 2 - 0 = 0
  • C=1时，左侧为2 & 3 - 1 = 2 - 1 = 1
• 两个不同C值得到的左侧结果不相等，和“右侧为定值”的结论矛盾，因此不存在符合要求的函数F和G。

本质原因 #

按位与运算和普通加法混合时，加法产生的进位会跨比特位影响结果，C的取值不仅会单独贡献偏移，还会改变A+C、B+C运算过程中的进位逻辑，进而影响按位与的结果，这种耦合效应无法被拆解为仅含A、B的项和仅含C的项的加和。

内容的提问来源于stack exchange，提问作者Taha Khabouss