# 逻辑和证明

# 命题逻辑

# 命题

命题是一个陈述语句（即陈述事实的语句），它或真或假，但不能既真又假。

例子：

🌰 下面的陈述句均是命题：

1. 华盛顿特区是美利坚合众国的首都；
2. 多伦多是加拿大的首都；
3. 1+1=2；
4. 2+2=3；

命题 1 和 3 为真，命题 2 和 4 为假。

🌰 考虑下述语句：

1. 几点了？
2. 仔细读这个。
3. x+1=2
4. x+y=z

语句 1 和 2 不是命题，因为它们不是陈述语句。语句 3 和 4 不是命题，因为它们既不为真，也不为假。注意，如果我们给语句 3 和 4 中的变量赋值，那么语句 3 和 4 可以变成命题。

我们用字母来表示『 命题变元 』，它是代表命题的变量，就像用字母表示数值变量那样。

如果一个命题是真命题，它的『 真值 』为真，用 T 表示；如果它是假命题，其真值为假，用 F 表示。

涉及命题的逻辑领域称为『 命题演算 』或『 命题逻辑 』。

称为『 复合命题 』的新命题是由已知命题用逻辑运算符组合而来。

# 否定

『 否定 』的真值表：

例子：

🌰 “我是一个好人” 的否定是 “我不是一个好人”

# 合取

『 合取 』的真值表：

例子：

# 析取

『 析取 』的真值表：

例子：

# 异或

『 异或 』的真值表：

# 条件语句

这一节讨论几个重要的命题合成方式。

# 条件语句

条件语句可以有以下多种表达方式：

例子：

需要注意，我们日常说话中，假设和结论之间都有一定的联系。比如上例中，“找好工作” 和 “学习离散数学” 之间是有关系的。又或者举例 “如果今天天晴，那么我们就去海滩”。

但是，在数学推理中，条件语句作为一个数学概念不依赖于假设和结论之间的因果关系。🌰 例如：“如果我有手机，那么 2 + 3 = 5。” 这个条件语句总是成立的，因为它的结论是真的。不管前提和结论之间是否有因果关系。

# 逆命题，逆否命题与反命题

由条件语句 $p \rightarrow q$ 还可以构成一些新的条件语句。

$q \rightarrow p$ 称为 $p \rightarrow q$ 的 『 逆命题 』。

$p \rightarrow q$ 的『 逆否命题 』是命题 $\urcorner q \rightarrow \urcorner p$

$\urcorner p \rightarrow \urcorner q$ 是 $p \rightarrow q$ 的『 反命题 』。

# 双条件语句

我们可以有下面几种方式表达双条件语句的关系：

真值表：

只有当 $p \rightarrow q$ 和 $q \rightarrow p$ 都为真的时候，语句 $p \leftrightarrow q$ 才为真。

例子

# 复合命题 & 真值表

上面我们介绍了『 否定 』，以及四个逻辑联结词 『 合取 』『 析取 』『 条件 』『 双条件 』。

我们可以用这些联结词来构造更复杂的复合命题。然后用真值表来决定这些复合命题的真值。

例子：

# 逻辑运算符的优先级

通常我们用括号 ( ) 来规定复合命题中的逻辑运算符的作用顺序。但是为了减少括号数量，逻辑运算符之中也有优先级顺序：

# 命题逻辑的应用

逻辑在数学，计算机科学，以及其他很多学科中都有重要的应用。

# 语句翻译

人类语言常有二义性。把语句翻译成复合命题可以消除歧义。注意，这样翻译时也许需要根据语句的含义做一些合理的假设。此外，一旦完成了从语句到逻辑表达式的翻译，我们就可以分析这些逻辑表达式以确定它们的真值，对它们进行操作。

例子：

# 系统规范说明

在描述硬件系统和软件系统时，将自然语言语句翻译成逻辑表达式是很重要的一部分。系统和软件工程师根据自然语言描述的需求生成精确而无二义性的规范说明，这些规范说明可作为系统开发的基础。

例子：

# 布尔搜索

逻辑联结词广泛用于大量信息搜索中，例如，搜索网页索引。由于搜索采用命题逻辑的技术，所以称为布尔搜索。

在布尔搜索中，联结词 AND 用于匹配同时包含两个搜索项的记录，联结词 OR 用于匹配两个搜索项之一或两项均匹配的记录，而联结词 NOT（有时写做 AND NOT）用于排除某个特定的搜索项。

