计算模型入门：第一步

六节短课，讲这门课默认你已经懂的想法：集合，字符串与语言，函数与状态，什么是证明，逻辑词与真值表，以及怎样读懂记号。Python 例子用暴力检查在小情形上验证每个说法。

开始前需要什么

不需要安装任何东西。所有例子都是 Python，直接在本页运行：点代码下方的“运行”。你也可以改动代码再运行一次。
学校里学过的算术：加、乘、带余数的除法，并知道什么是偶数和奇数。
不需要会编程，也不需要学过逻辑。每个 Python 词和每个符号第一次出现时都会解释。
对符号有耐心。每个符号都配有名字和读法，第 6 课是一份可以反复回来看的阅读指南。

集合与属于关系

学完你能 学完后你能读写集合，判断某个东西是不是它的元素，并会用并集、交集和子集。

集合是一些东西的汇集，这些东西叫作它的元素。关于集合只有两个问题重要：里面有什么，没有什么。顺序不重要，重复不算数。集合用花括号来写：{1, 2, 3} 是以 1、2、3 为元素的集合。集合 {3, 1, 2, 2} 和它是同一个集合，因为顺序和重复都被忽略。

符号 ∈ 表示“是……的元素”，∉ 表示“不是……的元素”。所以 2 ∈ {1, 2, 3} 为真，5 ∈ {1, 2, 3} 为假。集合可以一个元素也没有，那就是空集，写作 ∅。集合 S 的大小写作 |S|，是它的元素个数。|{1, 2, 3}| 是 3，|∅| 是 0。

如果集合 A 的每个元素也都是集合 B 的元素，就说 A 是 B 的子集，写作 A ⊆ B。例如 {1, 2} ⊆ {1, 2, 3}。每个集合都是它自己的子集，∅ 是每个集合的子集。不要混淆 ∈ 和 ⊆。1 ∈ {1, 2} 说的是 1 是一个元素；{1} ⊆ {1, 2} 说的是只含 1 的那个集合是一个子集。集合也可以是另一个集合的元素。集合 {∅} 恰好有一个元素，这个元素就是空集。所以 |{∅}| 是 1，而 |∅| 是 0。里面装着一个空盒子的盒子，并不是空盒子。

两个集合有三种组合方式。并集 A ∪ B 包含属于 A 或属于 B 或两者都属于的所有元素。交集 A ∩ B 包含同时属于两者的元素。差集 A − B 包含属于 A 但不属于 B 的元素。取 A = {1, 2, 3}，B = {3, 4}：A ∪ B = {1, 2, 3, 4}，A ∩ B = {3}，A − B = {1, 2}。

Python 里也有集合。在 Python 里，变量是一个值的名字，= 把右边的值放到左边的名字下。print(...) 把值显示在屏幕上。集合本身没有顺序，所以例子打印的是每个集合的 sorted(...)，它把元素排好序，使每次运行的输出都一样。例子在很小的情形上检验每个说法。这样试小情形叫作暴力检查。它是看清一个想法如何运作的好办法，但并不能证明关于所有集合的结论。

新词

集合: 一些互不相同的东西的汇集。只看谁属于它，不看顺序，也不看重复。
元素: 集合里的一个东西。x ∈ S 读作“x 是 S 的元素”。
子集（⊆）: 如果 A 的每个元素也都在 B 里，A 就是 B 的子集。
并集、交集、差集: A ∪ B：属于 A 或 B。A ∩ B：同时属于两者。A − B：属于 A 但不属于 B。
空集（∅）: 没有元素的集合，大小是 0。
暴力检查: 把一个小范围里的每个情形都拿来检验。

完整例子

Python 3

A = {1, 2, 3}
B = {3, 4}

print("2 in A:", 2 in A)
print("5 in A:", 5 in A)
print("size of {3, 1, 2, 2}:", len({3, 1, 2, 2}))
print("A union B:", sorted(A | B))
print("A intersect B:", sorted(A & B))
print("A minus B:", sorted(A - B))
print("{1, 2} subset of A:", {1, 2} <= A)
print("A subset of B:", A <= B)
print("size of the empty set:", len(set()))
print("size rule holds:", len(A | B) == len(A) + len(B) - len(A & B))

先预测输出，再看结果

预期输出

2 in A: True
5 in A: False
size of {3, 1, 2, 2}: 3
A union B: [1, 2, 3, 4]
A intersect B: [3]
A minus B: [1, 2]
{1, 2} subset of A: True
A subset of B: False
size of the empty set: 0
size rule holds: True

逐步讲解

A = {1, 2, 3} 建立一个集合并取名 A。Python 里的花括号和纸上一样，用来写集合。
单词 in 提出属于关系的问题，答案是 True 或 False。2 in A 就是 Python 写法的 2 ∈ A。
len(...) 给出元素个数。在 {3, 1, 2, 2} 里重复的 2 只算一次，所以答案是 3。
符号 |、& 和 - 分别给出并集、交集和差集。外面的 sorted(...) 把结果按顺序列出，所以每次看到的行都相同。
<= 问的是“左边的集合是不是右边集合的子集？”{1, 2} 是 A 的子集，但 A 不是 B 的子集。
set() 建立空集。Python 里还有 {}，但它建立的是另一种东西，见下面的常见错误。
最后一行在这一对集合上用暴力检查验证一条规则：并集的大小等于两个大小相加，再减去重叠部分的大小，这样重叠部分就不会被数两次。这里打印 True。

