返回：0100 离散数学课程总目录 · 上一章：0122 包含排斥、Burnside 引理与 Polya 定理 · 下一章：0124 一阶谓词逻辑

1、学习目标

本章进入数理逻辑。组合数学里我们在“数对象”，命题逻辑里我们开始“数真假、管推理”：把自然语言命题符号化，再判断公式真假、推理是否有效、证明系统是否可靠和完备。

主线：

1
2
3
4
5
6
7
8
命题与联结词：把句子翻译成公式。
真值表：逐个赋值检查公式真假。
联结词完全集：哪些联结词足以表达所有真值函数。
推理形式：前提都真时结论必真。
自然推演 N：接近日常证明。
形式系统 P：公理模式 + MP 的证明机器。
等值演算与范式：把公式化成便于判断的形态。
可靠性、和谐性、完备性：连接语义真与形式可证。

本章没有常规“023 习题”文件，Auto_Tutor 中对应的是 23期中考试 与 23期中考试答案。下面的“测验答案”按试卷题号 1-6 整理。

2、命题与联结词

命题是有确定真假的陈述句。

不是命题的典型句子：

1
2
3
4
疑问句：8 大于 10 吗？
祈使句：请勿吸烟！
含自由变元的句子：x 大于 y。
悖论式句子：我正在撒谎。

命题逻辑把命题看作最小单位，常用命题变元：

1
p, q, r, ...

真值：

1
2
1 表示真
0 表示假

五个常用联结词

联结词 读法 真值条件
¬p 非 p p 假时真
p ∧ q p 且 q 二者都真时真
p ∨ q p 或 q 至少一个真时真
p → q 若 p 则 q 只在 p=1,q=0 时假
p ↔ q p 当且仅当 q 二者真值相同时真

自然语言中的“或”要分清相容或和相异或。命题逻辑里的 p ∨ q 默认是相容或：p、q 可以同时为真。

蕴含联结词的真值表：

1
2
3
4
5
p q | p->q
0 0 | 1
0 1 | 1
1 0 | 0
1 1 | 1

重点：p -> q 不表示时间先后，也不保证因果关系，它只是一个真值函数。

3、命题形式与真值表

命题形式由命题变元和联结词按规则递归生成：

1
2
3
4
5
6
1. 命题变元是命题形式。
2. 若 alpha 是命题形式，则 ¬alpha 是命题形式。
3. 若 alpha,beta 是命题形式，则
   alpha∨beta, alpha∧beta, alpha->beta, alpha<->beta
   都是命题形式。
4. 只有有限次应用以上规则得到的符号串才是命题形式。

约定：

1
2
¬ 的优先级最高。
可省略最外层括号。

指派与真值表

设公式 alpha 中出现的命题变元都在：

1
p1,p2,...,pn

一个指派就是给每个 p_i 指定 0 或 1。

分类：

1
2
成真指派：使 alpha 为真的指派。
成假指派：使 alpha 为假的指派。

公式分类：

1
2
3
重言式：所有指派下都真。
矛盾式：所有指派下都假。
可满足式：至少有一个成真指派。

例：

1
2
3
p ∧ ¬p 是矛盾式。
p ∨ ¬p 是重言式。
p -> q 等值于 ¬p ∨ q。

4、联结词完全集

真值函数：

1
f: {0,1}^n -> {0,1}

联结词集合 C 是完全集，意思是任意真值函数都能只用 C 中的联结词表示。

常见完全集：

1
2
3
4
5
6
{¬, ∨, ∧, ->}
{¬, ∨}
{¬, ∧}
{¬, ->}
{NAND}
{NOR}

常用表示：

1
2
3
4
alpha ∨ beta  等值于  (¬alpha) -> beta
alpha ∧ beta  等值于  ¬(alpha -> ¬beta)
alpha -> beta 等值于  ¬alpha ∨ beta
alpha <-> beta 等值于 (alpha -> beta) ∧ (beta -> alpha)

非完全集例子：

1
{∨, ∧, ->, <->}

