《人工智能知识表示方法》由会员分享,可在线阅读,更多相关《人工智能知识表示方法(51页珍藏版)》请在金锄头文库上搜索。
1、人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 人工智能与专家系统人工智能与专家系统人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 第2章 知识表示方法2.1 2.1 一阶谓词逻辑表示方法一阶谓词逻辑表示方法2.2 2.2 产生式表示方法产生式表示方法人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 知识表示知识表示是对知识的一种描述,或者说是一组约定,是一种计算机可以接受的用于描述知识的数据结构。 知识外部表示模式知识外部表示模式:是与软件开发与运行的软件工具与平
2、台无关的知识表示的形式化描述。 知识内部表示模式知识内部表示模式:是与开发软件工具与平台有关的知识表示的存储结构。人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 2.1 一阶谓词逻辑表示方法2.1.1 一阶谓词逻辑2.1.2 一阶谓词逻辑表示方法人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 2.1.1 一阶谓词逻辑1 命题命题 命题命题是具有真假意义的语句。命题代表人们进行思维时的一种判断,或者是肯定,或者是否定。人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社
3、2谓词谓词 谓词谓词:谓词可分为谓词名与个体两部分,个体表示某个独立存在的事物或者某个抽象谓词的概念,谓词名用于刻画个体的性质、状态或个体间的关系。 一阶谓词的一般形式为: P(x1, x2, , xn)其中,P是谓词名,x1, x2 , xn 是个体。人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 一阶谓词中的个体可以是常量,也可以是变元,还可以是一个函数。个体常量,个体变元、函数统称为“项项”。 规定规定:谓词名或谓词名的第一个字符用大写字符表示,项中的常量(或常量的第一个字符)用大写字符表示,项中的变元和函数名(或函数名的第一个字符)以及函数的
4、变元都用小写字符表示。人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 3谓词公式谓词公式4 (1)连词)连词 非连词 或连词:用连接两个命题称为析取析取。 与连词:用连接两个命题称为合取合取。 蕴合连词:它表示 “如果P,则Q”,其中P称为前件,Q称为后件。 (2)量词)量词 全称量词( x):表示对个体域 X 中的所有(或任一个)个体 x 。 存在量词( x ):表示在个体域X中存在个体 x 。人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 例:若谓词P(x )表示x是正数,F(x,y)表示x与y是朋友,
5、则:( 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)谓词公式)谓词公式 由下述规则得到的谓词公式称为合式公式合式公式: 单个谓词和单个谓词的否定称为原子谓词公式,原子谓词公式是合式公式
6、。 若A是合式公式,则A也是合式公式。 若A、B都是合式公式,则AB、AB、AB也都是合式公式。 若A是合式公式, x 是任一个体变元,则 ( x )A和( x )A也都是合式公式。 在合式公式中,连词的优先级别依序为: ,人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 4 谓词公式的解释 在命题逻辑中,对命题公式中各个命题的一次真值指派称为命题公式的一个解释解释。一个谓词公式的解释可能有很多个。对于每一个解释,谓词公式都可求出一个真值(T或F)。人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 例例2.12
7、.1 设变元设变元x x和和y y的个体域是的个体域是D=1D=1,22,谓词,谓词P P( x x ,y y)表示)表示x x 大于等于大于等于y y,给出公式,给出公式A=( A=( x x)( )( y y)P()P(x x , ,y y) )在在D D上的解释,指出每一种解释下公式上的解释,指出每一种解释下公式A 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
8、 ,y)的真值为T,即x 对于D中的所有取值,都存在y=1,使P(x ,y)的真值为T,所以在此解释下公式A的真值为T。人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 例2.2 设个体域设个体域D=1,2D=1,2,给出公式,给出公式 R=( R=( x x )(P( )(P(x x )Q( )Q(f f( (x x ),B) ),B)在在D D上的一个解释,指出公式上的一个解释,指出公式R R在此解释下的真值在此解释下的真值。 解:设对个体常量B指派D中的一个元素为B=1,对函数f (x)指派到D的映射为: f (1)=2,f (2)=1 设对谓词
9、指派的真值为: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
10、 (x ),B)的真值为T。所以公式R在此解释下的真值为T。人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 可见:谓词公式的真值是针对某一个解释而言的,它可能在某一个解释下的真值为T,在另一个解释下的真值为F。人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 5 谓词公式的永真性、可满足性、不可满足性 定义2.2: 如果谓词公式P对个体域D上的任何一个解释都取得真值T,则称公式P在域在域D D上是永真的上是永真的。如果P在每个非空个体域上均永真,则称P是永真永真的。 可见:为了判定某个公式永真,必须对每个个体
11、域上的每一个解释逐一判定公式的真值。人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 定义2.3 : 对于谓词公式P,如果至少存在一个解释使得公式P在此解释下的真值为T,则称公式P是可满足可满足的。 定义定义2.42.4 :如果谓词公式P对于个体域D上的任何一个解释都取得真值F,则称公式P在域在域D D上是永假的上是永假的。如果P在每个非空个体域上均永假,则称P是永假永假的。 谓词公式的永假性又称为不可满足性不可满足性。人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 6 谓词公式的等价性 定义2.5: 设P与
12、Q是两个谓词公式,D是它们共同的个体域,若对D上的任何一个解释,P与Q都有相同的真值,则称公式P和Q在在D D上是等价的上是等价的。如果D是任意的个体域,则称P和Q是等价等价的。记为P Q。人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 主要的等价式: (1)交换律 PQ QP PQ QP(2)结合律 (PQ)R P(QR) (PQ)R P(QR)人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 (3)分配律 P(QR) (PQ)(PR) P(QR) (PQ) (PR)(4)狄摩根律 (PQ) PQ (PQ)
13、 PQ人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 (5)双重否定律 P P(6)吸收律 P(PQ) P P(PQ) P(7)补余律 P P T P P F人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 (8)连词化归律 PQ PQ(9)量词转换律 ( x)P ( x ) (P) ( x)P ( x ) (P) (10) 量词分配律 ( x )(PQ) ( x )P( x ) Q ( x )(PQ) ( x )P( x )Q人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水
14、电出版社 7谓词公式的永真蕴含 定义2.6 : 对于谓词公式P和Q,如果PQ永真,则称P P永真蕴含永真蕴含Q Q,且称Q为P的逻辑结论逻辑结论,称P为Q的前提,记为P Q。人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 8 推理规则、定理与证明 推理规则用来由已知的合式公式推导出新的合式公式。导出的合式公式称为定定理理,而所使用的推理规则的序列则构成该定理的一个证明证明。人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 2.1.2 一阶谓词逻辑表示方法 1 一阶谓词逻辑表示方法 用谓词公式表示知识时,应按以
15、下步骤进行: (1)定义谓词,给出每个谓词的确切含义; (2)用连词把有关谓词连接起来表示一个更复杂的含义; (3)对谓词公式中的变元,根据知识表示的需要,把需要约束的变元用相应的量词予以约束。人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 例例2.32.3 用谓词公式表示下列知识:用谓词公式表示下列知识: 王林是计算机系的学生,但他不喜欢编程序。人人爱劳动。人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 解: (1) 定义谓词定义谓词COMPUTERCOMPUTER(x) 表示表示 x 是计算机系的学生是
16、计算机系的学生LIKELIKE(x , ,y y) 表示表示 x 喜欢喜欢y yLOVE(LOVE(x , ,y y) ) 表示表示 x 爱爱y yMANMAN(x) 表示表示 x 是人是人(2)谓词公式知识表示)谓词公式知识表示COMPUTERCOMPUTER(Wang LinWang Lin)LIKE(Wang Lin,Programing)LIKE(Wang Lin,Programing)( ( x)(MAN()(MAN(x)LOVE()LOVE( x,Labour)Labour)人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 例例2.42.4
17、 用谓词公式表示下列知识:用谓词公式表示下列知识: 自然数是大于零的整数。 所有整数不是偶数就是奇数。 偶数除以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 )
18、( x ) (E (x )I (f (x ) 其中,函数f (x )= x /2。人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 例例2.52.5 已知已知F1F1:王(:王(WangWang)先生是小李()先生是小李(LiLi)的老师。)的老师。F2F2:小李与小张(:小李与小张(Zhang Zhang )是同班同学。)是同班同学。F3F3:如果:如果 x x与与y y是同班同学,则是同班同学,则 x x 的老师也的老师也 是是y y 的老师。的老师。 求:小张的老师是谁?求:小张的老师是谁?人工智能与专家系统人工智能与专家系统(第二版)第二版)中
19、国水利水电出版社中国水利水电出版社 解解: (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 2.6 设设A A,B
20、 B,C C三人中有人从不说三人中有人从不说真话,也有人从不说假话,某人向这三人真话,也有人从不说假话,某人向这三人分别提出同一个问题:谁是说谎者?分别提出同一个问题:谁是说谎者?A A答:答:“B B和和C C都是说谎者都是说谎者”;B B答:答:“A A和和C C都是说都是说谎者谎者”;C C答:答:“A A和和B B中至少有一个是说谎中至少有一个是说谎者者”。求谁是老实人,谁是说谎者?。求谁是老实人,谁是说谎者?人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 解:(1) 定义谓词 T(x ) 表示表示 x 说真话说真话。 (2)谓词公式知识表示
21、 如果如果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)人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 2一阶谓词逻辑表示方法的优点3 (1)自然性 (2)精确性 (3)严密性 (4)容易实现人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 3
22、一阶谓词逻辑表示方法的局限性4 (1)不能表示不确定性的知识 (2)组合爆炸 (3)效率低人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 2.2 产生式表示方法产生式表示方法2.2.1 产生式与产生式系统2.2.2 产生式系统的分类及其特点人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 2.2.1 产生式与产生式系统1、产生式的基本形式、产生式的基本形式 产生式基本形式是:PQ 或者 if P then Q 蕴含式与产生式的差别: 蕴含式只能表示精确知识;产生式可以表示精确知识,也可以表示不精确知识。 蕴含
23、式要求匹配是精确的;产生式匹配可以是精确的,也可以是不精确的。人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 2 、产生式系统、产生式系统 产生式系统:产生式系统:把一组产生式放在一起,并让它们互相配合,协同作用,一个产生式生成的结论可以供另一个产生式作为已知事实使用,以求得问题的解决。(1)规则库 用于描述相应领域内知识的产生式集合称为规则库规则库。人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 例例2.72.7 建立一个动物识别系建立一个动物识别系统的规则库,用以识别虎、豹、统的规则库,用以识别虎、豹、
24、斑马、长颈鹿、企鹅、鸵鸟、信斑马、长颈鹿、企鹅、鸵鸟、信天翁等天翁等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 动物是
25、哺乳动物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
26、动物是鸟 and 不会飞 and 有长脖子 and 有长腿 and 有黑白二色 then 动物是鸵鸟R14:if 动物是鸟 and 不会飞 and 会游泳 and 有黑白二色 then 动物是企鹅R15:if 动物是鸟 and 善飞 then 动物是信天翁人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 (2)综合数据库)综合数据库 综合数据库综合数据库又称为全局数据库,或称为事实库、黑板。用于存放问题求解过程中各种当前信息,例如问题的初始事实、原始证据、推理中得到的中间结论以及最终结论。综合数据库的内容随着推理的进行是在不断动态变化的。(3)控制机构
27、)控制机构 控制机构控制机构又称为推理机构或推理机,由一组程序组成,实现对问题的推理求解。人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 2.2.2 产生式系统的分类及其特点1 可交换的产生式系统可交换的产生式系统 如果一个产生式系统对规则的使用次序是可交换的,无论先使用哪一条规则都可达到目的,即规则的使用次序对问题的最终求解是无关紧要的,则称为可交换的产生式系可交换的产生式系统统。人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 例:例:设DB的初始状态是A,B,C,并设RB中有下述规则:R1:if A,
28、B, C then A, B, C, ABR2: if A, B, C then A, B, C, BCR3::if A, B, C then A, B, C, AC 推理终止条件是综合数据库DB中的内容变为:A, B, C, AB, BC, AC 三条规则各被使用一次后就可达到目的,且与规则使用的次序无关。所以由上述RB和DB构成的产生式系统是一个可交换的产生式系统。 人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 在可交换产生式系统中,综合数据库DB中的内容是递增的,即对任意一个规则执行序列R1,R2,Rk都有 由此可见,用可交换产生式系统求解问
29、题时,推理过程不必进行回溯。 人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 2 可分解的产生式系统可分解的产生式系统 如果一个产生式系统的综合数据库DB的当前状态DBi可被分解为若干个独立的部分: 且根据DB的状态确定的推理过程的终止条件也可被分解为对这些独立部分进行推理的终止条件,则称为可分解的产生式系统可分解的产生式系统。人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 例例:设DB的初始内容为DBo=D,B,Z, RB中有如下规则:R1:if C then D, L R2:if C then B, M
30、 R3:if B then M, M R4:if Z then B, B, M 终止条件是生成只包含M的综合数据库,即使综合数据库的内容变为:M, M, , M人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 C, B, ZC B Z B,M M,MB,B,M D,L M, M DBLBBMMMMM, M M, M MMMMMMR1R2R3R4R3R3R3图图2.1 可分解的产生式系统示例可分解的产生式系统示例人工智能与专家系统人工智能与专家系统(第二版)第二版)中国水利水电出版社中国水利水电出版社 3 可恢复的产生式系统可恢复的产生式系统 在问题求解过程中既可以对综合数据库添加新内容、又可删除或修改老内容的产生式系统称为可恢复的产生式系统可恢复的产生式系统。4 产生式表示法的特点产生式表示法的特点(1)自然性(2)模块性(3)有效性(4)清晰性