第二章 知识表示_第1页
第二章 知识表示_第2页
第二章 知识表示_第3页
第二章 知识表示_第4页
第二章 知识表示_第5页
已阅读5页,还剩127页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、n什么是人工智能?n从表现形式的角度机器智能,能够在各类环境中,自主地或交互地执行各种拟人任务(Anthropomorphic Anthropomorphic taskstasks)的机器。n从学科发展的角度人工智能,是计算机科学中涉及研究、设计和应用智能机器的一个分支,其近期主要目标是用机器来模仿和执行人脑的某些智能功能,并开发相关理论和技术。n从实用主义的角度智能计算,研究智能信息处理技术,以使机器具有与人类智能相类似的行为,如:判断、推理、证明、识别、感知、理解、通信、设计、思考、规划、学习和问题求解等思维活动 知识表示方法知识表示方法n状态空间法状态空间法n问题归约法问题归约法n谓词逻

2、辑法谓词逻辑法. .n语义网络语义网络n另外还有框架表示以及剧本表示另外还有框架表示以及剧本表示, ,过程表示过程表示, ,这这里不在一一详述里不在一一详述. .n在表示和求解比较复杂的问题时在表示和求解比较复杂的问题时, ,采用单一的表采用单一的表示方法是不够的示方法是不够的, ,往往采用多种方法的混合表示往往采用多种方法的混合表示. .目前这仍是人工智能专家感兴趣的研究方向目前这仍是人工智能专家感兴趣的研究方向. .T0,1nq q ,.q Q 初始棋局初始棋局目标棋局目标棋局初始状态初始状态目标状态目标状态W 猴子的水平位置;猴子的水平位置;x 当猴子在箱子顶上时取当猴子在箱子顶上时取1

3、;否则取;否则取0;Y 箱子的水平位置;箱子的水平位置;z 当猴子摘到香蕉时取当猴子摘到香蕉时取1;否则取;否则取0。n要把问题的一切状态都表示出来,要定义一组算符。要把问题的一切状态都表示出来,要定义一组算符。n问题的求解过程是一个不断把算符作用于状态的过程。问题的求解过程是一个不断把算符作用于状态的过程。解解就是从初始状态到目标状态所采用算符的序列。使就是从初始状态到目标状态所采用算符的序列。使用算符最少的解称为用算符最少的解称为最优解最优解。n对任一个状态,可使用的算符可能不止一个。对任一个状态,可使用的算符可能不止一个。 已知问题的描述,通过一系列变换把此问题变为一个已知问题的描述,通

4、过一系列变换把此问题变为一个子问题集合;这些子问题的解可以直接得到,从而解子问题集合;这些子问题的解可以直接得到,从而解决了初始问题。决了初始问题。n问题归约法的组成部分问题归约法的组成部分(1 1)一个初始问题描述;)一个初始问题描述;(2 2)一套把问题变换为子问题的操作符;)一套把问题变换为子问题的操作符;(3 3)一套本原问题描述。)一套本原问题描述。( (本原问题本原问题: :不能再分解或不能再分解或变换且直接可解的子问题变换且直接可解的子问题) )n问题归约的本质问题归约的本质 从目标(要解决的问题)出发逆向推理,建立从目标(要解决的问题)出发逆向推理,建立子问题以及子问题的子问题

5、,直到最后把初始问题子问题以及子问题的子问题,直到最后把初始问题归约为一个本原问题集合。归约为一个本原问题集合。问题归约示例问题归约示例梵塔难题梵塔难题(a) 初始状态初始状态(b) 目标状态目标状态n复杂问题的简化复杂问题的简化n分解分解把一个复杂问题分解为若干个把一个复杂问题分解为若干个较为简单的子问题,形成较为简单的子问题,形成“与与”树。树。n等价变换等价变换利用同构或同态的等价变换,利用同构或同态的等价变换,把原问题变换为若干个较为容把原问题变换为若干个较为容易求解的新问题,形成易求解的新问题,形成“或或”树。树。n终叶节点是可解节点终叶节点是可解节点(对应于本原问题对应于本原问题)

6、。n如果某个非终叶节点含有或后继节点,那么只要如果某个非终叶节点含有或后继节点,那么只要当其后继节点至少有一个是可解的时,此非终叶当其后继节点至少有一个是可解的时,此非终叶节点才是可解的。节点才是可解的。n如果某个非终叶节点含有与后继节点,那么只有如果某个非终叶节点含有与后继节点,那么只有当其后继节点全部为可解时,此非终叶节点才是当其后继节点全部为可解时,此非终叶节点才是可解的。可解的。n没有后裔的非终叶节点为不可解节点。没有后裔的非终叶节点为不可解节点。 n如果某个非终叶节点含有或后继节点,那么只有如果某个非终叶节点含有或后继节点,那么只有当其全部后裔为不可解时,此非终叶节点才是不当其全部后

