用逻辑说话

$$ \Huge \textbf{用逻辑说话} $$

$$ \boxed{ \overbrace{\textit{degaokaolization}}^{\small{去高考化}} \text{ Discussion Group | Topic 02}} $$

我个人推荐阅读《Reading, Writing, and Proving - A Closer Look at Mathematics(Second Edition)》. 可以阅读第2章至第4章. 以下的笔记为该书的简化版本.

$$ \boxed{\textbf{注意:} 受限于翻译的水平, 推荐使用英语阅读本文. } $$

基础

教你们班的化学老师即马上就要换了. 有人说年级里面有两名还没有带班的老师, 分别是王瑞瑶老师和王艳波老师. 与此同时, 你参加化学竞赛的同学告诉你, 王瑞瑶正在带领学生参加世界性的化学竞赛IChO. 所以你很确定接下来要来给你上课的的老师是王艳波老师.

想一想我们刚刚做了什么样的推理: 如果你得到“A或B是真的”的传言, 并且你知道“A不是真的”, 你就可以知道“B是真的”. 这是一个有效的推理的例子.

所以, 在生活和学习中, 为了理解一个"证明", 我们必须能够阅读和理解那些构成论点的句子. 并且我们需要能够判断论证中的句子是真是假, 以及它们是否与前面的句子有逻辑关系.

所以, 现在定义一下那些所谓的论点, 或者说命题, 就像在高中时的那样.

Def. 命题是一个可以判断真假的陈述句. $#$

因为中文的说法和数学文本中的的说法很多时候有略微的差别, 所以在论证之前, 我们必须确保我们理解我们的命题. 现在, 我们仔细地研究命题的真与假. 具体地, 我们来看如下的几种情况:

非 $P$.
$P$ 和 $Q$.
$P$ 或 $Q$.
如果 $P$, 则 $Q$.
$P$ 当且仅当 $Q$.

像 $P$ 和 $Q$ 这样的字母只是表示一些抽象的命题. 小学的时候, 你一定学过 "如果......那么......" 这样的句子. 这里的$P$和$Q$只是把这些省略号具体化了.

让我们从最简单的形式开始：

非（$\lnot$）

假设 AUGPath 说：“我的电脑桌面图片是一座山！”通过观察他的桌面, 你发现那不是一座山. 换句话说, 你可以确定该陈述的“真值”(在这里就是假的). 你可以说：“桌面图片不是一座山！”

如果我们有一个命题, 用 $P$表示, 那么 $P$ 的否定读作 "非 $P$". 为了方便起见, 我们使用符号 $¬P$ 表示 "非 $P$". 根据直觉, 如果 $P$ 是真的, 则 $¬P$ 应该是假的. 如果 $P$ 是假的, 则 $¬P$ 应该是真的. 如此, 我们可以罗列所有的情况, 用一个真值表总结所有可能性, 如下所示：

$$ \begin{array}{c|c} \mathbf{P}&\lnot\mathbf{P}\\ \hline T&F \\F&T \end{array} $$

我们用 T 表示真, 用 F 表示假. 真值表是理解的好工具. 好, 这是针对单个命题的情况. 现在让我们看一下能够组合两个命题的连接词：

或($\lor$) 和($\land$)

下面, 让我们研究句子 "$P$ 或 $Q$". 数学中的 "或" 有时候不同于自然语言, 有着不同的意义.

例如, 在日常生活中, 我们在说 "你可以吃蛋糕或冰淇淋"的时候, 表达的意思是你可以两者都选择, 但是当我们说 "门是开着的或关着的"的时候, 表达的却不是门既是开着的又是关着的. 自然语言陈述中的 "或" 经常含糊不清. 在数学中, 一般不鼓励使用模糊性.

形如 "$P$ 或 $Q$" 的陈述被称为析取. 通常用符号 $P\lor Q$ 表示.

旁注. 为什么叫析取: 析的意思有1.劈；刮。2.分开；分散。3.分析；辨认。可能是$\lor$比较像一把斧子. 但是具体的原因还有待确认.

在数学中, 当 $P$ 单独为真, $Q$ 单独为真, 或者 $P$ 和 $Q$ 都为真时, 析取为真. 使用刚刚见过的真值表, 我们有如下结果：

