WorkLog

CH1 INTRODUCTION

学习课程"形式语言与自动机"时做的笔记, 内容主要来自 Automata Theory, Languages, and Computation一书的第一章. 提及的内容主要是形式化证明的知识.

总体而言, 作为一书的introduction部分, 不会涉及很多形式化定义与概念, 只是举了些简单的例子, 因此在笔记中就不做过多记录, 简单带过.

Why Study Automata Theory

讲述了自动机的一些例子与应用.

Introduction to Formal Proof

讲述了形式化证明的知识. 形式化证明可大致分为两类:

演绎法(Deductive Proofs)
归纳法(Inductive Proofs)

Deductive Proofs

从公里和已知条件出发, 逐步推演, 最终得到结论的证明方法. 典型代表为欧式几何的证明.

Reduction to Definitions

当面对一个需要证明的命题, 不知如何下手时, 将所有概念展开为定义, 往往会有所帮助.

Other Theorem Forms

列举了"If-Then""If-And-Only-if"等定理的形式. 数理逻辑中已经介绍过, 在此不做赘述.
面对"If-And-Only-if"这种双向箭头类型的定理时, 证明需要从两个方向分别进行.

Additional Forms of Proof

Proving Equivalences About Sets

对于两集合相等的证明 $A = B$ , 往往需要分别证明 $A \subseteq B, B\subseteq A$ , 从而得到相等

The Contrapositive

对于某些命题"if A, then B", 我们可以证明其逆否命题"if not B, then not A".

Proof by Contradiction

“归谬法”. 对于某些命题"if A, then B", 将其转换为"A and not B implies falsehood"的形式来证明, 即先否定结论, 再导出矛盾, 从而证明命题成立的方法.

Counterexamples

通过举出反例来证伪命题.

Inductive Proofs

通过"数学归纳法"来归纳性地证明命题. 归纳法包括第一类数学归纳法, 第二类数学归纳法(强归纳法), 对结构进行的数学归纳法等等.

Inductive on Integers

对于某个带自然数变量的命题 $P(n)$ ( $n \geq n_0$ ), 假设满足条件
(a): $P(n_0)$ 为真
(b) if $P(n)$ , then $P(n+1)$
则有结论" $\forall n \geq n_0, P(n)$ "

如上就是数学归纳法的第一形式. 其中, 我们往往把条件(a)称作归纳基础(basis), 条件(b)称作归纳链条(induction).

值得一提的是, 数学归纳法对于自然数的归纳能够成立, 归根结底是依靠着自然数本身的归纳性质, 即
BASIS: $0$ is an integer
INDUCTION: if $n$ is an integer, then so is $n+1$
此时, 我们对于自然数集合 $N$ 采用了归纳的定义:

$0 \in N$
if $n \in N$ , then $n^{+} \in N$
其中, $n^+$ 代表对 $n$ 进行后继运算得到的元素.
此时我们就得到一个循环群 $N$ , 其生成元为 $0$ . 可以得到, 对于任意给定的 $i$ , $n^{(i)} \in N$ 成立.

于此同时, 数学归纳法的成立是依赖于选择公理的成立的. 为了看清楚这一点, 我们给出一个对于"数学归纳法成立"的一个看似合理的"证明":

假设我们有归纳基础与归纳链条成立.
假设我们的结论不成立, 即 $\exists n_i \geq n_0, s.t. \lnot P(n_0)$ . 换言之, 存在一个或多个 $n_i$ , 使得命题 $P(n_i)$ 为假.
在上述的那些 $n_i$ 中, 我们挑选出最小的那个 $n_m = j$ .
由于 $j$ 已经是最小的那个不满足条件的数了, 因此, 任意的 $n_0\leq i < j$ , 都有 $P(i)$ 为真.
那么显然, $P(j - 1)$ 为真. 根据归纳链条, 我们就可以得到 $P(j)$ 为真. 这与我们的条件" $P(j)$ 为假"矛盾了.
因此, 第二步中做出的假设是错的, 当第一步中的假设成立时, 结论也会成立.

这是通过归谬法来证明数学归纳法的步骤. 看似天衣无缝的过程其实有着漏洞. bug就出在第二步中, "选出最小的数"的操作. 这步操作的本质是, 我们需要有一个函数, 满足 $f(\{n_i | \lnot P(n_i)\}) = n_{min}$ , 这样, 我们才能从"不满足条件的数"的集合中, 挑选出那个"最小的"代表元素.
从生活经验出发, 我们会很自然的认为这件事能够做到. 我们习惯了自然数之间存在的大小序关系, 并天然认为能够选出一个最小的元素. 但是数学有时候就是那么怪异和反常识: 这件事情不一定能做到. 或者说, 它的合理性需要依靠"选择公理"来保证.
为了说明这件事, 我们考虑这么一种情况:“对于集合 $S\in 2^{[0, 1]}$ , 选择其代表元素 $x\in S$ ”. 此时, 我们的选择就不是那么显然了, 需要精心构造一个函数才能做到.
更深入的细节一句两句无法说清, 事实上我也是似懂非懂. 这个问题已经触及到数学很基础与很底层的部分, 接近metamath的领域, 因而很难有丰富的语言对问题进行描述.

不过, 在几乎全部的情况下, 我们都可以直接把"数学归纳法"当做一种理所当然的合理方法来使用, 而不用考虑这些底层的数学问题.

More General Forms of Integer Inductions

Structural Inductions

Mutual Inductions

以上三小节是更深入的一些归纳法, 例如强数学归纳法, 对树和图的结构做归纳的归纳法, 多重的归纳法等等. 它们都是由最原始的对自然数的归纳拓展得到的, 在数理逻辑中也有讲述, 因此在此也不再赘述. 它们的形式化表述也在数理逻辑中被提到, 是一个十分玄奥且有趣的内容. (此处mark一下, 也许有时间会翻翻这部分内容. )

The Central Concepts of Automata Theory

这是本章除了形式化证明之外的另一块重要内容, 给出了字母表"alphabei", 字符串"strings"和语言"language"的定义.

Alphabets

一个有穷非空符号集, 例如

\Sigma = \{0, 1\}

\Sigma = \{a, b, ..., z\}

以及ASCII字符等等.

Strings

归纳定义:

空字符 $\epsilon$ 是一个string.
若 $s$ 是string, 则对于 $a \in \Sigma$ , $as$ 是string.

同样的, 可以归纳地定义某个字符串的长度 $|s| = l$

令所有长度为 $k$ 的字符串所组成的集合为 $\Sigma^k$ , 那么可将某个字母表 $\Sigma$ 所生成的字符串集合 $\Sigma^*$ 形式化地表示为

\Sigma^* = \Sigma^0 \cup \Sigma^1 \cup \Sigma^2 \cup ...

\Sigma^+ = \Sigma^* / \{\epsilon\}

Language

对于在字符集 $\Sigma$ 上的Language $L$ , 有

L \subseteq \Sigma^*

即, Language由那些满足某种条件的strings组成.

Problem

对于给定的Language和alphabet, 我们可以对应的得到一个Problem $L$ :

给定一个字符串 $w \in \Sigma^*$ , 判定是否有 $w \in L$

有的时候, 我们将一个字符串的集合视为Language, 而在另一些时候将它视为Problem. 这只不过是视角的转换, 本质并未改变.

总而言之, 这一章作为导入部分, 形式化的内容不多, 主要就自然归纳法和"字符串"等概念的定义, 之前都已经接触过, 没太多好说的
自然归纳法的深入探究思考起来很有趣, 但从使用和应试的角度来看没有难度. 复习的时候随便看看即可.