逻辑表示及推理方法课件

第三部分第三部分 逻辑表示及推理方法逻辑表示及推理方法 常用的知识表示方法：常用的知识表示方法：l非结构化方法非结构化方法逻辑表示法 QA3,STRIPS,DART,MOMO产生式系统 DENDRAL，MYCINl结构化方法结构化方法框架语义网络l过程式知识表示法过程式知识表示法6/17/20241第三部分 逻辑表示及推理方法 常用的知识表示方法：8/3/2第五章第五章 谓词演算（复习）谓词演算（复习）l数理逻辑思想的起源：数理逻辑思想的起源：Leibnitz之梦之梦 产生的历史：产生的历史：Boole的工作、的工作、Frege的工作的工作 发展的现实：计算机学科的基础（软件到硬件）发展的现实：计算机学科的基础（软件到硬件）古典数理逻辑主要包括两部分：命题逻辑和谓词逻辑。古典数理逻辑主要包括两部分：命题逻辑和谓词逻辑。命题逻辑又是谓词逻辑的一种简单情形。命题逻辑又是谓词逻辑的一种简单情形。l逻辑研究的基本内容逻辑研究的基本内容 语法语法 语言部分：基本符号集、公式形成规则语言部分：基本符号集、公式形成规则 推理部分：公理集、推理规则推理部分：公理集、推理规则 语义语义 语法和语义之间的关系：语法和语义之间的关系：可靠性、完备性可靠性、完备性l基本问题基本问题 逻辑表示下的判定问题逻辑表示下的判定问题6/17/20242第五章 谓词演算（复习）数理逻辑思想的起源：Leibnitz一、命题逻辑一、命题逻辑1 命题命题 一句有真假意义的话。用大写英文字母P，Q，P1，P2，表示。例：上海是中国最大的城市。上海是中国最大的城市。今天是星期日。今天是星期日。所有素数都是奇数。所有素数都是奇数。1+1=2。我不会解答这道题。我不会解答这道题。别的星球上有生物。别的星球上有生物。长春今天下雪。长春今天下雪。如果太阳从西方升起，你就可以长生不老。如果太阳从西方升起，你就可以长生不老。严禁吸烟。今天的温度有多少度？今天的温度有多少度？全体起立！今天好冷啊！今天好冷啊！我正在说谎。6/17/20243一、命题逻辑1 命题8/3/202332 真值 如果一个命题是真的，就说它的真值是T；如果一个命题是假的，就说它的真值是F。T和F统称为命题的真值。也用T代表一个抽象的真命题，用F代表一个抽象的假命题。6/17/202442 真值 如果一个命题是真的，就说它的真值是T；8/33 联结词、l设设P是一个命题，命题是一个命题，命题“P是不对的是不对的”称为称为P的否定，记的否定，记以以P，读作非，读作非P。例例.Q:张三是好人。张三是好人。Q：张三不是好人。：张三不是好人。语义规定语义规定：P是真的当且仅当是真的当且仅当P是假的。是假的。l设P，Q是两个命题，命题“P或者Q”称为P，Q的析取，记以PQ，读作P析取Q。例例.P：今天下雪，：今天下雪，Q：今天刮：今天刮风风，P Q：今天下雪或者刮：今天下雪或者刮风风。语义规定语义规定：P Q是真的当且仅当是真的当且仅当P,Q中至少有一个为真。中至少有一个为真。6/17/202453 联结词、设P是一个命题，命题 l设设P，Q是两个命题，命题是两个命题，命题“P并且并且Q”称为称为P，Q的合的合取，记以取，记以P Q，读作，读作P合取合取Q。例例.P：2 2=5，Q：雪是黑的，：雪是黑的，P Q：2 2=5并且雪是黑的。并且雪是黑的。语义规定语义规定：P Q是真的当且仅当是真的当且仅当P和和Q都是真的。都是真的。l设P，Q是两个命题，命题“如果P，则Q”称为P蕴涵Q，记以PQ。例例.P：f(x)是可微的，是可微的，Q：f(x)是是连续连续的，的，PQ：若若f(x)是可微的，是可微的，则则f(x)是是连续连续的。的。语义语义规定：规定：PQ是假的当且仅当是假的当且仅当P是真的而是真的而Q是假的。是假的。6/17/20246设P，Q是两个命题，命题“P并且Q”称为P，Q的合取，记以l设P，Q是两个命题，命题“P当且仅当Q”称为P等价Q，记以PQ。语义规定：语义规定：PQ是真的当且仅当是真的当且仅当P，Q或者都是真的，或者都是假的。或者都是真的，或者都是假的。例例 P：a2+b2=a2，Q：b=0，PQ：a2+b2=a2当且仅当当且仅当b=0。五种逻辑联结词的五种逻辑联结词的优先级优先级按如下次序递增：按如下次序递增：，例例.符号串符号串 P Q RQ S R 意味着：意味着：(P(Q R)(Q(S)R)6/17/20247设P，Q是两个命题，命题“P当且仅当Q”称为P等价Q，记以4 复合命题复合命题 用联结词将简单命题连接的结果。用联结词将简单命题连接的结果。5 原子原子 命题的抽象。命题的抽象。用大写的英文字母用大写的英文字母P，Q，R，等表示。等表示。6 文字文字 原子或原子的否定。原子或原子的否定。7 子句子句 有限个文字的有限个文字的析取式析取式称为一个称为一个子句。子句。特别，没有文字的子句称为空子句，记为特别，没有文字的子句称为空子句，记为 。只有一个文字的子句称为单元子句。只有一个文字的子句称为单元子句。8 短语短语 有限个文字的有限个文字的合取式合取式称为一个称为一个短语短语。6/17/202484 复合命题8/3/20238复合命题的抽象复合命题的抽象 公式的形成规则公式的形成规则-是如下定义的一个符号串：(1)原子是公式；(2)F、T是公式；(3)若G，H是公式，则(G)，(GH)，(GH)，(GH)，(GH)是公式；(4)所有公式都是有限次使用(1)，(2)，(3)得到的符号串。9 公式6/17/20249复合命题的抽象9 公式8/3/20239设设G是命题公式是命题公式,A1,An是出现在是出现在G中的所有原子。指定中的所有原子。指定A1,An的一组真值的一组真值,则这组真值称为则这组真值称为G的一个解释。的一个解释。l设设G是公式，是公式，I是是G的一个解释，的一个解释，G在在I下的真值记为下的真值记为TI(G)。l例例.G=P Q，设解释，设解释I，I如下：如下：I：I：则则TI(G)=T，TI(G)=F 注意：该例子中写成注意：该例子中写成G=T或或G=F是错误的！是错误的！10 解释解释 P Q T T P Q T F 6/17/202410设G是命题公式,A1,An是出现在G中的所有原子。指定A11 真值表真值表 公式公式G在其所有可能的解释下所取真值在其所有可能的解释下所取真值的表，称为的表，称为G的的真值表真值表。有有n个不同原子的公式，共有个不同原子的公式，共有2n个解释。个解释。12 恒真公式恒真公式 公式公式G称为称为恒真的恒真的(或有效的或有效的)，如果，如果G在在它的所有解释下都是真的它的所有解释下都是真的.6/17/20241111 真值表8/3/20231113 恒假公式恒假公式 公式公式G称为恒假的称为恒假的(或不可满足的或不可满足的)，如果，如果G在它的所有在它的所有解释下都是假的解释下都是假的.14 可满足公式可满足公式 公式公式G称为可满足的，如果它不是恒假的。称为可满足的，如果它不是恒假的。lG是恒真的是恒真的 iff G是恒假的。是恒假的。lG是可满足的是可满足的 iff 至少有一个解释至少有一个解释I，使，使G在在I下为真。下为真。l若若G是恒真的，则是恒真的，则G是可满足的；是可满足的；反之不对。反之不对。l如果公式如果公式G在解释在解释I下是真的，则称下是真的，则称I满足满足G；如果如果G在解释在解释I下是假的，则称下是假的，则称I弄假弄假G。6/17/20241213 恒假公式8/3/202312l例.考虑G1=(PQ)P，G2=(P Q)P，G3=P P。PQG1PQG2PG3FFTFFFFFFTTFTFTFTFTTFFTTTTTT6/17/202413PQG1PQG2PG3FFTFFFFFFTTFTFTFTFT15 判定问题l能否给出一个能否给出一个可行方法可行方法，对任意的公式，判定，对任意的公式，判定其是否是恒真公式。其是否是恒真公式。l命题逻辑可判定？命题逻辑可判定？原因？原因？因为一个命题公式的原子数目有限因为一个命题公式的原子数目有限(n)，从而，从而解释的数目是有限的解释的数目是有限的(2n)，所以命题逻辑的判，所以命题逻辑的判定问题是可解的定问题是可解的(可判定的，可计算的可判定的，可计算的).6/17/20241415 判定问题能否给出一个可行方法，对任意的公式，判定其是否16 公式等价公式等价l称公式称公式G，H是等价的，记以是等价的，记以G=H，如果，如果G，H在其任意解释在其任意解释I下，其真值相同。下，其真值相同。l 公式公式G，H等价等价 iff 公式公式GH恒真。恒真。l 基本等价式基本等价式1)(GH)=(GH)(HG)；2)(GH)=(G H)；3)G G=G，G G=G；(等幂律等幂律)4)G H=H G，G H=H G；(交换律交换律)5)G(H S)=(G H)S，G(H S)=(G H)S；(结合律结合律)6/17/20241516 公式等价称公式G，H是等价的，记以G=H，如果G，H6)G(G H)=G，G(G H)=G；(吸收律吸收律)7)G(H S)=(G H)(G S)，G(H S)=(G H)(G S)；(分配律分配律)8)G F=G，G T=G；(同一律同一律)9)G F=F，G T=T；(零一律零一律)10)(G H)=G H，(G H)=G H。(De Morgan律律)11)G G=T；G G=F （互补律）（互补律）12)G=G （双重否定律）（双重否定律）6/17/2024166)G(GH)=G，G(GH)=G；17 公式的蕴涵公式的蕴涵设设G，H是两个公式。是两个公式。称称H是是G的的逻辑结果逻辑结果(或称或称G蕴涵蕴涵H)，当且仅当对，当且仅当对G，H的任意解释的任意解释I，如果，如果I满足满足G，则，则I也满足也满足H，记作，记作GH。l公式公式G蕴涵公式蕴涵公式H iff 公式公式GH是恒真的。是恒真的。l设设G1,Gn，H是公式。是公式。称称H是是G1,Gn的的逻辑结果逻辑结果(或称或称G1,Gn共同蕴涵共同蕴涵H)，当且，当且仅当仅当(G1 Gn)H。例如，例如，P，PQ共同蕴涵共同蕴涵Q。6/17/20241717 公式的蕴涵设G，H是两个公式。称H是G的逻辑结果(或基本蕴涵式 lP QPlP QQlPP QlQP QlP(PQ)lQ(PQ)l(PQ)P6/17/202418基本蕴涵式 8/3/202318基本蕴涵式 8.(PQ)Q9.P，QP Q10.P，P QQ11.P，PQQ12.Q，PQ P13.PQ，QRPR14.P Q，PR，QRR 6/17/202419基本蕴涵式(PQ)Q8/3/20231918 范式范式l有限个有限个短语的析取式短语的析取式称为称为析取范式析取范式；l有限个有限个子句的合取式子句的合取式称为称为合取范式合取范式。l特别，一个特别，一个文字文字既可称为是一个合取范式，也既可称为是一个合取范式，也可称为是一个析取范式。一个可称为是一个析取范式。一个子句子句，一个，一个短语短语既可看做是合取范式，也可看做是析取范式。既可看做是合取范式，也可看做是析取范式。l例如，例如，P，P Q，P Q，(P Q)(P Q)是析取范式。是析取范式。P，P Q，P Q，(P Q)(P R)是合取范式。是合取范式。6/17/20242018 范式有限个短语的析取式称为析取范式；8/3/20232化范式方法：化范式方法：步步1.使使用用基基本本等等价价式式，将将G中中的的逻逻辑辑联联结结词词，删除。删除。步步2.使用使用(H)=H和摩根律，和摩根律，将将G中所有的否定号中所有的否定号都放在原子之前。都放在原子之前。步步3.反复使用分配律，即可得到等价于反复使用分配律，即可得到等价于G的范的范 式。式。6/17/202421化范式方法：步1.使用基本等价式，将G中的逻辑联结词，19 演绎l设设S是一个命题公式的集合是一个命题公式的集合(前提集合前提集合)。从。从S推推出公式出公式G的的一个演绎一个演绎是公式的一个有限序列：是公式的一个有限序列：G1,G2,Gk 其中，其中，Gi（1i k）或者属于）或者属于S，或者是某些，或者是某些 Gj (j3,23,503等等50个命题。个命题。6/17/202424命题逻辑的缺陷 把问题看成一个个孤立的命题，忽略了问题之8/2 不能描述问题间的逻辑联系不能描述问题间的逻辑联系l例如，逻辑学中著名的三段论：例如，逻辑学中著名的三段论：P：凡人必死：凡人必死Q：张三是人：张三是人R：张三必死：张三必死 l在命题逻辑中：应该有在命题逻辑中：应该有(P Q)R，从而公式，从而公式(P Q)R应该是恒真的。应该是恒真的。l显然该公式不是恒真的，解释显然该公式不是恒真的，解释P，Q，R就能弄就能弄假该公式。假该公式。6/17/2024258/3/202325l原因：命题原因：命题R是和命题是和命题P,Q有关系的，只是这种关有关系的，只是这种关系在命题逻辑中无法表示。系在命题逻辑中无法表示。l因此，需要对命题的成分、结构和命题间的共同因此，需要对命题的成分、结构和命题间的共同特性等作进一步的分析，这正是谓词逻辑所要研特性等作进一步的分析，这正是谓词逻辑所要研究的问题。究的问题。6/17/202426原因：命题R是和命题P,Q有关系的，只是这种关系在命题逻辑l为了表示出这三个命题的内在关系，需要引进谓为了表示出这三个命题的内在关系，需要引进谓词的概念。词的概念。l例如，在前面的例子例如，在前面的例子“张三是人张三是人”中的中的“是人是人”是谓是谓语，称为语，称为谓词谓词，“张三张三”是主语，称为是主语，称为个体个体。6/17/202427为了表示出这三个命题的内在关系，需要引进谓词的概念。8/3/二、谓词逻辑二、谓词逻辑 1 1 谓词谓词谓词谓词可以独立存在的物体称为可以独立存在的物体称为个体个体。如人、学生、桌子、自然数等都可以做个体。在谓词如人、学生、桌子、自然数等都可以做个体。在谓词演算中，个体通常指一个命题里的思维对象。演算中，个体通常指一个命题里的思维对象。设设设设D D是非空个体名称集合，定义在是非空个体名称集合，定义在是非空个体名称集合，定义在是非空个体名称集合，定义在D Dn n上取值于上取值于上取值于上取值于TT，FF上的上的上的上的n n元函数，称为元函数，称为元函数，称为元函数，称为n n元命题函数或元命题函数或元命题函数或元命题函数或n n元元元元谓词谓词谓词谓词。其中。其中。其中。其中D Dn n表示集合表示集合表示集合表示集合D D的的的的n n次笛卡尔乘积。次笛卡尔乘积。次笛卡尔乘积。次笛卡尔乘积。一般地，一元谓词描述个体的性质，二元或多元谓词一般地，一元谓词描述个体的性质，二元或多元谓词一般地，一元谓词描述个体的性质，二元或多元谓词一般地，一元谓词描述个体的性质，二元或多元谓词描述两个或多个个体间的关系。描述两个或多个个体间的关系。描述两个或多个个体间的关系。描述两个或多个个体间的关系。0 0元谓词中无个体，理元谓词中无个体，理元谓词中无个体，理元谓词中无个体，理解为就是命题，这样，谓词逻辑包括命题逻辑。解为就是命题，这样，谓词逻辑包括命题逻辑。解为就是命题，这样，谓词逻辑包括命题逻辑。解为就是命题，这样，谓词逻辑包括命题逻辑。6/17/202428二、谓词逻辑 1 谓词8/3/202328例.D=2,3,4l设设P(x)：x大于大于3，则，则P(x)为一元谓词。为一元谓词。指定元素指定元素-命题：命题：P(2)=F,P(3)=F,P(4)=Tl设设P(x,y)：x大于大于y,则则P(x,y)为二元谓词。为二元谓词。指定元素指定元素-命题：命题：P(2,3)=F,P(4,2)=Tl设设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)=F6/17/202429例.D=2,3,48/3/202329例.l用谓词的概念可将三段论做如下的符号化：用谓词的概念可将三段论做如下的符号化：令令H(x)表示表示“x是人是人”，M(x)表示表示“x必死必死”。l 则三段论的三个命题表示如下：则三段论的三个命题表示如下：P：H(x)M(x)Q：H(张三张三)R：M(张三张三)6/17/202430例.用谓词的概念可将三段论做如下的符号化：令H(x)表示l若想得到若想得到“命题命题”P的否定的否定“命题命题”，应该就是，应该就是“命命题题”P。但是，。但是，P=(H(x)M(x)=(H(x)M(x)=H(x)M(x)亦即，亦即，“命题命题”P的否定的否定“命题命题”是是“所有人都不死所有人都不死”。这和人们日常对命题这和人们日常对命题“所有人都必死所有人都必死”的否定的理的否定的理解，相差得实在太远了解，相差得实在太远了.6/17/202431若想得到“命题”P的否定“命题”，应该就是“命题”Pl原因命题原因命题P的确切意思应该是：的确切意思应该是：“对任意对任意x，如果如果x是人，则是人，则x必死必死”。但是但是H(x)M(x)中并没有确切的表示出中并没有确切的表示出“对任意对任意x”这个意思，亦这个意思，亦即即H(x)M(x)不是一个命题。不是一个命题。因此，在谓词逻因此，在谓词逻辑中除引进谓词外，还需要引进辑中除引进谓词外，还需要引进“对任意对任意x”这个这个语句，及其对偶的语句语句，及其对偶的语句“存在一个存在一个x”。6/17/202432原因命题P的确切意思应该是：“对任意x，如果x是人，则2 量词l定义定义 语句语句“对任意对任意x”称为全称量词，记以称为全称量词，记以 x；语句语句“存在一个存在一个x”称为存在量词，记以称为存在量词，记以 x。l这时，命题这时，命题P就可确切地符号化如下：就可确切地符号化如下：x(H(x)M(x)命题命题P的否定命题为：的否定命题为：P=(x(H(x)M(x)=x(H(x)M(x)亦即亦即“有一个人是不死的有一个人是不死的”。这个命题确实是。这个命题确实是“所有人都所有人都要死要死”的否定。的否定。l三段论的三个命题，在谓词逻辑中是如下这样表示的：三段论的三个命题，在谓词逻辑中是如下这样表示的：P：x(H(x)M(x)Q：H(张三张三)R：M(张三张三)6/17/2024332 量词定义 语句“对任意x”称为全称量词，记以x；l量词的语义规定量词的语义规定 xG(x)取取T值值对任意对任意x D，G(x)都取都取T值；值；xG(x)取取T值值至少至少有一个有一个x0 D，使，使G(x0)取取T值值 语义上，当语义上，当D=x0,x1,是可数集合时，是可数集合时，xG(x)等价于等价于G(x0)G(x1)xG(x)等价于等价于G(x0)G(x1)6/17/202434量词的语义规定8/3/202334l例例.将下列命题符号化：将下列命题符号化：)一切事物都是发展变化的一切事物都是发展变化的 x F(x)其中其中F(x)：x是发展变化的是发展变化的)存在着会说话的机器人存在着会说话的机器人 x(F(x)G(x)其中其中F(x)：x会说话会说话 G(x):x是机器人是机器人如果没有明确给出个体域，则认为个体域如果没有明确给出个体域，则认为个体域为一切事物。为一切事物。6/17/202435例.将下列命题符号化：8/3/2023353)每个计算机学院的学生都学离散数学。每个计算机学院的学生都学离散数学。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/17/2024363)每个计算机学院的学生都学离散数学。8/3/2023365)每个人都会犯错误每个人都会犯错误R(x):x是人是人P(x):x会犯错误会犯错误 x(R(x)P(x)6/17/2024375)每个人都会犯错误8/3/2023373 约束变量、自由变量 在一个由谓词，量词，逻辑联结词，括号组成的有意义在一个由谓词，量词，逻辑联结词，括号组成的有意义在一个由谓词，量词，逻辑联结词，括号组成的有意义在一个由谓词，量词，逻辑联结词，括号组成的有意义的符号串的符号串的符号串的符号串(公式公式公式公式)中，称变量的出现是约束的，当且仅当中，称变量的出现是约束的，当且仅当中，称变量的出现是约束的，当且仅当中，称变量的出现是约束的，当且仅当它出现在使用这个变量的量词范围之内；称变量的出现它出现在使用这个变量的量词范围之内；称变量的出现它出现在使用这个变量的量词范围之内；称变量的出现它出现在使用这个变量的量词范围之内；称变量的出现是自由的，当且仅当这个出现不是约束的。是自由的，当且仅当这个出现不是约束的。是自由的，当且仅当这个出现不是约束的。是自由的，当且仅当这个出现不是约束的。称变量是约束的，如果至少有一个它的出现是约束的；称变量是约束的，如果至少有一个它的出现是约束的；称变量是约束的，如果至少有一个它的出现是约束的；称变量是约束的，如果至少有一个它的出现是约束的；称变量是自由的，如果至少有一个它的出现是自由的。称变量是自由的，如果至少有一个它的出现是自由的。称变量是自由的，如果至少有一个它的出现是自由的。称变量是自由的，如果至少有一个它的出现是自由的。例如，例如，例如，例如，x(P(xx(P(x，y)y)Q(xQ(x，z)z)R(x)R(x)从左向右算起，变量从左向右算起，变量从左向右算起，变量从左向右算起，变量x x的第一，第二次出现是约束的第一，第二次出现是约束的第一，第二次出现是约束的第一，第二次出现是约束的，第三次出现是自由的；变量的，第三次出现是自由的；变量的，第三次出现是自由的；变量的，第三次出现是自由的；变量y y，z z的出现是自由的的出现是自由的的出现是自由的的出现是自由的。x x x x既是约束变量，又是自由变量；既是约束变量，又是自由变量；既是约束变量，又是自由变量；既是约束变量，又是自由变量；y y y y，z z z z只是自由变量。只是自由变量。只是自由变量。只是自由变量。6/17/2024383 约束变量、自由变量 在一个由谓词，量词，逻辑联结词，括4 约束变量的改名规则改名规则的理论依据改名规则的理论依据l xP(x)与与 yP(y)都是表示个体域都是表示个体域D中的中的“每个个体都具每个个体都具有性质有性质P”，所以可以把，所以可以把x改名为改名为y，即把，即把 xP(x)改成为改成为 yP(y)。l xP(x)与与 yP(y)都是表示个体域都是表示个体域D中的中的“某个个体具有某个个体具有性质性质P”，所以也可以把，所以也可以把x改名为改名为y，即把，即把 xP(x)改成为改成为 yP(y)。亦即，谓词逻辑中命题的真值，与命题中的约束变量的亦即，谓词逻辑中命题的真值，与命题中的约束变量的记法无关。这就引出了谓词逻辑中的改名规则。记法无关。这就引出了谓词逻辑中的改名规则。6/17/2024394 约束变量的改名规则改名规则的理论依据8/3/202339l改名规则：在由谓词，量词，逻辑联结词，括改名规则：在由谓词，量词，逻辑联结词，括号组成的有意义的符号串号组成的有意义的符号串(公式公式)中，可将其中中，可将其中出现的约束变量改为另一个约束变量，这种改出现的约束变量改为另一个约束变量，这种改名必须在量词作用区域内各处以及该量词符号名必须在量词作用区域内各处以及该量词符号中实行，并且改成的新约束变量要有别于改名中实行，并且改成的新约束变量要有别于改名区域中的所有其它变量。区域中的所有其它变量。l显然改名规则不改变原符号串的真值。显然改名规则不改变原符号串的真值。6/17/202440改名规则：在由谓词，量词，逻辑联结词，括号组成的有意义的符号例:对于对于 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/17/202441例:对于x(P(x，y)Q(x，z)R(x,v5 封闭公式公式中无自由变量，或将自由变量看做常量。公式中无自由变量，或将自由变量看做常量。(公式中每个变量的出现都是约束的）公式中每个变量的出现都是约束的）6/17/2024425 封闭公式公式中无自由变量，或将自由变量看做常量。8/31)常量符号常量符号：用小写英文字母：用小写英文字母a，b，c，表示，表示，当个体名称集合当个体名称集合D给出时，它可以是给出时，它可以是D中某个中某个元素。元素。2)变量符号变量符号：用小写英文字母：用小写英文字母u，v，w，x，y，z，表示，当个体名称集合表示，当个体名称集合D给出时，给出时，D中中任任意元素意元素可代入变量符号。可代入变量符号。6 谓词逻辑形式化中使用的四种符号谓词逻辑形式化中使用的四种符号6/17/2024431)常量符号：用小写英文字母a，b，c，表示，当个体名称3)函数符号函数符号：用小写英文字母：用小写英文字母f，g，表示，当表示，当个体名称集合个体名称集合D给出时，给出时，n元函数符号元函数符号f(x1，xn)可以是可以是Dn到到D的任意一个映射。的任意一个映射。4)谓词符号谓词符号：用大写英文字母：用大写英文字母P，Q，R，表表示，当个体名称集合示，当个体名称集合D给出时，给出时，n元谓词符号元谓词符号P(x1，xn)可以是可以是Dn上的任意一个谓词。上的任意一个谓词。6/17/2024443)函数符号：用小写英文字母f，g，表示，当个体名称集合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,t,tn)是原子。是原子。6/17/2024457 项8/3/2023459 公式公式谓词逻辑中的公式，被递归定义如下：谓词逻辑中的公式，被递归定义如下：谓词逻辑中的公式，被递归定义如下：谓词逻辑中的公式，被递归定义如下：1)1)原子是公式；原子是公式；原子是公式；原子是公式；2)2)若若若若GG，HH是公式，则是公式，则是公式，则是公式，则(G)G)，(G(G H)H)，(G (G H)H)，(G(GH)H)，(G(GH)H)是公式；是公式；是公式；是公式；3)3)若若若若GG是公式，是公式，是公式，是公式，x x是是是是GG中的自由变量，则中的自由变量，则中的自由变量，则中的自由变量，则 xGxG，xGxG是公式；是公式；是公式；是公式；4)4)所有公式都是有限次使用所有公式都是有限次使用所有公式都是有限次使用所有公式都是有限次使用1)1)3)3)生成的符号串。生成的符号串。生成的符号串。生成的符号串。6/17/2024469 公式谓词逻辑中的公式，被递归定义如下：8/3/2023410 公式的语义解释谓词逻辑中公式谓词逻辑中公式谓词逻辑中公式谓词逻辑中公式GG的一个解释的一个解释的一个解释的一个解释I I，是由非空区域，是由非空区域，是由非空区域，是由非空区域D D和对和对和对和对GG中常量符号，函数符号，谓词符号以下列规则进行中常量符号，函数符号，谓词符号以下列规则进行中常量符号，函数符号，谓词符号以下列规则进行中常量符号，函数符号，谓词符号以下列规则进行的一组指定组成：的一组指定组成：的一组指定组成：的一组指定组成：1.1.对每个常量符号，指定对每个常量符号，指定对每个常量符号，指定对每个常量符号，指定D D中一个元素；中一个元素；中一个元素；中一个元素；2.2.对每个对每个对每个对每个n n元函数符号，指定一个函数，即指元函数符号，指定一个函数，即指元函数符号，指定一个函数，即指元函数符号，指定一个函数，即指定定定定D Dn n到到到到D D的一个映射；的一个映射；的一个映射；的一个映射；3.3.对每个对每个对每个对每个n n元谓词符号，指定一个谓词，即指元谓词符号，指定一个谓词，即指元谓词符号，指定一个谓词，即指元谓词符号，指定一个谓词，即指定定定定D Dn n到到到到TT，FF的一个映射。的一个映射。的一个映射。的一个映射。6/17/20244710 公式的语义解释谓词逻辑中公式G的一个解释I，是由非空区例:1)G=x(P(f(x)Q(x，f(a)2)H=x(P(x)Q(x，a)设解释设解释I：D=2，3 a 2 f(2)f(3)3 2 P(2)P(3)Q(2,2)Q(2,3)Q(3,2)Q(3,3)F T T T F T6/17/202448例:1)G=x(P(f(x)Q(x，f(a)2例:lTI(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)=(T T)(F T)=TlTI(H)=TI(P(2)Q(2，2)P(3)Q(3，2)=F T T F=F6/17/202449例:TI(G)=TI(P(f(2)Q(2，f(2)11 谓词公式的恒真、恒假、可满足l公式公式G称为可满足的，如果存在解释称为可满足的，如果存在解释I，使，使G在在I下取下取 T值，简称值，简称I满足满足G。若若I不满足不满足G，则简称，则简称I弄假弄假G。l公式公式G称为是恒假的称为是恒假的(或不可满足的或不可满足的)，如果不，如果不存在解释存在解释I满足满足G。l公式公式G称为恒真的，如果称为恒真的，如果G的所有解释的所有解释I都满足都满足G。6/17/20245011 谓词公式的恒真、恒假、可满足公式G称为可满足的，如果存12 谓词逻辑的判定问题l谓词逻辑中公式恒真、恒假性的判断异常困难。谓词逻辑中公式恒真、恒假性的判断异常困难。原因？原因？谓词逻辑中的恒真谓词逻辑中的恒真(恒假恒假)公式，要求所有解释公式，要求所有解释I都满足都满足(弄弄假假)该公式。该公式。而解释而解释I依赖于一个非空集合依赖于一个非空集合D。由于集合由于集合D可以是无穷集合，而集合可以是无穷集合，而集合D的的“数目数目”也可能是也可能是无穷多个。无穷多个。因此，所谓公式的因此，所谓公式的“所有所有”解释，实际上是无法考虑的。解释，实际上是无法考虑的。l1936年年Church和和Turing分别独立地证明了：对于谓词分别独立地证明了：对于谓词逻辑，判定问题是不可解的。逻辑，判定问题是不可解的。6/17/20245112 谓词逻辑的判定问题谓词逻辑中公式恒真、恒假性的判断异常l谓词逻辑是半可判定的：谓词逻辑是半可判定的：如果谓词逻辑中的公式是恒真的，则有算法在如果谓词逻辑中的公式是恒真的，则有算法在有限步之内检验出这个公式的恒真性。如果该有限步之内检验出这个公式的恒真性。如果该公式不是恒真的公式不是恒真的(当然也不是恒假的当然也不是恒假的)，则无法，则无法在有限步内判定这个事实。在有限步内判定这个事实。6/17/202452谓词逻辑是半可判定的：8/3/20235213 等价l公式公式G，H称为等价，记以称为等价，记以G=H，如果公式，如果公式GH是恒真的。是恒真的。l公式公式G，H等价的充要条件是：对等价的充要条件是：对G，H的任意的任意解释解释I，G，H在在I下的真值相同。下的真值相同。l因为对任意公式因为对任意公式G，H，在解释，在解释I下，下，G，H就就是两个命题，所以命题逻辑中给出的基本等价是两个命题，所以命题逻辑中给出的基本等价式，在谓词逻辑中仍然成立。式，在谓词逻辑中仍然成立。6/17/20245313 等价公式G，H称为等价，记以G=H，如果公式GH是恒l l设设设设GG，H H是公式，称是公式，称是公式，称是公式，称GG蕴涵蕴涵蕴涵蕴涵H H，或，或，或，或H H是是是是GG的逻辑结果，如的逻辑结果，如的逻辑结果，如的逻辑结果，如果公式果公式果公式果公式GGH H是恒真的，并记以是恒真的，并记以是恒真的，并记以是恒真的，并记以GGH H。l l对任意两个公式对任意两个公式对任意两个公式对任意两个公式GG，H H，GG蕴涵蕴涵蕴涵蕴涵H H的充要条件是：对任的充要条件是：对任的充要条件是：对任的充要条件是：对任意解释意解释意解释意解释I I，若，若，若，若I I满足满足满足满足GG，则，则，则，则I I必满足必满足必满足必满足H H。l l同样，命题逻辑中的基本蕴涵式仍成立。同样，命题逻辑中的基本蕴涵式仍成立。同样，命题逻辑中的基本蕴涵式仍成立。同样，命题逻辑中的基本蕴涵式仍成立。14 蕴涵6/17/202454设G，H是公式，称G蕴涵H，或H是G的逻辑结果，如果公式G基本基本蕴涵式：涵式：(1)(PP)P(2)P(PQ)(3)(PQ)(QP)(4)(QR)(PQ)(PR)(5)xP(x)P(y)(6)P(y)xP(x)(7)x P(x)xP(x)(8)x P(x)x Q(x)x(P(x)Q(x)(9)x(P(x)Q(x)xP(x)xQ(x)(10)x(P(x)Q(x)x P(x)x Q(x)(11)x(P(x)Q(x)x P(x)x Q(x)6/17/202455基本蕴涵式：(PP)P8/3/202355l例例.设设G=x(A(x)B(x)，H=x A(x)x B(x)证明：证明：GH证明：设证明：设I是满足是满足G的任意一个解释。的任意一个解释。若若TI(x A(x)=F,则则TI(xA(x)xB(x)=T;若若TI(x A(x)=T,则在则在I下对任意下对任意x D，有，有TI(A(x)=T，又由又由TI(x(A(x)B(x)=T知，对知，对任意任意x D，TI(A(x)B(x)=T，故，故TI(B(x)=T，即，即，TI(x(B(x)=T，因此，因此，TI(xA(x)xB(x)=T。6/17/202456例.设G=x(A(x)B(x)，8/3/202356G，H不等价。不等价。举反例：简单扼要、击中要害举反例：简单扼要、击中要害lI:D=2，3 A(2)A(3)B(2)B(3)T F F FTI(G)=FTI(H)=TG=x(A(x)B(x)，H=x A(x)x B(x)？H G6/17/202457G，H不等价。G=x(A(x)B(x)，H=x58设在一个含有凹室设在一个含有凹室(alcove)(alcove)的房间内，有桌子的房间内，有桌子A A和书架和书架B B，一个机器人，一个机器人(robot)(robot)和和 一叠书一叠书(book)(book)。现在要求机器人。现在要求机器人(robot)(robot)从凹室出发，把从凹室出发，把桌子桌子A A上的书搬到上的书搬到B B处书架上，完成任务后回到凹室。请用谓词逻辑描处书架上，完成任务后回到凹室。请用谓词逻辑描述机器人完成这一工作的全过程。述机器人完成这一工作的全过程。谓词逻辑知识表示的例子6/17/20245858设在一个含有凹室(alcove)的房间内，有桌子A和书架59谓词逻辑知识表示的例子解解解解：为为了了能能够够描描述述这这个个机机器器人人世世界界的的有有关关环环境境和和状状态态变变迁迁，要要求求必必须须先先定定义义谓谓词词。注注意意这这里里需需要要定定义义两两类类谓谓词词：一一类类用用来来描描述述环环境境状状态态，另一类谓词用来表示机器人的操作。另一类谓词用来表示机器人的操作。首先定义描述环境状态的谓词。首先定义描述环境状态的谓词。TABLE(x)TABLE(x)：x x是桌子，是桌子，x x的个体域：的个体域：a a；BOOKCASE(z)BOOKCASE(z)：z z是书架，是书架，z z的个体域：的个体域：b b；EMPTY(y)EMPTY(y)：y y手中是空的，手中是空的，y y的个体域：的个体域：robot robot；HOLDS(yHOLDS(y，u)u)：y y手中拿着手中拿着u u，u u的个体域：的个体域：books books；AT(yAT(y，w)w)：y y在在w w处，处，w w的个体域：的个体域：a a，b b，alcove alcove；ON(uON(u，x)x)：u u被放在被放在x x之上；之上；CLEAR(v)CLEAR(v)：v v上上(中中)是空的，是空的，v v的个体域：的个体域：aa，b b.6/17/20245959谓词逻辑知识表示的例子解：为了能够描述这个机器人世界的60谓词逻辑知识表示的例子解：解：解：解：使用谓词以及联结词、量词等来表示环境状态。使用谓词以及联结词、量词等来表示环境状态。这样，问题的初始状态可表示为：这样，问题的初始状态可表示为：S S0 0：AT(robot,alcove)EMPTY(robot)AT(robot,alcove)EMPTY(robot)ON(books,a)CLEAR(b)ON(books,a)CLEAR(b)TABLE(a)BOOKCASE(b)TABLE(a)BOOKCASE(b)要求达到的目标状态为：要求达到的目标状态为：S Sg g：AT(robot,alcove)EMPTY(robot)AT(robot,alcove)EMPTY(robot)ON(books,b)CLEAR(a)ON(books,b)CLEAR(a)TABLE(a)BOOKCASE(b)TABLE(a)BOOKCASE(b)6/17/20246060谓词逻辑知识表示的例子解：使用谓词以及联结词、量词等来61谓词逻辑知识表示的例子解：解：解：解：从初始状态到达目标状态的变迁，必须由机器人从初始状态到达目标状态的变迁，必须由机器人一步一步地执行相应的操作序列，得以逐步实现。因此，一步一步地执行相应的操作序列，得以逐步实现。因此，必须要定义操作类谓词。仔细加以分析，必要的操作谓词必须要定义操作类谓词。仔细加以分析，必要的操作谓词共有三类。共有三类。GOTO(x,w)GOTO(x,w)：机器人从：机器人从x x走到走到w w处；处；PICK-UP(x)PICK-UP(x)：机器人在：机器人在x x处拿起书；处拿起书；SET-DOWN(w)SET-DOWN(w)：机器人在：机器人在w w处放下书。处放下书。一般说来，如果定义谓词太多，将造成信息冗余，增一般说来，如果定义谓词太多，将造成信息冗余，增加了问题的复杂度；如果定义谓词太少，就不够用。因此，加了问题的复杂度；如果定义谓词太少，就不够用。因此，定义的谓词性质与数量要合适。定义的谓词性质与数量要合适。6/17/20246161谓词逻辑知识表示的例子解：从初始状态到达目标状态的变迁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)GOTO(alcove,a)PICK-UPPICK-UP（a a）6/17/20246262谓词逻辑知识表示的例子解：按照行动规划，仔细选择操作，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)（解毕）GOTOGOTO（b,alcoveb,alcove）GOTOGOTO（a,ba,b）SET-DOWNSET-DOWN（b b）6/17/20246363谓词逻辑知识表示的例子解：AT(robot,64谓词逻辑知识表示的例子解解解解：这样这样,得到目标为得到目标为AT(robot,alcove)EMPTY(robot)ON(books,b)CLEAR(a)TABLE(a)BOOKCASE(b)这里顺便指出，若机器人智商不高，这个任务过程会这里顺便指出，若机器人智商不高，这个任务过程会产生许多冗余。比如，机器人拿着书，找不到产生许多冗余。比如，机器人拿着书，找不到b b处，无所处，无所适从而又扛回来了；或者适从而又扛回来了；或者等。可见，实际的机器人智等。可见，实际的机器人智能控制要更加复杂得多，虽然有时也很有趣。能控制要更加复杂得多，虽然有时也很有趣。6/17/20246464谓词逻辑知识表示的例子解：这样,得到目标为8/3/202例例 将自然数公理符号化：将自然数公理符号化：A1：每一个数，有且仅有一个直接后继者；：每一个数，有且仅有一个直接后继者；A2：没有一个数使：没有一个数使0是直接后继者；是直接后继者；A3：对任意异于：对任意异于0的数，有且仅有一个直接先行者。的数，有且仅有一个直接先行者。解：令解：令f(x)表示表示x的直接后继者的直接后继者g(x)表示表示x的直接先行者的直接先行者E(x,y)表示表示x等于等于y谓词逻辑知识表示的例子6/17/202465例 将自然数公理符号化：谓词逻辑知识表示的例子8/3/20于是将上述三个公理符号化如下：于是将上述三个公理符号化如下：A1：每一个数，有且仅有一个直接后继者：每一个数，有且仅有一个直接后继者 x y(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/17/202466于是将上述三个公理符号化如下：8/3/202366解：令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/17/202467解：令P(x)表示x是病人 D(剩下的任务就是调用某一过程证明A1A2B是一阶逻辑中的恒真公式，即B是A1、A2的逻辑结果。我们把它留到下一章中讨论。6/17/2024688/3/20236869 逻辑知识表示的主要特点是建立在某种形式逻辑的基础上，并利用了逻辑方法研究推理的规律，即条件与结论之间的蕴涵关系。逻辑表示法的主要优点如下：（1 1）自然）自然 一阶谓词逻辑是一种接近于自然语言的形式语言系统，谓词逻辑一阶谓词逻辑是一种接近于自然语言的形式语言系统，谓词逻辑表示法接近于人们对问题的直观理解，易于被人们接受。表示法接近于人们对问题的直观理解，易于被人们接受。（2 2）明确）明确 逻辑表示法对如何由简单陈述句构造复杂陈述句的方法有明确规逻辑表示法对如何由简单陈述句构造复杂陈述句的方法有明确规定，如联结词、量词的用法与含义等。对于用逻辑表示法表示的知识，定，如联结词、量词的用法与含义等。对于用逻辑表示法表示的知识，人们都可以按照一种标准的方法去解释它，因此用这种方法表示的知人们都可以按照一种标准的方法去解释它，因此用这种方法表示的知识明确、易于理解。识明确、易于理解。谓词逻辑表示的特性谓词逻辑表示的特性6/17/20246969 逻辑知识表示的主要特点是建立在某种形式逻辑的基础70（3 3）精确）精确 谓词逻辑是一种二值逻辑，其谓词公式的真值只有谓词逻辑是一种二值逻辑，其谓词公式的真值只有“真真”与与“假假”，因此可用来表示精确知识，并可保证经演绎推理所得结论的精，因此可用来表示精确知识，并可保证经演绎推理所得结论的精确性。确性。（4 4）灵活）灵活 逻辑表示法把知识和处理知识的程序有效地分开。在使用这逻辑表示法把知识和处理知识的程序有效地分开。在使用这种方法表示知识时，无须考虑程序中处理知识的细节。种方法表示知识时，无须考虑程序中处理知识的细节。（5 5）模块化）模块化 在逻辑表示法中，各条知识都是相对独立的，它们之间不直在逻辑表示法中，各条知识都是相对独立的，它们之间不直接发生联系。因此添加、删除、修改知识的工作比较容易进行。接发生联系。因此添加、删除、修改知识的工作比较容易进行。谓词逻辑表示的特性谓词逻辑表示的特性6/17/20247070（3）精确 谓词逻辑是一种二值逻辑，其谓词公式的71 逻辑表示法也存在一些不足，其主要缺点如下：（1）知识表示能力差 逻辑表示法只能表示确定性知识，而不能表示非确定性知识，如不精确、模糊性知识。实际上，人类的大部分知识都不同程度地具有某种不确定性，这就使得它表示知识的范围和能力受到了一定的限制。另外，逻辑表示法还难以表示过程性知识和启发性知识。（2）知识库管理困难 逻辑表示法缺乏知识的组织原则，利用这种表示法所形成的知识库管理比较困难。（3）存在组合爆炸 由于逻辑表示法难以表示启发性知识，因此在推理过程中只能盲目地使用推理规则。这样，当系统知识量较大时，容易发生组合爆炸。（4）系统效率低 逻辑表示法的推理过程是根据形式逻辑进行的。它把推理演算与知识含义截然分开，抛弃了表达内容中所含有的语义信息，往往使推理过程冗长，降低了系统效率。谓词逻辑表示的特性谓词逻辑表示的特性6/17/20247171 逻辑表示法也存在一些不足，其主要缺点如下：（1）知识15 前束范式 谓词逻辑中公式谓词逻辑中公式G称为称为前束范式前束范式，如果，如果G有如下有如下形状：形状：Q1x1QnxnM 其中其中 Qixi或者是或者是 xi，或者是，或者是 xi，i=1,n，M是不含量词的公式，是不含量词的公式，Q1x1Qnxn称为称为首标首标，M称为称为母式母式。例如，例如，x y z(P(x，y)Q(x，z)x y zP(x，y，z)6/17/20247215 前束范式 谓词逻辑中公式G称为前束范式，如果G有如l对任意谓词公式，量词是不能随便提前的。对任意谓词公式，量词是不能随便提前的。？xP(x)P(a)=x(P(x)P(a)？xP(x)P(a)=x(P(x)P(a)6/17/202473对任意谓词公式，量词是不能随便提前的。8/3/202373l 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/17/202474xP(x)P(a)是恒真公式.8/3/202374而而 x(P(x)P(a)不是恒真公式。不是恒真公