逻辑表示及推理方法.ppt

6/10/2020,1,第三部分逻辑表示及推理方法,常用的知识表示方法：非结构化方法逻辑表示法QA3,STRIPS,DART,MOMO产生式系统DENDRAL，MYCIN结构化方法框架语义网络过程式知识表示法,6/10/2020,2,第五章谓词演算（复习）,数理逻辑思想的起源：Leibnitz之梦产生的历史：Boole的工作、Frege的工作发展的现实：计算机学科的基础（软件到硬件）古典数理逻辑主要包括两部分：命题逻辑和谓词逻辑。命题逻辑又是谓词逻辑的一种简单情形。逻辑研究的基本内容语法语言部分：基本符号集、公式形成规则推理部分：公理集、推理规则语义语法和语义之间的关系：可靠性、完备性基本问题逻辑表示下的判定问题,6/10/2020,3,一、命题逻辑,1命题一句有真假意义的话。用大写英文字母P，Q，P1，P2，表示。例：上海是中国最大的城市。今天是星期日。所有素数都是奇数。1+1=2。我不会解答这道题。别的星球上有生物。长春今天下雪。如果太阳从西方升起，你就可以长生不老。严禁吸烟。今天的温度有多少度？全体起立！今天好冷啊！我正在说谎。,6/10/2020,4,2真值,如果一个命题是真的，就说它的真值是T；如果一个命题是假的，就说它的真值是F。T和F统称为命题的真值。也用T代表一个抽象的真命题，用F代表一个抽象的假命题。,6/10/2020,5,3联结词、,设P是一个命题，命题“P是不对的”称为P的否定，记以P，读作非P。例.Q:张三是好人。Q：张三不是好人。语义规定：P是真的当且仅当P是假的。设P，Q是两个命题，命题“P或者Q”称为P，Q的析取，记以PQ，读作P析取Q。例.P：今天下雪，Q：今天刮风，PQ：今天下雪或者刮风。语义规定：PQ是真的当且仅当P,Q中至少有一个为真。,6/10/2020,6,设P，Q是两个命题，命题“P并且Q”称为P，Q的合取，记以PQ，读作P合取Q。例.P：22=5，Q：雪是黑的，PQ：22=5并且雪是黑的。语义规定：PQ是真的当且仅当P和Q都是真的。设P，Q是两个命题，命题“如果P，则Q”称为P蕴涵Q，记以PQ。例.P：f(x)是可微的，Q：f(x)是连续的，PQ：若f(x)是可微的，则f(x)是连续的。语义规定：PQ是假的当且仅当P是真的而Q是假的。,6/10/2020,7,设P，Q是两个命题，命题“P当且仅当Q”称为P等价Q，记以PQ。语义规定：PQ是真的当且仅当P，Q或者都是真的，或者都是假的。例P：a2+b2=a2，Q：b=0，PQ：a2+b2=a2当且仅当b=0。五种逻辑联结词的优先级按如下次序递增：，例.符号串PQRQSR意味着：(P(QR)(Q(S)R),6/10/2020,8,4复合命题用联结词将简单命题连接的结果。5原子命题的抽象。用大写的英文字母P，Q，R，等表示。6文字原子或原子的否定。7子句有限个文字的析取式称为一个子句。特别，没有文字的子句称为空子句，记为。只有一个文字的子句称为单元子句。8短语有限个文字的合取式称为一个短语。,6/10/2020,9,复合命题的抽象公式的形成规则-是如下定义的一个符号串：(1)原子是公式；(2)F、T是公式；(3)若G，H是公式，则(G)，(GH)，(GH)，(GH)，(GH)是公式；(4)所有公式都是有限次使用(1)，(2)，(3)得到的符号串。,9公式,6/10/2020,10,设G是命题公式,A1,An是出现在G中的所有原子。指定A1,An的一组真值,则这组真值称为G的一个解释。设G是公式，I是G的一个解释，G在I下的真值记为TI(G)。例.G=PQ，设解释I，I如下：I：I：则TI(G)=T，TI(G)=F注意：该例子中写成G=T或G=F是错误的！,10解释,PQ,TT,6/10/2020,11,11真值表公式G在其所有可能的解释下所取真值的表，称为G的真值表。有n个不同原子的公式，共有2n个解释。12恒真公式公式G称为恒真的(或有效的)，如果G在它的所有解释下都是真的.,6/10/2020,12,13恒假公式公式G称为恒假的(或不可满足的)，如果G在它的所有解释下都是假的.14可满足公式公式G称为可满足的，如果它不是恒假的。G是恒真的iffG是恒假的。G是可满足的iff至少有一个解释I，使G在I下为真。若G是恒真的，则G是可满足的；反之不对。如果公式G在解释I下是真的，则称I满足G；如果G在解释I下是假的，则称I弄假G。,6/10/2020,13,例.考虑G1=(PQ)P，G2=(PQ)P，G3=PP。,6/10/2020,14,15判定问题,能否给出一个可行方法，对任意的公式，判定其是否是恒真公式。命题逻辑可判定？原因？因为一个命题公式的原子数目有限(n)，从而解释的数目是有限的(2n)，所以命题逻辑的判定问题是可解的(可判定的，可计算的).,6/10/2020,15,16公式等价,称公式G，H是等价的，记以G=H，如果G，H在其任意解释I下，其真值相同。公式G，H等价iff公式GH恒真。基本等价式1)(GH)=(GH)(HG)；2)(GH)=(GH)；3)GG=G，GG=G；(等幂律)4)GH=HG，GH=HG；(交换律)5)G(HS)=(GH)S，G(HS)=(GH)S；(结合律),6/10/2020,16,6)G(GH)=G，G(GH)=G；(吸收律)7)G(HS)=(GH)(GS)，G(HS)=(GH)(GS)；(分配律)8)GF=G，GT=G；(同一律)9)GF=F，GT=T；(零一律)10)(GH)=GH，(GH)=GH。(DeMorgan律)11)GG=T；GG=F（互补律）12)G=G（双重否定律）,6/10/2020,17,17公式的蕴涵,设G，H是两个公式。称H是G的逻辑结果(或称G蕴涵H)，当且仅当对G，H的任意解释I，如果I满足G，则I也满足H，记作GH。公式G蕴涵公式Hiff公式GH是恒真的。设G1,Gn，H是公式。称H是G1,Gn的逻辑结果(或称G1,Gn共同蕴涵H)，当且仅当(G1Gn)H。例如，P，PQ共同蕴涵Q。,6/10/2020,18,基本蕴涵式,PQPPQQPPQQPQP(PQ)Q(PQ)(PQ)P,6/10/2020,19,基本蕴涵式,(PQ)QP，QPQP，PQQP，PQQQ，PQPPQ，QRPRPQ，PR，QRR,6/10/2020,20,18范式,有限个短语的析取式称为析取范式；有限个子句的合取式称为合取范式。特别，一个文字既可称为是一个合取范式，也可称为是一个析取范式。一个子句，一个短语既可看做是合取范式，也可看做是析取范式。例如，P，PQ，PQ，(PQ)(PQ)是析取范式。P，PQ，PQ，(PQ)(PR)是合取范式。,6/10/2020,21,化范式方法：,步1.使用基本等价式，将G中的逻辑联结词，删除。步2.使用(H)=H和摩根律，将G中所有的否定号都放在原子之前。步3.反复使用分配律，即可得到等价于G的范式。,6/10/2020,22,19演绎,设S是一个命题公式的集合(前提集合)。从S推出公式G的一个演绎是公式的一个有限序列：G1,G2,Gk其中，Gi（1ik）或者属于S，或者是某些Gj(j3,23,503等50个命题。,6/10/2020,25,2不能描述问题间的逻辑联系例如，逻辑学中著名的三段论：P：凡人必死Q：张三是人R：张三必死在命题逻辑中：应该有(PQ)R，从而公式(PQ)R应该是恒真的。显然该公式不是恒真的，解释P，Q，R就能弄假该公式。,6/10/2020,26,原因：命题R是和命题P,Q有关系的，只是这种关系在命题逻辑中无法表示。因此，需要对命题的成分、结构和命题间的共同特性等作进一步的分析，这正是谓词逻辑所要研究的问题。,6/10/2020,27,为了表示出这三个命题的内在关系，需要引进谓词的概念。例如，在前面的例子“张三是人”中的“是人”是谓语，称为谓词，“张三”是主语，称为个体。,6/10/2020,28,二、谓词逻辑,1谓词可以独立存在的物体称为个体。如人、学生、桌子、自然数等都可以做个体。在谓词演算中，个体通常指一个命题里的思维对象。设D是非空个体名称集合，定义在Dn上取值于T，F上的n元函数，称为n元命题函数或n元谓词。其中Dn表示集合D的n次笛卡尔乘积。一般地，一元谓词描述个体的性质，二元或多元谓词描述两个或多个个体间的关系。0元谓词中无个体，理解为就是命题，这样，谓词逻辑包括命题逻辑。,6/10/2020,29,例.,D=2,3,4设P(x)：x大于3，则P(x)为一元谓词。指定元素-命题：P(2)=F,P(3)=F,P(4)=T设P(x,y)：x大于y,则P(x,y)为二元谓词。指定元素-命题：P(2,3)=F,P(4,2)=T设P(x,y,z)：若x+y-1=z，则P(x,y,z)为T，否则为F。则P(x,y,z)为三元谓词。指定元素-命题：P(2,3,4)=T,P(4,2,2)=F,6/10/2020,30,例.,用谓词的概念可将三段论做如下的符号化：令H(x)表示“x是人”，M(x)表示“x必死”。则三段论的三个命题表示如下：P：H(x)M(x)Q：H(张三)R：M(张三),6/10/2020,31,若想得到“命题”P的否定“命题”，应该就是“命题”P。但是，P=(H(x)M(x)=(H(x)M(x)=H(x)M(x)亦即，“命题”P的否定“命题”是“所有人都不死”。这和人们日常对命题“所有人都必死”的否定的理解，相差得实在太远了.,6/10/2020,32,原因命题P的确切意思应该是：“对任意x，如果x是人，则x必死”。但是H(x)M(x)中并没有确切的表示出“对任意x”这个意思，亦即H(x)M(x)不是一个命题。因此，在谓词逻辑中除引进谓词外，还需要引进“对任意x”这个语句，及其对偶的语句“存在一个x”。,6/10/2020,33,2量词,定义语句“对任意x”称为全称量词，记以x；语句“存在一个x”称为存在量词，记以x。这时，命题P就可确切地符号化如下：x(H(x)M(x)命题P的否定命题为：P=(x(H(x)M(x)=x(H(x)M(x)亦即“有一个人是不死的”。这个命题确实是“所有人都要死”的否定。三段论的三个命题，在谓词逻辑中是如下这样表示的：P：x(H(x)M(x)Q：H(张三)R：M(张三),6/10/2020,34,量词的语义规定xG(x)取T值对任意xD，G(x)都取T值；xG(x)取T值至少有一个x0D，使G(x0)取T值语义上，当D=x0,x1,是可数集合时，xG(x)等价于G(x0)G(x1)xG(x)等价于G(x0)G(x1),6/10/2020,35,例.将下列命题符号化：)一切事物都是发展变化的xF(x)其中F(x)：x是发展变化的)存在着会说话的机器人x(F(x)G(x)其中F(x)：x会说话G(x):x是机器人如果没有明确给出个体域，则认为个体域为一切事物。,6/10/2020,36,3)每个计算机学院的学生都学离散数学。D：全校学生集合P(x)：x是计算机学院的学生R(x):x学离散数学x(P(x)R(x)4）存在着偶素数D：正整数集合E(x)：x是偶数P(x)：x是素数x(E(x)P(x),6/10/2020,37,5)每个人都会犯错误R(x):x是人P(x):x会犯错误x(R(x)P(x),6/10/2020,38,3约束变量、自由变量,在一个由谓词，量词，逻辑联结词，括号组成的有意义的符号串(公式)中，称变量的出现是约束的，当且仅当它出现在使用这个变量的量词范围之内；称变量的出现是自由的，当且仅当这个出现不是约束的。称变量是约束的，如果至少有一个它的出现是约束的；称变量是自由的，如果至少有一个它的出现是自由的。例如，x(P(x，y)Q(x，z)R(x)从左向右算起，变量x的第一，第二次出现是约束的，第三次出现是自由的；变量y，z的出现是自由的。x既是约束变量，又是自由变量；y，z只是自由变量。,6/10/2020,39,4约束变量的改名规则,改名规则的理论依据xP(x)与yP(y)都是表示个体域D中的“每个个体都具有性质P”，所以可以把x改名为y，即把xP(x)改成为yP(y)。xP(x)与yP(y)都是表示个体域D中的“某个个体具有性质P”，所以也可以把x改名为y，即把xP(x)改成为yP(y)。亦即，谓词逻辑中命题的真值，与命题中的约束变量的记法无关。这就引出了谓词逻辑中的改名规则。,6/10/2020,40,改名规则：在由谓词，量词，逻辑联结词，括号组成的有意义的符号串(公式)中，可将其中出现的约束变量改为另一个约束变量，这种改名必须在量词作用区域内各处以及该量词符号中实行，并且改成的新约束变量要有别于改名区域中的所有其它变量。显然改名规则不改变原符号串的真值。,6/10/2020,41,例:,对于x(P(x，y)Q(x，z)R(x,v)，可改名为u(P(u，y)Q(u，z)R(x,v)。但下面的改名都是不对的：a.u(P(u，y)Q(x，z)R(x,v)b.x(P(u，y)Q(u，z)R(x,v)c.u(P(x，y)Q(x，z)R(x,v)d.y(P(y，y)Q(y，z)R(x,v)e.z(P(z，y)Q(z，z)R(x,v),6/10/2020,42,5封闭公式,公式中无自由变量，或将自由变量看做常量。(公式中每个变量的出现都是约束的）,6/10/2020,43,1)常量符号：用小写英文字母a，b，c，表示，当个体名称集合D给出时，它可以是D中某个元素。2)变量符号：用小写英文字母u，v，w，x，y，z，表示，当个体名称集合D给出时，D中任意元素可代入变量符号。,6谓词逻辑形式化中使用的四种符号,6/10/2020,44,3)函数符号：用小写英文字母f，g，表示，当个体名称集合D给出时，n元函数符号f(x1，xn)可以是Dn到D的任意一个映射。4)谓词符号：用大写英文字母P，Q，R，表示，当个体名称集合D给出时，n元谓词符号P(x1，xn)可以是Dn上的任意一个谓词。,6/10/2020,45,7项谓词逻辑中的项，被递归定义为：1)常量符号是项；2)变量符号是项；3)若f(x1,xn)是n元函数符号，t1,tn是项，则f(t1,tn)是项；4)所有项都是有限次使用1)，2)，3)生成的符号串。8原子若P(x1,xn)是n元谓词符号，t1,tn是项，则P(t1,tn)是原子。,6/10/2020,46,9公式,谓词逻辑中的公式，被递归定义如下：1)原子是公式；2)若G，H是公式，则(G)，(GH)，(GH)，(GH)，(GH)是公式；3)若G是公式，x是G中的自由变量，则xG，xG是公式；4)所有公式都是有限次使用1)3)生成的符号串。,6/10/2020,47,10公式的语义解释,谓词逻辑中公式G的一个解释I，是由非空区域D和对G中常量符号，函数符号，谓词符号以下列规则进行的一组指定组成：1.对每个常量符号，指定D中一个元素；2.对每个n元函数符号，指定一个函数，即指定Dn到D的一个映射；3.对每个n元谓词符号，指定一个谓词，即指定Dn到T，F的一个映射。,6/10/2020,48,例:,1)G=x(P(f(x)Q(x，f(a)2)H=x(P(x)Q(x，a)设解释I：D=2，3a2f(2)f(3)32P(2)P(3)Q(2,2)Q(2,3)Q(3,2)Q(3,3)FTTTFT,6/10/2020,49,例:,TI(G)=TI(P(f(2)Q(2，f(2)(P(f(3)Q(3，f(2)=TI(P(3)Q(2，3)(P(2)Q(3，3)=(TT)(FT)=TTI(H)=TI(P(2)Q(2，2)P(3)Q(3，2)=FTTF=F,6/10/2020,50,11谓词公式的恒真、恒假、可满足,公式G称为可满足的，如果存在解释I，使G在I下取T值，简称I满足G。若I不满足G，则简称I弄假G。公式G称为是恒假的(或不可满足的)，如果不存在解释I满足G。公式G称为恒真的，如果G的所有解释I都满足G。,6/10/2020,51,12谓词逻辑的判定问题,谓词逻辑中公式恒真、恒假性的判断异常困难。原因？谓词逻辑中的恒真(恒假)公式，要求所有解释I都满足(弄假)该公式。而解释I依赖于一个非空集合D。由于集合D可以是无穷集合，而集合D的“数目”也可能是无穷多个。因此，所谓公式的“所有”解释，实际上是无法考虑的。1936年Church和Turing分别独立地证明了：对于谓词逻辑，判定问题是不可解的。,6/10/2020,52,谓词逻辑是半可判定的：如果谓词逻辑中的公式是恒真的，则有算法在有限步之内检验出这个公式的恒真性。如果该公式不是恒真的(当然也不是恒假的)，则无法在有限步内判定这个事实。,6/10/2020,53,13等价,公式G，H称为等价，记以G=H，如果公式GH是恒真的。公式G，H等价的充要条件是：对G，H的任意解释I，G，H在I下的真值相同。因为对任意公式G，H，在解释I下，G，H就是两个命题，所以命题逻辑中给出的基本等价式，在谓词逻辑中仍然成立。,6/10/2020,54,设G，H是公式，称G蕴涵H，或H是G的逻辑结果，如果公式GH是恒真的，并记以GH。对任意两个公式G，H，G蕴涵H的充要条件是：对任意解释I，若I满足G，则I必满足H。同样，命题逻辑中的基本蕴涵式仍成立。,14蕴涵,6/10/2020,55,基本蕴涵式：,(PP)PP(PQ)(PQ)(QP)(QR)(PQ)(PR)xP(x)P(y)P(y)xP(x)xP(x)xP(x)xP(x)xQ(x)x(P(x)Q(x)x(P(x)Q(x)xP(x)xQ(x)x(P(x)Q(x)xP(x)xQ(x)x(P(x)Q(x)xP(x)xQ(x),6/10/2020,56,例.设G=x(A(x)B(x)，H=xA(x)xB(x)证明：GH证明：设I是满足G的任意一个解释。若TI(xA(x)=F,则TI(xA(x)xB(x)=T;若TI(xA(x)=T,则在I下对任意xD，有TI(A(x)=T，又由TI(x(A(x)B(x)=T知，对任意xD，TI(A(x)B(x)=T，故TI(B(x)=T，即，TI(x(B(x)=T，因此，TI(xA(x)xB(x)=T。,6/10/2020,57,G，H不等价。举反例：简单扼要、击中要害I:D=2，3A(2)A(3)B(2)B(3)TFFFTI(G)=FTI(H)=T,G=x(A(x)B(x)，H=xA(x)xB(x)？HG,6/10/2020,58,58,设在一个含有凹室(alcove)的房间内，有桌子A和书架B，一个机器人(robot)和一叠书(book)。现在要求机器人(robot)从凹室出发，把桌子A上的书搬到B处书架上，完成任务后回到凹室。请用谓词逻辑描述机器人完成这一工作的全过程。,谓词逻辑知识表示的例子,6/10/2020,59,59,谓词逻辑知识表示的例子,解：为了能够描述这个机器人世界的有关环境和状态变迁，要求必须先定义谓词。注意这里需要定义两类谓词：一类用来描述环境状态，另一类谓词用来表示机器人的操作。首先定义描述环境状态的谓词。TABLE(x)：x是桌子，x的个体域：a；BOOKCASE(z)：z是书架，z的个体域：b；EMPTY(y)：y手中是空的，y的个体域：robot；HOLDS(y，u)：y手中拿着u，u的个体域：books；AT(y，w)：y在w处，w的个体域：a，b，alcove；ON(u，x)：u被放在x之上；CLEAR(v)：v上(中)是空的，v的个体域：a，b.,6/10/2020,60,60,谓词逻辑知识表示的例子,解：使用谓词以及联结词、量词等来表示环境状态。这样，问题的初始状态可表示为：S0：AT(robot,alcove)EMPTY(robot)ON(books,a)CLEAR(b)TABLE(a)BOOKCASE(b)要求达到的目标状态为：Sg：AT(robot,alcove)EMPTY(robot)ON(books,b)CLEAR(a)TABLE(a)BOOKCASE(b),6/10/2020,61,61,谓词逻辑知识表示的例子,解：从初始状态到达目标状态的变迁，必须由机器人一步一步地执行相应的操作序列，得以逐步实现。因此，必须要定义操作类谓词。仔细加以分析，必要的操作谓词共有三类。GOTO(x,w)：机器人从x走到w处；PICK-UP(x)：机器人在x处拿起书；SET-DOWN(w)：机器人在w处放下书。一般说来，如果定义谓词太多，将造成信息冗余，增加了问题的复杂度；如果定义谓词太少，就不够用。因此，定义的谓词性质与数量要合适。,6/10/2020,62,62,谓词逻辑知识表示的例子,解：按照行动规划，仔细选择操作，一步步进行状态替换，直到达到目标状态。即要求把状态变迁过程和操作序列记录下来，来描述问题解。下面写出该过程的最优路径：AT(robot,alcove)EMPTY(robot)ON(books,a)CLEAR(b)TABLE(a)BOOKCASE(b),AT(robot,a)EMPTY(robot)ON(books,a)CLEAR(b)TABLE(a)BOOKCASE(b),AT(robot,a)HOLDS(robot，books)CLEAR(a)CLEAR(b)TABLE(a)BOOKCASE(b),GOTO(alcove,a),PICK-UP（a）,6/10/2020,63,63,谓词逻辑知识表示的例子,解：AT(robot,a)HOLDS(robot，books)CLEAR(a)CLEAR(b)TABLE(a)BOOKCASE(b),AT(robot,b)HOLDS(robot，books)CLEAR(a)CLEAR(b)TABLE(a)BOOKCASE(b),AT(robot,b)EMPTY(robot)ON(books,b)CLEAR(a)TABLE(a)BOOKCASE(b),AT(robot,alcove)EMPTY(robot)ON(books,b)CLEAR(a)TABLE(a)BOOKCASE(b)（解毕）,GOTO（b,alcove）,GOTO（a,b）,SET-DOWN（b）,6/10/2020,64,64,谓词逻辑知识表示的例子,解：这样,得到目标为AT(robot,alcove)EMPTY(robot)ON(books,b)CLEAR(a)TABLE(a)BOOKCASE(b)这里顺便指出，若机器人智商不高，这个任务过程会产生许多冗余。比如，机器人拿着书，找不到b处，无所适从而又扛回来了；或者等。可见，实际的机器人智能控制要更加复杂得多，虽然有时也很有趣。,6/10/2020,65,例将自然数公理符号化：A1：每一个数，有且仅有一个直接后继者；A2：没有一个数使0是直接后继者；A3：对任意异于0的数，有且仅有一个直接先行者。解：令f(x)表示x的直接后继者g(x)表示x的直接先行者E(x,y)表示x等于y,谓词逻辑知识表示的例子,6/10/2020,66,于是将上述三个公理符号化如下：A1：每一个数，有且仅有一个直接后继者xy(E(y,f(x)z(E(z,f(x)E(y,z)A2：没有一个数使0是直接后继者(xE(0,f(x)A3：对任意异于0的数，有且仅有一个直接先行者x(E(0,x)y(E(y,g(x)z(E(z,g(x)E(y,z),6/10/2020,67,解：令P(x)表示x是病人D(x)表示x是医生Q(x)表示x是骗子L(x,y)表示x喜欢yA1=x(P(x)y(D(y)L(x,y)A2=(xy(P(x)Q(y)L(x,y)x(P(x)y(Q(y)L(x,y)xy(P(x)Q(y)L(x,y)B=x(D(x)Q(x),例已知某些病人喜欢所有的医生，没有一个病人喜欢任意一个骗子。证明任意一个医生都不是骗子。,6/10/2020,68,剩下的任务就是调用某一过程证明A1A2B是一阶逻辑中的恒真公式，即B是A1、A2的逻辑结果。我们把它留到下一章中讨论。,6/10/2020,69,69,逻辑知识表示的主要特点是建立在某种形式逻辑的基础上，并利用了逻辑方法研究推理的规律，即条件与结论之间的蕴涵关系。逻辑表示法的主要优点如下：（1）自然一阶谓词逻辑是一种接近于自然语言的形式语言系统，谓词逻辑表示法接近于人们对问题的直观理解，易于被人们接受。（2）明确逻辑表示法对如何由简单陈述句构造复杂陈述句的方法有明确规定，如联结词、量词的用法与含义等。对于用逻辑表示法表示的知识，人们都可以按照一种标准的方法去解释它，因此用这种方法表示的知识明确、易于理解。,谓词逻辑表示的特性,6/10/2020,70,70,（3）精确谓词逻辑是一种二值逻辑，其谓词公式的真值只有“真”与“假”，因此可用来表示精确知识，并可保证经演绎推理所得结论的精确性。（4）灵活逻辑表示法把知识和处理知识的程序有效地分开。在使用这种方法表示知识时，无须考虑程序中处理知识的细节。,（5）模块化在逻辑表示法中，各条知识都是相对独立的，它们之间不直接发生联系。因此添加、删除、修改知识的工作比较容易进行。,谓词逻辑表示的特性,6/10/2020,71,71,逻辑表示法也存在一些不足，其主要缺点如下：（1）知识表示能力差逻辑表示法只能表示确定性知识，而不能表示非确定性知识，如不精确、模糊性知识。实际上，人类的大部分知识都不同程度地具有某种不确定性，这就使得它表示知识的范围和能力受到了一定的限制。另外，逻辑表示法还难以表示过程性知识和启发性知识。（2）知识库管理困难逻辑表示法缺乏知识的组织原则，利用这种表示法所形成的知识库管理比较困难。（3）存在组合爆炸由于逻辑表示法难以表示启发性知识，因此在推理过程中只能盲目地使用推理规则。这样，当系统知识量较大时，容易发生组合爆炸。（4）系统效率低逻辑表示法的推理过程是根据形式逻辑进行的。它把推理演算与知识含义截然分开，抛弃了表达内容中所含有的语义信息，往往使推理过程冗长，降低了系统效率。,谓词逻辑表示的特性,6/10/2020,72,15前束范式,谓词逻辑中公式G称为前束范式，如果G有如下形状：Q1x1QnxnM其中Qixi或者是xi，或者是xi，i=1,n，M是不含量词的公式，Q1x1Qnxn称为首标，M称为母式。例如，xyz(P(x，y)Q(x，z)xyzP(x，y，z),6/10/2020,73,对任意谓词公式，量词是不能随便提前的。？xP(x)P(a)=x(P(x)P(a)？xP(x)P(a)=x(P(x)P(a),6/10/2020,74,xP(x)P(a)是恒真公式.任取解释I，若P(a)在I下为真,则xP(x)P(a)在I下为真;若P(a)在I下为假,则xP(x)在I下为假,故xP(x)P(a)在I下为真因此,xP(x)P(a)是恒真公式.,6/10/2020,75,而x(P(x)P(a)不是恒真公式。设解释I为：D=1，2a1P(1)P(2)FT则TI(x(P(x)P(a)=TI(P(1)P(1)(P(2)P(1)=TF=F因此，xP(x)P(a)x(P(x)P(a),6/10/2020,76,x（P(x)P(a)）为恒真公式。任取解释I，由P(a)P(a)为真，知，存在xD，使得P(x)P(a)为真，即x（P(x)P(a)）为真。因此，x（P(x)P(a)）为恒真公式。,6/10/2020,77,而xP(x)P(a)不是恒真公式。对于解释I，若xP(x)在I下为F，则xP(x)P(a)在I下为T。若xP(x)在I下为T，则如果P(a)在I下为T，则xP(x)P(a)在I下为T，否则如果P(a)在I下为F，则xP(x)P(a)在I下为F。比如，对于前面给出的解释I，TI(xP(x)P(a)=(P(1)P(2)P(1)=(FT)F=F因此，x(P(x)P(a)和xP(x)P(a)不等价。,6/10/2020,78,引理1设G是仅含有自由变量x的公式，记以G(x)，H是不含变量x的公式，于是有(1)x(G(x)H)=xG(x)H(1)x(G(x)H)=xG(x)H(2)x(G(x)H)=xG(x)H(2)x(G(x)H)=xG(x)H(3)(xG(x)=x(G(x)(4)(xG(x)=x(G(x),6/10/2020,79,引理2设H，G是两个仅含有自由变量x的公式，分别记以H(x)，G(x)，于是有：(1)xG(x)xH(x)=x(G(x)H(x)(2)xG(x)xH(x)=x(G(x)H(x)(3)xG(x)xH(x)=xy(G(x)H(y)(4)xG(x)xH(x)=xy(G(x)H(y),6/10/2020,80,思考,?xG(x)xH(x)x(G(x)H(x)?xG(x)xH(x)x(G(x)H(x)?x(G(x)H(x)xG(x)xH(x),6/10/2020,81,设I为：D=a,bG(a)G(b)H(a)H(b)TFFTTI(xG(x)xH(x)=FTI(x(G(x)H(x)=T,6/10/2020,82,?xG(x)xH(x)x(G(x)H(x)?x(G(x)H(x)xG(x)xH(x)?xG(x)xH(x)x(G(x)H(x),6/10/2020,83,设I为：D=a,bG(a)G(b)H(a)H(b)TFFTTI(xG(x)xH(x)=TTI(x(G(x)H(x)=F,6/10/2020,84,化前束范式,定理1任意公式G都等价于一个前束范式证明通过如下四个步骤即可将公式G化为前束范式步骤1：使用基本等价式FH=(FH)(HF)FH=FH可将公式G中的和删去。步骤2：使用(F)=F和De.Morgan律及引理1，可将公式中所有否定号放在原子之前。步骤3：如果必要的话，则将约束变量改名步骤4：使用引理1和引理2又将所有量词都提到公式的最左边。,6/10/2020,85,例将xy(z(P(x,z)P(y,z)uQ(x,y,u)化为前束范式,xy(z(P(x,z)P(y,z)uQ(x,y,u)=xy(z(P(x,z)P(y,z)uQ(x,y,u)=xy(z(P(x,z)P(y,z)uQ(x,y,u)=xy(z(P(x,z)P(y,z)uQ(x,y,u)=xyz(P(x,z)P(y,z)uQ(x,y,u)=xyzu(P(x,z)P(y,z)Q(x,y,u),6/10/2020,86,例.将公式xy(A(x)B(x,y)(yC(y)zD(z)化为前束范式。,解：（1）消去联结词。xy（A(x)B(x,y)）(yC(y)zD(z)=xy（A(x)B(x,y)）（yC(y)zD(z)（2）将公式中所有否定号放在原子之前。xy（A(x)B(x,y)）（yC(y)zD(z)=xy(A(x)B(x,y)(yC(y)zD(z)（3）将约束变量改名.xy(A(x)B(x,y)(yC(y)zD(z)=xy(A(x)B(x,y)(tC(t)zD(z)（4）将量词提到整个公式前。xy(A(x)B(x,y)(tC(t)zD(z)=xytz（(A(x)B(x,y)C(t)D(z)）=xytz(A(x)C(t)D(z)(B(x,y)C(t)D(z),6/10/2020,87,16Skolem范式,设G是一个公式，Q1x1QnxnM是与G等价的前束范式，其中M为合取范式形式。若Qr是存在量词，并且它左边没有全称量词，则取异于出现在M中所有常量符号的常量符号c，并用c代替M中所有的xr，然后在首标中删除Qrxr。,6/10/2020,88,若Qs1,Qsm是所有出现在Qrxr左边的全称量词(m1,1s1s2smr),则取异于出现在M中所有函数符号的m元函数符号f(xs1,xsm)，用f(xs1,xsm)代替出现在M中的所有xr，然后在首标中删除Qrxr.,6/10/2020,89,对首标中的所有存在量词做上述处理后，得到一个在首标中没有存在量词的前束范式，这个前束范式就称为公式G的Skolem范式。其中用来代替xr的那些常量符号和函数符号称为公式G的Skolem函数.,6/10/