人工智能第五章

1、人工智能第五章8/30/20221第1页，共99页，2022年，5月20日，11点0分，星期日第五章 谓词演算（复习）数理逻辑思想的起源：Leibnitz之梦 产生的历史：Boole的工作、Frege的工作 发展的现实：计算机学科的基础（软件到硬件） 古典数理逻辑主要包括两部分：命题逻辑和谓词逻辑。 命题逻辑又是谓词逻辑的一种简单情形。逻辑研究的基本内容 语法 语言部分：基本符号集、公式形成规则 推理部分：公理集、推理规则 语义 语法和语义之间的关系：可靠性、完备性基本问题 逻辑表示下的判定问题8/30/20222第2页，共99页，2022年，5月20日，11点0分，星期日一、命题逻辑1 命题

2、 一句有真假意义的话。用大写英文字母P，Q，P1，P2，表示。 例： 上海是中国最大的城市。 今天是星期日。所有素数都是奇数。 1+1=2。我不会解答这道题。 别的星球上有生物。长春今天下雪。如果太阳从西方升起，你就可以长生不老。 严禁吸烟。 今天的温度有多少度？ 全体起立！ 今天好冷啊！ 我正在说谎。8/30/20223第3页，共99页，2022年，5月20日，11点0分，星期日2 真值 如果一个命题是真的，就说它的真值是T； 如果一个命题是假的，就说它的真值是F。 T和F统称为命题的真值。 也用T代表一个抽象的真命题，用F代表一个抽象的假命题。 8/30/20224第4页，共99页，202

3、2年，5月20日，11点0分，星期日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中至少有一个为真。8/30/20225第5页，共99页，2022年，5月20日，11点0分，星期日设P，Q是两个命题，命题 “P并且Q”称为P，Q的合取，记以PQ，读作P合取Q。例. P：22=5，Q：雪是黑的，

4、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是假的。8/30/20226第6页，共99页，2022年，5月20日，11点0分，星期日设P，Q是两个命题，命题 “P当且仅当Q”称为P等价Q，记以PQ。语义规定： PQ是真的当且仅当P，Q或者都是真的，或者都是假的。例 P ：a2+b2=a2，Q： b=0，PQ： a2+b2=a2当且仅当b=0 。五种逻辑联结词的

5、优先级按如下次序递增： ， 例. 符号串 PQRQ SR 意味着： (P(QR)(Q(S)R)8/30/20227第7页，共99页，2022年，5月20日，11点0分，星期日4 复合命题 用联结词将简单命题连接的结果。5 原子 命题的抽象。 用大写的英文字母P，Q，R，等表示。6 文字 原子或原子的否定。7 子句 有限个文字的析取式称为一个子句。 特别，没有文字的子句称为空子句，记为 。 只有一个文字的子句称为单元子句。8 短语 有限个文字的合取式称为一个短语。8/30/20228第8页，共99页，2022年，5月20日，11点0分，星期日复合命题的抽象 公式的形成规则-是如下定义的一个符号串

6、：(1)原子是公式；(2)F、T是公式； (3)若G，H是公式，则( G)，(GH)，(GH)，(GH)，(GH)是公式；(4)所有公式都是有限次使用(1)，(2)，(3)得到的符号串。9 公式8/30/20229第9页，共99页，2022年，5月20日，11点0分，星期日设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 解释 P Q T T P Q T

7、F 8/30/202210第10页，共99页，2022年，5月20日，11点0分，星期日11 真值表 公式G在其所有可能的解释下所取真值的表，称为G的真值表。 有n个不同原子的公式，共有2n个解释。 12 恒真公式 公式G称为恒真的(或有效的)，如果G在它的所有解释下都是真的. 8/30/202211第11页，共99页，2022年，5月20日，11点0分，星期日13 恒假公式 公式G称为恒假的(或不可满足的)，如果G在它的所有解释下都是假的.14 可满足公式 公式G称为可满足的，如果它不是恒假的。G是恒真的 iff G是恒假的。G是可满足的 iff 至少有一个解释I，使G在I下为真。若G是恒真

8、的，则G是可满足的； 反之不对。如果公式G在解释I下是真的，则称I满足G； 如果G在解释I下是假的，则称I弄假G。 8/30/202212第12页，共99页，2022年，5月20日，11点0分，星期日例.考虑G1= (PQ) P，G2=(P Q) P， G3=P P。PQG1PQG2PG3FFTFFFFFFTTFTFTFTFTTFFTTTTTT8/30/202213第13页，共99页，2022年，5月20日，11点0分，星期日15 判定问题能否给出一个可行方法，对任意的公式，判定其是否是恒真公式。命题逻辑可判定？ 原因？ 因为一个命题公式的原子数目有限(n)，从而解释的数目是有限的(2n)，所

9、以命题逻辑的判定问题是可解的(可判定的，可计算的).8/30/202214第14页，共99页，2022年，5月20日，11点0分，星期日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； (结合律)8/30/202215第15页，共99页，2022年，5月20日，11点0分，星期日6) G(GH)=G，G(G

10、H)=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。 (De Morgan律)11) GG=T；GG=F （互补律）12) G=G （双重否定律） 8/30/202216第16页，共99页，2022年，5月20日，11点0分，星期日17 公式的蕴涵设G，H是两个公式。 称H是G的逻辑结果(或称G蕴涵H)，当且仅当对G，H的任意解释I，如果I满足G，则I也满足H，记作GH。公式G蕴涵公式H iff 公式GH是恒真的。设G1,