常见错误

错误写法

empty = {}
print(empty | {1})

在 Python 里，{} 是空字典，是另一种东西。它不能和集合组合，所以第二行以 TypeError 停止。空集要写成 set()。

正确写法

empty = set()
print(empty | {1})

错误写法

print({1} in {1, 2})   # prints False

单词 in 问的是左边的东西是不是右边集合的元素。{1, 2} 的元素是 1 和 2，集合 {1} 不在其中，所以答案是 False。要问 {1} 是不是子集，应该用 <=。

正确写法

print({1} <= {1, 2})   # prints True

错误写法

print({"cat", "ant", "bee"})

集合没有顺序，所以 Python 在不同次运行时可能以不同的顺序显示元素，你的输出就和预期不一样。打印之前，要在集合外面加上 sorted(...)。

正确写法

print(sorted({"cat", "ant", "bee"}))

检查自己

{a, b, a, c} 有几个元素？{∅} 有几个元素，和 ∅ 比起来如何？
先自己做，再看答案
3 个，因为重复的 a 只算一次，这个集合就是 {a, b, c}。集合 {∅} 有 1 个元素，即空集，而 ∅ 有 0 个元素。
下面这些对吗？(a) {1, 2} ⊆ {1, 2}。(b) ∅ ⊆ {1, 2}。(c) 1 ⊆ {1, 2}。
先自己做，再看答案
(a) 对：每个集合都是自己的子集。(b) 对：∅ 没有元素，所以不会有哪个元素不在 {1, 2} 里。(c) 这不是一个合法的陈述，因为 1 是元素，不是集合。应该写 1 ∈ {1, 2}，或者 {1} ⊆ {1, 2}。
写出 A = {1, 2, 3, 4}、B = {2, 4, 6} 时 A ∩ B 的 Python 代码。它会打印什么？
先自己做，再看答案
print(sorted({1, 2, 3, 4} & {2, 4, 6})) 会打印 [2, 4]。这就是同时属于两个集合的元素。

字符串、字母表与语言

学完你能 学完后你能列出一个小字母表上的字符串，并能说明什么是语言。

字母表是有限的符号集合。我们把它写作 Σ，即希腊大写字母西格玛。例如 Σ = {a, b}，或者 Σ = {0, 1}。符号可以是任何东西：字母、数字、点。唯一的规则是这个集合是有限的。

Σ 上的字符串是由 Σ 中的符号一个接一个排成的有限序列。序列 abba 是 {a, b} 上的一个字符串。顺序有影响：ab 和 ba 是不同的字符串。字符串 w 的长度写作 |w|，所以 |abba| 是 4。还有一个完全没有符号的字符串，叫作空串，写作 ε（希腊字母厄普西隆）。它的长度是 0。空串是一个真正的字符串，尽管在纸面上看不见。把两个字符串首尾相接叫作连接：ab 与 ba 连接得到 abba。把 ε 连接到任何字符串上，都不改变它。

Σ*（读作“西格玛星”）是 Σ 上所有字符串的集合，包括所有长度，也包括长度 0。对 Σ = {a, b}，它开头是 ε, a, b, aa, ab, ba, bb, aaa，然后一直延续下去。长度为 1 的有 2 个，长度为 2 的有 4 个，长度为 3 的有 8 个。长度为 k 的字符串有 k 个位置，每个位置有 2 种选择，所以长度为 k 的字符串有 2 × 2 × ... × 2 = 2^k 个。集合 Σ* 是无限的，但它里面的每一个字符串都是有限的。

语言就是 Σ 上字符串的任意集合，也就是 Σ* 的任意子集。它不是口语或文字意义上的语言，也不必有什么规则。对 Σ = {a, b}，以 b 结尾的字符串组成一个语言：b、ab、bb、aab，等等。集合 {ab, ba} 是含两个字符串的语言。没有任何字符串的集合 ∅ 也是语言。含一个字符串（空串）的集合 {ε} 是另一个语言。这两个不一样：∅ 没有字符串，{ε} 有一个字符串，只不过这个字符串是空的。

在 Python 里，字符串是引号里的文字，例如 "abba"。空串是中间什么也没有的两个引号：""。len(...) 给出长度，+ 把两个字符串连接起来。列表写在方括号里，是按顺序排列的一行值。for 循环对列表的每一项各执行一次它缩进的行。Python 用缩进（行首的空格）表示哪些行在循环里面。两个星号表示“乘方”，所以 2 ** 3 是 8。例子一次一个长度地构造 {a, b} 上长度为 0、1、2、3 的字符串。每个长度为 k 的字符串，在末尾加 a 或加 b，得到两个长度为 k + 1 的字符串。然后第二个循环挑出一个语言：以 b 结尾的字符串。

新词

字母表（Σ）: 有限的符号集合。
字符串: 由字母表中的符号排成的有限序列。顺序有影响。
空串（ε）: 没有符号的字符串，长度是 0。
Σ*: Σ 上所有字符串的集合，包括 ε。它是无限的。
语言: Σ 上字符串的任意集合，也就是 Σ* 的任意子集。
连接: 把两个字符串首尾相接。Python 里用 + 号。

完整例子

Python 3