原因：这些联结词都保真，也就是当所有变元都取 1 时，公式值总为 1，因此无法表示恒假函数。

只含 {¬,<->} 的公式也不是完全集。一个常用判别思路是：这类公式本质上只能表达“奇偶翻转/等价关系”，不能表示任意真值函数。

5、推理形式

推理形式由一组前提和一个结论组成：

1
alpha1, alpha2, ..., alphan 推出 beta

记作：

1
Gamma |= beta

含义：

1
对任意指派，只要 Gamma 中所有前提都为真，beta 也必为真。

有效推理的充要条件：

1
(alpha1 ∧ alpha2 ∧ ... ∧ alphan) -> beta

是重言式。

典型有效形式：

1
2
3
4
5
6
7
8
Modus Ponens:
alpha -> beta, alpha |= beta

析取消去:
alpha∨beta, alpha->gamma, beta->gamma |= gamma

反证:
若 Gamma∪{¬alpha} 推出 beta 且推出 ¬beta，则 Gamma |= alpha

6、自然推演系统 N

N 是命题演算的自然推理形式系统，更接近日常证明。

证明判断：

1
Gamma |-N alpha

读作：在自然推演系统 N 中，可从前提集合 Gamma 推出 alpha。

常用规则按“引入/消去”理解：

联结词 引入 消去
∧ 由 alpha 和 beta 得 alpha∧beta 由 alpha∧beta 得任一分量
∨ 由 alpha 得 alpha∨beta 分情况证明同一结论
-> 假设 alpha 推出 beta，解除假设得 alpha->beta MP
¬ 假设导致矛盾，推出否定 由 alpha 和 ¬alpha 得矛盾
<-> 双向推出后引入 得到两个方向

做 N 证明的经验：

1
2
3
4
目标是 alpha->beta：先假设 alpha，再证 beta。
目标是 alpha∨beta：常用反证或先证明一边。
已有 alpha∨beta：分别在 alpha、beta 两种情况下推出同一结论。
要证否定：假设其肯定式，推出矛盾。

7、形式系统 P

P 是公理化证明系统，联结词只取：

1
¬, ->

公式形式由命题变元、¬、-> 生成。

三个公理模式：

1
2
3
4
5
6
A1: alpha -> (beta -> alpha)

A2: (alpha -> (beta -> gamma))
    -> ((alpha -> beta) -> (alpha -> gamma))

A3: ((¬alpha) -> (¬beta)) -> (beta -> alpha)

推理规则：

1
2
3
4
MP:
alpha, alpha->beta
------------------
beta

证明序列中每一行必须是：

1
2
3
1. 公理模式的实例；
2. 前提；
3. 由前面两行用 MP 得到。

N 与 P 的关系：

1
Gamma |-N alpha  当且仅当  Gamma |-P alpha

也就是说，两套证明系统风格不同，但可证明能力等价。

8、赋值、等值演算与范式

在 P 中，赋值 sigma 给每个命题变元指定 0/1，并递归定义：

1
2
(¬alpha)^sigma = 1 - alpha^sigma
(alpha -> beta)^sigma = max(1-alpha^sigma, beta^sigma)

常用等值式：

1
2
3
4
5
6
7
¬¬alpha = alpha
alpha -> beta = ¬alpha ∨ beta
alpha <-> beta = (alpha -> beta) ∧ (beta -> alpha)
¬(alpha ∧ beta) = ¬alpha ∨ ¬beta
¬(alpha ∨ beta) = ¬alpha ∧ ¬beta
alpha ∧ (beta∨gamma) = (alpha∧beta)∨(alpha∧gamma)
alpha ∨ (beta∧gamma) = (alpha∨beta)∧(alpha∨gamma)

范式

简单合取式：

1
若干文字用 ∧ 连接。

简单析取式：

1
若干文字用 ∨ 连接。

析取范式 DNF：

1
若干简单合取式用 ∨ 连接。

合取范式 CNF：

1
若干简单析取式用 ∧ 连接。

主析取范式：

