逻辑学北大课04.pptx

主讲人：何向东-进入-第四章 谓词逻辑 第一第一节 谓词逻辑概述概述25八月20243命题逻辑和谓词逻辑命命题逻辑：不分析简单命题内部结构，讨论关于联结词的推理理论。例如：如果某甲作案，那么他一定有作案动机。某甲没有作案动机。所以，某甲没有作案。谓词逻辑：分析简单命题的内部结构，讨论关于量词的推理理论。例如：所有的作案者都有作案动机。某甲没有作案动机。所以，某甲不是作案者。25八月20244命题逻辑和谓词逻辑研究推理形式的有效性研究推理形式的有效性时，把命，把命题当做不可分的当做不可分的逻辑单位有位有时是不是不够的。的。例如：例如：（1）张三的朋友都是李四的朋友，王五不是李四的朋友。所以，王五不是张三的朋友。这个推理的形式在命题逻辑中表示为：P，q r这个推理事个推理事实上是有效的。但上是有效的。但仅用命用命题逻辑的理的理论不能表明它是有效的不能表明它是有效的推理。推理。（2）所有人都会死，张三是人，所以，张三会死。这是一个正确的三段论推理。但仅用命题逻辑的理论也不能表明它是有效推理。因此，要研究涉及量因此，要研究涉及量词的推理，的推理，仅用命用命题逻辑的理的理论是不是不够的。只有在的。只有在命命题逻辑的基的基础上上发展展谓词逻辑，才能解决，才能解决这类推理的有效性推理的有效性问题。25八月20245个体词和谓词谓词逻辑就是把命题分解为个体词、谓词、量词以及联结词的逻辑系统。例如：（3）我是学生。（4）王五不是李四的朋友。个体个体词：表示个体的：表示个体的语词，如：“我”、“王五”、“李四”。谓词：用来：用来说明个体明个体词的性的性质或关系的或关系的语词。如例（3）中“是学生”是一元谓词，例（4）“是的朋友”是二元谓词。类似的，还有三元谓词，如“在和之间”以及n元谓词。25八月20246个体词和谓词的符号化个体常个体常项：表示一定范围内确定的个体，记为小写的：表示一定范围内确定的个体，记为小写的：a,b,c,a,b,c,；个体个体变元：元：表示一定范围内不确定的个体，记为小写的：表示一定范围内不确定的个体，记为小写的：x,y,z,x,y,z,；个体域也称个体域也称论域：域：个体变元的变化范围，记为：个体变元的变化范围，记为：D D。谓词符号：符号：表示性质或关系的符号，记为大写：表示性质或关系的符号，记为大写：D D、E E、F F、GG；一元一元谓词公式，公式，记为：记为：DxDx，ExEx，FxFx，；二元二元谓词公式，公式，记为：记为：DxyDxy，ExyExy，HxyHxy，RxyRxy，；三元三元谓词公式，公式，记为：记为：GxyzGxyz，BxyzBxyz，PxyzPxyz，KxyzKxyz，；n n元元谓词公式公式，记为：记为：SxSx1 1x x2 2xxn n，WxWx1 1x x2 2xxn n，。个体个体词和和谓词的符号化的符号化实例例:用用a a表示表示“张三”，用，用DxDx表示一元表示一元谓词“会死”，则命命题“张三会死”可表示可表示为：DaDa。如是如是FxyFxy表示二元表示二元谓词“是的朋友”，那么：，那么：FabFab表示表示“a是b的朋友”;FabFab表示表示“a不是b的朋友”。25八月20247开语句P：是紫色的。Px：x是紫色的。让开开语句有真句有真值的方法：的方法：（1）用个体常项代替个体变元。用a表示“这朵玫瑰花”，则Pa表示语句“这朵玫瑰花是紫色的”。（2）对个体变元进行量化。例如:命题“存在玫瑰花是紫色的”为真。没有真假的命题函数，即从个体到真值的函数。例如没有真假的命题函数，即从个体到真值的函数。例如:25八月20248量词全称量全称量词：指称论域指称论域D D中个体的全部。中个体的全部。例如：所有，任何，每一个，例如：所有，任何，每一个，。存在量存在量词：指称论域指称论域D D中个体至少有一个存在。中个体至少有一个存在。例如：存在，有，有些，例如：存在，有，有些，。符号化的量符号化的量词：全称量词：所有所有x x，任何，任何x x，均记为：，均记为：x x。存在量词：有有x x，存在，存在x x，均记为：，均记为：x x。全称命全称命题：含有全称量词的命题。含有全称量词的命题。特称特称(存在存在)命命题：含有存在量词的命题。含有存在量词的命题。表示论域表示论域D中个体数量的语词中个体数量的语词25八月20249命题的形式化（1 1）凡事物都是）凡事物都是发展的。展的。用用x x表示个体词，用表示个体词，用D D表示表示“是发展的是发展的”，形式化为：，形式化为：xDxxDx（2 2）凡是自然数都大于零。）凡是自然数都大于零。用用N N表示表示“是自然数是自然数”，用，用E E表示表示“大于零大于零”，形式化为：，形式化为：x(Nxx(NxExEx）（3 3）所有大学生都不是儿童。）所有大学生都不是儿童。用用S S表示表示“是大学生是大学生”，用，用C C表示表示“是儿童是儿童”，形式化为：，形式化为：x(Sxx(SxCx)Cx)（4 4）有的大学生是儿童）有的大学生是儿童：x(Sx(SC C)（5 5）小李没有同任何人吵架。）小李没有同任何人吵架。a a：小李；：小李；：是人是人，D D：同同吵架吵架，形式化为：形式化为：x x（xx axax）（6 6）有些大一学生）有些大一学生认识小李。小李。a a：小李；：小李；F F：是大一学生，是大一学生，R R：认识认识，形式化为：，形式化为：x(FxRxa)x(FxRxa)25八月202410命题的形式化 在对以上命题形式化时，没有限制论域，即论域是全域。我们也可在一定的范围内讨论问题，因些个体变元的变域往往被限制在某个特定的范围内。（7）有的学生（）作对（）所有试题（）不限制不限制论域：域：x x（xx y(TyRxy)y(TyRxy)）限制限制论域：域：x x的变域的变域:X=:X=学生；学生；y y的变域的变域:Y=:Y=试题试题 则形式为则形式为:x x yRxyyRxy一一阶逻辑：量词是只对命题中的个体变元进行量化，而不量词是只对命题中的个体变元进行量化，而不对谓词变元进行量化。对谓词变元进行量化。高高阶谓词：不仅对个体变元而且对谓词变元进行量化。不仅对个体变元而且对谓词变元进行量化。第四章 谓词逻辑第二第二节 一一阶语言及其言及其语义解解释 25八月202412一阶语言L L（1 1）初始符号）初始符号个体变元符号：个体变元符号：x,y,z,x,y,z,；x x1 1,x,x2 2,；若干（可以为若干（可以为0 0个）个体常项符号：个）个体常项符号：a,b,ca,b,c若干（至少一个）谓词符号：若干（至少一个）谓词符号：D,E,F,G,RD,E,F,G,R，联结词符号：联结词符号：,；量词符号：量词符号：,；辅助符号：括号：（，）；逗号：，。辅助符号：括号：（，）；逗号：，。（2 2）形成）形成规则：包括项的形成规则和公式的形成规则。包括项的形成规则和公式的形成规则。项的形成的形成规则：单个的个体变元（单个的个体变元（v v，u u，w w，）和个体常项（）和个体常项（a a，b b，c c，）称为项。）称为项。25八月202413一阶语言L公式的形成公式的形成规则：1、如果R是n元谓词（n1）,t1tn是n个项，则Rt1tn是公式（原子公式）；2、如果A是公式，则A是公式；3、如果A和B是公式，则AB、AB、AB是公式；4、如果A是公式，v是个体变元，则vA和vA是公式（vA称为全称公式；vA称为存在（特称）公式）。一一阶语言言L 的一个符号串是（合式）公式，当且的一个符号串是（合式）公式，当且仅当它符合以上形成当它符合以上形成规则。一一阶语言言L 的全体（合式）公式，的全体（合式）公式，记为Form（L ）。）。一一阶语言言L 是形式是形式语言言L 的的扩充。充。（3 3）定）定义：用来表示符号串的用来表示符号串的缩写写。如：AB=df(AB)(BA)。25八月202414量词的辖域 量量词的的辖域：域：量词的作用范围。量词的作用范围。量量词的的辖域可定域可定义为：如果如果B B是是 vBvB和和 vBvB的子公式，则称的子公式，则称B B为量词为量词 v v和和 v v的辖域。的辖域。在公式中，量词的辖域是该量词及紧接该量词的最短公式。在公式中，量词的辖域是该量词及紧接该量词的最短公式。带横线部分指明了存在量词的辖域。(1)xxx(2)x（xyyy）(3)xy（xyxz（xzyz）25八月202415约束变元和自由变元变元的约束出现：一个变元在公式里的出现是一个变元在公式里的出现是约束的，当且仅当，这种出现是在采用该变元的约束的，当且仅当，这种出现是在采用该变元的量词的辖域内。量词的辖域内。变元的自由出现：一个变元在公式里的出现是一个变元在公式里的出现是自由的自由的,当且仅当，该变元的出现不是约束的。当且仅当，该变元的出现不是约束的。约束束变元就是元就是约束出束出现的的变元；自由元；自由变元就是自由元就是自由出出现的的变元。元。例如：在 xxx中，变元x出现了三次，前两次出现是在量词x的辖域中，因而是约束出现的，第三次是自由出现的。25八月202416自由变元的代入如果公式如果公式A A中有自由中有自由变元元v v，则把把该公式公式记为：A(v)A(v)。以个体。以个体词t t代入代入A(v)A(v)中中的的v v，则记为：A(v/t)A(v/t)。例如：。例如：（1）对于公式PxQx，用A(x)来表示x是自由变元：A(x)：PxQx；（2）对于公式x(QxRxy)，用B(y)来表示y是自由变元：B（y）：x(QxRxy)；（3）用个体变元y代替A(x)中的自由变元：A(x/y)：PyQy；（4）用常元a代替A(x)中的自由变元：A(x/a)：PaQa。自由自由变元的代入元的代入规则：(1)、代代换必必须处处进行行A(x)A(x)：PxQx PxQx 以y代换A(x)中的自由变元x：A(x/y)A(x/y)：PyQy PyQy（正确代换）A(x/y)A(x/y)：PxQy PxQy （错误代换）(2)、代、代换不能改不能改变量量词的的约束关系束关系B(y)B(y)：x(QxRxy)x(QxRxy)以个体变元来代换B(y)中的自由变元y：B(y/z)：x(QxRxz)（正确代换）B(y/x)：x(QxRxx)（错误代换）25八月202417一阶语言L L 的语义解释一、原子公式的解一、原子公式的解释：给定一个个体域给定一个个体域D D，将个体常项解释为个体域中特定的，将个体常项解释为个体域中特定的个体，个体，将谓词符号解释成这个个体域中的性质或这个个体将谓词符号解释成这个个体域中的性质或这个个体域上的关系，则原子公式是否为真可以归结为某个个体是域上的关系，则原子公式是否为真可以归结为某个个体是否具有某种性质或某些个体是否具有某种关系。否具有某种性质或某些个体是否具有某种关系。二、全称公式和特称公式的解二、全称公式和特称公式的解释：在给定的一个解释下，在给定的一个解释下，vAvA为真要求将为真要求将v v解释成个体域解释成个体域中任何个体时中任何个体时A A都为真，而都为真，而 vAvA为真，则只要将为真，则只要将v v解释成个体解释成个体域中至少一个个体时域中至少一个个体时A A为真。为真。严格地讲，一阶语言的语义解释就是在把个体词解释严格地讲，一阶语言的语义解释就是在把个体词解释成为个体域中的个体、把谓词解释为个体域中的性质或个成为个体域中的个体、把谓词解释为个体域中的性质或个体域上的关系的基础上，确定公式的真值即给公式赋值。体域上的关系的基础上，确定公式的真值即给公式赋值。25八月202418一阶语言L 的语义解释语义解解释也称也称为模型，模型，记为，包括以下内容：包括以下内容：(1)一个个体变元的取值范围非空集合D(论域、个体域)(2)对每个个体常项a，指定D中一个确定的个体a；(3)对每个n元谓词符号R，指定D上的一个n元关系R；在一个解在一个解释（模型）中，每个（模型）中，每个闭公式有确定的真公式有确定的真值。例如：D=自然数，个体常项a解释为4（a a=4）；一元谓词P解释为“是偶数（P P）”；二元谓词G解释为“”（G G=）；则：Pa的解释是“4是偶数”（真命题）；xPx的解释是“所有自然数是偶数”（假命题）；xyGyx的解释是“对所有自然数总存在大于它的自然数”(真命题)。25八月202419指派和赋值个体变元与它所指称的对象通过指派建立了确定的联系。个体变元与它所指称的对象通过指派建立了确定的联系。一个模型上的指派有无穷多个。一个模型上的指派有无穷多个。原子公式的值可以根据模型和指派确定。原子公式的值可以根据模型和指派确定。设是模型是模型上的指派，上的指派，v是是变元，元，d D。所。所谓模型模型上与指派上与指派相关相关联的指派的指派(v/d)是指如下定是指如下定义的指派：的指派：如果uv,则(v/d)(u)=(u)(v/d)(u)=(u)；如果；如果u=vu=v，则(v/d)(u)=d(v/d)(u)=d。不管原指派中v的值是什么，新指派(v/d)总是把v指派成d，而其余变元的值都不变。显然，如果d=(v)，则(v/d)=，即自己也是与其自身相关联的指派。给每个变元指定一个个体的过程称作指派，记为给每个变元指定一个个体的过程称作指派，记为25八月202420谓词逻辑的每个的每个项和公式在和公式在赋值下都有确定的下都有确定的值。项的基本的基本语义定定义:设=,是一个是一个赋值，t t是任意的是任意的项，t t在在下的下的值(t)(t)是是论域域D D中的个体，具体定中的个体，具体定义如下：如下：(1)(1)如果如果t t是个体是个体变元元v v，则(v)=(v)(v)=(v)；(2)(2)如果如果t t是个体常是个体常项a a，则(a)=a(a)=a。模型模型和和上的一个指派上的一个指派确定一个赋值确定一个赋值，记为，记为=25八月202421公式的基本语义定义设=,是一个是一个赋值，A A是任意的公式，是任意的公式，A A在在下的下的值记为(A)(A)。（A A）=T=T，或者，或者 （A A）=F=F。定。定义如下：如下：（1 1）如果）如果A A是原子公式是原子公式R(tR(t1 1t tn n)，则(A)=T(A)=T当且当且仅当当（t t1 1）,，(t(tn n)RR；（2 2）如果）如果A A是是 B B，则（A A）=T=T当且当且仅当当（B B）=F=F；（3 3）如果）如果A A是是BCBC，则（A A）=T=T当且当且仅当当（B B）=T=T且且（C C）=T=T；（4 4）如果）如果A A是是BCBC，则(A)=T(A)=T当且当且仅当当(B)=T(B)=T或或(C)=T(C)=T；（5 5）如果）如果A A是是BCBC，则(A)=T(A)=T当且当且仅当当(B)=F(B)=F或或(C)=T(C)=T；（6 6）如果）如果A A是是 vBvB，则(A)=T(A)=T当且当且仅当当对任何任何dD,dD,都有都有(v/d)(B)=T(v/d)(B)=T；（7 7）如果）如果A A是是 vBvB，则(A)=T(A)=T当且当且仅当存在当存在dD,dD,使得使得(v/d)(B)=T(v/d)(B)=T。25八月202422公式的基本语义定义基本基本语义解解释的直的直观意意义第（第（1 1）条只不过是说原子公式）条只不过是说原子公式R R（t t1 1ttn n）为真，只要）为真，只要t t1 1，t tn n所指对象具有所指对象具有D D上的关系上的关系R R。第（第（2 2）（5 5）条只不过说对联结词的解释与第二章中）条只不过说对联结词的解释与第二章中的解释相同。的解释相同。第（第（6 6）条不过是说）条不过是说 vBvB为真就是为真就是v v的值取遍论域时的值取遍论域时B B的值的值总为真。总为真。第（第（7 7）条也不过是说）条也不过是说 vBvB为真就是论域中至少有一个个体为真就是论域中至少有一个个体使使B B为真。为真。25八月202423公式的基本语义定义 设一一阶语言言L L 包包括括二二元元谓词符符号号G G，个个体体常常项a a和和b b，取取模模型型，使使得得个个体体域域D D是是整整数数，G G是是“”（整整数数上上的的小小于于关关系系），a a=10=10，b b=11=11。=,其其中中为：(x)=2，(y)=13，(z)=8 8，那么：那么：(Gab)=T(命题“1011”为真)；(Gay)=T T(命题“1013”为真)；(Gyx)=F F(命题“132”为假)。可可满足性足性 设A A是公式，是公式，是任意模型；如果存在是任意模型；如果存在赋值，使得，使得（A A）=T=T，则称模型称模型满足足A A，记为：=A=A，否，否则，称模型，称模型 不不满足足A A，记为：A A。协调性性 设是公式集是公式集(=A(=A1 1，A A2 2，A An n)，是任意模型；如果存在是任意模型；如果存在赋值，使得，使得（）=T=T（即（即（A A1 1）=T=T，（A A2 2）=T,=T,(A,(An n)=T)=T），），则称在模型称在模型 中中该公式集公式集是是协调的，否的，否则，称，称在模型在模型 中是不中是不协调的。的。25八月202424语义后承 设 是任意模型，是任意模型，L L 是所有是所有 构成的模型构成的模型类，是公式是公式集（集（=A1，A2，An），），B是公式。如果模型是公式。如果模型 上任上任何何赋值都都满足：只要足：只要 =（即（即（）=T），就有），就有 =B（即（即（B）=T），），则称（在模型称（在模型类C 中）中）B是是的的语义后承（后承（逻辑蕴涵涵B，或，或与与B具有具有语义推出关系，推出关系，推出推出B是有效的），是有效的），记为=L L B。如果在模型如果在模型 上存在上存在赋值，使得，使得 =，但，但 B，则称称B不是不是的的语义后承（后承（不能有效地推出不能有效地推出B，与与B没有没有语义推出关系），推出关系），记为 L L B。25八月202425应用实例 由由前前提提“（这架架飞机机上上）所所有有乘乘客客或或者者是是中中国国人人或或者者是是日日本本人人”能能否否有有效效地地推推出出结论“（这架架飞机机上上）所所有有乘乘客客是是中中国国人人，或或者者，所所有有乘乘客客是日本人是日本人”。以以（这架架飞机机上上）乘乘客客为论域域D D，以以P P、Q Q分分别表表示示一一元元谓词“是是中中国国人人”和和“是是日日本本人人”，则前提和前提和结论的形式分的形式分别是：是：A：x（PxQx），），B：xPx xQx 。25八月202426 取模型取模型，使得，使得D=d1,d2,d3,d4,d5,其中其中d1、d2、d3 中国人；中国人；d4、d5 日本人日本人,=是是 上的一个上的一个赋值，其中，其中为：(x)=d，d D；任取任取d D,都有都有(x/d)(Px Qx)=T,所以所以,(x（Px Qx)=T(即前提即前提“（这架架飞机上）所有乘机上）所有乘客或者是中国人或者是日本人客或者是中国人或者是日本人”为真真)；但是，存在但是，存在d D(例如，d4),使得使得(x/d)(Px)=F,也存在也存在d D(例如d1),使得使得(x/d)(Qx)=F，所以，所以，(xPx)=F，而且，而且(xQx)=F；因此，因此，(xPx xQx)=F（即（即结论“(这架架飞机上机上)所乘客所乘客是中国人，或者，所有乘客是日本人是中国人，或者，所有乘客是日本人”假），即：假），即：x（Px Qx）L xPx xQx。第四章 谓词逻辑第三第三节 谓词逻辑的自然推理系的自然推理系统QNP25八月202428谓词逻辑自然推理的一般步骤1、把给定的前提符号化（如果给定前提是自然语言的话）；2、用有关的规则消去量词；3、运用命题逻辑自然推理的规则，求出不带量词的结论；4、用有关规则给结论添上量词。25八月202429全称量词的推理 所有所有动物都有死，物都有死，所有虎都是所有虎都是动物，物，所以，所有虎都有死。所以，所有虎都有死。（）（）（）1（）（）（）2（）（）消去（）的全称量词（）（）消去（）的全称量词（）（）（）、()假言三段论（）（）（）（）引入全称量词25八月202430消去全称量词的推理规则 消去全称量消去全称量词的推理的推理规则也称全称例示也称全称例示规则（_ _）从 可推出(/)，其中(/）表示消去全称量词，并用个体词代替中的个体词的每一出现而得到的公式。对 _ _的限制：自由的限制：自由变元元带标记 在推理时，如果引进的前提或假设中有自由变元，在推理时，如果引进的前提或假设中有自由变元，那么，须在该前提或假设的右边注上标记。注有标那么，须在该前提或假设的右边注上标记。注有标记的变元叫做记的变元叫做“带标记的变元带标记的变元”。25八月202431引入全称量词的推理规则引入全称量引入全称量词的推理的推理规则也称全称概括也称全称概括规则（+）如果个体变元在公式中是不带标记的（即v不在前提和A依赖的假设中自由出现），那么可从推出。对个体变元进行全称概括是有条件的：必须不带标记。下面推理是无效的：下面推理是无效的：不加限制地使用+构造一个模型，使得D是自然数，谓词H解释为“小于3”。=，其中(x)=1。于是(Hx)=T（即前提“1小于3”是真的），而(xHx)=F，即结论的解释命题“所有自然数小于3”是假的。由此可由此可见，对带有有标记的个体的个体变元不能元不能进行全称概括。行全称概括。25八月202432全称量词推理规则的应用所有所有绝缘体体(x)x)都不能都不能导电（）。金属（）都（）。金属（）都导电，铝制品制品（）都是金属，所以，（）都是金属，所以，铝制品不是制品不是绝缘体。体。（）（）（）（）（）（）（）（），_（）（），_（）（），_（），H（+的假设）（），(6)，(7)，_（），(5)，(8)，_（），(4)，(9)，_（）(7)(10)，+（）（）(11)，+25八月202433存在量词的推理规则（）（）A（）（）(1),_从（）到（）不是有效的逻辑推理：构造一个模型 使得D是自然数，一元谓词F解释为“大于1”。=,其中，（x）=1。于是(xFx)=T,即（）的解释“有的自然数大于1”是真的，而(Fx)=F,即（）的解释“大于”是假的。因此，从不能推出。断定了至少有一个具有性质的个体存在。但是，这一个体是不确定的，不能断定它就是某个具体的个体，因此，可以用符号：，；1，2，表示不确定个体不确定个体。F意指：“不确定个体有性质”。从而，可以从推出25八月202434存在量词的推理规则消去存在量消去存在量词的推理的推理规则 消去存在量消去存在量词的推理的推理规则也称也称为存在例示存在例示规则（_）从可推出（），称为新名，即在前的公式中没有出现过的不确定个体的名称，并且须带标记。引入存在量引入存在量词的推理的推理规则 引入存在量引入存在量词的推理的推理规则规则也称也称为存在概括存在概括规则（+）从（t）可推出。其中，t可以是不确定个体的名称，也可以是个体常项或个体变元。25八月202435关于存在量词推理的应用 x(HxGx)，xHx xGx（）（）（）（），（），（），_（）（），（），_（），（，（3），（），（4），），_（）（），（），+25八月202436关于存在量词推理的应用所有哺乳所有哺乳动物（）是物（）是动物（），有的哺乳物（），有的哺乳动物是水物是水生的（），所以，有的生的（），所以，有的动物是水生的。物是水生的。（）（）（）（）（），（），_（）（），_（），（），_（），（4），（5），_（），（），_（），（），（），+（）（）（），+25八月202437_规则的限制（1 1）不确定个体的名称必）不确定个体的名称必须是没有出是没有出现过的新名的新名（2 2）新名必）新名必须带标记。（）（）（），（），_ （），（），_ （）,（3）,（4），_ （6）（）（），_这个形式推理中，违反了_的第一个限制，因而造成指称混乱，导致推理无效。25八月202438_规则的限制第二个限制（新名必第二个限制（新名必须带标记）的理由：）的理由：如果新名不带标记，那么对它也可进行全称概括：从“某个体有性质”推出“所有个体都有性质”，这当然是荒谬的。所以，在用-规则进行推导时，均带标记，并且，依赖带标记公式的各公式，其中如有，亦须带标记。一旦新名从公式中消失后，就应同时消去该新名的标记。25八月202439关于量词推理的应用所有中文系学生（）都喜所有中文系学生（）都喜欢（）任何（）任何艺术家（），没有中文系学生喜家（），没有中文系学生喜欢任何数学家任何数学家（），有中文系学生。所以，没有（），有中文系学生。所以，没有艺术家是数家是数学家。学家。（1）（）A1（2）（）A2（3）A3（4）,(),_（5）（）()，_25八月202440（6）(zz)(2),_（7）y（）,(4),(5)，_（8）(zz),(4),(6)，_（9）,(7),_（0）Ey ,(8),_（1）Ey ,(10),RP.（2）Ey,(9),(11),HS（3）y（Ey）(12),+25八月202441量词的推理规则的进一步限制限制一：限制一：运用运用-和和+时，必，必须遵守个体遵守个体变元的代元的代入入规则。限制二：限制二：运用运用 _ _规则时，公式中可能有的自由个，公式中可能有的自由个体体变元均元均应记为新名的新名的标记的下的下标。合理代合理代换：不改不改变原公式量原公式量词的的约束关系的代束关系的代换。不合理代不合理代换（盲目代（盲目代换）：）：改改变原公式量原公式量词的的约束关系的代束关系的代换。25八月202442违反量词推理规则的应用举例下面是下面是错误地运用地运用 _ _的推理：的推理：（）xyGxy A1（）yGyy （1）,_（x/y）构造一个模型，使得D是自然数，谓词G解释为“小于”。=。于是:（xyGxy）=T,即（1）的解释“没有最大的自然数”是真的，而（yGyy）=F，即(2)的解释“有小于自己的自然数”是假的。这个推理之所以无效，是由于对（1）_时进行了盲目的代换，x本来不受y的约束，但以y代换x后，代入y的却被y约束了。25八月202443违反量词推理规则的应用举例下面是下面是错误运用运用+的推理：的推理：在包括运算符“+”的一阶语言L中，进行如下推理：（1）（）A1（2）（），（1），_（3）（）（2），+构造一个模型，使得D是实数，谓词解释成“”，那么（1）的解释是真的。（3）的解释是假的。原因是对（2）错误地运用了+，（2）中不受约束的，代换后被约束。25八月202444QNP系统的语形(语法)推出关系 谓词逻辑的自然推理系的自然推理系统QNPQNP是一个根据量是一个根据量词和和联结词的推的推导规则，运用有前提的形式推演构建起，运用有前提的形式推演构建起来的形式系来的形式系统。关于量关于量词的否定的否定规律：律：Q1：xAx A；Q2：xAx A；Q3：xA x A；Q4：xA x A。25八月202445QNP系统的语形(语法)推出关系Q1的的证明明先先证：xAx A：（1）xA(x)A(x是A中自由变元)（2）xA(x)H （3）xA(X)(2)，_ （4）A()，(3)，_ （5）A()(1)，_ （6）A()A()，(3)，(4)，+(7)xA(x)(2)(6)，_(消去H)25八月202446QNP系统的语形(语法)推出关系Q1的的证明明再再证：x x A A xA:xA:(1)xA(x)A(x是A的自由变元)(2)xA(x)H1 (3)A(x)x，H2 (4)xA(x)(3)，+(5)A(x)xA(x)(3)(4)，+(消去H2)(6)A（x）(1)，(5)，M.T.(7)A(x)(6)，_ (8)xA(x)(7)，+(9)xA(x)xA(x)(2)，(8)，+(10)xA(x)(2)(9)，_(消去H1)25八月202447QNP系统的语形(语法)推出关系设A是任何公式，是任何公式，x在在A中不自由，我中不自由，我们有有:Q5：A xAQ6：xAAQ7a：xA yA(x/y)(y不在不在A中出中出现)Q7b：yA xA(y/x)(x不在不在A中出中出现)Q8a：xA yA(x/y)(y不在不在A中出中出现)Q8b：yA xA(y/x)(x不在不在A中出中出现)改名规则：改变量词所约束的变元的置换规则。由于 xA yA(x/y),xA yA(x/y),因此，我们可以用等价置换规则把一个公式中出现的 xA置换为 yA(x/y),或者把 xA置换为 yA（x/y）。25八月202448QNP系统的语形(语法)推出关系Q9：x yA y xA；Q10：x y y xA；Q11：x yA y xA；（1）xyA(x,y)A(x,y是A中自由变元）（2）yA(,y),(1),-（3）A(,y),(2),-（4）xA(x,y)(3),+（5）yxA(x,y)(4),+Q12：x(A B)xA xB (x对的分配律的分配律)Q13：x(A B)xA xB (x对的分配律的分配律)25八月202449QNP系统的语形(语法)推出关系Q13的的证明明先先证：x(A B)xA xB(1)x(AB)A (2)(xAxB)H (3)A()B(),(1),_ (4)xAxB (2),R.P.(De.M）(5)xAxB (4),R.P.(Q3)(6)xA (5),_ (7)xB (5),_ (8)A()(6),_ (9)B()(7),_ (10)B(),(3),(8),_ (11)B()B(),(9),(10),+(12)xAxB (2)(11),_(消去H)25八月202450QNP系统的语形(语法)推出关系Q13的的证明明再再证:xA xB x(A B)(1)xAxB A (2)x(AB)H (3)x(AB)(2),R.P.(Q3)(4)x(AB)(3),R.P.(DeM.)(5)xAB (4),R.P.(Q12)(6)xA (5),_ (7)xA (6),R.P.(Q3)(8)xB (5),_ (9)xB (8),R.P.(Q3)(10)xB (1),(7),_ (11)xBxB (9),(10),+(12)x(AB)(2)(11)，_(消去H)25八月202451QNP系统的语形(语法)推出关系Q14：x(AB)xA xBQ15：x(AB)xA xBQ14：x(AB)xA xBQ15：x(AB)xA xB只只证Q14：（1）x(AB)A (2)xA H (3)AB (1),_ (4)A (2),_ (5)B (3),(4),_ (6)xB (5),+(7)xAxB (2)(6),+(消去H)25八月202452QNP系统的语形(语法)推出关系Q16：xA xB x(A B)Q17：x(A B)xA xB但是，但是，Q16和和Q17反反过来不成立，即：来不成立，即：x(A B)xA xB xA xB x(A B)对任意的公式任意的公式A和和B，如果，如果x不在不在B中自由出中自由出现，那么，我，那么，我们有：有：Q18：x(A B)xA B Q19：x(A B)xA B Q20：x(A B)xA B Q21：x(A B)xA B Q22：x(AB)xAB Q23：x(AB)xAB Q24：x(BA)B xA Q25：x(BA)B xA25八月202453量词和联结词辖域之间的联系和转化 分析命分析命题A A“只有千里只有千里马吃吃饱草，千里草，千里马才能才能跑跑”和命和命题B B“或者千里或者千里马吃吃饱草，或者千里草，或者千里马不能不能跑跑”的的逻辑形式和它形式和它们之之间的的逻辑关系。关系。以千里马为论域D，这两个命题的形式可以表示为(Px：x吃饱草；Qx：x能跑)：A:x(PxQx)(或者x(PxQx)；B:x(PxQx)。但是，A和B的形式决不能分析为：*A：xPxxQx；*B:xPxxQx；25八月202454根据量根据量词和和联结词辖域之域之间联系和系和转化的化的逻辑规律，律，我我们有：有：反之反之则不成立。不成立。而且，我而且，我们还有：有：反之也不成立。反之也不成立。并且可以并且可以证明和是可明和是可证等价的：等价的：x(x(PxPx Qx)Qx)x(Pxx(Px Qx)Qx)xPxxPx x x QxQx x(Pxx(Px Qx)Qx)x(x(PxPx Qx)Qx)x x PxPx x QxQx量词和联结词辖域之间的联系和转化25八月202455量词和联结词辖域之间的联系和转化 分析命分析命题A A：“如果有人找我，你就如果有人找我，你就说我不在我不在家家”和命和命题B B：“对任何找我的人，你都任何找我的人，你都说我不在我不在家家”的命的命题形式和它形式和它们的的逻辑关系。关系。以“（某特定范围的）人”为论域D，以个体常项a表示“我”这个特定个体，以R表示这个论域上的“找”这种二元关系，以B表示命题“你说我不在家”，那么，它们的形式可分析为：A：xRxaB(x在B中不自由)B：x(RxaB)（x在B中不自由）AA和和BB具有可具有可证等价关系，从等价关系，从A A和和B B而是等而是等值的。的。25八月202456量词和联结词辖域之间的联系和转化先先证：xRxaB x(RxaB)：(1)xRxaB A (2)Rxa x,H (3)xRxa (2)，+(4)B (1)，(3),_(5)RxaB (2)(4)，+(消去H)(6)x(RxaB)(5)，+25八月202457量词和联结词辖域之间的联系和转化再再证:x(RxaB)xRxaB：(1)x(RxaB)A (2)xRxa H (3)Ra ，(2)，_ (4)RaB (1)，_ (5)B (3)，(4)_(6)xRxaB (2)(5)，+(消去H)25八月202458QNP系统的可靠性和完全性QNP系系统的可靠性定理：的可靠性定理：凡是凡是QNPQNP系统中的语法系统中的语法推出关系都是语义推出关系。推出关系都是语义推出关系。可靠性定理的作用：可靠性定理的作用：保证我们只能从真前提得出保证我们只能从真前提得出真结论，决不会得出假结论甚至逻辑矛盾。真结论，决不会得出假结论甚至逻辑矛盾。QNP系系统的完全性：的完全性：凡是凡是QNPQNP系统中的语义推出系统中的语义推出关系都是语法推出关系。关系都是语法推出关系。完全性的作用：完全性的作用：凡是关于量词的语义推出关系，凡是关于量词的语义推出关系，都表现为都表现为QNPQNP的语法推出关系。在的语法推出关系。在QNPQNP系统外，再没系统外，再没有从真前提推出真结论的关于量词的推理了。有从真前提推出真结论的关于量词的推理了。25八月202459本章小结基本内容基本内容谓词逻辑、个体、个体词、谓词、量、量词。一一阶语言的言的语义解解释。谓词逻辑的推理的推理规则。自然推理系自然推理系统QNP。重重难点点语义解解释、语形与形与语义的关系。的关系。运用运用谓词逻辑的推的推导规则进行形式推演。行形式推演。