人工智能 谓词演算

1、第第2 2讲讲 基于谓词逻辑的机器推理基于谓词逻辑的机器推理 一阶谓词逻辑一阶谓词逻辑 归结演绎推理归结演绎推理 归结原理的应用归结原理的应用 Horn子句与子句与Prolog程序设计程序设计1第一节第一节 一阶谓词逻辑一阶谓词逻辑w 命题：凡可确定真假的陈述句称为命题命题：凡可确定真假的陈述句称为命题n可以取值可以取值“真真”（T）或或“假假”（F）n在一定的条件下，只能取其中一个值在一定的条件下，只能取其中一个值n例：例：l（1）北京是中国的首都）北京是中国的首都l（2）3 + 2 10l（3）1 + 11 = 100（根据制数）（根据制数）l（4）禁止吸烟）禁止吸烟 （祈使句）（祈使句）

2、l（5）本命题是假的）本命题是假的 （悖论）（悖论）2w 谓词：是用来刻画个体词的性质或个体词之间的关系的词（带参量谓词：是用来刻画个体词的性质或个体词之间的关系的词（带参量的命题叫谓词）的命题叫谓词）nn 元谓词，元谓词，P（x1, x2, x3, , xn）lP 是谓词符号，代表一个确定的特征（一个参量）或关系（多个参量）是谓词符号，代表一个确定的特征（一个参量）或关系（多个参量）lx1, x2, x3, , xn 称为参量或项（个体常元或个体变元）称为参量或项（个体常元或个体变元）l论述域（个体域）：个体变元的取值范围论述域（个体域）：个体变元的取值范围n例：例：l北京是一个城市北京是一

3、个城市 CITY（北京）北京）lx 是人是人 HUMAN（x）lA是是B的兄弟的兄弟 兄弟（兄弟（A，B）lx 大于大于 y G（x，y）n不带个体变元的谓词公式叫命题，命题是谓词公式的特例不带个体变元的谓词公式叫命题，命题是谓词公式的特例3w 逻辑连接词：研究单个谓词是不够的，还必须研究多个谓词之间的逻辑连接词：研究单个谓词是不够的，还必须研究多个谓词之间的关系，这需要引入逻辑连接词关系，这需要引入逻辑连接词n ：否定词：否定词l A A读为读为“非非A”A”，当当A A为真时，为真时， A A为假，当为假，当A A为假时，为假时， A A为真为真n：合取词合取词lA B读为读为“A并且并且

4、B”，当且仅当当且仅当A和和B都为真时，都为真时， A B为真，否则为真，否则A B为假为假n：析取词析取词lA B读为读为“A或者或者B”，当且仅当当且仅当A和和B都为假时，都为假时， A B为假，否则为假，否则A B为真为真4n：蕴涵词蕴涵词lA B读为读为“若若A则则B”，当且仅当当且仅当A为真，且为真，且B为假时，为假时， A B为假，否则为假，否则A B为真为真l在在A B中，中，A称为前件，称为前件，B称为后件称为后件n：等值词：等值词lA B读为读为“A等值于等值于B”，当且仅当当且仅当A和和B同为真或同为假时，同为真或同为假时， A B为真，为真，否则否则A B为假为假5w 量

5、词：有些陈述句包含表示数量的词，如量词：有些陈述句包含表示数量的词，如“所有所有”、“任一任一”、“存在存在”、“至少有一个至少有一个”等，为了表示这样的陈述句，需引入新等，为了表示这样的陈述句，需引入新的符号，称为量词的符号，称为量词n全称量词全称量词 l（ x ）表示表示 “ 对于所有的对于所有的 x ”l例：例：w凡是人都有名字凡是人都有名字 （ x ）（）（M （x） N（x）l（ x ）A（x） A（a1） A（a2） A（an），），若论域为有限集若论域为有限集合，合， 且且a1、 a2、 、an是论域中的所有个体是论域中的所有个体n存在量词存在量词 l（ x ）表示表示 “ 对于

6、某个对于某个 x ”l例：例：w存在不是偶数的整数存在不是偶数的整数 （ x ）（）（G （x） E（x）l（ x ）A（x） A（a1） A（a2） A（an）n例：见例：见P56例例136w 项：项： （ P64 定义定义1）n（1）个体常元和个体变元都是项）个体常元和个体变元都是项n（2）f (t1, t2, , tn)是项，是项，f 是是 n 元函数，元函数， t1, t2, , tn 是项是项n（3）只有有限次使用（）只有有限次使用（1）、（）、（2）得到的符号串才是项）得到的符号串才是项w 原子公式：原子公式： （ P64 定义定义2）n设设 P 为为 n 元谓词符号，元谓词符号，

