人工智能第五章精.ppt

《人工智能第五章精.ppt》由会员分享，可在线阅读，更多相关《人工智能第五章精.ppt（99页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、人工智能第五章2/10/20231第1页，本讲稿共99页第五章第五章 谓词演算（复习）谓词演算（复习）l数理逻辑思想的起源：数理逻辑思想的起源：Leibnitz之梦之梦 产生的历史：产生的历史：Boole的工作、的工作、Frege的工作的工作 发展的现实：计算机学科的基础（软件到硬件）发展的现实：计算机学科的基础（软件到硬件）古典数理逻辑主要包括两部分：命题逻辑和谓词逻辑。古典数理逻辑主要包括两部分：命题逻辑和谓词逻辑。命题逻辑又是谓词逻辑的一种简单情形。命题逻辑又是谓词逻辑的一种简单情形。l逻辑研究的基本内容逻辑研究的基本内容 语法语法 语言部分：基本符号集、公式形成规则语言部分：基本符号集

2、、公式形成规则 推理部分：公理集、推理规则推理部分：公理集、推理规则 语义语义 语法和语义之间的关系：语法和语义之间的关系：可靠性、完备性可靠性、完备性l基本问题基本问题 逻辑表示下的判定问题逻辑表示下的判定问题2/10/20232第2页，本讲稿共99页一、命题逻辑一、命题逻辑1 命题命题一句有真假意义的话。用大写英文字母P，Q，P1，P2，表示。例：上海是中国最大的城市。上海是中国最大的城市。今天是星期日。今天是星期日。所有素数都是奇数。所有素数都是奇数。1+1=2。我不会解答这道题。我不会解答这道题。别的星球上有生物。别的星球上有生物。长春今天下雪。长春今天下雪。如果太阳从西方升起，你就可

3、以长生不老。如果太阳从西方升起，你就可以长生不老。严禁吸烟。今天的温度有多少度？今天的温度有多少度？全体起立！今天好冷啊！今天好冷啊！我正在说谎。2/10/20233第3页，本讲稿共99页2真值如果一个命题是真的，就说它的真值是T；如果一个命题是假的，就说它的真值是F。T和F统称为命题的真值。也用T代表一个抽象的真命题，用F代表一个抽象的假命题。2/10/20234第4页，本讲稿共99页3联结词、l设设P是一个命题，命题是一个命题，命题“P是不对的是不对的”称为称为P的否定，记以的否定，记以P，读作非，读作非P。例例.Q:张三是好人。张三是好人。Q：张三不是好人。：张三不是好人。语义规定语义规

4、定：P是真的当且仅当是真的当且仅当P是假的。是假的。l设P，Q是两个命题，命题“P或者Q”称为P，Q的析取，记以PQ，读作P析取Q。例例.P：今天下雪，：今天下雪，Q：今天刮：今天刮风，P Q：今天下雪或者刮：今天下雪或者刮风。语义规定语义规定：P Q是真的当且仅当是真的当且仅当P,Q中至少有一个为真。中至少有一个为真。2/10/20235第5页，本讲稿共99页l设设P，Q是两个命题，命题是两个命题，命题“P并且并且Q”称为称为P，Q的合取，记的合取，记以以P Q，读作，读作P合取合取Q。例例.P：2 2=5，Q：雪是黑的，：雪是黑的，P Q：2 2=5并且雪是黑的。并且雪是黑的。语义规定语义

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是假的。是假的。2/10/20236第6页，本讲稿共99页l设P，Q是两个命题，命题“P当且仅当Q”称为P等价Q，记以PQ。语义规定：语义规定：PQ是真的当且仅当是真的当且仅当P，Q或者都是真的，或者都是假的。或者都是真的，或者都是假的。例例 P：a2+b2=a2

