人工智能知识表示方法谓词逻辑幻灯片.ppt

人工智能ArtificialIntelligence AI 曲维光wgqu 南京师范大学计算机学院 1 第2章知识表示方法2 1谓词逻辑法2 2状态空间法2 3问题归约法 2 2 1谓词逻辑法数理逻辑 符号逻辑 是用数学方法研究形式逻辑的一个分支 它通过符号系统来表达客观对象以及相关的逻辑推理 常用的是命题逻辑和谓词逻辑 3 谓词逻辑是数理逻辑的基本形式 是基于谓词分析的一种形式化 数学 语言人工智能中的谓词逻辑法是指用一阶谓词来描述问题求解和定理证明 限于本课程 4 2 1 0命题逻辑的复习 1 命题逻辑的基本概念命题是能够判断真或假的陈述句通常用大写字母来表示 如A B P Q等命题的真假值一般用T或F来表示 5 例 雪是白的 陈述句 T 雪是可蓝的 陈述句 F 雪是黑的 陈述句 F 他是学生 陈述句 他泛指 无法判断真假 你今天上课没有 疑问句 请坐校车 祈使句 6 命题逻辑是研究命题及命题之间关系的符号逻辑系统 在命题逻辑中 表示单一意义的命题 称之为原子命题 原子命题通过 联结词 构成复合命题 7 五个联结词 表示 非 复合命题 P为真 当且仅当P为假 表示 合取 复合命题 P Q 为真 当且仅当P和Q都为真 8 表示 蕴含 复合命题 P Q 为假 当且仅当P为真且Q为假 表示 析取 复合命题 P Q 为真 当且仅当P Q两者之一为真 9 表示 等价 复合命题 P Q 为真 当且仅当P Q同时为真 或者同时为假 联接词的优先顺序 非 合取 析取 蕴含 等价 注 可以用括号表示优先级 10 真值表 11 命题变元 用符号P Q等表示的不具有固定 具体含义的命题 它可以表示具有 真 假 含义的各种命题 命题变元可以利用联结词构成所谓的合适公式 12 合适公式的定义 若P为原子命题 则P为合适公式 称为原子公式 若P是合适公式 则 P也是一个合适公式 13 若P和Q是合适公式 则P Q P Q P Q P Q都是合适公式 经过有限次使用规则1 2 3 得到的由原子公式 联结词和园括号所组成的符号串 也是合适公式 14 对于合适公式 规定下列运算优先级 逻辑联结词的运算优先次序为 同级联结词按出现顺序优先运算 15 在命题逻辑中 主要研究推理的有效性 即 能否根据一些合适公式 前提 推导出新的合适公式 结论 一些合适公式 前提条件 合适公式 结论 16 在命题逻辑中 最基本的单元是命题 它是作为一个不可分割的整体 例如 雪是黑的命题逻辑具有较大的局限性 不合适于表达比较复杂的问题 17 例 所有科学都是有用的 假设1 数理逻辑是科学 假设2 所以 数理逻辑是有用的 结论 很明显 我们无法用两个假设推断出结论 18 谓词逻辑是命题逻辑的扩充和发展 它将一个原子命题分解成客体和谓词两个组成部分 例如 雪是黑的客体谓词本课程主要介绍一阶谓词逻辑 19 2 1 1谓词演算 1 语法与语义谓词逻辑的基本组成部分谓词变量函数常量圆括号 方括号 花括号和逗号 20 例 机器人 Robot 在第一个房间 r1 内 可以表示为 INROOM ROBOT r1 其中INROOM是谓词ROBOT和r1是常量 21 谓词是指个体 客体 所具有的性质或者若干个体之间的关系 用大写字母来表示 个体是可以具体的 如 小张 3 5 也可以是抽象的 如 x y 22 例 小明是学生 A表示是 是学生 x表示 小明 记作A x x大于y G表示 大于 记作G x y 23 论域 由个体组成的集合 个体 变量 定义在某一个论域上的变量 用x y z来表示 函数 或函词 以个体为变量 以个体为值的函数 一般用小写字母来表示 例如f x f x a 24 如果谓词有n个变量 称之为n元谓词 并约定0元谓词就是命题 谓词的特例 如果函数有n个个体 称之为n元函数 并约定0元函数就是常量 常量习惯上用小写字母来表示 如a b c 25 项的定义 常量是项 变量是项 如果f是n元函数 且t1 tn n 1 是项 则f t1 tn 也是项 所有的项都必须是有限次应用上述规则产生的 26 项的例子 常量 a变量 x函数 f x a g f x a 27 原子 谓词 公式的 递归 定义 原子命题是原子公式 如果t1 tn n 1 是项 P是谓词 则P t1 tn 是原子公式 其它表达式都不是原子公式 28 原子公式的例子1 原子公式 P 原子命题 2 项 x a f x a 谓词 P原子公式 P x a f x a 29 2 连词和量词 联结词 连词 就是命题逻辑中的五个 它们的含义也是一样的 30 两个量词 全称量词 记作 x 含义是 对每一个x 或 对一切x 存在量词 记作 x 含义是 存在某个x 有一个x 或者 某些x 31 例1 所有的机器人都是灰色的 用谓词逻辑可以表示成 x ROBOT x COLOR x gray 32 例2 一号房间里有一个物体 可以表示成 x INROOM x r1 33 我们称x是被量化了的变量 称为约束变量 否则称之为自由变量 一阶谓词 只允许对变量施加量词 不允许对谓词和函数施加量词 34 2 1 2谓词公式 1 谓词公式的定义 利用连词和量词可以将原子 谓词 公式组成复合谓词公式 称之为分子谓词公式 谓词合适公式 谓词公式 合适公式 35 谓词 合适公式的 递归 定义 原子 谓词 公式是合适公式 若A是合适公式 则 A也是合适公式 若A和B是合适公式 则A B A B A B A B也是合适公式 36 若A是合适公式 x为A的自由变元 变量 则 x A和 x A都是合适公式 只有按上述规则求得的公式才是合适公式 37 例 任何整数或者为正或者为负 数学表达 对于所有的x 如果x是整数 则x或者为正 或者为负 记作 I x x是整数 P x x是正数 N x x是负数 谓词公式 x I x P x N x 38 2 合适公式的性质 如果P和Q是合适公式 则由这两个合适公式构成的合适公式的真值表与前面介绍的真值表相同 如果两个合适公式的真值表相同 则我们称这两个合适公式是等价的 可以用 来表示 39 对于命题合适公式和谓词合适公式有下列等价关系 否定之否定 P 等价于P P Q等价于 P Q 狄 摩根定律 P Q 等价于 P Q P Q 等价于 P Q 40 分配律P Q R 等价于 P Q P R P Q R 等价于 P Q P R 交换律P Q等价于Q PP Q等价于Q P 41 结合律 P Q R等价于P Q R P Q R等价于P Q R 逆否律P Q等价于 Q P 说明 上述等价关系对命题合适公式 谓词合适公式都成立 42 对于谓词合适公式有下列等价关系 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 43 x P x 等价于 y P y x P x 等价于 y P y 注释 这两个关系说明 在一个量化的表达式中的约束变量是一类虚元 它们可以用任何不在表达式中出现的其它变量来代替 44 2 1 3置换与合一 1 置换 置换的定义 形如 t1 v1 tn vn 的集合 称为一个置换 其中vi是不同的变量 ti是与vi不同的项 45 例或例子的定义 设 t1 v1 tn vn 为一个置换 E是一个原子谓词公式 则E 表示将E中的vi同时用ti i 1 n 代入后所得到的结果 E 称为E的一个例子 46 例 表达式 原子谓词公式 P x f y B 的四个置换及其对应的四个例子 B是常量 s1 z x w y s2 A y s3 q z x A y s4 c x A y P x f y B s1 P z f w B P x f y B s2 P x f A B P x f y B s3 P q z f A B P x f y B s4 P c f A B P x f y B 47 置换的合成 设 t1 x1 tn xn 和 s1 y1 sm ym 是两个置换 则 和 的合成是如下置换 t1 x1 ti xi tn xn s1 y1 sn ym 其中 yj是 x1 xn 之一者消去 对于任何tj xj者消去 并记成 48 如何求ti s1 y1 sm ym 如果ti出现 y1 ym 中的变量yi 则用其对应的项si来代替 49 例 t1 x1 t2 x2 f y x z y s1 y1 s2 y2 s3 y3 a x b y y z t1 x1 t2 x2 s1 y1 s2 y2 s3 y3 f b x y y a x b y y z f b x y z 50 注意 置换的合成满足结合律 不满足交换律 s1s2 s3 s1 s2s3 满足结合律 s1s2 s2s1 不满足交换律 51 例 s1 z x w y s2 A y s1s2 z x w y A y z x w y s2s1 A y z x w y A y z x 52 2 合一 当某一个置换s作用于表达式集合 Ei 的每一个元素 此时我们用 Ei s来表示置换例子的集合 如果存在一个置换s 使得E1s E2s Eis 则我们称表达式集合 Ei 是可合一的 并称s为 Ei 的合一者 原因是它的作用是使集合 Ei 成为单一形式 其中 Ei是原子谓词公式 53 例 表达式集合 P x f y B P x f B B 的合一者为是s A x B y P x f y B s P A f B B P x f B B s P A f B B 54 如果s是 Ei 的任意一个合一者 又存在某一个s 使得s gs 或者 Ei s Ei gs 则称g是 Ei 的最通用 最一般 的合一者 记作mgu 55 例 s A x B y 是表达式集合 P x f y B P x f B B 的一个合一者 该集合的最一般的合一者是 g B y 56 3 合一算法 分歧集 或不一致集合 的定义 设有一非空有限公式集合F F1 Fn 从F中各个公式的第一个符号同时向右比较 直到发现第一个彼此不尽相同的符号为止 从F中的各个公式中取出那些以第一个不一致符号开始的最大的子表达式为元素 组成一个集合D 称为F的分歧集 不一致集合 其中 Fi i 1 n 是原子谓词公式 57 例 公式集 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 有的可以合一 有的则不能 58 设F为非空有限表达式集合 则可以按下列步骤求出mgu 置k 0 Fk F k 空置换 即不含元素的置换 若Fk只有一个表达式 则算法终止 其中 k就是要求的mgu 找出Fk的分歧集Dk 合一算法 59 若Dk中存在元素ak和tk 其中ak是变元 tk是项 且ak不在tk中出现 则置 k 1 k tk ak Fk 1 Fk tk ak k k 1然后转向 否则 继续 算法终止 F的mgu不存在 60 合一算法的流程图 k 0 Fk F k Fk 1 求得mgu 结束 求出不一致集合 有置换 求出新置换 更新公式集合与旧置换 k 无解 结束 61 说明 1 合一算法是消解原理的基础 2 合一算法中的公式集就是从谓词合适公式化成的子句集 62 例 求F P a x f g y P z h z u f u 的最一般的合一者 解 我们根据合一算法一步一步地求出mgu 63 第一步 k 0 F0 F 0 F0的分歧集合D0 a z 置换 a z 1 0 a z a z F1 F0 a 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 z u f u 64 第二步 D1 x h a u 置换 h a u x 2 1 h a u x a z h a u x F2 F1 h a u x P a h a u f g y P a h a u f u k 2 F P a x f g y P a h a u f u 65 第三步 D2 g y u 置换 g y u 3 2 g y u a z h a g y x g y u F3 F2 g y u P a h a g y f g y k 3 F P a h a u f g y P a h a u f u 66 F3是单一表达式