一个命题逻辑的排斥演算系统

杜国平



一个命题逻辑的排斥演算系统

杜国平

摘要：在日常推理中，一般的非有效式比逻辑矛盾具有更大的隐蔽性，通过对卢卡西维茨的工作进行改造，可以建立一个排斥所有非有效式的演算系统，并对其可靠性和完全性给出严格的证明。在此基础上，证明了排斥系统和证明系统的不同性质，这有利于人们进一步认识谬误的本质。

关键词：非有效式；排斥演算；等谬

逻辑矛盾是我们在一个正确推理或者论证中首先必须加以拒斥的*参见杜国平、赵曼《一阶谓词逻辑反驳演算自然推理系统》(《重庆理工大学学报》2013年第9期，第1~6页)，杜国平《一个命题逻辑的反驳演算系统》(《哲学研究》2014年第2期，第118~125页)。，另外，对于一些并非是逻辑矛盾但也不是有效推理形式的推理或者论证我们也必须加以排斥。而且，这些不是逻辑矛盾的非有效推理形式其谬误往往具有更大的隐蔽性，在日常的论证中也常常被不知不觉地广泛使用，这尤其需要引起逻辑研究者的注意。

卢卡西维茨曾经天才地指出了一个排斥所有非有效式的公理系统的框架*卢卡西维茨：《亚里士多德的三段论》，李真、李先琨译，北京：商务印书馆，1981年，第118~150页。，本文将在卢卡西维茨工作的基础上，对其公理系统进行适当的改造，构建一个排斥所有非有效式的演算系统，并对其中的演算过程进行比较充分的展开和讨论；随后，在给出严格语义的基础上，进一步证明该系统的可靠性和完全性。本文拟通过上述工作进而来探究如下若干问题：各种谬误的逻辑起点在哪里？如果有逻辑起点，那么为什么是它(或它们)？各种谬误之间的逻辑结构是什么？各种谬误如何公理化？如何证明排斥系统的可靠性和完全性？排斥系统和证明系统有什么本质区别？

一、排斥演算的公理系统

命题逻辑排斥演算的形式语言包括如下三类符号：

(1)命题符号：p1,p2, …,pn, …