6、，Q：b=0，PQ：a2+b2=a2当且仅当当且仅当b=0。五种逻辑联结词的五种逻辑联结词的优先级优先级按如下次序递增：按如下次序递增：，例例.符号串符号串 P Q RQ S R 意味着：意味着：(P(Q R)(Q(S)R)2/10/20237第7页，本讲稿共99页4 复合命题复合命题 用联结词将简单命题连接的结果。用联结词将简单命题连接的结果。5 原子原子 命题的抽象。命题的抽象。用大写的英文字母用大写的英文字母P，Q，R，等表示。等表示。6 文字文字 原子或原子的否定。原子或原子的否定。7 子句子句 有限个文字的有限个文字的析取式析取式称为一个称为一个子句。子句。特别，没有文字的子句称为空

7、子句，记为特别，没有文字的子句称为空子句，记为 。只有一个文字的子句称为单元子句。只有一个文字的子句称为单元子句。8 短语短语 有限个文字的有限个文字的合取式合取式称为一个称为一个短语短语。2/10/20238第8页，本讲稿共99页复合命题的抽象复合命题的抽象 公式的形成规则公式的形成规则-是如下定义的一个符号串：(1)原子是公式；(2)F、T是公式；(3)若G，H是公式，则(G)，(GH)，(GH)，(GH)，(GH)是公式；(4)所有公式都是有限次使用(1)，(2)，(3)得到的符号串。9公式2/10/20239第9页，本讲稿共99页设设G是命题公式是命题公式,A1,An是出现在是出现在G

8、中的所有原子。指定中的所有原子。指定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 2/10/202310第10页，本讲稿共99页11 真值表真值表 公式公式G在其所有可能的解释下所取真值的在其所有可能的解释下所取真值的表，称为表，称为G的的真值

9、表真值表。有有n个不同原子的公式，共有个不同原子的公式，共有2n个解释。个解释。12 恒真公式恒真公式 公式公式G称为称为恒真的恒真的(或有效的或有效的)，如果，如果G在它在它的所有解释下都是真的的所有解释下都是真的.2/10/202311第11页，本讲稿共99页13 恒假公式恒假公式 公式公式G称为恒假的称为恒假的(或不可满足的或不可满足的)，如果，如果G在它的所有解释下在它的所有解释下都是假的都是假的.14 可满足公式可满足公式 公式公式G称为可满足的，如果它不是恒假的。称为可满足的，如果它不是恒假的。lG是恒真的是恒真的 iff G是恒假的。是恒假的。lG是可满足的是可满足的 iff 至

10、少有一个解释至少有一个解释I，使，使G在在I下为真。下为真。l若若G是恒真的，则是恒真的，则G是可满足的；是可满足的；反之不对。反之不对。l如果公式如果公式G在解释在解释I下是真的，则称下是真的，则称I满足满足G；如果如果G在解释在解释I下是假的，则称下是假的，则称I弄假弄假G。2/10/202312第12页，本讲稿共99页l例.考虑G1=(PQ)P，G2=(PQ)P，G3=PP。PQG1PQG2PG3FFTFFFFFFTTFTFTFTFTTFFTTTTTT2/10/202313第13页，本讲稿共99页15 判定问题l能否给出一个能否给出一个可行方法可行方法，对任意的公式，判定，对任意的公式，

11、判定其是否是恒真公式。其是否是恒真公式。l命题逻辑可判定？命题逻辑可判定？原因？原因？因为一个命题公式的原子数目有限因为一个命题公式的原子数目有限(n)，从而，从而解释的数目是有限的解释的数目是有限的(2n)，所以命题逻辑的判，所以命题逻辑的判定问题是可解的定问题是可解的(可判定的，可计算的可判定的，可计算的).2/10/202314第14页，本讲稿共99页16 公式等价公式等价l称公式称公式G，H是等价的，记以是等价的，记以G=H，如果，如果G，H在其任意解释在其任意解释I下，其真值相同。下，其真值相同。l 公式公式G，H等价等价 iff 公式公式GH恒真。恒真。l 基本等价式基本等价式1)

12、(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；(结合律结合律)2/10/202315第15页，本讲稿共99页6)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

13、 G=F （互补律）（互补律）12)G=G （双重否定律）（双重否定律）2/10/202316第16页，本讲稿共99页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共

