4 知识表示方法 part2人工智能课件 西电

《4 知识表示方法 part2人工智能课件 西电》由会员分享，可在线阅读，更多相关《4 知识表示方法 part2人工智能课件 西电（48页珍藏版）》请在金锄头文库上搜索。

1、西安电子科技大学Artificial Intelligence (AI) 人工智能主讲：戚玉涛Email：qi_第二章：知识 表示方法西安电子科技大学内容提要第二章：知识表示方法第二章：知识表示方法1.状态空间法2.问题归约法3.谓词逻辑法4.语义网络法5.其他方法西安电子科技大学问题归约法v 问题归约（Problem Reduction） 是另外一种基于状态空间的问题描述与求解方法 已知问题的描述，通过一系列变换把此问题变为一个子问题 集合 这些子问题的解可以直接得到（本原问题），从而解决了初 始问题西安电子科技大学问题归约法v 问题归约法的组成部分一个初始问题描述；一套把问题变换为子问题的

2、操作符；一套本原问题描述。(本原问题:不能再分解或变换且直 接可解的子问题)v 问题归约的实质：从目标（要解决的问题）出发逆向推理，建立子问题以 及子问题的子问题，直到最后把初始问题归约为一个本 原问题集合。西安电子科技大学问题归约法v 问题归约法举例：汉诺塔问题（ Hanoi ） p 从1移到3p 每次移动一个盘子p 大盘在下小盘在上123CBA初始状态（111）目标状态（333）CBA西安电子科技大学汉诺塔问题v 原始问题可以归约为下列3个子问题：子问题1：移动圆盘移动圆盘A A和和 B B 至柱子至柱子2 2（借助柱子（借助柱子3 3）子问题2：移动圆盘移动圆盘C C至柱至柱 子子3 3

3、子问题3：把圆盘把圆盘A A和和B B移至移至 柱子柱子3 3（借助柱子（借助柱子1 1）西安电子科技大学汉诺塔问题v 归约过程（3个圆盘）西安电子科技大学汉诺塔问题v 汉诺塔问题归约图本原问题本原问题与或图CBA西安电子科技大学问题归约法v 与或图表示：用一个类似于图的结构来表示把问题归约为 后继问题的替换集合。 与图：把一个复杂问题 分解为若干个较为简单的 子问题，形成“与”树。 或图：把原问题变换为 若干个较为容易求解的新 问题，形成“或”树。西安电子科技大学问题归约法v 与或图表示：BCDEFGAHMBCDEFGAN子问题替代集合结构图与或图西安电子科技大学问题归约法v 一些关于与或图

4、的术语起始节点 对应于原 始问题描 述终叶节点对应于本原问题西安电子科技大学问题归约法v 与或图的构成规则 1）与或图中的每个节点代表一 个要解决的单一问题或问题集合 。图中所含起始节点对应于原始 问题A。 2）对应于本原问题的节点称为 终叶节点，它没有后继节点。 3）对于把算符应用于问题A的每 种可能情况，都把问题变换为一 个子问题集合；有向弧线自A指 向后继节点表示所求得的子问题 集合。HMBC DEFGAN西安电子科技大学问题归约法v 与或图的构成规则 4）一般对于代表两个或两个以上 子问题集合的每个节点，有向弧 线从此节点指向次子问题集合中 的各个节点。由于只有当集合中 所有项都有解时

5、，这个子问题的 集合才能获得解答，所以这些子 问题节点叫做与节点。 5）特殊情况下，当只有一个算符 可应用于问题A，而且这个算符产 生具有一个以上子问题的某个集 合时，由上述规则3）和规则4） 所产生的图可以得到简化。MDEFA ADEF简化西安电子科技大学问题归约法v与或图的搜索：目的在于表明起始节点是有解的。v可解节点终叶节点是可解节点（对应于本原问题）。如果某个非终叶节点含有或后继节点，那么只要当其后 继节点至少有一个是可解的时，此非终叶节点才是可解 的。如果某个非终叶节点含有与后继节点，那么只有当其后 继节点全部为可解时，此非终叶节点才是可解的。西安电子科技大学问题归约法v不可解节点

