自然演绎系统

自然演绎
术语名称	自然演绎
英语名称	natural deduction

自然演绎系统是逻辑领域形式化公理系统的一种，属于 Gentzen 式系统，其特征是可以引入假设。自然演绎系统通常公理集合较少（典型的情况下可能没有），使用更多的推理规则代替，这些推理规则可以综合多个前提给出一个新结论。 自然演绎系统中每一行都是一个公式，通过公式进行变换得到新的公式。其变换规则除了重复、使用规则、引入公理外，还允许假言推理规则（即中途开始一个以假设开始的子证明）和标示步骤（即标记一个仅在当前子证明的域内有效的变项，并在结论中消除其自由出现）。

描述

自然演绎系统是推理系统的一类。 在自然演绎系统中，推理的每一行都是一个公式，除前提外，每个公式都由当前证明或其外部证明中已出现的公式和变换规则（包括重复已出现的公式、使用给定的推理规则、使用公理）得到。 此外，自然演绎系统允许假言规则，表现为在证明中开启一个子证明，子证明可以附加有新前提，这样的新前提只在当前子证明其这一子证明内部的新的子证明中有效。

常见规则

自然演绎

关于命题逻辑的自然演绎系统，通常包括以下10条规则。

• 否定引入（[math]\displaystyle{ \lnot_\mathrm{I} }[/math] 或 [math]\displaystyle{ \lnot }[/math]-int）：从 [math]\displaystyle{ \phi\rightarrow\psi }[/math] 和 [math]\displaystyle{ \phi\rightarrow\lnot\psi }[/math] 可推出 [math]\displaystyle{ \lnot\phi }[/math] 。由于条件证明规则，在有的理论中的形式是在子证明中假定 [math]\displaystyle{ \phi }[/math] ，并演绎出[math]\displaystyle{ \psi }[/math] 和 [math]\displaystyle{ \lnot\psi }[/math] 。
• 双重否定消去（[math]\displaystyle{ \lnot\lnot_\mathrm{E} }[/math] 或 [math]\displaystyle{ \lnot\lnot }[/math]-elim）：从 [math]\displaystyle{ \lnot\lnot \phi }[/math] 可推出 [math]\displaystyle{ \phi }[/math] 。（有些材料可能称为否定消去 [math]\displaystyle{ \lnot }[/math]-elim）
• 合取引入（[math]\displaystyle{ \land_\mathrm{I} }[/math] 或 [math]\displaystyle{ \land }[/math]-int）：从 [math]\displaystyle{ \phi }[/math] 和 [math]\displaystyle{ \psi }[/math] 可推出 [math]\displaystyle{ \phi\land\psi }[/math]。
• 合取消去（[math]\displaystyle{ \land_\mathrm{E} }[/math] 或 [math]\displaystyle{ \land }[/math]-elim）：从 [math]\displaystyle{ \phi\land\psi }[/math] 可推出 [math]\displaystyle{ \phi }[/math] 、从 [math]\displaystyle{ \phi\land\psi }[/math] 可推出 [math]\displaystyle{ \psi }[/math]。
• 析取引入（[math]\displaystyle{ \lor_\mathrm{I} }[/math] 或 [math]\displaystyle{ \lor }[/math]-int）：从 [math]\displaystyle{ \phi }[/math] 可推出 [math]\displaystyle{ \phi\lor\psi }[/math] 、从 [math]\displaystyle{ \phi }[/math] 可推出 [math]\displaystyle{ \psi\lor\phi }[/math]。
• 析取消去（[math]\displaystyle{ \lor_\mathrm{E} }[/math] 或 [math]\displaystyle{ \lor }[/math]-elim）：从 [math]\displaystyle{ \phi\lor\psi }[/math] 、 [math]\displaystyle{ \phi\rightarrow\chi }[/math] 和 [math]\displaystyle{ \psi\rightarrow\chi }[/math] 可推出 [math]\displaystyle{ \chi }[/math]。由于条件证明规则，在有的理论中的形式是在两个子证明中假定 [math]\displaystyle{ \phi }[/math] 和 [math]\displaystyle{ \psi }[/math] ，并均演绎出[math]\displaystyle{ \chi }[/math] 。
• 双条件引入（[math]\displaystyle{ \leftrightarrow_\mathrm{I} }[/math] 或 [math]\displaystyle{ \leftrightarrow }[/math]-int）：从 [math]\displaystyle{ \phi\rightarrow\psi }[/math] 和 [math]\displaystyle{ \psi\rightarrow\phi }[/math] 可推出 [math]\displaystyle{ \phi\leftrightarrow\psi }[/math]。由于条件证明规则，在有的理论中的形式是在两个子证明中假定 [math]\displaystyle{ \phi }[/math] 和 [math]\displaystyle{ \psi }[/math] ，并演绎出对方。
• 双条件消去（[math]\displaystyle{ \leftrightarrow_\mathrm{E} }[/math] 或 [math]\displaystyle{ \leftrightarrow }[/math]-elim）：从 [math]\displaystyle{ \phi\leftrightarrow\psi }[/math] 可推出 [math]\displaystyle{ \phi\rightarrow\psi }[/math] 、 从 [math]\displaystyle{ \phi\leftrightarrow\psi }[/math] 可推出 [math]\displaystyle{ \psi\rightarrow\phi }[/math] 。
• 条件引入（[math]\displaystyle{ \rightarrow_\mathrm{E} }[/math] 或 [math]\displaystyle{ \rightarrow }[/math]-int）（假言规则）：中途引入一个由假设开始的子证明，假定 [math]\displaystyle{ \phi }[/math] 为真后演绎出 [math]\displaystyle{ \psi }[/math] ，此子证明可推出 [math]\displaystyle{ \phi\rightarrow\psi }[/math] 。
• 条件消去（[math]\displaystyle{ \rightarrow_\mathrm{E} }[/math] 或 [math]\displaystyle{ \rightarrow }[/math]-elim）：从 [math]\displaystyle{ \phi\rightarrow\psi }[/math] 和 [math]\displaystyle{ \phi }[/math] 可推出 [math]\displaystyle{ \psi }[/math]。