11、, Gn，H是公式。 称H是G1, ,Gn的逻辑结果(或称G1, , Gn共同蕴涵H)，当且仅当 (G1 Gn) H。 例如，P，PQ共同蕴涵Q。 8/30/202217第17页，共99页，2022年，5月20日，11点0分，星期日基本蕴涵式 PQPPQQPPQQPQP(PQ)Q(PQ)(PQ)P8/30/202218第18页，共99页，2022年，5月20日，11点0分，星期日基本蕴涵式 (PQ) QP，QPQP，PQQP，PQQQ，PQ PPQ，QRPRPQ，PR，QRR 8/30/202219第19页，共99页，2022年，5月20日，11点0分，星期日18 范式有限个短语的析取式称为析

12、取范式；有限个子句的合取式称为合取范式。特别，一个文字既可称为是一个合取范式，也可称为是一个析取范式。一个子句，一个短语既可看做是合取范式，也可看做是析取范式。例如，P，PQ，PQ，(PQ)(P Q)是析取范式。 P，PQ，PQ，(PQ)(PR)是合取范式。 8/30/202220第20页，共99页，2022年，5月20日，11点0分，星期日化范式方法：步1. 使用基本等价式，将G中的逻辑联结词，删除。步2. 使用(H)=H和摩根律， 将G中所有的否定号都放在原子之前。 步3. 反复使用分配律，即可得到等价于G的范 式。 8/30/202221第21页，共99页，2022年，5月20日，11点

