人工智能与专家系统 第2章 知识表示方法.ppt

,人工智能与专家系统,第2章知识表示方法,2.1一阶谓词逻辑表示方法,2.2产生式表示方法,,知识表示是对知识的一种描述，或者说是一组约定，是一种计算机可以接受的用于描述知识的数据结构。知识外部表示模式是与软件开发与运行的软件工具与平台无关的知识表示的形式化描述。知识内部表示模式是与开发软件工具与平台有关的知识表示的存储结构。,2.1一阶谓词逻辑表示方法,2.1.1一阶谓词逻辑2.1.2一阶谓词逻辑表示方法,2.1.1一阶谓词逻辑,1命题命题是具有真假意义的语句。命题代表人们进行思维时的一种判断，或者是肯定，或者是否定。它取的真值为真或假，记为T或F。,,谓词在谓词逻辑中，命题是用谓词来表示的。谓词谓词可分为谓词名与个体两部分，个体表示某个独立存在的事物或者某个抽象谓词的概念，谓词名用于刻画个体的性质、状态或个体间的关系。一阶谓词的一般形式为P（x1,x2,,xn）其中，P是谓词名，x1,x2,,xn是个体。,,个体变元的取值范围称为个体域。在谓词P（x1,x2,,xn）中，若xi都是个体常量，变元或函数，i1,2,,n，则称它为一阶谓词，若某个xi本身又是一个一阶谓词，则称P为二阶谓词。,,一阶谓词中的个体可以是常量，也可以是变元，还可以是一个函数。个体常量，个体变元、函数统称为“项”。如TeacherfatherWangfatherWang是一个函数，它是谓词Teacher的个体。Lessx,5代表x5谓词与函数的区别谓词的真值是真或假而函数是一个个体到另一个个体的映射，无真值。,,规定谓词名或谓词名的第一个字符用大写字符表示，项中的常量（或常量的第一个字符）用大写字符表示，项中的变元和函数名（或函数名的第一个字符）以及函数的变元都用小写字符表示。,,谓词公式（1）连词①非连词﹁②或连词∨用∨连接两个命题称为析取。③与连词∧用∧连接两个命题称为合取。④蕴合连词→它表示“如果P，则Q”，其中P称为前件，Q称为后件。（2）量词①全称量词（x）表示对个体域X中的所有（或任一个）个体x。②存在量词（x）表示在个体域X中存在个体x。,,,,,,,,,,,,,,,,,,,,,,,例若谓词Px表示x是正数，Fx,y表示x与y是朋友，则xPx表示个体域X中的所有个体x都是正数。xyFx,y表示对于个体域X中的任何个体x，在个体域Y中都存在个体y，x与y是朋友。xyFx,y表示在个体域X中存在个体x，他与个体域Y中的任何个体y都是朋友。xyFx,y表示在个体域X中存在个体x和在个体域Y中存在个体y，x与y是朋友。,,,,,（3）谓词公式由下述规则得到的谓词公式称为合式公式①单个谓词和单个谓词的否定称为原子谓词公式，原子谓词公式是合式公式。②若A是合式公式，则﹁A也是合式公式。③若A、B都是合式公式，则A∨B、A∧B、A→B也都是合式公式。④若A是合式公式，x是任一个体变元，则xA和xA也都是合式公式。在合式公式中，连词的优先级别依序为﹁，∧，∨，→,,4谓词公式的解释在命题逻辑中，对命题公式中各个命题的一次真值指派称为命题公式的一个解释。一个谓词公式的解释可能有很多个。对于每一个解释，谓词公式都可求出一个真值（T或F）。,,例2.1设变元x和y的个体域是D{1，2}，谓词P（x，y）表示x大于等于y，给出公式AxyPx,y在D上的解释，指出每一种解释下公式A的真值。,解设对谓词P（x,y）在个体域D上的真值指派为P1,1T，P1,2F，P2,1T，P2,2T这就是公式A在D上的一个解释。在此解释下，因为x1时有y1使Px,y的真值为T，x2时也有y1使Px,y的真值为T，即x对于D中的所有取值，都存在y1，使Px,y的真值为T，所以在此解释下公式A的真值为T。,,例2.2设个体域D{1,2}，给出公式RxPx→Qfx,B在D上的一个解释，指出公式R在此解释下的真值。,解设对个体常量B指派D中的一个元素为B1，对函数fx指派到D的映射为f12，f21设对谓词指派的真值为P1F，P2T，Q1,1T，Q2,1F由于已对个体常量B指派B1，所以Q1,2与Q2,2不可能出现，故没有给它们指派真值。,上述指派就是对公式R的一个解释。在此解释下，由于当x1时，有P1F，Qf1,1Q2,1F所以P1→Qf1,1的真值为T。当x2时，有P2T,Qf2,1Q1,1T所以P2→Qf2,1的真值也为T。即对个体域D中的所有x都有Px→Qfx,B的真值为T。所以公式R在此解释下的真值为T。,可见谓词公式的真值是针对某一个解释而言的，它可能在某一个解释下的真值为T，在另一个解释下的真值为F。,,5谓词公式的永真性、可满足性、不可满足性定义2.2如果谓词公式P对个体域D上的任何一个解释都取得真值T，则称公式P在域D上是永真的。如果P在每个非空个体域上均永真，则称P是永真的。可见为了判定某个公式永真，必须对每个个体域上的每一个解释逐一判定公式的真值。,定义2.3对于谓词公式P，如果至少存在一个解释使得公式P在此解释下的真值为T，则称公式P是可满足的。定义2.4如果谓词公式P对于个体域D上的任何一个解释都取得真值F，则称公式P在域D上是永假的。如果P在每个非空个体域上均永假，则称P是永假的。谓词公式的永假性又称为不可满足性。,,6谓词公式的等价性定义2.5设P与Q是两个谓词公式，D是它们共同的个体域，若对D上的任何一个解释，P与Q都有相同的真值，则称公式P和Q在D上是等价的。如果D是任意的个体域，则称P和Q是等价的。记为PQ。,,,,主要的等价式（1）交换律P∨QQ∨PP∧QQ∧P（2）结合律P∨Q∨RP∨Q∨RP∧Q∧RP∧Q∧R,,（3）分配律P∨Q∧RP∨Q∧P∨RP∧Q∨RP∧Q∨P∧R（4）狄摩根律﹁P∨Q﹁P∧﹁Q﹁P∧Q﹁P∨﹁Q,,（5）双重否定律﹁﹁PP（6）吸收律P∨P∧QPP∧P∨QP（7）补余律P∨﹁PTP∧﹁PF,,（8）连词化归律P→Q﹁P∨Q（9）量词转换律﹁（x）Px﹁P﹁（x）Px﹁P10量词分配律xP∧QxP∧xQxP∨QxP∨xQ,,谓词公式的永真蕴含定义2.6对于谓词公式P和Q，如果P→Q永真，则称P永真蕴含Q，且称Q为P的逻辑结论，称P为Q的前提，记为PQ。,,,8推理规则、定理与证明推理规则用来由已知的合式公式推导出新的合式公式。导出的合式公式称为定理，而所使用的推理规则的序列则构成该定理的一个证明。,2.1.2一阶谓词逻辑表示方法,1一阶谓词逻辑表示方法用谓词公式表示知识时，应按以下步骤进行1定义谓词，给出每个谓词的确切含义；2用连词把有关谓词连接起来表示一个更复杂的含义；3对谓词公式中的变元，根据知识表示的需要，把需要约束的变元用相应的量词予以约束。,,例2.3用谓词公式表示下列知识王林是计算机系的学生，但他不喜欢编程序。人人爱劳动。,,解（1）定义谓词COMPUTER（x）表示x是计算机系的学生LIKE（x,y）表示x喜欢yLOVEx,y表示x爱yMAN（x）表示x是人（2）谓词公式知识表示COMPUTER（WangLin）∧﹁LIKEWangLin,ProgramingxMANx→LOVEx，Labour,,例2.4用谓词公式表示下列知识自然数是大于零的整数。所有整数不是偶数就是奇数。偶数除以2是整数。,解（1）定义谓词Nx表示x是自然数Ix表示x是整数Ex表示x是偶数Ox表示x是奇数GZx表示x大于零,,（2）谓词公式知识表示xNx→GZx∧IxxIx→Ex∨OxxEx→Ifx其中，函数fxx/2。,例2.5已知F1王（Wang）先生是小李（Li）的老师。F2小李与小张（Zhang）是同班同学。F3如果x与y是同班同学，则x的老师也是y的老师。求小张的老师是谁,解（1）定义谓词Tx,yx是y的老师。Cx,yx与y是同班同学。,,（2）谓词公式知识表示（已知前提及待求解问题）F1TWang,LiF2CLi,ZhangF3xyzCx,y∧Tz,x→Tz,yGxTx,Zhang,例2.6设A，B，C三人中有人从不说真话，也有人从不说假话，某人向这三人分别提出同一个问题谁是说谎者A答“B和C都是说谎者”；B答“A和C都是说谎者”；C答“A和B中至少有一个是说谎者”。求谁是老实人，谁是说谎者,解（1）定义谓词Tx表示x说真话。（2）谓词公式知识表示如果A说的是真话，则有TA→﹁TB∧﹁TC如果A说的是假话，则有﹁TA→TB∨TC对B和C说的话作相同的处理，可得TB→﹁TA∧﹁TC﹁TB→TA∨TC﹁TC→TA∧TBTC→﹁TA∨﹁TB,,一阶谓词逻辑表示方法的优点（1）自然性（2）精确性（3）严密性（4）容易实现,,一阶谓词逻辑表示方法的局限性（1）不能表示不确定性的知识（2）组合爆炸（3）效率低,2.2产生式表示方法,2.2.1产生式与产生式系统2.2.2产生式系统的分类及其特点,2.2.1产生式与产生式系统,1、产生式的基本形式产生式基本形式是P→Q或者ifPthenQ蕴含式与产生式的差别①蕴含式只能表示精确知识；产生式可以表示精确知识，也可以表示不精确知识。②蕴含式要求匹配是精确的；产生式匹配可以是精确的，也可以是不精确的。,,2、产生式系统产生式系统把一组产生式放在一起，并让它们互相配合，协同作用，一个产生式生成的结论可以供另一个产生式作为已知事实使用，以求得问题的解决。（1）规则库用于描述相应领域内知识的产生式集合称为规则库。建立规则库时应该注意以下问题1）有效地表达领域知识2）对知识进行合理的组织与管理,例2.7建立一个动物识别系统的规则库，用以识别虎、豹、斑马、长颈鹿、企鹅、鸵鸟、信天翁等7种动物。,解为了识别这些动物，可以根据动物识别的特征，建立包含下述规则的规则库R1if动物有毛发then动物是哺乳动物R2if动物有奶then动物是哺乳动物R3if动物有羽毛then动物是鸟R4if动物会飞and会生蛋then动物是鸟R5if动物吃肉then动物是食肉动物R6if动物有犀利牙齿and有爪and眼向前方then动物是食肉动物R7if动物是哺乳动物and有蹄then动物是有蹄类动物,R8if动物是哺乳动物and反刍then动物是有蹄类动物R9if动物是哺乳动物and是食肉动物and有黄褐色and有暗斑点then动物是豹R10if动物是哺乳动物and是食肉动物and有黄褐色and有黑色条纹then动物是虎R11if动物是有蹄类动物and有长脖子and有长腿and有暗斑点then动物是长颈鹿R12if动物是有蹄类动物and有黑色条纹then动物是斑马R13if动物是鸟and不会飞and有长脖子and有长腿and有黑白二色then动物是鸵鸟R14if动物是鸟and不会飞and会游泳and有黑白二色then动物是企鹅R15if动物是鸟and善飞then动物是信天翁,（2）综合数据库综合数据库又称为全局数据库，或称为事实库、黑板。用于存放问题求解过程中各种当前信息，例如问题的初始事实、原始证据、推理中得到的中间结论以及最终结论。综合数据库的内容随着推理的进行是在不断动态变化的。（3）控制机构控制机构又称为推理机构或推理机，由一组程序组成，实现对问题的推理求解。,推理机主要功能为1）按某种策略从规则库中选择规则与综合数据库中的已知事实进行匹配。匹配成功的规则称为可用规则，不成功则相应的规则不可用于当前的推理。2）若匹配成功的可用规则有多条，此时推理机必须执行某种冲突消解策略，从中选择一条可用规则来执行。3）在执行某一条规则时，若该规则的后件是一个或多个结论，则把这些结论添加到综合数据库中；若规则的后件是一个或多个操作，则依次执行这些操作。4）对于不确定知识，在执行每一条规则时还要按一定的算法来计算结论的不确定性。5）随时检查结束推理机运行的条件，在满足结束条件时停止推理机的运行。,2.2.2产生式系统的分类及其特点,1可交换的产生式系统如果一个产生式系统对规则的使用次序是可交换的，无论先使用哪一条规则都可达到目的，即规则的使用次序对问题的最终求解是无关紧要的，则称为可交换的产生式系统。,例设DB的初始状态是{A,B,C}，并设RB中有下述规则R1if{A,B,C}then{A,B,C,AB}R2if{A,B,C}then{A,B,C,BC}R3if{A,B,C}then{A,B,C,AC}推理终止条件是综合数据库DB中的内容变为{A,B,C,AB,BC,AC}三条规则各被使用一次后就可达到目的，且与规则使用的次序无关。所以由上述RB和DB构成的产生式系统是一个可交换的产生式系统。,,在可交换产生式系统中，综合数据库DB中的内容是递增的，即对任意一个规则执行序列R1,R2,,Rk都有由此可见，用可交换产生式系统求解问题时，推理过程不必进行回溯。回溯是指当执行一条规则使DB的状态由DBi变成了DBi1时，如果发现由DBi1不可能得到问题的解，则立刻撤销由刚才执行规则所产生的结果，使DB恢复到先前的状态DBi，然后选用别的规则继续求解。,,,2可分解的产生式系统如果一个产生式系统的综合数据库DB的当前状态DBi可被分解为若干个独立的部分且根据DB的状态确定的推理过程的终止条件也可被分解为对这些独立部分进行推理的终止条件，则称为可分解的产生式系统。,,例设DB的初始内容为DBo{D,B,Z}，RB中有如下规则R1ifCthen{D,L}R2ifCthen{B,M}R3ifBthen{M,M}R4ifZthen{B,B,M}终止条件是生成只包含M的综合数据库，即使综合数据库的内容变为{M,M,,M},图2.1可分解的产生式系统示例,,用圆弧连接起来的子节点是“与”关系，不用圆弧连接的子节点是“或”关系。用图表示可分解产生式系统求解问题的过程时，得到的是一棵与/或树。,3可恢复的产生式系统在问题求解过程中既可以对综合数据库添加新内容、又可删除或修改老内容的产生式系统称为可恢复的产生式系统。4产生式表示法的特点（1）自然性（2）模块性（3）有效性（4）清晰性,