谈谈离散数学中

《谈谈离散数学中》由会员分享，可在线阅读，更多相关《谈谈离散数学中（31页珍藏版）》请在装配图网上搜索。

1、,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,谈谈离散数学中数理逻辑的教学,一、弄清数理逻辑演算形式系统的语构和语义,学习数理逻辑的命题演算和谓词演算形式系统，其实也是在学习一类语言系统,-,形式语言系统。要教好或学好这两个演算，弄清这类语言的语构（也称语法,syntax,）,和语义（,semantic,）,这两个方面是极其重要的。,语言的语构通常指语言的成分和构成，包括：字，词法，句法。在命题演算和谓词演算形式语言中则是指字母表（或符号表）：,命题演算符号表,=,(,),，,p,1,p,2,p,3,，q,1,q,2,q,3,其中(,)是技术符号-括

2、号,p,i,q,i,为命题变元或命题常元。,谓词演算,符号表,组成如下：,个体变元,x,1,x,2,x,3,y,1,y,2,y,3,（,简称变元）,个体常元,a,1,a,2,a,3,b,1,b,2,b,3,（,简称常元）,函词,（一元函词）,（二元函词）,（,n,元函词）,谓词,（一元谓词）,（二元谓词）,（,n,元谓词）,其真值联结词，,，,量词,括号（，）,由于命题演算形式语言以命题为最小研究单元，因此它不需要表示个体对象的词法，只有表示命题公式的词法。谓词演算形式语言的词法便是它的项的构成规则和合式公式的构成规则：,谓词演算中,项（,terms）,定义如下：,（1）变元和常元为项。,（2

3、）对任意正整数,n，,如果,t,1,t,2,，t,n,为项，那么,f,(n),t,1,t,2,t,n,亦为项。,除有限次使用（1），（2）条款可确认为项的符号串外，没有别的是项。,谓词演算形式语言中,的,合式,公式（,well found formula）,定义如下：,(1)对任意正整数,n，,如果,t,1,，t,n,为项，那么,P,(n),t,1,t,2,t,n,为公式，并称之为原子公式。,(2)如果,A，B,为公式，那么（,A）,（A,B）,（A,B）,（AB）,（A,B）,（,vA）,（,vA）（v,为任一变元）均为公式。,（3）除有限次使用（1），（2）条款可确认为公式的符号串外，没有

4、别的是公式。,命题演算和谓词演算形式语言的句法则是它们各自系统内的推理规则，即由公理导出定理（或由公式重写公式的重写规则）,语言的语义通常指语言成分的含义或对语言成分的指称，包括词义，句义（文意）。在命题演算和谓词演算形式语言中则是对个体域的确定（变元的语义：取值范围），对常元、函词、谓词的解释（个体域上的函数、性质和关系），对联接词、量词的真值规定，进而确定项的语义（个体域中的个体）以及公式的意义（即它的真值）。,我们知道语构的机器处理是十分简单的，就是通常所说的数据处理问题；而语义的机器处理是相当困难的，一个简单的命题公式的可满足性判断就已经是,NP,完全的了，一阶逻辑公式的可满足性判断则

5、是理论不可计算的（或半可计算的）。,离散数学中通常先从逻辑代数说起，即非形式地介绍数理逻辑，大体是在介绍数理逻辑形式系统的语义，然后才介绍形式系统本身，也就是它的语构部分。这种次序的颠倒对于教学是十分必要的，但由此引起了学生的混淆。因此，建议在讲解形式系统后，给予学生一个回顾和整理，区分数理逻辑形式系统的语构和语义这两个方面。以下的对照表，也许在教学中是会有帮助的。,语,构,语 义,变元(自由，约束),x,1,x,2,x,3,y,1,y,2,y,3,个体域,U,，,指派,s(v/t),常元,a,1,a,2,a,3,，,函词,解释,I,：,个体，函数,命题常元,P,1,P,2,P,3,，,谓词

6、,解释,I,：,真值，性质，关系,项,t,个体,t,联接词、量词(辖域),真值规定,公式,真值，真值函数,公理，定理,永真式,矛盾式,不可满足式,非矛盾式,可满足式（有模型）,逻辑后顺，,B,A,逻辑蕴涵,，,B,A,系统内的定理证明，,A,永真式的证明，,A,系统内的重写（形式演绎），,A,逻辑代数的保真变换，,A,二、,弄清数理逻辑形式系统的研究的几个层面,对数理逻辑演算形式系统的研究将使用两种语言三个层面。一种是数理逻辑形式系统本身所使用的那个形式语言，我们称之为,对象语言,（,object Language,），,另一种是介绍和研讨这个形式系统时使用的语言，为通常所用的数学语言，常称为

