Coursera离散数学概论笔记（三）： 数理逻辑之谓词逻辑及形式系统

---

1 个体、谓词和量词

1.1 命题的解析

命题逻辑中最小的研究单位是原子命题，并没有进一步的内部结构。命题是对确定的对象作出判断的陈述句，那么对不确定的对象以及进行不同条件下的判断如何？这就需要我们研究命题的内部结构。

命题逻辑中的推理，关注真值的推演，命题逻辑中，命题是相互独立的，没有内在联系，在经典的三段论推理中，命题逻辑有些力不从心。比如：

三段论例子：

大前提：$p$p ：所有的学校都有学生

小前提：$q$q ：北京大学是学校

结论：$r$r ：北京大学有学生

命题逻辑的形式化结果：$(p \bigwedge q) \rightarrow r$(p⋀q)→r

一个正确推理在命题逻辑中并不是永真式（因为会受到原子命题的真值的影响）。而且三个命题包含了某些有关联的概念，并非相互独立，命题逻辑无法反映出来。

1.2 命题的结构分析

1.2.1 谓词逻辑

命题是对确定的对象作出判断的陈述句，其中：

• 被作判断的对象：个体
• 作出的判断：谓词
• 个体的数量：量词（所有、有些、没有）

谓词逻辑将量词作用于个体，引入个体变元，讨论不确定的对象。谓词逻辑也称作一阶逻辑（First Order Logic），如果将量词作用于谓词，引入谓词变元，属于二阶逻辑研究范围。

1.2.2 个体（individual）

谓词逻辑中将一切被讨论的对象都称作个体。

• 确定的个体常用 $a , b , c$a,b,c 表示，称作个体常元（constants）。
• 不确定的个体常用 $x,y,z,u,v,w$x,y,z,u,v,w 表示，称作个体变元（variables）。
• 被讨论的对象的全体称作个体域（domain of individuals）,常记作 $D$D 。
• 包含一切对象的个体域特称为全总域（universe），记作 $U$U 。

1.2.3 谓词（predicate）

1.2.3.1 定义

表示个体性质或者关系的语言成分，通常是谓语，称作谓词。例如：

“北京大学是学校”中的“…是学校”

“张三和李四的朋友”中的“…和…是朋友”

谓词中可以放置个体的空位个数称为谓词的元数。

1.2.3.2 谓词命名式

将谓词中的个体空位用变元字母代替，称为谓词命名式。

常用大写字母 $P,Q,R$P,Q,R 等代表谓词，谓词命名形如 $P(x),Q(x,y)$P(x),Q(x,y) 。

命名式中的变元字母并没有独立的含义，仅仅是占位符（place holder）。

举几个谓词命名式的例子：

“…是学校”记作SCHL(x)

‘’…和…是朋友‘记作FRD(x,y)

1.2.3.3 谓词填式

将谓词中的个体空位用个体变元或常元代替，称为谓词填式。

谓词填式在形式上和命名式相同，但是属于不同的概念（可以类比编程语言函数中的形参和实参）。

举几个谓词填式的例子：

当谓词填式中的个体都是常元时，它是一个命题，具有确定的真值。

1.2.4 量词（quantifiers）

指数量词：

• “所有”为全称量词，记作 $\forall$∀ 。
• “有”为存在量词，记作 $\exists$∃ 。

量词作用于谓词时需要引入一个指导变元，同时放在量词后面和谓词填式中，例如：$\forall x P(x)$∀xP(x) 。指导变元是不可取值代入的，称作约束变元，约束变元可以改名而不改变语句含义。可以取值代入的个体变元称作自由变元。

量词所作用的谓词或者复合谓词表达式，称作量词的辖域（domain of quantifiers）。对于一元谓词， $\forall x P(x)$∀xP(x) ，$\exists x P(x)$∃xP(x) 都是命题，对于有穷的个体域：

