人工智能第2章(知识表示方法3-谓词逻辑)ppt课件.ppt

《人工智能第2章(知识表示方法3-谓词逻辑)ppt课件.ppt》由会员分享，可在线阅读，更多相关《人工智能第2章(知识表示方法3-谓词逻辑)ppt课件.ppt（93页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益人人 工工 智智 能能ArtificialIntelligence(AI)为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益第第2章章知识表示方法知识表示方法2.1状态空间法状态空间法2.2问题归约法问题归约法2.3谓词逻辑法谓词逻辑法为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益五房间问题：五房间问题：1、有5栋5种颜色的房子2、每一位房子的主

2、人国籍都不同3、这5个人只喝一个牌子的饮料，只抽一个牌子的香烟，只养一种宠物4、没有人有相同的宠物，抽相同牌子的香烟，喝相同的饮料谁养鱼？谁养鱼？为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益已知条件：已知条件：1、英国人住在红房子里2、瑞典人养了一条狗3、丹麦人喝茶4、绿房子在白房子左边5、绿房子主人喝咖啡6、抽PALLMALL烟的人养了一只鸟7、黄房子主人抽DUNHILL烟8、住在中间那间房子的人喝牛奶9、挪威人住在第一间房子10、抽混合烟的人住在养猫人的旁边11、养马人住在DUNHILL烟的人旁边12、抽BLUEMAS

3、TER烟的人喝啤酒13、德国人抽PRINCE烟14、挪威人住在蓝房子旁边15、抽混合烟的人的邻居喝矿泉水房间号房间号12345颜色颜色国籍国籍香烟香烟饮料饮料宠物宠物挪威人挪威人牛奶牛奶4、绿房子在白房子左边、绿房子在白房子左边5、绿房子主人喝咖啡、绿房子主人喝咖啡咖啡咖啡1、英国人住在红房子里、英国人住在红房子里英国人英国人7、黄房子主人抽、黄房子主人抽DUNHILL烟烟11、养马人住在、养马人住在DUNHILL烟的人旁边烟的人旁边DUNHILL马马3、丹麦人喝茶、丹麦人喝茶12、抽、抽BLUEMASTER烟的人喝啤酒烟的人喝啤酒矿泉水矿泉水2、瑞典人养了一条狗、瑞典人养了一条狗3、丹麦人喝

4、茶、丹麦人喝茶12、抽、抽BLUEMASTER烟的人喝啤酒烟的人喝啤酒13、德国人抽、德国人抽PRINCE烟烟瑞典人瑞典人BLUEMASTER啤酒啤酒狗狗丹麦人丹麦人茶茶德国人德国人PRINCE混合烟混合烟PALLMALL鸟鸟猫猫鱼鱼为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益推理的一般形式已知：已知：事实一，事实二，事实一，事实二，如果事实一，那么结论一；如果事实一，那么结论一；如果事实二，那么结论二；如果事实二，那么结论二；得到：得到：结论一，结论二，结论一，结论二，如果将如果将事实事实和和规则规则抽象出来，不涉及具体

5、内容，借抽象出来，不涉及具体内容，借助一些助一些符号符号来表示，推理过程可形式化为：来表示，推理过程可形式化为：P：某已知事实：某已知事实PQ：如果：如果P，则，则Q结论：结论：Q为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益自然语言自然语言不适合计算机推理不适合计算机推理如：小王不方便接电话，他方便去了。如：小王不方便接电话，他方便去了。需要一种无歧义，方便存储和表达的形式化符号表征体系需要一种无歧义，方便存储和表达的形式化符号表征体系逻辑逻辑经典逻辑：经典逻辑：命题逻辑命题逻辑、谓词逻辑谓词逻辑非经典逻辑非经典逻辑：不确