alphabet = ["a", "b"]
everything = []
current = [""]
for length in range(4):
    print(length, len(current), current)
    everything = everything + current
    longer = []
    for s in current:
        for symbol in alphabet:
            longer.append(s + symbol)
    current = longer

ends_in_b = []
for s in everything:
    if s.endswith("b"):
        ends_in_b.append(s)
print(ends_in_b)
print(len(everything), len(ends_in_b))

先预测输出，再看结果

预期输出

0 1 ['']
1 2 ['a', 'b']
2 4 ['aa', 'ab', 'ba', 'bb']
3 8 ['aaa', 'aab', 'aba', 'abb', 'baa', 'bab', 'bba', 'bbb']
['b', 'ab', 'bb', 'aab', 'abb', 'bab', 'bbb']
15 7

逐步讲解

alphabet 是含两个符号的列表。current 起初是 [""]，也就是含一个字符串（空串）的列表。长度为 0 的字符串只有这一个。
range(4) 给出数 0、1、2、3，所以外层 for 执行四次，length 依次取这些值。每次它打印长度、这个长度的字符串有多少个，以及这些字符串本身。
everything = everything + current 把这个长度的字符串加进“到目前为止所有字符串”的列表。+ 号连接两个列表，就像连接两个字符串一样。
里面的两层循环构造下一个长度。对每个字符串 s 和每个符号，s + symbol 是一个更长的字符串，append 把它放到列表 longer 的末尾。然后 current = longer 进入下一个长度。
打印出的个数是 1、2、4、8，也就是 2^length，和讲解中说的一样。循环不会列出 Σ* 的全部，因为它是无限的；它列出的是长度不超过 3 的所有字符串。
.endswith("b") 问的是一个字符串是否以 b 结尾。第二个循环留下这样的字符串。空串在 everything 里，但不在 ends_in_b 里，因为它没有最后一个符号。
最后一行显示长度不超过 3 的字符串共 15 个，其中 7 个以 b 结尾。所以“以 b 结尾的字符串”这个语言在长度 3 处截断后，有 7 个字符串。

常见错误

错误写法

print(len([""]))    # expecting 0

空串 "" 的长度是 0，但装着空串的列表有一项，所以它的长度是 1。这和 ε 与 {ε} 的差别是一样的，而 ∅ 就像空列表 []，它的长度是 0。

正确写法

print(len(""), len([""]), len([]))   # 0 1 0

错误写法

empty = " "     # a space

空格和别的符号一样是一个符号，所以 " " 是长度为 1 的字符串。空串一个字符也没有。把两者弄混会让计数差一，包含 ε 的语言也对不上。

正确写法

empty = ""

错误写法

# "ab" and "ba" are the same string, just like {a, b} and {b, a}

集合忽略顺序，字符串不忽略。{a, b} 和 {b, a} 是同一个集合，而 ab 和 ba 是两个不同的字符串。Python 也是这样判断的："ab" == "ba" 的结果是 False。

正确写法

print("ab" == "ba")   # False: a string is a row, order matters

检查自己

Σ = {0, 1, 2} 上长度为 5 的字符串有多少个？用 Python 验证你的答案。
先自己做，再看答案
5 个位置每个有 3 种选择，所以是 3 × 3 × 3 × 3 × 3 = 3^5 = 243。在 Python 里，print(3 ** 5) 会打印 243。
ε 属于 {a, b} 上“长度不超过 2 的所有字符串”这个语言吗？它属于“以 b 结尾的字符串”这个语言吗？
先自己做，再看答案
第一个属于，因为它的长度 0 不超过 2。第二个不属于，因为 ε 没有最后一个符号，所以不以 b 结尾。
预测 len("ab" + "" + "ba") 会打印什么。
先自己做，再看答案
4。与空串连接不改变任何东西，所以这个字符串是 "abba"，长度是 4。

函数，以及“状态”是什么意思

学完你能 学完后你能说明什么是函数，能把函数写成表，并能解释机器的状态是什么。

函数是这样一条规则：对每个允许的输入，恰好给出一个输出。规则 f(x) = x + 1 是一个函数：f(3) 是 4。有两点必须成立。每个允许的输入都有输出，所以没有哪个输入没有答案。并且没有哪个输入有两个不同的输出。允许输入的集合叫作定义域。

输入只有几个时，函数可以写成表，每个输入一行。当且仅当每个输入都恰好出现在一行里时，这个表才是函数。如果少了一行，函数在那个输入上就没有定义。如果同一个输入出现在两行里而输出不同，这个表就不是函数。

状态是一个过程此刻记住的信息。想想电灯开关。它的状态是“开”或“关”。它不记得被拨动过多少次，只知道此刻是什么样。一台逐个符号读取字符串的机器，必须决定记住什么。记住整个字符串可以做到，但字符串越长，需要的内存越多。通常只需很少的信息就够了。要回答“这个字符串里 1 的个数是偶数吗？”，只有两件事重要：到目前为止的个数是偶数，或者是奇数。这就是两个状态。

这样的机器由起始状态和转移函数来描述。转移函数接收两个输入：当前状态和下一个符号，给出一个输出：下一个状态。因为它是函数，所以对每一对状态和符号都要有一行。读完最后一个符号之后，机器所处的状态就是它的答案。

