人工智能第二章

Chapter2.DeclarativeKnowledgeKnowledgeandKnowledgeRepresentation§2.1Conceptualization§2.2PredicateCalculus§2.3Semantics§2.4~2.8Examples§2.9SpecializedLanguagesKnowledge是人们在改造客观世界的实践中积累起来的认识和经验Feigenbaum认为知识是经过削减、塑造、解释和转换的信息。简单地说，知识是经过加工的信息。Bernstein说知识是由特定领域的描述、关系和过程组成的。Hayes-Roth认为知识是事实、信念和启发式规则。从知识库观点看，知识是某论域中所涉及的各有关方面、状态的一种符号表示。知识的特性知识的特征相对正确性：知识在一定的条件下是正确的，但在另外一种情况下可能是不正确的。不确定性：事物之间的关系有时难以用真假状态来描述，不确定性就是指这种介于真假之间的中间状态。可表示性：知识通常通过一定的方法进行表示，如：语言、文字、图画、姿势、声音等。可利用性：人们常用知识来认识和改造世界ClassificationofKnowledge描述性知识（事实）：是有关问题环境的一些事物的知识，常以“…是…”的形式出现。判断性知识（规则）：是有关问题中与事物的行动、动作相联系的因果关系知识，是动态的，常以“如果…那么…”形式出现。过程性知识（控制）：是有关问题的求解步骤、技巧性知识，告诉怎么做一件事。也包括当有多个动作同时被激活时应选哪一个动作来执行的知识。KnowledgeRepresentation是研究用机器表示知识的可行性、有效性的一般方法，是一种数据结构与控制结构的统一体，既考虑知识的存储又考虑知识的使用。可看成是一组描述事物的约定，以把人类知识表示成机器能处理的数据结构。主要方法：谓词逻辑表示法、产生式规则表示法、语义网络表示法、框架表示法、面向对象表示法、脚本表示法、过程表示法。状态空间法在分析了人工智能研究中运用的问题求解方法之后，就会发现许多问题求解方法是采用试探搜索方法的。也就是说，这些方法是通过在某个可能的解空间内寻找一个解来求解问题的。这种基于解答空间的问题表示和求解方法就是状态空间法，它是以状态和算符(operator)为基础来表示和求解问题的。状态空间法的三要点状态（state）：表示问题解法中每一步问题状况的数据结构；算符（operator）：把问题从一种状态变换为另一种状态的手段；状态空间方法：基于解答空间的问题表示和求解方法，它是以状态和算符为基础来表示和求解问题的。

问题状态描述定义状态(state)：为描述某类不同事物间的差别而引入的一组最少变量q0，q1，…，qn的有序集合，其矢量形式如下：Q=[q0，q1，...，qn]T

式中每个元素qi(i=0,1，…，n)为集合的分量，称为状态变量。算符：使问题从一种状态变化为另一种状态的手段称为操作符或算符。操作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。操作的条件(对状态的要求)和对状态的改变。问题的状态空间(statespace)：是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即所有可能的问题初始状态集合S、操作符集合F以及目标状态集合G。可把状态空间记为三元状态(S，F，G)。

问题状态描述例

修道士和野人问题：设在河的左岸有三个野人,三个修道士和一条船,修道士想用这条船把所有的人运到河对岸,但受以下条件的约束: 1.修道士和野人都会划船; 2.船每次至多可载两个人; 3.在河的任一岸,如果野人数目超过修道士数,修道士就会被野人吃掉。 假设野人会服从任何一次过河安排,请规划一个确保修道士和野人都能过河,且没有修道士被野人吃掉的安全过河计划。问题状态描述状态

