《谈谈离散数学中》PPT课件.ppt

1、谈谈离散数学中数理逻辑的教学,一、弄清数理逻辑演算形式系统的语构和语义,学习数理逻辑的命题演算和谓词演算形式系统，其实也是在学习一类语言系统-形式语言系统。要教好或学好这两个演算，弄清这类语言的语构（也称语法syntax）和语义（semantic）这两个方面是极其重要的。,语言的语构通常指语言的成分和构成，包括：字，词法，句法。在命题演算和谓词演算形式语言中则是指字母表（或符号表）： 命题演算符号表=(,), , , ，,p1 ,p2 ,p3 ,，q1 ,q2 ,q3 ,其中(,)是技术符号-括号, pi ,qi为命题变元或命题常元。,谓词演算符号表组成如下： 个体变元x1,x2,x3, ,

2、y1,y2,y3, （简称变元） 个体常元a1,a2,a3, , b1,b2,b3, （简称常元） 函词,（一元函词） ,（二元函词） ,（n元函词） 谓词,（一元谓词） ,（二元谓词） ,（n元谓词） 其真值联结词，, , , ， 量词 , 括号（，）,由于命题演算形式语言以命题为最小研究单元，因此它不需要表示个体对象的词法，只有表示命题公式的词法。谓词演算形式语言的词法便是它的项的构成规则和合式公式的构成规则： 谓词演算中项（terms）定义如下： （1）变元和常元为项。 （2）对任意正整数n，如果t1,t2, ，tn为项，那么f(n)t1t2tn亦为项。 除有限次使用（1），（2）条款可

3、确认为项的符号串外，没有别的是项。,谓词演算形式语言中的合式公式（well found formula）定义如下： (1)对任意正整数n，如果t1,，tn为项，那么P(n) t1t2tn为公式，并称之为原子公式。 (2)如果A，B为公式，那么（A）, （AB）, （AB）, （AB）,（AB）,（vA）,（vA）（v为任一变元）均为公式。 （3）除有限次使用（1），（2）条款可确认为公式的符号串外，没有别的是公式。,命题演算和谓词演算形式语言的句法则是它们各自系统内的推理规则，即由公理导出定理（或由公式重写公式的重写规则）,语言的语义通常指语言成分的含义或对语言成分的指称，包括词义，句义（文意

4、）。在命题演算和谓词演算形式语言中则是对个体域的确定（变元的语义：取值范围），对常元、函词、谓词的解释（个体域上的函数、性质和关系），对联接词、量词的真值规定，进而确定项的语义（个体域中的个体）以及公式的意义（即它的真值）。,我们知道语构的机器处理是十分简单的，就是通常所说的数据处理问题；而语义的机器处理是相当困难的，一个简单的命题公式的可满足性判断就已经是NP完全的了，一阶逻辑公式的可满足性判断则是理论不可计算的（或半可计算的）。,离散数学中通常先从逻辑代数说起，即非形式地介绍数理逻辑，大体是在介绍数理逻辑形式系统的语义，然后才介绍形式系统本身，也就是它的语构部分。这种次序的颠倒对于教学是十

5、分必要的，但由此引起了学生的混淆。因此，建议在讲解形式系统后，给予学生一个回顾和整理，区分数理逻辑形式系统的语构和语义这两个方面。以下的对照表，也许在教学中是会有帮助的。,二、弄清数理逻辑形式系统的研究的几个层面,对数理逻辑演算形式系统的研究将使用两种语言三个层面。一种是数理逻辑形式系统本身所使用的那个形式语言，我们称之为对象语言（object Language），另一种是介绍和研讨这个形式系统时使用的语言，为通常所用的数学语言，常称为元语言（meta Language）。后者也用大量符号，包括（1）沿用形式系统的符号（它们是讨论的对象）；（2）表示形式系统中同一类符号的符号，称为语法变元（s