6、没有后裔的非终叶节点为不可解节点。 如果某个非终叶节点含有或后继节点，那么只有当其全 部后裔为不可解时，此非终叶节点才是不可解的。 如果某个非终叶节点含有与后继节点，那么只要当其后 裔至少有一个为不可解时，此非终叶节点才是不可解的 。 v解树 由可解节点所构成，并且由这些可解节点可推出初始节 点为可解节点的子树称为解树。 解树中一定包含初始节点，它对应于原始问题。西安电子科技大学问题归约法ttttttttt有解节点无解节点终叶节点 与或图例子原始问题有一 个以上的解原始问题 有解西安电子科技大学内容提要第二章：知识表示方法第二章：知识表示方法1.状态空间法2.问题归约法3.谓词逻辑法4.语义网

7、络法5.其他方法西安电子科技大学谓词逻辑法v命题逻辑与谓词逻辑命题逻辑与谓词逻辑是最先用于人工智能的两种逻辑， 对于知识的形式化表示，特别是定理的证明发挥了重要 作用虽然命题逻辑能够把客观世界的各种事实表示为逻辑命 题，但是它具有较大的局限性。命题逻辑只能进行命题 间关系的推理，无法解决与命题结构和成分有关的推理 问题，不适合表示比较复杂的问题。谓词逻辑是在命题逻辑的基础上发展而来的，命题逻辑 可以看作是谓词逻辑的一种特殊形式。西安电子科技大学谓词逻辑法v命题命题是具有真假意义的语句命题代表人们进行思维时的一种判断，若命题的意义为 真，称它的真值为“真”，记作“T”；若命题的意义为假 ，称它的

8、真值为“假”，记作“F”。例如：p“西安是陕西省省会”“10大于6”是真值为“T”的命题p“月亮是方的”“煤炭是白的”是真值为“F”的命题一个命题不能同时即为真又为假，但可以在一定条件下 为真，在另一种条件下为假。例如： p“1+1=10”在二进制情况下为真，十进制情况下为假西安电子科技大学谓词逻辑法v命题没有真假意义的语句，如感叹句、疑问句等，不是命 题。通常用大写英文字母表示一个命题，例如： p P：西安是座古老的城市v命题逻辑的局限性？客观事物的结构及逻辑特征？不同事物间的共同特征？西安电子科技大学谓词逻辑法v命题逻辑的局限性？ 命题这种表示方法无法把它所描述的客观事物的结构及 逻辑特征

9、反映出来，也不能把不同事物间的共同特征表 述出来 例如，用字母P表示“小张是老张的儿子”这一命题， 则无法表述出老张与小张是父子关系 又如，“张三是学生”，“李四是学生”这两个命题， 用命题逻辑表示时，无法把两者的共同特征“都是学生 ”形式的表示出来 可否用 Student（“张三”）， Student（“李四”）表示 上述命题？谓词逻辑西安电子科技大学谓词逻辑法v谓词在谓词逻辑中，命题是用形如P(x1,x2,xn)的谓词来表 述的。一个谓词可分为谓词名与个体两个部分个体： 是命题的主语，表示独立存在的事物或某个抽 象的概念p “x1,x2,xn”是个体，一般用小写字母表示p 个体可以是个体常

10、量、变元或函数谓词名：表示个体的性质、状态或个体之间的关系p “P”是谓词名，一般用大写字母表示p 称P 是一个n元谓词。西安电子科技大学谓词逻辑法v谓词对于命题“张三是学生” ，用谓词可以表示为：Student （“张三”）。其中， Student是谓词名， “张三”是个体 ， Student刻画了“张三”是个学生这一特征。在谓词中，个体可以是常量，也可以是变元，还可以是 一个函数。例如，对于命题“x10”可以表示为more（ x,10），其中x是变元。又如，命题“小张的父亲是老师 ”，可以表示为Teacher（father（Zhang），其中， father（Zhang）是一个函数。当谓词

11、中的变元都用特定的个体取代时，谓词就具有一 个确定的真值“T”或 “F” 。西安电子科技大学谓词逻辑法v谓词 在n元谓词 P(x1,x2,xn)中，若每个个体均为常量、变 元或函数，则称它为一阶谓词。如果某个个体本身又是一个一阶谓词，则称它为二阶谓 词，如此类推。个体变元的取值范围称为个体域。个体域可以是有限的 ，也可以是无限的。例如用I（x）表示“x是整数”，则 个体域为所有整数，是无限的。谓词与函数不同，谓词的真值是”T“或”F“，而函数的 值是个体域中的一个个体，无真值可言。西安电子科技大学谓词逻辑法v谓词演算谓词逻辑语言的语法和语义p基本符号：谓词符号、变量符号、函数符号、常量符号 、

