人工智能谓词演算.ppt

人工智能谓词演算
第1页，共32页，2022年，5月20日，11点1分，星期日
第一节 一阶谓词逻辑
命题：凡可确定真假的陈述句称为命题
可以取值“真”（T）或“假”（F）
在一定的条件下，只能取其中一个值
例：
（1）不唯一
析取范式： （ P66 定义5）
A为析取范式，B1 ∨ B2 ∨ … ∨ B n ,其中 Bi 形如L1 ∧ L2 ∧ … ∧ Lm, L j为原子公式或其否定
例：（P（x） ∧ Q（y）） ∨ （ ¬ P（x） ∧ Q（y） ∧ R（x，y）） ∨ …
任一谓词公式均可化为与之等价的析取范式，但一般不唯一
*
第9页，共32页，2022年，5月20日，11点1分，星期日
谓词公式的永真（有效）、永假（不可满足）、可满足： （ P58定义6、7）
与个体域有关
谓词公式之间的关系
常用逻辑等价式
注意与的区别，是等价符号，说明两个谓词公式之间的等价性，是逻辑连接词，是谓词公式的组成部分
常用逻辑蕴涵式 P60
注意与的区别， 是推导符号，说明由左边的谓词公式可以推导出右边的谓词公式， 是逻辑连接词，是谓词公式的组成部分
*
第10页，共32页，2022年，5月20日，11点1分，星期日
自然演绎推理：
（1）将自然语言命题转化为谓词公式
（2）利用上面的逻辑等价式和逻辑蕴涵式，可以进行推理，得出一些隐含在谓词公式中的结论
例：P61 例4-6
自然演绎推理实施困难，推理规则太多、应用规则需要很强的模式识别能力、中间结论呈指数增长
引入新的推理技术——归结演绎推理技术
归结——消解（Resolution），由Robinson于1965年提出，大大推动了自动定理证明的发展
*
第11页，共32页，2022年，5月20日，11点1分，星期日
练习：
1、设已知以下事实：
A
B
A→C
B∧C→D
D→Q
求证：Q为真。
*
第12页，共32页，2022年，5月20日，11点1分，星期日
证明：
因为
A，A→C  C
B，C  B ∧C
B∧C，B∧C→D  D
D，D→Q  Q
所以 Q为真
*
第13页，共32页，2022年，5月20日，11点1分，星期日
2、设已知如下事实：
（1）凡是容易的课程小王都喜欢。
（2）C班的课程都是容易的。
（3）ds 是C班的一门课程。

求证：小王喜欢 ds 这门课程。
*
第14页，共32页，2022年，5月20日，11点1分，星期日
证明： 事实  x （ EASY（x）→LIKE（Wang，x））
 x （C（x）→ EASY（x））
C（ds）
LIKE（Wang，ds）
因为  x （C（x）→ EASY（x））
所以 C（ds）→ EASY（ds）
所以 C（ds）， C（ds）→ EASY（ds） EASY（ds）
因为  x （ EASY（x）→LIKE（Wang，x） ）
所以 EASY（ds） →LIKE（Wang，ds）
所以 EASY（ds）， EASY（ds）→LIKE（Wang，ds）
 LIKE（Wang，ds）
*
第15页，共32页，2022年，5月20日，11点1分，星期日
第二节 归结演绎推理
建立子句集
文字、子句、空子句 （P62 定义1）
建立谓词公式 G 的子句集合 （P62定义2）
例：
例：P63 例2 有关消去存在量词
子句集中各子句的关系是 合取 ∧
经过变换后的子句集 S ，与谓词公式 G 并不等价
子句集的不可满足 （P64 定义3）
G不可满足当且仅当S不可满足（P64 定理1），即G永假是S永假的充分必要条件
*
第16页，共32页，2022年，5月20日，11点1分，星期日
练习：
P93 1、
（1）{p(x,y),Q(u,v)}
（2）{¬p(x,y)∨Q(x,y)}
（3）{P(x,f(x))∨ ¬Q(x,f(x))∨R (x,f(x))}
（4）{¬P(x,z)∨Q(x,y)∨R(x,y)}
（5）{P(a,b,z,f(z),v,g(z,v)),
Q(a,b,f(t),s,g(t,s))∨ ¬ R(a,t,g(t,s))}
*
第17页，共32页，2022年，5月20日，11点1分，星期日
命题逻辑中的归结原理
在定理证明系统中，已知一公式集F1，F2，…，Fn，要证明W（定理）是否成立，即要证明W是公式集的逻辑结果，有两