g = { B/y}
3、合一算法
分歧集（或不一致集合）的定义。 设有一非空有限公式集合 F = {F1 , … , Fn}，从 F 中各个公式的第一个符号同时向右比较，直到发现 第一个彼此不尽相同的符号为止，从 F 中的各个 公式中取出那些以第一个不一致符号开始的最大的 子表达式为元素，组成一个集合 D ，称为 F 的分 歧集（不一致集合）。 其中，F i ( i=1 , … , n)是原 子谓词公式
注意：
置换的合成满足结合律，不满足交换律。
(s1s2)s3 = s1(s2s3)
s1s2 ≠ s2s1
(满足结合律）
（不满足交换律）
例： s1={z/x , w/y} s2={A/y}
s1s2={z/x , w/y , A/y}={z/x , w/y}
s2s1={A/y, z/x , w/y}={A/y , z/x}
s3={q(z)/x, A/y}
s4={c/x, A/y}
P[x, f(y), B]s3=P[q(z), f(A), B]
P[x, f(y), B]s4=P[c, f(A), B]
置 换 的 合 成 ： 设 θ＝{t1/x1,
换：
…,tn/xn} 和 λ＝
{s1/y1, …,sm/ym}是两个置换，则θ和λ的合成是如下置
个 s’，使得
s = g s’ 或者 {Ei} s = {Ei} g s’ 则 称 g 是 {Ei} 的最通用（最一般）的合一者， 记作mgu。
例：
s = {A/x , B/y} 是表达式集合
{P[x , f(y) , B] , P[x , f(B) , B]} 的一个合一者，该集合的最一般的合一者是：
{t1λ/x1 ,…, tiλ/xi ,…, tnλ/xn, s1/y1, …, sn/ym }
其中，yj 是 {x1,…,xn} 之一者消去，对于任何 tjλ=xj 者消去，并记成θλ。
如何求 tiλ : λ＝{s1/y1 , … , sm/ym}
如果 ti 出现 {y1, …., ym}中的变量 yi ， 则用其对 应的项 si 来代替。
人
工
智
能
Artificial Intelligence (AI)
曲维光 wgqu@
南京师范大学计算机学院
第2章 知识表示方法
2.1 谓词逻辑法
2.2 状态空间法
2.3问题归约法
2.1 谓词逻辑法 数理逻辑（符号逻辑）是用数学方法研究形式逻 辑的一个分支。它通过符号系统来表达客观对象 以及相关的逻辑推理。常用的是命题逻辑和谓
2、合一
当某一个置换 s 作用于表达式集合 {Ei} 的每一个元
素，此时我们用 {Ei}s 来表示置换例子的集合。如
果存在一个置换 s ，使得
E1s = E2s = … = Eis = …
则我们称表达式集合 {Ei} 是可合一的，并称 s 为 {Ei} 的合一者。原因是它的作用是使集合 {Ei} 成 为单一形式。 其中，Ei 是原子谓词公式。
④若 A 是合适公式， x 为 A 的自由变元（变量），
则（x）A 和（x）A 都是合适公式。 ⑤只有按上述规则求得的公式才是合适公式。
例：任何整数或者为正或者为负。
数学表达：对于所有的 x，如果 x 是整数，则 x 或
者为正、或者为负。
记作： I(x)：“ x 是整数”。
P(x)：“ x 是正数”。
ti 是与 vi 不同的项。
例或例子的定义：
设 θ ＝{ t1/v1 , …, tn/vn }
为一个置换，E是一个原子谓词公式。则Eθ 表
示将E中的 vi 同时用 ti（i=1,…,n）代入后所得 到的结果，Eθ 称为E的一个例子。
例 ：表达式（原子谓词公式）P[x,f(y),B]的四个置
换及其对应的四个例子 （B是常量） P[x,f(y),B] s1={z/x, w/y} s2={A/y} P[x, f(y), B]s1=P[z, f(w), B] P[x, f(y), B]s2=P[x, f(A), B]
一阶谓词 ：只允许对变量施加量词，不允许对
谓词和函数施加量词。
2.1.2 谓词公式
1、谓词公式的定义 利用连词和量词可以将原子（谓词）公式组成复
合谓词公式，称之为分子谓词公式、谓词合适公
式、谓词公式、合适公式。
（谓词）合适公式 的（递归）定义：
①原子（谓词）公式是合适公式。
②若 A 是合适公式，则 ～A 也是合适公式。 ③若 A 和 B 是合适公式，则 A∧B 、A∨B 、 AB 、AB 也是合适公式。
谓词是指个体（客体）所具有的性质或者若干个体
之间的关系。用大写字母来表示。
个体是可以具体的（如，小张、3、5）也可以是抽 象的（如，x, y）。
例： 小明是学生，A表示是“是学生”，x表示“小
明”，记作A(x)。
x大于y，G表示“大于”，记作G（x, y）。
论域：由个体组成的集合。
（个体）变量：定义在某一个论域上的变量。用 x, y, z 来表示。
函数（或函词）：以个体为变量，以个体为值的
函数。一般用小写字母来表示，例如 f(x), f(x,a)。
如果谓词有 n 个变量，称之为 n 元谓词，并约定
0 元谓词就是命题（谓词的特例）。
如果函数有 n 个个体，称之为 n 元函数，并约定 0 元函数就是常量。常量习惯上用小写字母来表 示，如a, b, c。
T
F
T
F
T
命题变元：用符号P、Q等表示的不具有固定、具
体含义的命题。它可以表示具有“真”、“假”含
义的各种命题。
命题变元可以利用联结词构成所谓的合适公式。
合适公式的定义 ①若P为原子命题，则P为合适公式，称为原子公
式。
②若P是合适公式，则～P也是一个合适公式。
③若P和Q是合适公式，则P∧Q、 P∨Q 、PQ 、 PQ都是合适公式。 ④经过有限次使用规则1、2、3，得到的由原子公 式、联结词和园括号所组成的符号串，也是合适 公式。
⑤ “” 表示 “等价” 复合命题“PQ”为真，当且仅当P、Q同时为真、 或者同时为假。 联接词的优先顺序：非～ 、合取∧ 、析取∨ 、 蕴含 、等价
注：可以用括号表示优先级
真值表
P F F Q F T ～P T T
P∧Q P∨Q PQ PQ
F F
F T
T T
T F
T
T
F
T
N(x)：“ x 是负数”。
谓词公式：
（x）（I(x) (P(x) ∨ N(x))）
2、合适公式的性质 如果 P 和 Q 是合适公式，则由这两个合适公 式构成的合适公式的真值表与前面介绍的真值
表相同。
如果两个合适公式的真值表相同，则我们称这
两个合适公式是等价的，可以用“”来表示。
对于命题合适公式和谓词合适公式有下列等价关系： ①否定之否定：
⑩ (x)P(x) 等价于 (y)P(y)
(x)P(x) 等价于 (y)P(y)
注释：这两个关系说明，在一个量化的表达式中 的约束变量是一类虚元，它们可以用任何不在表
达式中出现的其它变量来代替。
2.1.3 置换与合一
1、置换
置换的定义：形如
{ t1 / v 1 , … , tn / v n } 的集合，称为一个置换，其中 vi 是不同的变量，
～（～P） 等价于 P
② P∨Q 等价于 ～PQ ③狄.摩根定律 ～（P∨Q）等价于 ～P∧～Q ～（P∧Q）等价于 ～P∨～Q
④分配律 P∧(Q∨R) 等价于 (P∧Q)∨(P∧R) P∨(Q∧R) 等价于 (P∨Q)∧(P∨R)
⑤交换律
P∧Q 等价于 Q∧P P∨Q 等价于 Q∨P
⑥结合律
例： θ= {t1/x1 , t2/x2}＝{f(y)/x , z/y} λ= {s1/y1 , s2/y2 , s3/y3} = {a/x , b/y , y/z}
θλ={t1λ/x1 , t2λ/x2 , s1/y1 , s2/y2 , s3/y3 }
={f(b)/x , y/y , a/x , b/y , y/z} ={f(b)/x , y/z}
③其它表达式都不是原子公式
原子公式的例子 1、原子公式：P（原子命题）
2、项：x, a, f(x, a)，谓词：P
原子公式：P(x, a, f(x,a))
2、连词和量词
联结词（连词）就是命题逻辑中的五个，它们的
含义也是一样的。
两个量词：
①全称量词，记作“x”,含义是 “对每一个x” 或“对一切x”。 ②存在量词，记作“x”，含义是 “存在某个
作为一个不可分割的整体。
例如：雪是黑的 命题逻辑具有较大的局限性，不合适于表达 比较复杂的问题。
例：
所有科学都是有用的（假设1）。
数理逻辑是科学（假设2）。 所以，数理逻辑是有用的（结论）。 很明显，我们无法用两个假设推断出结论。
谓词逻辑是命题逻辑的扩充和发展。它将一个原
子命题分解成客体和谓词两个组成部分。 例如： 雪 是黑的
项的定义：
①常量是项 ②变量是项
③如果 f 是n元函数，且t1 ,…, tn(n≥1)是项，则
f (t1 ,…, tn)也是项 ④所有的项都必须是有限次应用上述规则产生的
项的例子：
常量：a
变量：x 函数：f(x,a)
g(f(x,a))
原子（谓词）公式的（递归）定义：
①原子命题是原子公式
②如果t1,…,tn(n≥1)是项，P是谓词，则P(t1,…,tn) 是原子公式
词逻辑
谓词逻辑是数理逻辑的基本形式，是基于谓词
分析的一种形式化（数学）语言
人工智能中的谓词逻辑法是指用一阶谓词