1
数理逻辑
侯越先,yxhou@tju.edu.cn,16楼 -316室
一般性参考：
,离散数学,,左孝凌等，上海科学技术出版社
,数学家的逻辑,,哈密尔顿，商务印书馆
,元数学导论,,S,C．克林，科学出版社
课程辅助材料：
ftp://202.113.9.183/教师教学目录 /
2
数理逻辑的研究目的
逻辑（ Logics）研究的是 有效的 推理方法，数理逻辑
（ Mathematical Logics）就是用数学化（符号化）
的手段，研究 有效的 推理方法
什么是 有效的 推理方法?
a 有效的推理方法应具备 保真性,即如果推理前提真，
则推理结论真
b 有效的推理方法的保真性应是 普遍的,即不同的人，
在不同的语义环境下使用同样的推理方法，获得真假性相同的结论
例子：三段论他是医生，所以他是大夫
3
数理逻辑的研究目的
问题：是否所有真命题都可由满足条件 a和 b的推理方法获得？
,真,的分类：形式真、语义真和直觉真
下面中各个蓝色的结论的真假是由什么来决定的？推理形式、
语义和直觉？
1 他是医生,所以他是大夫
2 如果下雨，野餐将取消；
现在确实下雨了；
野餐将取消
3 如果 A优于 B；
且 B优于 C；
则 A优于 C
4 任何一个一班的同学都不能判定本语句是真的
4
数理逻辑的研究目的
注,d与说谎者悖论的区别（说谎者悖论,本语句是在说谎）
d与哥德尔不完备性定理之间的关系
数理逻辑的研究目的：研究 形式 有效的推理，
用 形式 手段地刻画人们对 形式 真的朴素理解。
5
逻辑学的历史
亚里士多德（ Aristotle,B.C,384-B.C,322）：三段论
莱布尼茨（ Gottfried Wilhelm von Leibniz,1646-
1716）：将推理还原为计算
布尔（ George Boole 1815-1864）：形式符号和等式，布尔代数
弗雷格（ Gottlob Frege,1848-1925）：一阶逻辑
罗素（ Bertrand Russell,1872-1970）：逻辑主义
希尔伯特（ David Hilbert,1862-1943）：形式主义
哥德尔（ Kurt Godel,1906-1978）：逻辑和形式方法不充分性
6
数理逻辑的主要内容
命题逻辑、谓词逻辑,非古典逻辑
模型论、证明论、递归论、公理化集合论模型论：用集合论的方法表示数学概念证明论：用形式化的方法研究数学证明的过程递归论：
7
第一章 命题逻辑
1-1 命题及其表示法
定义 1,命题 是一个具有确定真值的陈述语句
注,真值 表示真假的性质，其可能的取值只有,真,和
,假,,通常有,T”表示真,,F”表示假。
例子,5是一个整数
3是偶数
x+y=4
你吃过饭了吗?
我正在说谎任何一个一班的同学都不能断定本语句是真的
8
1-1 命题及其表示法
定义 2,原子命题 是不能再分解为更简单命题的命题
例子：苏格拉底是哲学家德国和法国都是欧洲国家
注,1 原子命题与维特根斯坦的原子事实
2 原子命题的界定 不宜 绝对化
3 原子命题常用大写字母 A,B,…,P，
Q,… 或带下标的大写字母来表示
9
1-1 命题及其表示法
定义 3：由原子命题、联结词或标点符号的复合构成的命题称 复合命题
例子,昨天下雨，今天也在下雨
定义 4：表示命题的符号称为 命题标识符
定义 5：一个命题标识符如果表示确定的命题，
称为 命题常元 ；如果命题标识符可以表示某类命题中的任何一个，称为 命题变元
10
1-2 命题的联结词
作用：规范日常语言中联结词（如,与,,,或,
等）在命题逻辑中的意义和用法，这里联结词可以看作是作用于命题之上的 运算符
定义 1：设 P为一命题,P的 否定 是一个新的命题，
记为 ┐ P。若 P为 T,┐ P为 F；若 ┐ P为 T,P为 F
例子,P：上海不是一个大城市
┐ P：？
11
1-2 命题的联结词
定义 2：两个命题 P和 Q的 合取 是一个复合命题，
记作 P∧Q 。当且仅当 P,Q同时为 T时,P∧Q 为 T，
其他情况下 P∧Q 均为 F
例子,P：地球是球形的
Q,牛顿是物理学家
P∧Q,地球是球形的并且牛顿是物理学家
P：拿破仑是科西嘉人
Q,拿破仑不是科西嘉人 （ ┐ P）
P∧Q,拿破仑是科西嘉人并且拿破仑不是科西嘉人
12
1-2 命题的联结词
注,1 ∧ 是汉语中,与,,,和,,,并,
的翻译，但 不能绝对化,例如,老张与小李是师徒,
2 合取在一起的两个命题不一定有实质的联系，也不一定是一致的，甚至可以将互为否定的命题合取在一起（该注释对其他逻辑联结词也适用）
定义 3：两个命题 P和 Q的 析取 是一个复合命题，记作 P?Q。当且仅当 P,Q同时为 F时，
P?Q的真值为 F；否则 P?Q的真值为 T
13
1-2 命题的联结词
例子,P：机器有故障
Q：开关有故障
P∨Q,机器有故障或开关有故障
注,∨ 是汉语中,或,的翻译，但不能绝对化。特别应 注意区分,可兼或,和,排斥或,。
例子,P：他是 78年出生的
Q：他是 79年出生的他是 78年出生的或 79年出生的表示为 P∨Q？
14
1-2 命题的联结词
定义 4：给定两个命题 P和 Q，其 条件 是一个复合命题，记作 P→Q,读作,如果 P，那么 Q” 或,P
蕴含 Q”。当且仅当 P的真值为 T,Q的真值为 F时，
P→Q 的真值为 F;否则 P→Q 的真值为 T。称 P为前项，
Q为后项
例子,P,月亮下山
Q,3+3=6
P→Q,如果月亮下山,则 3+3=6
15
1-2 命题的联结词
注,1 虽然上例的 P,Q之间并无实际联系，但只要 P,Q可分别确定真值，即可用,→,联结
2 Q→P 称为 P→Q 的 逆命题
┐ P→┐Q 称为 P→Q 的 反命题
┐ Q→┐P 称为 P→Q 的 逆反命题
3 前项 P为 F时，无论后项 Q取何真值,P→Q 的真值均为 T，这是所谓的,善意推定,
16
1-2 命题的联结词
补充说明,上面所定义,→,是所谓的,实质蕴含,。对于实质蕴含的合理性，存在着一定的争议。例如，根据实质蕴含的定义，下面的复合命题的真值必定为 T：
a (A→B)∨(B →A)
b F→A
a意味着任何两个命题之间有蕴含关系
b意味着假命题可以推出任何命题这并不符合人们关于蕴含的常识和直觉
17
1-2 命题的联结词
问题：形式逻辑系统是否可以精确地反映和把握人们关于蕴含和推理的全部直觉认识？
为了解决实质蕴涵的局限，人们提出了其他的蕴涵定义，如：严格蕴含、相干蕴含、直觉主义蕴含等。
总的来说，上述对于实质蕴含的发展可以在一定程度上解决实质蕴含的问题，但经常会带来新的问题甚至悖论。实质蕴含限制最少，包容性最强，形式最为简洁，是应用得最广泛的蕴含形式
18
1-2 命题的联结词
定义 5：给定两个命题 P和 Q，复合命题 P?Q称作双条件 命题，读作,P当且仅当 Q”，当 P和 Q的真值相同时,P?Q的真值为 T，否则 P?Q的真值为
F
注：双条件?的其他表示法
例子：
1 P,1+1=3
Q,雪是白的
P?Q,1+1=3当且仅当雪是白的
2 当且仅当明天不下雪且不下雨，我才去学校
3 只有他出差，我才会同意他不参加学习
19
1-2 命题的联结词
思考题：实质蕴含企图反映命题之间的必然联系，却并未反映命题之间的内容联系。尝试给出你自己的蕴含规则（可以利用和扩展前面介绍过的思路），以消除实质蕴含的反直觉怪论。
20
1-3 命题公式与翻译
定义 1,命题演算的 合式公式 （ wff），简称为合式公式 或 命题公式,规定为：
1) 单个命题变元本身是一个合式公式
2) 如果 A是合式公式，那么 ┐ A是合式公式
3) 如果 A和 B是合式公式，那么（ A∧B ）、
（ A∨B ）,(A→B) 和（ A?B)都是合式公式
4）当且仅当有限次地应用 1）,2）和 3）所得到的包含命题变元，联结词和括号的符号串是合式公式
21
1-3 命题公式与翻译
例子：指出 (P→(P?Q))中的哪些部分是命题公式
(wff)，并具体说明它是如何生成的解,① P
由 1)
② Q
由 1)
③ （ P?Q）是 wff
由 3)
④ (P→(P?Q))
由 3)
22
1-3 命题公式与翻译
例子：设计一个自然数集合的递归定义（皮亚诺公理）
约定：运算次序优先级,┐,?,?,→,?
相同的运算符按从左至右次序计算，否则要加上括号，最外层圆括号可省去
例子：如果命题 A等价命题 B，那么命题 C等价命题 D
23
1-4真值表与等价公式
定义 1：在 wff中，根据对分量指派真值的各种可能组合，求解 wff的对应真值，汇列成表，称为真值表
例子：构造 ┐ P→ （ P→Q ）的真值表解：
P Q ┐P P→Q ┐ P→ （ P→Q ）
F F T T T
F T T T T
T F F F T
T T F T T
24
1-4真值表与等价公式
例子：给出 ┐ (P?Q)?(┐P?┐Q) 的真值表解：
P Q P? Q ┐(P?Q) ┐P?┐Q ┐(P?Q)? (┐P?┐Q)
F F F T T T
F T F T T T
T F F T T T
T T T F F T
25
1-4真值表与等价公式
定义 2：一个命题公式如果对于其 分量 指派真值的各种可能组合，其真值恒为真（假），称该命题公式是 永真（假）式,记为 T（ F）
例子,P?┐P
P?┐P
P→Q
定义 3：给定两个命题公式,A(P1,P2...Pn),B(P1，
P2...Pn)若对于 P1,…,Pn任一组真值指派,A,B真值相同，称 A和 B是 等价的或逻辑相等,记为 A?B
问题：上面的定义是否有必要扩展到包含无限多分量的命题公式？
26
1-4真值表与等价公式
例子：求证 P?Q?(P→Q)?(Q→P)
解：
P Q P?Q Q→P P→Q (P→Q)?(Q→P)
F F T T T T
F T F F T F
T F F T F F
T T T T T T
27
1-4真值表与等价公式
基本的命题逻辑等价关系幂等律,P?P?P,P?P?P
结合律：（ P?Q）?R?P?（ Q?R）
（ P?Q）?R?P?（ Q?R）
交换律,P?Q? Q?P,P?Q?Q?P
分配律,P?(Q?R)?(P?Q)?(P?R）,
P?(Q?R)?(P?Q)?(P?R）
28
1-4真值表与等价公式
基本命题逻辑等价关系（续）
吸收律,P?(P?Q)?P,P?(P?Q)?P
德摩根律,┐ （ P?Q）?┐ P?┐Q
┐ （ P?Q）?┐ P?┐Q
同一律,P?F?P,P?T?P
零律,P?T?T,P?F?F
否定律,P? ┐ P?T,P? ┐ P?F
29
1-4真值表与等价公式
定义 4：如果 X是命题公式 A的一部分，且 X也是命题公式，则称 X是 A的 子公式
定理 1：设 X是命题公式 A的子公式，若 X?Y，则若将 A中的 X的 每一次出现 用 Y来置换，所得公式
B与 A等价，即 A?B
证明,因为对变元的任一组指派,X与 Y真值相同，故以 Y取代 X后，公式 B与公式 A相对于变元的任一指派的真值也必相同，所以 A?B
定义：称满足定理 1的置换为 等价置换
30
1-4真值表与等价公式
例子：证明下列命题公式（ 可以利用 基本的命题逻辑等价关系）
Q→ （ P?（ P?Q））?Q→P
（ P?Q)?（ P?┐Q)?P
P→Q?┐ P?Q
（ P→Q ） → （ Q?R）?P?Q?R
P?┐Q?Q?P?Q
31
1-5重言式与蕴含式
重言式即永真式；矛盾式即永假式
定理 1：任何两个重言式的合取或析取，仍然是重言式证明：设 A,B为两个重言式，则 A?B和 A?B的真值分别等于 T?T和 T?T
定理 2：对一个重言式的同一 分量 都用任何一个命题公式置换，所得命题公式仍为一个重言式证明：由于重言式的真值与分量的真值指派无关，故对同一分量以任何一个命题公式置换后，重言式的真值不变
问题：上述定理对于子公式替换的情形是否仍成立？
32
1-5重言式与蕴含式对一个重言式的同一分量用不同的命题公式置换，
所得命题公式是否仍为一个重言式？
对一个重言式的同一分量用 永假式 置换，所得命题公式是否仍为一个重言式？
定理 3：设 A,B是两个命题公式,A?B当且仅当
A?B是一个重言式证明：若 A?B，则对于 A,B所包含的分量的任意指派,A,B均取相同的真值，即 A?B是一个重言式；若 A?B是一个重言式，即对于分量的任意指派,A,B均取相同的真值，即 A?B
33
1-5重言式与蕴含式
例子,P→Q?┐ Q→┐P
永真式 永假式命题公式
34
1-5重言式与蕴含式
定义 1：当且仅当 P→Q 是一个重言式时，称
,P重言蕴含 Q”，在不会引起歧义的情况下，
简称为,蕴含,,记作 P?Q
例子,求证 ┐ Q?（ P→Q ）?┐ P
证法 1：
证法 2：
常用的蕴含关系式,p21，表 1-5.2
35
1-5重言式与蕴含式
定理 4：设 P,Q为任意两个命题公式,P?Q的充分必要条件是 P?Q且 Q?P
证明：若 P?Q，则 P?Q为重言式，即 P→Q 和 Q→P
是重言式；若有 P?Q且 Q?P，则 P→Q 和 Q→P 是重言式，即 P?Q为重言式
36
1-5重言式与蕴含式
蕴含的性质，设 A,B,C和 D为命题公式，则
1若 A是重言式，且有 A?B，则 B是重言式
2若有 A?B,B?C，则有 A?C，即蕴含关系是传递的
3若有 A?B,A?C，则有 A?（ B?C)
4如有 A?C,B?C，则有 A?B?C
37
1-6其他联结词
定义 1：设 P和 Q是两个命题公式，复合命题 P-?Q
称作 P和 Q的 不可兼析取 。当且仅当 P和 Q的真值不相同时,P-?Q的真值为 T，否则为 F
-?的性质：
P-?Q?Q-?P
（ P-?Q） -?R?P-?(Q-?R)
P?（ Q-?R）?（ P-?Q）?（ P-?R）
P-?Q?（ P?┐Q ）?（ ┐ P?Q）
P-?Q?┐ （ P?Q）
P-?┐P?F,P-?F?P,P-?T?┐P
38
1-6其他联结词
定理 1：设 P,Q,R是命题公式，如果 P-?Q?R，
则 P-?R?Q,Q-?R?P，且 P-?Q-?R为一矛盾式证明：若 P-?Q?R，则 P-?R?P-?P-?Q?F-?Q?Q
Q-?R?Q-?Q-?P?P
P-?Q-?R?R-?R?F
定义 2：设 P和 Q是两个命题公式，复合命题 Pc →
Q称为 P和 Q的 条件否定,Pc → Q的真值为 T，当且仅当 P的真值为 T,F的真值为 F
定义 3：设 P和 Q是两个命题公式，复合命题 P?Q
称为 P和 Q的 与非,当且仅当 P和 Q的真值都是 T时，
P?Q的真值为 F，否则其真值为 T
39
1-6其他联结词
定义 4：设 P和 Q是两个命题公式，复合命题 P? Q
称为 P和 Q的 或非,当且仅当 P和 Q的真值都是 F时，
P?Q的真值为 T，否则其真值为 F
联结词的种类：
一元联结词变量 运算
P f1 f2 f3 f4
0 0 0 1 1
1 0 1 0 1
永假 恒等 否定 永真
40
1-6其他联结词
二元联结词命题变元 运算
P Q f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 f16
1 1 1 0 1 1 0 0 1 0 1 0 1 0 1 0 1 0
1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 1 1 0
0 1 1 0 0 1 1 0 0 1 1 0 1 0 0 1 0 1
0 0 1 0 0 0 1 1 0 1 0 1 1 0 1 0 1 0
f1?T,f2?F,f3恒等 P,f4恒等 Q,f5?┐P,f6?┐Q,f7?P?Q
f8?┐(P?Q) f9?P?Q,f10?┐ （ P?Q）,f11?P→Q,f12?┐ (P→ Q)，
f13?P?Q,f14? ┐(P?Q),f15?Q→P,f16?┐ (Q→P)
除了 T,F和命题变元本身，需要再定义 9种联结词（ 5-6,7,8?,9,10?,11-15,
12-16c→,13,14 -?)
41
1-6其他联结词
问题：含 n个分量且互不等价的命题公式共有多少个？
定义 3：可以表示所有可能的真值函数（即联结词）的联结词集合，称为 联结词的充足集
定理 2：｛ ┐,?｝｛ ┐,? ｝，｛ ┐,→ ｝是联结词的充足集
定理 3：｛?｝和｛?｝是联结词的充足集
定义 4：若一联结词充足集的任意真子集不再是联结词的充足集，则称其为 极小联结词充足集
例子：｛?｝、｛?｝、｛ ┐,?｝、｛ ┐,? ｝、
｛ ┐,→ ｝（自证）
42
1-7对偶和范式
定义 1：在只包含联结词｛ ┐,?,?｝的命题公式 A中，将联结词?换成?，将?换成?，特殊变元
F和 T亦互换，所得公式 A*称为 A的 对偶式
例子：求 ┐ （ P?Q)?R的对偶式
定理 1：设 A*是 A的对偶式,P1,P2,P3……,Pn
是出现于 A和 A*中的 原子变元,则有
1)┐A(P1,P2,P3……,Pn）
A*（ ┐ P1,┐ P2,┐ P3……,┐Pn ）
2) ┐A *（ P1,P2,P3……,Pn）
A(┐P1,┐ P2,┐ P3……,┐Pn ）
43
1-7对偶和范式证明,1)施归纳于 A中出现的联结词的个数 n
n＝ 0时（即不含联结词时），则 A中只有一个原子变元，不妨记为 P1，显然有
┐ A（ P1）＝ ┐ P1＝ A*（ ┐ P1）
假定 n>0，即 A有 n个联结词，又具有少于 n个联结词的限制命题公式均满足式 1)。按命题公式的构造方式,A可能具有如下形式
a) ┐B b) B?C c) B?C
由归纳假设,┐ B?B* (┐),┐C?C*(┐),则：
a) ┐A(P1,P2,P3,…,Pn）?B
┐B * （ ┐ P1,┐P2,┐P3,…,┐Pn ）
A*（ ┐ P1,┐P2,┐P3,…,┐Pn ）
44
1-7对偶和范式
b) ┐A （ P1,…,Pn）
┐ （ B（ P1,…,Pn）?C（ P1,…,Pn））
┐ B（ P1,…,Pn）?┐ C（ P1,…,Pn）
B*（ ┐ P1,…,┐Pn ）?C*（ ┐ P1,…,┐Pn ）
A*（ ┐ P1,…,┐Pn ）
c) ┐A （ P1,…,Pn）
┐ （ B（ P1,…,Pn）?C（ P1,…,Pn））
┐ B（ P1,…,Pn）?┐ C（ P1,…,Pn）
B*（ ┐ P1,…,┐Pn ）?C*（ ┐ P1,…,┐Pn ）
A*（ ┐ P1,…,┐Pn ）
归纳步完成。由此,1）对于任意自然数 n成立
2）证明,证法一、证法二
45
1-7对偶和范式
例子,A（ P1,P2,P3） =┐P1?（ P2?P3），验证定理 1
解,1) ┐A （ P1,P2,P3）
┐ (┐P1?（ P2?P3））
┐ （ ┐ P1）?（ ┐ P2?┐P3 ）
A*(┐P1,┐ P2,┐ P3)
┐( ┐P1)?(┐P2?┐P3)
46
1-7对偶和范式
2) A（ ┐ P1,┐ P2,┐ P3）
P1?（ ┐ P2?┐P3 ）
┐ A*(P1,P2,P3)
┐ （ ┐ P1?（ P2?P3））
P1?（ ┐ P2?┐P3 ）
定理 2：如果 A?B，则 A*? B*
证明：设 P1,P2,…,Pn是出现在命题公式 A,B中的原子变元，因为 A?B，即,A（ P1,P2,…,Pn）
B （ P1,P2,…,Pn）是一个重言式。故有：
47
1-7对偶和范式
A（ ┐ P1,┐P2,…,┐Pn ）?B
（ ┐ P1,┐P2,…,┐Pn ）是一个重言式。即 A
（ ┐ P1,┐P2,…,┐Pn ）?B
（ ┐ P1,┐P2,…,┐Pn ）
再由定理 1,┐ A*? ┐B *,即 A*? B*
问题：是否每个 Pi,1<=i<=n,必须同时出现在 A和 B中，定理才能成立？
48
1-7对偶和范式
引入范式的目的：通过命题公式的标准形式，研究其性质。
定义 2：一个命题公式称为 合取范式,当且仅当它具有形式,A1?A2?…?An，其中 A1,A2,…,An都是由命题变元或其否定组成的析取式
定义 3：一个命题公式称为 析取范式,当且仅当它具有形式,A1?A2?…?An，其中 A1,A2,…,An都是由命题变元或其否定组成的合取式
49
1-7对偶和范式
求任意命题公式的合取（析取）范式的步骤
1）将公式中的联结词化成 ┐,?,?
2）利用德摩根律将否定符号 ┐ 直接移到各个命题变元之前
3）利用分配律、结合律将公式归约为合取范式
（析取）范式
注：一个命题公式的合（析）取范式不是唯一的，如
P?（ Q?R）?（ P?Q）?（ P?R）
（ P?P）?（ P?R）?（ P?Q）?（ Q?R）
50
1-7对偶和范式
定义 4,n个命题变元的合取式，称为 小项,其中每个变元与它的否定不能同时存在，但两者必须出现一次且仅一次
注,n个命题变元的小项有 2^n个由小项真值表（ p33）可知，没有两个小项是等价的，且每个小项只在一组真值指派下为 T
可以为小项指定一种编码，例如 m01对应于
┐ P?Q,m11对应 P?Q,m101对应 P?┐ Q?R等。
51
1-7对偶和范式小项的编码具有如下性质：当且仅当真值指派与小项的编码相同时，小项的真值为 T；否则小项的真值为 F
任意两个不同小项的合取为 F；
全体小项的析取为 T
定义 5：对于给定的命题公式，其中出现的原子变元记为 P1,P2,…,Pn。如果有一个等价公式，
它仅由 P1,P2,…,Pn的小项的析取构成，则该等价公式称为原式的 主析取范式
注：一个公式的主析取范式是唯一的
52
1-7对偶和范式
定理 3：在真值表中，一个命题公式的真值为 T的指派所对应的小项的析取，即为该命题公式的主析取范式证明：显然，对于任何真值指派，按如上方法构造的命题公式与原命题公式具有相同的真值；并且它又是一个小项的析取式，
即它是一个主析取范式
53
1-7对偶和范式
注：可以利用真值表，也可以利用等价变换来构造主析取范式
例子：求（ P?Q）?（ P?R）的主析取范式解：（ P?Q）?（ P?R）
（ （ P?Q）?（ R? ┐R ））?（（ P?R）?
（ Q? ┐ Q））
（ P?Q? R）?（ P?Q?┐R ）?（ P?┐ Q?R）
54
1-7对偶和范式
注：等价变换法求主析取范式的一般步骤
1）化归为析取范式
2）除去析取范式中所有永假析取项
3）合并重复项
4）补入合取项中没有出现的命题变元，例如添加（ P?┐ P）等,再用分配律展开
定义 6,n个命题变元的析取式，称为 大项,其中每个变元与它的否定不能同时存在，但两者必须出现一次且仅一次
55
1-7对偶和范式
注：可以为大项指定一种编码，例如,M00对应
P?Q,M101对应 ┐ P?Q?┐ R
大项具有如下性质：每个大项当其真值指派与编码相同时，其真值为 F，否则其真值为 T；
任意两个不同大项的析取为 T；全体大项的合取必为 F
定义 7：对于给定的命题公式，如果有一个等价公式，它仅由大项的合取组成，则该等价式称作原式的 主合取范式
注：一个公式的主合取范式是唯一的
56
1-7对偶和范式
定理 4：在真值表中，一个命题公式的真值为 F的指派所对应的大项的合取，即为该命题公式的主合取范式
证明：显然，对于任何真值指派，按如上方法构造的命题公式与原命题公式具有相同的真值；并且它又是一个大项的析取式，即它是一个主合取范式
注：主合取范式亦可由等价变换求得，基本步骤如下
1）化归为合取范式
2）除去合取范式中所有永真合取项
3）合并重复项
4）补入合取项中没有出现的命题变元，例如添加
（ P?┐ P）等,再用分配律展开
57
1-7对偶和范式
问题,n个命题变元的主析（合）取范式的共有多少个？
例：求 ┐ （ P?Q）? （ P?Q）的主合取范式解,┐ （ P?Q）?（ P?Q）
（ ┐ (P? Q)?(P? Q)）?((P?
Q)?┐(P?Q))
（ ┐ P?┐Q?P?Q）?((P?Q)?(┐P?┐Q))
(P? Q)?(┐P? ┐Q)
58
1-7对偶和范式
注：标记若 P的主析取范式为则其主合取范式为
kji mmmkji,,
kji MMMkji,,
12,.,,,1,1,.,,,0 11 nii
kiii,.,,,,21
59
1-8推理理论
推理的过程是由逻辑前提出发，根据逻辑推理规则，导出逻辑结论的过程。
推理的出发点是逻辑前提。逻辑前提有两种：逻辑永真式和假设前提。前者是命题逻辑系统固有的公理；后者由特定知识系统引入。
在某个特定的知识领域中做推理的时候，需要把该系统的定律、原理作为假设前提。一般地，具体系统的假设前提不应是逻辑永真式，但是在推理中这些假设前提的真值需要始终被认为是 T
定义 1：设 A和 C是两个命题公式，当且仅当 A→C
是一个重言式（即 A重言蕴含 C），称 C是 A的有效结论，或 C可由 A逻辑推出
60
1-8推理理论
注：上述定义可推广到 n个前提的情形：设 H1，
H2,…,Hn,C是命题公式，当且仅当
H1?H2?…?Hn→C 是重言式，称 C是前提 H1，
H2,…,Hn的有效结论
真值表法：直接给出包含前提 H1,H2,…,Hm和结论 C的真值表，检查是否每一个前提均为 T的行所对应的 C的真值也为 T；或者检查是否每一个结论 C为 F的行中至少有一个前提为 F
61
1-8推理理论
例子：前提,P?Q?R,┐ （ P?Q)；求证结论 R
P Q R P?Q?R ┐ （ P?Q）
0 0 0 0 1
0 0 1 1 1
0 1 0 1 0
0 1 1 1 0
1 0 0 1 0
1 0 1 1 0
1 1 0 1 0
1 1 1 1 0
62
1-8推理理论
问题：是否可以用真值表法作为一般的推理方法？
直接证法：由一组前提，利用推理规则，根据已知的等价或蕴含公式，推演得到有效结论。
P规则：前提在推导过程中的任何时候都可以使用。
T规则：推导中，如果有公式重言蕴含着 S，则公式
S可以引入推导注：等价式看作双向的蕴含
常用的蕴含（ Implication）式和等价
（ Equivalence）式见 p43
63
1-8推理理论
求证,R?S是前提 C?D,C→R,D→S 的有效结论。
证明,1 C?D P
2 C→R P
3 D→S P
4 ┐C→D T （ 1） E
5 ┐R→┐C T （ 2） E
6 ┐R→S T （ 5）（ 4）（ 3） I
7 R?S T（ 6） E
64
1-8推理理论
定义 2：设命题公式的集合为 { H1,.…,Hm}，
如果 H1?H2?…?Hm为永假式，则称公式 H1，
H2,…,Hm是不相容的；否则，称其为相容的
定理 1（间接证法 1 ）：设有一组前提 H1，
H2,…,Hm，要推出结论 C，只需证明 H1，
H2,…,Hm与 ┐ C是不相容的证明：要证 H1,H2,…,Hm推出 C，即要证
H1?H2?…?Hm?C。不妨将 H1?H2?…?Hm记作 S，
即要证 ┐ S?C为永真，故只需证 S?┐ C为永假
65
1-8推理理论
例子,求证 ┐ (P?Q)是 ┐ P?┐Q 的有效结论证,1 ┐┐(P?Q) P 附加前提
2 ┐P?┐Q P
3 P?Q T（ 1） E
4 P T（ 3） I
5 ┐P T （ 2） I
6 P?┐P( 矛盾 ) T（ 4）（ 5） E
所以,┐ (P?Q)?┐P?┐Q
66
1-8推理理论
定理 2（间接证法 2,CP规则 ）,设有一组前提 H1，
H2,…,Hm，要推出结论 R→C,只需证明
H1?H2?…?Hm?R?C
证明：设 H1?H2?…?Hm为 S，若 S?（ R→C ），
则有 S?（ ┐ R?C）
又 S→ （ ┐ R?C）?┐ S?（ ┐ R?C）
（ ┐ S?┐ R）?C
（ S?R） → C
故 S→ （ ┐ R?C）为永真式的充要条件是 （ S?R） → C
为永真式。
这样 H1?H2?…?Hm?R?C等价于 H1?H2?…?Hm?R→C
67
1-8推理理论
求证 W→┐T 是 P?Q→R?S,(T→Q)?(S→U),┐R,
(W→P)?(T→U) 的有效结论证,1 P?Q→R?S P
2 (T→Q)?(S→U) P
3 (W→P)?(T→U) P
4 ┐R P
5 W P 附加前提
6 ┐(R?S) T（ 4） I
7 ┐(P?Q) T（ 1）（ 6） I
8 P T（ 5）（ 3） I
9 ┐Q T （ 7）（ 8） I
10 ┐T T （ 9）（ 2） I
11 W→┐T T （ 10） CP
68
思考题,考试佯谬
逻辑课老师在周末放学时对学生说：
条件一：下周要进行一次考试；
条件二：到底哪天考试,你们在考试之前的任何一天都不能确知 。
注：每周上课 5天 （ 周一至周五 ）,每天都上一节逻辑课只有在逻辑课时才可能考试 。
一个聪明的学生运用逻辑知识做出了以下推理：
推论一：周五不可能考试,考试时间一定是周一至周四的某一天 。 因为如果周一至周四都不考,那么周四下课时我们就事先知道了明天一定考试,这不符合条件二 。 但根据条件一,下周肯定考试,因此考试时间只能是周一至周四的某一天,周五可以排除 。
69
思考题,考试佯谬
推论二：周四也不可能考试，考试时间一定是周一至周三的某一天。因为如果周一至周三都不考，那么周三放学时我们就事先知道了明天考试，这不符合条件二。但根据条件一，下周肯定考试，因此考试时间只能是周一至周三的某一天，周四可以排除。
推论三：周三也不可能考试,推理过程同上 。
推论四：周二也不可能考试,推理过程同上 。
推论五：周一也不可能考试,推理过程同上 。
结论：下周就不可能考试
70
思考题,考试佯谬
但是老师确实在下周的某一天考试了，这个聪明同学感到非常意外。问题究竟出在哪里呢？
一篇短文，说明你对这个问题的看法，下次课提交。
提示：将推理过程形式化
不失一般性，考虑简化问题的版本：每周只有两次逻辑课，分别在周一和周四。教师在本周四下课时宣布下周将有一次逻辑考试。。。
71
思考题,考试佯谬
考试佯谬的一个形式表述
命题常元
ExamB,考试在下周一的逻辑课上进行
ExamD,考试在下周四的逻辑课上进行
Know,学生在考试所在的那天之前知道考试的时间
系统公理,A1,（ ExamB?┐ExamD ）?（ ┐ ExamB?ExamD）
A2,┐ Know
A3,┐ ExamB→Know
A4,┐ ExamD→Know
72
思考题,考试佯谬
论证过程,用间接证法 1证明 A1-A4和 ExamD矛盾，推出 ┐ ExamD；
再用间接证法 1证明 A1-A4和 ExamB矛盾，推出 ┐ ExamB
（ 1） 1 ExamD 附加前提
2（ ExamB?┐ExamD ）?（ ┐ ExamB?ExamD） P
3（ ExamB?ExamD）?（ ┐ ExamB?┐ExamD ） T (2)
4 ┐ExamB?┐ExamD T (3)
5 ┐ExamB T (1)(4)
6 ┐ExamB→Know P
7 Know T (5)(6)
8 ┐Know P
所以，有 ┐ ExamD
73
思考题,考试佯谬
(2) 1 ExamB 附加前提
2（ ExamB?┐ExamD ）?（ ┐ ExamB?ExamD） P
3（ ExamB?ExamD）?（ ┐ ExamB?┐ExamD ） T (2)
4 ┐ExamB?┐ExamD T (3)
5 ┐ExamD T (1)(4)
6 ┐ExamD→Know P
7 Know T (5)(6)
8 ┐Know P
所有，有 ┐ ExamB
综合（ 1）和（ 2），有 ┐ ExamB?┐ExamD
74
思考题,考试佯谬
两个结论,1 学生推理的没有错误
2 教师的两个条件符合事实，故应视为真命题
问题,似乎正确的前提和正确的推理导致了错误的结论
（即与教师宣称的真命题矛盾的结论），为什么？
回答,佯谬之所以出现，是因为试图将一个广义 哥德尔型命题 （可粗略地理解为涉及系统 元知识 的命题）显式地作为系统公理，来建构系统的完备性。不幸的是，一旦这个原本是直觉真的广义哥德尔型命题在系统中被作为公理显式地表达出来，系统在一致性方面就产生了新的问题。
,There are truths of silence,when spoken,no
longer true anymore.” Ludwig Wittgenstein
75
1-9形式化命题逻辑系统 L
考试佯谬这类逻辑悖论促使人们深入省思逻辑系统的本质，它的能力和局限。对形式化的逻辑系统的研究有助于实现这个目的。在理论方面：形式化逻辑系统帮助人们澄清逻辑系统的 元性质 (一致性、完全性）,澄清基本的数学哲学问题（例如，数学是否可以形式化－希尔伯特方案）；在应用方面：形式化逻辑系统在理论计算机科学、计算机科学、人工智能、软件工程等领域有着深刻的应用。
命题逻辑形式系统 L定义如下
1 符号字母表,┐,→,（，）,p1,p2,p3,…
注：｛ ┐,→ ｝是联结词的充足集
76
1-9形式化命题逻辑系统 L
2 命题公式的集合：如下 3条递归规则确定命题公式的集合
（ 1）对每个 i>=1,pi是命题公式
（ 2）若 A和 B是命题公式，则（ ┐ A）和（ A→B ）是命题公式
（ 3）所有命题公式由递归应用（ 1）和（ 2）产生
3 公理：
L1,（ A→ （ B→A ））
L2,（（ A→ （ B→C ）） → （（ A→B ） → （ A→C ）））
L3,（（（ ┐ A） → （ ┐ B）） → （ B→A ））
注,A,B和 C可以是任意命题公式显然，公理 L1-L3是永真式
77
1-9形式化命题逻辑系统 L
4 演绎规则（分离规则，记为 MP)：从 A和（ A→B ），可以获得 B
定义 1,L中的一个证明是命题公式的一个序列 A1,A2,…,An，
使得对每个 i（ 1<=i<=n),Ai或者是 L的公理，或者是由序列中在前面的两项利用演绎规则得到的
注,L中的公理当然也是 L中的定理，它们在 L中的证明是其自身
例子：如下序列是 L中的证明
（ 1）（ p1→ （ p2→p1 ）） L1
（ 2）（（ p1→ （ p2→p1 ）） → （（ p1→p2 ） → （ p1→p1 ）） L2
（ 3）（（ p1→p2 ） → （ p1→p1 ）） （ 1），（ 2）,MP
78
1-9形式化命题逻辑系统 L
例子：在 L中求证 Q→R 是 P,Q→ （ P→R ）的逻辑结论证明,P P
Q→ （ P→R ） P
P→ （ Q→P ） L1
Q→P (1),(3) MP
(Q→ （ P→R ） )→((Q→P)→ （ Q→R ）） L2
(Q→P)→ （ Q→R ） (2),(5) MP
（ Q→R ） (4),(6) MP
79
1-9形式化命题逻辑系统 L
对于系统 L，我们关心如下一些问题：是否 L的每个定理都是重言式；基于 L的推演是否可能导致矛盾：即对任意的命题公式 A和 ┐ A，是否可能同时被 L证明为定理；以及 L是否可以证明 所有 永真式
定义 2（可靠性定义）：若 L的任意定理都是重言式，则称 L是 可靠的
定义 3（一致性定义）,若 L的任意互为否定的命题公式 A
和 ┐ A不同时为 L的定理，则称 L是 一致的
定义 4（完备性定义）：若 L中的任意重言式都是 L的定理，
则称 L是 完备的
定义 5（可判定性定义）：若存在一个通用的算法，判定任意命题公式是否是 L的定理，则称 L是 可判定的
定理 1（可靠性定理）,L的可靠的
80
1-9形式化命题逻辑系统 L
证明：（数学归纳法）设 A是 L的定理，施归纳于 A
的证明序列中所含命题公式的个数 n。
当 n＝ 1时,A的证明序列只包含一个命题公式,A是 L的公理，即 A是重言式当 n>1时，假设 L中证明序列长度小于 n的定理都是重言式
（归纳假设）。由于定理 A在 L中存在一个证明，则 A或者是 L的公理，或者由 MP规则获得。当 A是 L的公理时,A显然是重言式。当 A是由 MP规则获得时，其证明序列中必存在两个命题公式，不失一般性，记为 B和 B→A 。由于 B和
B→A 的证明序列长度小于 n，由归纳假设，它们是重言式。
这样 A必然是重言式。
综上,L是可靠的。
81
1-9形式化命题
定理 2（一致性定理）,L是一致的证明：反证法，若 L是不一致的，则存在命题公式 A，使得 A和 ┐ A均为 L的定理。由 L的可靠性定理,L的定理必是重言式，矛盾。
定理 3（完备性定理）,L是完备的证明：略。
定理 4（可判定性定理）,L是可判定的。
证明：真值表法。
82
1-9形式化命题逻辑系统 L
进一步的思考：更重要和实际的形式数学系统，如形式化数论系统，是否也具有系统 L的良好性质？如果回答是肯定的，上述数学系统的全部内涵即可由形式系统囊括，
至少在理论上，我们可以编写一个计算机程序，利用简单地穷尽搜索，逐步获得一个又一个定理，数学发现的过程可以还原为计算机程序操作
回答：这样的前景从来不会发生。 绝大多数 实际数学系统的形式化是不完备的（哥德尔第一不完备性定理），
甚至其一致性也无法在系统之内得到证明（哥德尔第二不完备性定理）。 数学真理不可能由包括程序在内的任何机械过程所穷尽，而必然包含直觉和洞察的成份 。存在着对于人的直觉来说明显为真，但无法形式证明的良定义数学命题（哥德尔）；存在无限多不可由,机械过程,计算的函数（图灵）；存在着具有重要实际意义，
但无法被机械过程解决的判定问题（停机问题－图灵）。
83
1-9形式化命题逻辑系统 L
注：机械过程?现代数字计算机程序?算法?图灵机所谓的,机械过程,,应广义理解，指可实现的物理过程。
,机械过程,涉及到数学之外的物理的内涵。量子计算的某些最新理论研究结果似乎暗示，某种理论上的量子计算模型似乎可以实现某些经典机械过程无法实现的计算任务（如等价于停机问题的丢番图方程解的存在性判定问题），但是上述结果尚未形成定论。
思考题,某些人认为，形式数学系统的不完备性意味着人工智能的不可能性，存在着直觉上为真但形式系统内无法证明的真理，说明人心比机器和程序更优越，程序不可能充分模拟人类智能。谈谈你对该问题的看法。
进一步的参考书目：
,皇帝新脑,,彭罗斯，胡南科技出版社
,哥德尔、埃舍尔、巴赫,,D,Hofstadter,商务印书馆
84
第二章 谓词逻辑
2-1谓词的概念与表示
目的,1 刻画客体的 性质 或 关系 2 克服命题逻辑的局限
例子,他 是三好学生他,x,是三好学生 P(.)； P(x)：他是三好学生
7是质数
7,x,是质数 P(.)； P(x),7是质数
例子：人都是要死的；
苏格拉底是人；
所以苏格拉底是要死的。
注：用大写字母表示谓词，用小写字母表示客体名称
（常元或变元）
用谓词＋客体名称构成一个完整命题
A(x):一元谓词； A(x,y)二元谓词； …
85
2-1谓词的概念与表示
谓词字母填上客体名称后形成的式子称为谓词填式代表客体名称的字母，一旦确定其所指，在多元谓词中以不同次序出现将导出不同的谓词。
例如,a,b确定地指代不同对象，则 A(a,b)和
A(b,a)是两个不同命题。
谓词刻画客体的性质和关系
86
2-2命题函数与量词
目的：简洁地表达相关命题的集合
定义 1：由一个谓词，一些客体变元构成的表达式称为简单 命题函数
例子,S（ x）,x是好学生，当 x分别指代张三、
李四和王五时，代表三个不同的命题
S（ x,y,z）,x+y=z，当 x,y和 z 分别指代不同的数时，代表一些不同的命题
87
2-2命题函数与量词
注,n元谓词就是有 n个客体变元的命题函数，当 n＝ 0时，
称为 0元谓词，它本身就是一个命题一个或多个简单命题函数以及逻辑联结词，根据命题公式递归构造规则，组合成的表达式称为复合命题函数命题函数不是一个命题，只有客体变元的所指确定之后，才能成为一个命题。
客体变元在的取值范围内对于命题函数所确定的命题的真值有很大影响。
定义 2：在命题函数中，客体变元的论述范围称为 个体域 ；
一个命题函数中所有客体变元的个体域之并称为命题函数的个体域
注：个体域可能有限，也可能无限
88
2-2命题函数与量词
存在量词的引入例子,God存在性的本体论证明（圣安瑟伦）
定义 God为具有所有积极属性者，则 God必存在。
证明,（反证法）假设 God不存在，则我们可以设想一个 God*,God*保有 God的所有其他积极属性，除了需要额外设想 God*是存在的。 由于存在性是比虚无性积极的属性,
所以 God*比 God具有更多的积极属性，与前面对 God的定义矛盾。故 God存在。
你接受这个证明吗？
89
2-2命题函数与量词
康德的回答：存在性不能作为一个谓词
P(x),x是存在的 （非法谓词）
例子：用谓词表达,某个单位的职工中有大学生,这个命题。
1)G(x),x是大学生
E(x)：存在 x
假设 x的个体域是某单位的职工则有,E(x)?G(x)
2） G(x):x是大学生假设 x的个体域是某单位的职工使用存在量词?，则有 （?x） G(x)
90
2-2命题函数与量词
是 存在量词
x读作 ‘ 存在 x?
x ┐P(x) 表示 ‘ 存在 x，使 ┐ P(x)为真 ’
┐?x ┐P(x) 表示 ‘ 不存在 x，使 P(x)为真 ’
全称量词的引入例子：假设用谓词表达,某个单位的职工全是大学生,
这个命题。
G(x):x是大学生；
假设 x的个体域是某单位的职工
（?x） G(x)
假设 x的个体域是该单位所在城市的全体职工？
91
2-2命题函数与量词
x是全称量词
x读作 ‘ 对任意 x?
（?x） P(x)表示 ‘ 对一切 x,P(x)为真 ’
（ ┐?x） ┐ P(x)表示
‘ 并非对任意 x,┐P(x) 是真 ’
全称量词和存在量词可以相互表示：
（?x） P(x）?┐ (?x) ┐P(x)
(?x) P(x)
92
2-2命题函数与量词
定义 3,所有一组特定命题函数的个体域的并，称为 全总个体域
例子,M(x),x是人； D(x),x是要死的； S(x),x怕死
1） 若论述域是全人类：
则 ‘ 人总是要死的 ’ 可译为?xD(x)
有些人不怕死 ’ 可译为?x┐S(x)
2） 若论述域是包括非人类的某个全总个体域：
则 ‘ 人总是要死的 ’ 可译为?x(M(x)→D(x)) 。
注意不能译为?x(M(x)?D(x))。
其意义是 ‘ 所有的 x,x都是人并且都是要死的 ’
‘ 有些人不怕死 ’ 可译为?x(M(x)?┐S(x))
93
2-2命题函数与量词
注,1）对全称量词，类别谓词作为蕴含式之前项加入
2）对存在量词，类别谓词作为合取项加入
例子：
没有不犯错误的人解：设 F(x)为 ‘ x会犯错误 ’,M(x)为 ‘ x是人 ’,则译为,
┐(?x (M(x)?┐F(x)))
用?x的形式表达？
某些人对某些食物过敏解：设 F(x,y)为 ‘ x对 y过敏 ’,M(x)为 ‘ x是人 ’,
G(x)为 ‘ x是食物 ’,则译为,
x?y (M(x)?G(x)?F(x,y))
94
2-2命题函数与量词尽管有人聪明，但未必一切人聪明解：设 M(x)为 ‘ x是人 ’,F(x)为 ‘ x聪明 ’ 则译为,
x(M(x)?F(x))?┐?x(M(x)→F(x))
每个建筑物都有一些装饰品解：设 A(x)为 ‘ x是建筑物 ’,
B(x,y)为 ‘ x有 y?，
C(x) 为 ‘ x是装饰品 ’,
则可译为：
x(A(x)→?y(B(x,y)?C(y))
用?x的形式表达？
95
2-2命题函数与量词对于实数 x,y和 z，如果 x>y，并且 z>0，那么 xy>yz
解：设 >(x,y) 为 ‘ x>y?,R(x)为 ‘ x是实数 ’
则译为,
x?y?z(R(x)?R(y)?R(z)→
((>(x,y)?>(z,0))→>(xy,yz))
96
2-3谓词公式与翻译
客体常元、客体变元和 客体函元 。客体函元即某个函数作用于客体常元或客体变元的结果，例如 f(x),x是客体常元或客体变元
定义 1：形如 A(x1,x2,…,xn)的公式称为 谓词演算的原子公式,其中 x1,x2,…,xn是客体变元、客体常元或客体函元
定义 2：谓词演算的合式公式的递归定义如下
1） 原子谓词公式是合式公式
2） 若 A是合式公式，则 ┐ A是合式公式
97
2-3谓词公式与翻译
3） 若 A和 B是合式公式，则（ A?B），（ A?B），（ A→B ）和
（ A?B）是合式公式
4） 如果 A是合式公式,x是 A中的任何变元，则（?x） A和（?x） A
是合式公式
5） 只有经过有限次应用步骤 1）－ 4）所获得的公式才是合式公式
注：最外层的括号可以省略，但量词后面的括号一般不能省略谓词合式公式简称为谓词公式符合语法的谓词公式的语义不一定总是符合直觉的，例如考虑如下谓词公式：
（?x）（?x） A（ x）,（?x） （?x） A（ x）
98
2-3谓词公式与翻译
思考题：如何用程序判定一个字符串是否是谓词公式？
例子：
并非每个实数都是有理数
（?x）（ R（ x）?┐ Q（ x））
如果一个数是偶数，那么它至少有一个素因子为偶数
Even（ x）,x是偶数
Factor（ x,y）,y是 x的素因子
（?x）（ Even（ x） → （?y）（ Factor（ x,y）?Even（ y）））
99
2-4变元的约束
定义 1,谓词公式 A的一部分形如（?x） P（ x）或（?x）
P（ x），则?或?后面所跟的变元叫做量词的 指导变元 或作用变元,P（ x）叫做相应量词的 作用域 或 辖域,在作用域中 x的一切出现，称为 x在 A中的 约束出现,x亦称为被相应量词中的指导变元所约束的 约束变元 。不是约束变元的客体变元称为自由变元
例子：指出下式中的自由变元和约束变元，以及指导变元的辖域
（?x） P(x)→Q(x)
（?x）（?y） (P(x,y)→Q(x,y) )?P(y,z)
100
2-4变元的约束
注：由约束变元的概念,P(x1,x2,…,xn)是 n元谓词，
有 n个独立的自由变元若对 P(x1,x2,…,xn)的 n-k个自由变元进行约束，
则成为 k阶谓词若 对 P(x1,x2,…,xn)的所有自由变元进行约束，
则成为一个命题为什么？
为了避免变元的约束形式和自由形式同时出现，引起混淆，可对变元做 换名,使得一个变元在一个公式中只呈一种形式出现
（?x） P（ x） → Q（ x）
101
2-4变元的约束
换名规则：
1）对约束变元可以进行换名，其更改的范围是量词中的指导变元和量词的作用域中出现的该变元，公式的其余部分不变
2）换名时要更改为作用域中没有出现的变元名称
可对自由变元换名，一般称对自由变元的换名为 代入
代入规则：
1）代入时需对公式中出现该自由变元的每一处进行
2）用以代入的变元与原公式中所有变元的名称不能相同
3）可以用客体常元做代入,但此时不是等价替换
102
2-4变元的约束
例子：对（?x）（ P（ x） → R（ x,y））?Q（ x,y,z）换名解,（?w）（ P（ w） → R（ w,y））?Q（ x,y,z）？
（?y）（ P（ y） → R（ y,y））?Q（ x,y,z）？
（?z）（ P（ z） → R（ z,y））?Q（ x,y,z）？
对（?x） (A(x)?B(x,y))?C(x)?D(w)换名、代入解,（?z） (A(z)?B(z,y))?C(x)?D(w)？
（?w） (A(w)?B(w,y))?C(z)?D(w)？
对（?x）（ P（ y）?R（ x,y））代入解,（?x）（ P（ z）?R（ x,z））？
（?x）（ P（ z）?R（ x,y））？
103
2-4变元的约束
注：量词作用域中的约束变元，当论域的元素有限时，
客体变元的所有代入是可枚举的。例如，若论域是｛ a，
b｝则有：
（?x） P（ x）? P（ a）?P（ b）
（?x） P（ x）?P（ a）?P（ b）
量词对变元的约束与量词的次序有关，改变次序可能改变谓词公式的含义设论述域为有理数,P(x,y)表示 x+y=0,Q(x,y)表示 x*y=0
(?y)(?x)(P(x,y)) (?x)(?y)(P(x,y)=0)
(?x)(?y)(Q(x,y)) (?y)(?x)(Q(x,y)=0)
104
2-5谓词演算的等价公式与蕴含式
定义 1：用确定客体取代谓词公式中的客体变元的过程，
称作对谓词公式 赋值 。赋值后的谓词公式成为具有确定真值的命题
定义 2：给定两个谓词公式 A和 B，设其具有相同的个体域
E，若对 A和 B中的任一组变元进行赋值，所得命题的真值相同，称谓词公式 A和 B在 E上是 等价 的，记作 A?B
定义 3：给定任意谓词公式 A，其个体域为 E，若对于 A的所有赋值，均使其真值为 T，则称 A在 E上是 永真的（或有效的）
定义 4：给定任意谓词公式 A，其个体域为 E，若对于 A的所有赋值，均使其真值为 F，则称 A在 E上是 不可满足的
105
2-5谓词演算的等价公式与蕴含式
定义 5：给定任意谓词公式 A，其个体域为 E，若至少存在
A的一组赋值，使其真值为 T，则称 A在 E上是 可满足的
注：谓词演算中赋值的作用类似于命题演算中真值指派的作用，即赋值使得谓词具有了特定真值。
若谓词公式 A中不包含自由变元，则给定 A的个体域 E，
即可确定 A的真值（更确切地说，是包括了个体域的 解释确定了 A的真值。所谓解释，这里可粗略理解为谓词符号的语义和谓词公式的个体域）
当谓词演算中的公式代替命题演算中永真式的命题变元时，所得的谓词公式即为谓词演算的永真式，故命题演算中的等价公式和蕴含式都可以在谓词演算中使用。 为什么？
106
2-5谓词演算的等价公式与蕴含式
例子：（?x）（ P（ x） → Q（ x））?（?x）（ ┐ P（ x）
Q（ x））
量词与联结词 ┐ 之间的关系（量词转化律）：
┐ （?x） P（ x）?（?x） ┐ P（ x）
┐ （?x） P（ x）?（?x） ┐ P（ x）
注：出现在量词前的否定，不是否定该量词，而是否定被该量词量化的整个命题
有限个体域上量词转化律的证明：
设个体域中的客体为 a1,a2,…,an，则
107
2-5谓词演算的等价公式与蕴含式
1） ┐ (?x） P(x)
┐(P(a1)?P(a2)?…?P(an))
┐P(a1)? ┐P(a2)?…? ┐P(an)
（?x） ┐ P(x)
2） ┐ （?x） P(x)
┐(P(a1)?P(a2)?…?P(an))
┐P(a1)?┐P(a2)?…?┐P(an)
（?x） ┐ P(x)
注：上述结果可以推广到无穷的个体域
108
2-5谓词演算的等价公式与蕴含式
量词作用域的扩张与收缩：
1）（?x） A(x)?P?（?x） (A(x)?P)
2）（?x） A(x)?P?（?x） (A(x)?P)
3）（?x） A(x)?P?（?x） (A(x)?P)
4）（?x） A(x)?P?（?x） (A(x)?P)
5）（?x） A（ x） → B?（?x）（ A（ x） → B）
6）（?x） A（ x） → B?（?x）（ A（ x） → B）
7） B→ （?x） A（ x）?（?x）（ B→ A（ x） ）
8） B→ （?x） A（ x）?（?x）（ B→ A（ x） ）
9） (?x)A(x)→(?x)B(x)?(?x)(A(x)→ B(x))
109
2-5谓词演算的等价公式与蕴含式证明,6）（?x） A（ x） → B
┐ （?x） A（ x）?B
（?x） ┐ A（ x）?B
（?x）（ A（ x） → B）
8） B→ （?x） A（ x）
┐ B?（?x） A（ x）
（?x）（ ┐ B?A（ x））
（?x）（ B→ A（ x））
注：当谓词的变元与量词的指导变元不同时，亦能有类似上述诸式的结果，例如：
(?x)A(x)→B(y)?(?x)(A(x)→B(y))
110
2-5谓词演算的等价公式与蕴含式
量词与命题联结词的一些等价公式：
1) (?x)(A(x)?B(x))?(?x)A(x)?(?x)B(x)
2) (?x)(A(x)?B(x))?(?x)A(x)?(?x)B(x)
证明,2）?x(┐A(x)?┐B(x))
(?x)(┐A(x))?(?x)(┐B(x))
两边取非：
┐?x(┐A(x)?┐B(x))
┐( (?x)(┐A(x))?(?x)(┐B(x)))
(?x)(A(x)?B(x))
(?x)A(x)?(?x)B(x)
111
2-5谓词演算的等价公式与蕴含式
量词与命题联结词之间的一些蕴含式：
1) (?x)A(x)?(?x)B(x)?(?x)(A(x)?B(x))
2) (?x)(A(x)?B(x))?(?x)A(x)?(?x)B(x)
3) (?x)(A(x)→B(x))?(?x)A(x)→(?x)B(x)
4) (?x)(A(x)?B(x))?(?x)A(x)?(?x)B(x)
证明,3) (?x)(A(x)→B(x))
(?x)(┐A(x)?B(x))
(?x)┐(A(x)?┐B(x))
┐(?x)(A(x)?┐B(x))
┐((?x)A(x)?(?x)(┐B(x)))
┐(?x)A(x)? ┐(?x)(┐B(x))
(?x)┐A(x)?(?x)B(x)
┐(?x)A(x)?(?x)B(x)
(?x)A(x)→(?x)B(x)
112
2-5谓词演算的等价公式与蕴含式
P70表 2-5.1
多个量词的使用
1) (?x)(?y)P(x,y)?(?y)(?x)P(x,y)
2) (?x)(?y)P(x,y)?(?y)(?x)P(x,y)
3) (?x)(?y)P(x,y)?(?y)(?x)P(x,y)
4) (?y)(?x)P(x,y)?(?x)(?y)P(x,y)
5) (?y)(?x)P(x,y)?(?x)(?y)P(x,y)
6) (?x)(?y)P(x,y)?(?y)(?x)P(x,y)
7) (?x)(?y)P(x,y)?(?y)(?x)P(x,y)
8) (?y)(?x)P(x,y)?(?x)(?y)P(x,y)
113
2-5谓词演算的等价公式与蕴含式证明,5） (?y)(?x)P(x,y)?(?x)(?y)P(x,y)
证法 1：存在一 y，对任意的 x,P(x,y)为 T；即对任意 x，对这个
y而言，使 P(x,y)为真；也就是对任意 x，存在 y，使 P(x,y)真证法 2,?y?xP(x,y)
(P(a1,a1) ∧ P(a2,a1)…… ∧ P(an,a1))
∨(P(a1,a2) ∧ P(a2,a2)…… ∧ P(an,a2))
∨ …
∨(P(a1,an) ∧ P(a2,an)…… ∧ P(an,an))
(P(a1,a1) ∨ P(a1,a2)…… ∨ P(a1,an))
∧ (P(a2,a1) ∨ P(a2,a2)…… ∨ P(a2,an))
∧ …
∧ (P(an,a1) ∨ P(an,a2)…… ∨P (an,an))
x?yP(x,y)
114
2-6前束范式
定义 1：一个谓词公式，如果量词均在全式的开始，它们的作用域延伸到整个公式的末尾，则该公式称为前束范式
例子,(?x)(?y)(?z)(Q(x,y)→R(z))
(?x)(?y)(┐P(x,y)→Q(y))
定理 1：任何一个谓词公式，均和一个前束范式等价证明,1)把否定词深入到命题变元和谓词前面
2)利用 A?(?x)B(x)?(?x)(A?B(x))
A?(?x)B(x)?(?x)(A?B(x))把量词推到前面
3)利用改名规则：
(?x)A(x)?(?x)B(x)
(?u)A(u)?(?x)B(x)
(?u)(?x)(A(u)?B(x))把量词推到前面
115
2-6前束范式
例子：把?x?y((?z)(P(x,y,z)?P(y,z))→(?u)Q(x,y,u))
化为前束范式解：原式
x?y(┐(?z(P(x,z)?P(y,z))?(?u)Q(x,y,u))
x?y(?z(┐P(x,z)?┐P(y,z))?(?u)Q(x,y,u))
x?y?z?u(┐P(x,y)?┐P(y,z)?Q(x,y,u))
把?xP(x,y)xQ(x,z)化为前束范式解：原式
xP(x,y)uQ(u,z)
x?u(P(x,y)?Q(u,z))
116
2-6前束范式
定义 2：若谓词公式是前束范式且作用域为合取范式，则称为 前束合取范式 。前束合取范式具有如下形式,
(□ u1)(□ u2)…,.(□ um)((A11?………?A1l1)?…
(An1?……,,?Anln)),这里□是?或?
定义 3：若谓词公式是前束范式且作用域为析取范式,则称为前束析取范式。前束析取范式形式,
(□ u1)(□ u2)…,.(□ um)((A11?………?A1l1)?…
(An1?……,,?Anln))
定理 2：任一谓词公式均可化为前束合取范式证明：首先利用定理 1的方法把谓词公式化为前束范式，
然后对作用域使用命题逻辑合取范式的化归方法转化为合取范式
117
2-6前束范式
定理 3：任一谓词公式均可化为前束析取范式证明：首先利用定理 1的方法把谓词公式化为前束范式，然后对作用域使用命题逻辑析取范式的化归方法转化为析取范式
例子：将?x?y(?zP(x,y,z) →?uQ(x,u) )uR(x,u)化为前束合取范式。
解：原式
x?y(?z┐P(x,y,z)uQ(x,u))vR(t,v)
x?y?z?u?v((┐P(x,y,z)? Q(x,u))?R(t,v))
x?y?z?u?v
(┐P(x,y,z)? Q(x,u))?R(t,v))
118
2-7谓词演算的推理理论
全称指定规则 简记为 US规则
xP(x)
------
P(c)
注：若对一切 x,P(x)为真,可推得对任意个体 c，都有
P(c)为真。
需要避免引入客体变元之间相互作用
例子,?x(P(x,z)yQ(x,y))
P(c,z)yQ(c,y)
P(y,z)yQ(y,y)
x(P(x,c)? Q(x,c))
P(c,c)? Q(c,c)
119
2-7谓词演算的推理理论
存在指定规则 简记为 ES规则
xP(x)
------
P(c)
注,若至少存在一个 x使得 P(x)为真，以 c标记取值于使得 P(x)为真的 x的集合的客体变元，即有使 P(c)。
通常,c可以看作是取值于个体域的特定子集的客体变元。
对于由全称量词衍生的 c，其取值的集合是全部个体域；对于由存在量词衍生的 c，其取值的集合一般是个体域的真子集需要避免引入客体变元之间相的互作用
例子,1）?xP(x)yQ(y)
P(a)?Q(b)
P(a)?Q(a)
2）?x (A(x,z)? B(c))
A(c,z)? B(c)
120
2-7谓词演算的推理理论
存在推广规则 简记为 EG规则
P(c)
------
x P(x)
注,c是某个确定的个体,若 P(c)为真,则?x P(x)
为真需要避免引入客体变元之间相的互作用
例子,?x P(x,c)z Q(c,z)
x (?x P(x,x)zQ(x,z))
y (?x P(x,y)zQ(y,z))
121
2-7谓词演算的推理理论
F全称推广规则 简记为 UG规则
P(x)
------
x P(x)
注：若对个体域中每一个客体 c,P(c)为真，则?x P(x)为真。
应用本规则时，必须能保证前提 P(x)对论域中的每个可能的 x
都是真的。具体在谓词演算的推理中，若一个谓词公式中的 x
是使用 US而自由的，后继推导中才能使用 UG规则
例子：下列推理过程 (P(x,y):y=x+1)是否正确？
1)?x?y P(x,y) P
2)?y P(c,y) US(1)
3) P(c,d) ES(2)
4)?x P(x,d) UG(3)
5)?y?x P(x,y) EG(4)
122
2-7谓词演算的推理理论
例子,下列推导是否有错误？
1.(1)?y(P(y)?Q(y)) P
(2)P(a)?Q(b) ES（ 1）
2.(1)?xP(x)→Q(x) P
(2) P(x)→Q(x) US （ 1）
3.(1)?xR(x)x(Q(x)?R(x)) P
(2) R(a)x(Q(x)?R(x)) ES（ 1）
例子,会议的每一个成员都是青年专家，一些成员来自人文学科。所以成员有一些是来自人文学科的青年。试构造一个证明来证明这一结论
123
2-7谓词演算的推理理论解：设 C(x)表示 ‘ x是会议成员 ’ 。
S(x)表示 ‘ x是专家 ’ 。
W(x)表示 ‘ x是青年 ’ 。
O(x)表示 ‘ x来自人文学科 ’ 。？
证：则结论形式化为：
x(C(x)→(W(x)?S(x)))x(C(x)?O(x))x(O(x)?W(x))
1,?x (C(x) → (W(x)? S(x))) P
2,?x( C(x)? O(x)) P
3 C(y)? O(y) ES（ 2）
4,C(y) → (W(y)? S(y)) US（ 1）,
5,C(y) T（ 4） I
124
2-7谓词演算的推理理论
6,W(y)? S(y) T（ 3）（ 5） I
7,O(y) T（ 4） I
8,W(y) T（ 6） I
9,O(y)? W(y) T（ 7）（ 8） E
10,?x( O(x)? W(x)) T（ 9） EG
例子：证明,?x(P(x) →Q(x))x(R(x) →┐Q(x))
x(R(x) →┐P(x))
证,1,?x(P(x) →Q(x)) P
2,?x(R(x) →┐Q(x)) P
3,P(x) →Q(x) US （ 1）
4,R(x) →┐Q(x) US （ 2）
5,Q(x) →┐R(x) T （ 4） E
6,P(x) →┐R(x) T(3)(5)I
7,?x(R(x) →┐P(x)) UG(6)
125
2-7谓词演算的推理理论
证明,?x(P(x)?Q(x))xP(x)xQ(x)
证明：反证法
1.?x(P(x)?Q(x)) P
2.┐(?xP(x)x Q(x)) P
3.?x┐P(x)x ┐Q(x) T（ 2） E
4.?x┐P(x) T （ 3） I
5.?x┐Q(x) T（ 4） I
6.┐P(y) ES(4)
7.┐Q(y) US （ 5）
8.┐(P(y)? Q(y)) T（ 6）（ 7） I
9.P(y)? Q(y) US（ 1）
10┐(P(y)? Q(y))? (P(y)? Q(y)) T（ 8）（ 9）矛盾其他证法：利用 CP规则
126
2-8形式化谓词演算系统 K
上节中的谓词演算系统 并非 完全形式化的，推理过程中使用推理规则时需要仔细考察谓词公式的具体含义。
这里谈论一个固定的，但是没有指明具体解释的形式化 一阶 谓词演算系统 K。 K的符号可以有许多不同的解释，但是我们关心的纯粹是语言的形式方面，着重讨论谓词公式的 逻辑关系 。在此基础上，讨论系统的 元性质,以及更为深入的 语义问题
形式化一阶谓词演算系统 K
符号字母表：
x1,x2,x3,… 客体变元
a1,a2,a3,… 客体常元
A11,A12,…,A21,A22,… 谓词字母，其中 Aij表示第 j个 i元谓词
f11,f12,…,f21,f22,… 函数字母，其中 fij表示第 j个 i元函数
127
2-8形式化一阶谓词演算系统
（，），,辅助技术性符号
┐,→ 逻辑联结词
量词
注 1：出于直观和表述方便的考虑，引入了函数符号（即函元）。客体常元、客体变元以及函数符号作用于客体常元和变元的结果可以作为谓词的项
K的项的递归定义：
1）客体变元和客体常元是项
2）若 fij是函数符号,x1,…,xi 是项，则
fij（ x1,…,xi)是项
3）所有的项通过有限次使用 1）和 2）生成
128
2-8形式化一阶谓词演算系统
注 2：函数是一种特殊的关系，而（多元）谓词也可以看作某种关系，这样函数实际上是一种特殊谓词，两者实际上可以互相表示。
问题：允许函数作为谓词的项,会不会破坏形式谓词演算系统的一阶性？
例子：任意比 x大 5的数大于比 x大 1的数
(?x)G(g5(x),g1(x))
(?x)(?y?z(G5（ y,x）?G1(z,x))→G(y,z))
值域的区别例子,P（ x):x不是真实的
P（ Q（ x） )
129
2-8形式化 一阶 谓词演算系统
注 3：语言中只有两个联结词,为什么？
注 4：语言中只有一个全称量词,为什么？
原子公式：形如 A(t1,t2,…,tn)的公式称为 K的 原子公式,
其中 t1,t2,…,tn是 K的项
合式公式：
1） K的每一原子公式是 K的合式公式
2） 若 A和 B是合式公式，则（ ┐ A），（ A→B ）和（?xi） A
是合式公式，这里 xi是任意客体变元
3） 只有经过有限次应用步骤 1）－ 2）所获得的公式才是合式公式
130
2-8形式化 一阶 谓词演算系统
下面将给出 K的公理。但是在此之前，需要澄清一个问题：
K的公理在何种意义上是真的？为了讨论谓词逻辑的真性问题，需要引入 解释 的概念。
定义 1,K的 解释 I是指一个对象域集合 DI、特异常元的集合 SI,DI上函数的集合 FI和关系的集合 RI。
注,K中的变元 x1,x2,… 的具体取值在 DI中产生； K中的客体常元在 SI上中产生； K中的函数和谓词分别由 FI和
RI产生
K的解释类似于 L的真值指派,K的谓词公式的真性需要基于解释加以讨论。
131
2-8形式化 一阶 谓词演算系统
例子,?x1(┐?x2)┐A21(x1,x2)
当 DI是正整数集合,A21(x1,x2)被解释为 x1*x2＝ 0时是假的；
当 DI是整数集合,A21(x1,x2)被解释为 x1*x2＝ 0时真
定义 2,K的解释 I的一个 赋值 是从 K的项到 DI的函数 v，满足：
对于 K的每个个体常元,v(ai)=ai*
对于 K的任意函数 fij：
v(fij(t1,…,ti))=f*ij(v(t1),… v(ti))
这里,ai* 和 f*ij分别是 ai和 fij在 I中的解释注：上述定义保证了赋值是相容的解释 I的赋值 v将由 v(x1),v(x2),… 完全确定
例子,A11(x1)
解释 I的 DI是整数集合,A11(x1)被解释为 a1大于 0。对于这个确定的解释 I，当赋予 x1不同的值时，上式有不同真值。
132
2-8形式化 一阶 谓词演算系统
注：赋值起到了进一步地真值指派作用，解释和赋值共同确定了
K中谓词公式的真值
定义 3：两个赋值 u,v是 i-等价的，如果对于任意 j不等于 i，
u(xj)=v(xj)
定义 4：设 A,B,C是 K的谓词公式,I是 K的一个解释。 I中赋值 v
满足 A，如果可由如下四种情形归纳证明 v满足 A：
1） v满足 A=Aij(t1,…,ti),当且仅当 A*ij(v(t1),… v(ti))真
2） v满足 A=┐B,当且仅当 v不满足 B
3） v满足 A=B→C,当且仅当 v满足 ┐ B或 v满足 C
4） v满足 A=(?xi)B，当且仅当任何 i-等价于 v的赋值均满足 B
注：上述定义是自洽的。对于任意 v和 A,v或者满足 A或者满足
┐ A，不可能同时满足或同时不满足。
133
2-8形式化 一阶 谓词演算系统
定义 4,K的谓词公式 A在解释 I下是 真 的，如果 I中每一赋值均满足 A； K的谓词公式 A在解释 I下是 假 的，如果 I中每一赋值均不满足 A
问题：对于特定解释 I：
是否可能存在即不真又不假的谓词公式？
是否可能存在即真又假的谓词公式？
命题 1：在 K的解释 I下，若 A→B 和 A真，则 B也真
命题 2：在 K的解释 I下,A真当且仅当 (?xi)A真,xi是任意变元
命题 3：在 K的解释 I下,A真当且仅当 (?x1)… (?xk)A真，
x1… xk是任意变元
注：命题 3意味着对 A中的自由变元增加全称量词，并不改变其真性（依照这里所定义的真）
134
2-8形式化 一阶 谓词演算系统
定义 5,K的谓词公式 A是重言式，如果 A是 L的重言式在 K中的一个代换实例
例子,A→(B→A) 代换为 (?xi)A→( (?xj)B→ (?xi)A)
命题 4,K的重言式在 K的任意解释下都是真的
定义 6,K的谓词公式 A称为封闭的，如果其中无自由变元
命题 5：若 A是 K的封闭谓词公式,I是 K的解释，则在 I下，或者 A
为真，或者 A为假
注：对于多数重要的系统，特别是数学系统，谓词公式 A通常中并不会出现自由变元
定义 7,K的谓词公式 A是 逻辑有效的,如果 A在 K的每一种解释下都是真的； A是 矛盾的,如果 A在 K的每一种解释下都是假的。
回顾：真、假、非真非假,重言,逻辑有效,矛盾解释、赋值、指派、封闭公式
135
2-8形式化 一阶 谓词演算系统
公理：设 A,B和 C是任意谓词公式，则以下为 K的公理
K1:（ A→ （ B→A ））
K2:（ A→ （ B→C ）） → （（ A→B ） → （ A→C ））
K3:（ ┐ A→┐B ） → （ B→A ）
K4,((?xi)A→A),xi 不在 A中自由出现
K4例子,(?xi)(?xi)A(xi)是否可以应用 K4？
(?xi)A(xj)是否可以应用 K4？
(?xi)A(f(xj))是否可以应用 K4？
K5,((?xi)A(xi)→A(t)),t 是 K的项，它对 A(xi)
中的 xi是 自由的
136
2-8形式化 一阶 谓词演算系统定义：设 A是 K的任意谓词公式，项 t对 A中的 xi是 自由的,如果 xi自由出现，且不在 A的任何一个（?xj）的辖域中，这里 xj
是在 t中出现的任意客体变元注：粗略地说,项 t对 A中的 xi是自由的，意味着 t可以对 A中的 xi的每一自由出现做代入，而不会引起与 A中量词的相互作用对任意谓词公式 A和任意变元 xi，无论 xi在 A中是否自由出现,xi对 A中的 xi是自由的
K5例子,xj对于 (?xi)A(xi,xj)中的 xi是否可用 K5？
xj对于 (?xi)(?xj)A(xi,xj)中的 xi是否可用 K5？
f(xj)对于 (?xi)A(xi,xj,xk)中的 xi是否可用 K5？
xi对于 (?xi)A(xi)中的 xi是否可用 K5？
137
2-8形式化 一阶 谓词演算系统
f(x1,x4),f(x2,x3),f(x1,x3)和 x4对于下式中的哪个变元是自由的，哪个变元不是自由的？
(?x1)(?x2)A21(x1,x2)→ (?x3)A22(x3,x1)
K6,(?xi)(A→B)→ （ A→(?xi)B），若 A不包含变元 xi的自由出现
K的演绎规则,1）分离规则，即从 A和（ A→B ），可以获得 B
2）全称概括规则（ UG）：由 A获得（?xi） A
注,K的公理模式和演绎规则包括了 L的公理模式和演绎规则，
增加的公理和规则对于涉及量词性质的演绎是必要的公理 K5以最一般的形式叙述。在应用中，我们将经常碰到
(?xi)A→A 这样的例子，这里 xi可以是也可以不是 A中自由出现的变元。若 xi在 A中自由出现，可把 A记作 A（ xi），因为 xi对
A(xi)中的 xi总是自由的，于是 K5成为 (?xi)A→A(xi) 。若 xi不在 A中自由出现，则 K4给出了变换的形式,(?xi)A→A
138
2-8形式化 一阶 谓词演算系统
定义 8,K中的一个 证明 是谓词公式的序列 A1,A2,…,An，
使得对每一个 Ai（ 1<=i<=n)，或者 Ai是 K的公理，或者
Ai是由序列中在前面的谓词公式用分离规则或全称概括规则推出的。 K的 定理 是某个证明序列中的最后一项。
命题 6,K1－ K6均是逻辑有效的
命题 7：若 K的谓词公式 A是重言式，则 A是 K的定理
注：逆命题不成立
在 K中，逻辑有效的概念相当于 L中真的概念。我们关注于系统 K基于逻辑有效性的可靠性、一致性和完备性
139
2-8形式化 一阶 谓词演算系统
命题 8（ K的可靠性定理 ）：若 K的谓词公式 A是 K的定理，则 A是逻辑有效的证明：归纳法，施归纳于定理 A的证明序列长度 n
奠基步：当 n＝ 1时,A是 K的公理，命题成立归纳步：假设 A有长度为 n(n>1)的证明，而 K的所有长度小于 n步的定理都是逻辑有效的。。。
命题 9（ K的一致性定理 ）,K是一致的，即不存在 K的谓词公式 A，
使得 A和 ┐ A都是 K的定理
命题 10（ K的完备性定理 ）：若 K的谓词公式 A是逻辑有效的，则
A是 K的定理
140
2-9模型和模态逻辑
系统 K要求推理是逻辑有效的，即在任意解释下是均保真的。此要求使 K具备充分的可靠性。但系统的可靠性和能力之间常存在内在的冲突（科学理论、软件系统等）。这促使人们重新审视逻辑有效性，尝试放宽对可靠性的限制以获得更强有力的系统。
逻辑有效性被定义为对于任何解释均为真，但通常情况下，并非每个解释都令我们感兴趣，甚至有些解释是不可形式定义的
（可形式定义的解释是可数的，而所有可能的解释是不可数的）
例子：如果我们所在的世界中，时间是单向流逝的，那么是否必要让我们的推理方法也适用于时间线封闭的世界？
如果确知日常世界可以由欧氏几何所精确地刻画，还是否必要让日常推理方法也适用于黎曼几何或罗巴切夫斯基几何世界？
可否扩展 K的公理集，在保证其可靠性的同时，使其功能更强？例如，将欧氏几何的公理和公设加入系统 K。 这就是形式系统的基本思想。
141
2-9模型和模态逻辑
定义 1：设 S是 K的谓词公式集合,S的一个解释（世界）称为 S的模型,如果 S中每个谓词公式在此解释下是真的
定义 2：若 S是一阶系统,S的一个模型是一个解释，在这个解释中,S的每个定理都是真的
定理 1：设 S是一阶系统,I是使 S的每个公理均为真且推理规则保真的解释，则 I是 S的一个模型
注：定义 1给出了公式集的模型的定义；定义 2给出了一阶系统的模型的定义。由模型的定义可知，任何一个解释都是一阶谓词系统 K的模型由定理 1，一个一阶系统的解释，只需使其所有公理真且推理规则保真，即可成为其模型
思考题：可否建构 现实有效系统,即 以 现实解释和所有可形式定义解释为模型的系统？如果可以，它与 K的区别？
142
2-9模型和模态逻辑
单世界和多世界我们的世界是所有可能世界中的最完美者－－－莱布尼茨量子力学的多世界（ multiverse）解释－－－ Everett
模态逻辑：关于可能世界（即解释）的逻辑
模态词
,读作可能,? p指命题 p在某个（或某些）解释中为真，
即在某个（或某些）可能世界中为真
：读作必然,?p指命题 p在所用可能的解释中均为真，即在所有可能世界中为真。
模态逻辑对于蕴含悖论的解决方案例子,A→(B→A) 与 S→P( S:如果太阳西升,P：有最大的质数 )
（ A→(B→A) ）与?（ S→P ）
143
2-9模型和模态逻辑
模态（命题）逻辑的重言式集合 S是古典命题逻辑重言式集合的超集，超集满足以下条件
1)?(p→ q)→ (?p→?q)? S
2) S在分离规则下封闭：若 A? S,A→ B? S,则 B? S
3) S在代入规则下封闭：若 A? S，则 A S，这里 A?是 A的代入特例
4) S在弱必然化规则下封闭：若 A是命题逻辑重言式，则
A? S
5) S在必然化规则下封闭：若 A? S，则?A? S
注：若一个模态逻辑系统满足 1)-4)，则称它为古典模态逻辑。
若一个模态系统满足 1)-3)和 5)，则称它为正规模态逻辑。
是否有必然化规则（记为 N），是正规系统区别于非正规系统的的主要标志。 N是说：如果一个公式是在某系统内是可证的，则它是逻辑必然的。
144
2-9模型和模态逻辑
命题模态逻辑系统 S5以代入规则（记为 US）和分离规则（记为
MP）作为推理规则
S5系统公理
M1(A2),? p?┐?┐p
M2(T),?p→p
M3(K),?(p→q)→(?p→?q)
M4(N),若 A可证，则有?A
M5(4),?p→p
M6(E),? p→ p
M7(A1),所有真值函项重言式
145
2-9模型和模态逻辑
例子：安瑟伦的上帝存在性本体论证明的 Descartes版本
,God could not be so complete if he weren?t,So he is.”
Descartes
扩展表述：
定义上帝为具有所有积极属性者，则上帝必存在证明：（反证法）假设上帝不存在，则我们可以设想一个 God*，
God*保有上帝的所有其他积极属性，除了需要额外设想 God*是存在的。 由于存在性是比虚无性积极的属性,所以 God*比上帝具有更多的积极属性，与前面对上帝的定义矛盾。故上帝存在。
Kant的批评：存在不应作为一个谓词
146
2-9模型和模态逻辑
例子：安瑟伦的上帝存在性本体论证明的 Hartshorne版本
,I believe you (i.e.,God) are that thing than which
nothing greater can be thought”
“But when the fool (i.e.,antitheist) hears me use the
phrase?something than which nothing greater can be
thought?,he understand what he hears…”
“So fool has to agree that the concept of something than
which nothing greater can be thought exists in his
understanding.” ---安瑟伦根据上面的论证安瑟伦假设可以理解 (understanding)的东西是可能存在的，即对应于可能模态。这样，安瑟伦给出了他的第一个公理 H1,? g，这里 g代表上帝存在这一命题,? g即上帝是可能存在的
147
2-9模型和模态逻辑
进一步，安瑟伦论证,something than which nothing
greater can be thought so truly exists that it is not
possible to think of it as not existing.”，由此获得公理 H2,g→?g。安瑟伦的理由是，如果上帝的存在仅仅是偶然的，我们就可以想像一个必然存在的上帝，在安瑟伦看来，后者显然比前者更伟大。所以如果上帝存在，则上帝的存在是必然的（公理 H2）
下面有公理 H1和 H2导出安瑟伦的结论：
由 M6，有 H3,? ┐ g→ ┐g
由排中律，有,(?g?┐?g)，由 M1，这等价于 H4：
(?g ┐g )
由 H3和 H4，可获得 H5,?g ┐g
由 H2，获得 ┐?g→┐g,即获得 H6,? ┐g→┐g
在 H6上应用 M4，获得 H7,?(? ┐g→┐g)
148
2-9模型和模态逻辑在 H7上应用 M3，获得 H8:( ┐g)→(?┐g)
由 H5和 H8，获得 H9,(?g)?(?┐g)
改写 H1，获得 H10,┐?┐ g
由 H9和 H10，获得?g，即上帝必然存在,Q.E.D
注：由必然模态词的含义,?g意味着上帝存在这一命题在所有可能的解释，也即所有可能的世界中都为真。
这样，在我们所身处的这个特殊的世界中，上帝必须也是存在的。
你的意见？
可能的反驳,H1？
,conceivable existence and possible existence
are not the same” －－－ Christopher Small
149
2-9模型和模态逻辑
,Logic is not the end of wisdom,it is the
beginning…”
anonymous
数理逻辑
侯越先,yxhou@tju.edu.cn,16楼 -316室
一般性参考：
,离散数学,,左孝凌等，上海科学技术出版社
,数学家的逻辑,,哈密尔顿，商务印书馆
,元数学导论,,S,C．克林，科学出版社
课程辅助材料：
ftp://202.113.9.183/教师教学目录 /
2
数理逻辑的研究目的
逻辑（ Logics）研究的是 有效的 推理方法，数理逻辑
（ Mathematical Logics）就是用数学化（符号化）
的手段，研究 有效的 推理方法
什么是 有效的 推理方法?
a 有效的推理方法应具备 保真性,即如果推理前提真，
则推理结论真
b 有效的推理方法的保真性应是 普遍的,即不同的人，
在不同的语义环境下使用同样的推理方法，获得真假性相同的结论
例子：三段论他是医生，所以他是大夫
3
数理逻辑的研究目的
问题：是否所有真命题都可由满足条件 a和 b的推理方法获得？
,真,的分类：形式真、语义真和直觉真
下面中各个蓝色的结论的真假是由什么来决定的？推理形式、
语义和直觉？
1 他是医生,所以他是大夫
2 如果下雨，野餐将取消；
现在确实下雨了；
野餐将取消
3 如果 A优于 B；
且 B优于 C；
则 A优于 C
4 任何一个一班的同学都不能判定本语句是真的
4
数理逻辑的研究目的
注,d与说谎者悖论的区别（说谎者悖论,本语句是在说谎）
d与哥德尔不完备性定理之间的关系
数理逻辑的研究目的：研究 形式 有效的推理，
用 形式 手段地刻画人们对 形式 真的朴素理解。
5
逻辑学的历史
亚里士多德（ Aristotle,B.C,384-B.C,322）：三段论
莱布尼茨（ Gottfried Wilhelm von Leibniz,1646-
1716）：将推理还原为计算
布尔（ George Boole 1815-1864）：形式符号和等式，布尔代数
弗雷格（ Gottlob Frege,1848-1925）：一阶逻辑
罗素（ Bertrand Russell,1872-1970）：逻辑主义
希尔伯特（ David Hilbert,1862-1943）：形式主义
哥德尔（ Kurt Godel,1906-1978）：逻辑和形式方法不充分性
6
数理逻辑的主要内容
命题逻辑、谓词逻辑,非古典逻辑
模型论、证明论、递归论、公理化集合论模型论：用集合论的方法表示数学概念证明论：用形式化的方法研究数学证明的过程递归论：
7
第一章 命题逻辑
1-1 命题及其表示法
定义 1,命题 是一个具有确定真值的陈述语句
注,真值 表示真假的性质，其可能的取值只有,真,和
,假,,通常有,T”表示真,,F”表示假。
例子,5是一个整数
3是偶数
x+y=4
你吃过饭了吗?
我正在说谎任何一个一班的同学都不能断定本语句是真的
8
1-1 命题及其表示法
定义 2,原子命题 是不能再分解为更简单命题的命题
例子：苏格拉底是哲学家德国和法国都是欧洲国家
注,1 原子命题与维特根斯坦的原子事实
2 原子命题的界定 不宜 绝对化
3 原子命题常用大写字母 A,B,…,P，
Q,… 或带下标的大写字母来表示
9
1-1 命题及其表示法
定义 3：由原子命题、联结词或标点符号的复合构成的命题称 复合命题
例子,昨天下雨，今天也在下雨
定义 4：表示命题的符号称为 命题标识符
定义 5：一个命题标识符如果表示确定的命题，
称为 命题常元 ；如果命题标识符可以表示某类命题中的任何一个，称为 命题变元
10
1-2 命题的联结词
作用：规范日常语言中联结词（如,与,,,或,
等）在命题逻辑中的意义和用法，这里联结词可以看作是作用于命题之上的 运算符
定义 1：设 P为一命题,P的 否定 是一个新的命题，
记为 ┐ P。若 P为 T,┐ P为 F；若 ┐ P为 T,P为 F
例子,P：上海不是一个大城市
┐ P：？
11
1-2 命题的联结词
定义 2：两个命题 P和 Q的 合取 是一个复合命题，
记作 P∧Q 。当且仅当 P,Q同时为 T时,P∧Q 为 T，
其他情况下 P∧Q 均为 F
例子,P：地球是球形的
Q,牛顿是物理学家
P∧Q,地球是球形的并且牛顿是物理学家
P：拿破仑是科西嘉人
Q,拿破仑不是科西嘉人 （ ┐ P）
P∧Q,拿破仑是科西嘉人并且拿破仑不是科西嘉人
12
1-2 命题的联结词
注,1 ∧ 是汉语中,与,,,和,,,并,
的翻译，但 不能绝对化,例如,老张与小李是师徒,
2 合取在一起的两个命题不一定有实质的联系，也不一定是一致的，甚至可以将互为否定的命题合取在一起（该注释对其他逻辑联结词也适用）
定义 3：两个命题 P和 Q的 析取 是一个复合命题，记作 P?Q。当且仅当 P,Q同时为 F时，
P?Q的真值为 F；否则 P?Q的真值为 T
13
1-2 命题的联结词
例子,P：机器有故障
Q：开关有故障
P∨Q,机器有故障或开关有故障
注,∨ 是汉语中,或,的翻译，但不能绝对化。特别应 注意区分,可兼或,和,排斥或,。
例子,P：他是 78年出生的
Q：他是 79年出生的他是 78年出生的或 79年出生的表示为 P∨Q？
14
1-2 命题的联结词
定义 4：给定两个命题 P和 Q，其 条件 是一个复合命题，记作 P→Q,读作,如果 P，那么 Q” 或,P
蕴含 Q”。当且仅当 P的真值为 T,Q的真值为 F时，
P→Q 的真值为 F;否则 P→Q 的真值为 T。称 P为前项，
Q为后项
例子,P,月亮下山
Q,3+3=6
P→Q,如果月亮下山,则 3+3=6
15
1-2 命题的联结词
注,1 虽然上例的 P,Q之间并无实际联系，但只要 P,Q可分别确定真值，即可用,→,联结
2 Q→P 称为 P→Q 的 逆命题
┐ P→┐Q 称为 P→Q 的 反命题
┐ Q→┐P 称为 P→Q 的 逆反命题
3 前项 P为 F时，无论后项 Q取何真值,P→Q 的真值均为 T，这是所谓的,善意推定,
16
1-2 命题的联结词
补充说明,上面所定义,→,是所谓的,实质蕴含,。对于实质蕴含的合理性，存在着一定的争议。例如，根据实质蕴含的定义，下面的复合命题的真值必定为 T：
a (A→B)∨(B →A)
b F→A
a意味着任何两个命题之间有蕴含关系
b意味着假命题可以推出任何命题这并不符合人们关于蕴含的常识和直觉
17
1-2 命题的联结词
问题：形式逻辑系统是否可以精确地反映和把握人们关于蕴含和推理的全部直觉认识？
为了解决实质蕴涵的局限，人们提出了其他的蕴涵定义，如：严格蕴含、相干蕴含、直觉主义蕴含等。
总的来说，上述对于实质蕴含的发展可以在一定程度上解决实质蕴含的问题，但经常会带来新的问题甚至悖论。实质蕴含限制最少，包容性最强，形式最为简洁，是应用得最广泛的蕴含形式
18
1-2 命题的联结词
定义 5：给定两个命题 P和 Q，复合命题 P?Q称作双条件 命题，读作,P当且仅当 Q”，当 P和 Q的真值相同时,P?Q的真值为 T，否则 P?Q的真值为
F
注：双条件?的其他表示法
例子：
1 P,1+1=3
Q,雪是白的
P?Q,1+1=3当且仅当雪是白的
2 当且仅当明天不下雪且不下雨，我才去学校
3 只有他出差，我才会同意他不参加学习
19
1-2 命题的联结词
思考题：实质蕴含企图反映命题之间的必然联系，却并未反映命题之间的内容联系。尝试给出你自己的蕴含规则（可以利用和扩展前面介绍过的思路），以消除实质蕴含的反直觉怪论。
20
1-3 命题公式与翻译
定义 1,命题演算的 合式公式 （ wff），简称为合式公式 或 命题公式,规定为：
1) 单个命题变元本身是一个合式公式
2) 如果 A是合式公式，那么 ┐ A是合式公式
3) 如果 A和 B是合式公式，那么（ A∧B ）、
（ A∨B ）,(A→B) 和（ A?B)都是合式公式
4）当且仅当有限次地应用 1）,2）和 3）所得到的包含命题变元，联结词和括号的符号串是合式公式
21
1-3 命题公式与翻译
例子：指出 (P→(P?Q))中的哪些部分是命题公式
(wff)，并具体说明它是如何生成的解,① P
由 1)
② Q
由 1)
③ （ P?Q）是 wff
由 3)
④ (P→(P?Q))
由 3)
22
1-3 命题公式与翻译
例子：设计一个自然数集合的递归定义（皮亚诺公理）
约定：运算次序优先级,┐,?,?,→,?
相同的运算符按从左至右次序计算，否则要加上括号，最外层圆括号可省去
例子：如果命题 A等价命题 B，那么命题 C等价命题 D
23
1-4真值表与等价公式
定义 1：在 wff中，根据对分量指派真值的各种可能组合，求解 wff的对应真值，汇列成表，称为真值表
例子：构造 ┐ P→ （ P→Q ）的真值表解：
P Q ┐P P→Q ┐ P→ （ P→Q ）
F F T T T
F T T T T
T F F F T
T T F T T
24
1-4真值表与等价公式
例子：给出 ┐ (P?Q)?(┐P?┐Q) 的真值表解：
P Q P? Q ┐(P?Q) ┐P?┐Q ┐(P?Q)? (┐P?┐Q)
F F F T T T
F T F T T T
T F F T T T
T T T F F T
25
1-4真值表与等价公式
定义 2：一个命题公式如果对于其 分量 指派真值的各种可能组合，其真值恒为真（假），称该命题公式是 永真（假）式,记为 T（ F）
例子,P?┐P
P?┐P
P→Q
定义 3：给定两个命题公式,A(P1,P2...Pn),B(P1，
P2...Pn)若对于 P1,…,Pn任一组真值指派,A,B真值相同，称 A和 B是 等价的或逻辑相等,记为 A?B
问题：上面的定义是否有必要扩展到包含无限多分量的命题公式？
26
1-4真值表与等价公式
例子：求证 P?Q?(P→Q)?(Q→P)
解：
P Q P?Q Q→P P→Q (P→Q)?(Q→P)
F F T T T T
F T F F T F
T F F T F F
T T T T T T
27
1-4真值表与等价公式
基本的命题逻辑等价关系幂等律,P?P?P,P?P?P
结合律：（ P?Q）?R?P?（ Q?R）
（ P?Q）?R?P?（ Q?R）
交换律,P?Q? Q?P,P?Q?Q?P
分配律,P?(Q?R)?(P?Q)?(P?R）,
P?(Q?R)?(P?Q)?(P?R）
28
1-4真值表与等价公式
基本命题逻辑等价关系（续）
吸收律,P?(P?Q)?P,P?(P?Q)?P
德摩根律,┐ （ P?Q）?┐ P?┐Q
┐ （ P?Q）?┐ P?┐Q
同一律,P?F?P,P?T?P
零律,P?T?T,P?F?F
否定律,P? ┐ P?T,P? ┐ P?F
29
1-4真值表与等价公式
定义 4：如果 X是命题公式 A的一部分，且 X也是命题公式，则称 X是 A的 子公式
定理 1：设 X是命题公式 A的子公式，若 X?Y，则若将 A中的 X的 每一次出现 用 Y来置换，所得公式
B与 A等价，即 A?B
证明,因为对变元的任一组指派,X与 Y真值相同，故以 Y取代 X后，公式 B与公式 A相对于变元的任一指派的真值也必相同，所以 A?B
定义：称满足定理 1的置换为 等价置换
30
1-4真值表与等价公式
例子：证明下列命题公式（ 可以利用 基本的命题逻辑等价关系）
Q→ （ P?（ P?Q））?Q→P
（ P?Q)?（ P?┐Q)?P
P→Q?┐ P?Q
（ P→Q ） → （ Q?R）?P?Q?R
P?┐Q?Q?P?Q
31
1-5重言式与蕴含式
重言式即永真式；矛盾式即永假式
定理 1：任何两个重言式的合取或析取，仍然是重言式证明：设 A,B为两个重言式，则 A?B和 A?B的真值分别等于 T?T和 T?T
定理 2：对一个重言式的同一 分量 都用任何一个命题公式置换，所得命题公式仍为一个重言式证明：由于重言式的真值与分量的真值指派无关，故对同一分量以任何一个命题公式置换后，重言式的真值不变
问题：上述定理对于子公式替换的情形是否仍成立？
32
1-5重言式与蕴含式对一个重言式的同一分量用不同的命题公式置换，
所得命题公式是否仍为一个重言式？
对一个重言式的同一分量用 永假式 置换，所得命题公式是否仍为一个重言式？
定理 3：设 A,B是两个命题公式,A?B当且仅当
A?B是一个重言式证明：若 A?B，则对于 A,B所包含的分量的任意指派,A,B均取相同的真值，即 A?B是一个重言式；若 A?B是一个重言式，即对于分量的任意指派,A,B均取相同的真值，即 A?B
33
1-5重言式与蕴含式
例子,P→Q?┐ Q→┐P
永真式 永假式命题公式
34
1-5重言式与蕴含式
定义 1：当且仅当 P→Q 是一个重言式时，称
,P重言蕴含 Q”，在不会引起歧义的情况下，
简称为,蕴含,,记作 P?Q
例子,求证 ┐ Q?（ P→Q ）?┐ P
证法 1：
证法 2：
常用的蕴含关系式,p21，表 1-5.2
35
1-5重言式与蕴含式
定理 4：设 P,Q为任意两个命题公式,P?Q的充分必要条件是 P?Q且 Q?P
证明：若 P?Q，则 P?Q为重言式，即 P→Q 和 Q→P
是重言式；若有 P?Q且 Q?P，则 P→Q 和 Q→P 是重言式，即 P?Q为重言式
36
1-5重言式与蕴含式
蕴含的性质，设 A,B,C和 D为命题公式，则
1若 A是重言式，且有 A?B，则 B是重言式
2若有 A?B,B?C，则有 A?C，即蕴含关系是传递的
3若有 A?B,A?C，则有 A?（ B?C)
4如有 A?C,B?C，则有 A?B?C
37
1-6其他联结词
定义 1：设 P和 Q是两个命题公式，复合命题 P-?Q
称作 P和 Q的 不可兼析取 。当且仅当 P和 Q的真值不相同时,P-?Q的真值为 T，否则为 F
-?的性质：
P-?Q?Q-?P
（ P-?Q） -?R?P-?(Q-?R)
P?（ Q-?R）?（ P-?Q）?（ P-?R）
P-?Q?（ P?┐Q ）?（ ┐ P?Q）
P-?Q?┐ （ P?Q）
P-?┐P?F,P-?F?P,P-?T?┐P
38
1-6其他联结词
定理 1：设 P,Q,R是命题公式，如果 P-?Q?R，
则 P-?R?Q,Q-?R?P，且 P-?Q-?R为一矛盾式证明：若 P-?Q?R，则 P-?R?P-?P-?Q?F-?Q?Q
Q-?R?Q-?Q-?P?P
P-?Q-?R?R-?R?F
定义 2：设 P和 Q是两个命题公式，复合命题 Pc →
Q称为 P和 Q的 条件否定,Pc → Q的真值为 T，当且仅当 P的真值为 T,F的真值为 F
定义 3：设 P和 Q是两个命题公式，复合命题 P?Q
称为 P和 Q的 与非,当且仅当 P和 Q的真值都是 T时，
P?Q的真值为 F，否则其真值为 T
39
1-6其他联结词
定义 4：设 P和 Q是两个命题公式，复合命题 P? Q
称为 P和 Q的 或非,当且仅当 P和 Q的真值都是 F时，
P?Q的真值为 T，否则其真值为 F
联结词的种类：
一元联结词变量 运算
P f1 f2 f3 f4
0 0 0 1 1
1 0 1 0 1
永假 恒等 否定 永真
40
1-6其他联结词
二元联结词命题变元 运算
P Q f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 f16
1 1 1 0 1 1 0 0 1 0 1 0 1 0 1 0 1 0
1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 1 1 0
0 1 1 0 0 1 1 0 0 1 1 0 1 0 0 1 0 1
0 0 1 0 0 0 1 1 0 1 0 1 1 0 1 0 1 0
f1?T,f2?F,f3恒等 P,f4恒等 Q,f5?┐P,f6?┐Q,f7?P?Q
f8?┐(P?Q) f9?P?Q,f10?┐ （ P?Q）,f11?P→Q,f12?┐ (P→ Q)，
f13?P?Q,f14? ┐(P?Q),f15?Q→P,f16?┐ (Q→P)
除了 T,F和命题变元本身，需要再定义 9种联结词（ 5-6,7,8?,9,10?,11-15,
12-16c→,13,14 -?)
41
1-6其他联结词
问题：含 n个分量且互不等价的命题公式共有多少个？
定义 3：可以表示所有可能的真值函数（即联结词）的联结词集合，称为 联结词的充足集
定理 2：｛ ┐,?｝｛ ┐,? ｝，｛ ┐,→ ｝是联结词的充足集
定理 3：｛?｝和｛?｝是联结词的充足集
定义 4：若一联结词充足集的任意真子集不再是联结词的充足集，则称其为 极小联结词充足集
例子：｛?｝、｛?｝、｛ ┐,?｝、｛ ┐,? ｝、
｛ ┐,→ ｝（自证）
42
1-7对偶和范式
定义 1：在只包含联结词｛ ┐,?,?｝的命题公式 A中，将联结词?换成?，将?换成?，特殊变元
F和 T亦互换，所得公式 A*称为 A的 对偶式
例子：求 ┐ （ P?Q)?R的对偶式
定理 1：设 A*是 A的对偶式,P1,P2,P3……,Pn
是出现于 A和 A*中的 原子变元,则有
1)┐A(P1,P2,P3……,Pn）
A*（ ┐ P1,┐ P2,┐ P3……,┐Pn ）
2) ┐A *（ P1,P2,P3……,Pn）
A(┐P1,┐ P2,┐ P3……,┐Pn ）
43
1-7对偶和范式证明,1)施归纳于 A中出现的联结词的个数 n
n＝ 0时（即不含联结词时），则 A中只有一个原子变元，不妨记为 P1，显然有
┐ A（ P1）＝ ┐ P1＝ A*（ ┐ P1）
假定 n>0，即 A有 n个联结词，又具有少于 n个联结词的限制命题公式均满足式 1)。按命题公式的构造方式,A可能具有如下形式
a) ┐B b) B?C c) B?C
由归纳假设,┐ B?B* (┐),┐C?C*(┐),则：
a) ┐A(P1,P2,P3,…,Pn）?B
┐B * （ ┐ P1,┐P2,┐P3,…,┐Pn ）
A*（ ┐ P1,┐P2,┐P3,…,┐Pn ）
44
1-7对偶和范式
b) ┐A （ P1,…,Pn）
┐ （ B（ P1,…,Pn）?C（ P1,…,Pn））
┐ B（ P1,…,Pn）?┐ C（ P1,…,Pn）
B*（ ┐ P1,…,┐Pn ）?C*（ ┐ P1,…,┐Pn ）
A*（ ┐ P1,…,┐Pn ）
c) ┐A （ P1,…,Pn）
┐ （ B（ P1,…,Pn）?C（ P1,…,Pn））
┐ B（ P1,…,Pn）?┐ C（ P1,…,Pn）
B*（ ┐ P1,…,┐Pn ）?C*（ ┐ P1,…,┐Pn ）
A*（ ┐ P1,…,┐Pn ）
归纳步完成。由此,1）对于任意自然数 n成立
2）证明,证法一、证法二
45
1-7对偶和范式
例子,A（ P1,P2,P3） =┐P1?（ P2?P3），验证定理 1
解,1) ┐A （ P1,P2,P3）
┐ (┐P1?（ P2?P3））
┐ （ ┐ P1）?（ ┐ P2?┐P3 ）
A*(┐P1,┐ P2,┐ P3)
┐( ┐P1)?(┐P2?┐P3)
46
1-7对偶和范式
2) A（ ┐ P1,┐ P2,┐ P3）
P1?（ ┐ P2?┐P3 ）
┐ A*(P1,P2,P3)
┐ （ ┐ P1?（ P2?P3））
P1?（ ┐ P2?┐P3 ）
定理 2：如果 A?B，则 A*? B*
证明：设 P1,P2,…,Pn是出现在命题公式 A,B中的原子变元，因为 A?B，即,A（ P1,P2,…,Pn）
B （ P1,P2,…,Pn）是一个重言式。故有：
47
1-7对偶和范式
A（ ┐ P1,┐P2,…,┐Pn ）?B
（ ┐ P1,┐P2,…,┐Pn ）是一个重言式。即 A
（ ┐ P1,┐P2,…,┐Pn ）?B
（ ┐ P1,┐P2,…,┐Pn ）
再由定理 1,┐ A*? ┐B *,即 A*? B*
问题：是否每个 Pi,1<=i<=n,必须同时出现在 A和 B中，定理才能成立？
48
1-7对偶和范式
引入范式的目的：通过命题公式的标准形式，研究其性质。
定义 2：一个命题公式称为 合取范式,当且仅当它具有形式,A1?A2?…?An，其中 A1,A2,…,An都是由命题变元或其否定组成的析取式
定义 3：一个命题公式称为 析取范式,当且仅当它具有形式,A1?A2?…?An，其中 A1,A2,…,An都是由命题变元或其否定组成的合取式
49
1-7对偶和范式
求任意命题公式的合取（析取）范式的步骤
1）将公式中的联结词化成 ┐,?,?
2）利用德摩根律将否定符号 ┐ 直接移到各个命题变元之前
3）利用分配律、结合律将公式归约为合取范式
（析取）范式
注：一个命题公式的合（析）取范式不是唯一的，如
P?（ Q?R）?（ P?Q）?（ P?R）
（ P?P）?（ P?R）?（ P?Q）?（ Q?R）
50
1-7对偶和范式
定义 4,n个命题变元的合取式，称为 小项,其中每个变元与它的否定不能同时存在，但两者必须出现一次且仅一次
注,n个命题变元的小项有 2^n个由小项真值表（ p33）可知，没有两个小项是等价的，且每个小项只在一组真值指派下为 T
可以为小项指定一种编码，例如 m01对应于
┐ P?Q,m11对应 P?Q,m101对应 P?┐ Q?R等。
51
1-7对偶和范式小项的编码具有如下性质：当且仅当真值指派与小项的编码相同时，小项的真值为 T；否则小项的真值为 F
任意两个不同小项的合取为 F；
全体小项的析取为 T
定义 5：对于给定的命题公式，其中出现的原子变元记为 P1,P2,…,Pn。如果有一个等价公式，
它仅由 P1,P2,…,Pn的小项的析取构成，则该等价公式称为原式的 主析取范式
注：一个公式的主析取范式是唯一的
52
1-7对偶和范式
定理 3：在真值表中，一个命题公式的真值为 T的指派所对应的小项的析取，即为该命题公式的主析取范式证明：显然，对于任何真值指派，按如上方法构造的命题公式与原命题公式具有相同的真值；并且它又是一个小项的析取式，
即它是一个主析取范式
53
1-7对偶和范式
注：可以利用真值表，也可以利用等价变换来构造主析取范式
例子：求（ P?Q）?（ P?R）的主析取范式解：（ P?Q）?（ P?R）
（ （ P?Q）?（ R? ┐R ））?（（ P?R）?
（ Q? ┐ Q））
（ P?Q? R）?（ P?Q?┐R ）?（ P?┐ Q?R）
54
1-7对偶和范式
注：等价变换法求主析取范式的一般步骤
1）化归为析取范式
2）除去析取范式中所有永假析取项
3）合并重复项
4）补入合取项中没有出现的命题变元，例如添加（ P?┐ P）等,再用分配律展开
定义 6,n个命题变元的析取式，称为 大项,其中每个变元与它的否定不能同时存在，但两者必须出现一次且仅一次
55
1-7对偶和范式
注：可以为大项指定一种编码，例如,M00对应
P?Q,M101对应 ┐ P?Q?┐ R
大项具有如下性质：每个大项当其真值指派与编码相同时，其真值为 F，否则其真值为 T；
任意两个不同大项的析取为 T；全体大项的合取必为 F
定义 7：对于给定的命题公式，如果有一个等价公式，它仅由大项的合取组成，则该等价式称作原式的 主合取范式
注：一个公式的主合取范式是唯一的
56
1-7对偶和范式
定理 4：在真值表中，一个命题公式的真值为 F的指派所对应的大项的合取，即为该命题公式的主合取范式
证明：显然，对于任何真值指派，按如上方法构造的命题公式与原命题公式具有相同的真值；并且它又是一个大项的析取式，即它是一个主合取范式
注：主合取范式亦可由等价变换求得，基本步骤如下
1）化归为合取范式
2）除去合取范式中所有永真合取项
3）合并重复项
4）补入合取项中没有出现的命题变元，例如添加
（ P?┐ P）等,再用分配律展开
57
1-7对偶和范式
问题,n个命题变元的主析（合）取范式的共有多少个？
例：求 ┐ （ P?Q）? （ P?Q）的主合取范式解,┐ （ P?Q）?（ P?Q）
（ ┐ (P? Q)?(P? Q)）?((P?
Q)?┐(P?Q))
（ ┐ P?┐Q?P?Q）?((P?Q)?(┐P?┐Q))
(P? Q)?(┐P? ┐Q)
58
1-7对偶和范式
注：标记若 P的主析取范式为则其主合取范式为
kji mmmkji,,
kji MMMkji,,
12,.,,,1,1,.,,,0 11 nii
kiii,.,,,,21
59
1-8推理理论
推理的过程是由逻辑前提出发，根据逻辑推理规则，导出逻辑结论的过程。
推理的出发点是逻辑前提。逻辑前提有两种：逻辑永真式和假设前提。前者是命题逻辑系统固有的公理；后者由特定知识系统引入。
在某个特定的知识领域中做推理的时候，需要把该系统的定律、原理作为假设前提。一般地，具体系统的假设前提不应是逻辑永真式，但是在推理中这些假设前提的真值需要始终被认为是 T
定义 1：设 A和 C是两个命题公式，当且仅当 A→C
是一个重言式（即 A重言蕴含 C），称 C是 A的有效结论，或 C可由 A逻辑推出
60
1-8推理理论
注：上述定义可推广到 n个前提的情形：设 H1，
H2,…,Hn,C是命题公式，当且仅当
H1?H2?…?Hn→C 是重言式，称 C是前提 H1，
H2,…,Hn的有效结论
真值表法：直接给出包含前提 H1,H2,…,Hm和结论 C的真值表，检查是否每一个前提均为 T的行所对应的 C的真值也为 T；或者检查是否每一个结论 C为 F的行中至少有一个前提为 F
61
1-8推理理论
例子：前提,P?Q?R,┐ （ P?Q)；求证结论 R
P Q R P?Q?R ┐ （ P?Q）
0 0 0 0 1
0 0 1 1 1
0 1 0 1 0
0 1 1 1 0
1 0 0 1 0
1 0 1 1 0
1 1 0 1 0
1 1 1 1 0
62
1-8推理理论
问题：是否可以用真值表法作为一般的推理方法？
直接证法：由一组前提，利用推理规则，根据已知的等价或蕴含公式，推演得到有效结论。
P规则：前提在推导过程中的任何时候都可以使用。
T规则：推导中，如果有公式重言蕴含着 S，则公式
S可以引入推导注：等价式看作双向的蕴含
常用的蕴含（ Implication）式和等价
（ Equivalence）式见 p43
63
1-8推理理论
求证,R?S是前提 C?D,C→R,D→S 的有效结论。
证明,1 C?D P
2 C→R P
3 D→S P
4 ┐C→D T （ 1） E
5 ┐R→┐C T （ 2） E
6 ┐R→S T （ 5）（ 4）（ 3） I
7 R?S T（ 6） E
64
1-8推理理论
定义 2：设命题公式的集合为 { H1,.…,Hm}，
如果 H1?H2?…?Hm为永假式，则称公式 H1，
H2,…,Hm是不相容的；否则，称其为相容的
定理 1（间接证法 1 ）：设有一组前提 H1，
H2,…,Hm，要推出结论 C，只需证明 H1，
H2,…,Hm与 ┐ C是不相容的证明：要证 H1,H2,…,Hm推出 C，即要证
H1?H2?…?Hm?C。不妨将 H1?H2?…?Hm记作 S，
即要证 ┐ S?C为永真，故只需证 S?┐ C为永假
65
1-8推理理论
例子,求证 ┐ (P?Q)是 ┐ P?┐Q 的有效结论证,1 ┐┐(P?Q) P 附加前提
2 ┐P?┐Q P
3 P?Q T（ 1） E
4 P T（ 3） I
5 ┐P T （ 2） I
6 P?┐P( 矛盾 ) T（ 4）（ 5） E
所以,┐ (P?Q)?┐P?┐Q
66
1-8推理理论
定理 2（间接证法 2,CP规则 ）,设有一组前提 H1，
H2,…,Hm，要推出结论 R→C,只需证明
H1?H2?…?Hm?R?C
证明：设 H1?H2?…?Hm为 S，若 S?（ R→C ），
则有 S?（ ┐ R?C）
又 S→ （ ┐ R?C）?┐ S?（ ┐ R?C）
（ ┐ S?┐ R）?C
（ S?R） → C
故 S→ （ ┐ R?C）为永真式的充要条件是 （ S?R） → C
为永真式。
这样 H1?H2?…?Hm?R?C等价于 H1?H2?…?Hm?R→C
67
1-8推理理论
求证 W→┐T 是 P?Q→R?S,(T→Q)?(S→U),┐R,
(W→P)?(T→U) 的有效结论证,1 P?Q→R?S P
2 (T→Q)?(S→U) P
3 (W→P)?(T→U) P
4 ┐R P
5 W P 附加前提
6 ┐(R?S) T（ 4） I
7 ┐(P?Q) T（ 1）（ 6） I
8 P T（ 5）（ 3） I
9 ┐Q T （ 7）（ 8） I
10 ┐T T （ 9）（ 2） I
11 W→┐T T （ 10） CP
68
思考题,考试佯谬
逻辑课老师在周末放学时对学生说：
条件一：下周要进行一次考试；
条件二：到底哪天考试,你们在考试之前的任何一天都不能确知 。
注：每周上课 5天 （ 周一至周五 ）,每天都上一节逻辑课只有在逻辑课时才可能考试 。
一个聪明的学生运用逻辑知识做出了以下推理：
推论一：周五不可能考试,考试时间一定是周一至周四的某一天 。 因为如果周一至周四都不考,那么周四下课时我们就事先知道了明天一定考试,这不符合条件二 。 但根据条件一,下周肯定考试,因此考试时间只能是周一至周四的某一天,周五可以排除 。
69
思考题,考试佯谬
推论二：周四也不可能考试，考试时间一定是周一至周三的某一天。因为如果周一至周三都不考，那么周三放学时我们就事先知道了明天考试，这不符合条件二。但根据条件一，下周肯定考试，因此考试时间只能是周一至周三的某一天，周四可以排除。
推论三：周三也不可能考试,推理过程同上 。
推论四：周二也不可能考试,推理过程同上 。
推论五：周一也不可能考试,推理过程同上 。
结论：下周就不可能考试
70
思考题,考试佯谬
但是老师确实在下周的某一天考试了，这个聪明同学感到非常意外。问题究竟出在哪里呢？
一篇短文，说明你对这个问题的看法，下次课提交。
提示：将推理过程形式化
不失一般性，考虑简化问题的版本：每周只有两次逻辑课，分别在周一和周四。教师在本周四下课时宣布下周将有一次逻辑考试。。。
71
思考题,考试佯谬
考试佯谬的一个形式表述
命题常元
ExamB,考试在下周一的逻辑课上进行
ExamD,考试在下周四的逻辑课上进行
Know,学生在考试所在的那天之前知道考试的时间
系统公理,A1,（ ExamB?┐ExamD ）?（ ┐ ExamB?ExamD）
A2,┐ Know
A3,┐ ExamB→Know
A4,┐ ExamD→Know
72
思考题,考试佯谬
论证过程,用间接证法 1证明 A1-A4和 ExamD矛盾，推出 ┐ ExamD；
再用间接证法 1证明 A1-A4和 ExamB矛盾，推出 ┐ ExamB
（ 1） 1 ExamD 附加前提
2（ ExamB?┐ExamD ）?（ ┐ ExamB?ExamD） P
3（ ExamB?ExamD）?（ ┐ ExamB?┐ExamD ） T (2)
4 ┐ExamB?┐ExamD T (3)
5 ┐ExamB T (1)(4)
6 ┐ExamB→Know P
7 Know T (5)(6)
8 ┐Know P
所以，有 ┐ ExamD
73
思考题,考试佯谬
(2) 1 ExamB 附加前提
2（ ExamB?┐ExamD ）?（ ┐ ExamB?ExamD） P
3（ ExamB?ExamD）?（ ┐ ExamB?┐ExamD ） T (2)
4 ┐ExamB?┐ExamD T (3)
5 ┐ExamD T (1)(4)
6 ┐ExamD→Know P
7 Know T (5)(6)
8 ┐Know P
所有，有 ┐ ExamB
综合（ 1）和（ 2），有 ┐ ExamB?┐ExamD
74
思考题,考试佯谬
两个结论,1 学生推理的没有错误
2 教师的两个条件符合事实，故应视为真命题
问题,似乎正确的前提和正确的推理导致了错误的结论
（即与教师宣称的真命题矛盾的结论），为什么？
回答,佯谬之所以出现，是因为试图将一个广义 哥德尔型命题 （可粗略地理解为涉及系统 元知识 的命题）显式地作为系统公理，来建构系统的完备性。不幸的是，一旦这个原本是直觉真的广义哥德尔型命题在系统中被作为公理显式地表达出来，系统在一致性方面就产生了新的问题。
,There are truths of silence,when spoken,no
longer true anymore.” Ludwig Wittgenstein
75
1-9形式化命题逻辑系统 L
考试佯谬这类逻辑悖论促使人们深入省思逻辑系统的本质，它的能力和局限。对形式化的逻辑系统的研究有助于实现这个目的。在理论方面：形式化逻辑系统帮助人们澄清逻辑系统的 元性质 (一致性、完全性）,澄清基本的数学哲学问题（例如，数学是否可以形式化－希尔伯特方案）；在应用方面：形式化逻辑系统在理论计算机科学、计算机科学、人工智能、软件工程等领域有着深刻的应用。
命题逻辑形式系统 L定义如下
1 符号字母表,┐,→,（，）,p1,p2,p3,…
注：｛ ┐,→ ｝是联结词的充足集
76
1-9形式化命题逻辑系统 L
2 命题公式的集合：如下 3条递归规则确定命题公式的集合
（ 1）对每个 i>=1,pi是命题公式
（ 2）若 A和 B是命题公式，则（ ┐ A）和（ A→B ）是命题公式
（ 3）所有命题公式由递归应用（ 1）和（ 2）产生
3 公理：
L1,（ A→ （ B→A ））
L2,（（ A→ （ B→C ）） → （（ A→B ） → （ A→C ）））
L3,（（（ ┐ A） → （ ┐ B）） → （ B→A ））
注,A,B和 C可以是任意命题公式显然，公理 L1-L3是永真式
77
1-9形式化命题逻辑系统 L
4 演绎规则（分离规则，记为 MP)：从 A和（ A→B ），可以获得 B
定义 1,L中的一个证明是命题公式的一个序列 A1,A2,…,An，
使得对每个 i（ 1<=i<=n),Ai或者是 L的公理，或者是由序列中在前面的两项利用演绎规则得到的
注,L中的公理当然也是 L中的定理，它们在 L中的证明是其自身
例子：如下序列是 L中的证明
（ 1）（ p1→ （ p2→p1 ）） L1
（ 2）（（ p1→ （ p2→p1 ）） → （（ p1→p2 ） → （ p1→p1 ）） L2
（ 3）（（ p1→p2 ） → （ p1→p1 ）） （ 1），（ 2）,MP
78
1-9形式化命题逻辑系统 L
例子：在 L中求证 Q→R 是 P,Q→ （ P→R ）的逻辑结论证明,P P
Q→ （ P→R ） P
P→ （ Q→P ） L1
Q→P (1),(3) MP
(Q→ （ P→R ） )→((Q→P)→ （ Q→R ）） L2
(Q→P)→ （ Q→R ） (2),(5) MP
（ Q→R ） (4),(6) MP
79
1-9形式化命题逻辑系统 L
对于系统 L，我们关心如下一些问题：是否 L的每个定理都是重言式；基于 L的推演是否可能导致矛盾：即对任意的命题公式 A和 ┐ A，是否可能同时被 L证明为定理；以及 L是否可以证明 所有 永真式
定义 2（可靠性定义）：若 L的任意定理都是重言式，则称 L是 可靠的
定义 3（一致性定义）,若 L的任意互为否定的命题公式 A
和 ┐ A不同时为 L的定理，则称 L是 一致的
定义 4（完备性定义）：若 L中的任意重言式都是 L的定理，
则称 L是 完备的
定义 5（可判定性定义）：若存在一个通用的算法，判定任意命题公式是否是 L的定理，则称 L是 可判定的
定理 1（可靠性定理）,L的可靠的
80
1-9形式化命题逻辑系统 L
证明：（数学归纳法）设 A是 L的定理，施归纳于 A
的证明序列中所含命题公式的个数 n。
当 n＝ 1时,A的证明序列只包含一个命题公式,A是 L的公理，即 A是重言式当 n>1时，假设 L中证明序列长度小于 n的定理都是重言式
（归纳假设）。由于定理 A在 L中存在一个证明，则 A或者是 L的公理，或者由 MP规则获得。当 A是 L的公理时,A显然是重言式。当 A是由 MP规则获得时，其证明序列中必存在两个命题公式，不失一般性，记为 B和 B→A 。由于 B和
B→A 的证明序列长度小于 n，由归纳假设，它们是重言式。
这样 A必然是重言式。
综上,L是可靠的。
81
1-9形式化命题
定理 2（一致性定理）,L是一致的证明：反证法，若 L是不一致的，则存在命题公式 A，使得 A和 ┐ A均为 L的定理。由 L的可靠性定理,L的定理必是重言式，矛盾。
定理 3（完备性定理）,L是完备的证明：略。
定理 4（可判定性定理）,L是可判定的。
证明：真值表法。
82
1-9形式化命题逻辑系统 L
进一步的思考：更重要和实际的形式数学系统，如形式化数论系统，是否也具有系统 L的良好性质？如果回答是肯定的，上述数学系统的全部内涵即可由形式系统囊括，
至少在理论上，我们可以编写一个计算机程序，利用简单地穷尽搜索，逐步获得一个又一个定理，数学发现的过程可以还原为计算机程序操作
回答：这样的前景从来不会发生。 绝大多数 实际数学系统的形式化是不完备的（哥德尔第一不完备性定理），
甚至其一致性也无法在系统之内得到证明（哥德尔第二不完备性定理）。 数学真理不可能由包括程序在内的任何机械过程所穷尽，而必然包含直觉和洞察的成份 。存在着对于人的直觉来说明显为真，但无法形式证明的良定义数学命题（哥德尔）；存在无限多不可由,机械过程,计算的函数（图灵）；存在着具有重要实际意义，
但无法被机械过程解决的判定问题（停机问题－图灵）。
83
1-9形式化命题逻辑系统 L
注：机械过程?现代数字计算机程序?算法?图灵机所谓的,机械过程,,应广义理解，指可实现的物理过程。
,机械过程,涉及到数学之外的物理的内涵。量子计算的某些最新理论研究结果似乎暗示，某种理论上的量子计算模型似乎可以实现某些经典机械过程无法实现的计算任务（如等价于停机问题的丢番图方程解的存在性判定问题），但是上述结果尚未形成定论。
思考题,某些人认为，形式数学系统的不完备性意味着人工智能的不可能性，存在着直觉上为真但形式系统内无法证明的真理，说明人心比机器和程序更优越，程序不可能充分模拟人类智能。谈谈你对该问题的看法。
进一步的参考书目：
,皇帝新脑,,彭罗斯，胡南科技出版社
,哥德尔、埃舍尔、巴赫,,D,Hofstadter,商务印书馆
84
第二章 谓词逻辑
2-1谓词的概念与表示
目的,1 刻画客体的 性质 或 关系 2 克服命题逻辑的局限
例子,他 是三好学生他,x,是三好学生 P(.)； P(x)：他是三好学生
7是质数
7,x,是质数 P(.)； P(x),7是质数
例子：人都是要死的；
苏格拉底是人；
所以苏格拉底是要死的。
注：用大写字母表示谓词，用小写字母表示客体名称
（常元或变元）
用谓词＋客体名称构成一个完整命题
A(x):一元谓词； A(x,y)二元谓词； …
85
2-1谓词的概念与表示
谓词字母填上客体名称后形成的式子称为谓词填式代表客体名称的字母，一旦确定其所指，在多元谓词中以不同次序出现将导出不同的谓词。
例如,a,b确定地指代不同对象，则 A(a,b)和
A(b,a)是两个不同命题。
谓词刻画客体的性质和关系
86
2-2命题函数与量词
目的：简洁地表达相关命题的集合
定义 1：由一个谓词，一些客体变元构成的表达式称为简单 命题函数
例子,S（ x）,x是好学生，当 x分别指代张三、
李四和王五时，代表三个不同的命题
S（ x,y,z）,x+y=z，当 x,y和 z 分别指代不同的数时，代表一些不同的命题
87
2-2命题函数与量词
注,n元谓词就是有 n个客体变元的命题函数，当 n＝ 0时，
称为 0元谓词，它本身就是一个命题一个或多个简单命题函数以及逻辑联结词，根据命题公式递归构造规则，组合成的表达式称为复合命题函数命题函数不是一个命题，只有客体变元的所指确定之后，才能成为一个命题。
客体变元在的取值范围内对于命题函数所确定的命题的真值有很大影响。
定义 2：在命题函数中，客体变元的论述范围称为 个体域 ；
一个命题函数中所有客体变元的个体域之并称为命题函数的个体域
注：个体域可能有限，也可能无限
88
2-2命题函数与量词
存在量词的引入例子,God存在性的本体论证明（圣安瑟伦）
定义 God为具有所有积极属性者，则 God必存在。
证明,（反证法）假设 God不存在，则我们可以设想一个 God*,God*保有 God的所有其他积极属性，除了需要额外设想 God*是存在的。 由于存在性是比虚无性积极的属性,
所以 God*比 God具有更多的积极属性，与前面对 God的定义矛盾。故 God存在。
你接受这个证明吗？
89
2-2命题函数与量词
康德的回答：存在性不能作为一个谓词
P(x),x是存在的 （非法谓词）
例子：用谓词表达,某个单位的职工中有大学生,这个命题。
1)G(x),x是大学生
E(x)：存在 x
假设 x的个体域是某单位的职工则有,E(x)?G(x)
2） G(x):x是大学生假设 x的个体域是某单位的职工使用存在量词?，则有 （?x） G(x)
90
2-2命题函数与量词
是 存在量词
x读作 ‘ 存在 x?
x ┐P(x) 表示 ‘ 存在 x，使 ┐ P(x)为真 ’
┐?x ┐P(x) 表示 ‘ 不存在 x，使 P(x)为真 ’
全称量词的引入例子：假设用谓词表达,某个单位的职工全是大学生,
这个命题。
G(x):x是大学生；
假设 x的个体域是某单位的职工
（?x） G(x)
假设 x的个体域是该单位所在城市的全体职工？
91
2-2命题函数与量词
x是全称量词
x读作 ‘ 对任意 x?
（?x） P(x)表示 ‘ 对一切 x,P(x)为真 ’
（ ┐?x） ┐ P(x)表示
‘ 并非对任意 x,┐P(x) 是真 ’
全称量词和存在量词可以相互表示：
（?x） P(x）?┐ (?x) ┐P(x)
(?x) P(x)
92
2-2命题函数与量词
定义 3,所有一组特定命题函数的个体域的并，称为 全总个体域
例子,M(x),x是人； D(x),x是要死的； S(x),x怕死
1） 若论述域是全人类：
则 ‘ 人总是要死的 ’ 可译为?xD(x)
有些人不怕死 ’ 可译为?x┐S(x)
2） 若论述域是包括非人类的某个全总个体域：
则 ‘ 人总是要死的 ’ 可译为?x(M(x)→D(x)) 。
注意不能译为?x(M(x)?D(x))。
其意义是 ‘ 所有的 x,x都是人并且都是要死的 ’
‘ 有些人不怕死 ’ 可译为?x(M(x)?┐S(x))
93
2-2命题函数与量词
注,1）对全称量词，类别谓词作为蕴含式之前项加入
2）对存在量词，类别谓词作为合取项加入
例子：
没有不犯错误的人解：设 F(x)为 ‘ x会犯错误 ’,M(x)为 ‘ x是人 ’,则译为,
┐(?x (M(x)?┐F(x)))
用?x的形式表达？
某些人对某些食物过敏解：设 F(x,y)为 ‘ x对 y过敏 ’,M(x)为 ‘ x是人 ’,
G(x)为 ‘ x是食物 ’,则译为,
x?y (M(x)?G(x)?F(x,y))
94
2-2命题函数与量词尽管有人聪明，但未必一切人聪明解：设 M(x)为 ‘ x是人 ’,F(x)为 ‘ x聪明 ’ 则译为,
x(M(x)?F(x))?┐?x(M(x)→F(x))
每个建筑物都有一些装饰品解：设 A(x)为 ‘ x是建筑物 ’,
B(x,y)为 ‘ x有 y?，
C(x) 为 ‘ x是装饰品 ’,
则可译为：
x(A(x)→?y(B(x,y)?C(y))
用?x的形式表达？
95
2-2命题函数与量词对于实数 x,y和 z，如果 x>y，并且 z>0，那么 xy>yz
解：设 >(x,y) 为 ‘ x>y?,R(x)为 ‘ x是实数 ’
则译为,
x?y?z(R(x)?R(y)?R(z)→
((>(x,y)?>(z,0))→>(xy,yz))
96
2-3谓词公式与翻译
客体常元、客体变元和 客体函元 。客体函元即某个函数作用于客体常元或客体变元的结果，例如 f(x),x是客体常元或客体变元
定义 1：形如 A(x1,x2,…,xn)的公式称为 谓词演算的原子公式,其中 x1,x2,…,xn是客体变元、客体常元或客体函元
定义 2：谓词演算的合式公式的递归定义如下
1） 原子谓词公式是合式公式
2） 若 A是合式公式，则 ┐ A是合式公式
97
2-3谓词公式与翻译
3） 若 A和 B是合式公式，则（ A?B），（ A?B），（ A→B ）和
（ A?B）是合式公式
4） 如果 A是合式公式,x是 A中的任何变元，则（?x） A和（?x） A
是合式公式
5） 只有经过有限次应用步骤 1）－ 4）所获得的公式才是合式公式
注：最外层的括号可以省略，但量词后面的括号一般不能省略谓词合式公式简称为谓词公式符合语法的谓词公式的语义不一定总是符合直觉的，例如考虑如下谓词公式：
（?x）（?x） A（ x）,（?x） （?x） A（ x）
98
2-3谓词公式与翻译
思考题：如何用程序判定一个字符串是否是谓词公式？
例子：
并非每个实数都是有理数
（?x）（ R（ x）?┐ Q（ x））
如果一个数是偶数，那么它至少有一个素因子为偶数
Even（ x）,x是偶数
Factor（ x,y）,y是 x的素因子
（?x）（ Even（ x） → （?y）（ Factor（ x,y）?Even（ y）））
99
2-4变元的约束
定义 1,谓词公式 A的一部分形如（?x） P（ x）或（?x）
P（ x），则?或?后面所跟的变元叫做量词的 指导变元 或作用变元,P（ x）叫做相应量词的 作用域 或 辖域,在作用域中 x的一切出现，称为 x在 A中的 约束出现,x亦称为被相应量词中的指导变元所约束的 约束变元 。不是约束变元的客体变元称为自由变元
例子：指出下式中的自由变元和约束变元，以及指导变元的辖域
（?x） P(x)→Q(x)
（?x）（?y） (P(x,y)→Q(x,y) )?P(y,z)
100
2-4变元的约束
注：由约束变元的概念,P(x1,x2,…,xn)是 n元谓词，
有 n个独立的自由变元若对 P(x1,x2,…,xn)的 n-k个自由变元进行约束，
则成为 k阶谓词若 对 P(x1,x2,…,xn)的所有自由变元进行约束，
则成为一个命题为什么？
为了避免变元的约束形式和自由形式同时出现，引起混淆，可对变元做 换名,使得一个变元在一个公式中只呈一种形式出现
（?x） P（ x） → Q（ x）
101
2-4变元的约束
换名规则：
1）对约束变元可以进行换名，其更改的范围是量词中的指导变元和量词的作用域中出现的该变元，公式的其余部分不变
2）换名时要更改为作用域中没有出现的变元名称
可对自由变元换名，一般称对自由变元的换名为 代入
代入规则：
1）代入时需对公式中出现该自由变元的每一处进行
2）用以代入的变元与原公式中所有变元的名称不能相同
3）可以用客体常元做代入,但此时不是等价替换
102
2-4变元的约束
例子：对（?x）（ P（ x） → R（ x,y））?Q（ x,y,z）换名解,（?w）（ P（ w） → R（ w,y））?Q（ x,y,z）？
（?y）（ P（ y） → R（ y,y））?Q（ x,y,z）？
（?z）（ P（ z） → R（ z,y））?Q（ x,y,z）？
对（?x） (A(x)?B(x,y))?C(x)?D(w)换名、代入解,（?z） (A(z)?B(z,y))?C(x)?D(w)？
（?w） (A(w)?B(w,y))?C(z)?D(w)？
对（?x）（ P（ y）?R（ x,y））代入解,（?x）（ P（ z）?R（ x,z））？
（?x）（ P（ z）?R（ x,y））？
103
2-4变元的约束
注：量词作用域中的约束变元，当论域的元素有限时，
客体变元的所有代入是可枚举的。例如，若论域是｛ a，
b｝则有：
（?x） P（ x）? P（ a）?P（ b）
（?x） P（ x）?P（ a）?P（ b）
量词对变元的约束与量词的次序有关，改变次序可能改变谓词公式的含义设论述域为有理数,P(x,y)表示 x+y=0,Q(x,y)表示 x*y=0
(?y)(?x)(P(x,y)) (?x)(?y)(P(x,y)=0)
(?x)(?y)(Q(x,y)) (?y)(?x)(Q(x,y)=0)
104
2-5谓词演算的等价公式与蕴含式
定义 1：用确定客体取代谓词公式中的客体变元的过程，
称作对谓词公式 赋值 。赋值后的谓词公式成为具有确定真值的命题
定义 2：给定两个谓词公式 A和 B，设其具有相同的个体域
E，若对 A和 B中的任一组变元进行赋值，所得命题的真值相同，称谓词公式 A和 B在 E上是 等价 的，记作 A?B
定义 3：给定任意谓词公式 A，其个体域为 E，若对于 A的所有赋值，均使其真值为 T，则称 A在 E上是 永真的（或有效的）
定义 4：给定任意谓词公式 A，其个体域为 E，若对于 A的所有赋值，均使其真值为 F，则称 A在 E上是 不可满足的
105
2-5谓词演算的等价公式与蕴含式
定义 5：给定任意谓词公式 A，其个体域为 E，若至少存在
A的一组赋值，使其真值为 T，则称 A在 E上是 可满足的
注：谓词演算中赋值的作用类似于命题演算中真值指派的作用，即赋值使得谓词具有了特定真值。
若谓词公式 A中不包含自由变元，则给定 A的个体域 E，
即可确定 A的真值（更确切地说，是包括了个体域的 解释确定了 A的真值。所谓解释，这里可粗略理解为谓词符号的语义和谓词公式的个体域）
当谓词演算中的公式代替命题演算中永真式的命题变元时，所得的谓词公式即为谓词演算的永真式，故命题演算中的等价公式和蕴含式都可以在谓词演算中使用。 为什么？
106
2-5谓词演算的等价公式与蕴含式
例子：（?x）（ P（ x） → Q（ x））?（?x）（ ┐ P（ x）
Q（ x））
量词与联结词 ┐ 之间的关系（量词转化律）：
┐ （?x） P（ x）?（?x） ┐ P（ x）
┐ （?x） P（ x）?（?x） ┐ P（ x）
注：出现在量词前的否定，不是否定该量词，而是否定被该量词量化的整个命题
有限个体域上量词转化律的证明：
设个体域中的客体为 a1,a2,…,an，则
107
2-5谓词演算的等价公式与蕴含式
1） ┐ (?x） P(x)
┐(P(a1)?P(a2)?…?P(an))
┐P(a1)? ┐P(a2)?…? ┐P(an)
（?x） ┐ P(x)
2） ┐ （?x） P(x)
┐(P(a1)?P(a2)?…?P(an))
┐P(a1)?┐P(a2)?…?┐P(an)
（?x） ┐ P(x)
注：上述结果可以推广到无穷的个体域
108
2-5谓词演算的等价公式与蕴含式
量词作用域的扩张与收缩：
1）（?x） A(x)?P?（?x） (A(x)?P)
2）（?x） A(x)?P?（?x） (A(x)?P)
3）（?x） A(x)?P?（?x） (A(x)?P)
4）（?x） A(x)?P?（?x） (A(x)?P)
5）（?x） A（ x） → B?（?x）（ A（ x） → B）
6）（?x） A（ x） → B?（?x）（ A（ x） → B）
7） B→ （?x） A（ x）?（?x）（ B→ A（ x） ）
8） B→ （?x） A（ x）?（?x）（ B→ A（ x） ）
9） (?x)A(x)→(?x)B(x)?(?x)(A(x)→ B(x))
109
2-5谓词演算的等价公式与蕴含式证明,6）（?x） A（ x） → B
┐ （?x） A（ x）?B
（?x） ┐ A（ x）?B
（?x）（ A（ x） → B）
8） B→ （?x） A（ x）
┐ B?（?x） A（ x）
（?x）（ ┐ B?A（ x））
（?x）（ B→ A（ x））
注：当谓词的变元与量词的指导变元不同时，亦能有类似上述诸式的结果，例如：
(?x)A(x)→B(y)?(?x)(A(x)→B(y))
110
2-5谓词演算的等价公式与蕴含式
量词与命题联结词的一些等价公式：
1) (?x)(A(x)?B(x))?(?x)A(x)?(?x)B(x)
2) (?x)(A(x)?B(x))?(?x)A(x)?(?x)B(x)
证明,2）?x(┐A(x)?┐B(x))
(?x)(┐A(x))?(?x)(┐B(x))
两边取非：
┐?x(┐A(x)?┐B(x))
┐( (?x)(┐A(x))?(?x)(┐B(x)))
(?x)(A(x)?B(x))
(?x)A(x)?(?x)B(x)
111
2-5谓词演算的等价公式与蕴含式
量词与命题联结词之间的一些蕴含式：
1) (?x)A(x)?(?x)B(x)?(?x)(A(x)?B(x))
2) (?x)(A(x)?B(x))?(?x)A(x)?(?x)B(x)
3) (?x)(A(x)→B(x))?(?x)A(x)→(?x)B(x)
4) (?x)(A(x)?B(x))?(?x)A(x)?(?x)B(x)
证明,3) (?x)(A(x)→B(x))
(?x)(┐A(x)?B(x))
(?x)┐(A(x)?┐B(x))
┐(?x)(A(x)?┐B(x))
┐((?x)A(x)?(?x)(┐B(x)))
┐(?x)A(x)? ┐(?x)(┐B(x))
(?x)┐A(x)?(?x)B(x)
┐(?x)A(x)?(?x)B(x)
(?x)A(x)→(?x)B(x)
112
2-5谓词演算的等价公式与蕴含式
P70表 2-5.1
多个量词的使用
1) (?x)(?y)P(x,y)?(?y)(?x)P(x,y)
2) (?x)(?y)P(x,y)?(?y)(?x)P(x,y)
3) (?x)(?y)P(x,y)?(?y)(?x)P(x,y)
4) (?y)(?x)P(x,y)?(?x)(?y)P(x,y)
5) (?y)(?x)P(x,y)?(?x)(?y)P(x,y)
6) (?x)(?y)P(x,y)?(?y)(?x)P(x,y)
7) (?x)(?y)P(x,y)?(?y)(?x)P(x,y)
8) (?y)(?x)P(x,y)?(?x)(?y)P(x,y)
113
2-5谓词演算的等价公式与蕴含式证明,5） (?y)(?x)P(x,y)?(?x)(?y)P(x,y)
证法 1：存在一 y，对任意的 x,P(x,y)为 T；即对任意 x，对这个
y而言，使 P(x,y)为真；也就是对任意 x，存在 y，使 P(x,y)真证法 2,?y?xP(x,y)
(P(a1,a1) ∧ P(a2,a1)…… ∧ P(an,a1))
∨(P(a1,a2) ∧ P(a2,a2)…… ∧ P(an,a2))
∨ …
∨(P(a1,an) ∧ P(a2,an)…… ∧ P(an,an))
(P(a1,a1) ∨ P(a1,a2)…… ∨ P(a1,an))
∧ (P(a2,a1) ∨ P(a2,a2)…… ∨ P(a2,an))
∧ …
∧ (P(an,a1) ∨ P(an,a2)…… ∨P (an,an))
x?yP(x,y)
114
2-6前束范式
定义 1：一个谓词公式，如果量词均在全式的开始，它们的作用域延伸到整个公式的末尾，则该公式称为前束范式
例子,(?x)(?y)(?z)(Q(x,y)→R(z))
(?x)(?y)(┐P(x,y)→Q(y))
定理 1：任何一个谓词公式，均和一个前束范式等价证明,1)把否定词深入到命题变元和谓词前面
2)利用 A?(?x)B(x)?(?x)(A?B(x))
A?(?x)B(x)?(?x)(A?B(x))把量词推到前面
3)利用改名规则：
(?x)A(x)?(?x)B(x)
(?u)A(u)?(?x)B(x)
(?u)(?x)(A(u)?B(x))把量词推到前面
115
2-6前束范式
例子：把?x?y((?z)(P(x,y,z)?P(y,z))→(?u)Q(x,y,u))
化为前束范式解：原式
x?y(┐(?z(P(x,z)?P(y,z))?(?u)Q(x,y,u))
x?y(?z(┐P(x,z)?┐P(y,z))?(?u)Q(x,y,u))
x?y?z?u(┐P(x,y)?┐P(y,z)?Q(x,y,u))
把?xP(x,y)xQ(x,z)化为前束范式解：原式
xP(x,y)uQ(u,z)
x?u(P(x,y)?Q(u,z))
116
2-6前束范式
定义 2：若谓词公式是前束范式且作用域为合取范式，则称为 前束合取范式 。前束合取范式具有如下形式,
(□ u1)(□ u2)…,.(□ um)((A11?………?A1l1)?…
(An1?……,,?Anln)),这里□是?或?
定义 3：若谓词公式是前束范式且作用域为析取范式,则称为前束析取范式。前束析取范式形式,
(□ u1)(□ u2)…,.(□ um)((A11?………?A1l1)?…
(An1?……,,?Anln))
定理 2：任一谓词公式均可化为前束合取范式证明：首先利用定理 1的方法把谓词公式化为前束范式，
然后对作用域使用命题逻辑合取范式的化归方法转化为合取范式
117
2-6前束范式
定理 3：任一谓词公式均可化为前束析取范式证明：首先利用定理 1的方法把谓词公式化为前束范式，然后对作用域使用命题逻辑析取范式的化归方法转化为析取范式
例子：将?x?y(?zP(x,y,z) →?uQ(x,u) )uR(x,u)化为前束合取范式。
解：原式
x?y(?z┐P(x,y,z)uQ(x,u))vR(t,v)
x?y?z?u?v((┐P(x,y,z)? Q(x,u))?R(t,v))
x?y?z?u?v
(┐P(x,y,z)? Q(x,u))?R(t,v))
118
2-7谓词演算的推理理论
全称指定规则 简记为 US规则
xP(x)
------
P(c)
注：若对一切 x,P(x)为真,可推得对任意个体 c，都有
P(c)为真。
需要避免引入客体变元之间相互作用
例子,?x(P(x,z)yQ(x,y))
P(c,z)yQ(c,y)
P(y,z)yQ(y,y)
x(P(x,c)? Q(x,c))
P(c,c)? Q(c,c)
119
2-7谓词演算的推理理论
存在指定规则 简记为 ES规则
xP(x)
------
P(c)
注,若至少存在一个 x使得 P(x)为真，以 c标记取值于使得 P(x)为真的 x的集合的客体变元，即有使 P(c)。
通常,c可以看作是取值于个体域的特定子集的客体变元。
对于由全称量词衍生的 c，其取值的集合是全部个体域；对于由存在量词衍生的 c，其取值的集合一般是个体域的真子集需要避免引入客体变元之间相的互作用
例子,1）?xP(x)yQ(y)
P(a)?Q(b)
P(a)?Q(a)
2）?x (A(x,z)? B(c))
A(c,z)? B(c)
120
2-7谓词演算的推理理论
存在推广规则 简记为 EG规则
P(c)
------
x P(x)
注,c是某个确定的个体,若 P(c)为真,则?x P(x)
为真需要避免引入客体变元之间相的互作用
例子,?x P(x,c)z Q(c,z)
x (?x P(x,x)zQ(x,z))
y (?x P(x,y)zQ(y,z))
121
2-7谓词演算的推理理论
F全称推广规则 简记为 UG规则
P(x)
------
x P(x)
注：若对个体域中每一个客体 c,P(c)为真，则?x P(x)为真。
应用本规则时，必须能保证前提 P(x)对论域中的每个可能的 x
都是真的。具体在谓词演算的推理中，若一个谓词公式中的 x
是使用 US而自由的，后继推导中才能使用 UG规则
例子：下列推理过程 (P(x,y):y=x+1)是否正确？
1)?x?y P(x,y) P
2)?y P(c,y) US(1)
3) P(c,d) ES(2)
4)?x P(x,d) UG(3)
5)?y?x P(x,y) EG(4)
122
2-7谓词演算的推理理论
例子,下列推导是否有错误？
1.(1)?y(P(y)?Q(y)) P
(2)P(a)?Q(b) ES（ 1）
2.(1)?xP(x)→Q(x) P
(2) P(x)→Q(x) US （ 1）
3.(1)?xR(x)x(Q(x)?R(x)) P
(2) R(a)x(Q(x)?R(x)) ES（ 1）
例子,会议的每一个成员都是青年专家，一些成员来自人文学科。所以成员有一些是来自人文学科的青年。试构造一个证明来证明这一结论
123
2-7谓词演算的推理理论解：设 C(x)表示 ‘ x是会议成员 ’ 。
S(x)表示 ‘ x是专家 ’ 。
W(x)表示 ‘ x是青年 ’ 。
O(x)表示 ‘ x来自人文学科 ’ 。？
证：则结论形式化为：
x(C(x)→(W(x)?S(x)))x(C(x)?O(x))x(O(x)?W(x))
1,?x (C(x) → (W(x)? S(x))) P
2,?x( C(x)? O(x)) P
3 C(y)? O(y) ES（ 2）
4,C(y) → (W(y)? S(y)) US（ 1）,
5,C(y) T（ 4） I
124
2-7谓词演算的推理理论
6,W(y)? S(y) T（ 3）（ 5） I
7,O(y) T（ 4） I
8,W(y) T（ 6） I
9,O(y)? W(y) T（ 7）（ 8） E
10,?x( O(x)? W(x)) T（ 9） EG
例子：证明,?x(P(x) →Q(x))x(R(x) →┐Q(x))
x(R(x) →┐P(x))
证,1,?x(P(x) →Q(x)) P
2,?x(R(x) →┐Q(x)) P
3,P(x) →Q(x) US （ 1）
4,R(x) →┐Q(x) US （ 2）
5,Q(x) →┐R(x) T （ 4） E
6,P(x) →┐R(x) T(3)(5)I
7,?x(R(x) →┐P(x)) UG(6)
125
2-7谓词演算的推理理论
证明,?x(P(x)?Q(x))xP(x)xQ(x)
证明：反证法
1.?x(P(x)?Q(x)) P
2.┐(?xP(x)x Q(x)) P
3.?x┐P(x)x ┐Q(x) T（ 2） E
4.?x┐P(x) T （ 3） I
5.?x┐Q(x) T（ 4） I
6.┐P(y) ES(4)
7.┐Q(y) US （ 5）
8.┐(P(y)? Q(y)) T（ 6）（ 7） I
9.P(y)? Q(y) US（ 1）
10┐(P(y)? Q(y))? (P(y)? Q(y)) T（ 8）（ 9）矛盾其他证法：利用 CP规则
126
2-8形式化谓词演算系统 K
上节中的谓词演算系统 并非 完全形式化的，推理过程中使用推理规则时需要仔细考察谓词公式的具体含义。
这里谈论一个固定的，但是没有指明具体解释的形式化 一阶 谓词演算系统 K。 K的符号可以有许多不同的解释，但是我们关心的纯粹是语言的形式方面，着重讨论谓词公式的 逻辑关系 。在此基础上，讨论系统的 元性质,以及更为深入的 语义问题
形式化一阶谓词演算系统 K
符号字母表：
x1,x2,x3,… 客体变元
a1,a2,a3,… 客体常元
A11,A12,…,A21,A22,… 谓词字母，其中 Aij表示第 j个 i元谓词
f11,f12,…,f21,f22,… 函数字母，其中 fij表示第 j个 i元函数
127
2-8形式化一阶谓词演算系统
（，），,辅助技术性符号
┐,→ 逻辑联结词
量词
注 1：出于直观和表述方便的考虑，引入了函数符号（即函元）。客体常元、客体变元以及函数符号作用于客体常元和变元的结果可以作为谓词的项
K的项的递归定义：
1）客体变元和客体常元是项
2）若 fij是函数符号,x1,…,xi 是项，则
fij（ x1,…,xi)是项
3）所有的项通过有限次使用 1）和 2）生成
128
2-8形式化一阶谓词演算系统
注 2：函数是一种特殊的关系，而（多元）谓词也可以看作某种关系，这样函数实际上是一种特殊谓词，两者实际上可以互相表示。
问题：允许函数作为谓词的项,会不会破坏形式谓词演算系统的一阶性？
例子：任意比 x大 5的数大于比 x大 1的数
(?x)G(g5(x),g1(x))
(?x)(?y?z(G5（ y,x）?G1(z,x))→G(y,z))
值域的区别例子,P（ x):x不是真实的
P（ Q（ x） )
129
2-8形式化 一阶 谓词演算系统
注 3：语言中只有两个联结词,为什么？
注 4：语言中只有一个全称量词,为什么？
原子公式：形如 A(t1,t2,…,tn)的公式称为 K的 原子公式,
其中 t1,t2,…,tn是 K的项
合式公式：
1） K的每一原子公式是 K的合式公式
2） 若 A和 B是合式公式，则（ ┐ A），（ A→B ）和（?xi） A
是合式公式，这里 xi是任意客体变元
3） 只有经过有限次应用步骤 1）－ 2）所获得的公式才是合式公式
130
2-8形式化 一阶 谓词演算系统
下面将给出 K的公理。但是在此之前，需要澄清一个问题：
K的公理在何种意义上是真的？为了讨论谓词逻辑的真性问题，需要引入 解释 的概念。
定义 1,K的 解释 I是指一个对象域集合 DI、特异常元的集合 SI,DI上函数的集合 FI和关系的集合 RI。
注,K中的变元 x1,x2,… 的具体取值在 DI中产生； K中的客体常元在 SI上中产生； K中的函数和谓词分别由 FI和
RI产生
K的解释类似于 L的真值指派,K的谓词公式的真性需要基于解释加以讨论。
131
2-8形式化 一阶 谓词演算系统
例子,?x1(┐?x2)┐A21(x1,x2)
当 DI是正整数集合,A21(x1,x2)被解释为 x1*x2＝ 0时是假的；
当 DI是整数集合,A21(x1,x2)被解释为 x1*x2＝ 0时真
定义 2,K的解释 I的一个 赋值 是从 K的项到 DI的函数 v，满足：
对于 K的每个个体常元,v(ai)=ai*
对于 K的任意函数 fij：
v(fij(t1,…,ti))=f*ij(v(t1),… v(ti))
这里,ai* 和 f*ij分别是 ai和 fij在 I中的解释注：上述定义保证了赋值是相容的解释 I的赋值 v将由 v(x1),v(x2),… 完全确定
例子,A11(x1)
解释 I的 DI是整数集合,A11(x1)被解释为 a1大于 0。对于这个确定的解释 I，当赋予 x1不同的值时，上式有不同真值。
132
2-8形式化 一阶 谓词演算系统
注：赋值起到了进一步地真值指派作用，解释和赋值共同确定了
K中谓词公式的真值
定义 3：两个赋值 u,v是 i-等价的，如果对于任意 j不等于 i，
u(xj)=v(xj)
定义 4：设 A,B,C是 K的谓词公式,I是 K的一个解释。 I中赋值 v
满足 A，如果可由如下四种情形归纳证明 v满足 A：
1） v满足 A=Aij(t1,…,ti),当且仅当 A*ij(v(t1),… v(ti))真
2） v满足 A=┐B,当且仅当 v不满足 B
3） v满足 A=B→C,当且仅当 v满足 ┐ B或 v满足 C
4） v满足 A=(?xi)B，当且仅当任何 i-等价于 v的赋值均满足 B
注：上述定义是自洽的。对于任意 v和 A,v或者满足 A或者满足
┐ A，不可能同时满足或同时不满足。
133
2-8形式化 一阶 谓词演算系统
定义 4,K的谓词公式 A在解释 I下是 真 的，如果 I中每一赋值均满足 A； K的谓词公式 A在解释 I下是 假 的，如果 I中每一赋值均不满足 A
问题：对于特定解释 I：
是否可能存在即不真又不假的谓词公式？
是否可能存在即真又假的谓词公式？
命题 1：在 K的解释 I下，若 A→B 和 A真，则 B也真
命题 2：在 K的解释 I下,A真当且仅当 (?xi)A真,xi是任意变元
命题 3：在 K的解释 I下,A真当且仅当 (?x1)… (?xk)A真，
x1… xk是任意变元
注：命题 3意味着对 A中的自由变元增加全称量词，并不改变其真性（依照这里所定义的真）
134
2-8形式化 一阶 谓词演算系统
定义 5,K的谓词公式 A是重言式，如果 A是 L的重言式在 K中的一个代换实例
例子,A→(B→A) 代换为 (?xi)A→( (?xj)B→ (?xi)A)
命题 4,K的重言式在 K的任意解释下都是真的
定义 6,K的谓词公式 A称为封闭的，如果其中无自由变元
命题 5：若 A是 K的封闭谓词公式,I是 K的解释，则在 I下，或者 A
为真，或者 A为假
注：对于多数重要的系统，特别是数学系统，谓词公式 A通常中并不会出现自由变元
定义 7,K的谓词公式 A是 逻辑有效的,如果 A在 K的每一种解释下都是真的； A是 矛盾的,如果 A在 K的每一种解释下都是假的。
回顾：真、假、非真非假,重言,逻辑有效,矛盾解释、赋值、指派、封闭公式
135
2-8形式化 一阶 谓词演算系统
公理：设 A,B和 C是任意谓词公式，则以下为 K的公理
K1:（ A→ （ B→A ））
K2:（ A→ （ B→C ）） → （（ A→B ） → （ A→C ））
K3:（ ┐ A→┐B ） → （ B→A ）
K4,((?xi)A→A),xi 不在 A中自由出现
K4例子,(?xi)(?xi)A(xi)是否可以应用 K4？
(?xi)A(xj)是否可以应用 K4？
(?xi)A(f(xj))是否可以应用 K4？
K5,((?xi)A(xi)→A(t)),t 是 K的项，它对 A(xi)
中的 xi是 自由的
136
2-8形式化 一阶 谓词演算系统定义：设 A是 K的任意谓词公式，项 t对 A中的 xi是 自由的,如果 xi自由出现，且不在 A的任何一个（?xj）的辖域中，这里 xj
是在 t中出现的任意客体变元注：粗略地说,项 t对 A中的 xi是自由的，意味着 t可以对 A中的 xi的每一自由出现做代入，而不会引起与 A中量词的相互作用对任意谓词公式 A和任意变元 xi，无论 xi在 A中是否自由出现,xi对 A中的 xi是自由的
K5例子,xj对于 (?xi)A(xi,xj)中的 xi是否可用 K5？
xj对于 (?xi)(?xj)A(xi,xj)中的 xi是否可用 K5？
f(xj)对于 (?xi)A(xi,xj,xk)中的 xi是否可用 K5？
xi对于 (?xi)A(xi)中的 xi是否可用 K5？
137
2-8形式化 一阶 谓词演算系统
f(x1,x4),f(x2,x3),f(x1,x3)和 x4对于下式中的哪个变元是自由的，哪个变元不是自由的？
(?x1)(?x2)A21(x1,x2)→ (?x3)A22(x3,x1)
K6,(?xi)(A→B)→ （ A→(?xi)B），若 A不包含变元 xi的自由出现
K的演绎规则,1）分离规则，即从 A和（ A→B ），可以获得 B
2）全称概括规则（ UG）：由 A获得（?xi） A
注,K的公理模式和演绎规则包括了 L的公理模式和演绎规则，
增加的公理和规则对于涉及量词性质的演绎是必要的公理 K5以最一般的形式叙述。在应用中，我们将经常碰到
(?xi)A→A 这样的例子，这里 xi可以是也可以不是 A中自由出现的变元。若 xi在 A中自由出现，可把 A记作 A（ xi），因为 xi对
A(xi)中的 xi总是自由的，于是 K5成为 (?xi)A→A(xi) 。若 xi不在 A中自由出现，则 K4给出了变换的形式,(?xi)A→A
138
2-8形式化 一阶 谓词演算系统
定义 8,K中的一个 证明 是谓词公式的序列 A1,A2,…,An，
使得对每一个 Ai（ 1<=i<=n)，或者 Ai是 K的公理，或者
Ai是由序列中在前面的谓词公式用分离规则或全称概括规则推出的。 K的 定理 是某个证明序列中的最后一项。
命题 6,K1－ K6均是逻辑有效的
命题 7：若 K的谓词公式 A是重言式，则 A是 K的定理
注：逆命题不成立
在 K中，逻辑有效的概念相当于 L中真的概念。我们关注于系统 K基于逻辑有效性的可靠性、一致性和完备性
139
2-8形式化 一阶 谓词演算系统
命题 8（ K的可靠性定理 ）：若 K的谓词公式 A是 K的定理，则 A是逻辑有效的证明：归纳法，施归纳于定理 A的证明序列长度 n
奠基步：当 n＝ 1时,A是 K的公理，命题成立归纳步：假设 A有长度为 n(n>1)的证明，而 K的所有长度小于 n步的定理都是逻辑有效的。。。
命题 9（ K的一致性定理 ）,K是一致的，即不存在 K的谓词公式 A，
使得 A和 ┐ A都是 K的定理
命题 10（ K的完备性定理 ）：若 K的谓词公式 A是逻辑有效的，则
A是 K的定理
140
2-9模型和模态逻辑
系统 K要求推理是逻辑有效的，即在任意解释下是均保真的。此要求使 K具备充分的可靠性。但系统的可靠性和能力之间常存在内在的冲突（科学理论、软件系统等）。这促使人们重新审视逻辑有效性，尝试放宽对可靠性的限制以获得更强有力的系统。
逻辑有效性被定义为对于任何解释均为真，但通常情况下，并非每个解释都令我们感兴趣，甚至有些解释是不可形式定义的
（可形式定义的解释是可数的，而所有可能的解释是不可数的）
例子：如果我们所在的世界中，时间是单向流逝的，那么是否必要让我们的推理方法也适用于时间线封闭的世界？
如果确知日常世界可以由欧氏几何所精确地刻画，还是否必要让日常推理方法也适用于黎曼几何或罗巴切夫斯基几何世界？
可否扩展 K的公理集，在保证其可靠性的同时，使其功能更强？例如，将欧氏几何的公理和公设加入系统 K。 这就是形式系统的基本思想。
141
2-9模型和模态逻辑
定义 1：设 S是 K的谓词公式集合,S的一个解释（世界）称为 S的模型,如果 S中每个谓词公式在此解释下是真的
定义 2：若 S是一阶系统,S的一个模型是一个解释，在这个解释中,S的每个定理都是真的
定理 1：设 S是一阶系统,I是使 S的每个公理均为真且推理规则保真的解释，则 I是 S的一个模型
注：定义 1给出了公式集的模型的定义；定义 2给出了一阶系统的模型的定义。由模型的定义可知，任何一个解释都是一阶谓词系统 K的模型由定理 1，一个一阶系统的解释，只需使其所有公理真且推理规则保真，即可成为其模型
思考题：可否建构 现实有效系统,即 以 现实解释和所有可形式定义解释为模型的系统？如果可以，它与 K的区别？
142
2-9模型和模态逻辑
单世界和多世界我们的世界是所有可能世界中的最完美者－－－莱布尼茨量子力学的多世界（ multiverse）解释－－－ Everett
模态逻辑：关于可能世界（即解释）的逻辑
模态词
,读作可能,? p指命题 p在某个（或某些）解释中为真，
即在某个（或某些）可能世界中为真
：读作必然,?p指命题 p在所用可能的解释中均为真，即在所有可能世界中为真。
模态逻辑对于蕴含悖论的解决方案例子,A→(B→A) 与 S→P( S:如果太阳西升,P：有最大的质数 )
（ A→(B→A) ）与?（ S→P ）
143
2-9模型和模态逻辑
模态（命题）逻辑的重言式集合 S是古典命题逻辑重言式集合的超集，超集满足以下条件
1)?(p→ q)→ (?p→?q)? S
2) S在分离规则下封闭：若 A? S,A→ B? S,则 B? S
3) S在代入规则下封闭：若 A? S，则 A S，这里 A?是 A的代入特例
4) S在弱必然化规则下封闭：若 A是命题逻辑重言式，则
A? S
5) S在必然化规则下封闭：若 A? S，则?A? S
注：若一个模态逻辑系统满足 1)-4)，则称它为古典模态逻辑。
若一个模态系统满足 1)-3)和 5)，则称它为正规模态逻辑。
是否有必然化规则（记为 N），是正规系统区别于非正规系统的的主要标志。 N是说：如果一个公式是在某系统内是可证的，则它是逻辑必然的。
144
2-9模型和模态逻辑
命题模态逻辑系统 S5以代入规则（记为 US）和分离规则（记为
MP）作为推理规则
S5系统公理
M1(A2),? p?┐?┐p
M2(T),?p→p
M3(K),?(p→q)→(?p→?q)
M4(N),若 A可证，则有?A
M5(4),?p→p
M6(E),? p→ p
M7(A1),所有真值函项重言式
145
2-9模型和模态逻辑
例子：安瑟伦的上帝存在性本体论证明的 Descartes版本
,God could not be so complete if he weren?t,So he is.”
Descartes
扩展表述：
定义上帝为具有所有积极属性者，则上帝必存在证明：（反证法）假设上帝不存在，则我们可以设想一个 God*，
God*保有上帝的所有其他积极属性，除了需要额外设想 God*是存在的。 由于存在性是比虚无性积极的属性,所以 God*比上帝具有更多的积极属性，与前面对上帝的定义矛盾。故上帝存在。
Kant的批评：存在不应作为一个谓词
146
2-9模型和模态逻辑
例子：安瑟伦的上帝存在性本体论证明的 Hartshorne版本
,I believe you (i.e.,God) are that thing than which
nothing greater can be thought”
“But when the fool (i.e.,antitheist) hears me use the
phrase?something than which nothing greater can be
thought?,he understand what he hears…”
“So fool has to agree that the concept of something than
which nothing greater can be thought exists in his
understanding.” ---安瑟伦根据上面的论证安瑟伦假设可以理解 (understanding)的东西是可能存在的，即对应于可能模态。这样，安瑟伦给出了他的第一个公理 H1,? g，这里 g代表上帝存在这一命题,? g即上帝是可能存在的
147
2-9模型和模态逻辑
进一步，安瑟伦论证,something than which nothing
greater can be thought so truly exists that it is not
possible to think of it as not existing.”，由此获得公理 H2,g→?g。安瑟伦的理由是，如果上帝的存在仅仅是偶然的，我们就可以想像一个必然存在的上帝，在安瑟伦看来，后者显然比前者更伟大。所以如果上帝存在，则上帝的存在是必然的（公理 H2）
下面有公理 H1和 H2导出安瑟伦的结论：
由 M6，有 H3,? ┐ g→ ┐g
由排中律，有,(?g?┐?g)，由 M1，这等价于 H4：
(?g ┐g )
由 H3和 H4，可获得 H5,?g ┐g
由 H2，获得 ┐?g→┐g,即获得 H6,? ┐g→┐g
在 H6上应用 M4，获得 H7,?(? ┐g→┐g)
148
2-9模型和模态逻辑在 H7上应用 M3，获得 H8:( ┐g)→(?┐g)
由 H5和 H8，获得 H9,(?g)?(?┐g)
改写 H1，获得 H10,┐?┐ g
由 H9和 H10，获得?g，即上帝必然存在,Q.E.D
注：由必然模态词的含义,?g意味着上帝存在这一命题在所有可能的解释，也即所有可能的世界中都为真。
这样，在我们所身处的这个特殊的世界中，上帝必须也是存在的。
你的意见？
可能的反驳,H1？
,conceivable existence and possible existence
are not the same” －－－ Christopher Small
149
2-9模型和模态逻辑
,Logic is not the end of wisdom,it is the
beginning…”
anonymous
