系统Z中的范式和插入定理，本文主要内容关键词为：范式论文,定理论文,系统论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
系统Z 是我在文〔1〕中建立的经典命题逻辑的一个公理系统。 这系统只用一种初始联结词——广义析舍，而且采用括号记法，因而使得系统的陈述更为直接明了。它的可判定性、可靠性、完全性和独立性等证明也都很简单。系统Z是很有独特之处的， 分离规则和双重否定规则在其中都不成立。
本文将继续这方面的工作。首先，我们提出一种析舍范式，并阐明它跟合取范式和析取范式的联系。其次，我们陈述并证明插入定理。通常插入定理的证明很少或几乎没有直接以公理系统为基础进行的，而我们的证明则是施归纳于系统Z中证明的长度进行的，这是系统Z的独特性带来的一大好处。
本文中的语形和语义方面的基本概念及记号都参照文〔1〕和〔2〕中的用法。
一、析舍范式 我们将称公式〔A[,0]，…，A[,n-1]〕为它的直接子公式A[,0]、……、A[,n-1]的析舍，并称这些直接子公式为它的析舍支。析舍式〔A[,0]，…，A[,n-1]〕为不可满足的，当且仅当，它的析舍支都是重言式。析舍式〔A[,0]，…，A[,n-1]〕为重言式，当且仅当，它的全部析舍支所形成的集合｛A[,0]，…，A[,n-1]｝为不可满足的。当析舍支A[,0]、……、A[,n-1] 都是原子析舍时，我们称公式〔A[,0]，…，A[,n-1]〕为析舍范式。为n为0时，析舍范式〔A[,0]，…，A[,n-1]〕为公式〔〕；而当n为1时，析舍范式〔A[,0]，…，A[,n-1] 〕则为原子析舍的否定。因此，恒假公式和原子析舍的否定都是析舍范式。空析舍恒假。
析舍范式可以显示公式的不可满足性。原子析舍是重言式，当且仅当，它是系统Z的公理；即，它是有〔〕为直接子公式的原子析舍， 或者是有某个命题符及其否定同时为直接子公式的原子析舍。因此，一析舍范式为不可满足的公式与否是极易识别的，只须弄清它的各个析舍支是否以〔〕为直接子公式，或者是否以某个命题符与其否定同时为直接子公式。例如，析取范式〔〔p，q〕，〔p，〔r〕〕，〔〔p〕，〔q〕，r〕〕不是不可满足的，因为它的三个析舍支都不是系统Z的公理；当p、q都真时，该析舍范式为真，所以原公式是可满足的。
令A为公式，如果某个析舍范式B与A等值，则称B为A 的一个析舍范式。给定一个公式A， 我们可以有下述两种方法找出它的一个析舍范式。
方法一是利用A的真值表来找。如果A恒真或恒假，则只须取恒真公式〔〔〕〕或恒假公式〔〕就行。如果A既不恒真又不恒假，则A中必出现有命题符。假定出现在A中的全部命题符为P[,1]，……，P[,k]， 则A的真值表共有2[k]行，A相应于这2[k]行的值既有真又有假。现在考虑A取值为真的行，设它们共有m行（m≥1）， 并从上往下依次编成第1行、……、第m行。对于第j行，j＝1，…，m，我们可以配上一个A[,j]如下：
A[,j]＝〔P[j][,1]，…，P[j][,k]〕；
这里，当 P[,i]在第j行中的值为真时p[j][,i]为p[,i]，否则P[j][,i]为〔p[,i]〕。显然，A[,j]（j＝1，…，m）都是原子析舍。最后，取B为公式〔A[,1]，…，A[,m]〕就行。
例如公式〔〔〔〔q，r〕，〔〔q〕，〔r〕〕〕，〔p 〕〕〕（用通常的符号表达，则为
的真值表如下：
q r p 〔〔〔〔q，r〕，〔〔q〕，〔r〕〕〕，〔p〕〕〕
1 1 1
0
1 1 0
1
1 0 1
0
1 0 0
0
0 1 1
0
0 1 0
0
0 0 1
0
0 0 0
1
其中只有两行使原公式为真。易见，A[,1]＝〔q，r，〔p〕〕并且A[,2]＝〔〔q〕，〔r〕，〔p〕〕。公式〔A[,1]，A[,2]〕＝〔〔q，r，〔p〕〕，〔〔q〕，〔r〕，〔p〕〕〕为原公式的一个析舍范式。
第二种方法是利用文〔1〕中构作树图来找。首先构作公式A的否定〔A〕的树图。当完成时图中各分枝的顶端都是原子析舍。 当这些原子析舍都是系统Z的公理时，A的否定〔A〕就是系统Z的一个定理，从而是重言式，因此A是恒假公式，公式〔〕就是A的一个析舍范式。当这些原子析舍不全是系统Z的公理时，将其中不是公理的那些析舍起来， 所得到的公式就是A的一个析舍范式。
例如上例中公式的否定〔〔〔〔〔q，r〕，〔〔q〕，〔r〕〕〕，〔p〕〕〕〕的树图如下：
顶端上的原子析舍都不是Z的公理，它们的析舍为〔〔q，r，〔p〕〕，〔〔q〕，〔r〕，〔p〕〕〕，这是原公式〔〔〔〔q，r〕，〔〔q〕，〔r〕〕〕，〔p〕〕〕的一个析舍范式。
我们将称公式〔〕和〔〔〕〕互为对偶，命题符p与其否定〔p〕互为对偶。任一个原子析舍A直接等值于一个析取式A′，这析取式的所有析取支正好是该原子析舍的直接子公式的全部对偶。例如，原子析舍〔〔〕，p，〔p〕〕等值于公式〔〔〔〔〕〕〕，〔〔p〕〕，〔q〕〕，即，〔〔〕〕∨〔p〕∨q。类似地，任一个原子析舍A的否定〔A〕直接就是一个合取式，这合取式的所有合取支正好是该原子析舍的全部直接子公式。例如，原子析舍〔〔〕，p，〔q〕〕的否定〔〔〔〕，p，〔q〕〕〕是〔〕、p、〔q〕的合取。
析舍范式跟通常的合取范式、析取范式的联系是非常密切的。 令A为任意一个公式。从A的一个析舍范式〔A[,0]，…，A[,n-1] 〕（这里，诸A[,i]都是原子析舍）可以立即得到A的一个析取范式，因为析舍范式〔A[,0]，…，A[,n-1]〕等值于〔〔〔A[,0]〕〕，…，〔〔A[,n-1]〕〕〕，并且由上一段落的论述可知诸〔A[,i] 〕直接就是一个由公式〔〕、命题符、或命题符的否定组成的合取式，从而〔〔〔A[,0] 〕〕，…，〔〔A[,n-1]〕〕〕为A的一个析取范式。类似地， 从否定式〔A〕的一个析舍范式〔A[,0]，…，A[,n-1]〕可以立即得到A 的一个合取范式，因为此时A等值于〔〔A[,0]，…，A[,n-1]〕〕，并且对小于n的i而言A[,i]等值于一个析取式A′[,i]，A′[,i]的全部析取支正好是原子析舍A[,i]的直接子公式的所有对偶，从而〔〔A′[,0]，…，A′[,n-1]〕〕为A的一个合取范式。
例如取A为公式〔〔〔〔q，r〕，〔〔q〕，〔r〕〕，〔p〕〕〕，则A的一个析舍范式为〔〔q，r，〔p〕〕，〔〔q〕，
〔A[,ij]〕，…〕，…〕〕，因此A等值于〔…，〔…，〔A[,ij]〕，…，〕…〕，从而等值于析舍范式〔…，〔…，A′[,ij]，…〕，…〕，这里A′[,ij]如下确定：
┌〔〕，当A[,ij]为〔〔〕〕时；
A′[,ij]＝< 〔p〕，
当A[,ij]为p时；
│ p， 当A[,ij]为〔p〕时；
└空符，当A[,ij]为〔〕时。
二、插入定理 在证明系统Z的插入定理以前， 我们先引进一些记法和定义。
下面，我们将以大写希腊字母Γ、Δ（或加添标）表示由公式组成的有穷序列（包括空序列）。若Γ是序列A[,0]，…，A[,n-1]，则公式〔A[,0]，…，A[,n-1]〕可简记成〔Γ〕；类似地，若Γ是序列A[,0 ]，…，A[,n-1]，而Δ为序列B[,0]，…，B[,m-1]，则〔Γ， Δ〕将表示公式〔A[,0]，…，A[,n-1]，B[,0]，…，B[,m-1]〕。令Γ为序列A[,0]，…，A[,n-1]，并将序列〔A[,0]〕，…，〔A[,n-1]〕，记成
那么广义蕴涵和广义等值可以定义如下：
当n＝1时，这里定义的“广义蕴涵”与文〔1 〕中“实质蕴涵”的定义一致；而当n＝2时，这里定义的“广义等值”则与文〔1 〕中“等值”的定义一致。
利用序列记法，系统Z的两个推证规则可简记如下：
另外，我们将以│Γ│表示由出现在Γ中的全部公式组成的集合，即，当Γ为序列A[,0]，…，A[,n-1]时，│Γ│＝｛A[,0]，…，A[,n-1]｝。利用这一记号可知，一原子析舍〔Γ〕为系统Z的公理， 当且仅当，恒假公式〔〕属于│Γ│或者有命题符p与其否定〔p〕同属│Γ│。
在插入定理的叙述中，将涉及命题符在一公式中的出现的正负性概念，其递归定义如下：定义：令p为一命题符。
（1）p在公式p中的出现是正的；
p在公式〔p〕中的出现是负的；
（2）若p在公式A[,0]、…、或A[,n-1]中的某出现是正的，则p 的这个出现在公式〔A[,0]，…，A[,n-1]〕中是负的；
（3）若p在公式A[,0]、…、或A[,n-1]中的某出现是负的，则p 的这个出现在公式〔A[,0]，…，A[,n-1]〕中是正的。
例如，在公式〔〔〔〔q，r〕，〔〔q〕，〔r〕〕，〔p〕〕〕中，p的出现是负的，q的第一个出现是正的，而q的第二个出现则是负的。实际上，一命题符在一公式中的某个出现的正负由该公式中管辖该出现的六角括号的总数决定；当这个总数为偶数时该出现是正的，而当这个总数为奇数时该出现就是负的。
插入定理：如果公式〔Γ，Δ〕在系统Z中可证，则有公式A使得〔Γ，〔A〕〕和〔A，Δ〕都在系统Z中可证，并且满足下述两条件：
（1）A中出现的命题符一定在Γ内某公式中和Δ内某公式中出现；
（2）若一命题符p出现在A中，则该出现在A中的正负性一定与它在Γ内某公式中某出现的正负性相同，也一定与它在Δ内某公式中某出现的正负性相异。
证明：序列Γ可以被称为〔Γ，Δ〕的一个始段， 所要求的公式A则可以被称为相应于始段Γ的插入式。因此，插入定理的实质是说，对于任意可证公式的任一始段总有相应的插入式。我们的证明将施归纳于系统Z中证明的长度上进行。令〔Γ，Δ〕在系统Z中证明的长度为n，我们要作的强归纳假设是：对于任意证明长度小于n 的公式的任一始段总有相应的插入式。作为归纳步骤，我们有下述情形需要考虑。
情形1.〔Γ，Δ〕是公理。此时，〔Γ，Δ〕应是一原子析舍，并且有恒假公式〔〕属于│Γ，Δ│或者有命题符P与其否定〔p〕同属于│Γ，Δ│。由于│Γ，Δ│＝│Γ│∪│Δ│，我们又有下列三种子情形要考虑：
子情形（i）.〔〕属于│Γ│或者│Δ│。当〔〕属于│Γ│时，只须取A为〔〕，易证它即为所求。类似地，当〔〕属于│Δ│时， 只须取A为公式〔〔〕〕就行。
子情形（ii）.p和〔p〕同属│Γ│或同属│Δ│。 当同属│Γ│时取A为〔〕；当同属│Δ│时取A为〔〔〕〕；易证，所取的A 即为所求。
子情形（iii）.p和〔p〕二者同属│Γ│和│Δ│。 此时只须取A为属于│Γ│的那个p或〔p〕就行。
情形2.〔Γ，Δ〕在证明中由推证规则（Ⅰ）而得。这也就是说，公式〔Γ，Δ〕有一个直接子公式形如〔〔A[,0]，…，A[,n-1]〕〕，并且在〔Γ，Δ〕的证明中有一个先于它出现的公式形如〔Γ′，Δ′〕；这里，当〔〔A[,0]，…，A[,n-1]〕〕出现在序列Γ中时，Δ′为Δ，Γ′为在Γ中删去此公式两边的两个左括号和两个右括号后所得到的序列；当〔〔A[,0]，…，A[,n-1]〕〕出现在序列Δ中时，Γ′为Γ，而Δ′则为在Δ中删去此公式两个左括号和两个右括号后而得的序列。公式〔Γ′，Δ′〕的证明长度小于n，因此据归纳假设可知， 有相应于始段Γ′的插入式A。由于一命题符在A[,i]（i＝0，…，n－1）中某出现的正负性相同于该出现在〔〔A[,0]，…，A[,n-1]〕〕中的正负性，我们不难验证A也是公式〔Γ，Δ〕的相应于始段Γ的插入式。
情形3.〔Γ，Δ〕在证明中由推证规则（Ⅱ）而得。这也就是说，公式〔Γ，Δ〕有一个直接子公式形如〔A[,0]，…，A[,n-1]〕，n ≥2，并且在〔Γ，Δ〕的证明中有n个先于它出现的公式分别形如〔Γ[,0]，Δ[,0]〕，…，〔Γ[,n-1]，Δ[,n-1]〕；这里，当〔A[,0]， …，A[,n-1]〕出现在Γ中时，Δ[,0]、…、Δ[,n-1]都为Δ，而各个Γ[,i]（i＝0，…，n－1）为在Γ中将此公式换成A[,i]后所得的序列；当〔A[,0]，…，A[,n-1]〕出现在Δ中时，Γ[,0]、…、Γ[,n-1]都为Γ，而各个Δ[,i]（i＝0，…，n－1）为在Δ中将此公式换成A[,i] 后而得的序列。可证公式〔Γ[,0]，Δ[,0]〕、…、〔Γ[,n-1]，Δ[,n-1]〕的证明长度都小于n，因此据归纳假设可知，有相应于始段Γ[,i]的插入式B[,i]，i＝0，…，n－1。当〔A[,0]，…，A[,n-1] 〕出现在序列Γ中时，取A为〔〔B[,0]，…，B[,n-1]〕〕；而当〔A[,0]，…，A[,n-1]〕出现在序列Δ中时，则取A为〔〔B[,0]，…，B[,n-1]〕〕。不难验证，A即为所求的插入式。
至此，我们完成了归纳步骤，从而据归纳法可知原结论成立，即，对于任意可证公式的任一始段总有相应的插入式。证毕
取Γ为仅以公式A为单独一项的序列并且取Δ为仅以公式〔B〕为单独一项的序列，那么作为插入定理的特例，我们将有以下两个定理，证明从略。
Lynden插入定理.如果公式〔A，〔B〕〕在系统Z中可证，则有公式C使得公式〔A，〔C〕〕和〔C，〔B〕〕都在系统Z中可证，并且出现在C中的命题符也以同样的正负性出现在A和B中。
Craig插入定理.如果公式〔A，〔B〕〕在系统Z中可证， 则有公式C使得公式〔A，〔C〕〕和〔C，〔B〕〕都在系统Z中可证，并且C 中出现的命题符也都在A和B中出现。
推论.如果公式〔A，〔B〕〕在系统Z中可证，并且A和B无共同的命题符，则〔A〕和B中有一是在系统Z中可证的。
证明：由于A和B无共同的命题符，〔A，〔B〕〕的插入式C 中将不出现命题符，从而C必定等值于〔〕或〔〔〕〕。当C等值于〔〕时，由〔A，〔C〕〕可证可知〔A〕也可证；当C等值于〔〔〕〕时，由〔C ，〔B〕〕可证可知〔〔B〕〕可证，因此B不得为命题符，从而B也可证。所以，〔A〕和B中有一是可证的。
证毕