关于“不用联结词的逻辑系统”的注记

杜国平

(中国社会科学院 哲学研究所， 北京 100732)

张清宇先生从1995年开始发表文章，阐述其在形式语言中只用括号、不用联结词的基本思想，并构建了一系列逻辑系统。本文拟对先生的这一开创性工作做一些阐发，并对相关研究工作做进一步推进。张清宇先生已经离开8年了，但授课之状仍历历在目，谨以此文缅怀先师。

一、括号表示法

一个逻辑系统的形式语言基本上包括三类符号：变元符号、常元符号和结构符号。变元符号一般指的是在给定论域中表示不确定对象的符号，如命题变元p、q、r等等，个体变元x、y、z等；常元符号指的是在给定论域中表示确定对象的符号，如命题常元符号T，真值联结词符号﹁ 、∧等；结构性符号指的是确定符号之间的间隔、结合和顺序关系的符号，它发挥确定符号的结合顺序、运算层次和排除歧义的功能，如逗号、左右括号等。在一般的逻辑系统中，三类符号各司其职，协同发挥着描述所研究对象的功能。

张清宇先生则创造性地建立了一套新的符号系统，这套符号系统只使用括号而不使用命题联结词和量词，使括号既表达特定联结词的逻辑功能又发挥括号本身的结构性功能。在文献[2]中，其技术处理的核心要旨是使用命题常项“t”和括号“( )”发挥命题联结词的作用。“(AB)”相当于“A∧(﹁B)”，即对于一个真值赋值v，v(t)=1；v((AB))=1当且仅当，v(A)=1且v(B)=0。在文献[3]和[4]中，使用命题常项“T”和括号“( )”发挥命题联结词的作用，并扩展为使用括号“( )”进一步发挥量词的作用。“(AxB)”相对于“∃x(A∧﹁B)”，即，给定一个模型U=(D,I)和U的一个指派α，TI,α=1；(AB)I,α=1当且仅当，AI,α=1且1I,α=0；(AxB)I,α=1当且仅当，对α的某个x-变异1，(AB)I,β=1。其他联结词均可以通过定义而引入，如：

A∧B=def(A(TB))

A∨B=def(T((TA)B))

A→B=def(T(AB))

∃xA=def(Tx(TA))

∀xA=def(T(TxA))[4]25-68

这样，括号一方面发挥了结构性功能，另一方面也可同时表达命题联结词和量词的功能。准确、简洁，完全可以媲美波兰表示法！

在此，需要澄清一个问题，“不用联结词”指的是在形式语言中没有直接使用常用的命题联结词符号，并非指的是在形式语言中语义上完全没有表达联结词功能的符号。今后，我们将把在形式语言中不用联结词而只使用括号的逻辑符号表示法统称为括号表示法，以区别并比照于波兰表示法。

一个符号往往承载着不同的功能，如符号C通常作为一个英文大写字母，但是在波兰表示法中，它具体的语义功能是表示命题联结词的“蕴涵”。因此，形式语言中的符号至少存在着两个功能：一是在语法层面上的语形功能，一个是在解释层面上的语义功能。在波兰表示法中，符号N、A、K、C等一方面在语形上是命题之间的连接符号，另一方面在语义功能上承载着真值函数运算功能和结合的次序功能。同样，在括号表示法中，括号作为一个技术性符号，它语形上呈现的是结构性功能，但是在语义上，它也同时承载着真值函数的运算功能和结合的次序功能。所以，无论是不用括号的卢卡西维茨的波兰表示法还是只用括号的括号表示法，都仅仅指的是在语形上的呈现，而不是指它们在语义层面上没有排除歧义等的结构功能或表达逻辑运算的真值函数功能。所以，“不用联结词”仅仅指的是语形层面上的，而不是语义层面上的。在语义功能上，不论是波兰表示法还是括号表示法，无疑都有承载真值函数功能的“联结词”。

机器识别的首先是语形层面上的形式语言，无论是波兰表示法还是括号表示法均如此，因为其符号简单、无歧义，便于机器的实现和识别，这是其独特的应用价值。另外，探究符号的不同表达功能，可以进一步加深对符号形式处理技术的理解。可以认为，波兰表示法和括号表示法是逻辑符号表示法的两个相互映衬的典范！

二、0元联结词