(3)技术性符号：), (

定义1.1命题逻辑排斥演算中的公式指的是当且仅当由使用下列规则生成的有限长的符号串：

(1)单独一个命题符号是公式；

(2)如果A是公式，那么(A)也是公式；

(3)如果A、B是公式，那么(AB)也是公式。

由单独一个命题符号构成的公式称之为原子公式，我们以小写字母p、q、r等表示任一原子公式，以大写字母A、B、C等(或加下标)表示任意一个公式，以符号、、等表示任意的公式集。下面引入3个定义连接词符号：

ABdef(AB)

ABdef((AB))

ABdef((AB)(BA))

在不引起歧义的情况下，括号可以省略。

定义1.2如果以公式A1、A2、A3、…替换公式B中各处出现的命题变元p、q、r、…，得到公式A，则称公式A是B的代入，记为AB(p/A1, q/A2, r/A3,)。

命题逻辑排斥演算系统E包括如下两组公理模式和推理规则：

第一组：

证明公理：

证明规则：

第二组：

排斥公理：p

排斥规则：

(2)如果A是B的一个代入，并且A被排斥，则排斥B。简记为E2。

(1)Ak是证明公理；

(2)Ak；

公式序列A1, A2, …,An1,An称之为公式A的一个证明。

如果公式A由公式集形式可证明，则称可证明出A，符号记为├EA，也简记为：├A。

定义1.4如果公式A由形式可证明，则称公式A是可证明的。由到A形式可证明的一个公式序列称为公式A的一个证明。如果公式A是可证明的，则称公式A为排斥演算系统E的定理，符号记为：├EA，也简记为：├A。

定义1.5公式A形式可排斥，当且仅当存在公式序列A1,A2, …,An1, An，使得AnA且An是通过排斥公理或者排斥规则得到，并且对于每一个Ak(1kn)，Ak满足下列条件之一：

(1)Ak是证明公理；

(2)Ak是排斥公理；

(3)有i，jk，使得AiAjAk；

(4)Ak由在它前面的公式通过使用排斥规则E1或者E2而得到。

公式序列A1,A2, …,An1, An称之为公式A的一个排斥。

定义1.6如果公式A形式可排斥，则称公式A为排斥演算系统E的谬论，符号简记为：★A。

在一个证明或者排斥中，我们将直接使用已经证明或者排斥的定理或者谬论。

关于一个定理的证明，在一般的现代逻辑教科书中都有比较详细的表述*参见Elliott Mendelson, Introduction to Mathematical Logic, Florida：CRC Press, 2010.，本文不再重复，以下只是列出在后面的排斥中将要用到的一些主要定理。

定理1.1

(2)├((qq)p)p

(3) ├(pp)p

(6)├(pq)(pq)

(7)├pqp

(8)├AAB

(9)├A(AB)

(10)├A(BB)A

(11)├A(BB)A

(12)如果A├B，则├AB

(13)如果├ABC，则├CAB

排斥

定理1.1(1)

(2)★p

排斥公理

(1)(2)E1

(3)E2(p/pq)

这表明任一原子公式的否定都是谬论，都可以被排斥演算系统E所排斥。

谬论1.2★pq(其中p、q是不同的原子公式)

排斥

(1)((qq)r)r

定理1.1(2)

(2)★r

排斥公理

(3)★(qq)r

(1)(2)E1

(4)★pq(其中p、q是不同的原子公式)

(3)E2(p/qq,q/r)

这表明任一前后件是不同原子公式的蕴涵式都是谬论，都可以被排斥演算系统E所排斥。

谬论1.3★pq

排斥

(1)(pp)p

定理1.1(3)

谬论1.1

(3)★pp

(1)(2)E1

(4)★pq

(3)E2(p/p,q/p)

这表明以任一原子公式作为前件、以任一原子公式的否定作为后件而构成的蕴涵式都是谬论，都可以被排斥演算系统E所排斥。

排斥

定理1.1(4)

(2)★q

排斥公理

(1)(2)E1

(3)E2(p/q,q/q)

这表明以任一原子公式的否定作为前件、以任一原子公式作为后件而构成的蕴涵式都是谬论，都可以被排斥演算系统E所排斥。

排斥

定理1.1(5)

(2)★pq

谬论1.2

(1)(2)E1

(3)E2(p/pq,q/p)

这表明以任意不同原子公式的否定作为前后件而构成的蕴涵式都是谬论，都可以被排斥演算系统E所排斥。

谬论1.6★pq

排斥

(1)(pq)(pq)

定理1.1(6)

谬论1.4

(3)★pq

(1)(2)E1

这表明任意两个原子公式的析取式都是谬论，都可以被排斥演算系统E所排斥。

类似可以排斥以下3个谬误：

谬论1.8★pq(其中p、q是不同的原子公式)

对于合取式，也有类似的谬误可以被排斥：

谬论1.10★pq

排斥

(1)pqp

定理1.1(7)

(2)★p

排斥公理

(3)★pq

(1)(2)E1

这表明任意两个原子公式的合取式都是谬论，都可以被排斥演算系统E所排斥。

类似可以排斥以下3个谬误：

谬论1.12★pq

作为一个非常特殊的谬误——逻辑矛盾式AA，在排斥演算系统E中也可以被排斥：

谬论1.14★AA

(1)AAp

定理1.1(8)

(2)★p

排斥公理

(3)★AA

(1)(2)E1

根据命题逻辑的可靠性定理可知，所有命题逻辑系统的定理A都是永真式，因而其否定A都是矛盾式。以下定理表明，所有矛盾式在排斥演算系统E中都可以被排斥：

定理1.2如果├A，则★A。

证明

(1)A

前提

(2)A(Ap)

定理1.1(9)

(1)(2)MP

(4)★p

排斥公理

(1)(2)E1

下面我们来排斥一个更一般的谬论：

谬论1.15★A1A2…An1An(其中每一Ak(1kn)是任一原子公式或者原子公式的否定，并且所涉及的原子公式各不相同)

排斥

施归纳于其中所涉及的原子公式的数目k。

当k1时，A1或者是p或者是p，根据排斥公理和谬论1.1，命题成立。

假设当kn1时命题成立，下面来证明当kn时命题也成立。

可分如下两种情况排斥A1A2…An1An：

情况一：An是原子公式p

(1) (A1A2…An1(AnAn))(A1A2…An1)

定理1.1(10)

(2)★A1A2…An1

归纳假设

(3)★A1A2…An1(AnAn)

(1)(2)E1

(4)★A1A2…An1p

(3)E2(p/AnAn)

情况二：An是原子公式的否定p

(1) (A1A2…An1(AnAn))(A1A2…An1)

定理1.1(11)

(2)★A1A2…An1

归纳假设

(3)★A1A2…An1(AnAn)

(1)(2)E1

(4)★A1A2…An1p

(3)E2(p/(AnAn))

二、排斥演算的语义

定义2.1一个真值赋值v是以所有公式的集为定义域、以{0,1}为值域的一个函数，并满足下列条件：

(1)v(A)1，当且仅当v(A)0；

(2)v(AB)1，当且仅当v(A)0或者v(B)1。

定义2.2对于任一公式A，如果对于任一赋值v，均有v(A)1，则称公式A是永真式，记为：╞A；对于任一公式A，如果存在赋值v，使得v(A)0，则称公式A是非永真式，记为：☆A。

根据定义，显然可得：

定理2.1☆p。

即排斥公理是非永真式。

定理2.2如果╞AB，并且☆B，则☆A。

证明：假设☆B，根据定义2.2，则存在赋值v，使得v(B)0。因为╞AB，所以有v(AB)1，根据语义定义2.1，可得v(A)0，因此有☆A。

该定理表明，排斥规则E1是保持非永真性的。

定理2.3如果A是B的一个代入，并且☆A，则☆B。

证明：假设AB(p/A1,q/A2,r/A3,)，如果☆A，根据定义2.2，则存在赋值v，使得v(A)0。现构造一个赋值v′，令v′(p)v(A1),v′(q)v(A2),v′(r)v(A3),，则有v′(B)v(A)0，因而有☆B。

该定理表明，排斥规则E2是保持非永真性的。

三、排斥演算的可靠性和完全性

根据上述定理2.1、定理2.2和定理1.2.3，可以得出关于命题逻辑排斥演算系统E的一个重要元定理：

定理3.1(可靠性定理)设A为任一公式，如果★A，则☆A。

定理3.2设A为任一公式，A1,A2, …,An1,An是其中出现的所有不同的原子公式。对于任一给定的赋值v，如果v(Ak)1(1kn)，则令Ak′Ak；如果v(Ak)0(1kn)，则令Ak′Ak。在该赋值v下，如果v(A)1，则令A′A；如果v(A)0，则令A′A。则有：A1′,A2′, …,An1′,An′├A′。

证明：施归纳于公式A中连接词和的数目n。

当n0，即A中没有连接词和，则A即为原子命题p。因此在赋值v下，如果v(p)1，则v(A)1，所需证明的即为p├p；如果v(p)0，则v(A)0，所需证明的即为p├p。无论在哪种情况下，原命题都显然成立。

假设原命题在A中连接词和的数目小于n时都成立，则当A中连接词和的数目为n时，可有如下两种情况：

情况一：AB。在赋值v下，如果v(B)1，则有v(A)0，A′A，由v(B)1根据归纳假设有A1′,A2′, …,An1′,An′├B，因而有A1′,A2′, …,An1′,An′├B，即有A1′,A2′, …,An1′,An′├A，因而所需得证；如果v(B)0，则有v(A)1，A′A，由v(B)0根据归纳假设有A1′,A2′, …,An1′,An′├B，因而有A1′,A2′, …,An1′,An′├A，因而所需得证。

情况二：ABC。

情况二(1)，在赋值v下，v(B)1并且v(C)1，则有v(A)1，A′A。由v(B)1并且v(C)1根据归纳假设有A1′,A2′, …,An1′,An′├B，A1′,A2′, …,An1′,An′├C，因而有A1′,A2′, …,An1′,An′├BC，即有A1′,A2′, …,An1′,An′├A，因而所需得证。

情况二(2)，在赋值v下，v(B)1并且v(C)0，则有v(A)0，A′A。由v(B)1并且v(C)0根据归纳假设有A1′,A2′, …,An1′,An′├B，A1′,A2′, …,An1′,An′├C，因而有A1′,A2′, …,An1′,An′├(BC)，即有A1′,A2′, …,An1′,An′├A，因而所需得证。

情况二(3)，在赋值v下，v(B)0并且v(C)1，则有v(A)1，A′A。由v(B)0并且v(C)1根据归纳假设有A1′,A2′, …,An1′,An′├B，A1′,A2′, …,An1′,An′├C，因而有A1′,A2′, …,An1′,An′├BC，即有A1′,A2′, …,An1′,An′├A，因而所需得证。

情况二(4)，在赋值v下，v(B)0并且v(C)0，则有v(A)1，A′A。由v(B)0并且v(C)0根据归纳假设有A1′,A2′, …,An1′,An′├B，A1′,A2′, …,An1′,An′├C，因而有A1′,A2′, …,An1′,An′├BC，即有A1′,A2′, …,An1′,An′├A，因而所需得证。*该定理的证明主要参考了Elliott Mendelson的思想,见Elliott Mendelson, Introduction to Mathematical Logic, pp.32-33.

定理3.3(完全性定理)设A为任一公式，如果☆A，则★A。

证明：假设A1,A2, …,An1,An是A中出现的所有不同的原子公式，如果☆A，则存在一赋值v，使得v(A)0。根据定理3.2可得：A1′,A2′, …,An1′,An′├A，由此可得如下排斥序列：

(1)A1′,A2′, …,An1′,An′├A

已知

(2)A1′A2′…An1′An′A

定理1.1(12)

(3)AA1′A2′…An1′An′

定理1.1(13)

(5)★A

(3)(4)E1

四、排斥演算的特殊结果

在经典命题逻辑的证明系统中，p和pq不是逻辑等值的，因而在下列两个陈述中只有一个是成立的。

(1)p├pq

(2)pq├p

即只有(1)成立，(2)不成立。

但是在排斥系统中，有下列定理：

定理4.1

(1)如果★p，则★pq

(2)如果★pq，则★p

证明1

(1)★p

前提

(2)p(AA)p

定理1.1(10)

(3)★p(AA)

(1)(2)E1

(4)★pq

(3)E2(q/AA)

证明2

(1)★pq

前提

(2)★p

(2)E2(p/pq)

定义3.1设A、B为任意公式，如果★A当且仅当★B，则称A和B等谬，简记为：★A★B。

定理4.2★pq★pq

证明

(1)★pq

前提

(2)pqpq经典命题逻辑证明系统定理

(3)★pq

(1)(2)E1

(4)★pq

前提

(5)(pq)(AA)pq

经典命题逻辑证明系统定理

(6)★(pq)(AA)

(4)(5)E1

(7)★pq

(6)E2(p/pq,q/AA)

定理4.1和定理4.2表明，pq和pq都可以代替排斥公理p来作为命题逻辑排斥系统的唯一一条公理。

责任编校：余沉

作者简介：杜国平，中国社会科学院哲学研究所研究员，哲学博士、工学博士(北京100732)。

基金项目：国家社科基金重大招标项目(14ZDBO14)

中图分类号：B812.5

文献标识码：A

文章编号：1001-5019(2015)01-0042-05

DOI：10.13796/j.cnki.1001-5019.2015.01.005