$$ \begin{array}{cc|c} {P}&{Q}&P\lor Q\\ \hline T&T&T\\ T&F&T\\ F&T&T\\ F&F&F \end{array} $$

同样地, 在数学中的 "与"（$P$ 和 $Q$）有明确的含义, 即当 $P$ 和 $Q$ 同时为真时, 结果才为真；否则为假.

$$ \begin{array}{cc|c} {P}&{Q}&P\land Q\\ \hline T&T&T\\ T&F&F\\ F&T&F\\ F&F&F \end{array} $$

如果...那么...($\to$) 当且仅当($\iff$)

现在让我们考虑 "如果 $P$, 则 $Q$" 这样的说法. 这种命题形式被称为蕴含式, 通常表述为 "$P$ 蕴含 $Q$" 或者 "$P$推出$Q$" , 并写作 "$P\to Q$". 有多种等价的表述方式, 其中一些需要读者仔细思考. 我们在这里列出它们：

如果 $P$, 则 $Q$.
$P$ 对于 $Q$ 是充分条件（意味着 $P$ 足够让 $Q$ 发生）.
$Q$ 对于 $P$ 是必要条件（如果 $P$ 发生, 则必定 $Q$ 也发生）.
只有当 $Q$ 时, 才有 $P$.
只要 $P$, 就有 $Q$.

在这些表述中, $P$ 称为前件, $Q$ 称为结论. 那么像这样的命题, 真假性应该如何决定呢? 我们来看下面的例子:

假设我们对儿子说：

"如果你收拾好房间, 你就可以去亨利家玩. "

在什么情况下, 他会觉得我们撒谎了？在这个例子中, 前件 $P$ 是 "你收拾好房间", 结论 $Q$ 是 "你可以去亨利家玩". 嗯... 如果儿子收拾好房间, 我们让他去亨利家, 每个人都开心. 那个蕴含应该是真的. 所以, 如果 $P$ 是真的, $Q$ 是真的, 整个命题应该是真的.

同时, 对你们而言, 如果他收拾好房间, 而我们不让他去亨利家, 我们就算是撒谎了. 所以, 如果 $P$ 是真的, $Q$ 是假的, 那个蕴含的结果应该是假的.

那么如果他不收拾房间呢？我们从未讨论过这种可能性. 所以, 无论我们在这里做什么决定, 我们都没有撒谎. 所以, 如果 $P$ 是假的, 无论结论的真值如何, 我们将认为这个命题的结果为真.

这将引导我们给出蕴含的真值表：

$$ \begin{array}{cc|c} {P}&{Q}&P\to Q\\ \hline T&T&T\\ T&F&F\\ F&T&T\\ F&F&T \end{array} $$

重新表述一个命题很多时候有意想不到的结果, 只要我们确保我们重新说的内容和原来的内容的"真假"相同. 这里, "$P$ 当且仅当 $Q$" 这种形式被称为等价, 我们将其写作 $P \leftrightarrow Q$. 根据描述, 我们可以将其表示为 $(P\to Q)\land (Q\to P)$.

$$ \begin{array}{c|c|c|c}\mathbf{P}&\mathbf{Q}&\mathbf{P}\to\mathbf{Q}&\mathbf{Q}\to\mathbf{P}&\mathbf{P}\leftrightarrow\mathbf{Q}\\\hline T&T&T&T&T\\T&F&F&T&F\\F&T&T&F&F\\F&F&T&T&T\end{array} $$

"如果 $P$, 则 $Q$" 也可以写作 $P\implies Q$, "$P$ 当且仅当 $Q$" 可以写作 "$P \iff Q$" 或 "$P\text{ iff }Q$". (iff是if and only if的缩写)

在学习了连接词之后, 我们现在简单说说什么是命题公式. 命题公式是表示还没有确定真假的一些字母, 以及使用若干连接词构成的一个串. 命题公式可以非常复杂. 但是我们可以可以逐步为它们分配真值, 就像进行算术运算一样.

命题公式: 类型

给一个命题公式之后, 列出它的真值表. 如果真值表的最后一列全为 T, 则命题公式是永真式. 如果最后一列全为 F, 则称为矛盾式.

两个命题公式 $P$ 和 $Q$ 如果 $P ↔ Q$ 是一个永真式, 就被称为是（逻辑上）等价的；进而就可以用自然语言在这两个命题之间进行转化, 方便我们的理解.