13、0分，星期日19 演绎设S是一个命题公式的集合(前提集合)。从S推出公式G的一个演绎是公式的一个有限序列：G1, G2, , Gk 其中，Gi （1i k）或者属于S，或者是某些 Gj (j3,23,503等50个命题。8/30/202224第24页，共99页，2022年，5月20日，11点0分，星期日2 不能描述问题间的逻辑联系例如，逻辑学中著名的三段论：P：凡人必死Q：张三是人R：张三必死 在命题逻辑中：应该有(PQ) R，从而公式(PQ)R应该是恒真的。显然该公式不是恒真的，解释P，Q， R就能弄假该公式。8/30/202225第25页，共99页，2022年，5月20日，11点0分，星期

14、日原因：命题R是和命题P, Q有关系的，只是这种关系在命题逻辑中无法表示。因此，需要对命题的成分、结构和命题间的共同特性等作进一步的分析，这正是谓词逻辑所要研究的问题。8/30/202226第26页，共99页，2022年，5月20日，11点0分，星期日为了表示出这三个命题的内在关系，需要引进谓词的概念。例如，在前面的例子“张三是人”中的“是人”是谓语，称为谓词，“张三”是主语，称为个体。8/30/202227第27页，共99页，2022年，5月20日，11点0分，星期日二、谓词逻辑 1 谓词可以独立存在的物体称为个体。 如人、学生、桌子、自然数等都可以做个体。在谓词演算中，个体通常指一个命题里

15、的思维对象。设D是非空个体名称集合，定义在Dn上取值于T，F上的n元函数，称为n元命题函数或n元谓词。其中Dn表示集合D的n次笛卡尔乘积。一般地，一元谓词描述个体的性质，二元或多元谓词描述两个或多个个体间的关系。0元谓词中无个体，理解为就是命题，这样，谓词逻辑包括命题逻辑。8/30/202228第28页，共99页，2022年，5月20日，11点0分，星期日例.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,

16、z)：若x+y-1=z，则P(x,y,z)为T，否则为F 。则P(x,y,z)为三元谓词。指定元素-命题：P(2,3,4)=T,P(4,2,2)=F8/30/202229第29页，共99页，2022年，5月20日，11点0分，星期日例.用谓词的概念可将三段论做如下的符号化： 令H(x)表示 “x是人”，M(x)表示 “x必死”。 则三段论的三个命题表示如下：P： H(x)M(x)Q： H(张三)R： M(张三)8/30/202230第30页，共99页，2022年，5月20日，11点0分，星期日若想得到 “命题”P的否定 “命题”，应该就是“命题” P。但是， P= (H(x)M(x)= (H(

17、x)M(x)=H(x) M(x)亦即，“命题”P的否定 “命题”是 “所有人都不死”。这和人们日常对命题 “所有人都必死”的否定的理解，相差得实在太远了.8/30/202231第31页，共99页，2022年，5月20日，11点0分，星期日原因命题P的确切意思应该是： “对任意x，如果x是人，则x必死”。 但是H(x)M(x)中并没有确切的表示出 “对任意x”这个意思，亦即H(x)M(x)不是一个命题。 因此，在谓词逻辑中除引进谓词外，还需要引进 “对任意x”这个语句，及其对偶的语句 “存在一个x”。 8/30/202232第32页，共99页，2022年，5月20日，11点0分，星期日2 量词定

18、义 语句 “对任意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(张三)8/30/202233第33页，共99页，2022年，5月20日，11点0分，星期日量词的语义规定 xG(x)取T值对任意xD，G(x)都取T值； xG(x)取T值至少有一个x0D，使G(x0)取T值 语义上，当

19、D=x0,x1,是可数集合时，xG(x)等价于G(x0)G(x1)xG(x)等价于G(x0)G(x1) 8/30/202234第34页，共99页，2022年，5月20日，11点0分，星期日例.将下列命题符号化：)一切事物都是发展变化的 x F(x) 其中F(x)：x是发展变化的)存在着会说话的机器人 x(F(x)G(x)其中F(x)：x会说话 G(x): x是机器人如果没有明确给出个体域，则认为个体域为一切事物。8/30/202235第35页，共99页，2022年，5月20日，11点0分，星期日3) 每个计算机学院的学生都学离散数学。D：全校学生集合P(x)：x是计算机学院的学生R(x): x

20、学离散数学x(P(x) R(x)4）存在着偶素数D：正整数集合E(x)：x是偶数P(x)：x是素数x(E(x)P(x)8/30/202236第36页，共99页，2022年，5月20日，11点0分，星期日5) 每个人都会犯错误R(x):x是人P(x):x会犯错误x(R(x) P(x)8/30/202237第37页，共99页，2022年，5月20日，11点0分，星期日3 约束变量、自由变量 在一个由谓词，量词，逻辑联结词，括号组成的有意义的符号串(公式)中，称变量的出现是约束的，当且仅当它出现在使用这个变量的量词范围之内；称变量的出现是自由的，当且仅当这个出现不是约束的。 称变量是约束的，如果至少

21、有一个它的出现是约束的； 称变量是自由的，如果至少有一个它的出现是自由的。例如，x(P(x，y)Q(x，z)R(x)从左向右算起，变量x的第一，第二次出现是约束的，第三次出现是自由的；变量y，z的出现是自由的。x既是约束变量，又是自由变量；y，z只是自由变量。 8/30/202238第38页，共99页，2022年，5月20日，11点0分，星期日4 约束变量的改名规则改名规则的理论依据xP(x)与yP(y)都是表示个体域D中的“每个个体都具有性质P”，所以可以把x改名为y，即把xP(x)改成为yP(y)。xP(x)与yP(y)都是表示个体域D中的“某个个体具有性质P” ，所以也可以把x改名为y，

22、即把xP(x)改成为yP(y)。亦即，谓词逻辑中命题的真值，与命题中的约束变量的记法无关。这就引出了谓词逻辑中的改名规则。 8/30/202239第39页，共99页，2022年，5月20日，11点0分，星期日改名规则：在由谓词，量词，逻辑联结词，括号组成的有意义的符号串(公式)中，可将其中出现的约束变量改为另一个约束变量，这种改名必须在量词作用区域内各处以及该量词符号中实行，并且改成的新约束变量要有别于改名区域中的所有其它变量。显然改名规则不改变原符号串的真值。8/30/202240第40页，共99页，2022年，5月20日，11点0分，星期日例:对于x(P(x，y)Q(x，z) R(x, v

23、)，可改名为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)8/30/202241第41页，共99页，2022年，5月20日，11点0分，星期日5 封闭公式公式中无自由变量，或将自由变量看做常量。 (公式中每个变量的出现都是约束的）8/30/202242第42页，共99页，2022年，5月20日，11点0分，星期日

24、1) 常量符号：用小写英文字母a，b，c，表示，当个体名称集合D给出时，它可以是D中某个元素。2) 变量符号：用小写英文字母u，v，w，x，y，z，表示，当个体名称集合D给出时，D中任意元素可代入变量符号。6 谓词逻辑形式化中使用的四种符号8/30/202243第43页，共99页，2022年，5月20日，11点0分，星期日3) 函数符号：用小写英文字母f，g，表示，当个体名称集合D给出时，n元函数符号f(x1，xn)可以是Dn到D的任意一个映射。4) 谓词符号：用大写英文字母P，Q，R，表示，当个体名称集合D给出时，n元谓词符号P(x1，xn)可以是Dn上的任意一个谓词。 8/30/20224

