人工智能：3.2    推理的逻辑基础

 

3.2.1        
谓词公式的解释

在命题逻辑中，命题公式的一个解释就是对该命题公式中各个命题变元的一 次真值指派 。有了命题公式的解释 ，就可以根据这个解释求出该命题公式的真值。但谓词逻辑则不同，由于谓词公式中可能包含有个体常量、个体变元或函数，因 此，不能像命题公式那样直接通过真值指派给出解释。必须先考虑个体常量和函
数在个体域下的取值，然后才能根据常量与函数的具体取值为谓词分别指派真  假。下面给出谓词公式的解释的定义。

设 D 是谓词公式 P 的非空个体域，若对 P 中的个体常量、函数和谓词按如

下规定赋值 ：

(1)      为每个个体常 量指派 D 中的一个元素 ，

(2)      为每个 n 元函数指派一个从 D
ⁿ 到 D 的一个映射 ，

(3)     
为每个 n 元谓词指派一个从 D ⁿ到{F,T} 的一个映射， 则称这些指派为 P 在 D 上的一个解释。

例
3.1    设个体域 D
＝ {1 ，2} ，求公式 A
＝( “ x)( $ y)P (x,y) 在 D 上的解释，并指出在每一种解释下公式 A
的真值。

解   由于公式 A 中没有包含个体常量和函数，因此可以直接为谓词指派真

 

・45 ・

人工智能技术与方法

值，设真值指派如下 ：

 

P(1,1)	P(1,2)	P(2,1)	P(2,2)
T	F	T	F

这就是公式 A 在 D
上的一个解释。从这个解释可以看出 ： 当 x ＝ 1
、y ＝ 1
时，有 P (x ，y
) 的真值为 T
；

当 x
＝ 2 、y ＝ l
时，有 P (x ，y
) 的真值为 T
。

即对 x 在 D 上的任意取值，都存在 y ＝1 使 P (x ，y ) 的真值为 T ，因此，在此解释下公式 A 的真值为 T 。

需要注意，一个谓词公式在其个体域上的解释不是唯一的。例如，对于公式

A ，若给出另一组真值指派 ：

 

P(1,1)	P(1,2)	P(2,1)	P(2,2)
T	T	T	F

这也是公式 A 在 D 上的一个解释。从这个解释 可以看出 ： 当 x ＝ 1
、y ＝1 时，有 P
(x ，y ) 的真值为 T ；

当 x
＝ 2 、y
＝1 时，有 P
(x ，y ) 的真值为 F
。

同样，

当 x
＝ 1 、y
＝2 时，有 P
(x ，y ) 的真值为 T
；

当 x
＝ 2 、y
＝2 时，有 P
(x ，y ) 的真值为 F
。

即并非在 D
上的任意 x ，都能使 P (x
，y ) 的真值总是为 T
。因此，在此解释下公式

A 的真值为 F 。

实际上， A 在 D 上共有 16 种解释，这里就不再一一列举。

例 3. 2      设个体域 D
＝ {l ，2} ，求公式 B
＝ ( “ x)P (f (x )
，a)
在 D
上的解释，并指出在该解释下公式 A 的真值。

解  设对个体常量 a
和函数 f (x) 的真值指派如下：

 

a	f (1)	f (2)
1	1	2

对谓词的真值指派如下 ：

 

 

・46 ・

第 3 章   基本推理原理

 

P(1,1)	P(1,2)	P(2,1)	P(2,2)
T		F

这里，由于已知指派 a ＝ 1 ，所以 P (1 ，2) 和 P (2 ，2) 不可能出现，故没有给它们指派真值。上述指派是公式 B 在 D 上的一个解释。在此解释下，有以下情况
：

当 x ＝ 1 时 ，P (1 ， 1) ＝ T ；

当 x
＝ 2
时 ，P
(2 ， 1)
＝ T
。

即对
x 在 D
上的任意取值，且 a 指派为 1 时，都使 P
(f(x
) ，a)
的真值为 T
，因此， 在此解释 下公式 B 的真值为 T
。

由上面的例子可以看出，谓词公式的真值都是针对某一个解释而言的，它可能在某一个解释下真值为 T ，而在另一个解释下真值为 F 。

 

3.2.2        
谓词公式的永真性与可满足性

为了以后推理的需要，下面先定义谓词公式的永真性、永假性、可满足性与不可满足性。

如果谓词公式 P
对非空个体域 D 上的任一解释都取得真值 T ，则称 P
在 D 上是永真的 ；如果 P 在任何非空个体域上均是永真的，则称 P 永真。由此定义可以看出，要判定一个谓词公式为永真，就必须对每个非空个体域上的每个解释逐一进行判断。当解释的个数有限时，尽管工作量大 ，但毕竟还可以判定 ； 当解释个数无限时，就很难判定了。