需要表示出在某岸上的修道士人数和野人数及船在哪岸上。Sk=(m,c,b) 其中,m表示左岸的修道士人数,c表示左岸的野人数,b表示左岸的船数。 初始状态:S0=(3,3,1) 中间状态:S4=(1,1,1) 目标状态:S15=(0,0,0)问题状态描描述算符算符定义：用符号Pij表示从左岸岸到右岸运运i个修道士,j个野人；用用符号Qij表示从右岸岸到左岸运运i个修道士,j个野人。考考虑到船每每次最多只只能载两人人,则所有有操作集合合:F={P01,P10,P11,P02,P20,Q01,Q10,Q11,Q02,Q20}操作的条件件:当前状态满满足可执行行条件操作不能产产生非法状状态例:P01的操作条条件:b=1,m=0或m=3,c≥1当前状态态:S4=(1,1,1)可执行的的操作:P01,P11问题状态态描述操作的结结果:操作执行行后对状状态的改改变例:P01的结果:b=0,c=c-1P10的结果:b=0,m=m-1P11的结果:b=0,c=c-1,m=m-1P02的结果:b=0,c=c-2,P20的结果:b=0,m=m-2Q01的结果:b=1,c=c+1Q10的结果:b=1,m=m+1……问题状态态描述要完成某某个问题题的状态态描述必必须确定定三件事事情：1、该状状态描述述方式，，特别是是初始状状态的描描述方式式2、操作作符（算算符）集集合及其其对状态态描述的的作用3、目标标状态描描述的特特征§2.1ConceptualizationTheformalizationofknowledgeindeclarativeforbeginswithaConceptualization.Objects（对象象）Function（函函数）Relation（关关系）Conceptualization（（概念化化）Objects需要描述述的任何何事物，，也称为为个体(individuals)具体的、、抽象的的简单的、、复杂的的客观存在在的、虚虚幻的论域（UniverseofDiscourse））：只与与问题有有关的对对象集合合积木例子子：D={a,b,c,d,e}abcde有限的Function函数：表表示对象象与对象象之间的的相互关关系。基函数集集：在概概念化过过程中使使用的基基本函数数集合。。举例：hat：：hat(b)=ahat(c)=b或者写成成{<b,a>,<c,b>,<e,d>}rotate:{<a,b>,<b,c>,<c,d>,<d,e>,<e,a>}abcdeRelation表示对象象与对象象之间的的相互关关系的另另一种形形式。基关系集集：在概概念化过过程中使使用的基基本关系系集合。。举例：on关系系：{<a,b>,<b,c>,<d,e>}above关系系:{<a,b>,<b,c>,<a,c>,<d,e>}clear关系系：{a,d}table关系系：{c,e}abcdeGeneralityofRelation关系的一一般性可可以通过过比较其其中的元元素来确确定。如如关系on比关关系above一般性性低，因因为onabove。特殊的关关系：空空关系，，全关系系具有b个个对象的的n元全全关系中中有bn个元组，，任一n元关系系都是上上述全关关系的一一个子集集。有个个n元元关系函数与关关系的区区别：函数：值值仍为对对象，至至少涉及及两个对对象关系：值值为真或或假，可可以只涉涉及一个个对象可以用关关系来表表示函数数Conceptualization概念化是是三元组组：<{对象集集},{函数集集},{关系集集}>如<{a,b,c,d,e},{hat},{on,above,clear,table}>概念化的的物理含含义与元元组的定定义（解解释）有有关，而而与名字字无关。。同一问题题存在多多种不同同的概念念化。不同的概概念化表表达的知知识可能能是不同同的，如如光的波波粒二象象性。概念化不不是一成成不变的的，需要要不断完完善和发发展。如如地心说说到日心心说的发发展。Conceptualization关系与函函数的实实例化：：将函数数与关系系作为对对象加入入到对象象集合中中，可以以描述函函数与关关系的属属性。<{a,b,c,d,e},{},{red,white,blue}>可可以描述述积木的的颜色;<{a,b,c,d,e,red,white,blue},{color},{nice}>可以评评价颜色色的好坏坏。(color(a)=red,nice:{red,white})如何找到更合合理的概念化化？需要考虑粒度度问题：也用用于粗糙集和和数据仓库中中粒度太小：问问题表示过于于繁琐，如积积木问题中以以原子为粒度度；粒度太大大：无法表达达细节§2.2PredicateCalculus谓词演算：将将知识形式化化成谓词公式式的形式语言言。谓词演算的基基本概念–命题谓词连接词与量词词项与谓词公式式自由变元和约约束变元谓词逻辑表示示方法谓词逻辑表示示方法的应用用Proposition命题：一个陈陈述句称为一一个断言，凡凡有真假意义的断言称为命命题。命题的意义通通常称为真值值。如果命题题是真，则称称它的真值为为真。如果命命题是假，则则称它的真值值为假。命题题的真值真与与假分别用“T”与“F”表示例：判别下列列语句哪些是是命题，哪些些不是命题，，是命题的指指出其真假。。海洋的面积比比陆地大别的星球上有有生物1+101=110请问电影院怎怎么走？Predicates谓词：带有参参数的命题叫叫谓词（反过过来，也可以以说不带参数数的谓词叫命命题）。例：北京是一个城城市：P1:CITY(北京)X是人：P2：HUMAN（X）张三打了李四四：P3：HIT（张三，李四））X和Y是同学：P4：CLASSMATE(x,y)谓词演算中的的符号变量、常量变量：小写字字母与数字的的序列，首字字母为小写字字母。对象常量：论论域中特定的的元素，字符符或数字序列列，首字母为为大写字符或或数字。函数常量：字字符或数字序序列，首字母母为大写字母母。关系常量：字字符或数字序序列，首字母母为大写字母母。每一个n元函函数常量能够够表达为一个个n+1元关关系常量，反反之不然。(Age(Confucius)=100),Age(confucius,100)DefinitionofPredicates定义：设D为论域，P是Dn→{T,F}的一个映射，，其中则称P是一个n元谓词，记为为P(x1,x2,…,xn)其中x1,x2,…,xn为谓词的个体体变元。如果xi(i=1,2,…,n)都是个体常量量、个体变量量或函数，称称P为一阶谓词。。如果xi又是一个一阶阶谓词，则称称P为二阶谓词。。ComparisonofPredicates&Propositions谓词比命题有有更强的表达达能力一个谓词通过过个体的变换换可以表达不不同命题的意意义。谓词可以代表表变化着的情情况，而命题题只能代表某某种固定的情情况。谓词的真值随随个体的变化化而变化而命题的真值值是固定的Connecters连接词：用来来连接简单命命题，并构成成复合命题的的逻辑运算符符号。￢：表示对其其后面的命题题的否定∨：“析取取”表示所连连结的两个命命题之间具有有或的关系。。∧：“合取”表示所连结的的两个命题之之间具有“与”的关系。→：“条件”或“蕴含”，表示“若…则…”。：“反向蕴蕴含”：“双条件”表示“当且仅当”Quantifiersx（全称量词））：对于所有有的x，任意的xx（存在量词））：存在x举例：所有的机器人人都是灰色的的x(ROBOT(x)→COLOR(x,GRAY))每个人都有父父亲xy(PERSON(x)→FATHER(x,y))Term项是论域中的的对象名，定定义如下：单独一个个体体（常量或变变量）是项；；若t1,t2,…,tn是项，f是n元函数，则则f(t1,t2,…,tn)是项；由1,２生成的表表达式是项项。因此，项有有三种类型型：变量、、常量或者者函数表达达式。Sentences谓词公式包包括原子公公式、逻辑辑公式和量量词公式。。原子公式：：若t1,t2,…,tn是项，Ｐ是谓词符号号，则称Ｐ(t1,t2,…,tn)是原子公式式。逻辑公式：：由原子公公式经过￢￢、∧、∨∨、→、、等逻辑运算算符连接得得到的公式式称为逻辑辑公式。量词公式：：若A是逻辑公式式，x是变量，则则xＡ和xＡ分别称为为全称量词词公式和存存在量词公公式。Scope辖域：谓词词公式中被被限定的公公式称为该该量词的辖辖域。例：x(P(x,y)→Q(x,y))∨R(x,y)z(P(z,t)→Q(z,t)∨R(z,t))量词的嵌套套顺序不同同，谓词公公式的含义义也不同。。如：x(yLove(x,y))y(xLove(x,y))whoisy?Raymond《人人都爱爱雷蒙德》》BoundandFreevariables约束变量：：辖域内与与量词中同同名的变量量称为约束束变量，其其它不受约约束的变量量称为自由由变量。Apple(x)→→Red(x)x(Apple(x)→Red(x))Apple(x)∨(xPear(x))闭谓词公式式：不含自自由变量的的谓词公式式。基谓词公式式：不含任任何变量的的谓词公式式。逻辑运算符符的优先级级如Table2.1。↑/∩+-∪∪=<>≤≥≥∈PredicateCalculusRepresentation事实性知识识：否定、、析取或合合取等连接接的谓词公公式表示。。规则：用蕴蕴含式表示示。一般方法：：定义谓词：：谓语作谓谓词，主语语作个体用连接词或或量词把谓谓词连结起起来，形成成谓词公式式。另一种方法法：从外到到里层层细细化。Example1例：所有教教师都有自自己的学生生定义谓词：：TEACHER(x):表示x是教师STUDENT(y):表示y是学生TEACHES(x,y):表示x是y的老师谓词公式：：xTEACHER(x)→y(TEACHES(x,y)∧STUDENT(y))Example2例：王宏是是计算机系系的一名学学生。李明明是王宏的的同班同学学。凡是计计算机系的的学生都喜喜欢编程。。定义谓词：：COMPUTER(x):表示x是计算机系系的学生CLASSMATE(x,y):表示x是y同班同学LIKE(x,y):表示x喜欢y。谓词公式：：COMPUTER(WangHong)CLASSMATE(LiMing,WangHong)x(COMPUTER(x)→→LIKE(x,Programing))Example3例：世上没没有无缘无无故的爱，，也没有无无缘无故的的恨。没有无缘无无故的爱∧∧没有无缘缘无故的恨恨￢存在无缘缘无故的爱爱∧￢存在在无缘无故故的恨￢x无缘无故的的爱(x)∧￢y无缘无故的的恨(y)￢x(爱(x)∧无缘故(x))∧￢y(恨(y)∧无缘故(y))￢x(爱(x)∧￢有缘故故(x))∧￢y(恨(y)∧￢有缘缘故(y))￢x(爱(x)∧￢z缘故(x,z))∧￢y(恨(y)∧￢t缘故(y,t))Example4x(Apple(x)Red(x))与x(Apple(x)Red(x))的区别§2.3SemanticsInterpretation（解解释）VariableAssignment（变变量指派）Satisfaction（满足性性）Elementarilyequivalent（单体体等价性）DeclarativeSemantics当且仅当一个个公式依照我我们采用的概概念化准确描描述了客观世世界时才称该该公式为真。。DatabaseWordConceptualizationObjectsFunctionsRelationsDefinitionofInterpretationAmappingbetweenelementsofthelanguageandelementsofaconceptualization.DenotedasI()orI.ForItobeaninterpretation,itmustsatisfythefollowingconditions:(a)Ifisanobjectconstant,thenI()|I|.(b)Ifisann-aryfunctionconstant,thenI():|I|n|I|.(c)Ifisann-aryrelationconstant,thenI()|I|n.|I|representstheuniverseofdiscourse.ExampleinthetextbookInterpretationIInterpretationJabcdeExampleofInterpretationI(P)D2I(P)={<1,2>,<2,1>,<2,2>}ExampleofInterpretationI(P)D2I(P)={<2,1>,<2,2>}ExampleofInterpretationI(b)=1I(f):f(1)=2f(2)=1I(P)={1}I(Q):包包含<2,1>不包含<1,1><1,2>,<2,2>未设定VariableAssignmentAfunctionfromthevariableofalanguagetoobjectsintheuniverseofdiscourse.DenotedasU()orU.xU=ayU=azU=bJointassignmentIU:AssignmentofvariablecorrespondstovariableassignmentU;AssignmentofnonvariablesymbolcorrespondstointerpretationI;TermjointassignmentTermjointassignmentIU:amappingfromtermstoobjects.(a)Ifisanobjectconstant,thenIU()=I().(b)Ifisavariable,thenIU()=U().(c)Ifisatermoftheform(1,…,n)andI()=gandIU(i)=xi,thenIU()=g(x1,...,xn).Example:Hat(C)=?:becauseI(C)=c,Hat(c)=b(<c,b>)Hat(z)=?:ifU(z)=babcdeSatisfactionAninterpretationIandavariableassignmentUsatisfyasentencemeansthatsentenceistruerelativetotheinterpretationIandtheassignmentU.Denotedas|=I[U].Aninterpretationandvariableassignmentsatisfyanequationifandonlyifthecorrespondingtermmapsintothesameobject.SatisfactionofanatomicsentenceIandUsatisfyanatomicsentence:Example：|=IOn(A,B)[U]IU(A)=aIU(B)=b<a,b>I(On)|=JOn(A,B)[U]JU(A)=aJU(B)=b<a,b>J(On)J(On)={<b,a>,<c,b>,<e,d>}abcdeSatisfactionofLogicalSentences(a)|=I(¬)[U]ifandonlyif|I[U].(b)|=I(1...n)[U]ifandonlyif|=I(i)[U]foralli=1,...,n.(c)|=I(1...n)[U]ifandonlyif|=I(i)[U]forsomei,1in.(d)|=I()[U]ifandonlyif|I[U]or|=I[U].(e)|=I()[U]ifandonlyif|=I[U]or|I[U].(f)|=I()[U]ifandonlyif|=I()[U]and|=I()[U].SatisfactionofquantifiedsentencesUniversallyquantifiedsentencesExistentiallyquantifiedsentencesTwokindsofvariables:andModelIfforallvariableassignment,aninterpretationIsatisfiesasentence,thenIiscalledamodelof.Denotedas|=I.Example:On(x,y)Above(x,y)Asentenceissatisfiableifandonlyifthereissomeinterpretationandvariableassignmentthatsatisfyit.Otherwise,itisunsatisfiable.Asentenceisvalid(正确的)ifandonlyifitissatisfiedbyeveryinterpretationandvariableassignment.abcdeSatisfactionofasetofsentencesAsetofsentencesissatisfiedbyaninterpretationIandavariableassignmentUifandonlyifeverymemberofissatisfiedbyIandU.Denotedas|=I[U].AninterpretationIisamodelofifandonlyifIisamodelofeverymemberof.Denotedas|=I.Asetofsentencesissatisfiableifandonlyifeverymemberofissatisfiable.Asetofsentencesisvalidifandonlyifeverymemberofisvalid.ElementarilyequivalentTwointerpretationsIandJareelementarilyequivalent(IJ)ifandonlyif|=I|=Jand|=J|=Iforanysentence.Example:|I|=setofrealnumbers|J|=setofrationalnumbers(有有理数)I(R):greaterthanrelationonrealsJ(R):greaterthanrelationonrationalsIandJareelementarilyequivalentdespitetheiruniversesaredifferent.if:R(5,3)then|=Ialso|=JStepsofknowledgerepresentation(1)conceptualizingtheapplicationarea(2)selectavocabularyofobjectconstants,functionconstantsandrelationconstants.(3)associatetheseconstantswiththeobjects,functionsandrelationsinourconceptualization.(4)writesentencesStartwithanideaofaconceptualization,writemoreandmoresentencestomakeitprecise.§2.5CircuitsExamplesConceptualizingtheapplicationareaf1:acircuitx1,x2:xorgatesa1,a2:andgateso1:orgate20Ports:Threeinputsandtwooutputsoff1TwoinputsandoneoutputofeachgateSelectavocabularyConnectionRepresenta