在 Python 里，字典就是一张表。它把键和值配成对，delta[key] 查出某个键对应的值。用圆括号写成的一对东西，例如 ("even", "1")，叫作元组，元组可以当键用。例子把转移函数存成字典。它每读一个符号就更新一次名为 state 的变量，以此来运行机器。单词 if 提出问题，只在答案为“是”时执行缩进的行，else 则处理另一种情况。

新词

函数: 对每个允许的输入恰好给出一个输出的规则。
定义域: 函数允许的输入的集合。
状态: 一个过程此刻记住的信息。状态有限的机器只能记住有限的东西。
转移函数: 接收当前状态和下一个符号，给出下一个状态。常写作 δ。
字典: Python 中把键和值配成对的表。
元组: 圆括号里固定的一对或一行值，例如 ("even", "1")。

完整例子

Python 3

delta = {
    ("even", "0"): "even",
    ("even", "1"): "odd",
    ("odd", "0"): "odd",
    ("odd", "1"): "even",
}

def run(word):
    state = "even"
    for symbol in word:
        state = delta[(state, symbol)]
    return state

state = "even"
for symbol in "1101":
    state = delta[(state, symbol)]
    print("read", symbol, "-> state", state)

for word in ["", "1", "11", "0110", "10101"]:
    if word.count("1") % 2 == 0:
        expected = "even"
    else:
        expected = "odd"
    print(repr(word), run(word), run(word) == expected)

先预测输出，再看结果

预期输出

read 1 -> state odd
read 1 -> state even
read 0 -> state even
read 1 -> state odd
'' even True
'1' odd True
'11' even True
'0110' even True
'10101' odd True

逐步讲解

delta 是一个有四行的字典。每个键是一对 (状态, 符号)，值是下一个状态。这是写成表的转移函数，每一对都有一行。
def run(word): 是一个函数，它从状态 "even" 开始，一次读一个符号，最后返回所处的状态。state = delta[(state, symbol)] 这一行查到对应的行，并把答案存回 state。
第一个循环一步步展示机器处理 1101：odd、even、even、odd。这个单词有三个 1，是奇数个，机器最后停在 "odd"。
第二个循环在五个单词上检验机器。word.count("1") 数出 1 的个数，% 2 给出除以 2 的余数：个数为偶数时余数是 0，为奇数时是 1。expected 是答案应有的样子。
repr(word) 把字符串连同引号一起打印，这样空串显示为两个引号，而不是消失不见。每一行都以 True 结尾：机器的结果与直接数数一致。
机器从不保存整个单词。它只保存两种状态中的一种。这正是状态的意义所在。

常见错误

错误写法

delta = {
    ("even", "0"): "even",
    ("even", "1"): "odd",
    ("odd", "0"): "odd",
}

没有 ("odd", "1") 这一行。机器第一次处于状态 odd 并读到 1 时，Python 会以 KeyError: ('odd', '1') 停止。用数学的话说，转移函数没有对每个输入都有定义，所以它不是一个完整的函数。

正确写法

delta = {
    ("even", "0"): "even",
    ("even", "1"): "odd",
    ("odd", "0"): "odd",
    ("odd", "1"): "even",
}

错误写法

for symbol in word:
    delta[(state, symbol)]

查表找到了下一个状态，却把它丢掉了。state 从不改变，所以机器对每个单词都回答 "even"。查表的结果必须存回 state。

正确写法

for symbol in word:
    state = delta[(state, symbol)]

错误写法

delta[[state, symbol]]

字典的键不能是列表，因为列表存进去之后还可以改变。Python 会以 TypeError: unhashable type: 'list' 停止。圆括号构成元组，元组不能改变，所以可以做键。

正确写法

delta[(state, symbol)]

错误写法

history = ""
for symbol in word:
    history = history + symbol

这样记住了读过的每个符号。信息确实足以回答问题，但内存会随单词变长而增长，所以任何固定个数的状态都装不下。状态有限的机器必须忘掉不重要的东西。对奇偶性来说，两个状态就够了。

正确写法

state = delta[(state, symbol)]   # two states are enough

检查自己

手动追踪机器处理 0110 的过程，写出每个符号之后的状态。
先自己做，再看答案
从 even 开始。读 0：even。读 1：odd。读 1：even。读 0：even。最终状态是 even，与“有两个 1，是偶数个”一致。
这张表是函数吗？(even,0) 得 even；(even,0) 得 odd；(even,1) 得 odd；(odd,0) 得 odd；(odd,1) 得 even。
先自己做，再看答案
不是。输入 (even,0) 出现了两次，而输出不同。函数对每个输入只给出一个输出。Python 字典甚至装不下这张表：重复的键只会保留最后一个值。
写出一台只记住上一个读到的符号是 0 还是 1 的机器的转移表。状态取名 "zero" 和 "one"，起始状态是 "zero"。
先自己做，再看答案
delta = {("zero", "0"): "zero", ("zero", "1"): "one", ("one", "0"): "zero", ("one", "1"): "one"}。不管处于哪个状态，读到一个符号就会转到以这个符号命名的状态。

什么是证明：反证法与归纳法

学完你能 学完后你能说明证明和测试有什么不同，并能读懂一个反证法和一个归纳法的证明。

证明是一串陈述。每一个陈述要么是已知的，要么由前面的陈述通过任何人都能检查的一步推出。最后一个陈述就是要证的命题。证明和测试不同。测试尝试一些情形。只要有一个情形失败，你就得到一个反例，它推翻了这个命题。如果每个情形都通过，你得到的是证据，不是证明，因为总有你没试过的情形。Python 很擅长找反例，却无法证明关于所有数的命题。