1
把所有成真指派对应的小项相析取。

主合取范式：

1
把所有成假指派对应的大项相合取。

从真值表写范式：

1
2
1. 成真行 -> 小项 -> 主析取范式。
2. 成假行 -> 大项 -> 主合取范式。

9、可靠性、和谐性与完备性

1
2
3
可靠性：可证则永真。
和谐性：不会同时证明 alpha 和 ¬alpha。
完备性：永真则可证。

常用考试模板：

1
2
3
4
5
6
证明是内定理：
给出 N 或 P 中的证明。

证明不是内定理：
给一个成假赋值；
再由可靠性说明它不可能可证。

10、单元测验答案

第 1 题、只用 ¬ 和 -> 表示 (p <-> q) ∨ r

题目：求一个只含联结词 ¬, -> 的命题形式 alpha，使：

1
alpha <-> ((p <-> q) ∨ r)

先把等价和析取消去：

1
2
3
p <-> q = (p->q) ∧ (q->p)
A ∧ B = ¬(A -> ¬B)
X ∨ r = ¬X -> r

令：

1
X = (p->q) ∧ (q->p)

则：

1
X = ¬((p->q) -> ¬(q->p))

所以：

1
alpha = ((p->q) -> ¬(q->p)) -> r

该公式只含 ¬ 和 ->。

第 2 题、真值表、析取范式与合取范式

题目：

1
alpha = p -> (¬(q∨r) -> r)

化简：

1
2
3
4
5
6
7
¬(q∨r) -> r
= ¬¬(q∨r) ∨ r
= (q∨r)∨r
= q∨r

alpha = p -> (q∨r)
= ¬p∨q∨r

真值表：

1
2
3
4
5
6
7
8
9
p q r | alpha
0 0 0 | 1
0 0 1 | 1
0 1 0 | 1
0 1 1 | 1
1 0 0 | 0
1 0 1 | 1
1 1 0 | 1
1 1 1 | 1

一个析取范式可以直接写成：

1
¬p ∨ q ∨ r

主析取范式：

1
2
(¬p∧¬q∧¬r) ∨ (¬p∧¬q∧r) ∨ (¬p∧q∧¬r) ∨ (¬p∧q∧r)
∨ (p∧¬q∧r) ∨ (p∧q∧¬r) ∨ (p∧q∧r)

一个合取范式，也是主合取范式：

1
¬p ∨ q ∨ r

因为唯一成假指派是 <1,0,0>。

第 3 题、用三元公式拼接两个二元公式

题目：设 alpha(q,r) 和 beta(q,r) 是两个二元命题形式，证明存在三元命题形式 gamma(p,q,r)，使得：

1
2
gamma(0,q,r) <-> alpha(q,r)
gamma(1,q,r) <-> beta(q,r)

构造：

1
gamma(p,q,r) = (¬p -> alpha(q,r)) ∧ (p -> beta(q,r))

验证：

1
2
3
4
5
6
7
8
9
p=0 时：
gamma = (1 -> alpha) ∧ (0 -> beta)
      = alpha ∧ 1
      = alpha

p=1 时：
gamma = (0 -> alpha) ∧ (1 -> beta)
      = 1 ∧ beta
      = beta

等价构造：

1
gamma = (¬p∧alpha) ∨ (p∧beta)

第 4 题、P 中的证明序列

本题使用 P 的公理模式 A1,A2,A3 和规则 MP。

4.1 证明 ¬alpha -> (alpha -> beta)

记：

1
theta = ¬beta -> ¬alpha

证明序列：

1
2
3
4
5
6
7
8
9
10
11
1. ¬alpha -> (¬beta -> ¬alpha)                         A1
2. (¬beta -> ¬alpha) -> (alpha -> beta)                 A3
3. [(¬beta -> ¬alpha) -> (alpha -> beta)]
   -> [¬alpha -> ((¬beta -> ¬alpha) -> (alpha -> beta))] A1