逻辑联结词在语形上的作用是作用于已有公式之上形成新的公式，如一元联结词“﹁ ”作用于单个公式“p”之上可形成新公式“(﹁p)”，二元联结词“C”作用于两个公式“p”“q”之上可形成新公式“Cpq”。“T”作用于0个公式之上形成公式“T”，在此意义上，可将“T”视为0元联结词。从语义上看，在通常的语义解释中，对于一个真值赋值v，v(﹁α)=1-v(α)，“﹁ ”是一个1元函数运算；v(α∧β)=min(v(α),v(β))，v(α∨β)=max(v(α),v(β))，v(α→β)=max((βαv(α)),v(β))，“∧”“∨”“→”均是一个2元函数运算。而v(T)=1，恰是一个0元函数运算。因此，“T”可看作一个0元联结词，这正如在一阶语言中，将个体常项看成0元函数符号一样[4]26。

但如果纯粹从语形层面来看，“T”无疑是作为一个命题常项出现的。因此，在文献[2][3]和[4]等的括号表示法中，说“不用联结词”是完全可以的。

三、独立性

张清宇先生在文献[2]建立的公理系统H中，可能是出于对括号的引入和消去的考虑，有形如t(A(t((tB)(AB))))、t((AB)A)和t((AB)(tB))等公理，这增强了公理系统的直观性，也便于简化系统内定理的证明。但是，如果从公理系统的简洁性方面去考虑，这些公理并非都是必须的。

下面，我们将证明公理系统H中的公理模式(也简称为公理)并非都是必须的，即公理系统H不具有独立性。我们可以将公理系统H进行简化，删除其中的公理1、公理4和公理5，只保留其中的公理2、公理3、公理6等3条公理和推理规则t(E)，简化后的公理系统简记为QY。即公理系统QY包括如下公理(模式)和推理规则：

1. t(At(BA))

公理系统H之公理2

2. t((t(A(t(BC))))(t((t(AB))(t(BC)))))

公理系统H之公理3

3. t((t((tA)B))(t((t((tA)(tB)))A)))

公理系统H之公理6

推理规则即公理系统H之推理规则t(E)：由A和t(AB)可得出B。

可以证明公理系统H中的公理1、公理4和公理5都是系统QY的定理。

1. t((t(A(t((t(AA))A))))(t((t(A(t(AA))))(t(AA)))))

公理系统QY之公理2

2. t(A(t((t(AA))A)))

公理系统QY之公理1

3. t((t(A(t(AA))))(t(AA)))

1、2，公理系统QY之推理规则t(E)

4. t(A(t(AA)))

公理系统QY之公理1

5. t(AA)

3、4，公理系统QY之推理规则t(E)

定理1即为公理系统H之公理1。在定理1的证明中，只用到了公理系统H的公理2、公理3以及推理规则t(E)。

在公理系统H中证明演绎定理时，只使用了公理系统H的公理1、公理2、公理3以及推理规则t(E)[2]。因为公理系统H的公理1可以由公理系统H的公理2、公理3以及推理规则t(E)被证明而作为系统QY的一个定理。因此，在系统QY中演绎定理显然是成立的。所以，在下面的证明中，如果需要，我们将直接使用演绎定理。

1.A

hyp

2. (tB)

hyp

3. t(AB)

hyp

4.B

1、3，公理系统QY之推理规则t(E)

5. t((t(AB))B)

3～4，公理系统QY之演绎定理

6. t((tB)(t((t(AB))(tB))))

公理系统QY之公理1

7. t((t(AB))(tB))

2、6，公理系统QY之推理规则t(E)

8. t((t((t(AB))B))(t((t((t(AB))(tB)))(AB))))

公理系统QY之公理3

9. t((t((t(AB))(tB)))(AB))

5、8，公理系统QY之推理规则t(E)

10. (AB)

7、9，公理系统QY之推理规则t(E)

11. t((tB)(AB))

2～10，公理系统QY之演绎定理

12. t(A(t((tB)(AB))))

1～11，公理系统QY之演绎定理

定理2即为公理系统H之公理4。

1. t((t((tA)(tA)))(t((t((tA)(t(tA))))A)))

公理系统QY之公理3

2. t((tA)(tA))

公理系统QY之定理1

3. t((t((tA)(t(tA))))A)

1、2，公理系统QY之推理规则t(E)

4. t((t((t((tA)(t(tA))))A))(t((t(tA))(t((t((tA)(t(tA))))A)))))

公理1

5. t((t(tA))(t((t((tA)(t(tA))))A)))