反证法是这样的。要说明一个命题为真，先假设它为假。顺着推下去，直到得出某个不可能的结果，比如一个数既是偶数又是奇数。正确的推理不可能导出不可能的事，所以假设一定是错的，命题就为真。如果命题的形式是“如果 P 那么 Q”，要假设的是 P 为真而 Q 为假。

看一个例子。命题：如果 n × n 是偶数，那么 n 是偶数。用反证法，假设 n × n 是偶数而 n 不是偶数。不是偶数的整数就是奇数，所以对某个整数 m，n = 2m + 1。于是 n × n = 4m² + 4m + 1 = 2(2m² + 2m) + 1，这是奇数。但我们假设了 n × n 是偶数，而没有数既是偶数又是奇数。这就是矛盾。所以假设是错的，命题成立。

归纳法分两部分证明对每个 k = 0, 1, 2, ... 成立的命题。基本情形证明命题对 k = 0 成立。归纳步骤假设命题对某个 k 成立，再证明它对 k + 1 成立。这样命题对 0 成立，于是对 1 成立，于是对 2 成立，依此类推，就像一排多米诺骨牌。例子命题：{a, b} 上长度为 k 的字符串恰好有 2^k 个。基本情形，k = 0：只有空串的长度是 0，而 2^0 是 1。归纳步骤：长度为 k + 1 的每个字符串，都是一个长度为 k 的字符串后面加一个符号 a 或 b。由假设，长度为 k 的字符串有 2^k 个，每个得到 2 个长度为 k + 1 的字符串。所以共有 2 × 2^k = 2^(k+1) 个。

Python 例子在 1000 以内的数里寻找第一个命题的反例。结果是空列表，说明没有找到。这是证据，而上面的证明才把它变成确定的结论。接着，它为一个假命题寻找反例，立刻就找到了。单词 break 会提前结束循环。最后，它数出长度到 6 的每个长度的字符串个数，并与 2^k 比较。

新词

证明: 一串陈述，每一个要么已知，要么由前面的陈述经可检查的一步推出，最后得到要证的命题。
反例: 命题失败的一个情形。一个就足以推翻命题。
反证法: 假设命题为假，并推出不可能的结果。
归纳法: 证明基本情形，再证明命题对 k 成立能推出命题对 k + 1 成立。
偶数、奇数: 偶数：对某个整数 m，等于 2m。奇数：对某个整数 m，等于 2m + 1。

完整例子

Python 3

# Claim 1: if n * n is even, then n is even.
counterexamples = []
for n in range(1000):
    if (n * n) % 2 == 0 and n % 2 == 1:
        counterexamples.append(n)
print("counterexamples to claim 1:", counterexamples)

# A false claim: if n * n is even, then n is a multiple of 4.
for n in range(1000):
    if (n * n) % 2 == 0 and n % 4 != 0:
        print("counterexample to the false claim:", n)
        break

# Claim 2: there are 2 ** k strings of length k over {a, b}.
strings = [""]
for k in range(7):
    print(k, len(strings), 2 ** k)
    assert len(strings) == 2 ** k
    longer = []
    for s in strings:
        longer.append(s + "a")
        longer.append(s + "b")
    strings = longer

先预测输出，再看结果

预期输出

counterexamples to claim 1: []
counterexample to the false claim: 2
0 1 1
1 2 2
2 4 4
3 8 8
4 16 16
5 32 32
6 64 64

逐步讲解

第一个循环寻找一个数 n，使 n * n 是偶数而 n 是奇数。条件由 and 连接的两部分组成，两部分必须同时成立。n % 2 是除以 2 的余数，所以 n % 2 == 1 表示 n 是奇数。
列表是空的：在 1000 以内没有找到反例。这与反证法的证明一致，但只有证明才覆盖每一个数。
第二个循环检验一个假命题。n = 2 时，n * n 是 4，是偶数，但 2 不是 4 的倍数。一个反例就足以推翻命题，break 立刻结束循环。
最后一部分像上一课那样构造每个长度的字符串。每个字符串变成两个更长的字符串，一个加 a，一个加 b。这就是用具体字符串做出来的归纳步骤。
每一行显示 k、字符串的个数和 2 ** k（2 的 k 次方）。两个数一致。如果它们哪次不同，assert 会让程序以 AssertionError 停止。
这只检查了长度 0 到 6。讲解里的归纳法证明覆盖每一个长度。

常见错误

错误写法

# 2**n - 1 is prime for n = 2, 3, 5, 7
# so it is prime for every prime n

四次成功不是证明。下一个质数就让它失败了：n = 11 时这个数是 2047，等于 23 乘 89。测试能推翻一个命题，却不能证明它对所有情形成立。

正确写法

print(2 ** 11 - 1, 23 * 89)   # 2047 2047

错误写法

Assume n is even. Then n * n is even. Done.

这证明的是相反的方向：如果 n 是偶数，则 n * n 是偶数。而命题是：如果 n * n 是偶数，则 n 是偶数。要用反证法证明它，应当从“n * n 是偶数而 n 不是偶数”出发，推出不可能的结果。

正确写法

Assume n * n is even and n is odd. Then n * n is odd. Contradiction.

