人工智能第二章

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-1 P10的结果:b=0,m=m-1 P11的结果:b=0,c=c-1,m=m-1 P02的结果:b=0,c=c-2, P20的结果:b=0,m=m-2 Q01的结果:b=1,c=c+1 Q10的结果: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(x

Love(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)Asentenceis

satisfiableifandonlyifthereissomeinterpretationandvariableassignmentthatsatisfyit.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:Threeinputs

andtwooutputsoff1Twoinputsandone

o