反演定理

定义

在逻辑代数中，反演定理讨论的是如何由一个逻辑式直接写出它的反函数。按照定理的表述，对任意一个逻辑式 Y，把逻辑式中的“与”改成“或”、“或”改成“与”，常量 0 与 1 对调，每个原变量取反、每个反变量还原为原变量，得到的新逻辑式就是 Y 的反函数，记作 $\overline{Y}$。^[1] 这条规则也被称为反演规则或求补规则。^[2]

德·摩根定律是反演定理最简单的形式。以两个变量为例，$\overline{A+B}=\overline{A}\cdot\overline{B}$，$\overline{A\cdot B}=\overline{A}+\overline{B}$，即“或”的非等于各变量“非”的“与”，“与”的非等于各变量“非”的“或”。^[2] 反演定理把这一关系扩展到含任意多个变量和更复杂运算组合的逻辑式，所以被看作德·摩根定律的推广，可用于对布尔表达式整体取反。^[2]

原理

反演定理的操作可以概括为三类替换同时进行：运算符“与”与“或”互换，常量 0 与 1 互换，参与运算的变量取反。^[3] 由于逻辑变量只有 0 和 1 两种取值，变量取反相当于把它在真值表中的取值整体对调，替换后得到的新逻辑式即为原式的反函数。^[2]

例如对 $Y=A(B+C)+CD$ 求反函数时，先把其中的“或”项加上括号，再逐项做替换，可得到 $\overline{Y}=(A'+B'C')(C'+D')$。 香农把这条规则概括为：把每个变量换成它的反，并交换“+”与“·”两种运算，就能得到任意函数的“非”。^[4] 与逐层使用德·摩根定律相比，这种一次性的替换方式简化了复杂表达式的求补过程。^[4]

发展历程

反演定理建立在德·摩根定律之上。德·摩根定律以 19 世纪英国数学家德·摩根的名字命名，在集合论中表现为并集的补等于补集的交、交集的补等于补集的并。^[2]

20 世纪 30 年代，克劳德·香农在麻省理工学院攻读硕士期间，把布尔代数与开关、继电器电路对应起来，用代数方法分析和化简电话交换设备中的复杂电路。^[5] 他给出的做法是：把每个变量换成它的反，并交换“+”与“·”运算，就能得到任意函数的“非”，这一步后来被概括为反演定理的核心内容。^[4]

在中文的数字电路与逻辑代数教材中，这条规则通常称为反演定理或反演规则，与代入定理、对偶定理并列为逻辑代数的基本定理。^[3]

应用

反演定理最直接的用途是求逻辑函数的反函数，即补函数，并配合公式化简逻辑表达式。^[2][3] 在组合逻辑设计中，先求出补函数有助于把表达式改写成便于用与非门等器件实现的形式。^[2]

在工程设计中，该定理被用于具体电路的优化。有研究以核电厂保护系统的 4 取 2 数字逻辑电路为例，比较直接设计法与基于反演定理的设计法，最终使相关电路比原电路减少了一块芯片，并简化了印制电路板设计。^[6]

在理论分析与教学中，反演定理也被用来研究逻辑函数标准形式的性质。有文献在分析最小项之和、最大项之积两种标准形式的基础上，运用反演定理和对偶定理研究最大项与最小项的性质。^[7]

局限

运用反演定理时必须保持原函数的运算次序。变换要遵循先括号内、再“与”、最后“或”的优先顺序，原来的“与”项在变成“或”项后需要加括号，否则写出的表达式可能与原式的补函数不等价。^[8][3]

非号的处理是另一个容易出错之处。只有单个变量上方的反号才参与原变量与反变量的互换；位于两个及以上变量之上的公共非号应保持不变，只需把它所辖的式子按定理逐项变换。^[1][8]

“反演定理”这一名称在不同数学分支中含义并不相同。在几何学，尤其是复分析与经典几何中，它指基于一个圆或球把点映射为反演点的变换规则及其性质；在形式逻辑与证明论中，它又指构成反证法基础的推理规则。使用这一名称时需要结合所在分支判断所指内容。^[2]

参见

• 德·摩根定律 —— 反演定理的基础，反演定理是它向复杂逻辑式的推广。

• 对偶定理 —— 与反演定理形式相近、常一并使用的逻辑代数规则。

• 代入定理 —— 逻辑代数中与反演定理并列的另一条基本运算规则。

• 布尔代数 —— 反演定理所属的代数系统，又称逻辑代数。

• 反演变换 —— 几何学中关于圆或球的变换，名称相近而含义不同。

• 逻辑函数 —— 反演定理作用的对象，其取值只有 0 和 1。