错误写法

# Claim: a string of length k has k + 1 symbols.
# Step: if length k has k + 1 symbols, adding one symbol gives k + 2 symbols for length k + 1.
# So it is true for every k.

归纳步骤本身是对的，但基本情形从来没有检查，而这个命题是假的。空串的长度是 0，有 0 个符号，不是 1 个。正确的步骤也救不了一个一开始就失败的命题：没有人推第一块骨牌。

正确写法

print(len(""))   # 0, not 1: the base case fails, so the claim is false

检查自己

用反证法证明：不存在最大的偶数。
先自己做，再看答案
假设 m 是最大的偶数。那么 m + 2 也是偶数，并且比 m 大。这与“m 是最大的”矛盾。所以假设是错的，不存在最大的偶数。
用归纳法证明：对 n = 1, 2, 3, ...，1 + 2 + 4 + ... + 2^(n-1) = 2^n - 1。
先自己做，再看答案
基本情形 n = 1：左边是 1，右边是 2^1 - 1 = 1。归纳步骤：假设 1 + 2 + ... + 2^(k-1) = 2^k - 1。两边都加上下一项 2^k：2^k - 1 + 2^k = 2 × 2^k - 1 = 2^(k+1) - 1。这就是 k + 1 对应的命题。
Python 在 n 从 1 到 1,000,000 的范围内没有找到某个命题的反例。命题就证明了吗？为什么？
先自己做，再看答案
没有。这是一百万个情形的证据，而数有无穷多个。上面 2^n - 1 的例子通过了四个质数，在第五个就失败了。只有证明才覆盖所有情形。

逻辑词与真值表

学完你能 学完后你能画出并读懂“且、或、非、蕴含”的真值表，并能用暴力检查验证两个陈述等价。

要么真要么假的陈述叫作命题。“7 是奇数”是命题，“请关门”不是。我们用 p、q 这样的字母代表命题。逻辑用几个连接词，由小的陈述组成大的陈述。

下面是这些词。“非 p”，写作 ¬p，在 p 为假时为真。“p 且 q”，写作 p ∧ q，只有两者都为真时才为真。“p 或 q”，写作 p ∨ q，至少有一个为真时为真，两者都真的情形也包括在内。日常说话里的“或”常常指“二选一，不能都要”，在逻辑里从来没有这个意思。“p 蕴含 q”，写作 p → q，也读作“如果 p 那么 q”，恰好在一种情形下为假：p 为真而 q 为假。其他情形都为真。

最后一个让人惊讶。想想这个承诺：“如果下雨，我就带伞。”只有下了雨而我没带伞，承诺才算被违背。如果没下雨，不管我做什么，承诺都没有被违背。所以只要 p 为假，p → q 就为真。逻辑学家把这叫作空真：什么都没有被检验，所以什么也没有失败。

真值表列出这些字母的真假的每一种组合，并给出陈述在每一行的值。两个字母有 4 行，三个字母有 8 行，k 个字母有 2^k 行。如果两个陈述的真值表在每一行的值都相同，它们就是等价的。德摩根律就是一个例子：“非 (p 且 q)”等价于“(非 p) 或 (非 q)”。

Python 里 and、or、not 是普通的词，True 和 False 是它的两个真值。它没有表示蕴含的词。我们写 (not p) or q，它的真值表和 p → q 相同。两层循环，一个套在另一个里面，就能走遍每一行。在这里，检查每一行就是完整的证明，因为只有四行，而检查覆盖了全部。暴力检查恰好在它覆盖每一个情形时才是证明。

新词

命题: 要么真要么假的陈述。
¬ ∧ ∨ →: 非、且、或、蕴含。Python 里：not、and、or，以及 (not p) or q。
真值表: 每一行对应字母真假的一种组合，并给出陈述在该行的值的表。
等价: 两个陈述的真值表在每一行都一致，它们就等价。
空真: 前半部分为假的蕴含是真的，因为没有承诺任何东西。

完整例子

Python 3

def implies(p, q):
    return (not p) or q

print("p q | p and q | p or q | not p | p implies q")
for p in [True, False]:
    for q in [True, False]:
        print(p, q, "|", p and q, "|", p or q, "|", not p, "|", implies(p, q))

same = True
for p in [True, False]:
    for q in [True, False]:
        if (not (p and q)) != ((not p) or (not q)):
            same = False
print("not (p and q) equals (not p) or (not q):", same)

先预测输出，再看结果

预期输出

p q | p and q | p or q | not p | p implies q
True True | True | True | False | True
True False | False | True | False | False
False True | False | True | True | True
False False | False | False | True | True
not (p and q) equals (not p) or (not q): True

逐步讲解

def implies(p, q): 根据规则建立一个函数：p 蕴含 q 与 (not p) or q 相同。Python 没有表示蕴含的词，所以我们自己做一个。
两层嵌套循环走遍每一行。外层循环让 p 依次取 True 和 False，内层循环让 q 依次取 True 和 False，所以 print 执行四次。
每个打印出的行显示 p、q，然后是 p and q、p or q、not p 和 implies(p, q)。读第二行：p 是 True，q 是 False，所以“p and q”是 False，“p or q”是 True，“not p”是 False，“p implies q”是 False。这是 implies 为 False 的唯一一行。
第三、四行 p 是 False，implies 是 True。这又是那个带伞的承诺：什么都没有被检验，所以什么也没有失败。
第二部分在全部四行上检验德摩根律。!= 的意思是“不等于”。如果两边哪一行不同，same 就会变成 False。它保持为 True，所以这两个陈述等价。
因为这四行就是所有的行，所以这个暴力检查就是对等价性的完整证明。