14、同蕴涵共同蕴涵Q。2/10/202317第17页，本讲稿共99页基本蕴涵式 lP QPlP QQlPP QlQP QlP(PQ)lQ(PQ)l(PQ)P2/10/202318第18页，本讲稿共99页基本蕴涵式 8.(PQ)Q9.P，QP Q10.P，P QQ11.P，PQQ12.Q，PQ P13.PQ，QRPR14.P Q，PR，QRR 2/10/202319第19页，本讲稿共99页18 范式范式l有限个有限个短语的析取式短语的析取式称为称为析取范式析取范式；l有限个有限个子句的合取式子句的合取式称为称为合取范式合取范式。l特别，一个特别，一个文字文字既可称为是一个合取范式，也既可称为是一个合

15、取范式，也可称为是一个析取范式。一个可称为是一个析取范式。一个子句子句，一个，一个短语短语既可看做是合取范式，也可看做是析取范式。既可看做是合取范式，也可看做是析取范式。l例如，例如，P，P Q，P Q，(P Q)(P Q)是析取范式。是析取范式。P，P Q，P Q，(P Q)(P R)是合取范式。是合取范式。2/10/202320第20页，本讲稿共99页化范式方法：化范式方法：步步1.使使用用基基本本等等价价式式，将将G中中的的逻逻辑辑联联结结词词，删除。删除。步步2.使用使用(H)=H和摩根律，和摩根律，将将G中所有的否定号中所有的否定号都放在原子之前。都放在原子之前。步步3.反复使用分配

16、律，即可得到等价于反复使用分配律，即可得到等价于G的范的范 式。式。2/10/202321第21页，本讲稿共99页19 演绎l设设S是一个命题公式的集合是一个命题公式的集合(前提集合前提集合)。从。从S推推出公式出公式G的的一个演绎一个演绎是公式的一个有限序列：是公式的一个有限序列：G1,G2,Gk 其中，其中，Gi（1i k）或者属于）或者属于S，或者是某些，或者是某些 Gj (j3,23,503等等50个命题。个命题。2/10/202324第24页，本讲稿共99页2 不能描述问题间的逻辑联系不能描述问题间的逻辑联系l例如，逻辑学中著名的三段论：例如，逻辑学中著名的三段论：P：凡人必死：凡人

17、必死Q：张三是人：张三是人R：张三必死：张三必死 l在命题逻辑中：应该有在命题逻辑中：应该有(P Q)R，从而公式，从而公式(P Q)R应该是恒真的。应该是恒真的。l显然该公式不是恒真的，解释显然该公式不是恒真的，解释P，Q，R就能弄就能弄假该公式。假该公式。2/10/202325第25页，本讲稿共99页l原因：命题原因：命题R是和命题是和命题P,Q有关系的，只是这种关有关系的，只是这种关系在命题逻辑中无法表示。系在命题逻辑中无法表示。l因此，需要对命题的成分、结构和命题间的共同因此，需要对命题的成分、结构和命题间的共同特性等作进一步的分析，这正是谓词逻辑所要研特性等作进一步的分析，这正是谓词

18、逻辑所要研究的问题。究的问题。2/10/202326第26页，本讲稿共99页l为了表示出这三个命题的内在关系，需要引进谓为了表示出这三个命题的内在关系，需要引进谓词的概念。词的概念。l例如，在前面的例子例如，在前面的例子“张三是人张三是人”中的中的“是人是人”是谓语，称为是谓语，称为谓词谓词，“张三张三”是主语，称为是主语，称为个体个体。2/10/202327第27页，本讲稿共99页二、谓词逻辑二、谓词逻辑 1 1 谓词谓词谓词谓词可以独立存在的物体称为可以独立存在的物体称为个体个体。如人、学生、桌子、自然数等都可以做个体。在谓词演算中，个如人、学生、桌子、自然数等都可以做个体。在谓词演算中，

19、个体通常指一个命题里的思维对象。体通常指一个命题里的思维对象。设设设设D D是非空个体名称集合，定义在是非空个体名称集合，定义在是非空个体名称集合，定义在是非空个体名称集合，定义在D Dn n上取值于上取值于上取值于上取值于TT，FF上的上的上的上的n n元函数，称为元函数，称为元函数，称为元函数，称为n n元命题函数或元命题函数或元命题函数或元命题函数或n n元元元元谓词谓词谓词谓词。其中。其中。其中。其中D Dn n表示集合表示集合表示集合表示集合D D的的的的n n次笛卡尔乘积。次笛卡尔乘积。次笛卡尔乘积。次笛卡尔乘积。一般地，一元谓词描述个体的性质，二元或多元谓词描一般地，一元谓词描述

20、个体的性质，二元或多元谓词描一般地，一元谓词描述个体的性质，二元或多元谓词描一般地，一元谓词描述个体的性质，二元或多元谓词描述两个或多个个体间的关系。述两个或多个个体间的关系。述两个或多个个体间的关系。述两个或多个个体间的关系。0 0元谓词中无个体，理解为元谓词中无个体，理解为元谓词中无个体，理解为元谓词中无个体，理解为就是命题，这样，谓词逻辑包括命题逻辑。就是命题，这样，谓词逻辑包括命题逻辑。就是命题，这样，谓词逻辑包括命题逻辑。就是命题，这样，谓词逻辑包括命题逻辑。2/10/202328第28页，本讲稿共99页例.D=2,3,4l设设P(x)：x大于大于3，则，则P(x)为一元谓词。为一元

21、谓词。指定元素指定元素-命题：命题：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)=F2/10/202329第29页，本讲稿共99页例.l用谓词的概念可将三段论做如下的符号化：用谓词的概念可将三段论做如下的符号化：令令H(x)表示表示“x是人是人”，M(x)表