7、 t1, t2, , tn 是项，则是项，则P（ t1, t2, , tn ）称为原子称为原子谓词公式，简称原子公式谓词公式，简称原子公式7w 谓词公式：谓词公式： （ P56 定义定义3）n（1）原子公式是谓词公式）原子公式是谓词公式n（2）若）若A、B是谓词公式，则是谓词公式，则 AB、AB、 A、AB、A B、 x A、 x A也是谓词公式也是谓词公式n（3）只有有限次应用（）只有有限次应用（1）、（）、（2）生成的公式才是谓词公式）生成的公式才是谓词公式l谓词公式又称为谓词逻辑中的合式公式，记为谓词公式又称为谓词逻辑中的合式公式，记为 Wff (well-formed formula)

8、l几个概念：几个概念：w辖域（辖域（P57）：）：紧接于量词之后被量词作用的（说明的）谓词公式称为该量词的紧接于量词之后被量词作用的（说明的）谓词公式称为该量词的辖域辖域w指导变元、约束变元和自由变元指导变元、约束变元和自由变元 （ P57）w改名规则（改名规则（ P57），），保证一个变元或者是约束变元，或者是自由变元保证一个变元或者是约束变元，或者是自由变元w例：例： x （H（x） G（x, y） x A（x） B（x）8w 合取范式：合取范式： （ P58定义定义4）lA为合取范式，为合取范式，B1 B2 B n ,其中其中 Bi 形如形如L1 L2 Lm, L j为原子公式或其否定为

9、原子公式或其否定w例例：（：（P（x） Q（y） （ P（x） Q（y） R（x，y） w任一谓词公式均可化为与之等价的合取范式，但一般不唯一任一谓词公式均可化为与之等价的合取范式，但一般不唯一w 析取范式：析取范式： （ P66 定义定义5）lA为析取范式，为析取范式，B1 B2 B n ,其中其中 Bi 形如形如L1 L2 Lm, L j为为原子公式或其否定原子公式或其否定w例例：（：（P（x） Q（y） （ P（x） Q（y） R（x，y） w任一谓词公式均可化为与之等价的析取范式，但一般不唯一任一谓词公式均可化为与之等价的析取范式，但一般不唯一9w 谓词公式的永真（有效）、永假（不可满

10、足）、可满足：谓词公式的永真（有效）、永假（不可满足）、可满足： （ P58定定义义6、7）n与个体域有关与个体域有关w 谓词公式之间的关系谓词公式之间的关系n常用逻辑等价式常用逻辑等价式 P59表表3.1l注意注意与与的区别，的区别，是等价符号，说明两个谓词公式之间的等价性，是等价符号，说明两个谓词公式之间的等价性，是逻辑连接词，是谓词公式的组成部分是逻辑连接词，是谓词公式的组成部分 n常用逻辑蕴涵式常用逻辑蕴涵式 P60 表表3.2l注意注意与与的区别，的区别， 是推导符号，说明由是推导符号，说明由左边的谓词公式可以推导出左边的谓词公式可以推导出右边的谓词公式，右边的谓词公式， 是逻辑连接

11、词，是谓词公式的组成部分是逻辑连接词，是谓词公式的组成部分 10w 自然演绎推理：自然演绎推理：n（1）将自然语言命题转化为谓词公式）将自然语言命题转化为谓词公式n（2）利用上面的逻辑等价式和逻辑蕴涵式，可以进行推理，得出一些）利用上面的逻辑等价式和逻辑蕴涵式，可以进行推理，得出一些隐含在谓词公式中的结论隐含在谓词公式中的结论l例：例：P61 例例4-6l自然演绎推理实施困难，推理规则太多、应用规则需要很强的模式识别能自然演绎推理实施困难，推理规则太多、应用规则需要很强的模式识别能力、中间结论呈指数增长力、中间结论呈指数增长l引入新的推理技术引入新的推理技术归结演绎推理技术归结演绎推理技术w归

12、结归结消解（消解（Resolution），），由由Robinson于于1965年提出，大大推动了自动定理年提出，大大推动了自动定理证明的发展证明的发展11练习：练习：w 1、设已知以下事实：、设已知以下事实：ABACBCDDQ求证：求证：Q为真。为真。12证明：证明：因为因为A，AC CB，C B CBC，BCD DD，DQ Q所以所以Q为真为真13w 2、设已知如下事实：、设已知如下事实：（1）凡是容易的课程小王都喜欢。）凡是容易的课程小王都喜欢。（2）C班的课程都是容易的。班的课程都是容易的。（3）ds 是是C班的一门课程。班的一门课程。求证：小王喜欢求证：小王喜欢 ds 这门课程。这门课

13、程。14证明：证明：事实事实 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第二节第二节 归结演绎推理归结演绎推理w 建立子句集建立子句集n文字、子句、空子