# 逻辑谜题

可以用逻辑推理解决的谜题称为逻辑谜题。求解逻辑谜题是实践逻辑规则的一种最好的方法。同样，用于执行逻辑推理的计算机程序通常也使用著名的逻辑谜题来演示它们的能力。

例子：

# 逻辑电路

命题逻辑可应用于计算机硬件的设计。这是 1938 年克劳德·香农（Claude Shannon）首次发现并写在他的 MIT 硕士论文中。

例子：

# 命题等价式

数学证明中使用的一个重要步骤就是用真值相同的一条语句替换另一条语句。因此，从给定复合命题生成具有相同真值命题的方法广泛使用于数学证明的构造。

# 逻辑等价式

在所有可能的情况下都有相同真值的两个复合命题称为逻辑等价的。

判定两个复合命题是否等价的方法之一是使用真值表。

证明 De.Morgan 律：

下面是一些  有用的等价式：

---

# De.Morgan 律的运用

德·摩根律的两个逻辑等价式非常重要它们告诉我们怎么取合取的否定和析取的否定。

例子：

# 构造新的逻辑等价式

上一节，表 6 中的逻辑等价式可以用来构建新的等价式。能这样做的原因是复合命题中的一个命题可以用与它逻辑等价的复合命题替换而不改变原复合命题的真值。

例子：

# 命题的可满足性

一个复合命题称为是『 可满足的 』，如果存在一个对其变元的真值赋值使其为真。当不存在这样的赋值时，即当复合命题对所有变元的真值赋值都是假的，则复合命题是『 不可满足的 』。注意一个复合命题是不可满足的当且仅当它的否定对所有变元的真值赋值都是真的，也就是说，当且仅当它的否定是永真式。

当我们找到一个特定的使得复合命题为真的真值赋值时，就证明了它是可满足的。这样的一个赋值称为这个特定的可满足性问题的一个『 解 』。可是，要证明一个复合命题是不可满足的，我们需要证明每一组变元的真值赋值都使其为假。

尽管我们总是可以用真值表来确定一个复合命题是否是可满足的，但通常有更有效的方法。如下例所示：

例子：

# 可满足性的应用

在不同领域（如机器人学、软件测试、计算机辅助设计、机器视觉、集成电路设计、计算机网络以及遗传学）中的许多问题都可以用命题可满足性来建立模型。

下面我们证明一下，如何用命题的可满足性来为 “数独” 建模。

# 谓词 & 量词

这一节我们来学习一种表达能力更强的逻辑，即谓词逻辑。

# 谓词

在数学断言，计算机程序中，我们经常可以看见含有变量的语句。比如：

• x > 3；
• y = x + 10；
• 有 x 台计算机被用来使用；

前面我们提到，在变量的值未指定时。这些语句既不为真，也不为假。这一节我们来讨论，从这些语句中生成命题的方式。

语句 “x 大于 3” 可以分成两个部分：

• 变量 x 是语句的主语；
• 谓词 “大于 3”，表明语句主语的一个性质。

我们可以用 P(x) 表示语句 “x 大于 3”。其中 P 表示谓词 “大于 3”。x 是变量。语句 P(x) 可以说成是命题函数 P 在 x 的  值。一旦变量 x 被赋值了。语句 P(x) 就变成了命题，且具有真值。

例子：

一般地，涉及 n 个变量 x1，x2，…，x 的语句可以表示成 P（x1，x2，…，xn）形式为 P（x1，x2，…，xn）的语句是『 命题函数 』 P 在 n 元组（x1，x2，…，xn）的值，P 也称为 『 n 位谓词 』或 『 n 元谓词 』。

# 前置条件 & 后置条件

谓词还可以用来验证计算机程序，也就是证明当给定合法输入时计算机程序总是能产生所期望的输出。（注意除非建立了程序的正确性，否则无论测试了多少次都不能证明程序对所有输入都产生所期望的输出，除非能测试到每个输入值。）

描述合法输入的语句叫做『 前置条件 』，而程序运行的输出应该满足的条件称为『 后置条件 』。

 例子：

# 量词

上面说，当命题函数中的变量均被赋值时，所得到语句就变成具有某个真值的命题。

可是，还有另外一种称为『 量化 』的重要方式也可以从命题函数生成一个命题。量化表示在何种程度上谓词对于一定范围的个体成立。

在自然语言中，所有、某些、许多、没有，以及少量这些词都可以用在量化上。

这里我们集中讨论两类量化：