12、括号和逗号p原子公式：原子公式由若干谓词符号和项组成 谓词符号规定定义域内的一个相应关系 常量符号是最简单的项，表示论域内的物体或实体 变量符号也是项，不明确涉及是哪一个实体 函数符号表示论域内的函数，是从论域内的一个实体到另 外一个实体的映射 例如：原子公式 Married father(LI) , mother(LI) 表示“ 李（LI）的父亲和他的母亲结婚”西安电子科技大学谓词逻辑法连词和量词 p连词 合取：符号“ ”， 表示所连结的两个命题之间具有“与 ”的关系。 析取： 符号“ ”，表示所连结的两个命题之间具有“或 ”的关系 蕴涵：符号“ ” ，表示“若则”的语义。PQ读 作“如果P

13、，则Q”其中，P称为条件的前件，Q称为条件 的后件。 非：符号“ ”，表示对其后面的命题的否定 双条件：符号“ ”，表示“当且仅当”的语义。 PQ 读作“P当且仅当Q”。西安电子科技大学谓词逻辑法p量词 全称量词：符号“”，意思是“所有的”、“任一个” x读作“对一切x”,或“对每一x”，或“对任一x” 。 命题(x)P(x)为真，当且仅当对论域中的所有x，都有 P(x)为真 命题(x)P(x)为假，当且仅当至少存在论域中的一个x ，使得P(x)为假 存在量词：符号“”，意思是“至少有”、“存在” x读作“存在一个x”,或“对某些x”，或“至少有一 x”。 命题(x)P(x)为真，当且仅当至少

14、存在论域中的一个x ，使得P(x)为真 命题( x)P(x)为假，当且仅当对论域中的所有x，都有 P(x)为假 西安电子科技大学谓词逻辑法v谓词公式 原子谓词公式：是由谓词符号和若干项组成的谓词演算。 分子谓词公式：可以用连词把原子谓词公式组成复合谓词公式， 并把它叫做分子谓词公式。 合式公式（WFF，Well-formed Formulas）：通常把合式公式叫 做谓词公式，递归定义如下：p(1) 原子谓词公式是合式公式 p(2) 若A为合式公式，则 A也是一个合式公式 p(3) 若A,B是合式公式，则AB，AB，AB，AB也都是合式公 式 p(4) 若A是合式公式，x为A中的自由变元，则 (

15、x)A和( x)A都是合式 公式 p(5) 只有按上述规则(1)至(4)求得的那些公式，才是合式公式。西安电子科技大学谓词逻辑法v谓词公式 用谓词公式表示知识时，需要首先定义谓词，然后再用连接 词把有关的谓词连接起来，形成一个谓词公式表达一个完整 的意义。 例1：设有下列知识 刘欢比他父亲出名。 高扬是计算机系的一名学生，但他不喜欢编程 。 任何整数或者为正或者为负。为了用谓词公式表示上述知识，首先需要定义谓词： FAMOUS (x, y) : x比y出名 COMPUTER ( x ) : x 是计算机系的 LIKE (x, y ) : x 喜欢 y西安电子科技大学谓词逻辑法 I(x)表示“x

16、是整数” P(x)表示“x是正数” N(x)表示“x是负数”此时可用谓词公式把上述知识表示为: 刘欢比他父亲出名: FAMOUS ( liuhuan, father ( liuhuan ) 高扬是计算机系的一名学生，但他不喜欢编程 : COMPUTER(gaoyang)LIKE(gaoyang, programing) 任何整数或者为正或者为负: (x)(I(x) (P(x) N(x)西安电子科技大学谓词逻辑法v谓词公式 例2：用谓词逻辑描述右图中的房子的概念p个体 ：A , Bp谓词 ：SUPPORT( x,y )：表示 x 被 y支撑着 WEDRE ( x )：表示 x 是楔形块 BRICK( y