常见错误

错误写法

# "if p then q" is false whenever p is false

恰恰相反。承诺只有在条件发生时才可能被违背。p 为假时没有承诺任何东西，所以 p → q 为真。p → q 为假的唯一一行是 p 真而 q 假。

正确写法

# "if p then q" is true whenever p is false

错误写法

# p implies q  means the same as  q implies p

q → p 是逆命题，它是另一个陈述。p 为 False、q 为 True 时，p → q 是 True，而 q → p 是 False。与 p → q 等价的是 (not q) → (not p)，叫作逆否命题。

正确写法

implies(p, q) == implies(not q, not p)   # True in all four rows

错误写法

not p and q    # meant: not (p and q)

在 Python 里，not 只作用于紧跟在它后面的东西，所以这表示 (not p) and q。p 为 True、q 为 False 时它是 False，而 not (p and q) 是 True。想表达“对整体取非”时，一定要加括号。

正确写法

not (p and q)

错误写法

# True or True is False, because "or" means one or the other

日常说话里的“或”常常排除两者都有的情况。在逻辑里，p ∨ q 在至少一个为真时为真，两者都真时同样为真。Python 遵循逻辑的规定。

正确写法

print(True or True)   # True

检查自己

真值表的哪些行里 p → q 为假？
先自己做，再看答案
只有 p 为真而 q 为假的那一行。其余三行里 p → q 都为真。
写一个 Python 表达式，恰好在 p 为 True 且 q 为 False 时是 True。它和 p → q 是什么关系？
先自己做，再看答案
p and (not q)。它在 p → q 为假的那一行为 True，在其余三行为 False。所以它是 p → q 的反面：非 (p → q) 等价于 p ∧ ¬q。
p → q 与 (not q) → (not p) 等价吗？列出四行来检查。
先自己做，再看答案
等价。(p, q) 取 (真, 真)：两者都真。(真, 假)：两者都假。(假, 真)：两者都真。(假, 假)：两者都真。真值表在每一行都一致，所以两个陈述等价。

读懂记号：Σ*、δ(q, a) 与集合构造记号

学完你能 学完后你能把课程里的一行记号大声读出来，说出它的意思，并用 Python 写出同样的想法。

数学记号是句子的速记。像 L = {w ∈ Σ* : |w| 是偶数} 这样的一行看起来很难，其实是压缩成符号的一句话。读它，就是把它展开。方法有四步。把每个符号的名字大声说出来。问清每个符号是哪种东西：集合、字符串、状态还是数。用平常的话把整行说出来。在一个很小的情形上检验它。最后一步 Python 能帮上忙，因为这些记号大多在 Python 里有对应的写法。

Σ 和 Σ*。符号 Σ（西格玛）是字母表，即有限的符号集合。Σ* 是 Σ 上所有字符串的集合，包括空串。Σ^k 读作“西格玛的 k 次方”，是长度恰好为 k 的字符串的集合。所以 {0, 1}^2 是 {00, 01, 10, 11}。写在字母右下方的小数字是名字的一部分：q₀ 是一个状态，即起始状态，不是“q 减 0”。

集合构造记号（描述法）。{x ∈ S : P(x)} 读作“S 中所有使 P(x) 成立的 x 组成的集合”。冒号前面的部分说明 x 从哪里来，冒号后面的部分说明保留哪些 x。有些书用竖线 | 代替冒号。例如 {w ∈ {0, 1}^2 : w 以 1 结尾} 是 {01, 11}。在 Python 里，这是用带筛选条件的循环构造的集合：{w for w in S if P(w)}。

δ(q, a)。符号 δ（德尔塔）是机器的转移函数。δ(q, a) 读作“在状态 q 读到符号 a 时到达的状态”。它只接收一个符号。像 {("q0", "1"): "q1", ...} 这样的 Python 字典就是同一个函数，δ(q, a) 就是 delta[(q, a)]。对整个字符串，书上用第二个函数，写作 δ*(q, w)，它对 w 的每个符号各用一次 δ。

量词。符号 ∀ 表示“对所有”。“∀w ∈ S : P(w)”说的是 P 对 S 中每个 w 都成立。符号 ∃ 表示“存在”。“∃w ∈ S : P(w)”说的是 S 中至少有一个 w 满足 P。Python 的 all(...) 和 any(...) 在有限集合上做同样的事。课程中的其他符号：ε 是空串，∅ 是空集，∪ 和 ∩ 是并集和交集，|w| 是字符串的长度，|S| 是集合的大小，⊆ 表示子集。

新词

Σ^k: Σ 上长度恰好为 k 的字符串的集合。
集合构造记号（描述法）: {x ∈ S : P(x)} 是 S 中所有使 P(x) 成立的 x 组成的集合。冒号的意思是“使得”。
δ(q, a): 在状态 q 读到符号 a 时到达的状态。
∀ 和 ∃: “对所有”和“存在”。在有限集合上，Python 里是 all(...) 和 any(...)。
下标: 写在符号下方的小数字或小字母，是名字的一部分，如 q₀。