• 『 全称量化 』，它告诉我们一个谓词在所考虑范围内对每一个体都为真；
• 『 存在量化 』，它告诉我们一个谓词对所考虑范围内的一个或多个个体为真。

处理谓词和量词的逻辑领域称为『 谓词演算 』。

# 全称量词

许多数学命题断言某一性质对于变量在某一特定域内的所有值均为真，这一特定域称为变量的『 论域 』，时常简称为『 **域 **』（domain）这类语句可以用全称量化表示。

对特定论域而言 P（x）的全称量化是这样一个命题：它断言 P（x）对 x 在其论域中的所有值均为真。

注意，论域规定了变量 x 所有可能取的值。当我们改变论域时，P（x）的全称量化的意义也随之改变。

在使用全称量词时必须指定论域，否则语句的全称量化就是无定义的。

例子：

# 存在量词

我们可以用存在量化构成这样一个命题，该命题为真当且仅当论域中至少有一个 x 的值使得 P(x) 为真。

我们可以用一下几种方式表达存在量化：

• 有一个 x 满足 P(x)；
• 至少有一个 x 满足 P(x)；
• 对某个 x，P(x) 为真；

例子：

# 唯一性量词

# 约束论域的量词

在要限定一个量词的论域时经常会采用简写的表示法。在这个表示法里，变量必须满足的条件直接放在量词的后面。

例子：

# 量词的优先级

量词比其他逻辑运算符都有更高的优先级。

# 变量绑定

当量词作用于变量 x 时，我们说此变量的这次出现为『 约束的 』。一个变量的出现被称为是『 自由的 』，如果没有被量词约束或设置为等于某一特定值。

命题函数中的所有变量出现必须是约束的或者被设置为等于某个特定值的，才能把它转变为一个命题。这可以通过采用一组全称量词、存在量词和赋值来实现。

逻辑表达式中一个量词作用到的部分称为这个量词的作用域。因此，一个变量是自由的，如果变量在公式中所有限定该变量的量词的作用域之外。

例子：

# 涉及量词的逻辑等价式

复合命题逻辑等价式的概念，可以扩展到涉及谓词和量词的表达式中。

例子：

# 量化表达式的否定

例子：

---

量词否定的规则称为量词的德·摩根律（De.Morgan Law）：

例子：

# 语句到逻辑表达的翻译

下面给出一些例子，来展示  如何将汉语语句翻译成逻辑表达式。

例子：

# 系统规范说明中量词的使用

之前我们用命题来表示系统规范说明。 现在我们来  引入谓词和量词。

例子：

# 嵌套量词

# 理解嵌套量词

『 嵌套量词 』指一个量词出现在另一个量词的作用域内。

例子：

# 量词的顺序

例子：

# 嵌套量词语句的翻译

# 数学语句到嵌套量词语句的翻译

例子：

# 嵌套量词到自然语言的翻译

用嵌套量词表达汉语语句的表达式可能会相当复杂。在翻译这样的表达式时，第一步是写出表达式中量词和谓词的含义，第二步是用简单的句子来表达这个含义。

例子：

# 自然语言到嵌套量词的翻译

# 嵌套量词的否定

带嵌套量词语句的否定可以通过连续地应用单个量词语句的否定规则得到。

例子：

# 推理规则

所谓的论证（argument），是指一连串的命题并以结论为最后的命题。所谓『 有效性 』（valid），是指结论或论证的最后一个命题必须根据论证过程前面的命题或前提（premise）的真实性推出。

一个论证是有效的当且仅当不可能出现所有前提为真而结论为假的情况。为从已知命题中推出新的命题，我们应用推理规则，这是构造有效论证的模板。推理规则是建立命题真实性的基本工具。

# 命题逻辑的有效论证

一个论证的有效性来自于论证形式的有效性。证明命题逻辑中论证有效性的关键就是要证明它的论证形式的有效性。

# 命题逻辑的推理规则

我们总是可以用一个真值表来证明一个论证形式是有效的。通过证明只要前提为真则结论也就肯定为真来做到这一点。然而，这会是一个冗长乏味的方法。

幸运的是，我们不是必须采用真值表。反之，我们可以先建立一些相对简单的论证形式（称为推理规则）的有效性。这些推理规则可以作为基本构件用来构造更多复杂的有效论证形式。

下表是一些推理规则：

例子：

# 使用推理规则建立论证

当有多个前提时，常常需要用到多个推理规则来证明一个论证是有效的。

