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

人工智能与专家系统(第二版）中国水利水电出版社人工智能与专家系统人工智能与专家系统(第二版）中国水利水电出版社第2章知识表示方法2.1一阶谓词逻辑表示方法2.2产生式表示方法人工智能与专家系统(第二版）中国水利水电出版社知识表示是对知识的一种描述，或者说是一组约定，是一种计算机可以接受的用于描述知识的数据结构。知识外部表示模式：是与软件开发与运行的软件工具与平台无关的知识表示的形式化描述。知识内部表示模式：是与开发软件工具与平台有关的知识表示的存储结构。人工智能与专家系统(第二版）中国水利水电出版社2.1一阶谓词逻辑表示方法2.1.1一阶谓词逻辑2.1.2一阶谓词逻辑表示方法人工智能与专家系统(第二版）中国水利水电出版社2.1.1一阶谓词逻辑1命题命题是具有真假意义的语句。命题代表人们进行思维时的一种判断，或者是肯定，或者是否定。它取的真值为真或假，记为T或F。人工智能与专家系统(第二版）中国水利水电出版社2谓词在谓词逻辑中，命题是用谓词来表示的。谓词:谓词可分为谓词名与个体两部分，个体表示某个独立存在的事物或者某个抽象谓词的概念，谓词名用于刻画个体的性质、状态或个体间的关系。一阶谓词的一般形式为：P（x1,x2,…,xn）其中，P是谓词名，x1,x2,…,xn是个体。人工智能与专家系统(第二版）中国水利水电出版社个体变元的取值范围称为个体域。在谓词P（x1,x2,…,xn）中，若xi都是个体常量，变元或函数，i=1,2,…,n，则称它为一阶谓词，若某个xi本身又是一个一阶谓词，则称P为二阶谓词。人工智能与专家系统(第二版）中国水利水电出版社一阶谓词中的个体可以是常量，也可以是变元，还可以是一个函数。个体常量，个体变元、函数统称为“项”。如：Teacher(father(Wang))father(Wang)是一个函数，它是谓词Teacher的个体。Less(x,5)代表x5谓词与函数的区别：谓词的真值是真或假而函数是一个个体到另一个个体的映射，无真值。人工智能与专家系统(第二版）中国水利水电出版社规定：谓词名或谓词名的第一个字符用大写字符表示，项中的常量（或常量的第一个字符）用大写字符表示，项中的变元和函数名（或函数名的第一个字符）以及函数的变元都用小写字符表示。人工智能与专家系统(第二版）中国水利水电出版社3谓词公式（1）连词①非连词﹁②或连词∨：用∨连接两个命题称为析取。③与连词∧：用∧连接两个命题称为合取。④蕴合连词→：它表示“如果P，则Q”，其中P称为前件，Q称为后件。（2）量词①全称量词（x）：表示对个体域X中的所有（或任一个）个体x。②存在量词（x）：表示在个体域X中存在个体x。人工智能与专家系统(第二版）中国水利水电出版社例：若谓词P(x)表示x是正数，F(x,y)表示x与y是朋友，则：(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）谓词公式由下述规则得到的谓词公式称为合式公式：①单个谓词和单个谓词的否定称为原子谓词公式，原子谓词公式是合式公式。②若A是合式公式，则﹁A也是合式公式。③若A、B都是合式公式，则A∨B、A∧B、A→B也都是合式公式。④若A是合式公式，x是任一个体变元，则(x)A和(x)A也都是合式公式。在合式公式中，连词的优先级别依序为：﹁，∧，∨，→人工智能与专家系统(第二版）中国水利水电出版社4谓词公式的解释在命题逻辑中，对命题公式中各个命题的一次真值指派称为命题公式的一个解释。一个谓词公式的解释可能有很多个。对于每一个解释，谓词公式都可求出一个真值（T或F）。人工智能与专家系统(第二版）中国水利水电出版社例2.1设变元x和y的个体域是D={1，2}，谓词P（x，y）表示x大于等于y，给出公式A=(x)(y)P(x,y)在D上的解释，指出每一种解释下公式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,y)的真值为T，即x对于D中的所有取值，都存在y=1，使P(x,y)的真值为T，所以在此解释下公式A的真值为T。人工智能与专家系统(第二版）中国水利水电出版社例2.2设个体域D={1,2}，给出公式R=(x)(P(x)→Q(f(x),B))在D上的一个解释，指出公式R在此解释下的真值。解：设对个体常量B指派D中的一个元素为B=1，对函数f(x)指派到D的映射为：f(1)=2，f(2)=1设对谓词指派的真值为：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(x),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∨R)(P∧Q)∧RP∧(Q∧R)人工智能与专家系统(第二版）中国水利水电出版社（3）分配律P∨(Q∧R)(P∨Q)∧(P∨R)P∧(Q∨R)(P∧Q)∨(P∧R)（4）狄·摩根律﹁(P∨Q)﹁P∧﹁Q﹁(P∧Q)﹁P∨﹁Q人工智能与专家系统(第二版）中国水利水电出版社（5）双重否定律﹁﹁PP（6）吸收律P∨(P∧Q)PP∧(P∨Q)P（7）补余律P∨﹁PTP∧﹁PF人工智能与专家系统(第二版）中国水利水电出版社（8）连词化归律P→Q﹁P∨Q（9）量词转换律﹁（x）P(x)(﹁P)﹁（x）P(x)(﹁P)(10)量词分配律(x)(P∧Q)(x)P∧(x)Q(x)(P∨Q)(x)P∨(x)Q人工智能与专家系统(第二版）中国水利水电出版社7谓词公式的永真蕴含定义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喜欢yLOVE(x,y)表示x爱yMAN（x）表示x是人（2）谓词公式知识表示COMPUTER（WangLin）∧﹁LIKE(WangLin,Programing)(x)(MAN(x)→LOVE(x，Labour))人工智能与专家系统(第二版）中国水利水电出版社例2.4用谓词公式表示下列知识：自然数是大于零的整数。所有整数不是偶数就是奇数。偶数除以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))(x)(E(x)→I(f(x)))其中，函数f(x)=x/2。人工智能与专家系统(第二版）中国水利水电出版社例2.5已知F1：王（Wang）先生是小李（Li）的老师。F2：小李与小张（Zhang）是同班同学。F3：如果x与y是同班同学，则x的老师也是y的老师。求：小张的老师是谁？人工智能与专家系统(第二版）中国水利水电出版社解：（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设A，B，C三人中有人从不说真话，也有人从不说假话，某人向这三人分别提出同一个问题：谁是说谎者？A答：“B和C都是说谎者”；B答：“A和C都是说谎者”；C答：“A和B中至少有一个是说谎者”。求谁是老实人，谁是说谎者？人工智能与专家系统(第二版）中国水利水电出版社解：（1）定义谓词T(x)表示x说真话。（2）谓词公式知识表示如果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一阶谓词逻辑表示方法的优点（1）自然性（2）精确性（3）严密性（4）容易实现人工智能与专家系统(第二版）中国水利水电出版社3一阶谓词逻辑表示方法的局限性（1）不能表示不确定性的知识（2）组合爆炸（3）效率低人工智能与专家系统(第二版）中国水利水电出版社2.2产生式表示方法2.2.1产生式与产生式系统2.2.2产生式系统的分类及其特点人工智能与专家系统(第二版）中国水利水电出版社2.2.1产生式与产生式系统1、产生式的基本形式产生式基本形式是：P→