人工智能chp40.ppt

人工智能 AI 第四章 0 人工智能中的一级谓词逻辑4 0 1一级谓词演算的基本体系4 0 2归结 消解Resolution 4 0 3归结反演系统 Refutation 4 0 4基于归结法的问答系统参考书 人工智能原理与技术 俞瑞钊 史济建浙江大学出版社 人工智能基础 高济 朱淼良高等教育出版社 人工智能导论 林尧瑞 马少平清华大学出版社 第四章人工智能中的谓词逻辑传统的形式逻辑始于古希腊的亚里士多德 已有两千多年的历史 它是人类思维的形式和规律 17世纪70年代数学中的形式化表示方法引入逻辑研究领域 经过几代科学家出色工作已发展成为数理逻辑的重要方向之一 4 1命题及逻辑连接词定义 命题是能够判断真假的陈述句 例如 1 雪是白的 是 2 他是工人 不是 3 19是3和6的倍数 是 4 请乘坐汽车去 不是 一般情况下用P Q R等大写符号表示命题 第四章人工智能中的谓词逻辑逻辑连接词定义 逻辑 非 命题P的非记成 P P为真当且仅当P假 合取 P Q表示不仅P而且Q P Q真P和Q为真 析取 命题P Q为真当且仅当其中有一个为真 蕴涵 P Q意思是如果P则Q 结果为假当且仅当P为真且Q为假 等价 PQ为真当且仅当P Q同时为真或同时为假 第四章人工智能中的谓词逻辑例子1 命题P表示 昨天下雨 Q表示 昨天开会 则 昨天下雨且开会 表示成P Q 例子2 P表示 6大于4 Q表示 3大于4 R表示 18大于16 则 如果6大于4 3不大于4 则18不大于16 写成 P Q R 注意 符号表达语句时首先要确切 与原语句涵义一致 其次对于复合命题都要写成原子命题联结 如用P表示 18是6和9的公倍数 是错误的 例子3 小张不会德文也不会法文 用P表示 小张会德文 Q表示 小张会法文 则原语句写成 P Q 第四章人工智能中的谓词逻辑4 2命题公式得永真性与等值定义 公式 1 原子命题是命题公式 2 若 是命题公式 则 也是命题公式 3 如果 是命题公式 那么 也都是命题公式 4 所有命题公式都是有限次应用上述规则得到的 判断一个字符串是否公式的方法是将任意由五个联结符连接的原子命题用一个原子命题表示 例 P Q R P Q 1 P R P 2 P R P 3 PP 4 P 3 P所以 是命题公式 第四章人工智能中的谓词逻辑指派 命题公式 含有n个不同的原子命题P1 Pn 它的任意一组确定值 P01 P0n P0i t f 称为 的一个指派 指派分为成真指派 成假指派 永真公式 若 的任一指派都使 为真 假 则称 为永真 假 公式 存在成真指派则也称 为可满足公式 下面是三个永真公式 P P Q P Q P P Q R S P R Q S 一般情况下可以列出公式的真值表确定其永真性 等值公式 设两公式 对于任意指派都同时取相同的真假值 则称 为等值公式 记成 常用的等值公式表 第四章人工智能中的谓词逻辑替换定理 设公式 是公式 的部分公式 则将 中 的某些出现替换成与 等值的公式 得到的新公式 代入规则 等值 公式中用任一公式代入等值公式中任一原子命题 处处代入 则仍为等值公式 例子1 设 P Q R 由于 Q P Q P 所以用右侧的公式代入 的部分公式 Q P 中得到的新公式与原公式等值 即 P Q R P Q P 利用上述定理还可以证明一些新的复杂等值公式 但是我们时常需要判断一些公式的永真性和可满足性 最简单的方法是使用真值表 但当变元很多时 指派总数很大 非常麻烦 因此常用二杈树方法确定 性质 第四章人工智能中的谓词逻辑二杈树方法 例 P Q R P Q P R 将P用t代入作为左分支 f代入作为右分支 依次代Q R得 P Q R P Q P R Q R Q R R R t t R t R f Q t Q f P t P f t t 1 置值时可以从公式中选出现次数最多的符号首先指定值 2 根据二杈树方法还可以确定该公式所有的指派 第四章人工智能中的谓词逻辑4 3对偶定理 最小 完全联结词 任何一个公式 都能够用联结词集S表达成一个与 等值的公式 则S称为完全联结词集 若S中每个联结词都是独立的则称其为最小联结词集 常见的最小联结词集有 对偶公式 设 是由 表达的命题公式 将其中的 换成 换成 得到的新公式 称为 的对偶公式 引理 设 是 的对偶公式 且 中含有原子命题P1 Pn 则 P1 Pn P1 Pn 对偶定理 若 和 满足 则对偶公式 和 也满足 第四章人工智能中的谓词逻辑4 4析取范式和合取范式定义 若公式 是由一些原子命题或它的非利用合取联结词 组成的 则称 为简单合取式 简单析取式 即 由 或 与原子命题组成 如P1 P2 P3显然它们都有特殊的性质 如唯一的成真或成假指派 定理1 设 1 n为P1 Pm的公式 则合取式 1 n的成真指派等于 1 n成真指派的交集 而成假指派是 1 n成假指派的并集 定理2 任公式 都可以表示为简单合取式的析取 析取范式 也可以表示为简单析取式的合取 合取范式 第四章人工智能中的谓词逻辑上述定理表明知道一个公式的成真指派可以写出该公式 例题 设 有四个原子命题P1 P2 P3 P4 其成真指派为txft ftxf txxf 则对应的简单合取为P1 P3 P4 P1 P2 P4 P1 P4 则其析取范式为 P1 P3 P4 P1 P2 P4 P1 P4 任何都可以用等值公式将其化为析取 合取 范式 1 使用公式PQ P Q Q P P Q P Q消去联结词 及 2 使用 P P P Q P Q P Q P Q3 反复使用P Q R P Q P R P Q R P Q P R 将公式化为范式 第四章人工智能中的谓词逻辑例题1 将 P Q R S化为合取范式 P Q R S P Q R S P Q R S P Q R S P Q R S P Q P R S P Q S P R S 例题2 将 P Q R 化为析取范式 P Q R P Q R Q R P P Q R Q R P P Q R Q R P Q R P P Q R Q R Q R Q R P P Q P R Q R Q Q R R Q R P P Q P R P Q R 第四章人工智能中的谓词逻辑4 5逻辑推理例题1 如果天气干旱则粮食歉收 又设当粮食歉收时大多数人是不幸的 再设天气干旱 那么可以指出大多数人是不幸的 设相应的陈述表示为 P表天气干旱 S表粮食丰收 U表大多数人是幸运的 题目中相应的四个陈述分别表示为 P S S U P U 我们指出当上述表示均为真时 U为真 将上述式子的合取化为范式 P S S U P P P S S U P S U如果 P S S U P为真 那么P S U为真 进而必须P S U均为真 所以得U为假 此时逻辑上称 U是 P S S U 和P的逻辑结果 第四章人工智能中的谓词逻辑定义 设命题公式序列 1 n及命题公式 如果对任何使 1 n成真的指派也使 成真 则 称为 1 n的逻辑推论 逻辑结果 记成 1 n 定理1 设 1 n及 均为命题公式 则 1 n 当且仅当 1 n 是永真的 定理2 设 1 n及 均为命题公式 则 1 n 当且仅当 1 n 是永假的 证明 由上知 是逻辑结果当且仅当 1 n 是永真的 因此 1 n 是永假的 而 1 n 1 n 1 n 因此定理得证 第四章人工智能中的谓词逻辑4 6一级谓词逻辑的基本概念4 6 1谓词 谓词是指个体所具有的性质或若干个体之间的关系 如 数理逻辑是科学 分为两部分 主语 数理逻辑 与谓表语 是科学 3整除6 表现3和6间的整除关系 其中 数理逻辑 3 6 也可以是抽象的x y等称为个体变元 是科学 整除 是谓词 一般用A B C等表示谓词 如x y间的关系写成B x y 谓词中有n个体变元则称为n元谓词 0元谓词就是命题 记为P Q R等 为方便常用一些符号直接表示谓词 如 等于 直接用 表示 这样E x y 写成 x y 单独的谓词没有意义 必须赋予个体 通常把谓词填以个体后的式子称为谓词填式 如 张山高于李四 则张山高于王五 用A表示 高于 a b c分别表示 张山 李四 王五 则上述谓词填式表示为A a b A a c 第四章人工智能中的谓词逻辑4 6 2量词 量词有全称量词和存在量词 分别记为 x 和 x 意思为 对于所有的x 和 存在一个x 当写xP x 和 yQ x y 时称其为量词的作用域 x称为约束变元 y称为自由变元 变元的取值范围称为个体域 例 任何整数是正的或负的 用M x 表x是整数 P x 表x是正数 N x 表x是负数 则整个语句表示为x M x P x N x 而如果事先约定个体域是全体整数 则可以表示为x P x N x 注意在受量词约束的变元中 变元用什么记号是不重要的 如x P x N x 与y P y N y 是等价的 第四章人工智能中的谓词逻辑4 6 3函词 函词是以个体为变元 同时以个体为值的