例子：

# 消解律

消解律在基于逻辑规则的编程语言中扮演着重要的角色，如在 Prolog 中（其中用到了量化命题的消解规则）。而且，可以用消解律来构建自动定理证明系统。要使用消解律作为仅有的推理规则来构造命题逻辑中的证明，假设和结论必须表示为『 子句 』（clause），这里子句是指变量或其否定的一个析取式。我们可以将命题逻辑中非子句的语句用一个或多个等价的子句语句来替换。

例子：

# 谬误

几种常见的谬误都来源于不正确的论证。这些谬误看上去像是推理规则，但是它们是基于可满足式而不是永真式。

# 肯定结论的谬误

例子：

# 否定结论的谬误

例子：

# 量化命题的推理规则

现在将要描述针对含有量词的命题的一些重要的推理规则。

# 全称实例

# 全称引入

# 存在实例

# 存在引入

---

例子：

# 命题和量化命题推理规则的组合使用

上面的例子里，论证中既用了全称实例（量化命题推理规则）也用了假言推理（命题推理规则）。我们常常需要组合使用这些推理规则。由于全称实例和假言推理在一起使用是如此广泛，所以这种规则的组合有时称为『 全称假言推理 』（universal modus ponens）。

# 证明导论

本节我们介绍证明的概念并描述构造证明的方法。一个证明是建立数学语句真实性的有效论证。证明可以使用定理的假设（如果有的话），假定为真的公理以及之前已经被证明的定理。使用这些以及推理规则，证明的最后一步是建立被证命题的真实性。

# 一些专业术语

定理（theorem）是一个能够被证明是真的语句。在数学描述中，定理一词通常是用来专指那些被认为至少有些重要的语句。不太重要的定理有时称为命题（定理也可以称事实（fact）或结论（result））。一个定理可以是带一个或多个前提及一个结论的条件语句的全称量化式。当然，它也可以是其他类型的逻辑语句。

证明（proof）被用来展示一个定理是真的。证明就是建立定理真实性的一个有效论证。证明中用到的语句可以包括公理（axiom）或假设（postulate），这些是我们假定为真的语句。还有定理的前提（如果有的话）和以前已经被证明的定理。公理可以采用无须定义的原始术语来陈述，而在定理和证明中所用的所有其他术语都必须是有定义的。推理规则和其术语的定义一起用于从其他的断言推出结论，并绑定在证明中的每个步骤。实际上，一个证明的最后一步通常恰好是定理的结论。然而，为清晰起见，我们通常会重述定理的结论作为一个证明的最后步骤。

引理（lemma）是一个不太重要但有助于证明其他结论的定理，当用一系列引理来进行复杂的证明时通常比较容易理解，其中每一个引理都被独立证明。

推论（corollary）是从一个已经被证明的定理可以直接建立起来的一个定理。

猜想（conjecture）是一个被提出认为是真的命题，通常是基于部分证据、启发式论证或者专家的直觉。当猜想的一个证明被发现时，猜想就变成了定理。许多时候猜想被证明是假的，因此它们不是定理。

# 理解定理是如何陈述的

# 直接证明法

例子：

# 反证法

不采用直接证明法，即不从前提开始以结论结束来证明这类定理的方法叫做『 间接证明法 』。

例子：

当我们想要证明一条定理时：

1. 先评估『 直接证明法 』是否可行。可以通过展开前提中的定义开始。然后使用这些前提，加上公理和可用的定理进行推理；
2. 如果不行，尝试反证法。假定条件语句的结论为假，并使用直接证明法来证明这蕴含着前提必为假；

下面给出两个例子：

例子：

# 空证法 & 平凡证明

例子：

例子：

# 归谬证明法

归谬证明法也属于间接证明法。

例子：

# 等价证明法

例子：

# 反例证明法

例子：

# 证明中的谬误

在构造数学证明时容易犯许多常见错误。这里简述其中的一些错误。

数学证明的每一步都应当是正确的并且结论必须从之前的步骤中逻辑地导出。许多错误是源于引入了不是前面步骤得出的逻辑推导。下面的例子说明了这一点。

例子：

在证明中犯错是学习过程的一部分。当你犯了某个错误并被别人发现时，应该仔细分析哪里出了错误并确保不再犯同样的错误。

# 证明的方法和策略

上一节简要讨论了构造证明的策略。这些策略包括选择证明方法，然后基于该方法一步一步地成功构造论证。在开发了多功能的证明方法库之后，本节将研究关于证明的艺术和科学方面的一些问题。

