人工智能谓词演算.ppt

第2讲 基于谓词逻辑的机器推理,一阶谓词逻辑 归结演绎推理 归结原理的应用 Horn子句与Prolog程序设计,2,第一节 一阶谓词逻辑,命题：凡可确定真假的陈述句称为命题 可以取值“真”（T）或“假”（F） 在一定的条件下，只能取其中一个值 例： （1）北京是中国的首都 （2）3 + 2 10 （3）1 + 11 = 100 （根据制数） （4）禁止吸烟 （祈使句） （5）本命题是假的 （悖论）,3,谓词：是用来刻画个体词的性质或个体词之间的关系的词（带参量的命题叫谓词） n 元谓词，P（x1, x2, x3, , xn） P 是谓词符号，代表一个确定的特征（一个参量）或关系（多个参量） x1, x2, x3, , xn 称为参量或项（个体常元或个体变元） 论述域（个体域）：个体变元的取值范围 例： 北京是一个城市 CITY（北京） x 是人 HUMAN（x） A是B的兄弟 兄弟（A，B） x 大于 y G（x，y） 不带个体变元的谓词公式叫命题，命题是谓词公式的特例,4,逻辑连接词：研究单个谓词是不够的，还必须研究多个谓词之间的关系，这需要引入逻辑连接词 ：否定词 A读为“非A”，当A为真时， A为假，当A为假时， A为真 ：合取词 A B读为“A并且B”，当且仅当A和B都为真时， A B为真，否则A B为假 ：析取词 A B读为“A或者B”，当且仅当A和B都为假时， A B为假，否则A B为真,5,：蕴涵词 A B读为“若A则B”，当且仅当A为真，且B为假时， A B为假，否则A B为真 在A B中，A称为前件，B称为后件 ：等值词 A B读为“A等值于B”，当且仅当A和B同为真或同为假时， A B为真，否则A B为假,6,量词：有些陈述句包含表示数量的词，如“所有”、“任一”、“存在”、“至少有一个”等，为了表示这样的陈述句，需引入新的符号，称为量词 全称量词 （ x ）表示 “ 对于所有的 x ” 例： 凡是人都有名字 （ x ）（M （x） N（x） （ x ）A（x） A（a1） A（a2） A（an），若论域为有限集合， 且a1、 a2、 、an是论域中的所有个体 存在量词 （ x ）表示 “ 对于某个 x ” 例： 存在不是偶数的整数 （ x ）（G （x） E（x） （ x ）A（x） A（a1） A（a2） A（an） 例：见P56例13,7,项： （ P64 定义1） （1）个体常元和个体变元都是项 （2）f (t1, t2, , tn)是项，f 是 n 元函数， t1, t2, , tn 是项 （3）只有有限次使用（1）、（2）得到的符号串才是项 原子公式： （ P64 定义2） 设 P 为 n 元谓词符号， t1, t2, , tn 是项，则P（ t1, t2, , tn ）称为原子谓词公式，简称原子公式,8,谓词公式： （ P56 定义3） （1）原子公式是谓词公式 （2）若A、B是谓词公式，则 AB、AB、 A、AB、A B、 x A、 x A也是谓词公式 （3）只有有限次应用（1）、（2）生成的公式才是谓词公式 谓词公式又称为谓词逻辑中的合式公式，记为 Wff (well-formed formula) 几个概念： 辖域（P57）：紧接于量词之后被量词作用的（说明的）谓词公式称为该量词的辖域 指导变元、约束变元和自由变元 （ P57） 改名规则（ P57），保证一个变元或者是约束变元，或者是自由变元 例： x （H（x） G（x, y） x A（x） B（x）,9,合取范式： （ P58定义4） A为合取范式，B1 B2 B n ,其中 Bi 形如L1 L2 Lm, L j为原子公式或其否定 例：（P（x） Q（y） （ P（x） Q（y） R（x，y） 任一谓词公式均可化为与之等价的合取范式，但一般不唯一 析取范式： （ P66 定义5） A为析取范式，B1 B2 B n ,其中 Bi 形如L1 L2 Lm, L j为原子公式或其否定 例：（P（x） Q（y） （ P（x） Q（y） R（x，y） 任一谓词公式均可化为与之等价的析取范式，但一般不唯一,10,谓词公式的永真（有效）、永假（不可满足）、可满足： （ P58定义6、7） 与个体域有关 谓词公式之间的关系 常用逻辑等价式 P59表3.1 注意与的区别，是等价符号，说明两个谓词公式之间的等价性，是逻辑连接词，是谓词公式的组成部分 常用逻辑蕴涵式 P60 表3.2 注意与的区别， 是推导符号，说明由左边的谓词公式可以推导出右边的谓词公式， 是逻辑连接词，是谓词公式的组成部分,11,自然演绎推理： （1）将自然语言命题转化为谓词公式 （2）利用上面的逻辑等价式和逻辑蕴涵式，可以进行推理，得出一些隐含在谓词公式中的结论 例：P61 例4-6 自然演绎推理实施困难，推理规则太多、应用规则需要很强的模式识别能力、中间结论呈指数增长 引入新的推理技术归结演绎推理技术 归结消解（Resolution），由Robinson于1965年提出，大大推动了自动定理证明的发展,12,练习： 1、设已知以下事实： A B AC BCD DQ 求证：Q为真。,13,证明： 因为 A，AC C B，C B C BC，BCD D D，DQ Q 所以 Q为真,14,2、设已知如下事实： （1）凡是容易的课程小王都喜欢。 （2）C班的课程都是容易的。 （3）ds 是C班的一门课程。 求证：小王喜欢 ds 这门课程。,15,证明： 事实 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）,16,第二节 归结演绎推理,建立子句集 文字、子句、空子句 （P62 定义1） 建立谓词公式 G 的子句集合 （P62定义2） 例：P62例3.7 例：P63 例2 有关消去存在量词 子句集中各子句的关系是 合取 经过变换后的子句集 S ，与谓词公式 G 并不等价 子句集的不可满足 （P64 定义3） G不可满足当且仅当S不可满足（P64 定理1），即G永假是S永假的充分必要条件,17,练习： 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),18,命题逻辑中的归结原理 在定理证明系统中，已知一公式集F1，F2，Fn，要证明W（定理）是否成立，即要证明W是公式集的逻辑结果，有两种方法： 1、证明 F1 F2 Fn W 为永真式（见上一节） 2、（反证法）证明 F1 F2 Fn W 永假，即要证明对应子句集永假（不可满足） 几个概念：（P64 定义4、5）互补文字、归结式（消解式）、亲本子句、消解基 例：例3.9 归结式是其亲本子句的逻辑结果 P64 定理2 单向推导关系,19,归结原理： C1 C2 （C1-L1） （C2-L2） 互补文字进行归结得空子句（L L =），另L L = F（假），故空子句即永假子句 关于消解前后子句集的可满足性 P65 推论 （证明略） 故：要证明一子句集永假，可以通过对子句集应用消解原理得到空子句来证明 运用归结原理证明定理的例子：P65 例11、12 * 归结过程可以用一棵 归结演绎树 表示,20,替换与合一 为了对谓词逻辑的子句集运用消解原理，即在子句集合中寻找含互补文字的子句对，必须对子句进行替换合一操作 替换：P66 定义6 t1/x1， t2/x2， ，t n /x n 对表达式的替换过程 P66 定义7 表达式 项、原子公式、文字、子句 两个替换的乘积 P66-67 定义8 一部分仍是的替换对，只是的项被作了替换；另一部分是中与不同的那些变量对 例：例3.13 替换的乘积满足结合律,21,合一：P67 定义9 是 S 的一个合一 其中S 是一个原子谓词公式集， 是一个替换 满足 F1 = F2 = =Fn 一个公式集的合一一般不唯一 最一般的合一：P67 定义10 是 S 的一个合一 对于S 的任何一个合一，存在替换，使 = 称为S 的最一般（最普通、最简单）合一 MGU 例：例3.14 MGU 的替换限制最少，所产生的例更一般化，这有利于归结过程的灵活使用 一个公式集的最一般合一也可不唯一，如 P（x），P（y），y/x、 x/y都是它的最一般合一,22,差异集：P67 定义11 针对具有相同谓词名的原子公式集 例：例3.15 合一算法：求非空有限具有相同谓词名的原子公式集的最一般合一 P67-68 合一算法是解决两个表达式匹配的问题，两个表达式都可以含有变量，通过算法求得 MGU 并进行替换后就可以得到匹配的例 例：例16、17 合一定理： P68-69 定理3 可合一公式集一定存在最一般合一，用上述合一算法求得,23,谓词逻辑中的归结原理 归结过程： 若S 中的两子句间有相同互补文字的谓词，但它们的项不同，则必须找出对应的不一致项 进行变量替换合一操作，使它们的对应项一致 求归结式看能否导出空子句 几个概念：（P69 定义12）谓词逻辑中的二元归结式（二元消解式）、亲本子句、消解文字 例：例18、19 子句用文字的集合表示，各文字之间的关系是 析取 首先对子句内部的可合一文字进行合一,24,因子、单因子 （ P69 定义13） 例：例14 子句的归结（消解）式 （ P69 定义14） 定理：谓词逻辑中的消解式是它的亲本子句的逻辑结果 谓词逻辑中的归结原理：C1 C2 （C1- L1 ）（ C2 - L2 ） 关于消解前后子句集的可满足性 P70 （同命题逻辑） 故：要证明F1 F2 Fn W 为永真式，可证明 F1 F2 Fn W 永假，这又可以通过对对应子句集应用消解原理得到空子句来证明（同命题逻辑）,25,例：例15、16 定理：归结原理的完备性 （ P71） 练习： P93 3、（1）-（5）,26,第三节 归结原理的应用,例3.23：P71 例3.24：P72 练习： P94 5、6、,27,归结策略 计算机实现归结原理的一般算法： 1.将子句集S置入CLAUSES表； 2.若空子句NIL在CLAUSES中，则归结成功，结束。 3.若CLAUSES中存在可归结子句对，则归结之，并将归结式放入CLAUSES中； 4.归结失败，退出。 归结策略的完备性 策略：删除策略、支持集策略、线性归结策略、输入归结策略、单元归结策略、祖先过滤形策略。,28,归结举例,Sam、Clyde和Oscar是大象。关于它们，我们知道以下事实： 1）Sam是粉红色的； 2）Clyde是灰色的且喜欢Oscar； 3）Oscar是粉红色或者是灰色（但不是两种颜色）且喜欢Sam。 用归结法证明一个灰色大象喜欢一个粉红色大象。 即证明：x yGray(x) Pink(y) Likes(x,y), ,谓词： Gray(x), Pink(x), Like（x,y） 事实： 1）Pinky(Sam) 2）Gray(Clyde) Like(Clyde,Oscar) 3）(Gray(Oscar) Pink(Oscar)Likes(Oscar,Sam),29,子句集：1）Pink(Sam) 2）Gray(Clyde) 3）Like(Clyde,Oscar) 4）Gray(Oscar) Pink(Oscar) 5）Likes(Oscar,Sam) 6） Gray(x) Pink(y) Likes(x,y) 归结： 7） Gray(Oscar) Pink (Sam ) 5，6得 8） Gray(Clyde) Pink(Oscar) 3，6得 9） Pink(Oscar) Pink (Sam ) 4，7得 10） Pink(Oscar) 8，2得 11 ） Pink (Sam ) 9，10得 12）NIL 1，10得, ,30,第四节 Horn子句与Prolog程序设计,子句的蕴含表示 P90 （3-1） （3-4、4、4） 蕴含型子句的归结 P90-91 正、负文字归结（在的两头去找） Horn子句 定义：P91 定义1 蕴含型Horn子句的三种类型：P91 蕴含型Horn子句的归结 例：P91 例1 注意归结顺序,31,Prolog 程序设计 P30 Prolog 程序的语句均是 Horn 子句 事实无条件子句 规则条件子句 问题目标子句 Prolog 程序 P31-33 Prolog 程序的运行机制 P33-35 SLD归结： 从目标子句开始进行归结 归结顺序是从