《集合论与图论》第2讲1
第2讲一阶逻辑基础
内容提要
? 1. 量词、谓词、个体词、命题符号化
? 2. 合式公式、解释、永真式
? 3. 一阶逻辑等值式
? 4. 一阶逻辑推理规则
《集合论与图论》第2讲2
一阶逻辑的字母表
?个体常项: a, b, c, …, a
1
, b
1
, c
1
,…
?个体变项: x, y, z, …, x
1
, y
1
, z
1
,…
?函数符号: f, g, h, …, f
1
, g
1
, h
1
,…
?谓词符号: F, G, H, …, F
1
, G
1
, H
1
, …
?量词符号: ?, ?
?联结词符号: ?, ∧, ∨, →, ?
?括号与逗号: (, ), ，
《集合论与图论》第2讲3
谓词(predicate)
?谓词：表示性质、关系等；相当于句子
中的谓语。
?用大写英文字母F,G,H,…,后跟括号与变
元来表示。例如：
F(x): x是人。
G(x,y): x与y是兄弟。
? n元谓词：含有n个变元。例如：
F(x)是一元谓词，G(x,y)是二元谓词
《集合论与图论》第2讲4
量词(quantifier)
?全称(universal)量词: ?
“所有的”, “全部的”,…
?存在(existential)量词: ?
“有一些的”, “某些的”,…
?唯一(unique)存在量词: ?!
“恰好存在一个”
《集合论与图论》第2讲5
量词(举例)
?设：F(x)：x是自然数。G(x)：x是偶数。
H(x) ：x是奇数。I(x,y)：x=y。
?“有些自然数是偶数”。?x(F(x)∧G(x))
?“既有奇数又有偶数”。?xH(x)∧?yG(y)
?存在既奇又偶的数”。?x(H(x)∧G(x))
?“存在唯一的自然数0”。?!x(F(x)∧I(x,0))
《集合论与图论》第2讲6
个体常项(constant)
?表示具体的特定对象
?用小写英文字母a,b,c,…来表示
?例如：a:王大明，b:王小明，
G(x,y): x与y是兄弟,
“王大明与王小明是兄弟”: G(a,b)
《集合论与图论》第2讲7
个体变项(varible)
?表示不确定的泛指对象
?用小写英文字母x,y,z,…来表示
?例如：F(x): x是人。G(x): x是数。
“存在着人”: ?xF(x)
“仅有一人”: ?!xF(x)
“万物皆数”: ?xG(x)
《集合论与图论》第2讲8
合式公式（举例）
? ?x(F(x)∧?y(G(y)→H(x,y)))
? F(f(a,a),b)
?约定：省略多余括号
?最外层
?优先级递减：?, ?; ?;∧,∨; →,?
《集合论与图论》第2讲9
命题符号化
?个体域(scope): 个体词的取值范围, 缺省
(default)采用全总个体域.
?全总个体域: 世界上的万事万物
?特性谓词: 表示所关注的对象的性质
?两种模式:
?x(M(x)→G(x))
?x(M(x)∧G(x))
其中M(x)是特性谓词。
《集合论与图论》第2讲10
命题符号化(举例)
?例: “有些人是要死的”.
?解1: 采用全总个体域.
设: F(x): x是人; G(x):x是要死的.
原命题符号化成: ?x(F(x)∧G(x))
?解2: 采用全体人作为个体域.
设: G(x): x是要死的.
原命题符号化成: ?xG(x)
《集合论与图论》第2讲11
命题符号化(举例、续)
?例: “凡人都是要死的”.
?解1: 采用全总个体域.
设: F(x): x是人; G(x):x是要死的.
原命题符号化成: ?x(F(x)→G(x))
?解2: 采用全体人作为个体域.
设: G(x): x是要死的.
原命题符号化成: ?xG(x)
《集合论与图论》第2讲12
命题符号化(举例、续)
?例: “存在最小的自然数”。
解1: 设: F(x): x是自然数; G(x,y): x≤y;
原命题符号化成:
?x(F(x)∧?y(F(y)→G(x,y)))
解2: 采用全体自然数作为个体域.
设: G(x,y): x<y;
原命题符号化成: ?x?yG(x,y)
?注意量词顺序:
?y?xG(x,y): “没有最小的自然数”.
《集合论与图论》第2讲13
命题符号化(举例、续)
?例: “不存在最大的自然数”。
解: 设: F(x): x是自然数; G(x,y): x<y;
原命题符号化成:
??x(F(x)∧?y(F(y)→G(y,x)))
或: ?x(F(x)→?y(F(y)∧G(x,y)))
《集合论与图论》第2讲14
命题符号化(举例、续)
?例: “火车比汽车快”。
解: 设: F(x): x是火车; G(x): x是汽车;
H(x,y): x比y快
原命题符号化成:
?x(F(x)→?y(G(y)→H(x,y)))
或: ?x?y((F(x)∧G(y))→H(x,y))
《集合论与图论》第2讲15
命题符号化(举例、续)
?例: “有的汽车比火车快”。
解: 设: F(x): x是汽车; G(x): x是火车;
H(x,y): x比y快
原命题符号化成:
?x(F(x)∧?y(G(y)∧H(x,y)))
或: ?x?y(F(x)∧G(y)∧H(x,y))
《集合论与图论》第2讲16
命题符号化(举例、续)
?例: “有些病人相信所有的医生”。
解: 设: F(x): x是病人; G(x): x是医生;
H(x,y): x相信y
原命题符号化成:
?x(F(x)∧?y(G(y)→H(x,y)))
《集合论与图论》第2讲17
命题符号化(举例、续)
?例: “存在唯一的对象满足性质P”。
解: 设: P(x): x满足性质P
原命题符号化成:
?!xP(x)
或:
?x( P(x) ∧ ?y( P(y)→x=y ) )
《集合论与图论》第2讲18
合式公式中的变项
?量词辖域: 在?xA, ?xA中, A是量词的辖
域. 例如: ?x(F(x)∧?y(G(y)→H(x,y)))
?指导变项: 紧跟在量词后面的个体变项.
例如: ?x(F(x)∧?y(G(y)→H(x,y)))
?约束出现: 在辖域中与指导变项同名的变
项. 例如: ?x(F(x)∧?y(G(y)→H(x,y)))
?自由出现: 既非指导变项又非约束出现.
例如: ?y(G(y)→H(x,y))
《集合论与图论》第2讲19
合式公式中的变项(举例)
?H(x,y)∨?xF(x)∨?y(G(y)→H(x,y))
?x 与y 是指导变项
? x与y是约束出现
? x与y是自由出现
《集合论与图论》第2讲20
换名(rename)规则
?把某个指导变项和其量词辖域中所有同
名的约束出现, 都换成某个新的个体变项
符号.
?例如:
? ?x(A(x)∧B(x)) ??y(A(y)∧B(y))
? ?xA(x)∧?xB(x) ??yA(y)∧?zB(z)
? H(x,y)∨?xF(x)∨?y(G(y)→H(x,y))
? H(x,y)∨?zF(z)∨?u(G(u)→H(x,u))
《集合论与图论》第2讲21
代替(substitute)规则
?把某个自由变项的所有出现, 都换成某个
新的个体变项符号.
?例如:
? A(x)∧B(x) ? A(y)∧B(y)
? ?xA(x)∧B(x) ??xA(x)∧B(y)
? H(x,y)∨?xF(x)∨?y(G(y)→H(x,y))
? H(s,t)∨?xF(x)∨?y(G(y)→H(s,y))
《集合论与图论》第2讲22
闭式(closed form)
?闭式: 无自由出现的变项
?一般来说, 闭式表示的是命题, 例如
?F(a)
??xF(x)
?F(x)
??y(G(y)→H(x,y))
后两个不是闭式
《集合论与图论》第2讲23
解释(interpret)
?对一个合式公式的解释包括给出
?个体域
?谓词
?函数
?个体常项
的具体含义
《集合论与图论》第2讲24
解释(举例)
?F(f(a,a),b)
?解释1：个体域是全体自然数; a: 2;
b: 4; f(x,y)=x+y; F(x,y): x=y
原公式解释成: “2+2=4”。
?解释2：个体域是全体实数; a: 3;
b: 5; f(x,y)=x-y; F(x,y): x>y
原公式解释成: “3-3>5”。
《集合论与图论》第2讲25
一阶逻辑永真式(tautology)
?永真式:在各种解释下取值均为真(逻辑有
效式)
?命题逻辑永真式: 在各种赋值下取值均为真
(重言式)
?永假式:在各种解释下取值均为假(矛盾式)
?命题逻辑永假式: 在各种赋值下取值均为真
(矛盾式)
?可满足式：非永假式
《集合论与图论》第2讲26
一阶逻辑等值式(定义)
?等值：A?B
?读作：A等值于B
?含义：A与B在各种解释下取值均相等
?A?B 当且仅当A?B是永真式
?例如：??xF(x)??x?F(x)
F
?F
《集合论与图论》第2讲27
一阶逻辑等值式(来源)
?命题逻辑等值式的代换实例
?与量词有关的
?有限个体域量词消去
?量词否定
?量词辖域收缩与扩张
?量词分配
?与变项命名有关的
?换名规则
?代替规则
《集合论与图论》第2讲28
代换实例
?在命题逻辑等值式中, 代入一阶逻辑公式
所得到的式子, 称为原来公式的代换实例.
?例1：A???A, 令A=?xF(x), 得到
?xF(x)????xF(x)
?例2：A→B??A∨B,令A=F(x),
B=G(y), 得到
F(x)→G(y)??F(x)∨G(y)
《集合论与图论》第2讲29
有限个体域上消去量词
?设个体域为有限集D={a
1
, a
2
,…, a
n
}, 则
?xA(x)?A(a
1
)∧A(a
2
)∧…∧A(a
n
)
?xA(x)?A(a
1
)∨A(a
2
)∨…∨A(a
n
)
?例: 个体域D={a,b,c}, 则?x?yF(x,y)
??x (F(x,a)∧F(x,b)∧F(x,c))
? (F(a,a)∧F(a,b)∧F(a,c))∨
(F(b,a)∧F(b,b)∧F(b,c))∨
(F(c,a)∧F(c,b)∧F(c,c))
《集合论与图论》第2讲30
量词否定等值式
???xA(x)??x?A(x)
???xA(x)??x?A(x)
《集合论与图论》第2讲31
量词否定等值式(举例)
?
??ε ?N ?n ( n>N→|a
n
-a|<ε )
? a
1
,a
2
,a
3
,…,a
N
,a
N+1
,a
N+2
,
…
,a
n
,…
?
? ?
aa
n
n
=
∞→
lim
aa
n
n
≠
∞→
lim
a
εε
《集合论与图论》第2讲32
量词否定等值式(举例、续)
? ??
???ε ?N ?n ( n>N →|a
n
-a|<ε )
? ?ε??N ?n ( n>N →|a
n
-a|<ε )
? ?ε ?N??n ( n>N →|a
n
-a|<ε )
? ?ε ?N ?n?( n>N →|a
n
-a|<ε )
? ?ε ?N ?n?( ?n>N∨|a
n
-a|<ε )
? ?ε ?N ?n ( n>N ∧? |a
n
-a|<ε )
? ?ε ?N ?n ( n>N ∧|a
n
-a|≥ε )
aa
n
n
≠
∞→
lim aa
n
n
=
∞→
lim
《集合论与图论》第2讲33
量词辖域收缩与扩张(?)
??x(A(x)∨B) ??xA(x)∨B
??x(A(x)∧B) ??xA(x)∧B
??x(A(x)→B) ? ?xA(x)→B
??x(B→A(x)) ? B→?xA(x)
?说明: B中不含x的出现
?例1: ?x(F(x)∨G(y)) ??xF(x)∨G(y)
?例2: ?x?y(F(x)∧G(y)) ??x(F(x)∧?yG(y))
??xF(x)∧?yG(y)
《集合论与图论》第2讲34
量词辖域收缩与扩张(?、续)
? ?x(A(x)→B) ? ?xA(x)→B
证明: ?x(A(x)→B)
??x(?A(x)∨B) ? ?x?A(x)∨B
? ??xA(x)∨B ? ?xA(x)→B
? ?x(B→A(x)) ? B→?xA(x)
证明: ?x(B→A(x))
??x(?B∨A(x)) ? ?B∨?xA(x)
? ?B∨?xA(x) ? B→?xA(x)
《集合论与图论》第2讲35
量词辖域收缩与扩张(?)
??x(A(x)∨B) ??xA(x)∨B
??x(A(x)∧B) ??xA(x)∧B
??x(A(x)→B) ? ?xA(x)→B
??x(B→A(x)) ? B→?xA(x)
?说明: B中不含x的出现
?例1: ?x(F(x)∨G(y)) ??xF(x)∨G(y)
?例2: ?x?y(F(x)∧G(y)) ??x(F(x)∧?yG(y))
??xF(x)∧?yG(y)
《集合论与图论》第2讲36
量词辖域收缩与扩张(?、续)
? ?x(A(x)→B) ? ?xA(x)→B
证明: ?x(A(x)→B)
??x(?A(x)∨B) ? ?x?A(x)∨B
? ??xA(x)∨B ??xA(x)→B
? ?x(B→A(x)) ? B→?xA(x)
证明: ?x(B→A(x))
??x(?B∨A(x)) ? ?B∨?xA(x)
? ?B∨?xA(x) ? B→?xA(x)
《集合论与图论》第2讲37
量词分配
??x(A(x)∧B(x)) ? ?xA(x)∧?xB(x)
??x(A(x)∨B(x)) ? ?xA(x)∨?xB(x)
《集合论与图论》第2讲38
量词分配(反例)
??x(A(x)∨B(x)) ? ?xA(x)∨?xB(x)
??x(A(x)∨B(x)) ? ?xA(x)∨?xB(x)
个体域为全体自然数; A(x): x是偶数
B(x): x是奇数; 左?1, 右?0
??x(A(x)∧B(x)) ? ?xA(x)∧?xB(x)
??x(A(x)∧B(x)) ? ?xA(x)∧?xB(x)
个体域为全体自然数; A(x): x是偶数
B(x): x是奇数; 左?0, 右?1
《集合论与图论》第2讲39
一阶逻辑推理定律(定义)
?推出：A?B
?读作：A推出B
?含义：A为真时, B也为真
?A?B当且仅当A→B是永真式
?例如：?xF(x) ? ?xF(x)
F
《集合论与图论》第2讲40
一阶逻辑推理定律(来源)
?命题逻辑推理定律的代换实例
?基本等值式生成的推理定律
?其他的一阶逻辑推理定律
?xA(x)∨?xB(x) ? ?x(A(x)∨B(x))
?x(A(x)∧B(x)) ? ?xA(x)∧?xB(x)
?x(A(x)→B(x)) ? ?xA(x)→?xB(x)
?x(A(x)→B(x)) ? ?xA(x)→?xB(x)
M
《集合论与图论》第2讲41
一阶逻辑推理定律(举例)
?命题逻辑推理定律的代换实例
例如: 假言推理规则:
(A→B )∧A?B
代入A=F(a), B=G(a), 得到
(F(a)→G(a))∧F(a)?G(a)
《集合论与图论》第2讲42
一阶逻辑推理定律(举例、续)
?基本等值式生成的推理定律
即由A?B 可得A?B 和B?A
例如: 量词分配等值式:
?x(A(x)∧B(x)) ??xA(x)∧?xB(x)
可得
?x(A(x)∧B(x)) ??xA(x)∧?xB(x)
?xA(x)∧?xB(x) ??x(A(x)∧B(x))
《集合论与图论》第2讲43
总结
?一阶逻辑等值式（6组）
?有限个体域量词消去；
?量词否定；
?量词辖域收缩与扩张；
?量词分配；
?换名规则；
?代替规则
?一阶逻辑推理定律
《集合论与图论》第2讲44
习题
?1. 设个体域D={a,b,c}, 消去下列各式的
量词：
(1) ?x?y(F(x)∧G(x))
(2) ?x(F(x,y)→?yG(y))
?2. 证明等值式:
?xF(x)∨??xG(x)??x?y(F(x)∨?G(y))
