1
第 2章 一阶逻辑
?一阶逻辑基本概念, 命题符号化
?一阶逻辑公式, 解释及分类
?一阶逻辑等值式, 前束范式
?一阶逻辑推理理论
2
2.1 一阶逻辑基本概念
? 个体词
? 谓词
? 量词
? 一阶逻辑中命题符号化
3
基本概念 —— 个体词、谓词、量词
个体词 （ 个体 ）, 所研究对象中可以独立存在的具
体或抽象的客体
个体常项,具体的事务, 用 a,b,c表示
个体变项,抽象的事物, 用 x,y,z表示
个体域, 个体变项的取值范围
有限个体域, 如 {a,b,c},{1,2}
无限个体域, 如 N,Z,R,…
全总个体域, 宇宙间一切事物组成
4
基本概念 (续 )
谓词, 表示个体词性质或相互之间关系的词
谓词常项, F,… 是人, F(a),a是人
谓词变项, F,… 具有性质 F,F(x),x具有性质 F
一元谓词, 表示事物的性质
多元谓词 (n元谓词,n?2),表示事物之间的关系
如 L(x,y),x与 y有关系 L,L(x,y),x?y,…
0元谓词, 不含个体变项的谓词,即命题常项或命
题变项
5
基本概念 (续 )
量词, 表示数量的词
全称量词 ?,表示任意的,所有的,一切的等
如 ?x 表示对个体域中所有的 x
存在量词 ?,表示存在,有的,至少有一个等
如 ?x 表示在个体域中存在 x
6
一阶逻辑中命题符号化
例 1 用 0元谓词将命题符号化
要求：先将它们在命题逻辑中符号化, 再在一阶
逻辑中符号化
(1) 墨西哥位于南美洲
在命题逻辑中,设 p,墨西哥位于南美洲
符号化为 p,这是真命题
在一阶逻辑中,设 a：墨西哥, F(x),x位于南美洲
符号化为 F(a)
7
例 1(续 )
2
2
3
3
)3()2( GF ?
(2) 是无理数仅当 是有理数
在命题逻辑中,设 p,是无理数, q,是有理数,
符号化为 p ? q,这是假命题
在一阶逻辑中,设 F(x),x是无理数,G(x),x是有理
数符号化为
(3) 如果 2>3,则 3<4
在命题逻辑中,设 p,2>3,q,3<4,
符号化为 p?q,这是真命题
在一阶逻辑中,设 F(x,y),x>y,G(x,y),x<y,
符号化为 F(2,3)?G(3,4)
2
2 3
)3()2( GF ?
8
一阶逻辑中命题符号化 (续 )
例 2 在一阶逻辑中将下面命题符号化
(1) 人都爱美 ; (2) 有人用左手写字
分别取 (a) D为人类集合,(b) D为全总个体域,
解,(a) (1) 设 G(x),x爱美,符号化为 ?x G(x)
(2) 设 G(x),x用左手写字,符号化为 ?x G(x)
(b) 设 F(x),x为人, G(x)：同 (a)中
(1) ?x (F(x)?G(x))
(2) ? x (F(x)?G(x))
这是两个基本公式,注意这两个基本公式的使用,
9
一阶逻辑中命题符号化 (续 )
例 3 在一阶逻辑中将下面命题符号化
(1) 正数都大于负数
(2) 有的无理数大于有的有理数
解 注意, 题目中没给个体域,一律用全总个体域
(1) 令 F(x),x为正数,G(y),y为负数,L(x,y),x>y
?x(F(x)??y(G(y)?L(x,y))) 或
?x?y(F(x)?G(y)?L(x,y)) 两者等值
(2) 令 F(x),x是无理数,G(y),y是有理数,
L(x,y),x>y
?x(F(x)??y(G(y)?L(x,y)))
或 ?x?y(F(x)?G(y)?L(x,y)) 两者等值
10
一阶逻辑中命题符号化 (续 )
几点注意,
1元谓词与多元谓词的区分
无特别要求, 用全总个体域
量词顺序一般不要随便颠倒
否定式的使用
思考,
① 没有不呼吸的人
② 不是所有的人都喜欢吃糖
③ 不是所有的火车都比所有的汽车快
以上命题应如何符号化？
11
2.2 一阶逻辑公式及解释
?字母表
?合式公式 (简称公式 )
?个体变项的自由出现和约束出现
?解释
?永真式 （ 逻辑有效式 ）
?矛盾式 （ 永假式 ）
?可满足式
12
字母表
定义 字母表 包含下述符号,
(1) 个体常项,a,b,c,…,ai,bi,ci,…,i ?1
(2) 个体变项,x,y,z,…,xi,yi,zi,…,i ?1
(3) 函数符号,f,g,h,…,fi,gi,hi,…,i ?1
(4) 谓词符号,F,G,H,…,Fi,Gi,Hi,…,i ?1
(5) 量词符号,?,?
(6) 联结词符号,?,?,?,?,?
(7) 括号与逗号,(,),,
13
项
定义 项 的定义如下,
(1) 个体常项和个体变项是项,
(2) 若 ?(x1,x2,…,xn)是任意的 n元函数, t1,t2,…,tn
是任意的 n个项, 则 ?(t1,t2,…,tn) 是项,
(3) 所有的项都是有限次使用 (1),(2) 得到的,
其实,个体常项、变项是项，由它们构成的 n元函数
和复合函数还是项
14
原子公式
定义 设 R(x1,x2,…,xn)是任意的 n元谓词, t1,t2,…,tn
是任意的 n个项, 则称 R(t1,t2,…,tn)是 原子公式,
其实, 原子公式是由项组成的 n元谓词,
例如,F(x,y),F(f(x1,x2),g(x3,x4))等均为原子公式
15
合式公式
定义 合式公式 （ 简称 公式 ） 定义如下,
(1) 原子公式是合式公式,
(2) 若 A是合式公式, 则 (?A)也是合式公式
(3) 若 A,B是合式公式, 则 (A?B),(A?B),(A?B),
(A?B)也是合式公式
(4) 若 A是合式公式, 则 ?xA,?xA也是合式公式
(5) 只有有限次地应用 (1)~(4)形成的符号串
才是合式公式,
请举出几个合式公式的例子,
16
个体变项的自由出现与约束出现
定义 在公式 ?xA和 ?xA中, 称 x为 指导变元, A为相
应量词的 辖域, 在 ?x和 ?x的 辖域 中, x的所有出现都
称为 约束出现, A中不是约束出现的其他变项均称
为是 自由出现的,
例如,在公式 ?x(F(x,y)?G(x,z)) 中,
A=(F(x,y)?G(x,z))为 ?x的辖域,
x为指导变元,A中 x的两次出现均为约束出现,
y与 z均为自由出现,
闭式, 不含自由出现的个体变项的公式,
17
公式的解释与分类
给定公式 A=?x(F(x)?G(x))
成真解释, 个体域 N,F(x),x>2,G(x),x>1
代入得 A=?x(x>2?x>1) 真命题
成假解释, 个体域 N,F(x),x>1,G(x),x>2
代入得 A=?x(x>1?x>2) 假命题
问, ?xF(x)??x?F(x) 有成真解释吗？
?xF(x)??x?F(x) 有成假解释吗？
18
解释
},,,{ 1 ?? iaa
}1,|{ ?nif ni
}1,|{ ?niF ni
n
i
n
ii Ffa,,
ia
定义 解释 I由下面 4部分组成,
(a) 非空个体域 DI
(b) DI中一些特定元素的集合
(c) DI上特定函数集合
(d) DI上特定谓词的集合
说明,
在解释的定义中引进了元语言符号,如 等
被解释的公式 A中的个体变项均取值于 DI
若 A中含个体常项 ai，就解释成
19
解释 (续 )
n
iF
3
2F
),,(2 zyxF
),,(2 zyxF
为第 i 个 n元谓词, 例如, 表示第 2 个 3元谓词,
它可能以 的形式出现在解释中, 公式 A中
若出现 F2(x,y,z) 就解释成
被解释的公式不一定全部包含解释中的 4部分,
闭式在任何解释下都是命题,
注意不是闭式的公式在某些解释下也可能是命题,
21fn
if
),(,),( 1221 yxgyxyxf ??
),(1 yxf
),(1 yxg
为第 i 个 n元函数, 例如, 表示第一个二元函数,
它出现在解释中, 可能是
=2xy 等, 一旦公式中出现 f1(x,y) 就解释成,
出现 g1(x,y) 就解释成
20
公式的分类
永真式 （ 逻辑有效式 ）,无成假赋值
矛盾式 （ 永假式 ）,无成真赋值
可满足式,至少有一个成真赋值
几点说明,
永真式为可满足式, 但反之不真
判断公式是否为永真式不是易事
某些代换实例可判公式类型
21
代换实例
定义 设 A0是含命题变项 p1,p2,…,pn的命题公式,
A1,A2,…,An是 n个谓词公式, 用 Ai处处代替 A0中的 pi
(1?i?n), 所得公式 A称为 A0的 代换实例,
例如,
F(x)?G(x),?xF(x)??yG(y) 等都是 p?q的换实例,
?x(F(x)?G(x)) 等不是 p?q 的代换实例,
定理 重言式的代换实例都是永真式，矛盾式的代
换实例都是矛盾式,
22
代换实例 (续 )
例 1 给定解释 I 如下,
(a) 个体域 D=N
(b)
(c)
(d) 谓词
说明下列公式在 I 下的涵义,并讨论真值
(1) ?xF(g(x,a),x)
2?a
xyyxgyxyxf ??? ),(,),(
yxyxF ?:),(
?x(2x=x) 假命题
(2) ?x?y(F(f(x,a),y)?F(f(y,a),x))
?x?y(x+2=y?y+2=x) 假命题
23
例 1(续 )
(3) ?x?y?zF(f(x,y),z)
两点说明,
5个小题都是闭式,在 I下全是命题
(3)与 (5)说明，量词顺序不能随意改变
(5) ?x?y?zF(f(y,z),x)
?x?y?z (y+z=x) 假命题
(4) ?xF(f(x,x),g(x,x))
?x(2x=x2) 真命题
?x?y?z (x+y=z) 真命题
24
代换实例 (续 )
例 2 证明下面公式既不是永真式, 也不是矛盾式
(1) ?x(F(x) ?G(x))
(2) ?x(F(x)?G(x))
(3) ?x?y(F(x)?G(y)?H(x,y))
不难对每一个公式给出一个成假解释和一个成真
解释,从而证明它们既不是永真式，也不是矛盾
式,
第 2章 一阶逻辑
?一阶逻辑基本概念, 命题符号化
?一阶逻辑公式, 解释及分类
?一阶逻辑等值式, 前束范式
?一阶逻辑推理理论
2
2.1 一阶逻辑基本概念
? 个体词
? 谓词
? 量词
? 一阶逻辑中命题符号化
3
基本概念 —— 个体词、谓词、量词
个体词 （ 个体 ）, 所研究对象中可以独立存在的具
体或抽象的客体
个体常项,具体的事务, 用 a,b,c表示
个体变项,抽象的事物, 用 x,y,z表示
个体域, 个体变项的取值范围
有限个体域, 如 {a,b,c},{1,2}
无限个体域, 如 N,Z,R,…
全总个体域, 宇宙间一切事物组成
4
基本概念 (续 )
谓词, 表示个体词性质或相互之间关系的词
谓词常项, F,… 是人, F(a),a是人
谓词变项, F,… 具有性质 F,F(x),x具有性质 F
一元谓词, 表示事物的性质
多元谓词 (n元谓词,n?2),表示事物之间的关系
如 L(x,y),x与 y有关系 L,L(x,y),x?y,…
0元谓词, 不含个体变项的谓词,即命题常项或命
题变项
5
基本概念 (续 )
量词, 表示数量的词
全称量词 ?,表示任意的,所有的,一切的等
如 ?x 表示对个体域中所有的 x
存在量词 ?,表示存在,有的,至少有一个等
如 ?x 表示在个体域中存在 x
6
一阶逻辑中命题符号化
例 1 用 0元谓词将命题符号化
要求：先将它们在命题逻辑中符号化, 再在一阶
逻辑中符号化
(1) 墨西哥位于南美洲
在命题逻辑中,设 p,墨西哥位于南美洲
符号化为 p,这是真命题
在一阶逻辑中,设 a：墨西哥, F(x),x位于南美洲
符号化为 F(a)
7
例 1(续 )
2
2
3
3
)3()2( GF ?
(2) 是无理数仅当 是有理数
在命题逻辑中,设 p,是无理数, q,是有理数,
符号化为 p ? q,这是假命题
在一阶逻辑中,设 F(x),x是无理数,G(x),x是有理
数符号化为
(3) 如果 2>3,则 3<4
在命题逻辑中,设 p,2>3,q,3<4,
符号化为 p?q,这是真命题
在一阶逻辑中,设 F(x,y),x>y,G(x,y),x<y,
符号化为 F(2,3)?G(3,4)
2
2 3
)3()2( GF ?
8
一阶逻辑中命题符号化 (续 )
例 2 在一阶逻辑中将下面命题符号化
(1) 人都爱美 ; (2) 有人用左手写字
分别取 (a) D为人类集合,(b) D为全总个体域,
解,(a) (1) 设 G(x),x爱美,符号化为 ?x G(x)
(2) 设 G(x),x用左手写字,符号化为 ?x G(x)
(b) 设 F(x),x为人, G(x)：同 (a)中
(1) ?x (F(x)?G(x))
(2) ? x (F(x)?G(x))
这是两个基本公式,注意这两个基本公式的使用,
9
一阶逻辑中命题符号化 (续 )
例 3 在一阶逻辑中将下面命题符号化
(1) 正数都大于负数
(2) 有的无理数大于有的有理数
解 注意, 题目中没给个体域,一律用全总个体域
(1) 令 F(x),x为正数,G(y),y为负数,L(x,y),x>y
?x(F(x)??y(G(y)?L(x,y))) 或
?x?y(F(x)?G(y)?L(x,y)) 两者等值
(2) 令 F(x),x是无理数,G(y),y是有理数,
L(x,y),x>y
?x(F(x)??y(G(y)?L(x,y)))
或 ?x?y(F(x)?G(y)?L(x,y)) 两者等值
10
一阶逻辑中命题符号化 (续 )
几点注意,
1元谓词与多元谓词的区分
无特别要求, 用全总个体域
量词顺序一般不要随便颠倒
否定式的使用
思考,
① 没有不呼吸的人
② 不是所有的人都喜欢吃糖
③ 不是所有的火车都比所有的汽车快
以上命题应如何符号化？
11
2.2 一阶逻辑公式及解释
?字母表
?合式公式 (简称公式 )
?个体变项的自由出现和约束出现
?解释
?永真式 （ 逻辑有效式 ）
?矛盾式 （ 永假式 ）
?可满足式
12
字母表
定义 字母表 包含下述符号,
(1) 个体常项,a,b,c,…,ai,bi,ci,…,i ?1
(2) 个体变项,x,y,z,…,xi,yi,zi,…,i ?1
(3) 函数符号,f,g,h,…,fi,gi,hi,…,i ?1
(4) 谓词符号,F,G,H,…,Fi,Gi,Hi,…,i ?1
(5) 量词符号,?,?
(6) 联结词符号,?,?,?,?,?
(7) 括号与逗号,(,),,
13
项
定义 项 的定义如下,
(1) 个体常项和个体变项是项,
(2) 若 ?(x1,x2,…,xn)是任意的 n元函数, t1,t2,…,tn
是任意的 n个项, 则 ?(t1,t2,…,tn) 是项,
(3) 所有的项都是有限次使用 (1),(2) 得到的,
其实,个体常项、变项是项，由它们构成的 n元函数
和复合函数还是项
14
原子公式
定义 设 R(x1,x2,…,xn)是任意的 n元谓词, t1,t2,…,tn
是任意的 n个项, 则称 R(t1,t2,…,tn)是 原子公式,
其实, 原子公式是由项组成的 n元谓词,
例如,F(x,y),F(f(x1,x2),g(x3,x4))等均为原子公式
15
合式公式
定义 合式公式 （ 简称 公式 ） 定义如下,
(1) 原子公式是合式公式,
(2) 若 A是合式公式, 则 (?A)也是合式公式
(3) 若 A,B是合式公式, 则 (A?B),(A?B),(A?B),
(A?B)也是合式公式
(4) 若 A是合式公式, 则 ?xA,?xA也是合式公式
(5) 只有有限次地应用 (1)~(4)形成的符号串
才是合式公式,
请举出几个合式公式的例子,
16
个体变项的自由出现与约束出现
定义 在公式 ?xA和 ?xA中, 称 x为 指导变元, A为相
应量词的 辖域, 在 ?x和 ?x的 辖域 中, x的所有出现都
称为 约束出现, A中不是约束出现的其他变项均称
为是 自由出现的,
例如,在公式 ?x(F(x,y)?G(x,z)) 中,
A=(F(x,y)?G(x,z))为 ?x的辖域,
x为指导变元,A中 x的两次出现均为约束出现,
y与 z均为自由出现,
闭式, 不含自由出现的个体变项的公式,
17
公式的解释与分类
给定公式 A=?x(F(x)?G(x))
成真解释, 个体域 N,F(x),x>2,G(x),x>1
代入得 A=?x(x>2?x>1) 真命题
成假解释, 个体域 N,F(x),x>1,G(x),x>2
代入得 A=?x(x>1?x>2) 假命题
问, ?xF(x)??x?F(x) 有成真解释吗？
?xF(x)??x?F(x) 有成假解释吗？
18
解释
},,,{ 1 ?? iaa
}1,|{ ?nif ni
}1,|{ ?niF ni
n
i
n
ii Ffa,,
ia
定义 解释 I由下面 4部分组成,
(a) 非空个体域 DI
(b) DI中一些特定元素的集合
(c) DI上特定函数集合
(d) DI上特定谓词的集合
说明,
在解释的定义中引进了元语言符号,如 等
被解释的公式 A中的个体变项均取值于 DI
若 A中含个体常项 ai，就解释成
19
解释 (续 )
n
iF
3
2F
),,(2 zyxF
),,(2 zyxF
为第 i 个 n元谓词, 例如, 表示第 2 个 3元谓词,
它可能以 的形式出现在解释中, 公式 A中
若出现 F2(x,y,z) 就解释成
被解释的公式不一定全部包含解释中的 4部分,
闭式在任何解释下都是命题,
注意不是闭式的公式在某些解释下也可能是命题,
21fn
if
),(,),( 1221 yxgyxyxf ??
),(1 yxf
),(1 yxg
为第 i 个 n元函数, 例如, 表示第一个二元函数,
它出现在解释中, 可能是
=2xy 等, 一旦公式中出现 f1(x,y) 就解释成,
出现 g1(x,y) 就解释成
20
公式的分类
永真式 （ 逻辑有效式 ）,无成假赋值
矛盾式 （ 永假式 ）,无成真赋值
可满足式,至少有一个成真赋值
几点说明,
永真式为可满足式, 但反之不真
判断公式是否为永真式不是易事
某些代换实例可判公式类型
21
代换实例
定义 设 A0是含命题变项 p1,p2,…,pn的命题公式,
A1,A2,…,An是 n个谓词公式, 用 Ai处处代替 A0中的 pi
(1?i?n), 所得公式 A称为 A0的 代换实例,
例如,
F(x)?G(x),?xF(x)??yG(y) 等都是 p?q的换实例,
?x(F(x)?G(x)) 等不是 p?q 的代换实例,
定理 重言式的代换实例都是永真式，矛盾式的代
换实例都是矛盾式,
22
代换实例 (续 )
例 1 给定解释 I 如下,
(a) 个体域 D=N
(b)
(c)
(d) 谓词
说明下列公式在 I 下的涵义,并讨论真值
(1) ?xF(g(x,a),x)
2?a
xyyxgyxyxf ??? ),(,),(
yxyxF ?:),(
?x(2x=x) 假命题
(2) ?x?y(F(f(x,a),y)?F(f(y,a),x))
?x?y(x+2=y?y+2=x) 假命题
23
例 1(续 )
(3) ?x?y?zF(f(x,y),z)
两点说明,
5个小题都是闭式,在 I下全是命题
(3)与 (5)说明，量词顺序不能随意改变
(5) ?x?y?zF(f(y,z),x)
?x?y?z (y+z=x) 假命题
(4) ?xF(f(x,x),g(x,x))
?x(2x=x2) 真命题
?x?y?z (x+y=z) 真命题
24
代换实例 (续 )
例 2 证明下面公式既不是永真式, 也不是矛盾式
(1) ?x(F(x) ?G(x))
(2) ?x(F(x)?G(x))
(3) ?x?y(F(x)?G(y)?H(x,y))
不难对每一个公式给出一个成假解释和一个成真
解释,从而证明它们既不是永真式，也不是矛盾
式,
