归纳证明：德摩根定律和分配律的广义规则
摘要
本课程讨论了数学和命题逻辑中的归纳证明主题。我们解释了两种现有的证明类型：基于逻辑规则的内部或演绎证明，以及用于证明关于逻辑本身的陈述的外部或元数学证明。介绍了数学归纳法作为一种证明方法，它可以用来证明某些陈述对所有自然数都成立。课程展示了一个带有相应证明的示例，并解释了命题逻辑中德摩根定律和分配律的广义形式及其归纳证明。这节课对于理解数学和逻辑的基础知识并将其应用于不同领域至关重要。
学习目标：
完成本课程后，学生将能够：
- 识别两种需要区分的证明类型：内部或演绎证明和外部或元数学证明。
- 应用数学归纳法对自然数和命题逻辑进行证明。
- 使用合取与析取符号来书写命题逻辑表达式。
- 理解命题逻辑中德摩根定律和分配律的广义形式。
- 理解归纳假设的概念及其在归纳证明中的作用。
目录
内部与外部证明
数学归纳法证明
命题逻辑中的归纳证明
德摩根定律的广义形式
分配律的广义形式
内部与外部证明
有两种需要区分的证明类型。到目前为止，我们已经看到了许多形式证明的例子。这种类型的证明来自于逻辑规则。这样的证明被称为”逻辑内部”发生的，因此我们也称之为”内部证明”或演绎证明。这种形式的证明具有有限的焦点，因为它们只能用于证明可以用逻辑语言表达的陈述。然而，我们可能想要证明一些关于逻辑本身的东西。我们可能想要证明命题逻辑的所有陈述都具有某种性质。这些关于逻辑本身的陈述既不能在逻辑内部被建立也不能被证明。为了证明这些陈述，我们使用外部证明。外部证明有时被称为”元数学”，我们已经遇到过这种情况，比如当我们看到(元)演绎定理时。在这里，我们将归纳证明的背景进行说明。
数学归纳法证明
数学归纳法是一种证明方法，它允许我们证明某些陈述对所有自然数都成立。
示例：
可以证明形如11^n - 4^n的每一个数，其中n为任意自然数，总是可以被7整除。
证明：如果我们观察n=1的情况，我们会发现：
11^1 - 4^1 = 7
显然，这是可以被7整除的。
现在假设11^n - 4^n可以被某个n=k整除。从这里我们将证明该表达式对n=k+1也成立。我们可以通过以下方式进行证明：
因此，如果11^k - 4^k可以被7整除，那么11 ( 11^{k} - 4^{k} ) + 7\cdot 4^{k}也可以被7整除，这也就是说11^{k+1} - 4^{k+1}可以被7整除。因此，如果11^k - 4^k对k=1成立，那么它对k=2, k=3, k=4,\cdots等也成立，并且对于任何n\in\mathbb{N}都成立。当这种情况发生时，我们称归纳是完整的。 ■
命题逻辑中的归纳证明
在接下来要进行的归纳证明中，首先需要引入以下符号约定。
符号： 设F_1,\cdots, F_n为命题逻辑中的任意有限表达式集合。通过以下公式引入这些表达式的合取与析取：
\displaystyle \bigwedge_{i=1}^n F_i := F_1\wedge \cdots \wedge F_n
\displaystyle \bigvee_{i=1}^n F_i := F_1\vee \cdots \vee F_n
有了这些符号，我们现在可以处理以下两种广义形式。
德摩根定律的广义形式
对于命题逻辑中的任意有限表达式集合F_1,\cdots, F_n,总是满足以下两个性质：
\displaystyle\neg\left(\bigwedge_{i=1}^n F_i \right) \equiv \left( \bigvee_{i=1}^n \neg F_i \right)
\displaystyle\neg\left(\bigvee_{i=1}^n F_i \right) \equiv \left( \bigwedge_{i=1}^n \neg F_i \right)
证明：首先我们通过对n进行归纳来证明\neg\left(\bigwedge_{i=1}^n F_i \right) \equiv \left( \bigvee_{i=1}^n \neg F_i \right)
首先我们需要检查初始情况n=1.在这种情况下，显然\neg F_1 \equiv \neg\left(\bigwedge_{i=1}^1F_i\right)\equiv \left(\bigvee_{i=1}^n \neg F_i \right) \equiv\neg F_1
现在假设该性质对某个n=k;成立，即对于任意有限表达式集合F_1, F_2, \cdots, F_k成立：
\displaystyle \neg\left(\bigwedge_{i=1}^k F_i\right) \equiv \left(\bigvee_{i=1}^k \neg F_i\right)
然后我们将证明这一性质对
\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right) \equiv \left(\bigvee_{i=1}^{k+1} \neg F_i\right)
利用合取的定义，我们得到：
\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right) := \neg\left[\left(\bigwedge_{i=1}^{k} F_i\right) \wedge F_{k+1}\right]
对于该表达式，我们可以应用德摩根定律（通常用于两个项）以得到：
\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right)\equiv \left[\neg\left(\bigwedge_{i=1}^{k} F_i\right) \vee \neg F_{k+1}\right]
现在，如果应用归纳假设，我们将得到：
\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right)\equiv \left[ \left(\bigvee_{i=1}^k \neg F_i\right) \vee \neg F_{k+1}\right] := \left(\bigvee_{i=1}^{k+1}\neg F_i \right)
因此，归纳证明完成，该性质对所有n普遍成立。第二个关系可以通过完全类似的方式获得，因此我将其留作读者的练习，哈哈！
分配律的广义形式
类似于德摩根定律，分配律可以通过以下方式进行广义化。设\{F_1, \cdots, F_n\}和\{G_1,\cdots, G_m\}为任意有限表达式的两个集合，则有以下等价关系：
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^m G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^m(F_i\vee G_j) \right) \right]
\displaystyle \left[ \left(\bigvee_{i=1}^n F_i \right) \wedge \left(\bigvee_{j=1}^m G_j \right) \right] \equiv \left[\bigvee_{i=1}^n\left(\bigvee_{j=1}^m(F_i\wedge G_j) \right) \right]
证明：要构建这个证明，我们需要对n和m进行双重归纳。接下来，我将首先对n进行归纳，然后对m进行归纳，以证明表达式\left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^m G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^m(F_i\vee G_j) \right) \right]。
如果我们取m=1,那么这个表达式可以写成
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^1 G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^1(F_i\vee G_j) \right) \right].
这实际上等同于：
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee G_1 \right] \equiv \left[\bigwedge_{i=1}^n\left( F_i\vee G_1 \right) \right].
现在，我们将证明该表达式对n的归纳。
如果我们取n=1,那么该表达式简化为
F_1 \vee G_1 \equiv F_1 \vee G_1.
这一点我们已经知道是正确的。现在假设它对任意n=k成立；也就是说，归纳假设为：
\displaystyle \left[ \left(\bigwedge_{i=1}^k F_i \right) \vee G_1 \right] \equiv \left[\bigwedge_{i=1}^k\left( F_i\vee G_1 \right) \right].
那么，从此出发我们将证明该表达式对n=k+1.也成立。
根据合取的定义，我们得到：
\displaystyle \left[\left(\bigwedge_{i=1}^{k+1}F_i \right) \vee G_1 \right] := \left[\left(\left(\bigwedge_{i=1}^{k}F_i \right)\wedge F_{k+1} \right) \vee G_1 \right]
现在，使用\vee-分配律，我们将得到：
\displaystyle \left[\left(\bigwedge_{i=1}^{k+1}F_i \right) \vee G_1 \right] \equiv \left[\left(\left(\bigwedge_{i=1}^{k}F_i \right)\vee G_{1} \right) \wedge \left(F_{k+1} \vee G_1 \right) \right]
在这个时候，我们可以使用归纳假设得到：
\displaystyle \left[\left(\bigwedge_{i=1}^{k+1}F_i \right) \vee G_1 \right] \equiv \left[\left(\bigwedge_{i=1}^k\left( F_i\vee G_1 \right) \right) \wedge \left(F_{k+1} \vee G_1 \right) \right] := \left[\bigwedge_{i=1}^{k+1}(F_{i}\vee G_1 \right]
因此，我们通过归纳法证明了对所有n\in\mathbb{N}成立
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right)\vee G_1\right] \equiv \left[\bigwedge_{i=1}^n(F_i\vee G_1)\right]
完成对n的归纳后，我们已经验证了初始情况对m=1成立，现在我们只需完成对m的归纳。为了做到这一点，我们为某个m=l设定归纳假设，即成立
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^l G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^l(F_i\vee G_j) \right) \right]
然后我们将证明它对m=l+1.也成立。
如往常一样，从合取的定义出发，我们得到
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] := \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\left(\bigwedge_{j=1}^{l} G_j \right) \wedge G_{l+1}\right) \right]
现在，使用\vee-分配律我们得到
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] \equiv \left[ \left( \left(\bigwedge_{i=1}^n F_i \right) \vee \left( \bigwedge_{j=1}^l G_j \right) \right) \wedge \left( \left( \bigwedge_{i=1}^n F_i \right)\vee G_{l+1} \right) \right]
因此，利用归纳假设可以写为
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^l(F_i\vee G_j) \right) \wedge \left( \left( \bigwedge_{i=1}^n F_i \right)\vee G_{l+1} \right) \right]
现在，如果我们利用对n的归纳结果
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^l(F_i\vee G_j) \right) \wedge \left( \bigwedge_{i=1}^n (F_i \vee G_{l+1} )\right) \right]
最后，根据合取的定义我们得到
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^{l+1}(F_i\vee G_j) \right) \right]
因此，对m的归纳完成，该表达式
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{m} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^{m}(F_i\vee G_j) \right) \right]
对所有n,m\in\mathbb{N}都成立。
通过这一归纳证明的过程，我们展示了如何将严谨的数学证明技术应用于自然数领域之外，还应用于命题逻辑。通过归纳法，我们成功地确立了德摩根定律和分配律广义形式的有效性，从而加强了对数学知识的各个领域中逻辑基础的理解。这种方法不仅对抽象推理技能的发展至关重要，而且作为解决数学及其他领域复杂问题的有力工具。