7、裔为不可解时,此非终叶节点才是不可解的。可解的。 n如果某个非终叶节点含有与后继节点,那么只要如果某个非终叶节点含有与后继节点,那么只要当其后裔至少有一个为不可解时,此非终叶节点当其后裔至少有一个为不可解时,此非终叶节点才是不可解的。才是不可解的。n由可解节点所构成,并且由这些可解节点可推出初由可解节点所构成,并且由这些可解节点可推出初始节点为可解节点的子树称为解树。始节点为可解节点的子树称为解树。n解树中一定包含初始节点,它对应于原始问题解树中一定包含初始节点,它对应于原始问题。 命题逻辑命题逻辑 一个命题是一个或真或假不能两者都是的断一个命题是一个或真或假不能两者都是的断言。断言是指一陈述

8、语句。简单地说,命题是指言。断言是指一陈述语句。简单地说,命题是指一句有真假意义的陈述句。命题为真,记为一句有真假意义的陈述句。命题为真,记为 T 。 命题为假,记为命题为假,记为 F。 一个命题一个命题P如果是真值未指定任意命题,称如果是真值未指定任意命题,称P为命题变元。为命题变元。命题变元用命题变元用 P, Q, R表示;如果表示;如果P是一个真值已经指定的命题,称为命题常元。命是一个真值已经指定的命题,称为命题常元。命题常元只有题常元只有 T 和和 F。 复合命题复合命题:单个命题通过联结词联结构成的新:单个命题通过联结词联结构成的新命题。命题。常用的常用的5种联结词:种联结词:复合命

9、题与原命题的真值关系复合命题与原命题的真值关系P Q P P Q P Q PQ PQF F T F F T TT F F T F F FF T T T F T FT T F T T T T否定否定 合取合取 析取析取 蕴涵蕴涵 等值等值 命题公式及其解释命题公式及其解释原子公式原子公式:单个命题变元、单个命题常元称为原子:单个命题变元、单个命题常元称为原子公式。公式。命题公式命题公式:由如下规则生成的公式称为命题公式:由如下规则生成的公式称为命题公式:1. 单个原子公式是命题公式。单个原子公式是命题公式。2. 若若A ,B是命题公式,则是命题公式,则A , AB , AB , A B , A

10、B是公式。是公式。3. 所有命题公式都是有限次应用所有命题公式都是有限次应用1、2得到的符号串。得到的符号串。例如:公式例如:公式G= (A B) C 的一个解释是:的一个解释是:I1(G) = A/T, B/F, C/T 在解释在解释I1(G)下下G为真。为真。永真公式与永假公式永真公式与永假公式:如果公式在它所有的解释:如果公式在它所有的解释I下,其值都为下,其值都为T,则称公式,则称公式G为恒真的;如果其值为恒真的;如果其值都为都为F,则称公式,则称公式G为恒假的(不可满足的)。为恒假的(不可满足的)。命题公式的命题公式的解释解释:给命题公式中的每一个命题变元:给命题公式中的每一个命题变

11、元指定一个真假值,这一组真假值,就是命题公式的指定一个真假值,这一组真假值,就是命题公式的一个解释。用一个解释。用I表示。表示。注意:注意:关于五个联结词的约定关于五个联结词的约定:* 结合力的强弱顺序:结合力的强弱顺序: , , , , * 联结词相同时,从左至右运算。联结词相同时,从左至右运算。解释的个数解释的个数:如果一个公式如果一个公式G中有中有n个不同的原子公式(或简个不同的原子公式(或简称原子),则称原子),则G有有2n个不同的解释,于是个不同的解释,于是G在在2n个解个解释下有释下有2n个真值。如果将这些真值和它们的解释列成个真值。如果将这些真值和它们的解释列成表,就是表,就是G

12、的真值表。的真值表。等价命题公式等价命题公式 如果两个命题公式所含原子公式相同,且在任一解释如果两个命题公式所含原子公式相同,且在任一解释下,两个命题公式的值相同,则称这两个命题公式为等价下,两个命题公式的值相同,则称这两个命题公式为等价命题公式或等价公式。常用的等价公式有:命题公式或等价公式。常用的等价公式有:1. (P Q)= (P Q) (Q P)P Q P Q Q P (P Q) (Q P) P QT T T T T TT F F T F FF T T F F FF F T T T T2.(P Q)=(P Q)3. (P)= P4.交换律:P Q=Q P P Q=Q P5.结合律:P

