命题逻辑语法完全性问题，本文主要内容关键词为：命题论文,语法论文,性问题论文,逻辑论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
一、命题逻辑是否是语法完全的
形式系统的完全性问题是逻辑系统重要的元理论问题之一。一般而言，有如下三种意义的完全性：1、一个形式系统如果对于其中的任一公式α，或者α在系统中可证，或者
在系统中可证，则称该系统是古典完全的；2、如果把系统中的任一不可证公式作为公理增加到已有的系统中将导致系统的不协调，则称该系统是语法完全的（或绝对完备的）；3、如果在一个形式系统的所有模型中都真的公式在该系统中都可以得到证明，则称该系统是语义完全的（相对完备的）。命题逻辑具有语义完全性。但因为命题逻辑系统中含有命题变元，从而不具有古典完全性。
命题逻辑是否具有语法完全性呢？《现代逻辑辞典》中认为命题逻辑具有语法完全性（注：杨百顺，李志刚：《现代逻辑辞典》，湖北教育出版社1995版。
）。几本有影响的逻辑教材如王宪钧先生所著《数理逻辑引论》（新旧版）、莫绍揆先生所著《数理逻辑教程》、张尚水先生所著《数理逻辑导引》、陈慕泽先生所著《数理逻辑教程》等均认为命题逻辑具有语法完全性。只不过在叙述上大同小异：
王宪钧先生：命题逻辑是语法完全的。如果把一不可证的公式作为公理，其结果将是不一致的（注：王宪钧：《数理逻辑引论》，北京大学出版社1998年版，第101、102页。
莫绍揆先生：当把“原子命题”理解为命题变元时，上述永真公式的公理系统（指命题逻辑系统）有绝对完备性（注：莫绍揆：《数理逻辑教程》，华中工学院出版社1982年版，第108页。
张尚水先生：如果在P（指命题逻辑系统）中加进一个不可证的公式A作为公理，那么结果所得的系统是不协调的（注：张尚水：《数理逻辑导引》，中国社会科学出版社1990年版，第160页。
陈慕泽先生：如果在P（指命题逻辑系统）中加进一个不可证的公式（模式）作为公理（模式），那么所得的系统中是不一致的（注：陈慕泽：《数理逻辑教程》，上海人民出版杜2001年版，第218页。
但我们倘若从另外一个角度（即现代逻辑中被广泛使用的证明系统语义完全性的极大协调集方法）来研究这一问题，就可以发现如下命题逻辑系统不是语法完全的。我们称由公理模式：
Ax1:(A→(B→A))
Ax2:((A→(B→C))→((A→B)→(A→C))
和分离规则构成的命题逻辑系统（形式语言与一般的命题逻辑公理系统相同）为形式系统L（显然，该系统具有通常的命题逻辑可靠性和语义完全性），那么有：
命题1命题逻辑形式系统L（相对于通常的二值命题逻辑语义模型）不是语法完全的。
证明：实际上就是要证并非在命题逻辑形式系统L中加入任一不可证的公式则系统不协调。那么，只要证明存在某一（某些）不可证的公式，将它们加入命题逻辑形式系统L中后并没有导致系统的不协调即可。
首先，可以证明命题逻辑形式系统L中存在公式α，
且α协调。实际上所有L中可满足但不是有效的公式，如p、p→q等，都是这样的α。
因为α不是有效的，所以根据命题逻辑的可靠性定理有：；
由Lindenbaum定理知，任何协调的公式集都能够扩充为极大协调集（注：陆钟万：《面向计算机科学的数理逻辑》，中国科学出版社1998年版，第137页。
）。所以由上述的α公式可以扩充得到一极大协调集
。其扩充过程为：
因命题逻辑形式系统L中的公式集Form(L)是可数无限集。令
是所有L公式的一个排列。定义
的无限序列如下：
由极大协调集的扩充过程可以很显然地知道所有命题逻辑的永真式是包含在任一极大协调集之中的。由命题逻辑形式系统L的可靠性知，系统L中的所有定理是包含在极大协调集之中。
而极大协调集是封闭于形式可推演的，即对于任何公式A，若
。
这样在极大协调集中，既包含系统L的所有定理，又包含系统L中不可证但协调的公式α，还特别包括系统L增加一不可证的公式α后所能推出的所有公式。
这说明在系统L增加一不可证的公式α并没有导致不协调。
因此，命题逻辑形式系统L不是语法完全的。
这样，关于命题逻辑的语法完全性就得出了两个截然不同的结论。那么，如何解释这一看似矛盾的问题呢？
二、公理、公理模式和代入规则
现代命题逻辑系统中，通常有三类初始符号：①命题变元：p、q、r、Λ；②命题联结词：
；③技术性符号：（，）。由这些初始符号按照形成规则产生命题逻辑的合式公式，例如：
等。这些初始符号和合式公式成为系统内语言。有时为了研究系统内公式的性质以及叙述和言说的方便，我们还引入一些符号（例如大写字母A、B、C、Λ或α、β、γ、Λ来表示系统中的任一合式公式。例如用A表示任一合式公式，用B→C表示任一蕴涵式等。A、B、C、Λ或α、β、γ、A不是系统内语言，而是系统之外的语言。相对于这种内外关系和研究与被研究的关系，有时也将系统内语言称之为对象语言，将系统外的研究语言称为元语言。
现代命题逻辑由于各自的出发点和处理方法的不同，所建立的公理系统也千差万别，尽管可以证明它们是相互等价的。在诸多不同的命题逻辑系统中，若以公理数量来加以区分的话，那么大体可以分为两类：一类是公理数有限的形式系统，例如罗素的命题逻辑公理系统；另一类是公理数无限的形式系统，例如上述的命题逻辑公理系统L。在公理数有限的系统中，公理是用对象语言叙述的，例如罗素系统（改进后的）中的四条公理是
。在公理数无限的形式系统中，公理假如仍然用系统内语言叙述的话，就非常困难，因此采用元语言来叙述，即使用公理模式来描述这无穷多条公理。如上述形式系统中的三条公理模式。每一条公理实际上描述了所有具有该形式的合式公式都是公理，例如凡是具有公理模式Axl：(A→(B→A))形式的公式都是系统的公理。诸如(p→(q→p))，((r∨s)→((q←→p∨t)→(r∨s)))等。莫绍揆先生的《数理逻辑教程》、张尚水先生的《数理逻辑导引》、陈慕泽先生的《数理逻辑教程》所用的命题逻辑公理系统均采用公理模式的形式。
在公理数有限的形式系统中，推理规则一般有代入规则和分离规则，在使用公理模式的系统中其推理规则只有分离规则。如果仅限于系统内的推演能力而言，公理加代入规则的推演能力和公理模式的推演能力是相同的，因此这样的系统所得到的定理集是相同的，即系统等价。但在证明系统的元理论方面，采用公理模式的形式系统有其方便之处。例如在证明系统的定理都有某一性质时，一般是先证明公理（公理模式）具有该性质，然后证明所有的推理规则保持该性质。这样，在公理数有限的形式系统中，在第二步就必须证明代入规则和分离规则都能保持该性质，一般情况下，对代入规则的证明在技术上是比较烦琐的；而在采用公理模式的形式系统中，在第二步只须证明分离规则能保持该性质即可。对形式系统的这一改进归功于著名逻辑学家、计算机科学理论学家冯·诺意曼（注：'Zur Hilbertschen Beweistheorie',Mathematische Zeitschrift,xxvi(1927),pp.1-46.）。
通常说“某某系统具有完全性”或“某某系统不具有完全性”，往往让人产生一种误解，即系统的完全性概念是一个性质概念，即逻辑上的一元谓词。其实不然，实际上，完全性概念是个二元谓词。完整地表述应为“某某系统相对于某一（某些）模型具有完全性”或“某某系统相对于某一（某些）模型不具有完全性”。例如命题逻辑形式系统相对于经典命题逻辑模型是完全的，但正命题逻辑形式系统相对于经典命题逻辑模型就不是完全的，因为含有否定符的有效式就不是正命题逻辑形式系统的定理；正命题逻辑形式系统相对于正命题逻辑模型是完全的。而通常的表述只是一种省略的说法。而且命题逻辑的完全性也跟具体的形式系统联系在一起，单纯地说“命题逻辑具有完全性”或“命题逻辑不具有完全性”是不确切的。而应表述为“命题逻辑形式系统张三具有完全性”或“命题逻辑形式系统李四不具有完全性”等。系统的“可靠性”也和“完全性”一样是个关于形式系统和模型之间关系的二元谓词。而语法完全性也是和“可靠性”密切相连的。因此，上述问题的症结就在于所谈论的命题逻辑形式系统不同。如果我们将王宪钧先生所述的命题逻辑形式系统记为
，则《数理逻辑引论》中所表述的是：
定理2 命题逻辑形式系统（相对于通常的二值命题逻辑语义模型）不具有语法完全性。
为了便于说明问题，我们将其中的证明引述如下：
所以，如将一不可证的公式作为公理，则将导致逻辑矛盾。命题演算具有语法意义下的完全性（注：'Zur Hilbertschen Beweistheorie',Mathematische Zeitschrift,xxvi(1927),pp.1-46.
对比一下定理1和定理2的证明，我们可以看出，在定理2中使用了代入规则。容易看出在有代入规则的系统中加进一不可证的公式α作为公理，实际上就同时将公式α及其否定
加入到系统中了。因此必然导致系统的不协调。
而命题逻辑形式系统的公理是用元语言叙述的，采用的是公理模式，其中不再需要代入规则，这样定理1和定理2的结论自然就不相同了。
但是在莫绍揆先生所著《数理逻辑教程》、张尚水先生所著《数理逻辑导引》中，由于其形式系统都采用的是公理模式形式系统，其中推理规则只有分离规则而没有代入规则。那么，他们的系统语法完全性是如何得出的呢？
莫绍揆先生的证明和王宪钧先生的证明其思路大体相同，其中使用了代入规则。张尚水先生的证明和王宪钧先生的不同，其证明如下：
由A是不可证的，根据定理8.2，A不是重言式，对某个真值赋值σ，
。对A中出现的每个命题变元，依赋值σ指派的真值是⊥还是T而作代入，对σ指派真值T的命题变元代以公式(B→B)，对σ指派真值⊥的命题变元代以公式
。对A中的命题变元作这样的代入，结果所得的公式A′是一常假的公式，与等值。因为A是作为公理加入系统中的，由A可证而A′可证，因而是可证的，由
可证得
。因此这新的系统是不协调的（注：王宪钧：《数理逻辑引论》，北京大学出版社1998年版，第101、102页。
由这一证明我们不难看出，其中间接使用了代入规则。由于张尚水先生、莫绍揆先生的形式系统没有代入规则，而在元定理证明中却使用了代入规则，这显然是不妥的。
陈慕泽先生可能已经认识到其中的不妥，所以在其叙述中就对定理进行了修改。其证明大体类似张尚水先生的证明。因为他将所加入的不可证公式改为公式模式，其证明就避免了使用代入规则。这样就与其采用公理模式的形式系统相协调。但这实际上已经改变了语法完全性的概念。因为语法完全性指的是加入一不可证的公式，而不是公理模式。而在此定理的证明之后陈慕泽先生也接着指出：对任一公式A（注意，这里元语言变项A指的是公式，而不是公式模式），如果
在中不可证，则把A作为公理加入到系统中不会导致不一致（注：张尚水：《数理逻辑导引》，中国社会科学出版社1990年版，第160页。
）。而这就与定理2所表达的完全一致了。
与此相关的另外一个问题是，我们必须注意公式A（或公式集）相对于某一形式系统Ω的协调性与将A作为公理加入形式系统Ω而得到的新形式系统Ω的协调性是不能混淆的。
从上述四本教材关于命题逻辑形式系统和形式系统的语法完全性的讨论，可以看出一个基本的发展脉络来：王宪钧先生的《数理逻辑引论》其形式系统是有代入规则的、公理数有限的系统，系统具有语法完全性；莫绍揆先生的《数理逻辑教程》和张尚水先生的《数理逻辑导引》其形式系统是采用公理模式的系统，但在语法完全性的讨论中实际上仍然采用的是有代入规则的系统；陈慕泽先生的《数理逻辑教程》其形式系统也采用的是公理模式的系统，其语法完全性的讨论也遵循所用系统的规则，但改变了语法完全性的内容。可以推测，在采用公理模式的命题逻辑形式系统中关于该系统的语法完全性的讨论将使用本文定理1的表述，应是大势所趋。
三、结论
由上述讨论可以得出：
（一）命题逻辑的语法完全性是一个关于形式系统和语义模型关系的二元谓词，是与一具体的命题逻辑形式系统联系在一起的。
1.在公理数有限、有代入规则的命题逻辑公理系统中若加入任一不可证的公式作为公理，则新系统不协调；
2.在公理数有限、有代入规则的命题逻辑公理系统中若加入一不可证、但协调的公式作为公理，若限制代入规则的使用，即只有原系统的可证式才能使用代入规则，则新系统协调；
3.在由公理模式和分离规则构成的命题逻辑公理系统中若加入一不可证、但协调的公式作为公理，则新系统协调；
4.在由公理模式和分离规则构成的命题逻辑公理系统中若加入任一不可证的公式模式作为公理，则新系统不协调。
因此，
1.公理数有限、有代入规则的命题逻辑公理系统具有语法完全性；
2.由公理模式和分离规则构成的命题逻辑公理系统不具有语法完全性；
3.公理数有限、有代入规则但限制使用的命题逻辑公理系统不具有语法完全性；
4.由公理模式和分离规则构成的命题逻辑公理系统，若加入不可证公式模式，则具有语法完全性。
（二）建议在新版的数理逻辑教材中形式系统采用使用公理模式的系统，并在关于该系统的语法完全性讨论中使用本文的定理1。
标签：命题逻辑论文; 命题的否定论文; 公理系统论文; 逻辑模型论文; 关系逻辑论文; 数理逻辑论文; 陈慕泽论文; 逻辑学论文;