第
3
章
谓词演算基础
在命题演算中,把不可剖开或分解为更简单的命题的原子命题作为基本单
元,把语句分解为原子命题,而不对原子命题的内部结构加以分析。本章将对原
子命题进一步剖析,分解为个体和谓词。一般地讲,原子命题是由若干谓词和项
再加上一
组成的,本章的目标是把日常永真的知识表达成谓词演算的形式语言,
些永真的规则,推出一些新的知识,研究它们的形式结构和逻辑关系。谓词演算
中语句的符号化是人工智能中知识表示的基础。
..3.1
个体和谓词
视频3.
1
3.1
个体
1.
首先介绍与个体有关的几个重要概念。
(1)个体:具有独立意义、独立存在的东西。
常个体:具有确定含义的个体,也称为实体。例如,“南京理工大学”“人工智
能”“计算机科学”等均为常个体。常个体常用a、b、
c
等表示。
(2)个体域:由个体组成的集合。例如,{ 微信,微博,支付宝},{x|
x
为南京
理工大学学生}等就是个体域。个体域常用I、J、
K
等表示。
(3)全总个体域:所有个体,不管是何种类型的个体,组合在一起组成的个体域,
用
U
表示。
(4)个体变元:以个体域
I
中的变元为变目的变元称为个体域
I
上的个体变
元,常用x、y、
z
等表示。
(5)项:构成原子公式的一部分。常量符号是最简单的项,是用来表示论域
中的个体或实体。一般地讲,个体和实体可以是物体、人、概念或有名称的任何
事物。
项包括实体、变量符号和函数符号等。
1.谓词
3.2
1.
有关概念
1)谓词的定义
谓词是指个体所具有的性质或若干个体之间的关系。
例如,“5为质数”“7小于8”中的“为质数”和“小于”均为谓词。前者是个体
44离散数学(微课版)
“5”所具有的性质,为一元谓词;后者是指个体“7”和“8”所具有的关系,为二元谓词。
约定用大写字母A、B、C等表示谓词。
例如:
(1)5为质数。令A表示“为质数”,实体a表示“5”,则该语句可表示为A(a) 。
(2)7小于8。令B表示“小于”,实体a表示“7”,实体b表示“8”,则该语句可表示为
B(a,b) 。
2)谓词填式
单个谓词不构成完整的意思,只有在谓词后填以个体才能构成完整的意义,这种在谓词
后填以个体构成的式子称为谓词填式。
例如,“为质数”是谓词,但不构成完整的意义,而谓词填式“5为质数”“7为质数”等就能
表达完整的意思。
3)谓词命名式
谓词后填以命名变元e构成的式子称为谓词命名式。命名变元仅代表谓词的元数,不
代表其他意思。
例如,A(e)表示A为一元谓词,B(e1,e2)表示B为二元谓词,以此类推。
4)谓词变元
以谓词组成的集合为变域的变元称为谓词变元。
上面已经描述过,大写字母A、B、C等表示特定的谓词,小写字母a、b、c等表示特定的
个体或实体。现在约定用大写字母X、Y、
Z
等表示谓词变元,小写字母x、y、
z
等表示个体
变元。
2.
谓词语句的符号化
一阶谓词演算是一种形式语言,用它可以表示各种各样的语句。这种形式语言的表达
式可以作为产生式数据库的组成部分。现在讨论谓词语句是如何符号化的。一般地讲,动
词、系动词、形容词和集合名词均可以表达成谓词。
例3.1
他送我这台笔记本电脑
。
解:
令
A(e2,表示“
。
e1,e3) e1 送e2e3”
B(表示“
。
e)
e
为笔记本电脑
”
a
表示“他”
。
b
表示“我”
。
c
表示“这台”
。
则原句译为
A(b,c)
a,c)∧B(
例3.2
Tom 送Alice这只大的红气球
。
解:
令
A(e2,表示“
。
e1,e3) e1 送e2e3”
B(表示“
。
e)
e
为大的
”
C(
e)
表示“
e
为气球”
。
e)
e
为红的
”
D(表示“
。
第3章谓词演算基础45a表示“Tom”。
b表示“Alice”。
c表示“这只”。
则原句译为
A(a,b,c)∧B(c)∧C(c)∧D(c)
例3.3美国位于加拿大和拉丁美洲之间。
解:令
A(e1,e2,e3)表示e1 位于e2 和e3 之间。
a表示美国。
b表示加拿大。
c表示拉丁美洲。
则原句译为
A(a,b,c)
上面分别介绍了谓词和个体的有关知识,事实上这仅仅是基于实体(或称特定个体)的
谓词,而在谓词演算中,知识的表示往往采用变量,即个体变元,表达一类相同的事实或
概念。例
如,Shakespearewrote“Othello”,可以符号化为Write(Shakespeare,Othello )。此
表达式表示常谓词Write、实体Shakeseare和Othello之间的关系。
下面讨论另外两种情况:
p1)Write(x,即个体为变量符号项。(
此表达式表示
yx
),
和
y
的关系是Write,即作者
x
写y。此时
x
可在个体域I(表示作者
的集合)上变化;
ity)
表示书名的集合)
y
可在个体域J( 上变化
。
因而表达式Wre(x,表达一类关系
。
(y),即个体为变量符号项,谓词为谓词变元。
2)X(x,
此表达式表示
x
和
y
有关系X,此时x、
y
和
X
分别在3个个体域上变化。
综上所述,谓词和个体是息息相关的,基于个体的谓词才是一个完整的谓词,且个体、谓
词、个体域三者是可以变化的。
以个体域
I
为定义域、以真假为值域的谓词称作个体域
I
上的谓词。
以个体域
I
上的谓词为变域的变元称作个体域
I
上的谓词变元。
下面讨论
h
个个体组成的个体域
I
上的
m
元谓词。
先讨论个体域{b}
1所示。
a,上的谓词
。
一元谓词X(e)如表3.
表3.两个个体的一元谓词
1
e
X1
X2
X3
X4 a
T T F F
b
T F T F
从表3.确切地说共有4类。
1可知一元谓词共有4个,
46离散数学(微课版)
二元谓词X(e1,e2)共有16个,如表3.2所示。
表3.2两个个体的二元谓词
e1e2X1X2X3X4X5X6X7X8X9X10X11X12X13X14X15X16aaT F T T T F F F T T T T F F F F
abT T F T T F T T F F T F T F F F
baT T T F T T F T F T F F F T F F
bbT T T T F T T F T F F F F F T F
不难验证,h个个体组成的个体域I上的一元谓词有2h个,二元谓词有2h2个,m元谓
词有2hm个。
视频3.2
..3.2函数项和量词
3.1节讨论了基于实体和变量符号项的谓词,下面讨论函数项和量词。
3.2.1函数项
函数项是以个体为定义域、以个体为值域的函数。约定用f、g、h等表示抽象的函
数项。
例3.4
将语句Mark..smotherismariedtohisfather符号化
。
解:
令
M
(e1,e2) e1iridt
。
表示“ smaeoe2”
m(e)表示“ te”
。
e
的mohr
f(表示“ ahr
。
e)
e
的fte”
则语句表示为
M
(m(Mark),f(Mark))
2.量词
3.2
在引入量词以前,先看一个例子。
设P(x)表示
x
为教授,若
x
的个体域表示人工智能学院的教师,则P(x)表示人工智
能学院的教师均为教授,而事实并非如此,确切的表达应该是人工智能学院有些教师是教
授。如果仍用P(x)表示
x
为教授,显然会引起概念上的混乱,为此必须引入量词表示“所
有的”“有一些”等不同的概念。
从以上简单的例子可以看出,要确切、完整地表达一个语句,必须约定个体的取值范围。
如上例规定
x
的取值范围为人工智能学院的教师的集合,也可约定
x
为人文学院的教师的
集合,如此约定很显然不利于计算机的识别和处理。采用如下方法可解决上面的不利因素。
(1)约定变量符号即个体变元
x
取值于全总个体域U。
(2)用谓词来限定
x
的取值范围。
(3)引进全称量词.
x
表示“所有的
x
”“一切
x
”等,存在量词.
x
表示“存在一些
x
”
第3章谓词演算基础47“有一些x”等概念。
(4)规定一般情况下紧跟在全称量词.x之后的主联结词为→,紧跟在存在量词.x
之后的主联结词为∧。
至此,再来看上面的例子“人工智能学院有些教师是教授”。
设A(e)表示“ e为人工智能学院的教师”,P(e)表示“ e为教授”,则原句译为
.x(A(x)∧P(x))
此例中x取值于全总个体域U,谓词A(e)限定x的取值范围。
有了量词的概念,知识的符号化问题就很容易得到解决。下面举一些例子说明把知识
表达成符号公式的方法。
例3.5有些人没写过任何小说。
解:令
P(e)表示“ e为人”。
N(e)表示“ e为小说”。
W(e1,e2)表示“ e1 写过e2 ”。
则原句译为
.x(P(x)∧.y(N(y)→..W(x,y)))
例3.6尽管有人能干,但未必所有人能干。
解:令
P(e)表示“。
e
为人
”
A(表示“
。
e)
e
能干”
则原句译为
例3.7
.x(P(x)∧A(x))∧...x(P(x)→A(x))
Ifaporaoetlat,hniaoerhtfact。
rgamcnntbodafctetcnntlanta
解:令
P(表示“ rgr。
e)
e
为poam”
F(表示“ at
。
e)
e
为fc”
T(e2)表示“aetl
。
e1,
表示“
e1cnbode2
。
”
L(e1,e2) e1canlearne2”
则原句译为
x)∧F(x,..L(y))
例3.8
解:令
我敬人人,人人敬我。
.x.y((P(y)∧..T(y))→x,
P(e)表示“。
e
为人
”
A(e2) e1 敬e2”
。
e1,表示“
a
表示“我”。
则原句译为
.x((P(a,x,
x)∧A(x))→A(a)
)
例3.9
解:令
鱼我所欲,熊掌亦我所欲
。
48离散数学(微课版)
F(e)表示“ e为鱼”。
B(e)表示“ e为熊掌”。
W(e1,e2)表示“ e1 为e2 所欲”。
a表示“我”。
则原句译为
.x(F(x)→A(x,a))∧.x(B(x)→A(x,a))
例3.10有些人喜欢所有的网络游戏,但并非所有人均喜欢网络游戏。
解:令
P(e)表示“ e为人”。
G(e)表示“ e为网络游戏”。
L(e1,e2)表示“ e1 喜欢e2 ”。
则原句译为
.x(P(x)∧.y(G(y)→L(x,y)))∧...x(P(x)→.y(G(y)∧L(x,y)))
例3.11任何一个集合x,总存在一个集合y,y的基数比x的基数大。
解:令
S(e)表示“ e为集合”。
f(e)表示“ e的基数”。
表示“ e1 比e2 大”。
G(e2)
e1,
则原句译为
.x(S(.y(y)∧G(f(y),x))))
x)→S(f(
..3.3
自由变元和约束变元
视频3.
3
3.1
自由出现和约束出现
3.
在第1章中给出了命题演算公式的形式定义。对于谓词演算来说,也存在合式公式的
形式定义的问题。首先约定A(x2,…,
n
) 其中x1,xn
是项(实体、变量符号、函数)。
x1,x为谓词演算公式的原子公式, x2,…,
3.简称公式) 谓词填式或由它们利用联结
1:谓词演算的合式公式( 是由原子命题、
词和量词构成的式子
。
合式公式的形式定义如下
:
(1)原子命题
P
是合式公式。
(2)谓词填式A(x1,x2,…,xn
)是合式公式。
(3)若
A
是公式,则..
A
是合式公式。
(4)若
A
和
B
是合式公式,则(A∧B)、(A∨B)、(A→B)、(A.B)为公式。
(5)若
A
是合式公式,
x
是
A
中出现的任何个体变元,则.xA(x)、.xA(x)为合式
公式
(
。
6)只有有限次使用(1)、(2)、(3)、(4)、(5)所得到的式子才是合式公式。
2:设
α
为任何一个谓词演算公式,.xA()、.xA(x)为公式
α
的子公式,此
3.
x
第3章谓词演算基础49
时紧跟在.、.之后的x称为量词的指导变元或作用变元,A(x)称为量词的作用域,在
作用域中x的一切出现均称为约束出现,在α中除了约束出现外的一切出现均称为自由
出现。
例3.12指出合式公式.x(X(x,y)→.y(Y(x,y)∧Z(z))) 的作用域、约束出现和
自由出现。
解:.x的作用域为X(x,y)→.y(Y(x,y)∧Z(z)) 。
.y的作用域为Y(x,y)∧Z(z) 。
公式中的x为约束出现,第一个y和z是自由出现,Y(x,y)∧Z(z)中的y为约束出现。
3.3:一个变元x若在公式中有自由出现,则称此变元为自由变元;若有约束出现,
则称为约束变元。
注意,自由出现的变元可以在量词的作用域中出现,但不受相应量词的约束,所以有时
把它看作公式中的参数。有一个特例,若公式中无自由变元,公式即为命题。
3.3.2改名和代入
1.改名
从上面的例子可以看出,同一个变元,如在公式.x(X(x,y)→.y(Y(x,y)∧Z(z)))
中的y,既有约束出现又有自由出现。为了避免变元的约束出现和自由出现在某一公式中
同时出现,引起概念上的混乱,可以对约束变元进行改名,使得同一个变元或者为约束出现,
或者为自由出现,同时使不同的量词所约束的变元不同名,便于计算机对知识的处理。之所
以可以这样做,是因为一个公式的约束变元所用的符号与公式的真假是无关的。例如,公式
.xX(x)和公式.yX(y)具有相同的意义。
下面给出改名的规则:
(1)改名是对约束变元而言的,自由变元不能改名。改名时应对量词的指导变元及其
作用域中所出现的约束变元处处进行。
(2)改名前后不能改变变元的约束关系。
例3.13(3)改名用的新名应是该作用域中没有使用过的变元名称。
对公式.x(X(y)→.y(x,z)))
x,Y(y)∧Z(实施改名
。
解:可把公式改名
为
.x(X(y)→.u(x,z))
)
x,Y(u)∧Z(
但不能改名为
.x(X(y)→Y(z)∧Z(
因为这样将改变变量的约束关系
x。
,.z(x,z)))
2.
代入
谓词演算公式中的自由变元可以更改,称为代入。代入是对自由变元而言的,约束变元
不能代入,代入后的式子是原式的特例。代入必须遵循下列规则:
(1)代入必须处处进行,即代入时必须对公式中出现的所有同名的自由变元进行。
(2)代入后不能改变原式和代入式的约束关系。
(3)代入也可以对谓词填式进行,但也要遵循上面两条规则;
(4)命题变元也可以实施代入。
50
离散数学(微课版)
例3.14
x,Y(y)∧Z()))。
已知公式.x(X(y)→.y(x,
z
(1)把公式中的自由变元
y
代以式子x2+2 。
(2)把公式中的谓词变元X(e1,e2) e1,y,)。
代以.yD(e2,
x
解:
(1)先把式子x2+2 直接代入原式,观察结果
。
代入后
得
.x(X(x2+2)→.y(x,z)))
x,Y(y)∧Z(
显然代入式中的x2 中的
x
本应为自由变元,而现在受全称量词.
x
约束,改变了它的
约束关系,因此是一种非法代入。为此必须采用下面的方法:
先对原式改名,将.
x
改为.u,将.
y
改为.v,改名后得式子
u,Y(v)∧Z(
最后代入,得
.u(X(y)→.v(u,z)))
.u(X(x2+2)→Y(v)∧Z(
u,.v(u,z))
)
验证公式可知,没有改变变元的约束关系,所以这种代入符合代入规则
。
(2)采用直接代入,查看结果
。
代入后得式
子
y,x)→.y(x,z)))
显然,代入式中的
x
本应为自由变元,代入后受.
x
约束,改变了约束关系。原式中的
y
本是自由变元,代入后受.
y
约束,改变了约束关系。因此,这是一种非法代入。
先对原式改名,将.
x
改为.u,将.
y
改为.v:
.u(X(y)→.v(u,z)))
.x(.yD(x,y,Y(y)∧Z(
u,Y(v)∧Z(
再对代入式改名,将.
y
改为.t,
得
.tD(e2,x)
e1,t,
最后代入,得
.u(.tD(y,x)→.v(u,z))) u,t,Y(v)∧Z(
..3.4
永真性和可满足性
视频3.
4
3.1
真假性
4.
由前面的讨论可知,谓词演算公式的真假性与4个因素有关。下面简单讨论相关的理
由,以便读者对知识的真假性有一个全面了解。
(1)个体域:设A(表示“,公式.xA(x)的值随个体域的不同而不同。
e)
e
为偶数”
例如,个体域
I
为{1,2,3,4,5,6}时,公式的值为假;个体域
I
为{2,4,6,8}时,公式的值
为真
(
。
2)自由变元:取值于个体域{1,2,3,4,5,6}。对于公式A(x), 当
x
取4时,其值为
真;当
x
取5时,其值为假。所以,公式的真假性随变元取值情况不同而不同。
(3)谓词变元:对于个体域I={4,8}, 分以下两种情况
。
当A(e)表示“ 时,.xA2(
,6,
e
为偶数” x)=T 。
第3章 谓词演算基础 51
当A(e)表示“e 为奇数”时,.xA(x)=F。
(4)命题变元:对于个体域I={2,4,6,8},A(e)表示“e 为偶数”。
考虑公式.xA(x)∧P ,当P =T时,公式的值为真;当P =F时,公式的值为假。
设α 为任何一个谓词演算公式,其中自由变元为x1,x2,…,xn ,谓词变元为X1,X2,…,
Xm ,命题变元为P1,P2,…,Pk 。此时α 可表示为
α(x1,x2,…,xn ;X1,X2,…,Xm ;P1,P2,…,Pk)
有了上面的讨论,就可对谓词演算公式给予解释。
设个体域I 解释为常个体域I0。
自由变元x1,x2,…,xn 解释为I0 中的个体a1,a2,…,an 。
谓词变元X1,X2,…,Xm 解释为I0 上的谓词A1,A2,…,Am 。
命题变元P1,P2,…,Pk 解释为P01,P02,…,P0k,其中P0i =T或F,i={1,2,…,k}。
则说给了公式α 一个解释。记为
(I0;a1,a2,…,an ;A1,A2,…,Am ;P01,P02,…,P0k)
公式α 在该解释下的值记为
α(a1,a2,…,an ;A1,A2,…,Am ;P01,P02,…,P0k)
简记为α(a;A ;P0)。
如果该值取为T,则称该解释为成真解释;
如果该值取为F,则称该解释为成假解释。
下面讨论含有量词的谓词演算公式的真假性。首先讨论公式.xα(x)和.xα(x)的真
假性。.xα(x)为真.个体域I 中的每一个个体均使得α 取为真。
.xα(x)为真.个体域I 中有一个个体使得α 取为真。
下面举例说明给定一个解释后求公式真假性的方法。
例3.15 已知公式.x.y((X (x,y)∧Y(z)∧P )→Z(x,y)),求公式在解释(I;z;
X (e1,e2),Y(e),Z(e1,e2);P)=({1,2,3,4};2;e1≥e2,e 为偶数,e1≤e2;T)之下的值。
解:将解释代入公式,得
原式=.x.y((x ≥y ∧2为偶数∧ T)→x ≤y)
=.x.y(x ≥y →x ≤y)
(1)当x=1时,原式的作用域=.y(1≥y→1≤y)。
① 当y=1时,.y 的作用域=1≥1→1≤1=T。
② 当y≥2时,.y 的作用域=1≥y→1≤y=F→T=T。
(2)当x=2时,原式的作用域=.y(2≥y→2≤y)。
① 当y=1时,.y 的作用域=2≥1→2≤1=T→F=F。
② 当y=2时,.y 的作用域=2≥2→2≤2=T→T=T。
③ 当y≥3时,.y 的作用域=2≥y→2≤y=F→T=T。
(3)当x=3时,原式的作用域=.y(3≥y→3≤y)。
① 当y=1,2时,.y 的作用域=3≥y→3≤y=T→F=F。
② 当y=3时,.y 的作用域=3≥3→3≤3=T→T=T。
③ 当y=4时,.y 的作用域=3≥4→3≤4=F→T=T。
5
2
离散数学(微课版)
(4)当x=4时,原式的作用域=.y(4≥y→4≤y)。
①当y=1,2,3时,.
y
的作用域=4≥y→4≤y=T→F=F 。
②当y=4时,.
y
的作用域=4≥4→4≤4=T→T=T
。
综上所述,当x=2且y=1,x=3且y=1,2,x=4且y=1,2,3时,
有
.y(
x
≥
y
→
x
≤y)=
F
所以,根据含有全称量词公式真假的定义知
:
.x.y((X(y)∧Y(x,=
F
x,z)∧P)→Z(y)
)
故原式在已知解释下的值为F
。
3.2
同真假性、永真性和可满足性
4.
有了解释的概念,就可讨论公式的同真假性、永真性和可满足性。
4:设有两个公式
α
和β,如果对于个体域
I
上的任何解释,公式
α
和
β
均取得相
同的真假值,则称
α
和
β
在
I
上同真假。
如果
α
和
β
在每一个非空域上均同真假,则称
α
和
β
同真假。
下面给出两组等价公式。
3.
(1)关于否定的等价公式。
...xα(x)=.x..α(x)
...xα(x)=.x..α(x)
对于上面两个公式可在有限域I={a2,…,
n
}上加以说明,当然在无限域上等价公
a1,a
式仍成立。
...xα(x)..(a1)∧α(…a))
=α(a2)∧∧α(
n =
..α(a2)∨…a)
a1)∨..α(∨..α(
n =
.x..α(x)
...xα(x)..(a1)∨α(…a))
=α(a2)∨∨α(
n =
..α(a2)∧…a)
a1)∧..α(∧..α(
n =
.x..α(x)
(2)量词作用域的收缩与扩张。
设公式
γ
中不含有自由的x,则下面的公式成立
。
.x(α(x)∨γ)
=
.xα(x)∨
γ
.x(α(x)∧γ)
=
.xα(x)∧
γ
.x(α(x)∨γ)
=
.xα(x)∨
γ
.x(x)∧γ)
=
.xα(x)∧
γ
例3.16
α(
用上面的等价公式判断公式.xα(→
γ
和.x(x)是否等价。
x)α(→γ)
解:
.xα(x)→γ=...xα(x)∨
γ
=.x..α(x)∨
γ
=.x(..α(x)∨γ)
=.x(x)→γ)
α(
≠.x(x)→γ)
α(
第3章谓词演算基础53
所以两公式不等价。
3.5:给定一个谓词演算公式α,其个体域为I。对于I中的任意一个解释,若α均
取为真,则称公式α在I上为永真的;若α均取为假,则称公式α在I上为永假的,也称为公
式α在I上不可满足。
3.6:给定一个谓词演算公式α,其个体域为I。如果在个体域I上存在一个解释
使得α取为真,则称公式α在I上为可满足公式;如果在个体域I上存在一个解释使得α取
为假,则称公式α在I上为非永真公式。
3.1:如果I、J是两个具有相同个数的个体的个体域(个体本身可不相同), 则任
意一个公式α在I中永真当且仅当其在J中永真,在I中可满足当且仅当其在J中可满足。
证明:要证明该问题,首先要在两个个体域I和J上建立个体、谓词、解释等元素间的
一一对应关系。构造如下:
(1)因为I和J具有相同个数的个体的个体域,所以可在两者之间建立一一对应关系,
即在I中有一个个体a,总能在J中找到一个个体与之对应,反之亦然。
(2)建立个体域I和J中谓词的一一对应关系。
设X(x1,x2,…,xn)是I中的n元谓词,令满足下列性质的J中的n元谓词X'(x'1,
x'2,…,x'n)与X(x1,x2,…,xn)相对应:X(x1,x2,…,xn)为真当且仅当X'(x'1,x'2,…,x'n)
为真,其中x在I中取值,x'在J中取值。
(3)为I中的解释与J中的解释建立一一对应关系:
设有
I
中的一个解
释
x2,…,X1,P2,…
,
(x1,xn
;X2,…,Xm
;P1,Pk
)
a2,…,;A2,…,;P0P0
=(a1,an
A1,Am
1,
k
)
简记为(x;P)a;P0)。
P02,…,
X;=(A;
则令
J
中的下列解释为其对应的解释
:
(x2,…,;X2,…,;P2,…
,
x1,xn
X1,Xm
P1,Pk
)
a(') a(') nAA2(') Am
;1,2,…,
k
)
简记为(P0)。
=(a(') 1,2,…,;1,(') ,…,'P0P0P0
a';A';
a;=aAP0)。3.
利用归纳法,可证明α(A;P0)α(';';(1)
如果
α
为命题变元,命题显然成立。
如果
α
为谓词填式X(x1,x2,…,xn
), 则有
α(a;A;P0)a1,a)
=A(a2,…,
n
'(2,…,)
=Aa1,''
'aan
aA
故命题成立。
=α(';';P0)
如果
α
为下列5种情形之一:
β1∨β2,β1→β2,
由归纳假设知,
..β1,3.
β1
即
∧β2,β1.β2
β1 和β2 满足式(1),
β1(A;P0)β1(';';P0)
a;=aA=aA
β2(a;A;P0)β2(';';P0)
54
离散数学(微课版)
当α=..β1 时,
α(A;P0)..β1(A;P0)
a;=a;
=..β1(';A';P0)
a
故式(1)成立。
=α(a';A';P0)
3.
当α=β1∨β2 时,
a;P0)β1∨β2)(A;
α(A;=(a;P0)
a;P0)∨β2(A;
=β1(A;a;P0)
=β1(AaA
a';';P0)∨β2(';';P0)
β1∨aA
故式(3.成立。
=(β2)(';';P0)
1)
同理可证其他3种情形。
y),
P0;';P0;(
如果
α
形如.yβ1(x;
X
;P;由归纳假设知
a;A;y)';') 2)
β1(=β1(Ay3.
.yβ1(x;P;为真, 一个(a) a;b) 根据
X
;y) 即在个体域
I
中有个体
b
使得β1(A;P0;为真,
式(2)
1)
';P0;为真, x;P;在
J
上取为真。
3.知:β1(A';') 即.yβ1(
X
;y)
ab
故式(3.成立。
X
;y), 如果
α
形如.yβ1(x;P;同理可证。
设
α
在
I
中可满足,即在
I
中存在一个解释(A;使得
α
取真值,由解释的一一对
应关系和式(3.知, aaA;
PP00)
)
使得
α
取为真,
足。反之亦然。
1) 在
J
中也存在一个解释(';';故
α
在
J
中可满
同理可证,
α
在
I
中永真当且仅当
α
在
J
中永真。
讨论公式的永真性和可满足性的目的是简化讨论任一谓词演算公式在某一个体域上的
真假性。由上可知,有限域上一个公式的永真性和可满足性依赖于个体域中个体的数目,与
个体的内容无关,因此要讨论公式
α
在任何
k
个个体域上的永真性和可满足性,只要讨论公
1,k} 1,k}
式
α
在个体域I={2,…,上的永真性和可满足性即可。我们把个体域{2,…,称为
k
域,即由
k
个个体组成的个体域。当k=1时,称为1域,以此类推。
显然有下面的定理。
3.2:如果一个公式在
k
域上永真,则其在h(<k)域上永真。
例3.173:如果一个公式在
h
域上可满足,则其在k(域上可满足。
足性。
3.
试讨论公式.x(X(→(.y(y)∧Z(
k>h)
Y(的永真性和可满
x)Y(z))→.xx)))
解:
(1)讨论1域即个体域I={1}的情形
Y
。
(1))→Y(
公式=X(1)→((1)∧Z(1))
=X(1)→T
=T
所以公式在1域上永真。
第3章谓词演算基础55
(2)讨论2域上的情形,此时个体域I={1,2}。
由于公式在1域上永真,所以公式在1域上可满足。由定理33知公式在2域上可满足。
.
由前面讨论可知,2域上的一元谓词有4个,3所示。
如表3.
表3.
32
域上的一元谓词
e
X1
X2
X3
X4
1 T F T F
2 T T F F
在解释(Y,=({2};X1,下,
I;z;X,Z)1,2;X2,X2)
原式
=
.x(x)→(.y(y)∧X2(2))→.xX2(
X1(X2(x)))
=
.x(x)→(.y(y)∧T)→.xX2(x)))
X1(X2(
=
.x(x)→(.yX2(.xX2(x)))
X1(y)→
=
.x(X1(x)→(T→.xX2(x)))
=
.x(X1(x)→.xX2(x))
=
.x(X1(x)→F)
=
.x..X1(x)
=F
故公式在2域上可满足但非永真。
(3)讨论k(域上的情形
。
k>2)
3知
,
因为公式在2域上可满足,根据定理3.公式在
k
域上可满足
。
设公式在
k
域上永真,根据定理3.公式在2域上永真
,
2知, 与公式在2域上非永真
矛盾。故
公式在
k
域上可满足但非永真。
4.范式
3.3
在命题演算中,任一命题演算公式均有一个范式与之等价。对于谓词演算公式也有相
应的范式,其中任一谓词演算公式均有一个前束范式与之等价。前束范式对于计算机处理
和识别谓词演算公式有着重要的作用。
1.
前束范式
3.量词前不含否定词)
7:如果谓词演算公式
α
中的一切量词均在公式的最前面(
且其作用域一直延伸到公式的末端,则称公式
α
为前束形公式。前束形公式的一般形式为
Q1x1Q2x2…QnxnM
(x2,…,)
x1,xn
其中,Qi
为.或.,x1,xn
)称为公式
α
的母式且其中不含有量词。
M
(x2,…,
4:任意一个谓词演算公式均有一个前束范式与之等价。
下面用具体的例子来说明该定理。
范式
例3.18
。
把公式.x.y.z(
X
(x,y,z)∧(.uY(u,x)→.xW
(y,x))) 化为前束
3.
56
离散数学(微课版)
解:
(1)利用等值公式消去→和.:
原式=.x.y.z(X(y,Y(x)∨.xW
(x)))
(2)否定深入:
x,z)∧(...uu,y,
原式=X(x,y,u,y,
(3)改名:
.x.y.z(z)∧(.u..Y(x)∨.xW
(x)))
原式
=
.x.y.z(x,z)∧(.u..Y(x)∨.vW
(v)))
(4)前移量词:
X(y,
x,z,v)
u,y,
原式=x,z)∧(..Y(x)∨
W
(v)))
.x.y.z.u.v(X(y,u,y,
=
.x.y.z.u.vM
(y,u,
2.Skolem
标准形
3.ol
8:仅含有全称量词的前束范式称为Skem 标准形。
5:任一谓词演算公式
α
均可以化成相应的Skem 标准形且
α
为不可满足的
3.ol
当且仅当其Skolem 标准形是不可满足的。
Skolem 标准形的求解算法如下:
(1)求谓词演算公式的前束范式。
(2)按如下方法消去存在量词。
①若存在量词.
x
前无全称量词,则引入Skolem 常量a,代替公式中受.
x
约束的变
元,消去存在量词。
②若存在量词.
x
前有
n
个全称量词,则引入
n
元Skolem 函数f,代替公式中受.
x
约束的变元,消去存在量词。
例3.19(3)从左至右重复上述过程,直至公式中不含有存在量词。
求公式.x(..(.yX(x,→(.zz)∧.xZ(的Skol
y)Y(x)))) em 标准形。
解:
(1)先把公式化为前束范式
.x(..(...
:
yX(x,y)∨(.zY(z)∧.xZ(
原式=
x,z)∨.x..Z(
x))))
=
.x(.yX(y)∧(.z..Y(x)))
=
.x(.yX(y)∧(.z..Y(u)))
x,z)∨.u..Z(
=
.x.y.z.u(x,z)∨..Z(
X(y)∧(..Y(u)))
(2)化为Skolem 标准形:
a,z)∨..Z(
原式..y.z.u(X(y)∧(..Y(u))
)
..y.z(X(y)∧(..Y(f(z))))
a,z)∨..Z(y,
..3.5
唯一性量词和摹状词
5.唯一性量词
3.1
日常语句中常常出现“只有一个……”“恰好有一个……” 等语句,对于这些语句可以引
进唯一性量词.!
x
来表示它们。
第3章 谓词演算基础 57
.!xα(x)表示恰好有一个x 使得α(x)为真。.!称为唯一性量词。
可以利用等价公式消去唯一性量词。等价公式如下:
.!xα(x)=.x(α(x)∧ .y(x ≠y → ..α(y)))
下面通过例子说明利用唯一性量词符号化语句的方法。
例3.20 他是唯一没有去过美国的人。
解:令
P(e)表示“e 为人”。
B(e1,e2)表示“e1 去过e2”。
a 表示“他”。
b 表示“美国”。
则原句译为
.!x(P(x)∧ ..B(x,b)∧x =a)
例3.21 地球是唯一有人的星球。
解:令
S(e)表示“e 为星球”。
P(e)表示“e 为人”。
C(e1,e2)表示“e1 上有e2”。
a 表示“地球”。
则原句译为
.!x.y(S(x)∧P(y)∧C(x,y)∧x =a)
3.5.2 摹状词
日常语句中经常使用“纸的发明者”“上帝的创造者”等利用个体的特征性质描述特定的
个体,这种描述特定个体的短语称为摹状词。它跟谓词正好相反,谓词P(x)是指x 所具有
的性质,而摹状词是指具有性质P 的那个个体x。
γxα(x)是指使得α(x)成立的那个唯一的个体,其中γ 称为摹状词,x 称为摹状词的指
导变元,α(x)称为摹状词的作用域。
注意,摹状词的作用域与量词的作用域均为谓词演算公式,但摹状词的值为个体,而量
词的值为真或假,且要使用摹状词必须满足存在性和唯一性。对于不满足存在性和唯一性
的语句,如“地球的创造者”不满足存在性,“计算机的发明者”不满足唯一性,引入下面的表
示方法:
γy
xα(x)=
x .!xα(x)成立时,指使α(x)成立时的那个唯一的个体x
y 否则{
由摹状词的定义可知,下列等式成立。
β(γy
xα(x))=(.!xα(x)∧ .t(β(t)∧α(t)))∨ (...!xα(x)∧β(y))
下面利用摹状词来符号化公式。
例3.22 并非读书最多的人最有知识。
解:设
P(e)表示“e 为人”。
58离散数学(微课版)
B(e1,e2)表示“ e1 比e2 读书多”。
C(e1,e2)表示“ e1 比e2 有知识”。
则“读书最多的人”译为
γyx(P(x)∧.y((P(y)∧y≠x)→B(x,y)))
把它记为u,故原句译为
...t((P(t)∧t≠u)→C(u,t))
..3.6典型例题
例3.23把下列语句翻译为谓词演算公式。
(1)微信是一种智能手机应用程序,但并非所有人均喜欢微信。
(2)有些人喜欢所有的网络服务。
解:
(1)设
S(e)表示“ e为一种智能手机应用程序”。
P(e)表示“ e为人”。
L(e1,e2)表示“ e1 喜欢e2 ”。
则原句译为
(2)设
S(微信)∧...x(P(x)→L(x,微信))
N
(表示“。
e)
e
为网络服务
”
P(表示“
。
e)
e
为人
”
L(e1,e2) e1 喜欢e2”
表示“。
则原句译为
例3.24
x)∧.y(y)→L(y)))
.x(Px(
)∨Y(.
N
(.
(
xX(
x,
Y(的永真性和可满足性。
讨论公式.x(X(x))x)∨.xx))
解:
(1)讨论1域即个体域{1}的情形。
公式=(X(1)∨Y(1)).(X(1)∨Y(1))=
T
所以公式在1域上永真
。
(2)讨论2域上的情形,此时个体域I={1,2}
。
由于公式在1域上永真,由定理3.
3知公式在2域上可满足
。
由前面的讨论可知,2域上的一元谓词有4个,4所示
。
如表3.
表3.
42
域上的一元谓词
e
X1
X2
X3
X4
1 T F T F
2 T T F F
第3章谓词演算基础59
在解释(I;X;=({2};X2,X3)下,
Y)1,
原式
=
.x(X2(x)∨X3(x)).(.xX2(x)∨.xX3(x))
=T.(F∨F)
=F
故公式在2域上可满足但非永真。
(3)讨论k(域上的情形
。
k>2)
3知
,
因为公式在2域上可满足,根据定理3.公式在
k
域上可满足
。
设公式在
k
域上永真,根据定理3.公式在2域上永真
,
2知, 与公式在2域上非永真
矛盾。故
公式在
k
域上可满足但非永真。
准形
例3.25
。
求公式.x.yX(x,y)→(.x.yY(y)∧.x.yZ(y)) 的Skolem 标
x,x,
解:
(1)利用等值公式消去→和.:
x,y)
)
原式=x,x,
(2)否定深入:
...x.yX(y)∨(.x.yY(y)∧.x.yZ(
原式=.x.y..X(y)∨(.x.yY(y)∧.x.yZ(x,
(3)改名:
x,x,y)
)
原式
=
.x.y..X(y)∨(.u.vu,s.ts,
(4)前移量词:
x,Y(v)∧.Z(t)
)
原式=x,Y(v)∧Z(t))
)
.x.y.u.v.s.t(..X(y)∨(u,s,
(5)消去存在量词:
Y(v)∧Z(t))
)
原式..y.u.v.s.t(..X(a,y)∨(u,s,
Y(v)∧Z(t)))
..u.v.s.t(..X(a,b)∨(u,s,
a,b)∨(Y(f(s,
..u.s.t(..X(u,u))∧Z(t)))
u))∧Z(s))))
a,Y(f(g(
..u.s(..X(b)∨(u,s,u,
..
习题
1 将下列语句符号化。
3.
(1)如果知道你不在家,我就不去找你了。
(2)这只大红书柜摆满了那些古书。
(3)苏州位于南京与上海之间。
(4)他既熟悉C++语言又熟悉Java语言
。
(5)Alice喜欢人工智能或机器学习
。
(6)区块链是一种分布式账本技术。
2 将下列语句符号化为含有量词的谓词演算公式。
3.
(1)没有不犯错误的人。
(2)有不是奇数的质数。
60离散数学(微课版)
(3)金子闪光,但闪光的并非全是金子。
(4)并非“人不为己,天诛地灭”。
(5)人不犯我,我不犯人;人若犯我,我必犯人。
(6)有一种液体可溶解任何金属。
(7)并非“人为财死,鸟为食亡”。
(8)若要人不知,除非己莫为。
(9)任何一数均有一数比它大。
(10)每个作家均写过作品。
(11)某些人对某些食物过敏。
(12)天下乌鸦一般黑。
(13)己所不欲,勿施于人。
(14)有些人喜欢所有的明星,但并非所有人均喜欢所有的明星。
(15)所有人均喜欢微信或微博。
(16)我爱人人,人人爱我。
(17)有些学生不喜欢离散数学。
(18)群山中珠穆朗玛峰最高。
(19)并非一切劳动均能用机器代替。
(20)并非所有大学生都能成为科学家。
(21)有些人喜欢机器学习课程,但并非所有人均喜欢机器学习课程。
3
令
P(e)表示“
。
3.
e
为质数
”
E(e)表示“
。
e
为偶数
”
O(e)表示“
。
e
为奇数
”
D(e2) e1 除尽e2”
。
e1,表示
“
将下列公式翻译为日常语句
。
(1)E(2)∧P(2)
(2).x(2,→E(x)
)
D(x)
(3).x(..E(2,
x)→..D(x)
)
(4).x(x)→.y(x,→E(
E(D(y)y))
)
(5).x(E(x)∧P(x)
)
3.自由变元和约束变元。
4 指出下列公式的约束关系
、
(1).x(x,Y(y)z))
)
X(y)→.y(x,→Z(
(2).x(x)y,X(x,
X(→Y(t))→.y(y)∧Y(y))
3.x)→.y(x,y))。
5 已知公式.xX(Y(y)∧Z(
(1)将公式中的自由变元
x
代以y2+2 。
e1,代以式子.xA(e2,y)。
(2)将公式中的谓词变元Y(e2) e1,x,
3.6 讨论公式.x.yX(x,在个体域{2}上的成真解释和成假解释。
3.X(yy)
)
P
∧Y(
1,
y,在解释(z;e1,Y(e2,
7 求公式.x.y(x,→(x,z))) I;
X
(e2),e1,
e3);P)1,5};e1≥e2,T)
=({3,1;e1-e2=e3;下的值。
第3章谓词演算基础61
3.其中
γ
中不含
8 利用量词的等价公式判断下列每一组公式中的两个公式是否等价,
有自由的x。
1)γ→.xγ→α((α(x)和.x(x))
(→
γ
和.x(
2)...x..α(x)α(x)→γ)
3.x)→.xX(的永真性和可满足性。
9 讨论公式.xX(x)
3..(.xX(x)∧.
x
10 讨论公式.x(X(x)∧Y(x))Y(x)) 的永真性和可满足性
。
3.ol
11 求下列公式的前束范式和Skem 标准形
。
X(x,
(1).x(x)∧(.yY(y)→.xZ(x))
)
(2).xX(x)..xY(x)
(3).xF(x)∨(..(.xF(y))∧.yG(y)
)
x)→.yG(
(4).x.y(x)y))→.x(X(x)∧.yY(
X(→Y(y)
)
(5)...x(.yX(y)→.x.y(x,X(x)x,
3.
x,Y(y)∧.y(y,→Y(y))))
。
12 用唯一性量词或摹状词符号化下列语句
。
(1)只有一个人去过南极。
(2)最后一个离开办公室的人关门窗和电源。
(3)并非年龄最大的人最有知识。
(4)每个数均有唯一的一个数是它的后继。
(5)反对这个提案的人只有一个。