4. ¬alpha -> ((¬beta -> ¬alpha) -> (alpha -> beta))     MP 2,3
5. [¬alpha -> ((¬beta -> ¬alpha) -> (alpha -> beta))]
   -> ([¬alpha -> (¬beta -> ¬alpha)]
   -> [¬alpha -> (alpha -> beta)])                      A2
6. [¬alpha -> (¬beta -> ¬alpha)]
   -> [¬alpha -> (alpha -> beta)]                       MP 4,5
7. ¬alpha -> (alpha -> beta)                            MP 1,6

4.2 由 alpha -> (beta -> gamma) 证明 beta -> (alpha -> gamma)

前提：

1
1. alpha -> (beta -> gamma)                             Premise

证明序列：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2. [alpha -> (beta -> gamma)]
   -> [(alpha -> beta) -> (alpha -> gamma)]             A2
3. (alpha -> beta) -> (alpha -> gamma)                  MP 1,2

4. beta -> (alpha -> beta)                              A1

5. [(alpha -> beta) -> (alpha -> gamma)]
   -> [beta -> ((alpha -> beta) -> (alpha -> gamma))]   A1
6. beta -> ((alpha -> beta) -> (alpha -> gamma))        MP 3,5

7. [beta -> ((alpha -> beta) -> (alpha -> gamma))]
   -> ([beta -> (alpha -> beta)]
   -> [beta -> (alpha -> gamma)])                       A2
8. [beta -> (alpha -> beta)]
   -> [beta -> (alpha -> gamma)]                        MP 6,7
9. beta -> (alpha -> gamma)                             MP 4,8

第 5 题、在 N 中证明 (alpha -> beta) -> gamma ⊢ alpha ∨ gamma

前提：

1
(alpha -> beta) -> gamma

自然推演思路：

1
2
3
4
5
6
7
8
9
1. 假设 ¬(alpha∨gamma)。
2. 在该假设下，若再假设 alpha，则可由 ∨+ 得 alpha∨gamma，
   与 ¬(alpha∨gamma) 矛盾。
3. 因此在假设 alpha 下可推出任意 beta，
   从而得到 alpha -> beta。
4. 由前提 (alpha -> beta) -> gamma 和 MP 得 gamma。
5. 由 gamma 得 alpha∨gamma。
6. 这又与 ¬(alpha∨gamma) 矛盾。
7. 所以由反证法得到 alpha∨gamma。

简写为：

1
(alpha -> beta) -> gamma ⊢ alpha ∨ gamma

第 6 题、P+ 不和谐

P+ 是在 P 中增加下列公理模式得到的系统：

1
(¬alpha -> beta) -> (alpha -> ¬beta)

要证明：存在公式 gamma，使得：

1
2
|-P+ gamma
|-P+ ¬gamma

取：

1
gamma = p -> p

先说明 P+ 中可证 gamma，因为 P 中本来就可证：

1
|-P p -> p

而 P 的定理当然也是 P+ 的定理。

再证 ¬gamma：

1
2
3
4
5
6
1. gamma                                             已可证
2. gamma -> (¬gamma -> gamma)                        A1
3. ¬gamma -> gamma                                   MP 1,2
4. (¬gamma -> gamma) -> (gamma -> ¬gamma)             P+ 新公理，取 alpha=gamma,beta=gamma
5. gamma -> ¬gamma                                   MP 3,4
6. ¬gamma                                            MP 1,5

因此：

1
2
|-P+ gamma
|-P+ ¬gamma

P+ 不是和谐的。

11、复盘清单

1
2
3
4
5
6
7
8
1. 会区分命题、非命题、命题形式。
2. 会写五个联结词的真值条件，尤其是 p->q。
3. 会从真值表写主析取范式和主合取范式。
4. 会判断常见完全集与非完全集。
5. 推理有效性可以转成重言式判断。
6. N 证明更像自然语言证明；P 证明必须逐行说明 A1/A2/A3/MP。
7. 证明不可证常用“成假赋值 + 可靠性”。
8. 可靠性、和谐性、完备性分别对应可证与真值之间的三个方向/性质。