• $\forall x P(x)$∀xP(x) 等价于 $P(a_1) \bigwedge ... \bigwedge P(a_N)$P(a1​)⋀...⋀P(aN​)
• $\exists x P(x)$∃xP(x) 等价于 $P(a_1) \bigvee ... \bigvee P(a_N)$P(a1​)⋁...⋁P(aN​)

举几个量词的例子：

2 谓词公式

2.1 谓词公式的定义

谓词公式的定义如下：

• 谓词填式是公式，命题常元（可视为零元谓词）是公式，称作原子公式。

• 如果 $A,B$A,B 是公式，$x$x 为任一变元，那么 $(¬A),(A \rightarrow B),(\forall x A), (\exists x A)$(¬A),(A→B),(∀xA),(∃xA) 都是公式。

• 只有有限次使用上述两个条件构成的符号串才是公式。

联结词结合优先级和括号省略约定同前。

注意 $(\forall x A), (\exists x A)$(∀xA),(∃xA) 中的公式可以不包含变元 $x$x ， 此时 $(\forall x A), (\exists x A)$(∀xA),(∃xA) 均等价于 $A$A 。

2.2 谓词公式成为命题的条件

如果给定个体域，公式中的所有谓词都有明确意义，公式中的所有自由变元取定个体，谓词公式就成为一个命题。举一个例子：

2.3 语句形式化

举几个语句形式化的例子：

3 谓词公式永真式

3.1 谓词公式成真的几个层次

谓词公式一共有4个层次的“永真”：

1. 给定个体域D，公式A中各谓词符号的解释I，如果A中的自由变元 $x_1,...,x_n$x1​,...,xn​ 分别取值 $u_1,...,u_n$u1​,...,un​ 时A为真，则称A在 $u_1,...,u_n$u1​,...,un​ 处真。
2. 如果A在自由变元的任何取值下都为真，则称A在解释I下为真。
3. 如果A在每个解释I下均真，则称A在D上永真。
4. 如果A在任何个体域D永真，则称A永真。

可以用下图方便理解：

3.2 谓词公式可满足式以及永假式

可满足式：如果对于某个个体域，谓词的某个解释，和自由变元的某个取值，公式A在此处取值为真，则称公式A是可满足式。

永假式：公式A不可满足时也称A是永假式。

3.3 谓词公式的逻辑等价与逻辑蕴含

逻辑等价：$A \models\hspace{-5pt}|~ B$A⊨∣ B 当且仅当对于一切域、解释和变元取值情况，A和B都具有相同的真值。

逻辑蕴涵：$A \models B$A⊨B 当且仅当对一切域、解释，一切使A成真的变元取值情况均使B成真。

3.4 重要的谓词演算永真式

4 谓词演算形式系统FC

4.1 符号系统

4.2 合式公式

合式公式（well-formed formula），简称公式，需满足：

• 对任意非负整数 $n$n ，如果 $p^{(n)}$p(n) 是一个 $n$n 元谓词符，$t_1,...,t_n$t1​,...,tn​ 为项，那么 $p^{(0)}$p(0) （命题常元）和 $p^{(n)}(t_1,...,t_n) (n > 0)$p(n)(t1​,...,tn​)(n>0) 是公式；
• 如果 A，B 是公式，$v$v 为任一个体变元，那么 $(¬A),(A \rightarrow B),(\forall v A)$(¬A),(A→B),(∀vA) （或 $(\forall v A(v))$(∀vA(v)) )都是公式；
• 除有限次数使用上述两个条款确定的符号串外，没有别的东西是公式。

4.3 全称封闭式（generalization closure）

设 $v_1,...,v_n$v1​,...,vn​ 是公式A中的自由变元，那么公式 $\forall v_1...\forall n A(v_1,...,v_n)$∀v1​...∀nA(v1​,...,vn​) 称为公式A的全称封闭式。

A中不含自由变元时，A的全称封闭式为其自身。

4.4 FC的公理

4.5 FC的推理规则和重要性质

FC的推理规则（A，B表示任意公式）：$A,A \rightarrow B / B$A,A→B/B（分离规则）

