人工智能知识表示方法.ppt

人工智能与专家系统 第2章知识表示方法 2 1一阶谓词逻辑表示方法 2 2产生式表示方法 知识表示是对知识的一种描述 或者说是一组约定 是一种计算机可以接受的用于描述知识的数据结构 知识外部表示模式 是与软件开发与运行的软件工具与平台无关的知识表示的形式化描述 知识内部表示模式 是与开发软件工具与平台有关的知识表示的存储结构 2 1一阶谓词逻辑表示方法 2 1 1一阶谓词逻辑2 1 2一阶谓词逻辑表示方法 2 1 1一阶谓词逻辑 1命题命题是具有真假意义的语句 命题代表人们进行思维时的一种判断 或者是肯定 或者是否定 谓词谓词 谓词可分为谓词名与个体两部分 个体表示某个独立存在的事物或者某个抽象谓词的概念 谓词名用于刻画个体的性质 状态或个体间的关系 一阶谓词的一般形式为 P x1 x2 xn 其中 P是谓词名 x1 x2 xn是个体 一阶谓词中的个体可以是常量 也可以是变元 还可以是一个函数 个体常量 个体变元 函数统称为 项 规定 谓词名或谓词名的第一个字符用大写字符表示 项中的常量 或常量的第一个字符 用大写字符表示 项中的变元和函数名 或函数名的第一个字符 以及函数的变元都用小写字符表示 谓词公式 1 连词 非连词 或连词 用 连接两个命题称为析取 与连词 用 连接两个命题称为合取 蕴合连词 它表示 如果P 则Q 其中P称为前件 Q称为后件 2 量词 全称量词 x 表示对个体域X中的所有 或任一个 个体x 存在量词 x 表示在个体域X中存在个体x 例 若谓词P x 表示x是正数 F x y 表示x与y是朋友 则 x P x 表示个体域X中的所有个体x都是正数 x y F x y 表示对于个体域X中的任何个体x 在个体域Y中都存在个体y x与y是朋友 x y F x y 表示在个体域X中存在个体x 他与个体域Y中的任何个体y都是朋友 x y F x y 表示在个体域X中存在个体x和在个体域Y中存在个体y x与y是朋友 3 谓词公式由下述规则得到的谓词公式称为合式公式 单个谓词和单个谓词的否定称为原子谓词公式 原子谓词公式是合式公式 若A是合式公式 则 A也是合式公式 若A B都是合式公式 则A B A B A B也都是合式公式 若A是合式公式 x是任一个体变元 则 x A和 x A也都是合式公式 在合式公式中 连词的优先级别依序为 4谓词公式的解释在命题逻辑中 对命题公式中各个命题的一次真值指派称为命题公式的一个解释 一个谓词公式的解释可能有很多个 对于每一个解释 谓词公式都可求出一个真值 T或F 例2 1设变元x和y的个体域是D 1 2 谓词P x y 表示x大于等于y 给出公式A x y P x y 在D上的解释 指出每一种解释下公式A的真值 解 设对谓词P x y 在个体域D上的真值指派为 P 1 1 T P 1 2 F P 2 1 T P 2 2 T这就是公式A在D上的一个解释 在此解释下 因为x 1时有y 1使P x y 的真值为T x 2时也有y 1使P x y 的真值为T 即x对于D中的所有取值 都存在y 1 使P x y 的真值为T 所以在此解释下公式A的真值为T 例2 2设个体域D 1 2 给出公式R x P x Q f x B 在D上的一个解释 指出公式R在此解释下的真值 解 设对个体常量B指派D中的一个元素为B 1 对函数f x 指派到D的映射为 f 1 2 f 2 1设对谓词指派的真值为 P 1 F P 2 T Q 1 1 T Q 2 1 F由于已对个体常量B指派B 1 所以Q 1 2 与Q 2 2 不可能出现 故没有给它们指派真值 上述指派就是对公式R的一个解释 在此解释下 由于当x 1时 有P 1 F Q f 1 1 Q 2 1 F所以P 1 Q f 1 1 的真值为T 当x 2时 有P 2 T Q f 2 1 Q 1 1 T所以P 2 Q f 2 1 的真值也为T 即对个体域D中的所有x都有P x Q f x B 的真值为T 所以公式R在此解释下的真值为T 可见 谓词公式的真值是针对某一个解释而言的 它可能在某一个解释下的真值为T 在另一个解释下的真值为F 5谓词公式的永真性 可满足性 不可满足性定义2 2 如果谓词公式P对个体域D上的任何一个解释都取得真值T 则称公式P在域D上是永真的 如果P在每个非空个体域上均永真 则称P是永真的 可见 为了判定某个公式永真 必须对每个个体域上的每一个解释逐一判定公式的真值 定义2 3 对于谓词公式P 如果至少存在一个解释使得公式P在此解释下的真值为T 则称公式P是可满足的 定义2 4 如果谓词公式P对于个体域D上的任何一个解释都取得真值F 则称公式P在域D上是永假的 如果P在每个非空个体域上均永假 则称P是永假的 谓词公式的永假性又称为不可满足性 6谓词公式的等价性定义2 5 设P与Q是两个谓词公式 D是它们共同的个体域 若对D上的任何一个解释 P与Q都有相同的真值 则称公式P和Q在D上是等价的 如果D是任意的个体域 则称P和Q是等价的 记为PQ 主要的等价式 1 交换律P QQ PP QQ P 2 结合律 P Q RP Q R P Q RP Q R 3 分配律P Q R P Q P R P Q R P Q P R 4 狄 摩根律 P Q P Q P Q P Q 5 双重否定律 PP 6 吸收律P P Q PP P Q P 7 补余律P PTP PF 8 连词化归律P Q P Q 9 量词转换律 x P x P x P x P 10 量词分配律 x P Q x P x Q x P Q x P x Q 谓词公式的永真蕴含定义2 6 对于谓词公式P和Q 如果P Q永真 则称P永真蕴含Q 且称Q为P的逻辑结论 称P为Q的前提 记为PQ 8推理规则 定理与证明推理规则用来由已知的合式公式推导出新的合式公式 导出的合式公式称为定理 而所使用的推理规则的序列则构成该定理的一个证明 2 1 2一阶谓词逻辑表示方法 1一阶谓词逻辑表示方法用谓词公式表示知识时 应按以下步骤进行 1 定义谓词 给出每个谓词的确切含义 2 用连词把有关谓词连接起来表示一个更复杂的含义 3 对谓词公式中的变元 根据知识表示的需要 把需要约束的变元用相应的量词予以约束 例2 3用谓词公式表示下列知识 王林是计算机系的学生 但他不喜欢编程序 人人爱劳动 解 1 定义谓词COMPUTER x 表示x是计算机系的学生LIKE x y 表示x喜欢yLOVE x y 表示x爱yMAN x 表示x是人 2 谓词公式知识表示COMPUTER WangLin LIKE WangLin Programing x MAN x LOVE x Labour 例2 4用谓词公式表示下列知识 自然数是大于零的整数 所有整数不是偶数就是奇数 偶数除以2是整数 解 1 定义谓词N x 表示x是自然数I x 表示x是整数E x 表示x是偶数O x 表示x是奇数GZ x 表示x大于零 2 谓词公式知识表示 x N x GZ x I x x I x E x O x x E x I f x 其中 函数f x x 2 例2 5已知F1 王 Wang 先生是小李 Li 的老师 F2 小李与小张 Zhang 是同班同学 F3 如果x与y是同班同学 则x的老师也是y的老师 求 小张的老师是谁 解 1 定义谓词T x y x是y的老师 C x y x与y是同班同学 2 谓词公式知识表示 已知前提及待求解问题 F1 T Wang Li F2 C Li Zhang F3 x y z C x y T z x T z y G x T x Zhang 例2 6设A B C三人中有人从不说真话 也有人从不说假话 某人向这三人分别提出同一个问题 谁是说谎者 A答 B和C都是说谎者 B答 A和C都是说谎者 C答 A和B中至少有一个是说谎者 求谁是老实人 谁是说谎者 解 1 定义谓词T x 表示x说真话 2 谓词公式知识表示如果A说的是真话 则有T A T B T C 如果A说的是假话 则有T A T B T C 对B和C说的话作相同的处理 可得 T B T A T C T B T A T C T C T A T B T C T A T B 一阶谓词逻辑表示方法的优点 1 自然性 2 精确性 3 严密性 4 容易实现 一阶谓词逻辑表示方法的局限性 1 不能表示不确定性的知识 2 组合爆炸 3 效率低 2 2产生式表示方法 2 2 1产生式与产生式系统2 2 2产生式系统的分类及其特点 2 2 1产生式与产生式系统 1 产生式的基本形式产生式基本形式是 P Q或者ifPthenQ蕴含式与产生式的差别 蕴含式只能表示精确知识 产生式可以表示精确知识 也可以表示不精确知识 蕴含式要求匹配是精确的 产生式匹配可以是精确的 也可以是不精确的 2 产生式系统产生式系统 把一组产生式放在一起 并让它们互相配合 协同作用 一个产生式生成的结论可以供另一个产生式作为已知事实使用 以求得问题的解决 1 规则库用于描述相应领域内知识的产生式集合称为规则库 例2 7建立一个动物识别系统的规则库 用以识别虎 豹 斑马 长颈鹿 企鹅 鸵鸟 信天翁等7种动物 解 为了识别这些动物 可以根据动物识别的特征 建立包含下述规则的规则库 R1 if动物有毛发then动物是哺乳动物R2 if动物有奶then动物是哺乳动物R3 if动物有羽毛then动物是鸟R4 if动物会飞and会生蛋then动物是鸟R5 if动物吃肉then动物是食肉动物R6 if动物有犀利牙齿and有爪and眼向前方then动物是食肉动物R7 if动物是哺乳动物and有蹄then动物是有蹄类动物 R8 if动物是哺乳动物and反刍then动物是有蹄类动物R9 if动物是哺乳动物and是食肉动物and有黄褐色and有暗斑点then动物是豹R10 if动物是哺乳动物and是食肉动物and有黄褐色and有黑色条纹then动物是虎R11 if动物是有蹄类动物and有长脖子and有长腿and有暗斑点then动物是长颈鹿R12 if动物是有蹄类动物and有黑色条纹then动物是斑马R13 if动物是鸟and不会飞and有长脖子and有长腿and有黑白二色then动物是鸵鸟R14 if动物是鸟and不会飞and会游泳and有黑白二色then动物是企鹅R15 if动物是鸟and善飞then动物是信天翁 2 综合数据库综合数据库又称为全局数据库 或称为事实库 黑板 用于存放问题求解过程中各种当前信息 例如问题的初始事实 原始证据 推理中得到的中间结论以及最终结论 综合数据库的内容随着推理的进行是在不断动态变化的 3 控制机构控制机构又称为推理机构或推理机 由一组程序组成 实现对问题的推理求解 2 2 2产生式系统的分类及其特点 1可交换的产生式系统如果一个产生式系统对规则的使用次序是可交换的 无论先使用哪一条规则都可达到目的 即规则的使用次序对问题的最终求解是无关紧要的 则称为可交换的产生式系统 例 设DB的初始状态是 A B C 并设RB中有下述规则 R1 if A B C then A B C A B R2 if A B C then A B C B C R3 if A B C then A B C A C 推理终止条件是综合数据库DB中的内容变为 A B C A B B C A C 三条规则各被使用一次后就可达到目的 且与规则使用的次序无关 所以由上述RB和DB构成的产生式系统是一个可交换的产生式系统 在可交换产生式系统中 综合数据库DB中的内容是递增的 即对任意一个规则执行序列R1 R2 Rk都有由此可见 用可交换产生式系统求解问题时 推理过程不必进行回溯 2可分解的产生式系统如果一个产生式系统的综合数据库DB的当前状态DBi可被分解为若干个独立的部分 且根据DB的状态确定的推理过程的终止条件也可被分解为对这些独立部分进行推理的终止条件 则称为可分解的产生式系统 例 设DB的初始内容为DBo D B Z RB中有如下规则 R1 ifCthen D L R2 ifCthen B M R3 ifBthen M M R4 ifZthen B B M 终止条件是生成只包含M的综合数据库 即使综合数据库的内容变为 M M M 图2 1可分解的产生式系统示例 3可恢复的产生式系统在问题求解过程中既可以对综合数据库添加新内容 又可删除或修改老内容的产生式系统称为可恢复的产生式系统 4产生式表示法的特点 1 自然性 2 模块性 3 有效性 4 清晰性