22、示表示“x必死必死”。l 则三段论的三个命题表示如下：则三段论的三个命题表示如下：P：H(x)M(x)Q：H(张三张三)R：M(张三张三)2/10/202330第30页，本讲稿共99页l若想得到若想得到“命题命题”P的否定的否定“命题命题”，应该就是，应该就是“命题命题”P。但是，。但是，P=(H(x)M(x)=(H(x)M(x)=H(x)M(x)亦即，亦即，“命题命题”P的否定的否定“命题命题”是是“所有人都所有人都不死不死”。这和人们日常对命题。这和人们日常对命题“所有人都必死所有人都必死”的否定的理解，相差得实在太远了的否定的理解，相差得实在太远了.2/10/202331第31页，本讲稿

23、共99页l原因命题原因命题P的确切意思应该是：的确切意思应该是：“对任意对任意x，如果，如果x是人，则是人，则x必死必死”。但是但是H(x)M(x)中并没有确切的表示出中并没有确切的表示出“对任意对任意x”这个意思，这个意思，亦即亦即H(x)M(x)不是一个命题。不是一个命题。因此，在谓词因此，在谓词逻辑中除引进谓词外，还需要引进逻辑中除引进谓词外，还需要引进“对任意对任意x”这个语句，及其对偶的语句这个语句，及其对偶的语句“存在一个存在一个x”。2/10/202332第32页，本讲稿共99页2 量词l定义定义 语句语句“对任意对任意x”称为全称量词，记以称为全称量词，记以 x；语句语句“存在

24、一个存在一个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(张三张三)2/10/202333第33页，本讲稿共99页l量词的语义规定量词的语义规定 xG(x)取

25、取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)2/10/202334第34页，本讲稿共99页l例例.将下列命题符号化：将下列命题符号化：)一切事物都是发展变化的一切事物都是发展变化的 x F(x)其中其中F(x)：x是发展变化的是发展变化的)存在着会说话的机器人存在着会说话的机器人 x(F(x)G(x)其中其中F(x)：x会说话会说话 G(x):x是机器人是机器人

26、如果没有明确给出个体域，则认为个体域如果没有明确给出个体域，则认为个体域为一切事物。为一切事物。2/10/202335第35页，本讲稿共99页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)2/10/202336第36页，本讲稿共99页5)每个人都会犯错误每个人都会犯错误R(x):x是人是人P(x):x会犯错误会犯错