对我们来说, $\lnot (P\land Q)$ 与 $\lnot P\lor \lnot Q$ 表达的是相同的内容. 根据定义, 我们可以为其列出真值表.

Thm. 如果两个陈述形式 $P$ 和 $Q$ 有相同的真值表, 那么它们等价.

Proof. 考虑等价式 $P ↔ Q$ 的真值表：我们知道如果 $P ↔ Q$ 是一个永真式, 那么 $P ↔ Q$ 的真值为 T（在上面的表中, 这是第1行和第4行）. 最后, $P ↔ Q$ 的真值为 T 当且仅当 P 和 Q 的真值相同. 由于只有当 $P ↔ Q$ 是一个永真式时 $P$ 和 $Q$ 是等价的, 这就证明了定理. $\square$

命题的否定

虽然能够以等价形式重新叙述某个命题非常重要, 但同样重要的是能够对一个命题进行否定. 一些有用的否定在练习和问题中会出现. 在数学中, 否定蕴含式尤为重要. 如果你思考这句话 "如果 $x$ 是质数, 则 $x$ 是奇数或 $x = 2$", 你会发现, 即使是一个相对简单的蕴含式, 否定它可能也没那么容易.

构造 $P \to Q$ 的真值表和 $¬P ∨ Q$ 的真值表. 你注意到了什么？

如果一切顺利, 你会注意到 $P \to Q$ 等价于 $¬P ∨ Q$, 因此"如果 $P$, 则 $Q$" 的否定是 "$P$ 且非 $Q$".

所以说, 回到例子

