-
1
《计算机数学基础
(
上
)
》辅导
(2)
??
谓词逻辑
本章重点
：谓词与量词，公式与解释
，前束范式，谓词逻辑推理证明
.
一、重点内容
1.
谓词与量词
?
谓词，在谓词逻辑中，原子命题分解成个体词和谓词
. <
/p>
个体词
是可以独
立存在的客体，它可以是
具体事物或抽象的概念
.
谓词
是用来
刻划个体词的性质
或事物之间的关系的词
.
个体词分个体常项
(
用
a
,
b
,
c
,
d
,…
表示
)
和个体变项
(
用
x
,
y
,
z
,…
表示
)
；谓词
分谓词常项
(
表示具体性质和关系的词
)
和谓词变项
(
表示抽象的或泛指
的谓词
)
，
用
F
,
G
,
P<
/p>
,…
表示
.
注意，单独的个体词和谓词不能构成命题，将个体词和谓词分
开不是命
题
.
?
量词，是在命题中表示数量的词，
量词有两类：全称量词
?
，表示“所
有
的”或“每一个”；存在量词
?
，表示“存在某个”或“至少有
一个”
.
在谓词逻辑中，使用量词应注意以下几点：
(1)
在
不同个体域中，命题符号化的形式可能不同，命题的真值也可能
会改变
< br>.
(2)
在考虑命题符号化时，如果对个体域未作说明，一律使用全个体域
.
(3)
< br>多个量词出现时，不能随意颠倒它们的顺序，否则可能会改变命题
的涵义
.
谓词公式只
是一个符号串，没有什么意义，但我们给这个符号串一个解
释，使它具有真值，就变成一
个命题
.
所谓解释就是使公式中的每一个变项都有
个体域中的元素相对应
.
2.
公式与解释
学习这一部分内容要侧重于能将谓词逻辑公式表达式中，消除
量词写成
与之等值的公式，然后将解释中的数值代入，求出真值，并着重理解在谓词和<
/p>
量词的作用下变元的自由性、约束性和更名规则、代入规则等
.
?
谓词公
式，我们将命题常数
0
，
1
，一个命题和命题变元以及一个命题
函数
P
(
x
1
,
x
2
,…,
x
n
)
，统称原子公式，由原子公式、联结词和量词
可构成谓词公式
(
严格定义见教材
)<
/p>
.
命题的符号化结果都是谓词公式。
例如
?
x
(
F
(
x
)
?
G
(
x
))
，
?
x
(
F
(
x
)
?
G
(
x
))
，
< br>?
x
?
y
(
F
(
x
)
?
F
(
y
)
?
L
(
x
,
y
)
?
H
(
x
< br>,
y
))
等
都是谓词公式
.
?
变元与辖域，在谓词公式
?
xA
和
?
xA
中，
x
是
指导变元
，
A
是相应量词
的
辖域
.
在
?
x
和
?
x
的辖域
A
中，
x
的所有出现都是约束出现，即
x
是
< br>约束变元
，
不是约束出现的变元，就是
< br>自由变元
.
也就是说，量词后面的式子是
辖域
.
量词
只对辖域内的同一变元有效
.
2
<
/p>
?
换名规则
，就是把公式中量词的指导变
元及其该量词的辖域中的该变
元换成该公式中没有出现的个体变元，公式的其余部分不变
.
?
代入
规则
，就是把公式中的某一自由变元，用该公式中没有出现的个体变
元符号替代，且要把该公式中所有的该自由变元都换成新引入的该符号
.
?
解释
(
赋值
)
，
谓词公式的个体域
D
是非空集合，
(1)
每一个常项指定
D
中一个元素；
(2)
每一个
n
元函数指定
D
n<
/p>
到
D
的一个函数；
(3)
每一个
n
元谓词指定
D
n
到
{0,1}
的一个谓词
.
?
谓词公式分类
，在任何解释下，谓词公式
A
取真值
1
，公式
A
为逻辑
有效式
(
永真式
)
；在任何解释下谓词公式
A
取真值
0
，公式
A
为永假式；至
少有
一个解释是公式
A
取真值
1
，公式
A
称为可满足
式。
3.
前束范式
一个谓词公式的前束范式，仍然是谓词公式
.
若一个谓词公式
F
等值地转
化
成
Q<
/p>
1
x
1
Q
2
x
2
...
Q
k
x
k
B
那么
Q
1
x
1
Q
< br>2
x
2
...
< br>Q
k
x
k
B
就是
F
的前束范式，其中
Q
1
，
Q
2
，
…
，
< br>Q
k
只能是
?
< br>或
?
，
而
x
1
,
x
2
,…,
x
k
是
个体变元，
B
是不含量词的谓词公式
.
每个谓词公式
F
都可以变换成与它等值的前束范式
.
其步骤如下：
①
消去联结词
?
，
?
，
?
?
；
②
<
/p>
将联结词
?
移至原子谓词公式之前；
③
利用换名或
代入规则使所有约束变元的符号均不同，并且自由变元与约
束变元的符号也不同；
④将
?
x,
?
x
移至整个公式最左边；
< br>
⑤
将公式化为前束范式
.
4.
谓词逻辑的推理理论
谓词演算的推理是命题演算推理的推广和扩充，命题演算中的
一些规
则，如基本等值公式，重言蕴含式以及
P
，
T
，
CP
< br>规则在谓词演算中仍然使用
.
在谓词演算推理中，某些
前提和结论可能受到量词的限制，为了使用这些推
理，引入消去和附加量词的规则，有<
/p>
US
规则
(
全称
量词消去规则
)
，
UG
规则
(
全
称量词附加规则
)
，
ES
规则
(
存在量词消去规则
)
，
EG
规则
(
存在量词附加规则
)
等，以便使谓词演算公式的推理过程可
类似于命题演算的推理进行
.
二、实例
例
2.1
将下列命题符号化：
(1)
每个母亲都爱自己的孩子；
(2)
所有的人都呼吸；
(3)
有某些实数是有理数
.
解
(1)
设个体域是所有母亲的集合
.
M
(
x
)
：
x
表示爱自己
的孩子；
3
该命题符号化为
?
xM
(
x
)
.
(2)
设个体域为人的集合
.
H
(
x
)
：
x
表示要呼吸
.
该命
题符号化为
?
xH
(
< br>x
)
或设个体域为生物集合，
M
(
x
)
：
x
是人
.
H
(
x
)
：
x
表示要呼吸
.
<
/p>
该命题符号化为
?
x
(
M
(
x
)
?
H
(
x<
/p>
))
(3)
设个体域为数的集合
.
R
(
x
)
：
x
表示实数<
/p>
Q
(
x
)
：
x
表示有理数
.
该命题符号化
?
x
(
R
(
x
)<
/p>
?
Q
(
x
))
.
例
2.2
指出下列公式
?
x
?
y
(
R
(
x
,
y
)
?
L
(
y
,
z
))
?
?
xH
(
x
,
y
< br>)
中量词的每次出现辖域，并指出变元的每次出现是约
束出现，还是自由出现，
以及公式的约束变元，自由变元
.
解
在公式
?
x
?
y
(
R
(
x
,
y
)
?
L
(
y
,
z
))
?
?
xH
(
x
< br>,
y
)
中，
?
x
只有一次出现，辖域是
?
y
(
R
(
x
,
y
)
?
L
(
y
< br>,
z
))
；
?
y
只有一次出现，辖域是
R
(
x
,
y
)
?
L
(
y
,
z
)
< br>；
?
x
只有一次
出现，辖域是
H
(
x
,
y
)
.
变元
x
在公式
?
x
?
y
(
R
(
x
,
< br>y
)
?
L
(
y
,
z
)
)
?
?
xH
(
x
,
y
)
中有四次
出现，其中第一次出现是在
?
x
中，是约束出现；第二次出现是在
?
x
的辖域中，
也是约束出现；第三次出现是
在
?
x
中，也是约束出现；第四次出现
是在
?
x
的辖
域中，也是约束出现
.
这四次出现都是约束出现，所以
x
是该公式的约束变元
.
不是该公式的自由变元
.
变元
y
在公式
?
x
?
y
(
R
(
x
,
y
)
?
L
(
y
,
z
))
?
?
xH
(
x
,
y
)
中有
四
次出现
.
其中第一次是在
?
y
中的出现，是约束出现；第二次出现和第三
次出现
是在
?
y
的辖域中的出现，也是约束出现；第四次出现是自由出现
. y
在该公式中
有三次约束出现，一次自由出现，因此变元
y
既是该公式的约束变元，也是自
由变元
.
变元
z
在公式
?
x
?
y
(<
/p>
R
(
x
,
y
)
?
L
(
y
,
z
))
?
?
xH
(
x
,
y
)
中只有一次自由出现，
所以
z<
/p>
是该公式的自由变元
.
注意，由例
2.2
< br>看到，同一个个体变项，在同一个公式中，既可以是约
束出现，也可以是自由出现
，这种情况有时会造成一些混淆，带来不变
.
要改
变这种情况，使一个个体变项在同一个公式中，不同时既是约束出现，又是自
由出现，采取换名规则或代入规则
.
例
2.3
给定解释
I
：
①
D
＝
{2,3};
②
D
中特定
元素
a
=2
；
③
函数为
f
(
2
)
?
3
,
f
(
3
)
?
2
④
谓词
F
(
x
)
为
F
(2)=0,
F
(3)=1
G
(
x
,
y
)
为
G
(2,2)=
G
(2,3)=
G
(
3,2)=0,
G
(3,3)=1
L
(
x
,
y
)
为
L
(2,2)=
L
(3,3)=1,
L
(2,3)=
L
(3,2
)=0
4
求在解释
I
下各公式的真值
.
(1)
?
xF
(
x
)
?
< br>G
(
x
,
a
)
;
(2)
?
x
?
yL
(
x
,
y
)
；
解
设所求
二个公式分别记作
A
，
C.
有
(<
/p>
1
)
A
?
(
F
(
2
)
?
G
(
2
,
2
))
< br>?
(
F
(
3
)
?
G
(
3
,
2
))<
/p>
?
(
0
?
0
)
?
(
1
?
0
)
?
0
?
0
?
0
(
2
)
C
?
?
yL
(
2
,
y
)
?
?
yL
(
3
,
y
)
?
{
L
(
2
,
2
)
?<
/p>
L
(
2
,
3
))
?
{
L
(
3
,
2
)
?
L
< br>(
3
,
3
)}
?
(
1
?
0
)<
/p>
?
(
0
?
1
)
?
1
?
1
?
1
和命题逻辑一样，在谓词逻辑中，有的公式在任何解释下都真，也有的
公式在任何解释下都假
.
以此，把公式分为
三类：在任何解释下公式
A
为真，或
者
公式
A
的真值表全为
1
，这就是永真式；在任何解释下公式
A
为假，或者公<
/p>
式
A
的真值表全为
0
，这就是永假式；公式
A
不总是假
，或者公式
A
的真值表
至少有一个
1
，这就是可满足式
.
由此可见，永真式也是可满足式
.
例
2.4
讨论公式
?
x
?
yF
(
x
,
y
)
?
?
y
?
xF
(
x
,
y
)
的类型
.
证明
用
A
表示该公式
.
取解释
I
如下：个体域为整数集，
F
(
x
,
y<
/p>
)
：
x
?
y
，在<
/p>
I
下，若
A
的前
件为
真，但后件为假，所以
A
为假，这
说明
B
不是永真式；
再取解释
I
?
：个体域认为仍
为整数集，
F
(
x
,
y
)
：
x
=
y.
在解释
I
?
下，当
A
的前件为
真时，后件为真
.
故<
/p>
A
为真，这又说明
A
不是永假式
.
综上所述，
A
是可满足式
.
由例
2.
4
可知，量词的次序不能随便颠倒
.
例
2.5
将公式
F
?
x
(
A
(
x
)
?
B
(
x
,
y
))
?
(
?
yC
(
y
)
< br>?
?
zD
(
y
,
z
))
化为前束范式
.
解
①消去联结词
?
(0
?
，
??
)
；
F
?
?
(
?
x
(
?
A
(<
/p>
x
)
?
B
(
x
,
y
))
?
(
??
yC
(
y
)
?
?
zD
(
y
,
z
))
< br>
②
将联结词
?
移至原子公式之前
.
F<
/p>
?
?
x
?
(
?
A
(
x
)
?
B
(
x
,
y
))
?
(
?
y
?
C
(
y
)
?
?
zD<
/p>
(
y
,
z
))
?
?
x
(
A
(
x
)
?
?
B
(
x
< br>,
y
))
?
(
?
y
?
C
(
y
)
?<
/p>
?
zD
(
y
,
z
))
③
换名
F
?
?
x
(
A
(
x
)
< br>?
?
B
(
x
,
y
))
?
(
?
t
?<
/p>
C
(
t
)
?
?
zD
(
y
,
z
))
④
把量词提到整个公式的前面
F
?
?
x
?
t
?
z
(
A
(
x
)
?
?
B
(
x
,
y
))
?
?
C
(
t
)
?
D
(
y
,
z
))
为所求前束范式
.
重要的是弄清楚前束范式的定义，求前束范式主要是利用基本等值式、蕴含式和换名
规则，把一个谓词公式化为前束范式，虽然前束范式是谓词公式的一种标准形式，但是一
般一个谓词公式的前束范式并不是唯一的
.
例
2.6
试
证
(
P
?
Q<
/p>
)
?
R
?
(
R
?
P
)
?
(
S
?
P
)
-
-
-
-
-
-
-
-
-
上一篇：华为三层交换机如何限制某端口的流量？
下一篇：中兴ZXR10配置说明