27、误 x(R(x)P(x)2/10/202337第37页，本讲稿共99页3 约束变量、自由变量 在一个由谓词，量词，逻辑联结词，括号组成的有意义的符号串在一个由谓词，量词，逻辑联结词，括号组成的有意义的符号串在一个由谓词，量词，逻辑联结词，括号组成的有意义的符号串在一个由谓词，量词，逻辑联结词，括号组成的有意义的符号串(公式公式公式公式)中，称变量的出现是约束的，当且仅当它出现在使用这个中，称变量的出现是约束的，当且仅当它出现在使用这个中，称变量的出现是约束的，当且仅当它出现在使用这个中，称变量的出现是约束的，当且仅当它出现在使用这个变量的量词范围之内；称变量的出现是自由的，当且仅当这个出现变量

28、的量词范围之内；称变量的出现是自由的，当且仅当这个出现变量的量词范围之内；称变量的出现是自由的，当且仅当这个出现变量的量词范围之内；称变量的出现是自由的，当且仅当这个出现不是约束的。不是约束的。不是约束的。不是约束的。称变量是约束的，如果至少有一个它的出现是约束的；称变量是约束的，如果至少有一个它的出现是约束的；称变量是约束的，如果至少有一个它的出现是约束的；称变量是约束的，如果至少有一个它的出现是约束的；称变量是自由的，如果至少有一个它的出现是自由的。称变量是自由的，如果至少有一个它的出现是自由的。称变量是自由的，如果至少有一个它的出现是自由的。称变量是自由的，如果至少有一个它的出现是自由的

29、。例如，例如，例如，例如，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

30、 z z只是自由变量。只是自由变量。只是自由变量。只是自由变量。2/10/202338第38页，本讲稿共99页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)。亦即，谓词逻辑中命题的真值，与命

31、题中的约束变量的记法无关。亦即，谓词逻辑中命题的真值，与命题中的约束变量的记法无关。这就引出了谓词逻辑中的改名规则。这就引出了谓词逻辑中的改名规则。2/10/202339第39页，本讲稿共99页l改名规则：在由谓词，量词，逻辑联结词，括改名规则：在由谓词，量词，逻辑联结词，括号组成的有意义的符号串号组成的有意义的符号串(公式公式)中，可将其中中，可将其中出现的约束变量改为另一个约束变量，这种改出现的约束变量改为另一个约束变量，这种改名必须在量词作用区域内各处以及该量词符号名必须在量词作用区域内各处以及该量词符号中实行，并且改成的新约束变量要有别于改名中实行，并且改成的新约束变量要有别于改名区域

32、中的所有其它变量。区域中的所有其它变量。l显然改名规则不改变原符号串的真值。显然改名规则不改变原符号串的真值。2/10/202340第40页，本讲稿共99页例:对于对于 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)2/10/202341第41页，本讲稿共99页5 封闭公式公

33、式中无自由变量，或将自由变量看做常量。公式中无自由变量，或将自由变量看做常量。(公式中每个变量的出现都是约束的）公式中每个变量的出现都是约束的）2/10/202342第42页，本讲稿共99页1)常量符号常量符号：用小写英文字母：用小写英文字母a，b，c，表示，表示，当个体名称集合当个体名称集合D给出时，它可以是给出时，它可以是D中某个中某个元素。元素。2)变量符号变量符号：用小写英文字母：用小写英文字母u，v，w，x，y，z，表示，当个体名称集合表示，当个体名称集合D给出时，给出时，D中中任任意元素意元素可代入变量符号。可代入变量符号。6 谓词逻辑形式化中使用的四种符号谓词逻辑形式化中使用的四

34、种符号2/10/202343第43页，本讲稿共99页3)函数符号函数符号：用小写英文字母：用小写英文字母f，g，表示，当表示，当个体名称集合个体名称集合D给出时，给出时，n元函数符号元函数符号f(x1，xn)可以是可以是Dn到到D的任意一个映射。的任意一个映射。4)谓词符号谓词符号：用大写英文字母：用大写英文字母P，Q，R，表表示，当个体名称集合示，当个体名称集合D给出时，给出时，n元谓词符号元谓词符号P(x1，xn)可以是可以是Dn上的任意一个谓词。上的任意一个谓词。2/10/202344第44页，本讲稿共99页7 项项谓词逻辑中的项，被递归定义为：谓词逻辑中的项，被递归定义为：1)常量符号

