用于人工智能的Prolog语言.ppt

用于人工智能的Prolog语言 归结原理与Prolog语言 家庭关系程序示例 TurboProlog程序结构 表与递归 Prolog程序分析 本章主要内容 文件与数据库 字符串处理 回溯及控制 输入与输出 1 Prolog是一种逻辑程序设计语言 基于一阶谓词逻辑 是典型的叙述型语言 DeclarationLanguage Prolog语言的特点 1 建立在一阶谓词逻辑和归结原理基础上 有自动推理功能 2 用Prolog设计应用程序时 仅需指明领域中各对象间的关系和决策规则 而应用这些知识的推理由Prolog完成 3 Prolog应用程序 由数据库和规则库组成 4 Prolog程序设计要做三件事 即说明事实 定义规则 提出问题 4 1归结原理与Prolog语言 2 Prolog有三种形式的语句 1 B A1 A2 An 含义是A1 A2 An B 相当于 A1 A2 An B 可视作人工智能系统中的推理规则 也可将该句看作一个过程 B为过程头 是过程名 而 A1 A2 An 为过程体 2 A1 A2 An 含义是A1 A2 An F 相当于 A1 A2 An 可视作推理的目标 或称目标子句 3 B 含义是公式B无条件地为真 可视作已知的事实 x M x R x M 张三 R 张三 如三段论 推理规则 R X M X 事实 M 张三 目标 R 张三 Prolog语句 3 证明公式 M X R X M 张三 R 张三 恒真 即证明公式 M X R X M 张三 R 张三 恒假 化成公式集 M X R X M 张三 R 张三 子句集 M X R X M 张三 R 张三 推理规则 事实 目标 子句B A1 A2 An 和子句B 都是仅有一个正文字的子句 称作定子句 目标子句A1 A2 An 是没有正文字出现的子句 定子句和目标子句统成为Horn子句 Prolog子句都是Horn子句 4 用Prolog证明三段论 推理规则 R X M X 事实 M 张三 目标 R 张三 M 张三 完整的Prolog程序 predicatesM symbol R symbol clausesR X M X M zhsan goalR zhsan 运行 5 4 2家庭关系程序示例 下图是一个表示家庭关系的实例 parent pam bob parent tom bob parent tom liz parent bob ann parent bob pat parent pat jim 用Prolog语句表示为 6 完整的Prolog程序 predicatesparent symbol symbol clausesparent pam bob parent tom bob parent tom liz parent bob ann parent bob pat parent pat jim 此程序可以回答的问题 1 bob是pat的父母吗 parent bob pat 2 liz是pat的父母吗 parent liz pat 3 谁是liz的父母 parent X liz 4 谁是谁的父母 parent X Y 1 系统回答 2 系统回答 3 系统回答 4 系统回答 7 5 谁是jim的祖父母 分析 程序中并没有直接的祖父母关系 此问题可分两步 1 谁是jim的父母 假设是Y 2 谁是Y的父母 假设是X X jim Y parent parent grandparent Prolog目标语句 parent Y jim parent X Y 6 类似的问题可以是 谁是tom的孙子 prolog目标语句 parent tom X parent X Y 5 系统回答 6 系统回答 parent pam bob parent tom bob parent tom liz parent bob ann parent bob pat parent pat jim clauses 8 以上程序说明的几个重要观点 1 在Prolog中定义一个关系是容易的 可以通过满足关系的n个对象来表达 2 对程序中已定义的关系 用户可以轻而易举地询问Prolog系统 3 关系的对象可以是常量 如 tom ann 也可以是变量 如 X Y 4 向系统提出问题 可由一个或多个目标组成 5 一个Prolog程序由一些子句 clauses 组成 每个子句用句号结束 6 对一个问题的回答是肯定的或者是否定的 取决于相应的目标是否满足 在肯定回答的情况下 说相应的目标是可满足的 而且这个目标成功了 否则 说目标不可满足 目标失败了 7 如果有多个回答都满足目标 那么Prolog将尽可能多地回答 9 Predicatesparent symbol clausesparent pam bob parent tom bob parent tom liz parent bob ann parent bob pat parent pat jim male tom male bob male jim female pam female liz female pat female ann 在示例程序中 添加有关性别的信息 10 在Prolog中定义offspring 后代 关系 对所有的X和Y Y是X的后代 如果X是Y的父母 对应的prolog语句为 offspring Y X parent X Y 子句头 子句体 注意 以上定义的是直接后代关系 对于间接后代 对所有的X和Y Y是X的后代 如果Z是Y的父母 且Z是X的后代 offspring Y X parent Z Y offspring Z X 对应的prolog语句为 X Y Z parent offspring offspring 11 关于sister的规则定义 predicatesparent symbol symbol sister symbol symbol female symbol male symbol clausesparent pam bob parent tom bob parent tom liz parent bob ann parent bob pat parent pat jim male tom male bob male jim female pam female liz female ann female pat sister X Y parent Z X parent Z Y female X goalsister X pat 运行 Pat的姐妹是谁 12 predicatesparent symbol symbol sister symbol symbol female symbol male symbol different symbol symbol clausesparent pam bob parent tom bob parent tom liz parent bob ann parent bob pat parent pat jim male tom male bob male jim female pam female liz female ann female pat sister X Y parent Z X parent Z Y female X different X Y different X Y XY goalsister X pat 改进的sister规则 运行 Pat的姐妹是谁 13 mother规则 对所有的X和Y X是Y的母亲 如果X是Y的父母 并且 X为女性 用prolog规则表示为 mother X Y parent X Y female X predicatesparent symbol symbol mother symbol symbol female symbol male symbol clausesparent pam bob parent tom bob parent tom liz parent bob ann parent bob pat parent pat jim mother X Y parent X Y female X male tom male bob male jim female pam female liz female ann female pat goalmother pat X Pat是谁的母亲 运行 14 4 3TurboProlog程序结构 一个TurboProlog程序通常包括5个部分 如下 注释 domains域说明database数据库说明predicates谓词说明goal目标说明clauses子句说明 注释 1 域说明部分 说明谓词对象的数据类型 2 数据库说明部分 包含一些数据库谓词的定义 是说明用于动态数据库管理的谓词 如果程序不需要动态数据库 该部分可省略 3 谓词说明部分 定义程序中除内部谓词以外的所有谓词 4 在目标部分 说明程序的目标 一个程序目标可以由多个字目标复合而成 5 子句部分 列出全部事实和规则 也可看作是程序的静态数据 15 程序名 Wordsmith文件名 prog0501 pro 目标 查找并打印一单词的同义词或反义词 domainsword syn ant symbolpredicatessynonym word syn antonym word ant goalsynonym brave X antonym brave Y write brave的同义词是 X nl write brave的反义词是 Y nl clausessynonym brave daring synonym honest truthful synonym modern new synonym rare uncommon antonym brave cowardly antonym honest dishonest antonym mordern ancient antonym rare common 4 4TurboProlog程序分析 16 程序名 Thesaurus文件名 prog0502 pro 目标 建立一个打印单词的同义词和反义词的小词典 domainsword syn1 syn2 syn3 ant1 ant2 ant3 symbolpredicatessynonym word syn1 syn2 syn3 antonym word ant1 ant2 ant3 goalsynonym brave S1 S2 S3 antonym brave A1 A2 A3 write brave的同义词是 nl write S1 S2 S3 write brave的反义词是 nl write A1 A2 A3 nl clausessynonym brave daring defiant courageous synonym honest truthful open sincere synonym modern new novel recent synonym rare uncommon scrace infrequent antonym brave cowardly fearful timid antonym honest dishonest crooked deceltful antonym mordern ancient old obsolete antonym rare common ordinary ubiquitous 多元谓词 多元子句 17 程序名 Presidents文件名 prog0503 pro 目标 使用混合对象类型举例 domainsname party state symbolbirth year year in year out integerpredicatespresident name party state birth year year in year out goalpresident X democrat S Yb Yi Yo nl write X democrat nl write State S nl write Birth year Yb nl write Year in Yi nl write Year out Yo nl nl clausespresident elsenhower republican texas 1890 1953 1961 president kennedy democrat massachusetts 1917 1961 1963 president johnson democrat texas 1908 1963 1969 president nixon republican california 1913 1969 1974 president ford republican nebraska 1913 1974 1977 president carter democrat georgia 1924 1977 1981 混合域的使用 18 程序名 Rlatives文件名 prog0504 pro 目标 规则结构举例 domainsperson symbolpredicatesmale person female person parents person person person sister person person who is the sistergoalwho is the sister clauses 事实 male Frank male Sam female Mary female Debbie parents Sam Frank Mary parents Debbie Frank Mary 规则 who is the sister sister Sister Brother write Sister isthesisterof Brother nl sister Sister Brother female Sister male Brother parents Sister Father Mother parents Brother Father Mother 目标中使用规则 19 domainsman symbolpredicateschoice man short height man medium height man tall height man black hair man brown hair man blond hair man old car man new car man sports car man kathy choice man who is the choicegoalwho is the choice clauses 事实 choice bill choice jim choice mark choice robert choice willy 规则 who is the choice kathy choice Choice write Kathy schoiceis Choice nl kathy choice Choice choice Choice tall height Choice blond hair Choice sports car Choice choice tom choice frank short height mark short height willy medium height jim medium height tom tall height jim tall height robert tall height frank black hair bill black hair willy brown hair jim brown hair tom blond hair mark blond hair robert blond hair frank new car mark new car willy new car frank old car mark old car tom sports car jim sports car robert 简单数据库 20 程序名 Europair文件名 prog0506 pro 目标 否定谓词应用举例 domainscountry symbolpredicateseuro pair country country border country country find non border pairgoalfind non border pair clauseseuro pair France Germany euro pair France Spain euro pair France Italy euro pair Germany Spain euro pair Germany Italy euro pair Spain Italy border France Germany border France Spain border France Italy find non border pair euro pair X Y not border X Y write X Y nl 否定谓词的应用 21 domainspersonal library book title author publisher year collector title author publisher symbolyear integerpredicatescollection collector personal library clausescollection kahn book TheComputerandtheBrain vonNeumann YaleUniversityPress 1958 collection kahn book SymbolicLogic LewisCarroll DoverPublications 1958 collection john book Database APrimer C J Date Addison Wesley 1983 collection john book Problem SolvingMethodsinAI NilsNilsson McGraw Hill 1971 collection smith book Alice inWonderland LewisCarroll TheNewAmericanLibrary 1960 collection smith book FablesofAesop Aesop Calder DoverPublications 1967 复合对象的应用 22 域结构图 域 第0层 结构 第1层 对象 DomainStructureDiagram collection collector book title author publisher year 谓词结构图 PredicateStructureDiagram 谓词 主函子 函子 第0层 第1层 第2层 23 domainspersonal library book title author publication publication publication publisher year collector title author publisher symbolyear integerpredicatescollection collector personal library clausescollection kahn book TheComputerandtheBrain vonNeumann publication YaleUniversityPress 1958 collection kahn book SymbolicLogic LewisCarroll publication DoverPublications 1958 collection john book Database APrimer C J Date publication Addison Wesley 1983 collection john book Problem SolvingMethodsinAI NilsNilsson publication McGraw Hill 1971 collection smith book Alice inWonderland LewisCarroll publication TheNewAmericanLibrary 1960 collection smith book FablesofAesop Aesop Calder publication DoverPublications 1967 三层域结构和四层谓词结构 24 personal library book title author publication year 域结构图 域 第0层 第1层 DomainStructureDiagram collection collector book title author publisher year 谓词结构图 PredicateStructureDiagram 谓词 主函子 函子 第0层 第1层 第2层 publisher 第2层 publisher 第3层 25 4 5表与递归 表是含有任意数目的其他对象的一个对象 一个包含1 2 3的表可被写成 1 2 3 表中的每个项被称为一个元素 在域说明中需要对表类型进行说明 如 domainsintegerlist integer predicatesnumber integerlist 表头 是表中的第一个元素 如 表 a b c 中a是表头 表尾 是表中除表头外的另一张表 如 表 a b c 中 b c 是表尾 空表 没有元素的表 对于表 c c是表头 是表尾 a b c d a b c d b c d c d d 26 Prolog提供一种使表头和表尾明确分开的方法 用逗号将元素分开 用 号将表头和表尾分开 如 a b c 等价于 a b c 等价于 a b c 等价于 a b c 打印表中元素的例子 domains