这些规则都可以看作某种条件下的联结词的引入和消去，因此统称为引入消去规则或 intelim 规则。

其中，由于条件引入必须通过加入假设来进行，这一条称为“假言规则”，其他九条称为“非假言规则”。

注：根据不同人的排版习惯，引入、消去的标记可能使用 [math]\displaystyle{ \odot }[/math]-int/elim 、 [math]\displaystyle{ \odot I/E }[/math] 、 [math]\displaystyle{ \odot \mathrm{I}/\mathrm{E} }[/math] 、 [math]\displaystyle{ \odot_{I/E} }[/math] 、 或 [math]\displaystyle{ \odot_{\mathrm{I}/\mathrm{E}} }[/math] 等。

谓词逻辑

关于谓词逻辑的则增加以下4条规则。

• 全称量词消去（[math]\displaystyle{ \forall_\mathrm{E} }[/math]，[math]\displaystyle{ \forall }[/math]-elim，US/UI）：从 [math]\displaystyle{ \forall x \phi }[/math] 可推出 [math]\displaystyle{ \phi(t / x) }[/math] ，其中要求 [math]\displaystyle{ t }[/math] 对 [math]\displaystyle{ x }[/math] 在 [math]\displaystyle{ \phi }[/math] 中可自由代入。
• 存在量词引入（[math]\displaystyle{ \exists_\mathrm{I} }[/math]，[math]\displaystyle{ \exists }[/math]-int，EG）：从 [math]\displaystyle{ \phi(t / x) }[/math] 可推出 [math]\displaystyle{ \exists x \phi }[/math] ，其中要求 [math]\displaystyle{ t }[/math] 对 [math]\displaystyle{ x }[/math] 在 [math]\displaystyle{ \phi }[/math] 中可自由代入。
• 等词引入（[math]\displaystyle{ =_\mathrm{I} }[/math]，[math]\displaystyle{ = }[/math]-int）：在任意地方，可以对任意项 [math]\displaystyle{ t }[/math] 得到 [math]\displaystyle{ t=t }[/math] 。
• 等词消去（[math]\displaystyle{ =_\mathrm{E} }[/math]，[math]\displaystyle{ = }[/math]-elim）：从 [math]\displaystyle{ s=t }[/math] 或 [math]\displaystyle{ t=s }[/math]，以及 [math]\displaystyle{ \phi(s/x) }[/math] 可以得到 [math]\displaystyle{ \phi(t/x) }[/math] 。

然后还有两条规则，涉及一个自由变项。这意味着引入一个个体变项，且对这个引入项进行使用范围上的限制。

• 存在量词消去（[math]\displaystyle{ \exists_\mathrm{E} }[/math]，[math]\displaystyle{ \exists }[/math]-elim，ES/EI）：从 [math]\displaystyle{ \exists x \phi }[/math] 可推出 [math]\displaystyle{ \phi(t / x) }[/math] ，其中要求 [math]\displaystyle{ t }[/math] 对 [math]\displaystyle{ x }[/math] 在 [math]\displaystyle{ \phi }[/math] 中可自由代入，且此步骤将 [math]\displaystyle{ t }[/math] 标示。
• 全称量词引入（[math]\displaystyle{ \forall_\mathrm{I} }[/math]，[math]\displaystyle{ \forall }[/math]-int，UG）：标示任意 [math]\displaystyle{ t }[/math] 演绎出 [math]\displaystyle{ \phi(t/x) }[/math] 可推出 [math]\displaystyle{ \forall x \phi }[/math] ，其中要求 [math]\displaystyle{ t }[/math] 对 [math]\displaystyle{ x }[/math] 在 [math]\displaystyle{ \phi }[/math] 中可自由代入。

常见书写记号

属于自然演绎系统的推理方式有多种不同书写规则，常见主要形式有：

• Gentzen 式自然演绎
• Fitch 式自然演绎
• Suppes–Lemmon 式自然演绎

证明论
形式化公理系统（形式化、公理化）
形式化范式	公理系统、自然演绎系统、相继式演算
证明、演绎	证明、可证明、演绎、可演绎
命题、定理	公理、定理、元定理、变形规则
推理规则性质	保存真实性、保存重言性
公理系统性质	可靠性、完全性、一致性、独立性