35、是项；常量符号是项；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)是原子。是原子。2/10/202345第45页，本讲稿共99页9 公式公式谓词逻辑中的公式，被递归定义如下：谓词逻辑中的公式，被递归定义如下：谓词逻辑中的公式，被递归定义如下：谓词逻辑中的公式，被递归定义如下：1)1)原子是公式；原子是公式；原

36、子是公式；原子是公式；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)生成的符号串。生成的符号串。生成的符号串。生成的符号串。2/10/202346第46页，本讲稿共

37、99页10 公式的语义解释谓词逻辑中公式谓词逻辑中公式谓词逻辑中公式谓词逻辑中公式GG的一个解释的一个解释的一个解释的一个解释I I，是由非空区域，是由非空区域，是由非空区域，是由非空区域D D和对和对和对和对GG中常中常中常中常量符号，函数符号，谓词符号以下列规则进行的一组指定量符号，函数符号，谓词符号以下列规则进行的一组指定量符号，函数符号，谓词符号以下列规则进行的一组指定量符号，函数符号，谓词符号以下列规则进行的一组指定组成：组成：组成：组成：1.1.对每个常量符号，指定对每个常量符号，指定对每个常量符号，指定对每个常量符号，指定D D中一个元素；中一个元素；中一个元素；中一个元素；2.

