第2章_知识表示

ArtificialIntelligencePrinciplesandApplications第2章知识表示教材：王万良《人工智能及其应用》（第2版）高等教育出版社，2008.62第2章知识表示2.1知识与知识表示的概念2.2一阶谓词逻辑表示法2.3产生式表示法2.4框架表示法2.5语义网络表示法3第2章知识表示2.1知识与知识表示的概念2.2一阶谓词逻辑表示法2.3产生式表示法2.4框架表示法2.5语义网络表示法42.1.1知识的概念知识：在长期的生活及社会实践中、在科学研究及实验中积累起来的对客观世界的认识与经验。知识：把有关信息关联在一起所形成的信息结构。知识反映了客观世界中事物之间的关系，不同事物或者相同事物间的不同关系形成了不同的知识。信息关联形式：“如果……，则……”如果大雁向南飞，则冬天就要来临了。——规则——事实例如：“雪是白色的”。“如果头痛且流涕，则有可能患了感冒”。52.1.2知识的特性1.相对正确性任何知识都是在一定的条件及环境下产生的，在这种条件及环境下才是正确的。1+1=2（十进制）1+1=10(二进制）2.不确定性①随机性引起的不确定性②模糊性引起的不确定性③经验引起的不确定性④不完全性引起的不确定性知识状态：“真”“假”“真”与“假”之间的中间状态“如果头痛且流涕，则有可能患了感冒”小李很高62.1.2知识的特性3.可表示性与可利用性知识的可表示性:知识可以用适当形式表示出来，如用语言、文字、图形、神经网络等。知识的可利用性:知识可以被利用。72.1.3知识的分类事实性知识：有关概念、事实、事物的属性及状态等。过程性知识：有关系统状态变化、问题求解过程的操作、演算和行动的知识。控制性知识（深层知识或元知识）：关于如何运用已有的知识进行问题求解的知识。糖是甜的。西安是一个古老的城市。一年有春、夏、秋、冬四个季节。1.按知识的作用范围2.按知识的作用及表示常识性知识：通用性知识。领域性知识：专业性的知识。1个字节由8个“位”构成。一个扇区有512个“字节”的数据。82.1.3知识的分类例如：从北京到上海是乘飞机还是火车的问题表示如下：事实性知识：北京、上海、飞机、时间、费用。过程性知识：乘飞机、坐火车。控制性知识：乘坐飞机较快、较贵；坐火车较慢、较便宜。2.按知识的作用及表示92.1.3知识的分类确定性知识：可指出其真值为“真”或“假”的知识，是精确性的知识。不确定性知识：具有不精确、不完全及模糊性等特性的知识。3.按知识的结构及表现形式4.按知识的确定性逻辑性知识：反映人类逻辑思维过程的知识。形象性知识：通过事物的形象建立起来的知识。例：什么是树?102.1.4知识的表示知识表示（knowledgerepresentation）：将人类知识形式化或者模型化。知识表示是对知识的一种描述，或者说是一组约定，一种计算机可以接受的用于描述知识的数据结构。选择知识表示方法的原则：（1）充分表示领域知识。（2）有利于对知识的利用。（3）便于对知识的组织、维护与管理。（4）便于理解与实现。11第2章知识表示2.1知识与知识表示的概念2.2一阶谓词逻辑表示法2.3产生式表示法2.4框架表示法2.5语义网络表示法122.2一阶谓词逻辑表示法132.2一阶谓词逻辑表示法2.2.1命题2.2.2谓词2.2.3谓词公式2.2.4谓词公式的性质2.2.5一阶谓词逻辑知识表示方法2.2.6一阶谓词逻辑表示法的特点14命题逻辑：研究命题及命题之间关系的符号逻辑系统。命题逻辑表示法：无法把它所描述的事物的结构及逻辑特征反映出来，也不能把不同事物间的共同特征表述出来。2.2.1命题命题（proposition）：一个非真即假的陈述句。若命题的意义为真，称它的真值为真，记为T。若命题的意义为假，称它的真值为假，记为F。一个命题可在一种条件下为真，在另一种条件下为假。例如：35例如：太阳从西边升起例:1＋1＝10P：老李是小李的父亲P：北京是中华人民共和国的首都P：李白是诗人Q：杜甫也是诗人152.2.2谓词谓词的一般形式：P(x1,x2,…,xn)个体x1,x2,…,xn：某个独立存在的事物或者某个抽象的概念；谓词名P：刻画个体的性质、状态或个体间的关系。“老张是一个教师”：一元谓词Teacher(Zhang)“53”：二元谓词Greater(5,3)“Smith作为一个工程师为IBM工作”：三元谓词Works(Smith,IBM,engineer)（1）个体是常量：一个或者一组指定的个体。162.2.2谓词（2）个体是变元（变量）：没有指定的一个或者一组个体。“小李的父亲是教师”：Teacher(father(Li))（3）个体是函数：一个个体到另一个个体的映射。“x5”：Less(x,5)（4）个体是谓词“Smith作为一个工程师为IBM工作”：二阶谓词Works(engineer(Smith),IBM)172.2.3谓词公式1.连接词（连词）（1）﹁：“否定”（negation）或“非”。（2）∨：“析取”（disjunction）——或。（3）∧：“合取”（conjunction）——与。“机器人不在2号房间”：﹁Inroom(robot,r2)“李明打篮球或踢足球”：Plays(Liming,basketball)∨Plays(Liming,football)“我喜欢音乐和绘画”：Like(I,music)∧Like(I,painting)182.2.3谓词公式1.连接词（连词）（4）→：“蕴含”(implication)或“条件”(condition)。“如果刘华跑得最快，那么他取得冠军。”：RUNS(Liuhua，faster)→WINS(Liuhua，champion)（5）：“等价”（equivalence）或“双条件”（bicondition）。PQ:“P当且仅当Q”。192.2.3谓词公式1.连接词（连词）谓词逻辑真值表202.2.3谓词公式2.量词（quantifier）（1）全称量词（universalquantifier）（x）：“对个体域中的所有（或任一个）个体x”。“所有的机器人都是灰色的”：(x)[ROBOT(x)→COLOR(x，GRAY)]（2）存在量词（existentialquantifier）（x）：“在个体域中存在个体x”。“1号房间有个物体”：（x）INROOM（x，r1）212.2.3谓词公式全称量词和存在量词举例：(x)(y)F(x,y)表示对于个体域中的任何个体x都存在个体y，x与y是朋友。(x)(y)F(x,y)表示在个体域中存在个体x，与个体域中的任何个体y都是朋友。(x)(y)F(x,y)表示在个体域中存在个体x与个体y，x与y是朋友。(x)(y)F(x,y)表示对于个体域中的任何两个个体x和y，x与y都是朋友。222.2.3谓词公式全称量词和存在量词出现的次序将影响命题的意思。例如：(x)(y)(Employee(x)→Manager(y,x)):“每个雇员都有一个经理。”(y)(x)(Employee(x)→Manager(y,x)):“有一个人是所有雇员的经理。”232.2.3谓词公式3.谓词公式定义2.2可按下述规则得到谓词演算的谓词公式：(1)单个谓词是谓词公式，称为原子谓词公式。(2)若A是谓词公式，则﹁A也是谓词公式。(3)若A，B都是谓词公式，则A∧B，A∨B，A→B，AB也都是谓词公式。(4)若A是谓词公式，则(x)A，(x)A也是谓词公式。(5)有限步应用（1）－（4）生成的公式也是谓词公式。连接词的优先级别从高到低排列：﹁，∧，∨，→，242.2.3谓词公式4．量词的辖域量词的辖域：位于量词后面的单个谓词或者用括弧括起来的谓词公式。约束变元与自由变元：辖域内与量词中同名的变元称为约束变元，不同名的变元称为自由变元。例如：(x)(P(x,y)→Q(x,y))∨R(x,y)(P(x,y)→Q(x,y))：(x)的辖域，辖域内的变元x是受（x）约束的变元，R(x,y)中的x是自由变元。公式中的所有y都是自由变元。252.2.4谓词公式的性质1.谓词公式的解释谓词公式在个体域上的解释：个体域中的实体对谓词演算表达式的每个常量、变量、谓词和函数符号的指派。Friends(george,x)Friends(george,susie)TFriends(george,kate)F对于每一个解释，谓词公式都可求出一个真值（T或F）。262.2.4谓词公式的性质2.谓词公式的永真性、可满足性、不可满足性定义2.5对于谓词公式P，如果至少存在一个解释使得P在此解释下的真值为T，则称P是可满足的，否则，则称P是不可满足的。定义2.4如果谓词公式P对个体域D上的任何一个解释都取得真值F，则称P在D上是永假的；如果P在每个非空个体域上均永假，则称P永假。定义2.3如果谓词公式P对个体域D上的任何一个解释都取得真值T，则称P在D上是永真的；如果P在每个非空个体域上均永真，则称P永真。272.2.4谓词公式的性质3.谓词公式的等价性定义2.6设P与Q是两个谓词公式，D是它们共同的个体域，若对D上的任何一个解释，P与Q都有相同的真值，则称公式P和Q在D上是等价的。如果D是任意个体域，则称P和Q是等价的，记为PQ。（4）德.摩根律(De.Morgen)（8）连接词化规律（蕴含、等价等值式）（10）量词转换律282.2.4谓词公式的性质4.谓词公式的永真蕴含定义2.7对于谓词公式P与Q，如果P→Q永真，则称公式P永真蕴含Q，且称Q为P的逻辑结论，称P为Q的前提，记为PQ。（3）假言推理（4）拒取式推理（5）假言三段论292.2.4谓词公式的性质谓词逻辑的其他推理规则①P规则：在推理的任何步骤上都可引入前提。②T规则：在推理过程中，如果前面步骤中有一个或多个公式永真蕴含公式S，则可把S引入推理过程中。③CP规则：如果能从任意引入的命题R和前提集合中推出S来，则可从前提集合推出R→S来。302.2.4谓词公式的性质所有的人都是会死的，因为诸葛亮是人，Human（Zhugeliang）所以诸葛亮是会死的。Die（Zhugeliang）{1}P规则{2}Human（Zhugeliang）P规则{1,2}Die（Zhugeliang）T规则QQPP,)3())()((xDiexHumanx))()((xDiexHumanx312.2.4谓词公式的性质谓词逻辑的其他推理规则：④反证法：，当且仅当，即Q为P的逻辑结论，当且仅当是不可满足的。QPFQPQP定理：Q为，，…，的逻辑结论，当且仅当是不可满足的。1P2PnPQPPPn)(21322.2.5一阶谓词逻辑知识表示方法谓词公式表示知识的步骤：（1）定义谓词及个体。（2）变元赋值。（3）用连接词连接各个谓词，形成谓词公式。例如：用一阶谓词逻辑表示下列关系数据库。住户房间电话号码房间Zhang201491201Li201492201Wang202451202Zhao203451203OccupantTelephone33用一阶谓词表示：Occupant（Zhang，201）Occupant（Li，201）Occupant（Wang，202）Occupant（Zhao，203）Telephone（491，201）Telephone（492，201）Telephone（451，202）Telephone（451，203）2.2.5一阶谓词逻辑知识表示方法342.2.6一阶谓词逻辑表示法的特点优点：①自然性②精确性③严密性④容易实现应用：（1）自动问答系统（Green等人研制的QA3系统）（2）机器人行动规划系统（Fikes等人研制的STRIPS系统）（3）机器博弈系统（Filman等人研制的FOL系统）（4）问题求解系统（Kowalski等设计的