5
谓词逻
辑
命题逻辑研究命题与命题的逻辑关系,它的基本研究单位是原子命题。在命题演算
中,原子命题是最小的单位,不能再进行分割。这样处理原子命题对研究命题间的关系来
说是合适的。但是,原子命题不考虑命题内在的结构和逻辑关系,这就使人类的很多思维
过程在命题逻辑中表达不出来。这给推理带来了很大的局限性,因此,本章引入谓词逻
辑,介绍关于谓词逻辑的相关概念和定理,用来解决实际问题。
例如,逻辑学中著名的三段论是由一个大前提、一个小前提推出结论的方法。经典的
苏格拉底三段论是:“ 凡是人都是要死的,苏格拉底是人,所以苏格拉底是要死的。另(”) 有
推论“所有自然数都是有理数,100 是自然数,所以,100 是有理数。显(”) 然,这些都是正确的
推理,但在命题逻辑中却无法得到证明。因为,三段论中每一句都是一个原子命题,分别
用P,Q,
R
来表示。这样,三段论方法用符号表示应为:P,Q.R,即P∧Q.R,亦即
P
∧Q→R.1 。但在命题逻辑中,P∧Q→
R
显然不是重言式。出现问题的原因在于,三段
论中,结论
R
与前提P,
Q
的内在联系不可能在命题逻辑中表示出来。
下面再看两个原子命题:张三是共青团员;李四是共青团员。在命题逻辑中,这两个
命题分别对“张三”和“李四”这两个特定的人做出了判断,所以它们可能有不同的真值,需
要用两个不同的字母表示。但这样一来便掩盖了这两个命题都表示“…… 是共青团员”这
个共同的本质属性。
为了克服命题逻辑的局限性,我们在命题逻辑的基础上引入谓词逻辑。谓词逻辑将
进一步揭示命题之间的内在联系和逻辑关系。
本章主要介绍谓词逻辑的基本内容,通过本章学习,读者将掌握以下内容:
(1)个体、谓词和量词等基本谓词逻辑的概念;
(2)谓词公式的定义、符号化、约束与替换、解释和类型;
(3)谓词公式的逻辑等值的定义和基本的逻辑等值式;
(4)谓词公式的前束范式的定义和计算;
(5)谓词公式的逻辑蕴涵和逻辑蕴涵式;
(6)谓词逻辑的推理规则和自然推理系统。
5.谓词逻辑的相关概念
1
5.1
个体词与谓词
1.
定义5.1.1
个体词是研究对象中不依赖人的主观而独立存在的具体的或抽象的客
142
离散数学
观实体。
个体可以是具体的事物,也可是抽象的概念,例如:3、中国、计算机、大学生、物质等。
具体或特定客体的个体词称为个体常项或个体常元,一般用小写英文
字母a,c,一般用小写英文字母
定义5.1.2
b,…表示。抽象或泛指个体词称为个体变项或个体变元,
x,y,z,…表示。个体变元的取值范围称为个体域或论域,个体域可以是有限集合,也可
以是无限集合。特别地,一个特殊的个体域,由宇宙间一切事物和概念构成的集合,称为
全总个体域。一般情况下,如果没有特别说明,个体的取值范围为全总个体域。当给定个
体域后,个体常元为该个体域中的一个确定的元素,个体变元则可取该个体域中的任一
元素。
定义5.1.3
用来刻画个体词的性质或个体词之间关系的词称为谓词。
一般来说,“
x
是A”类型的命题可以用A(x)表达。对于“
x
大于y”这种两个个体之
y),
间关系的命题,可表达为B(x,这里
B
表示“…… 大于……” 谓词。我们把A(x)称为
一元谓词,B(y) C(y,称为三元谓词, 通常把二元及其
x,称为二元谓词,x,z) 以此类推,
以上谓词称作多元谓词。
显然,才成为一个命题。
n
元谓词不是命题。只有当个体变元用特定的个体替代时,
但个体变元的取值范围对命题的真值有极大影响。例如,用F(x)表示
x
是大学生,当取
值范围限定为某大学的全体学生时,F(x)是真的,但当取值范围限定为某中学的所有学
生时,则F(x)是假的。因此,在谓词逻辑中,我们要指定个体的取值范围。
例5.1
1.指出下列命题中的谓词。
(1)张三是大学生。
(2)3大于5。
在上述例子中,张三、3、5都是个体,而“…… 是大学生”“…… 大于……” 是谓词。其
中,“…… 是大学生”是刻画个体张三性质的谓词,“…… 大于……” 是刻画个体3和5之间
关系的谓词。
显然,有了个体和谓词的概念之后,可以进一步刻画命题的内在结构和命题之间的关
系。例如在命题逻辑中,“张三是大学生”和“李四是大学生”之间的关系是无法表达的,现
在可以用谓词“…… 是大学生”及个体“张三”“李四”刻画;再如,“张三和李四是表兄弟”,
在命题逻辑中也是无法刻画其内在结构的,现在可用谓词“…… 和…… 是表兄弟”及个体
“张三”“李四”刻画之。
命题变元是真值不确定的陈述句,反映在上述结构中,由个体或谓词不确定来体现。
例5.2
将下列命题在谓词逻辑中符号化,并讨论它们的真值:
1.
(1)只有4是素数,8才是素数;
(2)如果1小于2,则5小于4。
解(x)
x
是素数;b:8。(中的命题符号化为谓词的蕴涵式:
1)设谓词G(:a:4;1)
G(→G(所以,(1)中的命题为真。
a)b)。由于此蕴涵式的前件为假
,
x,y)a:1;c:5;
(2)设谓词
H
(:
x
小于y;b:2;d:4。(2)中的命题符号化为谓词
的蕴涵式:
H
(a,b)c,后件为假, 2)
题为假。
→
H
(d)。由于此蕴涵式的前件为真, 所以,(中的命
第5章谓词逻辑
143
例5.3
将下列命题在谓词逻辑中符号化:
1.
(1)李明是学生;
(2)张亮比陈华高。
Q(
解
表示
(1
。
)“ 李明”是个体,用
a
表示。
Q
是谓词“…… 是学生”,说明李明的性质,用
a)
张亮”陈华” 用b,…… 比…… 高”
(2)“ “ 是个体,
c
表示。“描述两个个体之间的高矮
关系,是谓词, b,表示。
用G(c)
1.量词
5.2
定义5.1.4
仅定义个体词和谓词的概念,对有些命题来说,还是不能准确地进行符
号化,如“所有的”和“有些”表示个体常项或个体变项之间数量关系的词。将表示个体常
项或个体变项之间数量关系的词称为量词。量词包括全称量词和存在量词两种。
定义5.1.5
对于日常生活和数学中出现的“一切的”“任意的”“所有的”“每一个”
“都”“凡”等词统称为全称量词,用符号.表示。.x,.
y
表示个体域中的所有个体,用
(.x)F(x),(.y)F(y)等表示个体域中的所有个体具有性质F。
例如,下面用符号表示命题“凡是人都是要死的”。
定义5.1.6
令D(x):
x
是要死的。该命题可表示为(.x)D(x),
x
的个体域为所有人的集合。
对日常生活和数学中常用的“存在”“存在一个”“有一个”“至少有一个”
“有些”“有的”等词统称为存在量词,用符号.表示。.x,.
y
表示个体域中有的个体,
用(.x)F(F(等表示个体域中有的个体具有性质F。
x),(.y)y)
例如,下面用符号表示命题“有些有理数是整数”。
令I(x)
x
是整数。该命题可表示为(.x)x),
x
的个体域为有理数集。
:I(
现在,我们可以用个体、谓词和量词将命题符号化,并且可以刻画命题的内在结构以
及命题之间的关系。因此,引进个体、谓词和量词后,用形式符号表示命题的功能得到加
强,表达意思更加全面、确切。
例5.4
1.用谓词和量词将下列命题符号化。
(1)所有的人都是要死的。
(2)每个自然数都是实数。
(3)一些大学生有远大的理想。
(4)有的学生选修了人工智能课。
解(1)符号化为(.x)(S(x)→L(x)), 其中,S(x):
x
是人,L(x):
x
是要死的。
(2)符号化为(.x)(
N
(x)→R(x)), 其中,
N
(x):
x
是自然数,R(x):
x
是实数。
(3)符号化为(.x)(P(x)∧Q(x)), 其中,
P
(x):
x
是大学生,Q(x):
x
有远大
理想。
(x)), :x):
智能课
4)
。
符号化为(.x)(F(x)∧T(其中,F(x)
x
是学生,T(
x
选修了人工
上述命题中都没有指明个体的取值范围,因而都指全总个体域。但当个体域为一个
特定的范围时,其符号形式将会有所不同。例如,在命题(1)中将个体域指定为所有人的
144
离散数学
集合,则命题(1)符号化为(.x)L(x), 在命题(2)中将个体域指定为实数集,则命题(2)
符号化为(.x)R(等。我们把例5.4中的S(x)、x)、P()、x)
x)1.
N
(xF(这种对个体变
元变化范围进行限制的谓词称为特性谓词。在命题符号化时,一定要正确地使用特性
谓词。
最后,还需要指出4点注意事项。
(1)在不同的个体域内,同一命题的符号化形式可能不同,也可能相同。
(2)同一命题在不同的个体域中的真值可能不同,也可能相同。
(3)全称量词后跟的是条件式,存在量词后跟的是合取式。
(4)P(x)不是命题,但前面加上量词后,(.x)P(x)和(.x)P(x)在给定个体域内
就有了真假,也就成了命题。
习题5.
1
(A)
1.下列各命题中是否包含量词,如果包含,请指出是全称量词还是存在量词。
(1)有理数是实数。
(2)刘鸣是三好学生。
(3)有人喜欢锻炼身体。
(4)发光的东西不一定是金子。
(5)星期二我去出差。
(6)上海有外国人。
(7)有些实数能表示成分数。
2.指出下列命题中的个体词和谓词
。
(1)2是素数
。
(2)小红和小明是大学同学。
(3)并不是所有的汽车都比火车跑得慢
。
(4)8>3
。
(B)
3.令Z(x):
x
是整数,Q(x):
x
是有理数。则命题“并非每个有理数都是整数”的
符号化表示为( )。
A....x(Q(x)→Z(x))
B....x(Z(x)∧Q(x))
C....x(Q(x)→Z(x))
D....x(Z(x)∨Q(x))
第5章谓词逻辑
5.谓词公式
2
145
2.谓词公式的定义
5.1
与命题逻辑一样,谓词逻辑中也同样包含命题变元和命题联结词,为了使谓词逻辑中
谓词表达式符号化更加规范与准确,能正确进行谓词逻辑的演算和推理,我们首先在谓词
逻辑公式中引入所使用的符号。
a,c,…。
(1)个体常项:b,
x,z,…。
(2)个体变项:y,
(3)谓词:F,G,
H
,…。
(4)函数:f,h,…。
g,
(5)联结词:..,∧,∨,→,.。
(6)量词:.,.。
(7)括号及逗号:(,) 以及“,”。
一个符号化的谓词表达式是由一串这些符号所组成的表达式,但并不是任意一个由
此类符号组成的表达式都对应一个正确的谓词表达式,因此,要给出谓词表达式的严格
定义。
定义5.2.1
谓词逻辑中项的定义如下。
(1)任何一个个体变元或个体常元称为项。
(2)若f(x2,…,是任意的
n
元函数,t2,…,
n
是任意的
n
个项, t1,
t2,…,t)是项
x。
1,xn
) t1,t则f(
定义5.2.2(由有限次使用(1),(得到的表达式是项。3)(n) 设P(x1,2)
) 其中,x2,…,则称
x2,…,xn
是
n
元谓词, x1,xn
是个体变项,
P(x1
定义5.2.3,x2,…,xn
)为谓词演算的原子公式。
P(P(y),f(y),a,因此原子谓词公式包括各种特例,如Q,x),x,P(x),P(y)等。
谓词演算的谓词公式定义如下。
(1)原子公式是谓词公式。
(2)若
A
是谓词公式,则(..A)也是谓词公式。
(3)若A,
B
是谓词公式,则(A∧B),(A∨B),(A→B),(A.B)是谓词公式。
(4)若
A
是谓词公式,则(.x)A,(.x)
A
是谓词公式。
(5)只有有限次地应用(1)~(4)构成的符号串才是谓词公式。
由定义5.3可知, 联结词、量词、圆括号和逗号
2.谓词公式是按上述规则由原子公式、
所组成的符号串,而且命题公式是它的一个特例。谓词逻辑的谓词公式就是合式公式或
公式。
谓词公式中的某些括号也可以省略,其规定与命题公式相同,谓词公式最外层的括号
可以省略,但量词后若有括号则不能省略。特别地,命题公式也是谓词公式,因此命题逻
辑包含在谓词逻辑中。
146
离散数学
2.谓词公式的符号化
5.2
谓词演算中命题符号化的步骤如下。
(1)确定个体域,一般使用全总个体域。
(2)分析命题中的个体及各个体间的关系,确定谓词。
(3)根据表示数量的词确定量词,并利用联结词将整个命题符号化
。
例5.1
a) b) 将下面的命题符号化
。
2.在个体域分别限制为(和(条件时,
(1)所有人都是要死的。
(2)有的人天生就近视
。
其中,(a)个体域D1 为人类集合;(b)个体域D2 为全总个体域
。
解(a)令F(x):
x
是要死的;G(x):
x
天生就近视
。
(1)在个体域D1 中除人外,没有其他的事物,因而(1)可符号化为(.x)F(x)。
(2)在个体域D1 中有些人是天生就近视,因而(2)可符号化为(.x)G(x)。
(b)在个体域D2 中除人外,还有其他的事物,因而将(1)、(2)符号化时,必须考虑先
将人分离出来,令
M
(x):
x
是人。在个体域D2 中,(1)、(2)可分别描述如下。
(1)对于宇宙间的一切事物,如果事物是人,则他是要死的。
(2)在宇宙间存在着天生近视的人。
将(1)和(2)分别符号化为:
(1)(.x)(
M
(x)→D(x));
(2)(.x)(
M
(x)∧G(x))。
在个体域D1、D2 中命题(1)、(2)都是真命题。
命题(1)、(2)在个体域D1、D2 中符号化的形式不同,主要区别在于,使用个体域D2
时,要将人从其他事物中区别出来,为此引进谓词
M
(x), 像这样的谓词称为特性谓词,在
命题符号化时一定要正确使用特性谓词。
例5.2
在个体域分别限制为(a)和(b)条件时,将下面的命题符号化:
2.
(1)对任意的x,都有x2-5x+6=(x-2)(x-3)。
(2)存在x,使得x+1=0
。
其中,(a)个体域D1 为自然数集合;(b)个体域D2 为实数集合
。
解(a)令F(x):x2-5x+6=(x-2)(x-3);G(x):x+1=0
。
(1)可符号化为:(.x)F(x)。
(2)可符号化为:(.x)G(x)
。
在个体域D1 中命题(1)为真命题,命题(2)为假命题
。
(b)在个体域D2 中(1)、(2)符号化分别如下
。
(1)(.x)F(x)
。
(2)(.x)G()
。
在个体域D2 命题(1)、(2)都是真命题
。
例5.3
并指出真值情况
。中(x)
2.将下列命题符号化,
第5章谓词逻辑
147
(1)没有人登上过月球。
(2)所有人的头发未必都是黑色的
。
解个体域为全总个体域,令
M
(x):
x
是人
。
(1)令F(x):
x
登上过月球。命题(1)可符号化
为
..(.x)(
M
(x)∧F(x))
,
设
a
是1969 年登上月球完成阿波罗计划的一名美国人,则
M
(a)为真,故命
题(1)为假。
..(.x)(
M
(x)→
H
(x)),
a)∧F(
(2)令
H
(x):
x
的头发是黑色的。命题(2)可符号化为
我们知道有的人头发是褐色的,所以,(.x)(
M
(x)→
H
(x)) 为假,故命题(2)为真。
例5.4
2.将下列命题符号化。
(1)火车比汽车跑得快。
(2)有的火车比所有汽车跑得快。
(3)并不是所有的火车比汽车跑得快。
(4)不存在跑得同样快的两辆汽车。
解设个体域为全总个体域。令C(:G(Q(y)
x
比
y
跑得快;L(x,:
x)
x
是火车;y):
y
是汽车;x,:
y)
x
和
y
跑得同样快
。
这4个命题分别符号化如下
。
(1)(.x)(.y)(x)∧G(→Q(x,))
。
C(
C(
Gy(
)
→Q(
yy)))。
(2)(.x)(x)∧(.y)(y)x,
(3)..(.x)(.y)(x)∧G(→Q(x,))。
C(y)
y
G(y)∧L(
(4)..(.x)(.y)(x)∧G(x,y))。
例5.5
将下列命题符号化。
2.
(1)一切人不是一样高。
(2)不是一切人都一样高。
(3)会叫的狗未必咬人。
分析“一切人”用.
x
表示,为全总个体域,特性谓词
M
(x)表示“
x
是人”;因为要
比较高矮,所以引入二元谓词G(y); 故还引入
H
(y
x,由于同一个人是一样高的, x,)。
解设
M
(:
x
是人;y):
x
与
y
一样高;y):
x
与
y
是不同的人,则命
x)G(x,
H
(x,
题(1)、(2)可符号化如下
M
。
(y)∧
H
(y)→..G(y))。
(1)(.x)(.y)(x)∧
M
(x,x,
(2)..((.x)(.y)(
M
(x)∧
M
(x,→G(y)))。
y)∧
H
(y)x,
或(.x)(.y)(
M
(y)x,))。
x)∧
M
(→G(
y
(3)令D(x):
x
是狗;P(x):
x
会叫;Q(x):
x
会咬人。则命题可符号化为
(.x)(D(x)∧P(x)∧..Q(x))
。
或..(.x)(D(x)∧P(x)→Q(x))
。
例5.6
2.在谓词逻辑中将下列命题符号化。
(1)不存在最大的数。
148
离散数学
(2)计算机系的学生都要学离散数学
。
解取个体域为全总个体域
。
(1)令F(x):
x
是数;L(y):
x
大于y;则命题(符号化为
x,1)
x)∧(.y)(y)
..(.x)(F(F(→L(x,)))。
y
(2)令C(x):
x
是计算机系的学生;G(x):
x
要学离散数学;则命题(2)符号化为
例5.7
将下列命题符号化
(
。
.x)(C(x)→G(x))。
2.
(1)尽管有人聪明,但并非所有人都聪明。
(2)这只大红书柜摆满了那些古书。
解
(1)令C(x):
x
聪明;
M
(x):
x
是人。则命题(1)可符号化
为
(.x)(
M
(x)∧C(x))∧..(.x)(
M
(x)→C(x))
。
(2)令F(y)
x
摆满了y;x):Q(
x
是古书;b:
x,:R(
x
是大红书柜;x):a:这只;
那些。则命题(2)可符号化为
R(b)∧F(b)。a)∧Q(a,
例5.8
将命题“凡人都是要死的;苏格拉底是人;苏格拉底是要死的”符号化。
解令
M
(:D(:a:苏格拉底。则命题的符号化表示为
2.
x)
x
是人;x)
x
是要死的;
((.x)(
M
(x)x))∧
M
(→D()。
→D(a))
a
2.谓词的约束与替换
5.3
定义5.2.4
在公式(.x)F(x)和(.x)F(x)中,称
x
为指导变元,称F(x)为相应
量词的辖域或作用域。在.
x
和.
x
的辖域中,
x
的所有出现都称为约束变元,F(x)中
不是约束变元的其他变元均称为自由变元。
要正确地理解谓词公式,必须准确地判断量词的辖域以及哪些是约束变元,哪些是自
由变元。
一般地,判断量词的辖域要看其后是否是括号,如果是,则括号内的子公式为其辖域,
否则量词邻接的子公式是其辖域。
判断给定公式中的个体变元是约束变元还是自由变元,关键要看它是约束出现还是
自由出现。
辖域的概念在程序设计中也有出现。例如,C语言中的全局变量和局部变量,其辖域
分别是整个程序和某个子程序。
例5.9
2.指出下列各式量词的辖域及变元的约束情况
。
(1)(.x)(F(x,→G(z))
。
y)x,
(2)(.x)(P(x)→(.y)R(x,))
。
y
(3)(.x)(F(x)y))→(.y)(
H
(x,z))
。
→G(x)∧
M
(y,
解(F(y)x,在
A
中,而且
1)对于.
x
的辖域是A=(x,→G(z)),
x
是约束变元,
约束出现两次;
z
均为自由变元,而且均自由出现一次。
(2)对于.
yx
,
的辖域是(P(x)→(.y)R(x,y)),.
y
的辖域是R(x,y),x,
y
均是
约束变元。
149
第5章谓词逻辑
(3) 对于.
x
的辖域是(F(x)→ G(y)), 其中
x
是约束变元, 而
y
是自由变元。对于
.
y
的辖域是(
H
(x)∧
M
(x,y,z)), 其中
y
是约束变元, 而x,
z
是自由变元。在整个公
式中,
x
约束出现一次, 自由出现两次;
y
约束出现一次, 自由出现一次;
z
仅自由出现
一次。
例5.10
2.指出下列各式量词的辖域及变元的约束情况。
(1)( . x)( . y)((P(x)∧ Q(y)) →(. z)R(z))。
(2)( . x)(P(x,y)→(. y)Q(x,y,z)) ∧ S(x,z)。
解(1)( . y)((P(x)∧ Q(y)) →(. z)R(z)) 是.
x
的辖域,((P(x)∧ Q(y)) →
(. z)R(z)) 是.
y
的辖域,R(z) 是.
z
的辖域,x,y,
z
在公式(1) 中均是约束变元, 故都
是约束变元。
(2)(P(x,y)→(. y)Q(x,y,z)) 是.
x
的辖域,Q(x,y,z) 是.
y
的辖域,P(x,y),
Q(x,y,z) 中的
x
是约束变元,Q(x,y,z) 中的
y
是约束变元,P(x,y) 中的
y
是自由变
元,S(x,z) 中的
x
是自由变元,Q(x,y,z),S(x,z) 中的
z
是自由变元, 因此公式(2) 中,
x,
y
既是约束变元, 又是自由变元。
在谓词公式中, 一个个体变元可以既是约束变元, 也是自由变元。为了避免一个变元
既是约束变元又是自由变元引起混乱, 可以对约束变元或自由变元进行改名,( . x)
A(x) 与(. y)A(y) 具有相同的意义, 使得一个变元在一个公式中只呈现一种形式。
.. .. .. .. .. .. .. .. ..
..
..
.............................................................................. ..
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
约束变元的换名规则
(1) 将量词的作用变元及其辖域中所有相同符号的变元用一个新的变元符号代
替, 公式的其余部分不变。
(2) 新的变元符号是原公式中没有出现过的。
(3) 用(1)、(2) 得到的新公式与原公式等值。
................
...... ...... ..
..
例5.11
2.对下列公式进行换名。
(1)( . x)(P(x)→ R(x,y)) ∧ Q(x,y)。
(2)( . x)(P(x,y)→(. y)Q(x,y,z)) ∧ S(x,z)。
解
(1) 将约束变元
x
换名为t:
(. t)(P(t)→ R(t,y)) ∧ Q(x,y)
。
(2) 将约束变元x,
y
换成u,v:
(. u)(P(u,y)→(. v)Q(u,v,z)) ∧ S(x,z)
。
同理, 对公式中的自由变元也可以更改, 这种更改称作代入
。
.............................................................................. ..
(2) 用以代入的变元与原公式中所有变元的名称都不能相同。
自由变元的代入规则
(1) 对于谓词公式中的自由变元, 可以代入, 此时需要对公式中出现该自由变元
的每一处进行代入。
............ ..
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
150
离散数学
例5.12
2.对下列公式代入
。
(1)(.x)(y))∧(.y))
。
F(x)→G(x,
H
(
y
(2)(.x)(x,→(.y)x,z))∧S(
z
P(y)Q(y,x,)
。
(3)(.x)(.y)(x,y))x,)
。
P(z)→Q(.S(
y
解(1)对
y
实施代入,经过代入后原公式为
:
(.x)(F(→G(t))∧(.y)
H
()
。
x)x,
y
(2)用w,
y
的自由变元:
t
来代入x,
x,→(.y)x,z))∧S(z), (.x)(P(t)Q(y,w,
其中,
y
为约束变元;
z
为自由变元。x,t,w,
P(z)y));.
y
的辖域是P(z)y);x,
(3).
x
的辖域是(.y)(x,→Q(x,→Q(P(z),
Q(y)中的x,
y
换成u,
x,中的
z
是自由变元;x,中的x,
y
是约束变元;P(z) S(y)
y
是自由变元。
将约束变元x,
(.u)(
v.
:
v)(P(u,z)→Q(v)).S(x,y)
。
将自由变元x,
w
代入:
x,→Q(.S(
w
y
用t,
(.x)(.y)(P(z)y))t,)。
另外,量词作用域中的约束变元,当个体域的元素有限时,个体变元的所有可能的取
代是可以枚举的。
若个体域为{a1,a2,…,
n
},
a则有下面二式成立
。
定义5.2.5(1)(.x)AA((
x)
.A(
a1)∧A(
a2)∨…∨Aann
)
。
.A(a2)∧…∧A(
(2)(.x)x)a1)∨A()
。((a)
没有自由变元的公式称为闭式
。
例如,(.x)(.y)(P(→R(y))∧(.x)(.y)Q(x,是闭式
。
x)x,y)
在谓词公式中,自由变元虽然可以出现在量词的辖域中,但它不受相应量词中指导变
元的约束,因而可把自由变元看作公式的参数。
在多个量词同时出现且它们之间无括号分隔时,后面的量词在前面量词的辖域之中,
且不能随意颠倒它们的顺序。颠倒顺序后会改变原命题的含义。
例5.13
P(
x
是学生;x)
x
是坐在这个教室里的人( a:张
2.x):Q(:命题函数);
三;(1(则) )Q(x)∧P(x):
x
是坐在这个教室里的学生。(谓词公式)
(2)Q(a): 张三是坐在这个教室里的学生。命题)
a)∧P((
(3)(.x)(Q(x)∧P(x)): 有一些坐在这个教室里的人是学生。(命题)
(4)(.x)(Q(x)→P(x)): 所有坐在这个教室里的人都是学生。(命题)
一般来说,若P(x2,…,xn
是
n
元谓词,它有
n
个相互独立的自由变元,当对其
x1,)
中
k
个变元进行约束后,则P(x1,x2,…,xn
)成为一个含有n-
k
个自由变元的命题函
数。因此,谓词公式中如果没有自由变元出现,则该公式就成为一个命题。
例如,(.x)(.y)
H
(y)
x,是一个命题。