38、2.对每个对每个对每个对每个n n元函数符号，指定一个函数，即指元函数符号，指定一个函数，即指元函数符号，指定一个函数，即指元函数符号，指定一个函数，即指定定定定D Dn n到到到到D D的一个映射；的一个映射；的一个映射；的一个映射；3.3.对每个对每个对每个对每个n n元谓词符号，指定一个谓词，即指元谓词符号，指定一个谓词，即指元谓词符号，指定一个谓词，即指元谓词符号，指定一个谓词，即指定定定定D Dn n到到到到TT，FF的一个映射。的一个映射。的一个映射。的一个映射。2/10/202347第47页，本讲稿共99页例:1)G=x(P(f(x)Q(x，f(a)2)H=x(P(x)Q(x，a

39、)设解释设解释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 T2/10/202348第48页，本讲稿共99页例: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=F2/10/202349第49页，本讲稿共99页11 谓词公式的恒真、恒假、可满足l公式公式G称为可满足的，如果存在解释称为可满足的，如果存在解释I，使，使G在在I下取下

40、取 T值，简称值，简称I满足满足G。若若I不满足不满足G，则简称，则简称I弄假弄假G。l公式公式G称为是恒假的称为是恒假的(或不可满足的或不可满足的)，如果不，如果不存在解释存在解释I满足满足G。l公式公式G称为恒真的，如果称为恒真的，如果G的所有解释的所有解释I都满足都满足G。2/10/202350第50页，本讲稿共99页12 谓词逻辑的判定问题l谓词逻辑中公式恒真、恒假性的判断异常困难。谓词逻辑中公式恒真、恒假性的判断异常困难。原因？原因？谓词逻辑中的恒真谓词逻辑中的恒真(恒假恒假)公式，要求所有解释公式，要求所有解释I都满足都满足(弄弄假假)该公式。该公式。而解释而解释I依赖于一个非空集

41、合依赖于一个非空集合D。由于集合由于集合D可以是无穷集合，而集合可以是无穷集合，而集合D的的“数目数目”也可能是也可能是无穷多个。无穷多个。因此，所谓公式的因此，所谓公式的“所有所有”解释，实际上是无法考虑的。解释，实际上是无法考虑的。l1936年年Church和和Turing分别独立地证明了：对于谓词逻辑，分别独立地证明了：对于谓词逻辑，判定问题是不可解的。判定问题是不可解的。2/10/202351第51页，本讲稿共99页l谓词逻辑是半可判定的：谓词逻辑是半可判定的：如果谓词逻辑中的公式是恒真的，则有算法在如果谓词逻辑中的公式是恒真的，则有算法在有限步之内检验出这个公式的恒真性。如果该有限步

42、之内检验出这个公式的恒真性。如果该公式不是恒真的公式不是恒真的(当然也不是恒假的当然也不是恒假的)，则无法，则无法在有限步内判定这个事实。在有限步内判定这个事实。2/10/202352第52页，本讲稿共99页13等价l公式公式G，H称为等价，记以称为等价，记以G=H，如果公式，如果公式GH是恒真的。是恒真的。l公式公式G，H等价的充要条件是：对等价的充要条件是：对G，H的任意的任意解释解释I，G，H在在I下的真值相同。下的真值相同。l因为对任意公式因为对任意公式G，H，在解释，在解释I下，下，G，H就就是两个命题，所以命题逻辑中给出的基本等价是两个命题，所以命题逻辑中给出的基本等价式，在谓词逻

43、辑中仍然成立。式，在谓词逻辑中仍然成立。2/10/202353第53页，本讲稿共99页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

44、 I满足满足满足满足GG，则，则，则，则I I必满足必满足必满足必满足H H。l l同样，命题逻辑中的基本蕴涵式仍成立。同样，命题逻辑中的基本蕴涵式仍成立。同样，命题逻辑中的基本蕴涵式仍成立。同样，命题逻辑中的基本蕴涵式仍成立。14 蕴涵2/10/202354第54页，本讲稿共99页基本基本蕴蕴涵式：涵式：(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(

45、x)x Q(x)(11)x(P(x)Q(x)x P(x)x Q(x)2/10/202355第55页，本讲稿共99页l例例.设设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

46、)=T。2/10/202356第56页，本讲稿共99页G，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 G2/10/202357第57页，本讲稿共99页58设在一个含有凹室设在一个含有凹室(alcove)(alcove)的房间内，有桌子的房间内，有桌子A A和书架和书架B B，一个机器人，一个机器人(robot)(robot)和和 一叠书一叠书(book)(book)。现在要求机器人。现在要求机器人(robot)(rob

47、ot)从凹室出发，把桌子从凹室出发，把桌子A A上的上的书搬到书搬到B B处书架上，完成任务后回到凹室。请用谓词逻辑描处书架上，完成任务后回到凹室。请用谓词逻辑描述机器人完成这一工作的全过程。述机器人完成这一工作的全过程。谓词逻辑知识表示的例子2/10/202358第58页，本讲稿共99页59谓词逻辑知识表示的例子解解解解：为为了了能能够够描描述述这这个个机机器器人人世世界界的的有有关关环环境境和和状状态态变变迁迁，要要求求必必须须先先定定义义谓谓词词。注注意意这这里里需需要要定定义义两两类类谓谓词词：一一类类用用来来描描述述环环境境状状态态，另另一一类类谓谓词用来表示机器人的操作。词用来表示

48、机器人的操作。首先定义描述环境状态的谓词。首先定义描述环境状态的谓词。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的个体域：的个体域：robotrobot；HOLDS(yHOLDS(y，u)u)：y y手中拿着手中拿着u u，u u的个体域：的个体域：booksbooks；AT(yAT(y，w)w)：y y在在w w处，处，w w的个体域：的个体域：aa，b b，alcove a

49、lcove；ON(uON(u，x)x)：u u被放在被放在x x之上；之上；CLEAR(v)CLEAR(v)：v v上上(中中)是空的，是空的，v v的个体域：的个体域：aa，b b.2/10/202359第59页，本讲稿共99页60谓词逻辑知识表示的例子解：解：解：解：使用谓词以及联结词、量词等来表示环境状态。使用谓词以及联结词、量词等来表示环境状态。这样，问题的初始状态可表示为：这样，问题的初始状态可表示为：S S0 0：AT(robot,alcove)EMPTY(robot)AT(robot,alcove)EMPTY(robot)ON(books,a)CLEAR(b)ON(books,a

50、)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)2/10/202360第60页，本讲稿共99页61谓词逻辑知识表示的例子解：解：解：解：从初始状态到达目标状态的变迁，必须由机器人一从初始状态到达目标状态的变迁，必须由机器人一步一步地