逻辑学(北大精品课)04.ppt

ACourseinLogic,主讲人：何向东,-进入-,逻辑学教程,第四章谓词逻辑,第一节谓词逻辑概述,2020年5月30日星期六,3,命题逻辑和谓词逻辑,命题逻辑：不分析简单命题内部结构，讨论关于联结词的推理理论。例如：如果某甲作案，那么他一定有作案动机。某甲没有作案动机。所以，某甲没有作案。谓词逻辑：分析简单命题的内部结构，讨论关于量词的推理理论。例如：所有的作案者都有作案动机。某甲没有作案动机。所以，某甲不是作案者。,2020年5月30日星期六,4,命题逻辑和谓词逻辑,研究推理形式的有效性时，把命题当做不可分的逻辑单位有时是不够的。例如：（1）张三的朋友都是李四的朋友，王五不是李四的朋友。所以，王五不是张三的朋友。这个推理的形式在命题逻辑中表示为：P，qr这个推理事实上是有效的。但仅用命题逻辑的理论不能表明它是有效的推理。（2）所有人都会死，张三是人，所以，张三会死。这是一个正确的三段论推理。但仅用命题逻辑的理论也不能表明它是有效推理。因此，要研究涉及量词的推理，仅用命题逻辑的理论是不够的。只有在命题逻辑的基础上发展谓词逻辑，才能解决这类推理的有效性问题。,2020年5月30日星期六,5,个体词和谓词,谓词逻辑就是把命题分解为个体词、谓词、量词以及联结词的逻辑系统。例如：（3）我是学生。（4）王五不是李四的朋友。个体词：表示个体的语词，如：“我”、“王五”、“李四”。谓词：用来说明个体词的性质或关系的语词。如例（3）中“是学生”是一元谓词，例（4）“是的朋友”是二元谓词。类似的，还有三元谓词，如“在和之间”以及n元谓词。,2020年5月30日星期六,6,个体词和谓词的符号化,个体常项：表示一定范围内确定的个体，记为小写的：a,b,c,；个体变元：表示一定范围内不确定的个体，记为小写的：x,y,z,；个体域也称论域：个体变元的变化范围，记为：D。谓词符号：表示性质或关系的符号，记为大写：D、E、F、G；一元谓词公式，记为：Dx，Ex，Fx，；二元谓词公式，记为：Dxy，Exy，Hxy，Rxy，；三元谓词公式，记为：Gxyz，Bxyz，Pxyz，Kxyz，；n元谓词公式，记为：Sx1x2xn，Wx1x2xn，。个体词和谓词的符号化实例:用a表示“张三”，用Dx表示一元谓词“会死”，则命题“张三会死”可表示为：Da。如是Fxy表示二元谓词“是的朋友”，那么：Fab表示“a是b的朋友”;Fab表示“a不是b的朋友”。,2020年5月30日星期六,7,开语句,P：是紫色的。Px：x是紫色的。让开语句有真值的方法：（1）用个体常项代替个体变元。用a表示“这朵玫瑰花”，则Pa表示语句“这朵玫瑰花是紫色的”。（2）对个体变元进行量化。例如:命题“存在玫瑰花是紫色的”为真。,没有真假的命题函数，即从个体到真值的函数。例如:,2020年5月30日星期六,8,量词,全称量词：指称论域D中个体的全部。例如：所有，任何，每一个，。存在量词：指称论域D中个体至少有一个存在。例如：存在，有，有些，。符号化的量词：全称量词：所有x，任何x，均记为：x。存在量词：有x，存在x，均记为：x。全称命题：含有全称量词的命题。特称(存在)命题：含有存在量词的命题。,表示论域D中个体数量的语词,2020年5月30日星期六,9,命题的形式化,（1）凡事物都是发展的。用x表示个体词，用D表示“是发展的”，形式化为：xDx（2）凡是自然数都大于零。用N表示“是自然数”，用E表示“大于零”，形式化为：x(NxEx）（3）所有大学生都不是儿童。用S表示“是大学生”，用C表示“是儿童”，形式化为：x(SxCx)（4）有的大学生是儿童：x(SC)（5）小李没有同任何人吵架。a：小李；：是人，D：同吵架，形式化为：x（xax）（6）有些大一学生认识小李。a：小李；F：是大一学生，R：认识，形式化为：x(FxRxa),2020年5月30日星期六,10,命题的形式化,在对以上命题形式化时，没有限制论域，即论域是全域。我们也可在一定的范围内讨论问题，因些个体变元的变域往往被限制在某个特定的范围内。（7）有的学生（）作对（）所有试题（）不限制论域：x（xy(TyRxy)）限制论域：x的变域:X=学生；y的变域:Y=试题则形式为:xyRxy一阶逻辑：量词是只对命题中的个体变元进行量化，而不对谓词变元进行量化。高阶谓词：不仅对个体变元而且对谓词变元进行量化。,第四章谓词逻辑,第二节一阶语言及其语义解释,2020年5月30日星期六,12,一阶语言L,（1）初始符号个体变元符号：x,y,z,；x1,x2,；若干（可以为0个）个体常项符号：a,b,c若干（至少一个）谓词符号：D,E,F,G,R，联结词符号：,；量词符号：,；辅助符号：括号：（，）；逗号：，。（2）形成规则：包括项的形成规则和公式的形成规则。项的形成规则：单个的个体变元（v，u，w，）和个体常项（a，b，c，）称为项。,2020年5月30日星期六,13,一阶语言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）定义：用来表示符号串的缩写。如：AB=df(AB)(BA)。,2020年5月30日星期六,14,量词的辖域,量词的辖域：量词的作用范围。量词的辖域可定义为：如果B是vB和vB的子公式，则称B为量词v和v的辖域。在公式中，量词的辖域是该量词及紧接该量词的最短公式。带横线部分指明了存在量词的辖域。(1)xxx(2)x（xyyy）(3)xy（xyxz（xzyz）,2020年5月30日星期六,15,约束变元和自由变元,变元的约束出现：一个变元在公式里的出现是约束的，当且仅当，这种出现是在采用该变元的量词的辖域内。变元的自由出现：一个变元在公式里的出现是自由的,当且仅当，该变元的出现不是约束的。约束变元就是约束出现的变元；自由变元就是自由出现的变元。例如：在xxx中，变元x出现了三次，前两次出现是在量词x的辖域中，因而是约束出现的，第三次是自由出现的。,2020年5月30日星期六,16,自由变元的代入,如果公式A中有自由变元v，则把该公式记为：A(v)。以个体词t代入A(v)中的v，则记为：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)：PxQx以y代换A(x)中的自由变元x：A(x/y)：PyQy（正确代换）A(x/y)：PxQy（错误代换）(2)、代换不能改变量词的约束关系B(y)：x(QxRxy)以个体变元来代换B(y)中的自由变元y：B(y/z)：x(QxRxz)（正确代换）B(y/x)：x(QxRxx)（错误代换）,2020年5月30日星期六,17,一阶语言L的语义解释,一、原子公式的解释：给定一个个体域D，将个体常项解释为个体域中特定的个体，将谓词符号解释成这个个体域中的性质或这个个体域上的关系，则原子公式是否为真可以归结为某个个体是否具有某种性质或某些个体是否具有某种关系。二、全称公式和特称公式的解释：在给定的一个解释下，vA为真要求将v解释成个体域中任何个体时A都为真，而vA为真，则只要将v解释成个体域中至少一个个体时A为真。严格地讲，一阶语言的语义解释就是在把个体词解释成为个体域中的个体、把谓词解释为个体域中的性质或个体域上的关系的基础上，确定公式的真值即给公式赋值。,2020年5月30日星期六,18,一阶语言L的语义解释,语义解释也称为模型，记为，包括以下内容：(1)一个个体变元的取值范围非空集合D(论域、个体域)(2)对每个个体常项a，指定D中一个确定的个体a；(3)对每个n元谓词符号R，指定D上的一个n元关系R；在一个解释（模型）中，每个闭公式有确定的真值。例如：D=自然数，个体常项a解释为4（a=4）；一元谓词P解释为“是偶数（P）”；二元谓词G解释为“”（G=）；则：Pa的解释是“4是偶数”（真命题）；xPx的解释是“所有自然数是偶数”（假命题）；xyGyx的解释是“对所有自然数总存在大于它的自然数”(真命题)。,2020年5月30日星期六,19,指派和赋值,个体变元与它所指称的对象通过指派建立了确定的联系。一个模型上的指派有无穷多个。原子公式的值可以根据模型和指派确定。设是模型上的指派，v是变元，dD。所谓模型上与指派相关联的指派(v/d)是指如下定义的指派：如果uv,则(v/d)(u)=(u)；如果u=v，则(v/d)(u)=d。不管原指派中v的值是什么，新指派(v/d)总是把v指派成d，而其余变元的值都不变。显然，如果d=(v)，则(v/d)=，即自己也是与其自身相关联的指派。,给每个变元指定一个个体的过程称作指派，记为,2020年5月30日星期六,20,谓词逻辑的每个项和公式在赋值下都有确定的值。项的基本语义定义:设=,是一个赋值，t是任意的项，t在下的值(t)是论域D中的个体，具体定义如下：(1)如果t是个体变元v，则(v)=(v)；(2)如果t是个体常项a，则(a)=a。,模型和上的一个指派确定一个赋值，记为=,2020年5月30日星期六,21,公式的基本语义定义,设=,是一个赋值，A是任意的公式，A在下的值记为(A)。（A）=T，或者（A）=F。定义如下：（1）如果A是原子公式R(t1tn)，则(A)=T当且仅当（t1）,，(tn)R；（2）如果A是B，则（A）=T当且仅当（B）=F；（3）如果A是BC，则（A）=T当且仅当（B）=T且（C）=T；（4）如果A是BC，则(A)=T当且仅当(B)=T或(C)=T；（5）如果A是BC，则(A)=T当且仅当(B)=F或(C)=T；（6）如果A是vB，则(A)=T当且仅当对任何dD,都有(v/d)(B)=T；（7）如果A是vB，则(A)=T当且仅当存在dD,使得(v/d)(B)=T。,2020年5月30日星期六,22,公式的基本语义定义,基本语义解释的直观意义第（1）条只不过是说原子公式R（t1tn）为真，只要t1，tn所指对象具有D上的关系R。第（2）（5）条只不过说对联结词的解释与第二章中的解释相同。第（6）条不过是说vB为真就是v的值取遍论域时B的值总为真。第（7）条也不过是说vB为真就是论域中至少有一个个体使B为真。,2020年5月30日星期六,23,公式的基本语义定义,设一阶语言L包括二元谓词符号G，个体常项a和b，取模型，使得个体域D是整数，G是“”（整数上的小于关系），a=10，b=11。=,其中为：(x)=2，(y)=13，(z)=8，那么：(Gab)=T(命题“1011”为真)；(Gay)=T(命题“1013”为真)；(Gyx)=F(命题“132”为假)。可满足性设A是公式，是任意模型；如果存在赋值，使得（A）=T，则称模型满足A，记为：=A，否则，称模型不满足A，记为：A。协调性设是公式集(=A1，A2，An)，是任意模型；如果存在赋值，使得（）=T（即（A1）=T，（A2）=T,(An)=T），则称在模型中该公式集是协调的，否则，称在模型中是不协调的。,2020年5月30日星期六,24,语义后承,设是任意模型，L是所有构成的模型类，是公式集（=A1，A2，An），B是公式。如果模型上任何赋值都满足：只要=（即（）=T），就有=B（即（B）=T），则称（在模型类C中）B是的语义后承（逻辑蕴涵B，或与B具有语义推出关系，推出B是有效的），记为=LB。如果在模型上存在赋值，使得=，但B，则称B不是的语义后承（不能有效地推出B，与B没有语义推出关系），记为LB。,2020年5月30日星期六,25,应用实例,由前提“（这架飞机上）所有乘客或者是中国人或者是日本人”能否有效地推出结论“（这架飞机上）所有乘客是中国人，或者，所有乘客是日本人”。以（这架飞机上）乘客为论域D，以P、Q分别表示一元谓词“是中国人”和“是日本人”，则前提和结论的形式分别是：A：x（PxQx），B：xPxxQx。,2020年5月30日星期六,26,取模型，使得D=d1,d2,d3,d4,d5,其中d1、d2、d3中国人；d4、d5日本人,=是上的一个赋值，其中为：(x)=d，dD；任取dD,都有(x/d)(PxQx)=T,所以,(x（PxQx)=T(即前提“（这架飞机上）所有乘客或者是中国人或者是日本人”为真)；但是，存在dD(例如，d4),使得(x/d)(Px)=F,也存在dD(例如d1),使得(x/d)(Qx)=F，所以，(xPx)=F，而且(xQx)=F；因此，(xPxxQx)=F（即结论“(这架飞机上)所乘客是中国人，或者，所有乘客是日本人”假），即：x（PxQx）LxPxxQx。,第四章谓词逻辑,第三节谓词逻辑的自然推理系统QNP,2020年5月30日星期六,28,谓词逻辑自然推理的一般步骤,1、把给定的前提符号化（如果给定前提是自然语言的话）；2、用有关的规则消去量词；3、运用命题逻辑自然推理的规则，求出不带量词的结论；4、用有关规则给结论添上量词。,2020年5月30日星期六,29,全称量词的推理,所有动物都有死，所有虎都是动物，所以，所有虎都有死。（）（）1（）（）2（）消去（）的全称量词（）消去（）的全称量词（）（）、()假言三段论（）（）（）引入全称量词,2020年5月30日星期六,30,消去全称量词的推理规则,消去全称量词的推理规则也称全称例示规则（_）从可推出(/)，其中(/）表示消去全称量词，并用个体词代替中的个体词的每一出现而得到的公式。对_的限制：自由变元带标记在推理时，如果引进的前提或假设中有自由变元，那么，须在该前提或假设的右边注上标记。注有标记的变元叫做“带标记的变元”。,2020年5月30日星期六,31,引入全称量词的推理规则,引入全称量词的推理规则也称全称概括规则（+）如果个体变元在公式中是不带标记的（即v不在前提和A依赖的假设中自由出现），那么可从推出。对个体变元进行全称概括是有条件的：必须不带标记。下面推理是无效的：不加限制地使用+构造一个模型，使得D是自然数，谓词H解释为“小于3”。=，其中(x)=1。于是(Hx)=T（即前提“1小于3”是真的），而(xHx)=F，即结论的解释命题“所有自然数小于3”是假的。由此可见，对带有标记的个体变元不能进行全称概括。,2020年5月30日星期六,32,全称量词推理规则的应用,所有绝缘体(x)都不能导电（）。金属（）都导电，铝制品（）都是金属，所以，铝制品不是绝缘体。（）（）（）（）（）（）（）（），_（）（），_（）（），_（），H（+的假设）（），(6)，(7)，_（），(5)，(8)，_（），(4)，(9)，_（）(7)(10)，+（）（）(11)，+,2020年5月30日星期六,33,存在量词的推理规则,（）A（）(1),_从（）到（）不是有效的逻辑推理：构造一个模型使得D是自然数，一元谓词F解释为“大于1”。=,其中，（x）=1。于是(xFx)=T,即（）的解释“有的自然数大于1”是真的，而(Fx)=F,即（）的解释“大于”是假的。因此，从不能推出。断定了至少有一个具有性质的个体存在。但是，这一个体是不确定的，不能断定它就是某个具体的个体，因此，可以用符号：，；1，2，表示不确定个体。F意指：“不确定个体有性质”。从而，可以从推出,2020年5月30日星期六,34,存在量词的推理规则,消去存在量词的推理规则消去存在量词的推理规则也称为存在例示规则（_）从可推出（），称为新名，即在前的公式中没有出现过的不确定个体的名称，并且须带标记。引入存在量词的推理规则引入存在量词的推理规则规则也称为存在概括规则（+）从（t）可推出。其中，t可以是不确定个体的名称，也可以是个体常项或个体变元。,2020年5月30日星期六,35,关于存在量词推理的应用,x(HxGx)，xHxxGx（）（）（）（），（），_（）（），_（），（3），（4），_（）（），+,2020年5月30日星期六,36,关于存在量词推理的应用,所有哺乳动物（）是动物（），有的哺乳动物是水生的（），所以，有的动物是水生的。（）（）（）（）（），（），_（）（），_（），（），_（），（4），（5），_（），（），_（），（），（），+（）（）（），+,2020年5月30日星期六,37,_规则的限制,（1）不确定个体的名称必须是没有出现过的新名（2）新名必须带标记。（）（）（），（），_（），（），_（）,（3）,（4），_（6）（）（），_这个形式推理中，违反了_的第一个限制，因而造成指称混乱，导致推理无效。,2020年5月30日星期六,38,_规则的限制,第二个限制（新名必须带标记）的理由：如果新名不带标记，那么对它也可进行全称概括：从“某个体有性质”推出“所有个体都有性质”，这当然是荒谬的。所以，在用-规则进行推导时，均带标记，并且，依赖带标记公式的各公式，其中如有，亦须带标记。一旦新名从公式中消失后，就应同时消去该新名的标记。,2020年5月30日星期六,39,关于量词推理的应用,所有中文系学生（）都喜欢（）任何艺术家（），没有中文系学生喜欢任何数学家（），有中文系学生。所以，没有艺术家是数学家。（1）（）A1（2）（）A2（3）A3（4）,(),_（5）（）()，_,2020年5月30日星期六,40,（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),+,2020年5月30日星期六,41,量词的推理规则的进一步限制,限制一：运用-和+时，必须遵守个体变元的代入规则。限制二：运用_规则时，公式中可能有的自由个体变元均应记为新名的标记的下标。合理代换：不改变原公式量词的约束关系的代换。不合理代换（盲目代换）：改变原公式量词的约束关系的代换。,2020年5月30日星期六,42,违反量词推理规则的应用举例,下面是错误地运用_的推理：（）xyGxyA1（）yGyy（1）,_（x/y）构造一个模型，使得D是自然数，谓词G解释为“小于”。=。于是:（xyGxy）=T,即（1）的解释“没有最大的自然数”是真的，而（yGyy）=F，即(2)的解释“有小于自己的自然数”是假的。这个推理之所以无效，是由于对（1）_时进行了盲目的代换，x本来不受y的约束，但以y代换x后，代入y的却被y约束了。,2020年5月30日星期六,43,违反量词推理规则的应用举例,下面是错误运用+的推理：在包括运算符“+”的一阶语言L中，进行如下推理：（1）（）A1（2）（），（1），_（3）（）（2），+构造一个模型，使得D是实数，谓词解释成“”，那么（1）的解释是真的。（3）的解释是假的。原因是对（2）错误地运用了+，（2）中不受约束的，代换后被约束。,2020年5月30日星期六,44,QNP系统的语形(语法)推出关系,谓词逻辑的自然推理系统QNP是一个根据量词和联结词的推导规则，运用有前提的形式推演构建起来的形式系统。关于量词的否定规律：Q1：xAxA；Q2：xAxA；Q3：xAxA；Q4：xAxA。,2020年5月30日星期六,45,QNP系统的语形(语法)推出关系,Q1的证明先证：xAxA：（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),2020年5月30日星期六,46,QNP系统的语形(语法)推出关系,Q1的证明再证：xAxA:(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),2020年5月30日星期六,47,QNP系统的语形(语法)推出关系,设A是任何公式，x在A中不自由，我们有:Q5：AxAQ6：xAAQ7a：xAyA(x/y)(y不在A中出现)Q7b：yAxA(y/x)(x不在A中出现)Q8a：xAyA(x/y)(y不在A中出现)Q8b：yAxA(y/x)(x不在A中出现)改名规则：改变量词所约束的变元的置换规则。由于xAyA(x/y),xAyA(x/y),因此，我们可以用等价置换规则把一个公式中出现的xA置换为yA(x/y),或者把xA置换为yA（x/y）。,2020年5月30日星期六,48,QNP系统的语形(语法)推出关系,Q9：xyAyxA；Q10：xyyxA；Q11：xyAyxA；（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(AB)xAxB(x对的分配律)Q13：x(AB)xAxB(x对的分配律),2020年5月30日星期六,49,QNP系统的语形(语法)推出关系,Q13的证明先证：x(AB)xAxB(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),2020年5月30日星期六,50,QNP系统的语形(语法)推出关系,Q13的证明再证:xAxBx(AB)(1)xAxBA(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),2020年5月30日星期六,51,QNP系统的语形(语法)推出关系,Q14：x(AB)xAxBQ15：x(AB)xAxBQ14：x(AB)xAxBQ15：x(AB)xAxB只证Q14：（1）x(AB)A(2)xAH(3)AB(1),_(4)A(2),_(5)B(3),(4),_(6)xB(5),+(7)xAxB(2)(6),+(消去H),2020年5月30日星期六,52,QNP系统的语形(语法)推出关系,Q16：xAxBx(AB)Q17：x(AB)xAxB但是，Q16和Q17反过来不成立，即：x(AB)xAxBxAxBx(AB)对任意的公式A和B，如果x不在B中自由出现，那么，我们有：Q18：x(AB)xABQ19：x(AB)xABQ20：x(AB)xABQ21：x(AB)xABQ22：x(AB)xABQ23：x(AB)xABQ24：x(BA)BxAQ25：x(BA)BxA,2020年5月30日星期六,53,量词和联结词辖域之间的联系和转化,分析命题A