逻辑表示及推理方法课件.ppt

4/13/20221第三部分第三部分 逻辑表示及推理方法逻辑表示及推理方法 常用的知识表示方法：常用的知识表示方法：l非结构化方法非结构化方法逻辑表示法 QA3,STRIPS,DART,MOMO产生式系统 DENDRAL，MYCINl结构化方法结构化方法框架语义网络l 过程式知识表示法过程式知识表示法4/13/20222第五章第五章 谓词演算（复习）谓词演算（复习）l数理逻辑思想的起源：数理逻辑思想的起源：Leibnitz之梦之梦 产生的历史：产生的历史：Boole的工作、的工作、Frege的工作的工作 发展的现实：计算机学科的基础（软件到硬件）发展的现实：计算机学科的基础（软件到硬件） 古典数理逻辑主要包括两部分：命题逻辑和谓词逻辑。古典数理逻辑主要包括两部分：命题逻辑和谓词逻辑。 命题逻辑又是谓词逻辑的一种简单情形。命题逻辑又是谓词逻辑的一种简单情形。l逻辑研究的基本内容逻辑研究的基本内容 语法语法 语言部分：基本符号集、公式形成规则语言部分：基本符号集、公式形成规则 推理部分：公理集、推理规则推理部分：公理集、推理规则 语义语义 语法和语义之间的关系：语法和语义之间的关系：可靠性、完备性可靠性、完备性l基本问题基本问题 逻辑表示下的判定问题逻辑表示下的判定问题4/13/20223一、命题逻辑一、命题逻辑1 命题命题 一句有真假意义的话。用大写英文字母P，Q，P1，P2，表示。 例： 上海是中国最大的城市。上海是中国最大的城市。 今天是星期日。今天是星期日。所有素数都是奇数。所有素数都是奇数。 1+1=2。我不会解答这道题。我不会解答这道题。 别的星球上有生物。别的星球上有生物。长春今天下雪。长春今天下雪。如果太阳从西方升起，你就可以长生不老。如果太阳从西方升起，你就可以长生不老。 严禁吸烟。 今天的温度有多少度？今天的温度有多少度？ 全体起立！ 今天好冷啊！今天好冷啊！ 我正在说谎。4/13/202242 真值 如果一个命题是真的，就说它的真值是T； 如果一个命题是假的，就说它的真值是F。 T和F统称为命题的真值。 也用T代表一个抽象的真命题，用F代表一个抽象的假命题。 4/13/202253 联结词 、 、 、 、 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中至少有一个为真。中至少有一个为真。4/13/20226l设设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是假的。是假的。4/13/20227l设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)4/13/202284 复合命题复合命题 用联结词将简单命题连接的结果。用联结词将简单命题连接的结果。5 原子原子 命题的抽象。命题的抽象。 用大写的英文字母用大写的英文字母P，Q，R，等表示。等表示。6 文字文字 原子或原子的否定。原子或原子的否定。7 子句子句 有限个文字的有限个文字的析取式析取式称为一个称为一个子句。子句。 特别，没有文字的子句称为空子句，记为特别，没有文字的子句称为空子句，记为 。 只有一个文字的子句称为单元子句。只有一个文字的子句称为单元子句。8 短语短语 有限个文字的有限个文字的合取式合取式称为一个称为一个短语短语。4/13/20229复合命题的抽象复合命题的抽象 公式的形成规则公式的形成规则-是如下定义的一个符号串：(1)原子是公式；(2)F、T是公式； (3)若G，H是公式，则( G)，(GH)，(GH)，(GH)，(GH)是公式；(4)所有公式都是有限次使用(1)，(2)，(3)得到的符号串。9 公式4/13/202210设设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 4/13/20221111 真值表真值表 公式公式G在其所有可能的解释下所取真值在其所有可能的解释下所取真值的表，称为的表，称为G的的真值表真值表。 有有n个不同原子的公式，共有个不同原子的公式，共有2n个解释。个解释。 12 恒真公式恒真公式 公式公式G称为称为恒真的恒真的(或有效的或有效的)，如果，如果G在在它的所有解释下都是真的它的所有解释下都是真的. 4/13/20221213 恒假公式恒假公式 公式公式G称为恒假的称为恒假的(或不可满足的或不可满足的)，如果，如果G在它的所有在它的所有解释下都是假的解释下都是假的.14 可满足公式可满足公式 公式公式G称为可满足的，如果它不是恒假的。称为可满足的，如果它不是恒假的。lG是恒真的是恒真的 iff G是恒假的。是恒假的。lG是可满足的是可满足的 iff 至少有一个解释至少有一个解释I，使，使G在在I下为真。下为真。l若若G是恒真的，则是恒真的，则G是可满足的；是可满足的； 反之不对。反之不对。l如果公式如果公式G在解释在解释I下是真的，则称下是真的，则称I满足满足G； 如果如果G在解释在解释I下是假的，则称下是假的，则称I弄假弄假G。 4/13/202213l例.考虑G1= (PQ) P，G2=(P Q) P， G3=P P。PQG1PQG2PG3FFTFFFFFFTTFTFTFTFTTFFTTTTTT4/13/20221415 判定问题l能否给出一个能否给出一个可行方法可行方法，对任意的公式，判定，对任意的公式，判定其是否是恒真公式。其是否是恒真公式。l命题逻辑可判定？命题逻辑可判定？ 原因？原因？ 因为一个命题公式的原子数目有限因为一个命题公式的原子数目有限(n)，从而，从而解释的数目是有限的解释的数目是有限的(2n)，所以命题逻辑的判，所以命题逻辑的判定问题是可解的定问题是可解的(可判定的，可计算的可判定的，可计算的).4/13/20221516 公式等价公式等价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； (结合律结合律)4/13/2022166) 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 （双重否定律）（双重否定律） 4/13/20221717 公式的蕴涵公式的蕴涵设设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。 4/13/202218基本蕴涵式 lP QPlP QQlPP QlQP QlP(PQ)lQ(PQ)l(PQ)P4/13/202219基本蕴涵式 8.(PQ) Q9.P，QP Q10.P，P QQ11.P，PQQ12.Q，PQ P13.PQ，QRPR14.P Q，PR，QRR 4/13/20222018 范式范式l有限个有限个短语的析取式短语的析取式称为称为析取范式析取范式；l有限个有限个子句的合取式子句的合取式称为称为合取范式合取范式。l特别，一个特别，一个文字文字既可称为是一个合取范式，也既可称为是一个合取范式，也可称为是一个析取范式。一个可称为是一个析取范式。一个子句子句，一个，一个短语短语既可看做是合取范式，也可看做是析取范式。既可看做是合取范式，也可看做是析取范式。l例如，例如，P，P Q，P Q，(P Q) (P Q)是是析取范式。析取范式。 P，P Q，P Q，(P Q) (P R)是合取范式。是合取范式。 4/13/202221化范式方法：化范式方法：步步1. 使用基本等价式，将使用基本等价式，将G中的逻辑联结词中的逻辑联结词，删除。删除。步步2. 使用使用(H)=H和摩根律，和摩根律， 将将G中所有的否定号中所有的否定号都放在原子之前。都放在原子之前。 步步3. 反复使用分配律，即可得到等价于反复使用分配律，即可得到等价于G的范的范 式。式。 4/13/20222219 演绎l设设S是一个命题公式的集合是一个命题公式的集合(前提集合前提集合)。从。从S推推出公式出公式G的的一个演绎一个演绎是公式的一个有限序列：是公式的一个有限序列：G1, G2, , Gk 其中，其中，Gi （1i k）或者属于）或者属于S，或者是某，或者是某些些 Gj (j3,23,503等等50个命题。个命题。4/13/2022252 不能描述问题间的逻辑联系不能描述问题间的逻辑联系l例如，逻辑学中著名的三段论：例如，逻辑学中著名的三段论：P：凡人必死：凡人必死Q：张三是人：张三是人R：张三必死：张三必死 l在命题逻辑中：应该有在命题逻辑中：应该有(P Q) R，从而公式，从而公式(P Q)R应该是恒真的。应该是恒真的。l显然该公式不是恒真的，解释显然该公式不是恒真的，解释P，Q， R就能弄就能弄假该公式。假该公式。4/13/202226l原因：命题原因：命题R是和命题是和命题P, Q有关系的，只是这种关有关系的，只是这种关系在命题逻辑中无法表示。系在命题逻辑中无法表示。l因此，需要对命题的成分、结构和命题间的共同因此，需要对命题的成分、结构和命题间的共同特性等作进一步的分析，这正是谓词逻辑所要研特性等作进一步的分析，这正是谓词逻辑所要研究的问题。究的问题。4/13/202227l为了表示出这三个命题的内在关系，需要引进谓为了表示出这三个命题的内在关系，需要引进谓词的概念。词的概念。l例如，在前面的例子例如，在前面的例子“张三是人张三是人”中的中的“是人是人”是谓语，称为是谓语，称为谓词谓词，“张三张三”是主语，称为是主语，称为个体个体。4/13/202228二、谓词逻辑二、谓词逻辑可以独立存在的物体称为可以独立存在的物体称为个体个体。 如人、学生、桌子、自然数等都可以做个体。在谓词如人、学生、桌子、自然数等都可以做个体。在谓词演算中，个体通常指一个命题里的思维对象。演算中，个体通常指一个命题里的思维对象。4/13/202229例.D=2,3,4u设设P(x)：x大于大于3，则，则P(x)为一元谓词。为一元谓词。 指定元素指定元素-命题：命题：P(2)=F, P(3)=F, P(4)=Tu设设P(x,y)：x大于大于y,则则P(x,y)为二元谓词。为二元谓词。指定元素指定元素-命题：命题：P(2,3)=F, P(4,2)=Tu设设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)=F4/13/202230例.l用谓词的概念可将三段论做如下的符号化：用谓词的概念可将三段论做如下的符号化： 令令H(x)表示表示 “x是人是人”，M(x)表示表示 “x必死必死”。l 则三段论的三个命题表示如下：则三段论的三个命题表示如下：P： H(x)M(x)Q： H(张三张三)R： M(张三张三)4/13/202231l若想得到若想得到 “命题命题”P的否定的否定 “命题命题”，应该就是，应该就是“命题命题” P。但是，。但是， P= (H(x)M(x)= (H(x) M(x)=H(x) M(x)亦即，亦即，“命题命题”P的否定的否定 “命题命题”是是 “所有人都所有人都不死不死”。这和人们日常对命题。这和人们日常对命题 “所有人都必死所有人都必死”的否定的理解，相差得实在太远了的否定的理解，相差得实在太远了.4/13/202232l原因命题原因命题P的确切意思应该是：的确切意思应该是： “对任意对任意x，如果如果x是人，则是人，则x必死必死”。 但是但是H(x)M(x)中并没有确切的表示出中并没有确切的表示出 “对任意对任意x”这个意思，这个意思，亦即亦即H(x)M(x)不是一个命题。不是一个命题。 因此，在谓词因此，在谓词逻辑中除引进谓词外，还需要引进逻辑中除引进谓词外，还需要引进 “对任意对任意x”这个语句，及其对偶的语句这个语句，及其对偶的语句 “存在一个存在一个x”。 4/13/2022332 量词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(张三张三)4/13/202234l量词的语义规定量词的语义规定 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) 4/13/202235l例例.将下列命题符号化：将下列命题符号化：)一切事物都是发展变化的一切事物都是发展变化的 x F(x) 其中其中F(x)：x是发展变化的是发展变化的)存在着会说话的机器人存在着会说话的机器人 x(F(x) G(x)其中其中F(x)：x会说话会说话 G(x): x是机器人是机器人如果没有明确给出个体域，则认为个体域如果没有明确给出个体域，则认为个体域为一切事物。为一切事物。4/13/2022363) 每个计算机学院的学生都学离散数学。每个计算机学院的学生都学离散数学。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)4/13/2022375) 每个人都会犯错误每个人都会犯错误R(x):x是人是人P(x):x会犯错误会犯错误 x(R(x) P(x)4/13/2022383 约束变量、自由变量 4/13/2022394 约束变量的改名规则改名规则的理论依据改名规则的理论依据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)。亦即，谓词逻辑中命题的真值，与命题中的约束变量的亦即，谓词逻辑中命题的真值，与命题中的约束变量的记法无关。这就引出了谓词逻辑中的改名规则。记法无关。这就引出了谓词逻辑中的改名规则。 4/13/202240l改名规则：在由谓词，量词，逻辑联结词，括改名规则：在由谓词，量词，逻辑联结词，括号组成的有意义的符号串号组成的有意义的符号串( (公式公式) )中，可将其中中，可将其中出现的约束变量改为另一个约束变量，这种改出现的约束变量改为另一个约束变量，这种改名必须在量词作用区域内各处以及该量词符号名必须在量词作用区域内各处以及该量词符号中实行，并且改成的新约束变量要有别于改名中实行，并且改成的新约束变量要有别于改名区域中的所有其它变量。区域中的所有其它变量。l显然改名规则不改变原符号串的真值。显然改名规则不改变原符号串的真值。4/13/202241例:对于对于 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)4/13/2022425 封闭公式公式中无自由变量，或将自由变量看做常量。公式中无自由变量，或将自由变量看做常量。 (公式中每个变量的出现都是约束的）公式中每个变量的出现都是约束的）4/13/2022431) 常量符号常量符号：用小写英文字母：用小写英文字母a，b，c，表示，表示，当个体名称集合当个体名称集合D给出时，它可以是给出时，它可以是D中某个中某个元素。元素。2) 变量符号变量符号：用小写英文字母：用小写英文字母u，v，w，x，y，z，表示，当个体名称集合表示，当个体名称集合D给出时，给出时，D中中任任意元素意元素可代入变量符号。可代入变量符号。6 谓词逻辑形式化中使用的四种符号谓词逻辑形式化中使用的四种符号4/13/2022443) 函数符号函数符号：用小写英文字母：用小写英文字母f，g，表示，当表示，当个体名称集合个体名称集合D给出时，给出时，n元函数符号元函数符号f(x1，xn)可以是可以是Dn到到D的任意一个映射。的任意一个映射。4) 谓词符号谓词符号：用大写英文字母：用大写英文字母P，Q，R，表表示，当个体名称集合示，当个体名称集合D给出时，给出时，n元谓词符号元谓词符号P(x1，xn)可以是可以是Dn上的任意一个谓词。上的任意一个谓词。 4/13/2022457 项项谓词逻辑中的项，被递归定义为：谓词逻辑中的项，被递归定义为：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)是原子。是原子。4/13/2022469 公式公式4/13/20224710 公式的语义解释 4/13/202248例: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 T4/13/202249例: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=F4/13/20225011 谓词公式的恒真、恒假、可满足l公式公式G称为可满足的，如果存在解释称为可满足的，如果存在解释I，使，使G在在I下取下取 T值，简称值，简称I满足满足G。 若若I不满足不满足G，则简称，则简称I弄假弄假G。l公式公式G称为是恒假的称为是恒假的(或不可满足的或不可满足的)，如果不，如果不存在解释存在解释I满足满足G。l公式公式G称为恒真的，如果称为恒真的，如果G的所有解释的所有解释I都满足都满足G。 4/13/20225112 谓词逻辑的判定问题l谓词逻辑中公式恒真、恒假性的判断异常困难。谓词逻辑中公式恒真、恒假性的判断异常困难。原因？原因？谓词逻辑中的恒真谓词逻辑中的恒真(恒假恒假)公式，要求所有解释公式，要求所有解释I都满足都满足(弄弄假假)该公式。该公式。而解释而解释I依赖于一个非空集合依赖于一个非空集合D。由于集合由于集合D可以是无穷集合，而集合可以是无穷集合，而集合D的的 “数目数目”也可能也可能是是无穷多个。无穷多个。因此，所谓公式的因此，所谓公式的 “所有所有”解释，实际上是无法考虑的。解释，实际上是无法考虑的。l1936年年Church和和Turing分别独立地证明了：对于谓词分别独立地证明了：对于谓词逻辑，判定问题是不可解的。逻辑，判定问题是不可解的。4/13/202252l 谓词逻辑是半可判定的：谓词逻辑是半可判定的： 如果谓词逻辑中的公式是恒真的，则有算法如果谓词逻辑中的公式是恒真的，则有算法在有限步之内检验出这个公式的恒真性。如果在有限步之内检验出这个公式的恒真性。如果该公式不是恒真的该公式不是恒真的(当然也不是恒假的当然也不是恒假的)，则无，则无法在有限步内判定这个事实。法在有限步内判定这个事实。4/13/20225313 等价l公式公式G，H称为等价，记以称为等价，记以G=H，如果公式，如果公式GH是恒真的。是恒真的。l公式公式G，H等价的充要条件是：对等价的充要条件是：对G，H的任的任意解释意解释I，G，H在在I下的真值相同。下的真值相同。l因为对任意公式因为对任意公式G，H，在解释，在解释I下，下，G，H就就是两个命题，所以命题逻辑中给出的基本等价是两个命题，所以命题逻辑中给出的基本等价式，在谓词逻辑中仍然成立。式，在谓词逻辑中仍然成立。4/13/20225414 蕴涵4/13/202255基本蕴涵式：基本蕴涵式：(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)4/13/202256l例例.设设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。4/13/202257G= x(A(x)B(x)，H= x A(x) x B(x) ？ H G4/13/20225858设在一个含有凹室设在一个含有凹室(alcove)(alcove)的房间内，有桌子的房间内，有桌子A A和书架和书架B B，一个机器人，一个机器人(robot)(robot)和和 一叠书一叠书(book)(book)。现在要求机器人。现在要求机器人(robot)(robot)从凹室出发，把从凹室出发，把桌子桌子A A上的书搬到上的书搬到B B处书架上，完成任务后回到凹室。请用谓词逻辑描处书架上，完成任务后回到凹室。请用谓词逻辑描述机器人完成这一工作的全过程。述机器人完成这一工作的全过程。 谓词逻辑知识表示的例子4/13/20225959谓词逻辑知识表示的例子为了能够描述这个机器人世界的有关环境和状态变迁，要求必为了能够描述这个机器人世界的有关环境和状态变迁，要求必须先定义谓词。注意这里需要定义两类谓词：一类用来描述环境状态，须先定义谓词。注意这里需要定义两类谓词：一类用来描述环境状态，另一类谓词用来表示机器人的操作。另一类谓词用来表示机器人的操作。首先定义描述环境状态的谓词。首先定义描述环境状态的谓词。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 alcove ；ON(uON(u，x)x)： u u被放在被放在x x之上；之上；CLEAR(v)CLEAR(v)： v v上上( (中中) )是空的，是空的，v v的个体域：的个体域：aa，b b . .4/13/20226060谓词逻辑知识表示的例子使用谓词以及联结词、量词等来表示环境状态。使用谓词以及联结词、量词等来表示环境状态。这样，问题的初始状态可表示为：这样，问题的初始状态可表示为：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) 4/13/20226161谓词逻辑知识表示的例子从初始状态到达目标状态的变迁，必须由机器人从初始状态到达目标状态的变迁，必须由机器人一步一步地执行相应的操作序列，得以逐步实现。因此，一步一步地执行相应的操作序列，得以逐步实现。因此，必须要定义操作类谓词。仔细加以分析，必要的操作谓词必须要定义操作类谓词。仔细加以分析，必要的操作谓词共有三类。共有三类。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处放下书。处放下书。 一般说来，如果定义谓词太多，将造成信息冗余，增一般说来，如果定义谓词太多，将造成信息冗余，增加了问题的复杂度；如果定义谓词太少，就不够用。因此，加了问题的复杂度；如果定义谓词太少，就不够用。因此，定义的谓词性质与数量要合适。定义的谓词性质与数量要合适。 4/13/20226262谓词逻辑知识表示的例子按照行动规划，仔细选择操作，一步步进行状态替换，直到达到目标状态。即要求把状态变迁过程和操作序列记录下来，来描述问题解。下面写出该过程的最优路径： 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)4/13/20226363谓词逻辑知识表示的例子 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) （解毕） 4/13/20226464谓词逻辑知识表示的例子 AT(robot, alcove)EMPTY(robot)ON(books, b)CLEAR(a)TABLE(a)BOOKCASE (b) 这里顺便指出，若机器人智商不高，这个任务过程会这里顺便指出，若机器人智商不高，这个任务过程会产生许多冗余。比如，机器人拿着书，找不到产生许多冗余。比如，机器人拿着书，找不到b b处，无所处，无所适从而又扛回来了；或者适从而又扛回来了；或者等。可见，实际的机器人智等。可见，实际的机器人智能控制要更加复杂得多，虽然有时也很有趣。能控制要更加复杂得多，虽然有时也很有趣。 4/13/202265例例 将自然数公理符号化：将自然数公理符号化：A1：每一个数，有且仅有一个直接后继者；：每一个数，有且仅有一个直接后继者；A2：没有一个数使：没有一个数使0是直接后继者；是直接后继者；A3：对任意异于：对任意异于0的数，有且仅有一个直接先行者。的数，有且仅有一个直接先行者。解：令解：令f(x)表示表示x的直接后继者的直接后继者g(x)表示表示x的直接先行者的直接先行者E(x,y)表示表示x等于等于y谓词逻辑知识表示的例子4/13/202266于是将上述三个公理符号化如下：于是将上述三个公理符号化如下：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)4/13/202267解：令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)例例 已知某些病人喜欢所有的医生， 没有一个病人喜欢任意一个骗子。 证明任意一个医生都不是骗子。4/13/202268 剩下的任务就是调用某一过程证明A1A2B是一阶逻辑中的恒真公式，即B是A1、A2的逻辑结果。我们把它留到下一章中讨论。 4/13/20226969 逻辑知识表示的主要特点是建立在某种形式逻辑的基础上，并利用了逻辑方法研究推理的规律，即条件与结论之间的蕴涵关系。逻辑表示法的主要优点如下：（1 1）自然）自然 一阶谓词逻辑是一种接近于自然语言的形式语言系统，谓词一阶谓词逻辑是一种接近于自然语言的形式语言系统，谓词逻辑表示法接近于人们对问题的直观理解，易于被人们接受。逻辑表示法接近于人们对问题的直观理解，易于被人们接受。（2 2）明确）明确 逻辑表示法对如何由简单陈述句构造复杂陈述句的方法有明逻辑表示法对如何由简单陈述句构造复杂陈述句的方法有明确规定，如联结词、量词的用法与含义等。对于用逻辑表示法表确规定，如联结词、量词的用法与含义等。对于用逻辑表示法表示的知识，人们都可以按照一种标准的方法去解释它，因此用这示的知识，人们都可以按照一种标准的方法去解释它，因此用这种方法表示的知识明确、易于理解。种方法表示的知识明确、易于理解。谓词逻辑表示的特性谓词逻辑表示的特性4/13/20227070（3 3）精确）精确 谓词逻辑是一种二值逻辑，其谓词公式的真值只有谓词逻辑是一种二值逻辑，其谓词公式的真值只有“真真”与与“假假”，因此可用来表示精确知识，并可保证经演绎推理所得结，因此可用来表示精确知识，并可保证经演绎推理所得结论的精确性。论的精确性。（4 4）灵活）灵活 逻辑表示法把知识和处理知识的程序有效地分开。在使用这逻辑表示法把知识和处理知识的程序有效地分开。在使用这种方法表示知识时，无须考虑程序中处理知识的细节。种方法表示知识时，无须考虑程序中处理知识的细节。（5 5）模块化）模块化 在逻辑表示法中，各条知识都是相对独立的，它们之间不直在逻辑表示法中，各条知识都是相对独立的，它们之间不直接发生联系。因此添加、删除、修改知识的工作比较容易进行。接发生联系。因此添加、删除、修改知识的工作比较容易进行。谓词逻辑表示的特性谓词逻辑表示的特性4/13/20227171 逻辑表示法也存在一些不足，其主要缺点如下：（1）知识表示能力差 逻辑表示法只能表示确定性知识，而不能表示非确定性知识，如不精确、模糊性知识。实际上，人类的大部分知