7、,元语言,（,meta Language,）。,后者也用大量符号，包括（,1,）沿用形式系统的符号（它们是讨论的对象）；（,2,）表示形式系统中同一类符号的符号，称为,语法变元,（,syntactic variables,），,例如用,v,表示系统中的,变元,x,1,x,2,x,3,y,1,y,2,y,3,中的任意一个；（,3,）为表达元语言概念引入的新符号例如,，,等。,对数理逻辑演算形式系统的研究的三个层面是：,第一个,是对对象语言语构的研究，即形式系统的建立和系统内的推演，构成形式系统内的公理、推理规则及其由它们导出的定理所组成的那个逻辑学理论；,第二个,是对这个形式系统的语义进行研究所

8、得的语义学结论，即逻辑代数和模型理论；,第三个,是关于这个系统的性质的定理（称为,元定理,（,meta theorems,）,所组成的理论，称为,元理论,（,meta fheory,）。,元理论又包括两个方面：（,1,）系统导出规则的研究，以及（,2,）对语构和语义的一致性研究，即系统的合理性、完备性等的研究。,一个例子,在离散数学教学教材中，常常有所谓“全称消除规则”和“存在消除规则”：即,（,t,对,x,可代入），,其实，这是两个层面的的事情，前者可以用做系统内的推理规则，而后者实际上是一条元定理的不正确的表述形式，这条元定理是：,定理,设,为一阶逻辑的任一公式集，,A,，,B,为任意公式

9、，变元,v,在,的每一公式及公式,B,中均无自由出现，那么由,vA,及,；,AB,可推出,B,。,该定理是这样一条导出规则；当我们有了,vA,后便可将,A,看作附加的演绎前提，当得到与,v,无关的,B,时，可确认,B,已推出，即它并不依赖于,A,而成立。这就象数学证明中我们常做的那样：当推知方程,F,（,x,）,=0,有根（即,x(F(x)=0),）,时，可设这个根为,x,0,（,即,F(x,0,)=0,），,然后再据此去证所需的结论，只要所证结论与,x,0,的性质（除,x,0,为,F(x)=0,的根这一性质）无关，它就是有效的演绎结果。也就是说，,表示：有了,xA(x),可以假定,A(x)，

10、,而不是由,xA(x),推出,A(x)（,这显然是不正确的）。,当然，可以把这一定理引入系统，作为一个自然推理系统的推理规则，那么应当正确地表示为,（,和,C,中无,e,的出现）,三、讲一点自然推理系统,不少离散数学教材不讲形式系统，也有不少教材所给的形式系统是不严谨的。我认为这都是不适当的，建议简要地介绍一个自然推理系统。不讲形式系统，学生无法了解现代逻辑学的真谛，无法弄清,形式系统的语构和语义，也无法弄清形式系统研究的几个层面，也就谈不上掌握形式化方法和技术。事实上，不,讲形式系统，许多重要概念也无法说得清楚。,另一个例子,全称推广规则通常是必定要讲的，但这条规则有一个重要的应用前提：“,

11、x,不在导出,A（x）,的前提中自由出现”。这个应用前提就很难讲得清楚，很难掌握得好，特别是碰到,x,yA(x,y),的情况时，更是如此。以下推理的错误是明显的：,（1）,x,yA(x,y),前提,（2）,yA(x,y),全称消除规则,（3）,A(x,y),存在消除规则,（4）,xA(x,y),全称推广规则,（5）,y,xA(x,y),存在推广规则,也许你会告诉学生对,x,yA(x,y),应该注意什么，但还有许多其他情况很难一一加以注明，如何处置？可是，在自然推理系统中，我们可以处理得很简单。,推广规则,(,v,在,的任一公式里均不自由出现),其中,为前提和假设的集合（直观上即为符号,的左边部

12、分的所有公式的集合,）。显然，,条件“,v,在,的任一公式里均不自由出现”是不可缺少的。例如，,A,为,中一个含自由变元,v,的公式(记为,A(v)，,显然,A(v)，,如果由此得到,vA(v),显然是荒谬的，因为,A(v),正是一个关于,v,的假设，怎么能由此即断定由,能演绎出,vA(v),呢？这犹如从,y=5 y,2,=5,2,而推出,y=5,y(y,2,=5,2,)，,是十分荒谬的。当然，由,y=5 y,2,=5,2,可得,y=5,y,2,=5,2,，,进而有,y(y=5,y,2,=5,2,)，,这是因为,y=5,y,2,=5,2,中的,为空集合，,v,在,里不会有自由出现，从而可以使用

13、全称推广规则。,在上文提到的推理,中的（3）,A(x,y)，,在自然推理中是一个假设，处于,中，因而,中有自由变元,x，,对,A(x,y),的全称推广便被阻断，错误也就不会发生。,值得向大家推荐的是文献3中给出的自然推理系统，在4中也有介绍。,四、自然推理形式系统,ND,1、,ND,的基本构成,规则形如,分离规则,公理模式只有一个,；,A,A,推理规则模式为18个,假设引入规则,假设消除规则,引入规则,消除规则,引入规则,消除规则,引入规则,消除规则,引入规则,消除规则,引入规则,消除规则,引入规则,消除规则,引入规则,(,v,在,中无自由出现,),消除规则,(,t,对,v,可代入,),引入规则,消除规则,