学习目标：
完成本课后，学生将能够：

1. 回忆文字以及合取范式和析取范式的定义。
2. 识别CNF和DNF表达式的结构。
3. 使用CNF或DNF简化命题逻辑表达式。

目录
文字定义
范式定义
范式定理

命题逻辑的一个有趣且有用的结果与范式有关。要深入探讨这些问题，我们首先需要回顾一些概念。

文字定义

文字是任何原子表达式或原子表达式的否定。基于此，我们谈论正文字或负文字，取决于原子表达式是否有否定前缀。例如：A 是一个正文字，而 \neg A 是一个负文字。

范式定义

一个表达式 F 在范式中是合取范式（CNF），当它可以表示为文字的析取的合取形式，即：

\displaystyle F=\bigwedge_{i=1}^n \left( \bigvee_{j=1}^m L_{ij}\right)

同样，若一个表达式表示为文字合取的析取形式，则为析取范式（DNF）：

\displaystyle F=\bigvee_{i=1}^n \left(\bigwedge_{j=1}^m L_{ij}\right)

范式定理

所有命题逻辑表达式 都等价于CNF和DNF表达式。

证明：

这可以通过对公式 F 复杂性的归纳进行证明。

• 初始情况：如果 F 是一个原子表达式，那么它可以同时以CNF和DNF表示，因为：F\equiv F_D \equiv F_C，其中 F_C:=((F\vee F)\wedge (F\vee F)) 和 F_D:=((F\wedge F)\vee (F\wedge F))
• 归纳步骤：设 G 和 H 是任意两个表达式，对它们成立的结果是：存在 H_C 和 G_C 在CNF中，且存在 H_D 和 G_D 在DNF中，使得：

  G\equiv G_D \equiv G_D

  H\equiv H_D \equiv H_D

  因此，我们可以写：

  \displaystyle G_D := \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{GD}； \displaystyle G_C := \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{GC}

  \displaystyle H_D := \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{HD}； \displaystyle H_C := \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{HC}

  不失一般性，如果 F:= \neg G，则根据替代定理 和 广义摩根定律 我们有：

  \displaystyle F:= \neg G \equiv \left\{ \begin{matrix} \neg G_D := \neg \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{GD} \equiv\bigwedge_{i=1}^n \neg \bigwedge_{j=1}^m L_{ij}^{GD} \equiv \bigwedge_{i=1}^n \bigvee_{j=1}^m \neg L_{ij}^{GD} \\ \\ \neg G_C := \neg \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{GC} \equiv \bigvee_{i=1}^n \neg \bigvee_{j=1}^m L_{ij}^{GC} \equiv \bigvee_{i=1}^n \bigwedge_{j=1}^m \neg L_{ij}^{GC} \end{matrix}\right.

  另一方面，如果 F:=G\wedge H，则根据替代定理：

  \displaystyle F:=G\wedge H \equiv G_C \wedge H_C := \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{GC} \wedge \bigwedge_{i=1}^{n^\prime} \bigvee_{j=1}^{m^\prime} L_{ij}^{HC}

  这是一个合取范式。同理，如果 F:=H\vee G,那么：

  \displaystyle F:=G\wedge H \equiv G_D \vee H_D := \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{GD} \vee \bigvee_{i=1}^{\overline{n}} \bigwedge_{j=1}^{\overline{m}} L_{ij}^{HD}

  即为一个析取范式。

  因此，归纳完成，所有命题逻辑表达式都可以用FND和FNC表示。

研究命题逻辑的合取范式（CNF）和析取范式（DNF）对于简化和解决数学和计算机科学中的复杂问题至关重要。该定理表明任何逻辑表达式都可以同时用FND和FNC表示，这一结果具有重要意义，因为它使得命题的结构更加易于管理和标准化，从而有利于其分析和操作。这个结果的重要性在于它为算法设计、逻辑表达式的优化以及在各个知识领域（如人工智能和软件验证）中高效解决问题提供了坚实的基础。此外，用归纳法证明该定理的技巧强化了对逻辑表达式基本性质的理解，并展示了其在其他数学背景中的应用可能性。