6、yntactic variables），例如用v 表示系统中的变元x1,x2,x3, , y1,y2,y3, 中的任意一个；（3）为表达元语言概念引入的新符号例如， 等。,对数理逻辑演算形式系统的研究的三个层面是：,第一个是对对象语言语构的研究，即形式系统的建立和系统内的推演，构成形式系统内的公理、推理规则及其由它们导出的定理所组成的那个逻辑学理论； 第二个是对这个形式系统的语义进行研究所得的语义学结论，即逻辑代数和模型理论； 第三个是关于这个系统的性质的定理（称为元定理（meta theorems）所组成的理论，称为元理论（meta fheory）。元理论又包括两个方面：（1）系统导出规则的

7、研究，以及（2）对语构和语义的一致性研究，即系统的合理性、完备性等的研究。,一个例子,在离散数学教学教材中，常常有所谓“全称消除规则”和“存在消除规则”：即 （t对x可代入） ， 其实，这是两个层面的的事情，前者可以用做系统内的推理规则，而后者实际上是一条元定理的不正确的表述形式，这条元定理是： 定理 设为一阶逻辑的任一公式集，A，B为任意公式，变元v在的每一公式及公式B中均无自由出现，那么由vA 及 ；AB可推出 B。,该定理是这样一条导出规则；当我们有了vA后便可将A看作附加的演绎前提，当得到与v无关的B时，可确认B已推出，即它并不依赖于A而成立。这就象数学证明中我们常做的那样：当推知方程

8、F（x）=0有根（即x(F(x)=0)）时，可设这个根为x0（即F(x0)=0），然后再据此去证所需的结论，只要所证结论与x0的性质（除x0为F(x)=0的根这一性质）无关，它就是有效的演绎结果。也就是说， 表示：有了xA(x),可以假定A(x)，而不是由xA(x)推出A(x)（这显然是不正确的）。,当然，可以把这一定理引入系统，作为一个自然推理系统的推理规则，那么应当正确地表示为 （和C中无e的出现）,三、讲一点自然推理系统,不少离散数学教材不讲形式系统，也有不少教材所给的形式系统是不严谨的。我认为这都是不适当的，建议简要地介绍一个自然推理系统。不讲形式系统，学生无法了解现代逻辑学的真谛，无

9、法弄清形式系统的语构和语义，也无法弄清形式系统研究的几个层面，也就谈不上掌握形式化方法和技术。事实上，不讲形式系统，许多重要概念也无法说得清楚。,另一个例子,全称推广规则通常是必定要讲的，但这条规则有一个重要的应用前提：“x不在导出A（x）的前提中自由出现”。这个应用前提就很难讲得清楚，很难掌握得好，特别是碰到xyA(x,y)的情况时，更是如此。以下推理的错误是明显的： （1）xyA(x,y) 前提 （2）yA(x,y) 全称消除规则 （3）A(x,y) 存在消除规则 （4）xA(x,y) 全称推广规则 （5）yxA(x,y) 存在推广规则 也许你会告诉学生对xyA(x,y)应该注意什么，但还

10、有许多其他情况很难一一加以注明，如何处置？可是，在自然推理系统中，我们可以处理得很简单。,推广规则 (v在 的任一公式里均不自由出现) 其中 为前提和假设的集合（直观上即为符号 的左边部分的所有公式的集合）。显然，条件“v在的任一公式里均不自由出现”是不可缺少的。例如，A为中一个含自由变元v的公式(记为A(v)，显然A(v)，如果由此得到 vA(v)显然是荒谬的，因为A(v)正是一个关于v的假设，怎么能由此即断定由 能演绎出vA(v)呢？这犹如从y=5 y2=52而推出y=5y(y2=52)，是十分荒谬的。当然，由y=5 y2=52 可得 y=5y2=52，进而有 y(y=5y2=52)，这是因为 y=5y2=52中的 为空集合，v在 里不会有自由出现，从而可以使用全称推广规则。,在上文提到的推理中的（3）A(x,y)，在自然推理中是一个假设，处于 中，因而 中有自由变元x，对A(x,y)的全称推广便被阻断，错误也就不会发生。 值得向大家推荐的是文献3中给出的自然推理系统，在4中也有介绍。,四、自然推理形式