6、定性推理、非单调性推理不确定性推理、非单调性推理为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益命题逻辑命题逻辑谓词逻辑谓词逻辑如果今天不下雨，我就去你家如果今天不下雨，我就去你家今天没有下雨今天没有下雨我去了你家我去了你家QPPQ命题逻辑核心思想：原子命题不可再分命题逻辑核心思想：原子命题不可再分凡人都会死凡人都会死苏格拉底是人苏格拉底是人苏格拉底会死苏格拉底会死Man(Socrates)Mortal(Socrates)x(Man(x)Mortal(x)为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工

7、作人员聘用制度，保障用人单位和职工的合法权益2.3谓词逻辑法谓词逻辑法数理逻辑数理逻辑（符号逻辑）是用数学方法研究形式逻（符号逻辑）是用数学方法研究形式逻辑的一个分支。辑的一个分支。它它通过符号系统来表达客观对象通过符号系统来表达客观对象以及相关的逻辑推理。常用的是以及相关的逻辑推理。常用的是命题逻辑命题逻辑和和谓谓词逻辑词逻辑为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益谓谓词词逻逻辑辑是是数数理理逻逻辑辑的的基基本本形形式式，是是基基于于谓谓词词分析的一种形式化（数学）语言分析的一种形式化（数学）语言人工智能中的谓词逻辑

8、法人工智能中的谓词逻辑法是指用一阶谓词是指用一阶谓词来描述问题求解和定理证明（来描述问题求解和定理证明（限于本课程限于本课程）为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益2.3.0命题逻辑的复习命题逻辑的复习 1、命题逻辑的基本概念命题逻辑的基本概念命题命题 是能够判断是能够判断真真或或假假的的陈述句陈述句通常用通常用大写字母大写字母来表示，如来表示，如A,B,P,Q等等命题的真假值一般用命题的真假值一般用 T或或 F来表示来表示 为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障

9、用人单位和职工的合法权益例例：雪是白的。（陈述句，雪是白的。（陈述句，T）雪是蓝的。（陈述句，雪是蓝的。（陈述句，F）雪是黑的。（陈述句，雪是黑的。（陈述句，F）他他是学生。（陈述句，他泛指，无法判断真假）是学生。（陈述句，他泛指，无法判断真假）你今天上课没有？（疑问句）你今天上课没有？（疑问句）去北校区，请坐校车！（祈使句）去北校区，请坐校车！（祈使句）为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益命题逻辑命题逻辑是研究是研究命题命题及及命题之间命题之间关系的符关系的符号逻辑系统。号逻辑系统。在命题逻辑中，表示单一意义的命

10、题，称之为在命题逻辑中，表示单一意义的命题，称之为原原子命题子命题。原子命题通过原子命题通过“联结词联结词”构成构成 复合命题复合命题。为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益五个联结词五个联结词：“”表示表示 “非非”复合命题复合命题P为真，当且仅当为真，当且仅当P为假。为假。“”“”表示表示“合取合取”复合命题复合命题“PQ”为真，当且仅当为真，当且仅当P和和Q都为真。都为真。为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益“”表示表示“蕴含蕴含”

11、复合命题复合命题“PQ”为假，当且仅当为假，当且仅当P为真且为真且Q为假。为假。“”“”表示表示“析取析取”复合命题复合命题“PQ”为真，当且仅当为真，当且仅当P、Q两者之两者之一为真。一为真。为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益“”表示表示“等价等价”复合命题复合命题“PQ”为真，当且仅当为真，当且仅当P、Q同时为真、同时为真、或者同时为假。或者同时为假。联接词的联接词的优先顺序优先顺序：非非、合取合取、析取析取、蕴含蕴含、等价等价注注：可以用括号表示优先级：可以用括号表示优先级为了规范事业单位聘用关系，建立和完

12、善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益真值表真值表 PQPPQPQPQPQFFTFFTTFTTFTTFTFFFTFFTTFTTTT为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益命题变元命题变元：用符号：用符号P、Q等表示的不具有固定、具等表示的不具有固定、具体含义的命题。它可以表示具有体含义的命题。它可以表示具有“真真”、“假假”含含义的各种命题。义的各种命题。命题变元可以利用联结词构成所谓的命题变元可以利用联结词构成所谓的合适公式合适公式。为了规范事业单位聘用关系，建立和完善适应

13、社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益合适公式的定义合适公式的定义若若P为为原原子子命命题题，则则P为为合合适适公公式式，称称为为原原子子公公式。式。若若P是合适公式，则是合适公式，则P也是一个合适公式。也是一个合适公式。为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益若若P和和Q是是合合适适公公式式，则则PQ、PQ、PQ、PQ都是合适公式。都是合适公式。经经过过有有限限次次使使用用规规则则1、2、3，得得到到的的由由原原子子公公式式、联联结结词词和和园园括括号号所所组组成成的的符符号号串

14、串，也也是是合合适适公式。公式。为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益对于合适公式，规定下列对于合适公式，规定下列运算优先级运算优先级：逻辑联结词的运算优先次序为：逻辑联结词的运算优先次序为：、同级联结词按出现顺序优先运算同级联结词按出现顺序优先运算为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益在命题逻辑中，主要研究推理的有效性。在命题逻辑中，主要研究推理的有效性。即：能否根据一些合适公式（即：能否根据一些合适公式（前提前提）推导出新的）推导出新的

15、合适公式（合适公式（结论结论）。）。一些合适公式一些合适公式（前提条件）（前提条件）合适公式合适公式（结论）（结论）？为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益在在命命题题逻逻辑辑中中，最最基基本本的的单单元元是是命命题题，它它是是作为一个不可分割的整体。作为一个不可分割的整体。例如：例如：雪是黑的雪是黑的命命题题逻逻辑辑具具有有较较大大的的局局限限性性，不不合合适适于于表表达达比较复杂的问题。比较复杂的问题。为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法

16、权益例例：所有科学都是有用的所有科学都是有用的（假设（假设1）。数理逻辑是科学数理逻辑是科学（假设（假设2）。所以，数理逻辑是有用的所以，数理逻辑是有用的（结论）（结论）。很明显，我们无法用很明显，我们无法用两个假设两个假设推断出推断出结论结论。为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益谓词逻辑谓词逻辑是命题逻辑的扩充和发展。它将一个原是命题逻辑的扩充和发展。它将一个原子命题分解成子命题分解成客体客体和和谓词谓词两个组成部分。两个组成部分。例如：例如：雪雪 是黑的是黑的 客体客体 谓词谓词本课程主要介绍一阶谓词逻辑。本课

17、程主要介绍一阶谓词逻辑。为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益2.3.1谓词演算谓词演算1 1、语法与语义、语法与语义谓词逻辑的基本组成部分谓词逻辑的基本组成部分谓词谓词变量变量函数函数常量常量圆括号圆括号、方括号、花括号和逗号、方括号、花括号和逗号为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益例例“机机器器人人（Robot）在在第第一一个个房房间间（Room1）内内”，可以表示为：，可以表示为：INROOM（ROBOT，r1）其中其中INROOM

18、是是谓词谓词ROBOT和和r1是是常量常量为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益谓词谓词是指个体（客体）所具有的是指个体（客体）所具有的性质性质或者若干个体或者若干个体之间的之间的关系关系。用。用大写字母大写字母来表示。来表示。个体个体是可以具体的（如是可以具体的（如:小张、小张、3、5）也可以是抽）也可以是抽象的（如象的（如:x,y）。）。为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益例例：小小明明是是学学生生，A表表示示是是“是是学学生生”，x

19、表表示示“小小明明”，记作，记作A(x)。x大于大于y，G表示表示“大于大于”，记作，记作G（x,y）。）。为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益论域论域：由个体组成的集合。：由个体组成的集合。（个体个体）变量变量：定义在某一个论域上的变量。用：定义在某一个论域上的变量。用x,y,z来表示。来表示。函数函数（或函词）（或函词）：以个体为变量，以个体为值的：以个体为变量，以个体为值的函数。一般用小写字母来表示，例如函数。一般用小写字母来表示，例如f(x),f(x,a)。为了规范事业单位聘用关系，建立和完善适应社会主义市

20、场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益如如果果谓谓词词有有n个个变变量量，称称之之为为n元元谓谓词词，并并约约定定0元谓词就是命题（谓词的特例）。元谓词就是命题（谓词的特例）。如如果果函函数数有有 n个个个个体体，称称之之为为n元元函函数数，并并约约定定0元元函函数数就就是是常常量量。常常量量习习惯惯上上用用小小写写字字母母来来表表示示，如如a,b,c。为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益项项的定义：的定义：常量是项常量是项变量是项变量是项如果如果f 是是n元函数，且元函数，且t1,tn

21、(n1)是项，则是项，则f(t1,tn)也是项也是项所有的项都必须是有限次应用上述规则产生的所有的项都必须是有限次应用上述规则产生的为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益项的例子项的例子：常量：常量：a变量：变量：x函数：函数：f(x,a)g(f(x,a)为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益原子（谓词）公式原子（谓词）公式的（递归）定义：的（递归）定义：原子命题是原子公式原子命题是原子公式如如果果t1,tn(n1)是是项项，P是是谓谓词词

22、，则则P(t1,tn)是原子公式是原子公式其它表达式都不是原子公式其它表达式都不是原子公式为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益原子公式的例子原子公式的例子1、原子公式：、原子公式：P（原子命题）原子命题）2、项：、项：x,a,f(x,a)，谓词：谓词：P原子公式：原子公式：P(x,a,f(x,a)为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益2、连词和量词、连词和量词联结词（连词）联结词（连词）就是命题逻辑中的五个，它们的就是命题逻辑中的五个，它

23、们的含义也是一样的。含义也是一样的。为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益两个量词两个量词：全全称称量量词词，记记作作“x x”,”,含含义义是是“对对每每一一个个x x”或或“对一切对一切x x”。存存在在量量词词，记记作作“x x”，含含义义是是“存存在在某某个个x x”、“有一个有一个x x”或者或者“某些某些x x”。AllAExistE为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益例例1：“所所有有的的机机器器人人都都是是灰灰色色的的”，

24、用用谓谓词词逻逻辑辑可以表示成：可以表示成：（x）ROBOT(x)COLOR(x，gray)为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益例例2：“一号房间里有一个物体一号房间里有一个物体”，可以表示成，可以表示成（x）INROOM（x,r1）为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益我我们们称称x是是被被量量化化了了的的变变量量，称称为为约约束束变变量量。否则称之为否则称之为自由变量自由变量。一一阶阶谓谓词词：只只允允许许对对变变量量施施加加量量词词

25、，不不允允许许对对谓词和函数施加量词。谓词和函数施加量词。为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益2.3.2谓词公式谓词公式1、谓词公式的定义谓词公式的定义利用连词和量词可以将原子（谓词）公式组成复利用连词和量词可以将原子（谓词）公式组成复合谓词公式，称之为分子谓词公式、谓词合适公合谓词公式，称之为分子谓词公式、谓词合适公式、式、谓词公式谓词公式、合适公式、合适公式。为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益（谓词）（谓词）合适公式合适公式的（递

26、归）定义：的（递归）定义：原子（谓词）公式是合适公式。原子（谓词）公式是合适公式。若若A是合适公式，则是合适公式，则A也是合适公式。也是合适公式。若若A和和B是是合合适适公公式式，则则AB、AB、AB、AB也是合适公式。也是合适公式。为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益若若A是是合合适适公公式式，x为为A的的自自由由变变元元（变变量量），则，则（x）A和和（x）A都是合适公式。都是合适公式。只有按上述规则求得的公式才是合适公式。只有按上述规则求得的公式才是合适公式。为了规范事业单位聘用关系，建立和完善适应社会主义市

27、场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益例：任何整数或者为正或者为负。例：任何整数或者为正或者为负。数数学学表表达达：对对于于所所有有的的x，如如果果x是是整整数数，则则x或或者为正、或者为负。者为正、或者为负。记作记作：I(x)：“x是整数是整数”。P(x)：“x是正数是正数”。N(x)：“x是负数是负数”。谓词公式谓词公式：（x）（）（I(x)(P(x)N(x)）为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益2、合适公式的性质、合适公式的性质如果如果 P和和 Q是合适公式，则由这两个合适公式是合

28、适公式，则由这两个合适公式构成的合适公式的构成的合适公式的真值表真值表与前面介绍的与前面介绍的真值表真值表相同。相同。如果两个合适公式的真值表相同，则我们称这如果两个合适公式的真值表相同，则我们称这两个合适公式是等价的两个合适公式是等价的，可以用，可以用“”来表示。来表示。为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益对于命题合适公式和谓词合适公式有下列等价关系：对于命题合适公式和谓词合适公式有下列等价关系：否定之否定否定之否定：（P）等价于等价于PPQ等价于等价于PQ狄狄.摩根定律摩根定律（PQ）等价于等价于PQ（PQ）等

29、价于等价于PQ为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益分配律分配律P(QR)等价于等价于(PQ)(PR)P(QR)等价于等价于(PQ)(PR)交换律交换律PQ等价于等价于QPPQ等价于等价于QP为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益结合律结合律(PQ)R等价于等价于P(QR)(PQ)R等价于等价于P(QR)逆否律逆否律PQ等价于等价于QP说明说明：上述等价关系对命题合适公式、谓词合适上述等价关系对命题合适公式、谓词合适公式都成立。公式都成立。

30、为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益对于谓词合适公式有下列等价关系：对于谓词合适公式有下列等价关系：(x)P(x)等价于等价于(x)P(x)(x)P(x)等价于等价于(x)P(x)(x)P(x)Q(x)等等价价于于(x)P(x)(x)Q(x)(x)P(x)Q(x)等等 价价 于于(x)P(x)(x)Q(x)为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益(x)P(x)等价于等价于(y)P(y)(x)P(x)等价于等价于(y)P(y)注释注释：这两个

31、关系说明，在一个量化的表达式中这两个关系说明，在一个量化的表达式中的约束变量是一类虚元，它们可以用任何不在表的约束变量是一类虚元，它们可以用任何不在表达式中出现的其它变量来代替。达式中出现的其它变量来代替。为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益2.3.3置换与合一置换与合一1、置换、置换置换的定义置换的定义：形如：形如 t1/v1,tn/vn 的集合，称为一个置换，其中的集合，称为一个置换，其中 vi 是不同的变量，是不同的变量，ti 是与是与 vi 不同的项。不同的项。为了规范事业单位聘用关系，建立和完善适应社会主

32、义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益例或例子的定义例或例子的定义：设设 t1/v1,tn/vn 为一个置换，为一个置换，E是一个原子谓词公式。则是一个原子谓词公式。则E表示表示将将E中的中的 vi 同时用同时用 ti（i=1,n）代入后所得到代入后所得到的结果，的结果，E称为称为E的一个的一个例子例子。为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益例例：表表达达式式（原原子子谓谓词词公公式式）Px,f(y),B的的四四个个置置换及其对应的四个例子换及其对应的四个例子（B是常量是常量）s1=z

33、/x,w/ys2=A/ys3=q(z)/x,A/ys4=c/x,A/yPx,f(y),Bs1=Pz,f(w),BPx,f(y),Bs2=Px,f(A),BPx,f(y),Bs3=Pq(z),f(A),BPx,f(y),Bs4=Pc,f(A),BPx,f(y),B为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益置置换换的的合合成成：设设t1/x1,tn/xn和和s1/y1,sm/ym是两个置换，则是两个置换，则和和的合成是如下置换：的合成是如下置换：t1/x1,ti/xi,tn/xn,s1/y1,sm/ym其其中中，若若yj 是

34、是x1,xn之之一一者者消消去去，对对于于任任何何tj=xj 者消去，并记成者消去，并记成。为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益如何求如何求ti:s1/y1,sm/ym如如果果ti出出现现y1,.,ym中中的的变变量量yi，则则用用其其对对应的项应的项si来代替。来代替。为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益例：例：=t1/x1,t2/x2f(y)/x,z/y=s1/y1,s2/y2,s3/y3=a/x,b/y,y/z=t1/x1,t2/

35、x2,s1/y1,s2/y2,s3/y3=f(b)/x,y/yy/y,a/a/x x,b/y y,y/z=f(b)/x,y/z为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益注意注意：置换的合成满足结合律，不满足交换律。置换的合成满足结合律，不满足交换律。(s1s2)s3=s1(s2s3)(满足满足结合律结合律）s1s2s2s1（不不满足满足交换律交换律）为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益例例：s1=z/x,w/ys2=A/ys1s2=z/x,w

36、/y,A/y=z/x,w/ys2s1=A/y,z/x,w/y=A/y,z/x为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益2、合一、合一当当某某一一个个置置换换s作作用用于于表表达达式式集集合合Ei的的每每一一个个元元素素，此此时时我我们们用用Eis来来表表示示置置换换例例子子的的集集合合。如如果存在一个置换果存在一个置换s，使得使得E1s=E2s=Eis=则则我我们们称称表表达达式式集集合合 Ei是是可可合合一一的的，并并称称 s为为Ei的的合合一一者者。原原因因是是它它的的作作用用是是使使集集合合 Ei成成为为单一形式。

37、单一形式。其中，其中，Ei 是原子谓词公式。是原子谓词公式。为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益例例：表表达达式式集集合合Px,f(y),B,Px,f(B),B的的合合一一者为是者为是s=A/x,B/yPx,f(y),Bs=PA,f(B),BPx,f(B),Bs=PA,f(B),B为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益如如果果s是是Ei的的任任意意一一个个合合一一者者，又又存存在在某某一一个个s，使得使得s=gs或者或者Eis=Eigs则

38、则 称称 g是是 Ei的的最最通通用用（最最一一般般）的的合合一一者者，记作记作mgu。为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益例例：s=A/x,B/y是表达式集合是表达式集合Px,f(y),B,Px,f(B),B的一个合一者，该集合的的一个合一者，该集合的最一般的合一者最一般的合一者是：是：g=B/y为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益3、合一算法、合一算法分歧集（或不一致集合）的定义分歧集（或不一致集合）的定义。设有一非空有限公式集合设

39、有一非空有限公式集合 F=F1,Fn，从从 F中各个公式的第一个符号同时向右比较，直到发现中各个公式的第一个符号同时向右比较，直到发现第一个彼此不尽相同的符号为止，从第一个彼此不尽相同的符号为止，从 F中的各个中的各个公式中取出那些以第一个不一致符号开始的公式中取出那些以第一个不一致符号开始的最大的最大的最大的最大的子表达式子表达式子表达式子表达式为元素，组成一个集合为元素，组成一个集合 D，称为称为 F的分的分歧集（不一致集合）。歧集（不一致集合）。其中，其中，Fi (i=1,n)是原是原子谓词公式子谓词公式为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制

40、度，保障用人单位和职工的合法权益例例：公式集：公式集：F=P(x,g(f(y,z),x),y),P(x,g(a,b),b),P(x,g(g(h(x),a),y),h(x)分歧集为：分歧集为：D=f(y,z),a,g(h(x),a)为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益设设F为为非非空空有有限限表表达达式式集集合合，则则可可以以按按下下列列步步骤骤求出求出mgu：置置k=0，Fk=F,k=(空空置置换换，即即不不含含元元素素的的置换置换)。若若Fk 只只有有一一个个表表达达式式，则则算算法法终终止止，其其中中k就就是是

41、要求的要求的mgu。找出找出 Fk 的分歧集的分歧集 Dk。合一算法合一算法：为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益若若Dk 中中存存在在元元素素ak 和和tk，其其中中ak 是是变变元元，tk是项，且是项，且ak 不在不在tk 中出现，则置：中出现，则置：k+1=k tk/ak Fk+1=Fk tk/ak k=k+1然后转向然后转向。否则，继续。否则，继续。算法终止，算法终止，F的的 mgu不存在。不存在。为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合

42、法权益合一算法的流程图合一算法的流程图k=0,Fk=F,k=|Fk|1？求得求得mgu、结束结束求出不一致集合求出不一致集合有置换？有置换？求出新置换；更新公式集合与旧置换，求出新置换；更新公式集合与旧置换，k+无解、结束无解、结束为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益说明说明：1、合一算法是消解原理的基础。、合一算法是消解原理的基础。2、合一算法中的公式集就是从谓词合适公式合一算法中的公式集就是从谓词合适公式化成的子句集。化成的子句集。为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘

43、用制度，保障用人单位和职工的合法权益例例：求：求F=P(a,x,f(g(y),P(z,h(z,u),f(u)的最一般的合一者。的最一般的合一者。解解：我们根据合一算法一步一步地求出：我们根据合一算法一步一步地求出mgu。为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益第一步第一步：k=0,F0=F,0=F0的分歧集合的分歧集合D0=a,z 置换置换：a/z1=0a/z=a/zF1=F0a/z=P(a,x,f(g(y),P(a,h(a,u),f(u)k=1F1不是单一表达式不是单一表达式F=P(a,x,f(g(y)，P(z,h(

44、z,u),f(u)为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益第二步第二步：D1x,h(a,u)置换置换：h(a,u)/x21h(a,u)/x=a/z,h(a,u)/xF2=F1h(a,u)/x=P(a,h(a,u),f(g(y),P(a,h(a,u),f(u)k=2F=P(a,x,f(g(y)，P(a,h(a,u),f(u)为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益第三步第三步：D2g(y),u置换置换：g(y)/u32g(y)/u=a/z,h(a

45、,g(y)/x,g(y)/uF3=F2g(y)/u=P(a,h(a,g(y),f(g(y)k=3F=P(a,h(a,u),f(g(y)，P(a,h(a,u),f(u)为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益F3是单一表达式，所以是单一表达式，所以3a/z,h(a,g(y)/x,g(y)/u是是 F的最一般合一者的最一般合一者为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益例：例：F=Q(f(a),g(x),Q(y,y)是否可合一？是否可合一？第一步第一

46、步：k=0,F0=F,0=F0的分歧集合的分歧集合D0=f(a),y 置换置换：f(a)/y10f(a)/y=f(a)/yF1=F0 f(a)/y=Q(f(a),g(x),Q(f(a),f(a)k=1F1不是单一表达式不是单一表达式为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益第二步：第二步：D1g(x),f(a)不存在着变量，所以不可合一。不存在着变量，所以不可合一。F1=Q(f(a),g(x),Q(f(a),f(a)为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工

47、的合法权益练习：练习：求公式集求公式集W=Q(x,y,z),Q(a,f(b),a)的的最最一一般般的的合合一一者者?其其中中，x,y,z为为变变量量，a为为常常量，量，f为函数为函数为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益第一步第一步：k=0,W0=W,0=W0的分歧集合的分歧集合D0=a,x 置换置换：a/x10a/x=a/xW1=W0a/x=Q(a,y,z),Q(a,f(b),a)k=1W1不是单一表达式不是单一表达式Q(x,y,z),Q(a,f(b),a)为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体

48、制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益第二步第二步：W1的分歧集合的分歧集合D1=f(b)，y 置换置换：f(b)/y21f(b)/y=a/x,f(b)/yW2=W1f(b)/y=Q(a,f(b),z),Q(a,f(b),a)k=2W2不是单一表达式不是单一表达式Q(a,y,z),Q(a,f(b),a)为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益第三步第三步：W2的分歧集合的分歧集合D0=a,z 置换置换：a/z32a/z=a/x,f(b)/y,a/zW3=W2a/z=Q(a,f(b),a)k=3W3是

49、单一表达式是单一表达式，mgu=3=a/x,f(b)/y,a/zQ(a,f(b),z),Q(a,f(b),a)为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益1.1.谓词的一致性，谓词的一致性，P()P()与与Q()Q()，不可以不可以2.2.常量的一致性，常量的一致性，P(a,)P(a,)与与P(b,.)P(b,.)，不可不可以；变量，以；变量，P(a,.)P(a,.)与与P(x,)P(x,)，可以可以3.3.变量与函数，变量与函数，P(a,x,.)P(a,x,.)与与P(x,f(x),)P(x,f(x),)，不可以；但不可

50、以；但P(a,x,)P(a,x,)与与P(x,f(y),)P(x,f(y),)，可以可以4.4.是不能同时消去两个互补对，是不能同时消去两个互补对，PQPQ与与PPQ Q的空，不可以的空，不可以5.5.先进行内部简化（置换、合并）先进行内部简化（置换、合并）置换和合一的注意事项：置换和合一的注意事项：例如假设用下列定义例如假设用下列定义P（x,a）表示某人表示某人x的职业为的职业为a；A（y,b）表示表示Y的年龄为的年龄为b；GE（x,y）表示表示xyS（z,c）表示表示z的性别为的性别为c；W（w,d）表示表示w的工龄为的工龄为d；E（u，e）表示表示u的文化程度为的文化程度为e；R（t）表