3、4，公理系统QY之推理规则t(E)

6. t((t((t(tA))(t((t((tA)(t(tA))))A))))(t((t((t(tA))(t((tA)(t(tA))))))(t((t(tA))A)))))

公理2

7. t((t((t(tA))(t((tA)(t(tA))))))(t((t(tA))A)))

5、6，公理系统QY之推理规则t(E)

8. t(((t(tA))(t((t()(t(tA)))))

公理系统QY之公理1

9. t((t(tA))A)

7、8，公理系统QY之推理规则t(E)

此定理即为双否消去律。

1. (AB)

hyp

2. (tA)

hyp

3.A

hyp

4. t((tA)(t((tB)(tA)))

公理系统QY之公理1

5. t((tB)(tA)

2、4，公理系统QY之推理规则t(E)

6. t((A)(t((tB)A))

公理系统QY之公理1

7. t((tB)A)

3、6，公理系统QY之推理规则t(E)

8. t((t((tB)A))(t((t((tB)(tA))B))

公理系统QY之公理3

9. t((t((tB)(tA))B)

7、8，公理系统QY之推理规则t(E)

10.B

5、9，公理系统QY之推理规则t(E)

11. t(AB)

3～10，公理系统QY之演绎定理

12. t((tA)(t(AB)))

2～11，公理系统QY之演绎定理

13. t((AB)(t((tA)(AB))))

公理系统QY之公理1

14. t((tA)(AB))

1、13，公理系统QY之推理规则t(E)

15. t((t((tA)(AB)))(t((t((tA)(t(AB))))A)))

公理系统QY之公理3

16. t((t((tA)(t(AB))))A)

14、15，公理系统QY之推理规则t(E)

17.A

12、16，公理系统QY之推理规则t(E)

18. t((AB)A)

1～17，公理系统QY之演绎定理

1. (AB)

hyp

2. t((AB)(t((t(tB))(AB))))

公理系统QY之公理1

3. t((t(tB))(AB))

1、2，公理系统QY之推理规则t(E)

4. t(tB)

hyp

5.A

hyp

6. t((t(tB))B)

公理系统QY之定理3

7.B

4、6，公理系统QY之推理规则t(E)

8. t(AB)

5～7，公理系统QY之演绎定理

9. t((t(tB))(t(AB)))

4～8，公理系统QY之演绎定理

10. t((t((t(tB))(AB)))(t((t((t(tB))(t(AB))))(tB))))

公理系统QY之公理3

11. t((t((t(tB))(t(AB))))(tB))

3、10，公理系统QY之推理规则t(E)

12. (tB)

9、11，公理系统QY之推理规则t(E)

13. t((AB)(tB))

1～12，公理系统QY之演绎定理

定理4、定理5即为公理系统H之公理5。

对公理系统H的公理简化之后得到的公理系统QY和通常的命题逻辑希尔伯特系统只存在一个差异。即推理规则的差异，一个是分离规则，一个是t(E)，而根据QY中“A→B”的定义，这两者显然是定价的。

这样简化后的公理系统QY就是一个和通常的命题逻辑希尔伯特型系统相等价的系统[5]16-29。因此，该系统具有可靠性和完全性。

四、纯粹括号表示法

在文献[3]和[4]中，张清宇先生构建了不用联结词和量词的一阶逻辑公理系统QH。在通过定义引入联结词“﹁ ”“⊃”和全称量词“∀”之后，在QH中实际上包含了语形联结词“﹁ ”“⊃”和全称量词“∀”，并且其中除了括号“( )”之外，还包括方括号“[ ]”。我们可以将该系统使用括号表示法并使之纯粹化，可以在公理系统QY(原有 3条公理)的基础上增加如下公理(模式)和推理规则从而得到一阶逻辑公理系统QQY：

4. T((T(Tx(T(AB(x)))))(T(A(T(TxB(x))))))，x不在A中出现

5. T((T(TxA(x)))A(m))，A(m)是由将A(x)中的x全部替换为m而得(m是个体常元)

可以证明，一阶逻辑公理系统QQY和通常的一阶谓词逻辑系统等价[5]70-98，可参阅文献[5]。因此，该系统同样具有可靠性和完全性。

值得注意的是，在一阶逻辑公理系统QQY中，括号既有结构性功能，如“A(u)”中的括号；也有联结词功能，如“(AB)”中的括号；还有量词功能，如“(AxB)”中的括号。