14、句文字、子句、空子句 （P62 定义定义1）n建立谓词公式建立谓词公式 G 的子句集合的子句集合 （P62定义定义2）l例：例：P62例例3.7l例：例：P63 例例2 有关消去存在量词有关消去存在量词l子句集中各子句的关系是子句集中各子句的关系是 合取合取 n经过变换后的子句集经过变换后的子句集 S ，与谓词公式与谓词公式 G 并不等价并不等价n子句集的不可满足子句集的不可满足 （P64 定义定义3）nG不可满足当且仅当不可满足当且仅当S不可满足（不可满足（P64 定理定理1），即），即G永假是永假是S永假的充永假的充分必要条件分必要条件16练习：练习：P93 1、（1 1）p(x,y),Q

15、(u,v)p(x,y),Q(u,v)（2 2） p(x,y)Q(x,y)p(x,y)Q(x,y) （3 3）P(x,f(x)P(x,f(x) Q(x,f(x)R (x,f(x)Q(x,f(x)R (x,f(x) （4 4） P(x,z)Q(x,y)R(x,y)P(x,z)Q(x,y)R(x,y) （5 5）P(a,b,z,f(z),v,g(z,v),P(a,b,z,f(z),v,g(z,v),Q(a,b,f(t),s,g(t,s)Q(a,b,f(t),s,g(t,s) R(a,t,g(t,s) R(a,t,g(t,s) 17w 命题逻辑中的归结原理命题逻辑中的归结原理n在定理证明系统中，已知一

16、公式集在定理证明系统中，已知一公式集F1，F2，Fn，要证明要证明W（定理）定理）是否成立，即要证明是否成立，即要证明W是公式集的逻辑结果，有两种方法：是公式集的逻辑结果，有两种方法：l1、证明、证明 F1 F2 Fn W 为永真式（见上一节）为永真式（见上一节）l2、（反证法）证明、（反证法）证明 F1 F2 Fn W 永假，即要证明对应子句集永假，即要证明对应子句集永假（不可满足）永假（不可满足）n几个概念：（几个概念：（P64 定义定义4、5）互补文字、归结式（消解式）、亲本子）互补文字、归结式（消解式）、亲本子句、消解基句、消解基 l例：例例：例3.9n归结式是其亲本子句的逻辑结果归结

17、式是其亲本子句的逻辑结果 P64 定理定理2l单向推导关系单向推导关系18n归结原理：归结原理： C1 C2 （C1-L1） （C2-L2）n互补文字进行归结得空子句（互补文字进行归结得空子句（L L =），），另另L L = F（假），假），故空子句即永假子句故空子句即永假子句n关于消解前后子句集的可满足性关于消解前后子句集的可满足性 P65 推论推论 （证明略）（证明略）n故：要证明一子句集永假，可以通过对子句集应用消解原理得到空子故：要证明一子句集永假，可以通过对子句集应用消解原理得到空子句来证明句来证明n运用归结原理证明定理的例子：运用归结原理证明定理的例子：P65 例例11、12l*

18、 归结过程可以用一棵归结过程可以用一棵 归结演绎树归结演绎树 表示表示19w 替换与合一替换与合一n为了对谓词逻辑的子句集运用消解原理，即在子句集合中寻找含互补为了对谓词逻辑的子句集运用消解原理，即在子句集合中寻找含互补文字的子句对，必须对子句进行替换合一操作文字的子句对，必须对子句进行替换合一操作n替换：替换：P66 定义定义6 t1/x1， t2/x2， ，t n /x nl对表达式的替换过程对表达式的替换过程 P66 定义定义7l表达式表达式 项、原子公式、文字、子句项、原子公式、文字、子句n两个替换的乘积两个替换的乘积 P66-67 定义定义8 l一部分仍是一部分仍是的替换对，只是的替

19、换对，只是的项被的项被作了替换；另一部分是作了替换；另一部分是中与中与不同的不同的那些变量对那些变量对l例：例例：例3.13l替换的乘积满足结合律替换的乘积满足结合律20n合一：合一：P67 定义定义9l是是 S 的一个合一的一个合一l其中其中S 是一个原子谓词公式集，是一个原子谓词公式集， 是一个替换是一个替换l满足满足 F1 = F2 = =Fn l一个公式集的合一一般不唯一一个公式集的合一一般不唯一n最一般的合一：最一般的合一：P67 定义定义10l是是 S 的一个合一的一个合一l对于对于S 的任何一个合一的任何一个合一，存在替换存在替换，使使 = l称称为为S 的最一般（最普通、最简单

20、）合一的最一般（最普通、最简单）合一 MGUw例：例例：例3.14lMGU 的替换限制最少，所产生的例更一般化，这有利于归结过程的灵活使的替换限制最少，所产生的例更一般化，这有利于归结过程的灵活使用用l一个公式集的最一般合一也可不唯一，如一个公式集的最一般合一也可不唯一，如 P（x），），P（y），y/x、 x/y都是它的最一般合一都是它的最一般合一21n差异集：差异集：P67 定义定义11l针对具有相同谓词名的原子公式集针对具有相同谓词名的原子公式集l例：例例：例3.15n合一算法：求非空有限具有相同谓词名的原子公式集的最一般合一合一算法：求非空有限具有相同谓词名的原子公式集的最一般合一lP

21、67-68l合一算法是解决两个表达式匹配的问题，两个表达式都可以含有变量，通合一算法是解决两个表达式匹配的问题，两个表达式都可以含有变量，通过算法求得过算法求得 MGU 并进行替换后就可以得到匹配的例并进行替换后就可以得到匹配的例l例：例例：例16、17l合一定理：合一定理： P68-69 定理定理3w可合一公式集一定存在最一般合一，用上述合一算法求得可合一公式集一定存在最一般合一，用上述合一算法求得22w 谓词逻辑中的归结原理谓词逻辑中的归结原理n归结过程：归结过程：l若若S 中的两子句间有相同互补文字的谓词，但它们的项不同，则必须找出中的两子句间有相同互补文字的谓词，但它们的项不同，则必须

22、找出对应的不一致项对应的不一致项l进行变量替换合一操作，使它们的对应项一致进行变量替换合一操作，使它们的对应项一致l求归结式看能否导出空子句求归结式看能否导出空子句n几个概念：（几个概念：（P69 定义定义12）谓词逻辑中的二元归结式（二元消解式）、）谓词逻辑中的二元归结式（二元消解式）、亲本子句、消解文字亲本子句、消解文字 l例：例例：例18、19l子句用文字的集合表示，各文字之间的关系是子句用文字的集合表示，各文字之间的关系是 析取析取 l首先对子句内部的可合一文字进行合一首先对子句内部的可合一文字进行合一23n因子、单因子因子、单因子 （ P69 定义定义13）l例：例例：例14n子句的

23、归结（消解）式子句的归结（消解）式 （ P69 定义定义14）n定理：谓词逻辑中的消解式是它的亲本子句的逻辑结果定理：谓词逻辑中的消解式是它的亲本子句的逻辑结果l谓词逻辑中的归结原理：谓词逻辑中的归结原理：C1 C2 （C1- L1 ）（ C2 - L2 ）n关于消解前后子句集的可满足性关于消解前后子句集的可满足性 P70 （同命题逻辑）（同命题逻辑）n故：要证明故：要证明F1 F2 Fn W 为永真式，可证明为永真式，可证明 F1 F2 Fn W 永假，这又可以通过对对应子句集应用消解原理得到空子句永假，这又可以通过对对应子句集应用消解原理得到空子句来证明（同命题逻辑）来证明（同命题逻辑）2

24、4n例：例例：例15、16n定理：归结原理的完备性定理：归结原理的完备性 （ P71）练习：练习：P93 3、（、（1）-（5）25第三节第三节 归结原理的应用归结原理的应用w 例例3.23：P71w 例例3.24：P72练习：练习： P94 5、6、26w 归结策略归结策略w 计算机实现归结原理的一般算法：计算机实现归结原理的一般算法：1.将子句集将子句集S置入置入CLAUSES表；表；2.若空子句若空子句NIL在在CLAUSES中，则归结成功，结束。中，则归结成功，结束。3.若若CLAUSES中存在可归结子句对，则归结之，并将归结式放入中存在可归结子句对，则归结之，并将归结式放入CLAUS

25、ES中；中；4.归结失败，退出。归结失败，退出。归结策略的完备性归结策略的完备性策略：删除策略、支持集策略、线性归结策略、输入归结策略、单元策略：删除策略、支持集策略、线性归结策略、输入归结策略、单元归结策略、祖先过滤形策略。归结策略、祖先过滤形策略。27归结举例Sam、Clyde和和Oscar是大象。关于它们，我们知道以下事实：是大象。关于它们，我们知道以下事实：1）Sam是粉红色的；是粉红色的；2）Clyde是灰色的且喜欢是灰色的且喜欢Oscar；3）Oscar是粉红色或者是灰色（但不是两种颜色）且喜欢是粉红色或者是灰色（但不是两种颜色）且喜欢Sam。用归结法证明一个灰色大象喜欢一个粉红色

26、大象。用归结法证明一个灰色大象喜欢一个粉红色大象。即证明：即证明： 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)28子句集：子句集：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）NIL1，10得得 29第四节第四节 Horn子句与子句与Prolog程序设计程序设计w