# 分情形证明法 & 穷举证明法

# 分情形证明法

有时候采用单一的论证不能在定理的所有可能情况下都成立，故不能证明该定理。现在介绍一种通过分别考虑不同的情况来证明定理的方法。该方法是基于现在要介绍的一个推理规则：

作为推理规则。这个推理规则说明可以通过分别证明每个条件语句 $p→q（i ＝ 1，2，…，n）$ 来证明由命题 $ p1，p2，…，pn $ 的析取式组成前提的原条件语句。这种论证称为『 分情形证明法 』（proof by cases）

分情形证明一定要覆盖定理中出现的所有可能情况。

例子：

# 穷举证明法

有些定理可以通过检验相对少量的例子来证明。这样的证明叫做『 穷举证明法 』（exhaustive proof， proof by exhaustion），因为这些证明是要穷尽所有可能性的。一个穷举证明是分情形证明的特例，这里每一种情形涉及检验一个例子。

当只需要检查一个语句的相对少量的情形时，人们可以穷举证明法。当不可能列出所有要检查的情形时，就不要用了。

下面给出穷举证明法的一些例证：

例子：

# 不失一般性

一般地，当证明中用到『 不失一般性 』（缩写为 WLOG）一词时，我们断言通过证明定理的一种情形，不需要用额外的论证来证明其他特定的情形。也就是说，其他的一系列情形论证可以通过对论证做一些简单的改变，或者通过补充一些简单的初始步骤来完成当引入了不失一般性的概念后，分情形证明法就变得更加效了。

当然，不正确地应用这个原理会导致不幸的错误发生。有时候所做的假设会导致失去一般性。这类假设通常是由于忽略了一个情形可能与其他情形有着巨大的差异。这样会导致一个不完整的或许不可补救的证明。事实上，许多著名定理的不正确证明也是依赖于应用“不失一般性”的想法试图论证那些不能快速从简单情形来证明的情形。

例子：

# 穷举证明法 & 分情形证明法中的常见错误

推理中的一种常见错误是从个例中得出不正确结论。不管考虑了多少不同的个例，都不能从个例来证明定理，除非每一种可能情况都覆盖了。

例子：

# 存在性证明

例子：

# 唯一性证明

例子：

# 证明策略

寻找证明是一项富于挑战性的工作。当你面对待证命题时，应该先把术语替换成其定义，再仔细分析前提结论的含义。这样做之后，用一种可用的证明方法去尝试证明结论。一般情况下：

• 如果语句是条件语句，就应该首先尝试直接证明法；
• 如果这样不行，就尝试间接证明法；
• 如果这些方法都不行，就尝试归谬证明法。

# 正向和反向推理

例子：

# 改编现有证明

例子：

当你面临要证明一个新定理时，特别是当新定理类似于你原先证明过的定理时，一个好的窍门就是寻找你可以改编的现有的证明。

# 寻找反例

之前介绍了应用反例证明法来证明一些语句是假的。当面对一个猜想时，你首先可以试图去证明这个猜想，如果你的尝试没有成功，你可以试图寻找一个反例。如果你不能找到反例，你可以再试图证明这个语句。

例子：

# 证明策略实践

我们在学习数学时仿佛数学事实是刻在石头上的。数学教科书（包括这本书的绝大部分）正式地提出定理及其证明。这样的展示并不能揭示数学发现过程。这一过程以探索概念和例子开始，提出问题，形成猜想，并企图通过证明或者通过反例来解决这些猜想。这些就是数学家的日常活动。不管你信不信，教科书中所讲授的材料起初都是以这个方式发展出来的

人们基于各种可能证据来拟定猜想。对特殊情形的考察可能够导致一个猜想，就像识别一些可能的模式。对已知定理的假设和结论稍做改变也能导致可信的猜想。有些时候，猜想的建立是基于直觉或者甚至认为结果成立的信念。无论猜想是怎样产生的，一旦它被形式化描述，目标就是证明或者驳斥它。当数学家相信猜想可能是真的时，他们会尝试寻找证明。如果他们找不到证明，他们就会寻找反例。当他们不能找到反例时，他们又会转回来再次试图证明猜想。尽管许多猜想很快被解决，但有些猜想则抵御了数百年攻关，还导致数学新分支的发展。

# 费马大定理

费马大定理 - 李永乐老师

# 其他证明方法