不用联结词的经典命题逻辑系统，本文主要内容关键词为：命题论文,逻辑论文,经典论文,系统论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
一阶逻辑是现代逻辑中最简单、最有力、最有用的部分，经典命题逻辑是这一部分的基础。常见的经典命题逻辑系统中总是联结词和括号兼而用之，也就是说构作合式公式时所要求于它们的联结作用和分组作用分别由两类符号承担。实际上，这两种作用在经典命题逻辑系统中是可以由一类符号来承担的。卢卡西维茨(J.Lukasiewicz，1878-1956)采用前置法使联结词兼具括号的作用，创造了一套没有括号、书写简便、使用准确的符号，以“波兰符号”名满天下。本文的目的是建立不用联结词的经典命题逻辑系统，以此表明括号也能兼具联结词的作用。逻辑学家们为经典命题逻辑创制了多种证明方法，常见的有：自然推理、公理系统、后承演算和语义表列。本文将相应于这种种证明方法来建立不用联结词的系统，因此本文也可说是经典命题逻辑证明方法的一个简练而概括的综述。
一、语形
我们首先确定所使用的形式语言。 定义1.1.我们选取的形式语言有下列三类初始符号：
(1)命题变项：p[，0]，p[，1]，p[，2]，……；命题变项的全体记作P；元变元用p，q等；
(2)命题常项：t；
(3)括号：(，)；分别称为左、右括号。
由初始符号组成的有穷序列，叫作表达式。我们仅对这些表达式的一部分感兴趣，这部分由下面的定义1.2确定。 定义1.2.所谓公式，由下列递归规则给出：
(1)命题变项和命题常项都是公式；
(2)如果表达式A和B都是公式，那么表达式(AB)也是公式。
字母A，B，C等表示任意公式；全体公式所组成的集合记作F。公式的最外层括号常略而不写，即，(AB)可简记成AB。在公式概念的定义下，我们有下面的唯一分解定理；其证明从略，引用此定理时也常不加说明。 唯一分解定理。对任一个公式A，下列(1)、(2)、(3)中有且只有一个成立：
(1)A是某个命题变项；
(2)A是命题常项t；
(3)有唯一确定的两个公式B和C使得A为(BC)。
由此可知，每个公式有且仅有下列三种形式之一：p，t和(BC)。所以，要想在F上定义一个映射可以如下进行：
(1)对各个命题变项赋值；
(2)对命题常项t赋值；
(3)假定已经对公式B和C赋值，然后对公式(BC)赋值。 这种定义方式被称为公式上的归纳定义。下面的定义1.3就是利用这种定义方式作出的，以后使用这种方式时不再一一申明。 定义1.3.映射sub定义如下：
(1)sub(p)=｛p｝；
(2)sub(t)=｛t｝；
(3)sub(BC)=｛(BC)｝∪sub(B)∪sub(C)。
映射sub为每个公式A指定一个公式集sub(A)，其中的元素被称为A的子公式。不同于A的子公式，被称为A的真子公式。任一个公式中出现的左括号总数跟右括号总数是相同的。这个总数表示着公式的复杂程度，称作公式的复杂度。有关公式的一些性质，常常是施归纳于这个复杂度上来证明的。能如此进行证明的根据就在于，一公式A的真子公式的复杂度低于A的复杂度。
二、命题语义
初始符号本身并无任何意义，只表示其自身。公式也只是一串初始符号，只有当给这些初始符号以一定的解释后它们才有意义。所谓命题语义，也就是命题逻辑中所使用符号的含义的解释。命题逻辑中公式的涵义总是相对于某一给定的命题语义的。定义2.1.一个真值赋值。就是对每个公式A指定一个真值的一个映射，即，从F到｛0，1｝的一个映射，并满足下述条件：
；
。 我们称从P到｛0,1｝的映射为真值指派。每一个真值赋值确定一个真值指派；另一方面，每一个真值指派也唯一确定一个真值赋值。因此，我们只须确定一个真值指派，也就确定了一个真值赋值。根据定义2.1，我们定义常见的命题联结词如下：
～A指(tA)；
A∧B指(A(tB)；
A∨B指(t((tA)B))；
AB指(t(AB))；
A≡B指((t(AB))(BA))。 定义2.2.称公式A为可满足的，仅当有一真值赋值使它为真。称公式集Γ为可满足的，仅当有一真值赋值使Γ中任一公式都为真。称公式A为重言式，仅当任一真值赋值都使它为真。称公式A为公式集Γ的重言后承，仅当使Γ中任一公式为真的真值赋值也一定使A为真。定义2.3.令C是由一些公式集组成的类。
称C为一个协调类，仅当C中各个公式集Γ符合下列条件：
(1)(tt)不属于Γ；Γ不包含｛p，(tp)｝；
(2)如果(AB)属于Γ，则Γ∪｛A｝和Γ∪｛(tB)｝都属于C；
(3)如果(t(AB))属于Γ，则Γ∪｛(tA)｝和Γ∪｛B｝中至少有一个属于C。
如果对任一个Γ而言，Γ属于C当且仅当Γ的各个有穷子集都在C中，则称C为具有有穷性征的。 引理1.任一个协调类C都可扩张成具有有穷性征的协调类。证明：首先作一个类C′：
C′=｛Γ：Γ是C中某个公式集的子集｝。易证，C′是包含C的一个协调类。C′对于子集是封闭的，即，如果属于C′并且是的子集则也属于C′。然后，再作一个类C″：
C″=｛Γ：Γ的有穷子集都在C′中｝。同样易证，C″是包含C′(从而包含C)的一个协调类。此外，不难验证C″具有有穷性征。C″即为所求。
下面，我们先叙述选择公理的一个等价形式——Tukey引理，然后用它建立引理2，最后证明命题逻辑的一个基本定理。 Tukey引理。各个具有有穷性征的非空类有极大元。 引理2.令C是一个具有有穷性征的协调类。那么，C的任一个元素都可扩张成极大元。证明：设Γ属于C。作一个类D：
D=｛△：Γ∪△属于C｝。
可以验证，D是具有有穷性征的非空类。由Tukey引理可知，D有一个极大元△[，0]。由于△[，0]属于D，Γ∪△[，0]也属于C。Γ∪△[，0]就是所要求的、C的极大元。 基本定理。令C是一个协调类。如果Γ属于C，则Γ是可满足的。证明：据引理1可知，C可以扩张成一个具有有穷性征的协调类C′，显然Γ属于C′。从而由引理2可知，C′中有包含Γ的极大元△；利用△，我们可以作出这样一个真值指派：当且仅当命题变项p属于△时它为p指定1。这个真值指派确定了唯一的一个真值赋值
满足△；从而，也满足Γ。
利用这一基本定理，我们可以从语义方面直接证明经典命题逻辑的紧致性定理和Craig插入定理，并得到经典命题逻辑的可判定性，详细论证请参看文献[1]和[2]。
三、自然推理系统
自然推理方法把直观的衍推概念归结为可推演性的形式概念。这方法在大很大程度上是自然的、经济的，它的基础是熟知的演绎定理。这方法对于如何构作具体的证明提供了较多的指示，所作出的证明也比较短，主要缺点是它对于如何反驳可以反驳的公式缺乏指示。
经典命题逻辑的自然推理系统就是按自然推理方法构造起来的系统。这种系统有两个主要特点。一是它只有推理规则，而且这些规则也不像公理系统中推证规则那样必须以公理或已证公式进行推导。另一个特点是，各个联结词在推导中都有规律地按两条规则来运用：一条是引入规则，告诉我们怎样才能推出一个以所给联结词为主联结词的公式；另一条是消去规则，告诉我们怎样从一个以所给联结词为主联结词的公式推出进一步的结论，消去所给联结词。自然推理系统的最大优点就在于实际作推导时比较容易，不过它的算术化不如公理系统简单。
我们采用的自然推理系统中的推理规则表述如下：
(1)Hyp（假设引入规则）：可按需要随时引入一个假设，以此来开始一个子证明。
(2)Rep（重复规则）：同一个子证明中的公式可以在该子证明中重复出现。
(3)Reit（重述规则）：子证明中的公式可以在从属于它的子证明中重述出现。
(4)( )I（括号引入规则）：从A和(tB)可推出(AB)。
(5)( )E（括号消去规则）：从(AB)可推出A和(tB)。
(6)t（t＿规则）：从由(tA)导出B和(tB)的子证明可推出A。这些规则的图示如下：
我们以字母N表示这个系统。
一个推导就是按照上述规则构造起来的一个有穷的公式序列。推导分成两种：假设性的和非假设性的。推导过程中引进的假设并未都用t＿规则消除的推导是假设性的，其它推导是非假设性的。当公式A为某个非假设性推导的最后一步时，则称A为可证的或定理，记成┡ΝA；同时也称该推导为A的一个证明。在系统N中可以导出下列推理规则：
同时运用初始推理规则和这些导出规则在系统N中作推导还是相当方便的，下面是几个例子。
所以，Ａ是可证的。
四、公理系统
公理化方法用形式的对象语言的蕴涵概念替换直观的元语言的衍推概念，将我们对于逻辑的直观归结为逻辑联结词的形式化理论。
经典命题逻辑的公理系统就是按公理化方法构造起来的系统。这种系统是历史上最早出现的经典命题逻辑证明方法，也被称为希尔伯特型系统。公理系统的主要优点之一就是系统的描述比较简单，只要确定一些重言式为公理和确定若干推证规则（从可证公式推导可证公式的规则)，一个系统也就随之确定。许多公理系统只有一条推证规则，也就是假言推理规则MP。因此，这一类系统很适于算术化。另一个优点是，一系统的加强或减弱可以由公理的增减来实现。这一点对于研究非经典命题逻辑显得更为重要。公理系统的缺点就在于，在系统中实际进行推导时麻烦而不直观。但是，如果允许从假设作证明，则推导就比较容易。因此，演绎定理的证明在这种系统中相当重要。
我们采用的公理系统（记为H)只有一条推证规则(t)E：从A和t(AB)可推出B。它的全部公理模式如下：
可靠性定理的证明是容易的，只须证明公理是重言式，而规则(t)E保持重言性，也就是说当它的两个前提为重言式时所得的结论也是重言式。完全性定理的证明完全如前一样，利用基本定理来做。
五、后承演算和表列系统
根岑(G.Gentzen，1909-1945)的后承演算是经典命题逻辑的一种树式证明方法。这种方法现在有多种变型，这里我们描述的是一种对称性说法。
所谓一个后承Γ→△，是指由公式集Γ和△组成和序对＜Γ，△＞。当Γ为空的公式集时，“Γ→△”简记成“→△”；当△为空的公式集时，则简记成“Γ→”。“Γ∪｛A｝→△”简记成“Γ，A→△”；“Γ→△∪｛A｝”简记成“Γ→△，A”。
我们的对称性后承演算G有下列公理和规则。在下面的叙述中，Γ和△都只表示有穷的公式集。
公理：p指任一命题变项。
；
规则：
；
利用后承演算G，可以给出Craig插入定理的一个语形证明，请参看文献[1]和[2]。
从完全性定理可以看出，后承演算G跟自然推理系统N是等价的，也就是说，对于任一公式
。这一等价也可直接证明，不过要复杂得多。
我们最后要作的是语义表列系统。这种证明方法是后承演算的一种对偶形式，G中的证明像一棵树从下往上长，可下面的语义表列系统S中的证明却是一棵从上往下长的倒立树。
语义表列系统S中的证明以倒立树的形式表示，出现在树的各个结点上的是公式。给定一棵树，我们可以引用下列分枝扩张规则之一来使这棵树往下长成一棵新树：
称一个分枝为封闭的，仅当有某个公式A与其否定tA同在此分枝中出现。称一棵树为封闭的，仅当它的所有分枝都是封闭的。一个表列就是按分枝扩张规则长成的一棵树。
公式A的一个证明就是以tA为出发点的一个有穷的封闭表列，即，结点个数有穷、所有分枝都封闭的一棵树；此时，我们记
；
称一分枝为可满足的，仅当该分枝中全体公式组成的公式集是可满足的。称一表列为可满足的，仅当它的某个分枝是可满足的。显然，封闭表列是不可满足的。利用下面的引理，我们就能得到S的可靠性定理。
引理。令T是一可满足的表列，T′是由T引用一次分枝扩张规则而得的表列。那么T′也是可满足的。
可靠性定理。如果则A是重言式。
完全性定理。当且仅当A是重言式。
证明：设A是重言式。作一个类C：
C=｛Γ：没有以c(Γ)为出发点的封闭表列｝；这里，c(Γ)指Γ中全部公式的合取。不难验证，C是一个协调类。
如果┡sA不成立，则没有以tA为出发点的封闭表列；从而，｛tA｝属于C。据基本定理可知，｛tA｝是可满足的。因此，A不是重言式，引出矛盾。所以，┡sA成立。
以上所作的系统N、H、G和S都用到命题常项t。我们也可利用命题常项f（指恒假命题)来作不用联结词的经典命题逻辑系统。命题常项是零元联结词，因此利用它们建立的不用其他联结词的系统还不能说是十分严格的不用联结词的系统。不过，在语义中稍作修改就可抛弃命题常项而得到严格的不用联结词的系统。例如，将定义2.1中的(2)改成如下：
；
实际上也就是用我们的括号替代舍弗的竖记号。这一切就不在这里详细进行了。