对于谓词公式 P ，如果至少存在 D 上的一个解释，使公式 P 在此解释下的真

值为 T
，则称公式 P 在
D 上是可满足的。谓词公式的可满足性也称为相容性。如果谓词公式
P 对非空个体域
D 上的任一解释都取真值
F ，则称 P 在 D 上是永假的；如果 P
在任何非空个体域上均是永假的，则称 P
永假。谓词公式的永假性又称不可满足性或不相容性。

 

3.2.3        
谓词公式的范式

范式是公式的标准形式，公式往往需要变换为同它等价的范式，以便对它们作一般性的处理。在谓词逻辑中，根据量词在公式中出现的情况可将谓  词公式的

 

・47 ・

人工智能技术与方法

范式分为两种。

1.     前束范式

设 F 为一谓词公式，如果其中的所有量词均非否定地出现在公式的最前面， 而它们的辖域为整个公式，则称
F 为前束范式。一般地，前束范式可写成

(Q₁x ₁) ⋯ (
Q_nx _n)M(x ₁，x ₂ ，⋯， x _n)

其中， Q_i（
i ＝ 1 ， 2 ，⋯， n
）为前缀，它是一个由全称量词或存在量词组成的量词串， M (x
₁，x
₂ ，⋯， x
_n)
为母式，它是一个不含任何量词的谓词公式。例如，

( “ x)( “ y)( $ y)[P(x)∧Q(y,z)∨R
(x ,
z)]

2.   Skolem 范式

如果前束范式中所有的存在量词都在全称量词之前，则称这种形式的谓词公式为 Skolem 范式。例如， ( $
x)( $ z)( “ y)[P (x )∨Q(y ,z)∧R
(x ,z)]
是 Skolem 范式。

 

3.2.4        
置换与合一

在不同谓词公式中，往往会出现谓词名相同但其个体不同的情况，此时推理过程是不能
直接进行匹配的，需要先进行置换。例如，可根据全称固化推理和假言推理由谓词公式

W₁(A ) 和(
“ x)(W₁(x)
® W₂(x ))

推出 W₂(A ) 。谓词 W
₁(A ) 可看作是由全称固化推理推出的，其中 ，A 是任意个体常量。要使用假言推理，首先需要找到项 A
对变元 x 的置换，使 W₁(A ) 和 W₁(x) 一致。这种寻找项对变元的置换，使谓词一致的过程叫做合一的过程。下面讨论置换与 合一的有关概念与方法。

1.     置换

置换(Substitution)
可以简单理解为在一个谓词公式中用置换项 去替换变量。置换是形如

{t₁/x ₁ ，t₂/x₂ ，⋯， t _n/x _n}

的有限集合。其中， t₁ ， t₂ ，⋯， t _n是项；x ₁ ，x ₂ ，⋯ ，x
_n是互不相同的变元 ； t_i/x _i

表示用 t_i 置换 x
_i，并且要求 t_i 与 x
_i不能相同 ，x _i 也不能循环地出现在另一个
t_i 中。

 

・48 ・

第 3 章   基本推理原理

用项 A 替换函数表达式中的变量 x ，记作 Es ，即表示一个表达式 E 用一个置换 s

而得到的表达式的置换。例如，表达式 P [x
，f(y
) ，B ] 的 4
个置换分别为

s₁={z/x ， W/y }

s₂={A /y }

s₃={q(z)/x
，A /y }

s₄={C/x ，A
/y}

用 Es 来表示一个表达式 E 用置换 s 所得到的表达式的置换，于是，可分别得到
P [x ，f(y ) ，B
] 的 4
个置换的例子 ：

P
[x ，f(y ) ，B
]s₁=P
[z ，f( W) ，B
]

P
[x ，f(y ) ，B
]s₂=P
[x ，f(A ) ，B
]

P [x ，f(y ) ，B
]s₃=P
[q(z) ，f(A ) ，B
]

P
[x ，f(y ) ，B
]s₄=P
[C ，f(A ) ，B
]

2.     置换的合成

设θ={t₁/x₁ ， t₂/x₂ ，⋯， t_n/x_n} ，λ={u₁/y ₁ ，u₂/y ₂ ，⋯， u_n/y _n 
} 是两 个置换，则θ与λ的合成也是一个置换，记 作θ・λ。它是从集合

{t₁ λ/x ₁ ，t₂ λ/x ₂ ，⋯， t_n λ/x _n ，u₁/y ₁ ，u₂/y ₂ ，⋯， u_n/y _n }

中删去以下两种元素 ：