完整例子

Python 3

sigma = {"0", "1"}                      # Σ, the alphabet

# Σ^2: all strings of length 2 over Σ
sigma_2 = set()
for a in sigma:
    for b in sigma:
        sigma_2.add(a + b)
print("sigma^2 =", sorted(sigma_2))

# set-builder: {w in Σ^2 : w ends in 1}
ends_in_1 = {w for w in sigma_2 if w.endswith("1")}
print("ends in 1:", sorted(ends_in_1))

# δ(q, a): a transition function stored as a table
delta = {("q0", "0"): "q0", ("q0", "1"): "q1", ("q1", "0"): "q0", ("q1", "1"): "q1"}
print("delta(q0, 1) =", delta[("q0", "1")])
print("delta(q1, 0) =", delta[("q1", "0")])

# for all, there exists
print("all have length 2:", all(len(w) == 2 for w in sigma_2))
print("some w equals 11:", any(w == "11" for w in sigma_2))

先预测输出，再看结果

预期输出

sigma^2 = ['00', '01', '10', '11']
ends in 1: ['01', '11']
delta(q0, 1) = q1
delta(q1, 0) = q0
all have length 2: True
some w equals 11: True

逐步讲解

sigma 是用 Python 集合表示的字母表 Σ。一行里 # 后面的文字是注释：Python 会忽略它，人来读它。注释把数学符号和它在 Python 里的对应写法放在一起。
两层嵌套循环构造 Σ^2。对每个符号 a 和每个符号 b，a + b 是长度为 2 的字符串，add 把它放进集合。因为是集合，所以不会重复添加。
ends_in_1 是集合构造记号的那一行。把 {w for w in sigma_2 if w.endswith("1")} 大声读成“sigma_2 中所有 w 以 1 结尾的 w 组成的集合”。它和 {w ∈ Σ² : w 以 1 结尾} 逐部分对应，得到 {01, 11}。
delta 是一张表，delta[("q0", "1")] 就是 δ(q0, 1)。在状态 q0 读到 1 会到达 q1，在状态 q1 读到 0 会到达 q0。每次查表都接收一个状态和一个符号。
all(len(w) == 2 for w in sigma_2) 就是 ∀w ∈ Σ² : |w| = 2。它检验每一个 w，只有对所有 w 检验都为 True 时才回答 True。
any(w == "11" for w in sigma_2) 就是 ∃w ∈ Σ² : w = 11。只要至少有一个 w 通过检验，它就回答 True。这里两个答案都是 True。

常见错误

错误写法

# Sigma* with Sigma = {0, 1} is {0, 00, 000, ...}

那是只由 0 组成的字符串的集合。Σ* 里的星号表示 Σ 上的所有字符串，符号可以任意搭配，并且包括空串。它开头是 ε, 0, 1, 00, 01, 10, 11，然后继续下去。

正确写法

# Sigma* = {epsilon, 0, 1, 00, 01, 10, 11, 000, ...}

错误写法

delta[("q0", "101")]

δ 只接收一个符号，不接收字符串。表里没有 ("q0", "101") 这一行，所以 Python 以 KeyError 停止。要处理整个字符串，应当对每个符号各用一次 δ，这正是 δ* 做的事。

正确写法

state = "q0"
for symbol in "101":
    state = delta[(state, symbol)]

错误写法

{w: w.endswith("1") for w in sigma_2}

在数学里，冒号的意思是“使得”。在 Python 里，花括号内的冒号构成字典，这里的键是 w，值是 True 或 False。那是一张表，不是你想要的集合。在 Python 里，筛选条件要用 if 来写。

正确写法

{w for w in sigma_2 if w.endswith("1")}

错误写法

sigma_2 = {"00", "11"}    # each symbol written twice

Σ² 不是把每个符号各自重复一遍。它是所有长度为 2 的字符串，也就是全部四种组合。只含 00 和 11 的集合漏掉了 01 和 10。

正确写法

sigma_2 = {"00", "01", "10", "11"}

检查自己

把 L = {w ∈ {a, b}* : |w| 是偶数} 用平常的话说出来。给出 L 中的三个字符串和一个不在 L 中的字符串。
先自己做，再看答案
L 是所有长度为偶数的、由 a 和 b 组成的字符串的集合。在 L 中的：ε（长度 0）、ab（长度 2）、bbaa（长度 4）。不在 L 中的：a，它的长度是 1。
写出 Σ = {0, 1} 时 {w ∈ Σ³ : w 以 0 开头} 的 Python 代码。它有多少个元素？
先自己做，再看答案
用三层嵌套循环构造 sigma_3，每次加入 a + b + c，然后写 starts_0 = {w for w in sigma_3 if w.startswith("0")}。它有 4 个元素：000、001、010 和 011，是 Σ³ 中 8 个字符串的一半。
用例子中的表，δ(q1, 1) 是什么？从 q0 出发，一个符号一个符号地读 101，最后到达哪个状态？
先自己做，再看答案
δ(q1, 1) 是 q1。从 q0 出发：读 1 到 q1，读 0 到 q0，读 1 到 q1。最终状态是 q1。

接下来

接着阅读《计算模型》（COMP2022）课程笔记。它从你在这里见到的字符串和语言出发，在此之上讲机器、文法和逻辑。 →

独立整理的学习笔记，不是官方课程材料。