25、4第44页，共99页，2022年，5月20日，11点0分，星期日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)是原子。8/30/202245第45页，共99页，2022年，5月20日，11点0分，星期日9 公式谓词逻辑中的公式，被递归定义如下：1) 原子是公式；2) 若G，H是公式，则(G)，(GH)， (GH)， (GH)，(GH)是

26、公式；3) 若G是公式，x是G中的自由变量，则xG，xG是公式；4) 所有公式都是有限次使用1)3)生成的符号串。 8/30/202246第46页，共99页，2022年，5月20日，11点0分，星期日10 公式的语义解释谓词逻辑中公式G的一个解释I，是由非空区域D和对G中常量符号，函数符号，谓词符号以下列规则进行的一组指定组成：1. 对每个常量符号，指定D中一个元素；2. 对每个n元函数符号，指定一个函数，即指定Dn到D的一个映射；3. 对每个n元谓词符号，指定一个谓词，即指定Dn到T，F的一个映射。 8/30/202247第47页，共99页，2022年，5月20日，11点0分，星期日例:1)

27、 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 T8/30/202248第48页，共99页，2022年，5月20日，11点0分，星期日例: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=F8/30/202249第49页，共99页，20

28、22年，5月20日，11点0分，星期日11 谓词公式的恒真、恒假、可满足公式G称为可满足的，如果存在解释I，使G在I下取 T值，简称I满足G。 若I不满足G，则简称I弄假G。公式G称为是恒假的(或不可满足的)，如果不存在解释I满足G。公式G称为恒真的，如果G的所有解释I都满足G。 8/30/202250第50页，共99页，2022年，5月20日，11点0分，星期日12 谓词逻辑的判定问题谓词逻辑中公式恒真、恒假性的判断异常困难。原因？谓词逻辑中的恒真(恒假)公式，要求所有解释I都满足(弄假)该公式。而解释I依赖于一个非空集合D。由于集合D可以是无穷集合，而集合D的 “数目”也可能是无穷多个。因

29、此，所谓公式的 “所有”解释，实际上是无法考虑的。1936年Church和Turing分别独立地证明了：对于谓词逻辑，判定问题是不可解的。8/30/202251第51页，共99页，2022年，5月20日，11点0分，星期日谓词逻辑是半可判定的： 如果谓词逻辑中的公式是恒真的，则有算法在有限步之内检验出这个公式的恒真性。如果该公式不是恒真的(当然也不是恒假的)，则无法在有限步内判定这个事实。8/30/202252第52页，共99页，2022年，5月20日，11点0分，星期日13 等价公式G，H称为等价，记以G=H，如果公式GH是恒真的。公式G，H等价的充要条件是：对G，H的任意解释I，G，H在I