FC的重要性质（类比PC）：

• 合理性、一致性、完备性
• 演绎定理
• 归谬定理
• 穷举定理

5 全称引入规则及存在消除规则

5.1 全称引入规则（universal generalization）

全称引入规则：对于任意公式 A ，变元 $v$v ,如果 $\vdash A$⊢A ，那么 $\vdash \forall v A$⊢∀vA 。

利用数学归纳法证明如下：

推广到演绎结果：对于任何公式集 $\Gamma$Γ ，公式 A 以及不在 $\Gamma$Γ 中任何公式自由出现的变元 $v$v ，如果 $\Gamma \vdash A$Γ⊢A ，那么 $\Gamma \vdash \forall v A$Γ⊢∀vA 。

关于全称引入规则的直觉表述：

5.2 存在消除规则（existential instantiation）

存在消除规则：设 A，B 为任意公式，变元 $x$x 是公式 A ，但不是公式 B 的自由变元，那么当 $\vdash \exists x A(x),A(x) \vdash B$⊢∃xA(x),A(x)⊢B 同时成立时，有 $\vdash B$⊢B 。

存在消除规则同样具有演绎的推广形式。

意义：如果 $A(x)$A(x) 能推出 B 成立，而 B 中并不包含变元 $x$x ，说明 B 的成立与 $x$x 的具体取值无关，只需要有 $x$x 能使 $A(x)$A(x) 为真，B 即为真。

数学证明中经常使用的“不妨设…”句式，即为使用了存在消除规则。

6 自然推理系统

6.1 PC和FC的不足之处

FC和PC的证明和演绎过程都过于繁复，为了追求简洁，只用了2个联结词、1个量词和一条推理规则。

如果能够引入更多的联结词、量词、推理规则，那么证明和演绎过程会显得更加自然。

6.2 人们经常在推理过程中使用的假设

在形式系统中引入带假设的推理规则，能够使推理过程更加接近人的思维，更加高效和便捷。

6.3 自然推理系统ND（Natural Deduction）

6.3.1 符号系统

引入全部5个联结词、2个量词，少数的公理，更多的推理规则，引入假设，用推理规则体现人的推理习惯。

6.3.2 公理

ND的公理只有一条：$\Gamma;A \vdash A$Γ;A⊢A （ $\Gamma$Γ 是公式集合）

6.3.3 推理规则

7 ND中的定理证明

7.1 ND中的证明和演绎

在 ND 中，称 $A$A 为 $\Gamma$Γ 的演绎结果，即 $\Gamma \vdash _{ND} A$Γ⊢ND​A 简记为 $\Gamma \vdash A$Γ⊢A ，如果存在如下序列：

$\Gamma_1 \vdash A_1,\Gamma_2 \vdash A_2,...,\Gamma_n \vdash A_n(\Gamma_n = \Gamma,A_n = A)$Γ1​⊢A1​,Γ2​⊢A2​,...,Γn​⊢An​(Γn​=Γ,An​=A) ，使得 $\Gamma_i \vdash A_i(1 \leq i \leq n)$Γi​⊢Ai​(1≤i≤n) :

1. 或者是公理；
2. 或者是 $\Gamma_j \vdash A_j(j<i)$Γj​⊢Aj​(j<i) ；
3. 或者是对 $\Gamma_{j1} \vdash A_{j1},...,\Gamma_{jk} \vdash A_{jk}(j1,...,jk<i)$Γj1​⊢Aj1​,...,Γjk​⊢Ajk​(j1,...,jk<i) 使用推理规则导出的。

如果有 $\Gamma \vdash A$Γ⊢A ，且 $\Gamma = \emptyset$Γ=∅ ，则称 $A$A 为 ND 的定理。

7.2 ND证明和演绎定理的例子

7.3 ND的一些重要性质

ND的重要性质：

• FC的公理和定理都是ND的定理
• ND是合理的、一致的、完备的。