(1) 
当
t_iλ＝ x _i 时，删去 t_iλ/x_i  
(i ＝1 ， 2 ⋯， n) ，

(2) 当 y _i Î{x ₁ ，x ₂ ，⋯ ，x _n} 时，删去 u_j/y_j ( j ＝1 ， 2 ，⋯， m ) ， 最后剩下的元素所构成的集合。

例如，设θ={ f (y )/x ，z/y } ，λ={a/x ，b/y ，y /z} ，求θ与λ的合成。先求集合

{
f (b/y)/x ，(y /z)/y
，a/x ，b/y ，y
/z}

即

{ f (b)/x
，y /y ，a/x ，b/y ，y
/z}

其中 ，f (b)/x 中的 f(b) 是置换λ作用于 f(y
) 的结果；y /y 中的 y
是置换λ作用于 z 的结果。在该集合中 ，y /y
满足定义中的条件(1) ，需要删除；a/x ，b/y
满足定义中的条

件(2) ，即 x
， y 置换已包含于θ中， 也需要删除。最后得到

θ・λ={f(b)/x ，y /z}

置换满足结合律，但一般不满足交换律。设 E 为一表达式， s₁ ，s₂ 和 s₃ 为三个置

 

・49 ・

人工智能技术与方法

换，则有

 

 

3.     合一

 

 

(Es ₁)s₂=E
(s₁s₂)

(s₁s₂s₃)=s₁(s₂s₃)

s1 s2 ≠s2 s1

合一(Unifier) 可以简单地理解为寻找项对变量的置换，使两个谓词公式一致。设有公式集 F ＝ {F ₁，F
₂ ，⋯ ，F
_n}
，若存在一个置换θ，可使 F
₁ θ=F
₂θ= ⋯F _nθ，则称θ是 F
的一个合一者，称 F ₁ ，F ₂ ，⋯， F _n是可合一的。例如，设有公式集 F ＝

{P (x ，y
， f(y )) ，P
(a ， g(x ) ，z)} ，则θ={a/x ，g(x )/y ， f(g(a))/z}
是它的一个合一。

4.     最一般合一

一般来说，一个公式集的 合一不是唯一的。设 σ是公式集 F 的一个合一，如果对  F   的任一个合一 θ都存在一个置换λ，使得 θ=σ・λ，则称σ是一个最一般合一 (Most General Unifier ， MGU) 。一个公式集的最一般合一是唯一的。若用最一般合一去置换那些可合一的谓词公式，可使谓词公式产生的例更一般化，这有利于归结过程的灵活使用。下面给出 寻找到公式集的 最一般合一的 算法 ：

(1)      同时从每个公式的第一个符号向右开始比较 ；

(2)      直到发现第一个不相同的符号为止；

(3)      用其元素组成集合，称分歧集 ；

(4)      如此下去，可以找到多个分歧 集 ；

(5)      这些分歧集的合成，就是公式集的最一般合一。

例 3.3    求公式集 F
={P (a ，x ， f (g(y ))) ，P (z ，h(z ， u) ，f (u))} 的最一般合一。

解  (1) 取 F 0 =F ，F 0 不是单一表达式，分歧集 D 0 ={a ，z} ，则置换θ₁={a/z} ，

得

F 1 =F
0 θ₁= {P (a ，x
， f (g(y))) ，P
(a ， h(a ，u) ， f
(u))}

(2)   F 1  不是单一表达式 ，分歧集 D 1 ={x ，h(a ，u)} ，则置换θ2 = θ1 {h(a ，u)/x } ={a/z ，

h(a ，u)/x } ，得

F 2 =F1θ2={P (a ，h(a ， u) ， f (g(y ))) ，P (a ， h(a ， u) ， f(u))}

(3)   F 2  不是单一表达式，分歧集 D 2 ={g(y ) ，u} ； 则置换θ3 = θ2 ，{ g(y)/u}=

{a/z ， h(a ， g(y))/x ，g(y )/u} ，得

 

・50 ・

第 3 章   基本推理原理

F 3 =F2θ3={P (a ，h(a ， g(y )) ，f (g(y ))) ，P (a ， h(a ，y ) ， f (g(y)))}

因此， θ3 ={a/z ，h(a ， g(y ))/x ，g(y )/u}是 F 
的最一般合一。 另外， 表 3.1 给出几个可合一集及最一般合一的例子。

表 3.1 最一般合一的例子

 

公式集	最一 般合一
{ P(x) ， P( A)}	{ A/ x}
{ P(f (x) ， y ， g( y)) ， P(f (x) ，z ， g (x))}	{ x/ y ， x/ z }
{ P(f (x ，g (A ， y )) ， g(A ， y )) ， P (f (x ，z ) ，z ) }	{ g(A ， y)/ z }