30、下的真值相同。因为对任意公式G，H，在解释I下，G，H就是两个命题，所以命题逻辑中给出的基本等价式，在谓词逻辑中仍然成立。8/30/202253第53页，共99页，2022年，5月20日，11点0分，星期日设G，H是公式，称G蕴涵H，或H是G的逻辑结果，如果公式GH是恒真的，并记以GH。对任意两个公式G，H，G蕴涵H的充要条件是：对任意解释I，若I满足G，则I必满足H。同样，命题逻辑中的基本蕴涵式仍成立。14 蕴涵8/30/202254第54页，共99页，2022年，5月20日，11点0分，星期日基本蕴涵式：(PP) PP (PQ)(PQ) (QP)(QR) (PQ) (PR)xP(x) P(

31、y)P(y) xP(x)x P(x) xP(x)x P(x) x Q(x) x (P(x)Q(x)x(P(x) Q(x) xP(x) xQ(x)x (P(x) Q(x) x P(x) x Q(x)x (P(x) Q(x) x P(x) x Q(x)8/30/202255第55页，共99页，2022年，5月20日，11点0分，星期日例.设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下对任意xD，有TI(A(x)=T，又由TI(x(A(

32、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。8/30/202256第56页，共99页，2022年，5月20日，11点0分，星期日G，H不等价。举反例：简单扼要、击中要害I: 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 G8/30/202257第57页，共99页，2022年，5月20日，11点0分，星期日58设在一个含有凹室(alcove)的房间内，有桌子A和书

33、架B，一个机器人(robot)和 一叠书(book)。现在要求机器人(robot)从凹室出发，把桌子A上的书搬到B处书架上，完成任务后回到凹室。请用谓词逻辑描述机器人完成这一工作的全过程。 谓词逻辑知识表示的例子8/30/202258第58页，共99页，2022年，5月20日，11点0分，星期日59谓词逻辑知识表示的例子解：为了能够描述这个机器人世界的有关环境和状态变迁，要求必须先定义谓词。注意这里需要定义两类谓词：一类用来描述环境状态，另一类谓词用来表示机器人的操作。首先定义描述环境状态的谓词。TABLE(x)： x是桌子， x的个体域： a ；BOOKCASE(z)： z是书架， z的个体

34、域： 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 .8/30/202259第59页，共99页，2022年，5月20日，11点0分，星期日60谓词逻辑知识表示的例子解：使用谓词以及联结词、量词等来表示环境状态。这样，问题的初始状态可表示为：S0：AT(robot, alcove)EMPTY(robot)ON(books, a)CLEAR(b)TABLE

35、(a)BOOKCASE (b)要求达到的目标状态为：Sg：AT(robot, alcove)EMPTY(robot)ON(books, b)CLEAR(a)TABLE(a)BOOKCASE (b) 8/30/202260第60页，共99页，2022年，5月20日，11点0分，星期日61谓词逻辑知识表示的例子解：从初始状态到达目标状态的变迁，必须由机器人一步一步地执行相应的操作序列，得以逐步实现。因此，必须要定义操作类谓词。仔细加以分析，必要的操作谓词共有三类。GOTO(x, w)：机器人从x走到w处；PICK-UP(x) ：机器人在x处拿起书；SET-DOWN(w) ：机器人在w处放下书。 一

36、般说来，如果定义谓词太多，将造成信息冗余，增加了问题的复杂度；如果定义谓词太少，就不够用。因此，定义的谓词性质与数量要合适。 8/30/202261第61页，共99页，2022年，5月20日，11点0分，星期日62谓词逻辑知识表示的例子解：按照行动规划，仔细选择操作，一步步进行状态替换，直到达到目标状态。即要求把状态变迁过程和操作序列记录下来，来描述问题解。下面写出该过程的最优路径： AT(robot, alcove)EMPTY(robot)ON(books, a)CLEAR(b)TABLE(a)BOOKCASE(b)AT(robot, a)EMPTY(robot)ON(books, a)CL

37、EAR(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）8/30/202262第62页，共99页，2022年，5月20日，11点0分，星期日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)BOOK

38、CASE (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）8/30/202263第63页，共99页，2022年，5月20日，11点0分，星期日64谓词逻辑知识表示的例子解：这样,得到目标为 AT(robot, alcove)EMPTY(robot)ON(books, b)CLEAR(a)TA

39、BLE(a)BOOKCASE (b) 这里顺便指出，若机器人智商不高，这个任务过程会产生许多冗余。比如，机器人拿着书，找不到b处，无所适从而又扛回来了；或者等。可见，实际的机器人智能控制要更加复杂得多，虽然有时也很有趣。 8/30/202264第64页，共99页，2022年，5月20日，11点0分，星期日例 将自然数公理符号化：A1：每一个数，有且仅有一个直接后继者；A2：没有一个数使0是直接后继者；A3：对任意异于0的数，有且仅有一个直接先行者。解：令f(x)表示x的直接后继者g(x)表示x的直接先行者E(x,y)表示x等于y谓词逻辑知识表示的例子8/30/202265第65页，共99页，2

40、022年，5月20日，11点0分，星期日于是将上述三个公理符号化如下：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)8/30/202266第66页，共99页，2022年，5月20日，11点0分，星期日解：令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

41、) x(P(x) y(Q(y) L(x, y) xy(P(x)Q(y) L(x, y)B=x(D(x)Q(x)例 已知某些病人喜欢所有的医生， 没有一个病人喜欢任意一个骗子。 证明任意一个医生都不是骗子。8/30/202267第67页，共99页，2022年，5月20日，11点0分，星期日 剩下的任务就是调用某一过程证明A1A2B是一阶逻辑中的恒真公式，即B是A1、A2的逻辑结果。我们把它留到下一章中讨论。 8/30/202268第68页，共99页，2022年，5月20日，11点0分，星期日69 逻辑知识表示的主要特点是建立在某种形式逻辑的基础上，并利用了逻辑方法研究推理的规律，即条件与结论之间

42、的蕴涵关系。逻辑表示法的主要优点如下：（1）自然 一阶谓词逻辑是一种接近于自然语言的形式语言系统，谓词逻辑表示法接近于人们对问题的直观理解，易于被人们接受。（2）明确 逻辑表示法对如何由简单陈述句构造复杂陈述句的方法有明确规定，如联结词、量词的用法与含义等。对于用逻辑表示法表示的知识，人们都可以按照一种标准的方法去解释它，因此用这种方法表示的知识明确、易于理解。谓词逻辑表示的特性8/30/202269第69页，共99页，2022年，5月20日，11点0分，星期日70（3）精确 谓词逻辑是一种二值逻辑，其谓词公式的真值只有“真”与“假”，因此可用来表示精确知识，并可保证经演绎推理所得结论的精确性

43、。（4）灵活 逻辑表示法把知识和处理知识的程序有效地分开。在使用这种方法表示知识时，无须考虑程序中处理知识的细节。（5）模块化 在逻辑表示法中，各条知识都是相对独立的，它们之间不直接发生联系。因此添加、删除、修改知识的工作比较容易进行。谓词逻辑表示的特性8/30/202270第70页，共99页，2022年，5月20日，11点0分，星期日71 逻辑表示法也存在一些不足，其主要缺点如下：（1）知识表示能力差 逻辑表示法只能表示确定性知识，而不能表示非确定性知识，如不精确、模糊性知识。实际上，人类的大部分知识都不同程度地具有某种不确定性，这就使得它表示知识的范围和能力受到了一定的限制。另外，逻辑表示

44、法还难以表示过程性知识和启发性知识。（2）知识库管理困难 逻辑表示法缺乏知识的组织原则，利用这种表示法所形成的知识库管理比较困难。（3）存在组合爆炸 由于逻辑表示法难以表示启发性知识，因此在推理过程中只能盲目地使用推理规则。这样，当系统知识量较大时，容易发生组合爆炸。（4）系统效率低 逻辑表示法的推理过程是根据形式逻辑进行的。它把推理演算与知识含义截然分开，抛弃了表达内容中所含有的语义信息，往往使推理过程冗长，降低了系统效率。谓词逻辑表示的特性8/30/202271第71页，共99页，2022年，5月20日，11点0分，星期日15 前束范式 谓词逻辑中公式G称为前束范式，如果G有如下形状：Q1

45、x1QnxnM 其中 Qixi或者是xi，或者是xi，i=1,n， M是不含量词的公式，Q1x1Qnxn称为首标，M称为母式。例如，xyz(P(x，y)Q(x，z) xyzP(x，y，z)8/30/202272第72页，共99页，2022年，5月20日，11点0分，星期日对任意谓词公式，量词是不能随便提前的。？ xP(x) P(a) =x(P(x) P(a)？ xP(x) P(a) =x(P(x) P(a)8/30/202273第73页，共99页，2022年，5月20日，11点0分，星期日xP(x)P(a) 是恒真公式.任取解释I，若P(a) 在I下为真,则xP(x)P(a)在I下为真;若P(

46、a) 在I下为假,则xP(x)在I下为假,故xP(x)P(a)在I下为真因此,xP(x)P(a) 是恒真公式.8/30/202274第74页，共99页，2022年，5月20日，11点0分，星期日而x(P(x) P(a)不是恒真公式。设解释I为： D=1，2 a 1 P(1) P(2) F T 则 TI(x(P(x) P(a) = TI (P(1) P(1) (P(2) P(1) = T F = F因此， xP(x) P(a) x(P(x) P(a) 8/30/202275第75页，共99页，2022年，5月20日，11点0分，星期日x（P(x) P(a)）为恒真公式。任取解释I，由P(a) P

47、(a)为真，知， 存在xD，使得P(x) P(a)为真，即 x（P(x) P(a)）为真。因此，x（P(x) P(a)）为恒真公式。8/30/202276第76页，共99页，2022年，5月20日，11点0分，星期日而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

48、(a)和xP(x) P(a)不等价。8/30/202277第77页，共99页，2022年，5月20日，11点0分，星期日引理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)8/30/202278第78页，共99页，2022年，5月20日，11点0分，星期日引理2 设H，G是两个仅含有自由变量x的公式，分别记以H(x)，G(x)，于

49、是有：(1) xG(x)x H(x)= x(G(x )H(x)(2) xG(x)x H(x)= x(G(x )H(x) (3) xG(x)x H(x)= xy (G(x )H(y)(4) xG(x)x H(x)= xy (G(x )H(y)8/30/202279第79页，共99页，2022年，5月20日，11点0分，星期日思考? 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) 8/30/202280第80页，共99页，2022年，5月20日，11点0分，星期日设I为：D=a,b G(a) G(b) H(a)

50、H(b) T F F TTI(xG(x)xH(x)= FTI(x(G(x)H(x) )= T8/30/202281第81页，共99页，2022年，5月20日，11点0分，星期日? 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) 8/30/202282第82页，共99页，2022年，5月20日，11点0分，星期日设I为：D=a,b G(a) G(b) H(a) H(b) T F F TTI(xG(x) xH(x) )=TTI(x(G(x) H(x) )=F8/30/202283第83页，共99页

51、，2022年，5月20日，11点0分，星期日化前束范式定理1 任意公式G都等价于一个前束范式证明 通过如下四个步骤即可将公式G化为前束范式 步骤1：使用基本等价式 FH=(FH) (HF) FH=FH 可将公式G中的和删去。 步骤2：使用(F)=F和De. Morgan律及引理1， 可将公式中所有否定号放在原子之前。步骤3：如果必要的话，则将约束变量改名步骤4：使用引理1和引理2又将所有量词都提到公式的 最左边。8/30/202284第84页，共99页，2022年，5月20日，11点0分，星期日例 将xy(z (P(x, z)P(y, z) uQ(x, y, u) 化为前束范式xy (z (P

52、(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)8/30/202285第85页，共99页，2022年，5月20日，11点0分，星期日例. 将公式xy(A(x)B(x,y)(yC(y)zD(z) 化为前束范式。解：（1）消去联结词。 xy（A(x) B(x,y)）(y

53、C(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)8/30/202286

54、第86页，共99页，2022年，5月20日，11点0分，星期日16 Skolem 范式设G是一个公式，Q1x1QnxnM是与G等价的前束范式，其中M为合取范式形式。若Qr是存在量词，并且它左边没有全称量词，则取异于出现在M中所有常量符号的常量符号c，并用c代替M中所有的xr，然后在首标中删除Qrxr。8/30/202287第87页，共99页，2022年，5月20日，11点0分，星期日若Qs1, , Qsm是所有出现在Qrxr左边的全称量词(m1,1s1s2smr),则取异于出现在M中所有函数符号的m元函数符号f(xs1,xsm )，用f(xs1,xsm )代替出现在M中的所有xr，然后在首标中删除Qrxr.8/30/202288第88页，共99页，2022年，5月20日，11点0分，星期日 对首标中的所有存在量词做上述处理后，得到一个在首标中没有存在量词的前束范式，这个前束范式就称为公式G的Skolem范式。其中用来代替xr的那些常量符号和函数符号称为公式G的Skolem函数.8/30/202289第89页，共99页，2022年，5月20日，11点0分，星期日转化为Skolem 范式的例子G=xyzuvwP(x,y,z,u,v,w)用a代替x，用