$$ \text { `若 } \underbrace{x \text { 是质数 }}{P}, \text { 则 } \underbrace{x \text { 是奇数或 } x=2}{Q} . " $$

的否定是

$$ \text { `` } \underbrace{x \text { 是质数 }}{P} \text { 但是 } \underbrace{ x \text { 既不是奇数有不是 } 2}{\neg Q} . " $$

蕴含式的否定是应该格外注意的, 因为它经常出现. 在下面的定理中, 我们总结了到目前为止我们所讨论的五个最重要的等价性. 前两个经常被称为DeMorgan定律.

Thm. 如果 $P$ and $Q$ 是命题, 那么这些是恒真式:

DeMorgan 律: $$ \begin{aligned}\lnot(P\lor Q)&\leftrightarrow(\lnot P\land\lnot Q);\\\lnot(P\land Q)&\leftrightarrow(\lnot P\lor\lnot Q);\end{aligned} $$

蕴含式及其否定

$$ \begin{array}{l}(P\to Q)\leftrightarrow(\lnot P\lor Q);\\\lnot(P\to Q)\leftrightarrow(P\land\lnot Q);\end{array} $$

双重否定. $\lnot(\lnot P)\leftrightarrow P.$

$#$

通过画出真值表, 很容易可以得到证明.

Exercise. 否定 $P\to Q \land R$.

我们为什么关心永真式呢？因为永真式允许我们堂而皇之地用一个等价的命题替代原来的命题. 例如, 假设你想证明一个整数是奇数或质数. 你当然可以证明这个整数是质数或奇数, 这显然没有影响 - 因为它们是等价的.

对于蕴含式, 重新表述你想要证明的内容可能会产生重大影响. 我们已经知道 $P\to Q$ 等价于 $\lnot P\lor Q$.

现在考虑 $\lnot Q\to \lnot P$, 它被称为蕴含式 $P\to Q$ 的逆否命题. 通过比较真值表, 我们会发现它们是相同的！

$$ \begin{array}{c|c|c} \mathbf{P} & \mathbf{Q} & \mathbf{P} \rightarrow \mathbf{Q} \\ \hline T & T & T \\ T & F & F \\ F & T & T \\ F & F & T \end{array} ~~~~~~~~ \begin{array}{c|c|c} \mathbf{P} & \mathbf{Q} & \neg \mathbf{Q} \rightarrow \neg \mathbf{P} \\ \hline T & T & T \\ T & F & F \\ F & T & T \\ F & F & T \end{array} $$

因此, 真值表相同, 它们在逻辑上是等价的. 因此, 我们可以通过证明其逆否命题来证明原来的命题.

集合符号和量词

考虑句子 "$x^2-1=0$". 到目前为止我们不认为这是一个命题. 它的真假性这取决于我们心中所考虑的 $x$ 是哪个值. 接下来, 我们将采用一种严格的方式添加一点东西, 将我们的句子 $x^2-1=0$ 转化为一个命题. 但在此之前, 我们将回顾一些符号 - 集合符号.

集合的概念很常见. 通常, 我们将集合视为一组对象的聚合. 我们既不定义什么叫聚合, 也不定义什么是对象. 它可以通过公理来进行精确定义, 但为了简单起见, 我们现在不会描述它们. （大多数人现在使用的集合公理系统是带有选择公理的泽尔梅洛-弗兰克尔公理系统. 当然, 这种严格化的内容乍一看很难理解. ）

回想一下, 先前我们学到的一个元素 $e$ 要么属于集合 $S$, 要么不属于集合 $S$. 第一种情况我们将写作 $e\in S$, 或者否则写作 $e\notin S$. 在我们研究的环境中, 所有可能的对象的集合被称为全集, 或论域. 我们通常用 $X$ 或 $U$ 表示它. 当我们研究实数时, 我们可能会将 $X$ 设置为 ${\text{实数}}$. 取决于研究的环境, 如果你在研究畜牧业, 这个集合甚至可能包括所有在法国生活的奶牛. 酷爱哲学的朋友甚至提出他们的全集是“所有集合的集合”, 尽管这是一个矛盾的概念(后面会提到). 这就是罗素悖论. 这也是数学家努力公理化集合的原因之一.

我们还记得, $\mathbb Z, \mathbb R, \mathbb Q, \mathbb C$ 分别表示常见的数字集合. 整数、实数、有理数、复数.

此外, 我们可以用 $\mathbb R\times\mathbb R$ 表示平面. 集合之间的 $\times$ 表示两个集合元素之间的所有可能的排列(就像乘法表一样). 后面我们会看到, 这个就是集合的笛卡尔积.

全称量词（$\forall$）和存在量词（$\exists$）

现在我们可以讨论稍微复杂一些的命题了. 想想“每个盒子里都有一个奖品”和“某个盒子里有一个奖品”之间的区别. 显然, 如果你想要选择让自己获奖的话, 会选择第一个情况. 在数学中, 为了确定一个命题的真或假, 上下文中提供的集合也是必不可少的. 在这个集合里面, 我们会用两种符号来说明关于这个集合里面元素的信息. 比如$\forall x. \cdots$和$\exists x. \cdots$这里的 $x$ 说的是一个集合里面的变量. 短语 "所有"、"每一个"是全称; "存在" 或 "有一些" 用来是特称. "任意" 或 $∀$ 是全称量词, "存在" 或 $∃$ 是存在量词.

在确定全集为所有实数的情况下, 考虑以下陈述："对于所有的 $x$, $x^2-1\leq 0$. "我们知道这是在要求每个 $x$ 都满足某个条件. 恰好这个陈述是假的, 但它仍然是一个清晰的陈述. 通常写作 $\forall x. x^2-1\leq 0$. 所以我们可以写成

$$ \forall x. x^2-1\leq 0. $$

在我们的命题中, "任意的 x" 后面是另一个句子, 我们可以用 p 表示, 但由于 p 是涉及 x 的句子, 所以我们写作 p(x). 上面的陈述的形式是 $\forall x. p(x)$.

对于上面的例子, 还有一个备注. 假设全集仍然是实数, 但我们想要将其表示为仅关于正整数的陈述. 在这种情况下, 我们可以用符号表示我们的陈述如下：

$$ \forall x. (x\in \mathbb Z^+ {\color{red}\to} (x^2-1\leq 0)) $$

一个非常常见的错误是写成 $\forall x. (x\in \mathbb Z^+ {\color{red}\land} (x^2-1\leq 0))$, 而不是上面我们写的那样. 但是让我们思考一下这意味着什么：这会说“所有实数都是正整数, 并且满足不等式 $x^2 − 1 ≤ 0$”. 现在很明显, 这不是原始陈述所说的内容.

以另一个例子为例, 假设我们的全集是整数集合, 并考虑句子“存在一个整数 $x$, 使得 $x = 0$”. 这也是一个陈述, 也是真的. 可以用符号写作

$$ \exists x. (x=0). $$

并且读作 "存在一个 $x$, 使得 $x=0$". 关于最后一个例子还有一个备注. 如果我们将实数集作为全集, 我们会用符号写作

$$ \exists x, (x\in \mathbb Z \land x=0). $$

请注意, 这次我们只是宣称 $x$ 存在, 并且是一个整数, 并且 $x = 0$. 为了让这些条件都成立, 我们必须使用一个合取而不是一个蕴含, 正如定义中已经指出的那样. 这类事情通常需要仔细考虑. 我们稍后会给出一个表格, 来详细地总结一下各种情况.

当你否定一个陈述时, 你必须对你的全集非常清楚. 你也可以很容易地看出为什么：如果你否定了 $x ∈ \mathbb Z$, 并且 $\mathbb Z$ 是你的全集, 那么就没有剩下的 $x$, 但是如果你否定了 $x ∈ \mathbb Z$, 并且 $\mathbb R$ 是你的全集, 那么还有很多 $x$ 要考虑. 因此, 在开始解决问题之前, 请务必仔细考虑全集是什么.

量词的否定

我们已经对合取、析取和蕴含进行了否定. 现在我们将思考量化陈述的否定.

假设我们有命题 "每只奶牛都是黑色的". 我们如何否定它？

一种毫无意义的方式是说 "不是每只奶牛都是黑色的". 更好的方式是说 "存在一只奶牛不是黑色的". 因此, 对于 $\forall x. p(x)$, 一个有用的否定是 $\exists x. \lnot p(x)$.

类似地, 如果我们说 "存在一只黑色的奶牛", 一个有用的否定是 "没有一只奶牛是黑色的". 因此, 对于 $\exists x. p(x)$, 一个否定是 $\forall x. \lnot p(x)$.

你会发现有时你可以直接否定一个句子, 而有时你需要转换成符号. 这里是另一个例子.

Exercise. 对句子 "住在玻璃房子里的人不会扔石头" 进行否定. 使用符号 $g(x)$ 表示 $x$ 住在玻璃房子里. 记号 $t(x)$ 表示 $x$ 扔石头.

$$ \begin{aligned} \lnot (\forall x. (g(x)\to \lnot t(x))) & &(1)\\ \exists x. \lnot(g(x)\to \lnot t(x)) & &(2) \\ \exists x. \lnot(\lnot g(x)\land \lnot t(x)) & &(3) \\ \exists x. (g(x)\land t(x)) & &(4) \\ \end{aligned} $$

上面的最后一句话说, "住在玻璃房子里的人不会扔石头" 的否定是 "存在一个住在玻璃房子里并且扔石头的人". 这里还有一件重要的事情需要注意. 虽然在句子 "住在玻璃房子里的人不会扔石头" 中没有明显的量词, 但我们都会将量词解释为全称量词. 如果你或其他人没有明确包含量词, （注意是所有！）人们都会认为你的意思是在这里插入一个全称量词.

我们强调, 虽然练习这些符号操作很好, 但理解你所做的事情也很重要. 有时候你会发现使用符号表示法更容易, 有时候则不是. 请确保记住句子的含义, 以及你的答案是否合理. 在你独自进行之前, 我们将一起做一个相当复杂的例子.

Example. 假设我们的全集是实数集, 我们希望否定陈述 "对于每一个有理数 $x$, 存在一个大于 $x$ 的整数 $n$".

让我们试试. 首先我们注意到 "对于每一个有理数 $x$" 意味着我们被告知 "如果 $x$ 是一个有理数" 会发生某些事情. 什么事情？将会存在一个大于 $x$ 的整数. 因此, 这是一个形式为 "对于所有 $x$, 如果 $x$ 是一个有理数, 那么存在一个 $n$, $n$ 是一个整数且 $n > x$" 的蕴含. 有时候, 如果我们用符号表示法替换各种子句, 会更容易理解一个陈述. 我们使用

$$ \begin{aligned} p(x) & &\text{代表 } x \text{ 是有理数}\\ q(n) & &\text{代表} n \text{是整数}\\ r(n,x) & &\text{代表} n>x. \end{aligned} $$

使用这样的记号, 我们就有

$$ ∀x, (p(x) → ∃n, (q(n) ∧ r(n, x))) $$

让我们一步一步地尝试否定这个带有量词的命题, 从外面开始.

我们知道当我们否定 "对于所有" 时, 它变成了 "存在". 换句话说, 我们可以用 $∃x, ¬(· · · )$ 替换 $¬(∀x, · · · )$. 现在我们的表达式变成了：

$$ ¬(∀x. (p(x) → ∃n. (q(n) ∧ r(n, x)))) $$

与

$$ ∃x, ¬(p(x) → ∃n, (q(n) ∧ r(n, x))) $$

等价.

现在我们来否定蕴含. 根据上面所说, 我们知道 $¬(P → Q)$ 等价于 $P ∧ ¬Q$. 我们的表达式变成了：

$$ ∃x, (p(x) ∧ ¬(∃n, (q(n) ∧ r(n, x)))). $$

我们还需要否定 $Q$, 即表达式 $∃n. (q(n) ∧ r(n, x))$. 至少现在这比我们开始的时候简单了！现在 $∃$ 将变为 $∀$, 所以我们只需要考虑 $q(n)∧r(n, x)$. 但这是一个合取式. 因此, 最后一步是否定它, 我们知道合取的否定将变为 $¬q(n) ∨ ¬r(n, x)$. 现在我们的表达式变成了：

$$ ∃x, (p(x) ∧ (∀n, (¬q(n) ∨ ¬r(n, x)))) $$

我们已经完成了我们要做的事情, 但是我们的答案仍然是用符号表示的. 让我们翻译回来：

"存在一个 $x$, 它是有理数, 并且对于所有的 $n$, $n$ 不是整数或者 $n$ 不大于 $x$", 即 "存在一个有理数 $x$, 对于所有的整数 $n$, $n$ ≤ $x$".

关于量词的一些提示

检查每个变量的取值范围, 如果不明显的话, 写下来.
当陈述中变量的量词是全称量词时, 写作者有时会省略它. 例如, 你可能会看到关于实数的陈述, 如“如果$x$是负数, 则$x^2$是正数. ”因为量词没有明确说明, 我们假设作者的意思是“对于每个实数$x$, 如果$x$是负数, 则$x^2$是正数. ”如果你想表达存在这样的$x$, 你必须明显地标注出来使用存在量词.
假设一个陈述将变量$x$限定为全总域的一个真子集$A$, 如形式为“对于所有$x∈A$, 性质$p(x)$成立”的命题. 由于$x$是用任意修饰的, 可以写作一个蕴含形式$∀x, (x ∈ A → p(x))$.
假设一个命题将变量$x$限定为全总域的一个真子集$A$, 如形式为“对于一些$x∈A$, 性质$p(x)$成立”的命题. 由于$x$是用存在修饰的, 这是一个合取式形式$∃x, (x ∈ A ∧ p(x))$.
简单的陈述通常很容易否定. 只需直接取反即可.
复杂的陈述通常会对不太好“直接取反”. 首先以符号形式写出来. 确保你知道每个变量上的量化词是什么. 检查“如果..., 那么...”有哪些不同的表达方式.
不要在量化词之间使用逻辑联结词（$¬, ∧, ∨, →, ↔$）. （不要写成“$∀x ∨ ∀y · · ·$”或“$∀x ∧ ∀y · · ·$”. ）
熟悉规则. 你必须知道如何否定涉及存在、全称、合取、析取和蕴含的命题. 最重要的否定也是经常被忘记的是蕴含式的否定.
练习：每当你遇到一个定义或定理时, 尝试对其进行否定. 如果你做不到, 这可能表明你还没有完全理解它.

总结

使用逻辑符号有时非常有帮助.
事情看起来非常困难, 是因为缺乏前置知识.

advanced-math

(图为大学《高等数学》课堂的黑板笔记, 逻辑记号当然是很重要的)

文本信息附注

这篇文章摘自Reading, Writing, and Proving - A Closer Look at Mathematics(Second Edition). 原作者为Ulrich Daepp和Pamela Gorkin.

AUGPath对本文做了摘录和翻译. 限于翻译的水平, 建议查看英文的原文版. 来确认你的理解.

$$ -\mathscr {E}\text{nd of the note}- $$

基础