13、(Q R)=(P Q) R P (Q R)=(P Q) R6.分配律:P (Q R)=(P Q) (P R) P (Q R)=(P Q) (P R)7.泛界律:P F=P , P T=P P F=F ,P T=T 8.互余律:P P=T,P P=F9.德 摩根定律:(P Q)=P Q (P Q)=P Q证明两个公式等价,可用真值表,也可用基本公式。证明两个公式等价,可用真值表,也可用基本公式。例如例如 要证明公式要证明公式 P Q=Q P证 P Q = P Q = P ( Q )=(Q) P=Q P若要证明公式P P Q=P证 P P Q = P ( P Q) = P (Q Q) ( P Q)

14、= (P Q) (P Q) ( P Q)=( P Q) ( P Q) = P (Q Q)=P永真蕴涵式永真蕴涵式 若命题公式若命题公式G H是恒真的,称其为永真蕴涵式。是恒真的,称其为永真蕴涵式。记为记为GH,读做,读做“G蕴涵蕴涵H”,也称,也称“G是是H的逻辑结的逻辑结果果”。常用的永真蕴涵式:1. P P Q 证P P Q = P (P Q) = P P Q = T Q = T2. P Q P证P Q P =(P Q) P= P Q P=T Q= T3. P (P Q) Q4.( P Q) Q P5. P (P Q) Q6.(P Q) (Q R) (P R)7.( P Q) ( (Q R

15、) ( P R)8.(P Q) ( R S) (P R Q S)9.( P Q) ( Q R) ( P R)谓词与量词谓词与量词在命题逻辑中有一个三段论法:在命题逻辑中有一个三段论法:P:“所有的人都会犯错误所有的人都会犯错误”Q:“张三是人张三是人”R:“张三会犯错误张三会犯错误” R应该是应该是P和和Q的逻辑结论。但在命题逻辑中无法准确的逻辑结论。但在命题逻辑中无法准确表达这三个命题的逻辑关系。表达这三个命题的逻辑关系。因为因为( P Q ) R 不是恒真的。如:不是恒真的。如:解解释释: I=P/T,Q/T,R/F 则公式为假值则公式为假值F. 就是说解释就是说解释I 弄假了此公式。弄假

16、了此公式。为准确表达此类公式,必须引进谓词和量词的概念。为准确表达此类公式,必须引进谓词和量词的概念。谓词谓词先看几个命题:先看几个命题:1. 3是质数是质数2. 王二生于武汉市王二生于武汉市3. 7=2 3 x是质数是质数x生于武汉市生于武汉市x=y zF(x)G(x,y)H(x,y,z)称称“3”、“王二王二”、“武汉市武汉市”、“7”、“2”、“3”为个为个体体;代表个体的变元称为个体变元;代表个体的变元称为个体变元;刻画个体性质或个体之间关系的词叫刻画个体性质或个体之间关系的词叫谓词谓词。“是质数是质数”、“生于生于”、“=. .”都是谓词。都是谓词。量词量词量词分为全称量词和存在量词

17、。量词分为全称量词和存在量词。符号符号“ ”表示全称量词。符号表示全称量词。符号“ ”表示存在量词。表示存在量词。 x读作读作“对一切对一切x”,或或“对每一对每一x”,或,或“对任对任一一x”。x是是 所作用的个体变元。所作用的个体变元。 x读作读作“存在一个存在一个x”,或或“对某些对某些x”,或,或“至少有一至少有一x”。x是是 所作用的个体变元。所作用的个体变元。再看前面的三段论法:再看前面的三段论法:P:“所有的人都会犯错误所有的人都会犯错误”Q:“张三是人张三是人”R:“张三会犯错误张三会犯错误” x(M(x) R(x)M(“张三张三”)R(“张三张三”)在谓词前加上在谓词前加上

18、x,叫做变元被全称量化;叫做变元被全称量化;在谓词前加上在谓词前加上 x,叫做变元被存在量化。叫做变元被存在量化。量化的目的是约束变元。量化的目的是约束变元。n谓词演算谓词演算项项谓词符号常量符号 函数符号 谓词公式谓词公式 ( x)(I(x) (P(x)N(x)BA例例2 用谓词逻辑描述右图中的房子的概念。用谓词逻辑描述右图中的房子的概念。 个体个体 :A , B 谓词谓词 :SUPPORT( x,y ) 表示表示 x 被被 y支撑着支撑着 WEDRE ( x ) 表示表示 x 是楔形块是楔形块 BRICK( y ) 表示表示 y 是长方块是长方块 2022-4-19置换与合一置换与合一张宁张宁学生学生Is-a手手人体人体A-part-of 张宁张宁英语英语18160havehavecan学校学校公园公园风景美丽风景美丽Similar to fetch书书桌子桌子Loca

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论