内容提要:使用经典逻辑对海量知识系统进行分析处理和信息挖掘需要解决的关键问题之一就是司各脱法则问题。基于对蕴涵的一般认识,可以对司各脱法则问题提出一种不同于已有逻辑系统的解决策略。在根据这种策略而建立的知识蕴涵逻辑系统D中,[1]蕴涵关系符合直觉,[2]经典逻辑中基本的逻辑规律在该系统中得以保留;[3]不改变经典否定、合取的性质;[4]司各脱法则不成立。在给出严格形式语义的基础上,证明了该系统具有可靠性、协调性、完全性和可判定性。
关键词:司各脱法则 知识蕴涵 系统D 可靠性 协调性 完全性 可判定性
中图分类号:B81 文献标识码:A
一、直观背景
在运用经典逻辑对一个海量知识系统进行分析处理和信息挖掘的过程中,遇到的一个比较棘手的问题是:如果一个知识系统包含着相互矛盾的信息,那么任何命题都将成为这个系统的推论。这样,该理论将变得毫无价值。这是因为,在经典逻辑中有一条重要的定理: ,这就是著名的司各脱法则(Scott Law),该定理表明,矛盾蕴涵一切。
对于司各脱法则问题的解决,从理论上讲,不外乎有如下八种方案:
方案1 |
方案2 |
方案3 |
方案4 |
方案5 |
方案6 |
方案7 |
方案8 |
不改变 |
改变¬ |
改变∧ |
改变→ |
改变¬∧ |
改变¬→ |
改变∧→ |
改变¬∧→ |
这八种方案可以归结为三个基本的研究方向:弃合方向(non-adjunctive approach)、正加方向(“positive logic plus” approach)和相干方向(relevant approach.)。弃合方向的根本特征就是放弃合取规则(从 和 推出 )。沿着这一方向建立的非经典逻辑系统主要有雅可夫斯基(Ja’skowski)的谈论逻辑[1]。正加方向的做法是在正命题逻辑中附加适当的否定。巴西逻辑学家科斯塔(Da Costa)和他的合作者就是在这一方向上进行工作的[2]。相干方向是由卢特雷(R.Routley)和梅尔(R.K.Meyer)等相干逻辑学家开创的。普里斯特(G. Priest) 等逻辑学家在弗协调逻辑研究方面也做了大量的工作。上述逻辑学家的工作可参见《哲学逻辑手册》[3]。
这些工作基本上可以属于上述方案2、方案4、方案5、方案6和方案8。他们所建立的逻辑系统大部分都改变了经典否定的含义。例如,在弗协调逻辑系统中, 和 之间不再是经典的相互矛盾的关系,而是可以同真的下反对关系[4]、[5]。经过这样的处理,在弗协调逻辑中 不再有效,从而解决了司各脱法则问题。
对于这种解决方案,有两点值得关注:
[1] 不再有效,改变了人们对于矛盾的经典理解;
[2] 由于 和 之间不再是经典的相互矛盾的关系,也改变了人们对于司各脱法则的经典理解。
我们认为既然要限制矛盾的作用范围,既然要克服矛盾推出一切的问题,我们就不能改变人们对于矛盾的经典理解,而应该在矛盾的推出关系上寻求突破。
人们之所以认为“矛盾推出一切或假命题蕴涵任何命题”有问题,主要原因应该是经典的实质蕴涵关系和人们对于蕴涵的经验直觉存在一定的差距。
我们来看一下经典实质蕴涵关系的真值表:
1 1 1
1 0 0
0 1 1
0 0 1
对于第二行,如果前件真后件假,那么蕴涵式是假的,这在直觉上是没有问题的;第一行是真命题与真命题之间的蕴涵也可以接受;既然如此,在承认假言易位的前提下,第四行也可以接受;但是第三行人们缺乏经验的直觉。对此,我们不妨在第三行暂时不加定义。
恰恰是第三行,在经典实质蕴涵的真值表中规定,当前件 假后件 真时,蕴涵式 是真的。即经典实质蕴涵认可假命题蕴涵真命题,可以说这直接导致了司各脱法则。
对于司各脱法则的一般形式 直觉是不能接受的;但是它的一些特殊形式却是符合直觉的,例如 。因为这也是合取分解规则的一个特殊形式,而合取分解的一般形式 是符合直觉的。因此,我们希望在建立的非经典逻辑系统中,司各脱法则的一般形式不成立,但其一些特殊形式成立。为之,我们可以对司各脱法则加以适当的限制(例如让前后件相关)来实现这一点。
根据如上对蕴涵真值表的分析,我们希望建立满足下列形式的知识蕴涵关系:
[1] ;
[2] ;
[3] ,其中 和 相关。
这分别对应于上述真值表中 为真的第一行、第四行和第三行。直观的含义是:
[1] 真知识和真知识之间存在蕴涵关系;
[2] 假知识和假知识之间存在蕴涵关系;
[3] 如果 和 相关,那么真知识 或者为 所蕴涵,或者为 所蕴涵[6]。
另外,依据直觉,人们说命题 和命题 之间如果存在蕴涵关系,一般会首先假设 应该是一个真命题。这类似于在亚里士多德的三段论中性质命题的主项有一个存在预设一样。而司各脱法则的前件 恰好是一个恒假命题,这也是司各脱法则难以接受的一个原因。
综上所述,我们希望建立一种更符合人们直觉的知识蕴涵关系:
[1] 它在真值表的第三行不同于经典逻辑的实质蕴涵;
[2] 如果确立一个蕴涵关系,那么它的前件假设是真的;
[3] 这种蕴涵关系可以避免司各脱法则。
基于上述理解,我们可以对经典命题逻辑系统中的若干公理和定理重新进行审视:
[1]
其直观含义是:真命题可以为任何命题所蕴涵。借助常见的逻辑定理变形可得 ,进一步变形可得 。这就是司各脱法则的一个变形。所以,看来这是不能接受的。
[2]
它和 等相结合可以得到 ,当前提 假时,蕴涵关系本身就值得怀疑,其传递性更无须多言。
相似可接受的是: 。其直观含义是:对于一个真命题 ,它可以对蕴涵关系自分配。
[3]
其直观含义是:如果 ,那么若前提得到进一步断定,则该蕴涵关系亦成立。这是可以接受的。
对于其他公理和定理我们可以作类似分析,此处不一一列出。
下面,我们打算着手建立反映上述思想的公理系统。我们希望建立的系统尽量能实现下述目标:
[1] 蕴涵关系符合上述直觉;
[2] 遵守最基本的逻辑规律;
[3] 不改变经典否定、合取的性质;
[4] 司各脱法则不成立。
二、知识蕴涵逻辑的形式语言
知识蕴涵逻辑的形式语言和经典命题逻辑的形式语言[7]基本相同。它以 、 和 作为初始联结词。其他联结词通过定义给出:
[
由知识蕴涵逻辑所有公式构成的集合记为 。
定义2.1 设 , 定义如下:
[1] 如果 是原子公式,那么 ;
[2] 如果 ,那么 ;
[3] 如果 ,那么 ;
[4] 如果 ,那么 。
定义2.2 假设 、 是公式,称 、 相关,当且仅当 。
三、知识蕴涵逻辑公理系统D
定义3.1 系统D的公理是具有下列形式的公式:
,其中 和 相关。
系统D的推理规则只有一条,即分离规则(modus ponens):由 和 可以推出 。简记为 。
由系统D的构成,可以看出其中的公理是符合上述直观的,这样我们实现了目标之[1]。
定义3.2 公式 由公式集 形式可推演,当且仅当存在公式序列
, ,…, ,
使得 ,并且每一个 满足下列条件之一:
[1] 是公理;
[2] ;
[3] 有 , < ,使得 。
如果公式 由公式集 形式可推演,则称 可推演出 ,符号记为 ├D ,也简记为: ├ 。
定义3.3 如果公式 由 形式可推演,则称公式 是可证明的。由 到 形式可推演的一个公式序列称为公式 的一个证明。如果公式 是可证明的,则称公式 为系统D的定理,符号记为├D ,也简记为:├ 。为了与其它的定理相区别,在下文中,我们将系统D内的定理记为 。
定理3.4(D演绎定理) 如果 ├ ,那么 ├ 。
证明:
我们对由 到 的推演的公式序列 ,…, 的长度 进行归纳证明。
归纳基始: 。如果这个推演序列中只有一个公式。那么该公式必定就是 本身,因此 或者是命题逻辑的一条公理,或者是 中的一个成员。
情形1: 是命题逻辑的一条公理。那么下列是由 到 的一个推演:
1 系统D的公理
2
3 1、2
情形2: 是 。那么下列是由 到 的一个推演:
1
2
3 1、2
情形3: 。下列公式序列即为由 到 的一个推演:
1
2
3 1、2
归纳步骤:我们假设由 到 的推演的公式序列中公式的数目小于 > 时演绎定理成立,现在须证明当由 到 的推演的公式序列中公式的数目等于 > 时演绎定理成立。这时不外有如下四种情形:
情形1: 是系统D的一条公理。完全和上述情形1相同。
情形2: 是 。完全和上述情形2相同。
情形3: 。完全和上述情形3相同。
情形4: 由推演序列中较前的两个公式通过分离规则 而得到,这两个公式必定是形如 和 的公式。而由 , 到 和 的推演长度必小于 ,根据归纳假设,我们有由 到 的推演和由 到 的推演。这样我们可以构造出由 到 的一个推演:
1
… 由 到 的推演
… 由 到 的推演 <
、
、
综上所述,根据数学归纳原理,演绎定理成立。
演绎定理(The Deduction Theorem)我们简记为 。
在系统D中可以证明下列定理:
├
证明:
1
2
3 1、2
4
5
6 4、5
7
8 3、7
9 6、8
类似可证:
├
由 、 和 可以看出,经典命题逻辑系统的三大规律,即同一律、不矛盾律和排中律在系统D中都成立,这样我们实现了目标之[2]。
├
证明:
1
2
3 1、2
此定理即为 [ [ 。
├
证明:
1 假设
2 假设
3 假设
4 2、3
5 3、4
6 1、3
7 3、6
8 5、7
9 5、8
10 1~9
11 1~10
12
1~11
此定理即为 [ [ [ [ [ [ 。
├
证明:
1 假设
2 假设
3
4 1、3
5 2、4
6
7 5、6
8 1~7
9
1~8
此定理即为 [ [ [ [ 。
├ [
├ [
├ [ [
由 、 、 、 、 、 以及分离规则就构成了一个以 、 和[为初始联结词的经典命题逻辑公理系统,[具有经典实质蕴涵的所有性质。联系 和 可以看出:在系统D中,联结词 、 没有改变其在经典逻辑中的性质。这样我们实现了目标之[3]。
定义3.5 一个真值联结词集合 是完全的,当且仅当任何 ( ≥1)元真值联结词都能由 中的联结词定义[8]。
在经典二值逻辑中, ,[ 是完全的,根据[的定义和上述定理易知:
定理3.6 真值联结词集合 是完全的。
四、知识蕴涵逻辑的形式语义
定义4.1 知识蕴涵逻辑的一个赋值 是以所有公式的集 为定义域、以 为值域的一个函数,并满足下列条件:
[1] ,当且仅当, ;
[2] ,当且仅当, ;
[3] 如果 ,那么 ;
[4] 如果 , ,那么 ;
[5] 如果 , ,并且 、 相关,那么 。
定理4.2 [ 当且仅当 或者 。
定义4.3 称一知识蕴涵逻辑赋值 为公式集 的模型,当且仅当,对 中任一公式 有 ;若公式集 存在一模型,则称 是可满足的;称 为 的语义后承,记作 ╞ ,当且仅当, 的任一模型都使得 ; ╞ 简记为╞ ,此时对任一个赋值 都有 ,因而也称 为有效的。
五、形式系统D的可靠性和协调性
定理5.1 设 、 为任意的知识蕴涵逻辑公式,则
[1] ╞
[2] ╞
[3] ╞
[4] ╞ ,其中 和 相关。
[5] ╞
[6] ╞
[7] ╞
[8] ╞
[9] ╞
[10] ╞
[11] ╞
定理5.2 如果╞ ,并且╞ ,那么╞ 。
由定理5.1和定理5.2施归纳于系统D中定理证明的长度不难证明:
定理5.3(系统D的可靠性定理) 设 为任意公式集, 为任意公式,则
[1] 如果 ├ ,那么 ╞ ;
[2] 如果├ ,那么╞ 。
定义5.4 一个形式系统S是协调的,如果不是任一公式都是在S中可证明的。
定理5.5(系统D的协调性定理) 形式系统D是协调的。
证明:根据知识蕴涵逻辑的形式语义定义容易知道,对于任一公式 ,╞ 和╞ 不可能都成立。这样,根据系统D的可靠性定理得知, 和 不可能都是系统D的定理。所以,系统D是协调的。
定理5.6 下列公式都不是系统D的定理。
由定理5.6知,司各脱法则不是系统D的定理。这样我们实现了目标之[4]。
六、系统D的完全性
定义6.1 设 ,称 是协调的,当且仅当不存在 , ├ 并且 ├ 。
定理6.2 设 , ,则
[1] 如果 不协调,则 ├
[2] 如果 不协调,则 ├ 。
证明:
[1] 设 不协调,则存在 , ├ 并且 ├ ,因而有:
1 ├
2 ├ 1 D演绎定理
3 ├
4 ├ 3 D演绎定理
5 ├
6 ├ 2、5
7 ├ 4、6
[2] 设 不协调,根据[1]有: ├ ,根据 有 ├ ,根据 进而有: ├ 。
定义6.3 设 ,称 是极大协调的,当且仅当,
[1] 是协调的;
[2] 对于任何 ,如果 ,则 不协调。
定理6.4 设 是极大协调集,对于任何 ,当 ├ 且仅当 。
证明:
[1] 显然,如果 ,则 ├ 。
[2] 假设 ├ ,但是 ,则 不协调,根据定理6.2[1]有: ├ 。
这样,就有 ├ ,并且 ├ ,这与 是极大协调集相矛盾。因而假设不成立。
所以有:如果 ├ ,则 。
定理6.5 设 是极大协调集, 、 ,
[1] 当且仅当 ;
[2] 当且仅当 并且 ;
[3] 如果 并且 ,那么 ;
[4] 如果 并且 ,那么 ;
[5] 如果 , ,并且 和 相关,那么 ;
[6] 如果 并且 ,那么 。
证明:[1]、[2]略。
[3] 如果 并且 ,那么有: ├ 并且 ├ ,根据 有 ├ ,两次运用 可得: ├ ,根据定理6.4可得: 。
[4] 假设 并且 ,但是 。由 , 可得: ├ 并且 ├ ,运用 可得: ├ ,根据定理6.4可得: 。这与 矛盾。因而假设不成立。所以有:如果 并且 ,那么 。
[5] 假设 , ,并且 和 相关。由 ,根据[1]可知: 。由 , 可得: ├ 并且 ├ ,因为 和 相关,根据 可得: ├ ,两次运用 可得: ├ ,根据定理6.4可得: 。
[6] 如果 并且 ,根据[1]可知: 并且 ,那么有: ├ 并且 ├ ,根据 有 ├ ,两次运用 可得: ├ ,根据定理6.4可得: 。
定理6.6 设 是极大协调集,对于任何 ,令 当且仅当 。则 是一个知识蕴涵逻辑赋值。即 是极大协调集 的模型。
根据Lindenbaum定理[8]可得:
定理6.7 任何协调的公式集都能够扩充为极大协调集。
由定理6.6和定理6.7直接可得:
定理6.8 任何协调的公式集都有模型。
定理6.9(D的完全性定理) 设 , ,则
[1] 如果 ╞ ,那么 ├ ;
[2] 如果╞ ,那么├ 。
证明:
[1] 假设 ├ 不成立,根据定理6.2[1]有: 协调。根据定理6.8可知 有模型。所以 ╞ 不成立。
[2] 当[1]中 时,直接可得。
七、系统D的可判定性
定义7.1 称为公式 的子公式集。
[1] 如果 是原子公式,则 ;
[2] 如果 ,则 。
[3] 如果 ,则 。
其中 指的是 或 。
如果 ,则称 为 的子公式。
定义7.2 公式 的复杂度指的是 中所含联结词的数目。
对于任一个系统D中的公式 ,我们按照下列程序来建立它的类真值表:
第一步 列出 中出现的所有命题符,并列出这些命题符的各种真值组合。例如,假如公式 中只有两个命题符 和 ,那么它们的真值组合情形如下:
1 1
1 0
0 1
0 0
第二步 为 中所有子命题各辟出一列,并按照它们的复杂度从左到右排列。例如对于公式 作如下处理:
1 1
1 0
0 1
0 0
第三步 按照下列规则逐列计算出 中各个子公式的值:
1. 对于子命题 和 其计算方法和经典命题逻辑中的计算方法相同;
2. 对于子命题 ,当 和 相关时,其计算方法和经典命题逻辑中的计算方法相同;当 和 不相关时,其计算方法在其他各行和经典命题逻辑中的计算方法相同,但是在 为0、 为1的行其计算方法和经典命题逻辑中的计算方法不同:将该行裂分为两行,第一行的值为1,第二行的值为0。
考虑到第三步中的情况,对于第二步中有些不产生分裂行的 的子公式可以省略。
例如对于公式 就必须作如下处理:
1 1 0 0 1 1 1
1 0 0 1 0 0 1
0 1 1 0 1 1 1
0 0
0 1 1
0 1
0 0 1 1 1 1 1
定理7.3 知识蕴涵逻辑系统D是可判定的。
证明:
[1] 设 是任一知识蕴涵逻辑公式, 是任一知识蕴涵逻辑赋值。令
∣
那么有:对于任一公式 , ,特别地, 。
给定公式 的一个类真值表 ,对于 中的第 行,有一个映射 :
使得当 时, 等于 在第 行的值。
显然,对于任一赋值 ,总存在一个 , 。
[2] 对于任一 ,我们可以按照下面的方式将它扩张成一个从 到 的映射 :
对于任一知识蕴涵逻辑公式 、 、 ,
当 时, ;
当 时,
① 如果 是原子公式,那么 ;
② 如果 ,那么 当且仅当 ;
③ 如果 ,那么 当且仅当 ;
④ 如果 ,那么 当且仅当( 且 )或者( , ,并且 不 相关)。
容易验证,映射 具有下述性质:
当且仅当 ;
当且仅当 ;
如果 ,那么 ;
并且 ,那么 ;
, ,并且 、 相关,那么 。
显然, 是一个知识蕴涵逻辑赋值,并且 │ = 。
[3] 当类真值表 中最后一列只含有1时,根据[1]可知,任一赋值 到 上的限制 都等于某个 ,从而有: 。因此, 在任一赋值下的值都是1,即 是有效式,根据知识蕴涵逻辑系统D的完全性定理可知 是知识蕴涵逻辑系统D的定理。
当 为知识蕴涵逻辑系统D的定理时,根据知识蕴涵逻辑系统D的可靠性定理可知, 在任一知识蕴涵逻辑赋值下的值都是1,当然对各个 也有 ,从而有 。所以在 中最后一列只含有1。
所以,一知识蕴涵逻辑公式 是知识蕴涵逻辑系统D的定理,当且仅当, 的类真值表 中最后一列只含有1。
即类真值表提供了一个判定任一知识蕴涵逻辑公式是否是知识蕴涵逻辑系统D的定理的判定程序。
定理7.4 使用类真值表方法可以判定定理5.6中的公式都不是系统D的定理。
证明:我们选证其中的两个。
1 1 0 0 1
0
1 0 0 0 1
0 1 1 0 1
0
0 0 1 0 1
1 1 1 1 1 1 1
1 1 0 1 0 0 1
1 0 1 0 1 1 1
0 1 1
1 0 0 0 1 0 1
0 1 1 1 1 1 1
0 0
0 1 1 1
&nbs,p; 0 1
0 1 0 1 0 1 1
0 0 1 1
0 0 1 1 1 1 1
0 0
0 1 1
0 1
0 0 0 1 1 1 1
定理7.5 使用类真值表方法可以判定下列公式都是系统D的定理。
八、系统D与经典命题逻辑的关系
首先,对于系统D中的蕴涵关系 以及经典逻辑中的实质蕴涵关系 [ 有下述定理:
├ [ [
证明:
1
2
3 1、2
4 [ [ 4 [的定义
由 可以看出,在经典逻辑蕴涵关系的意义上,如果 成立,则 [ 成立;反之如果 [ 成立,那么 未必成立。可见对于 和 之间是否存在蕴涵关系,经典蕴涵比系统D中的蕴涵断定的多。即对于 和 ,经典蕴涵认为有蕴涵关系 [ ,但是在系统D中未必认为有蕴涵关系( )。这符合我们前述的分析。
定义8.1 系统D 中的公式 的C变形 规定如下:
[1] 若 是原子公式,则 ;
[2] 若 ,则 ;
[3] 若 ,则 ;
[4] 若 ,则 [ 。
对于系统D和经典命题逻辑PC之间的关系,有如下两条定理:
定理8.2 若├D ,则├PC 。
定理8.3 若公式 中只包含联结词 、 、 和 ,则├D 当且仅当├PC 。
由定理7.4可知, 不是系统D的定理,但是 ,即 是经典命题逻辑PC的定理。所以,结合定理7.4可知,系统D弱于经典命题逻辑系统,但也仅仅是在蕴涵关系上弱于经典命题逻辑系统。而这也正是我们所希望的。
定理8.4 设 、 、 , 、 、 两两相关,则下列公式是系统D的定理:
[1]
[2]
[3]
而这三个公式正是一般经典命题逻辑系统的三条公理[7]。这说明当推演中涉及的公式相关的时候,知识蕴涵逻辑系统可以简化为经典命题逻辑系统。
九、结论
知识蕴涵逻辑公理系统D具有可靠性、完全性和可判定性。知识蕴涵逻辑系统D可以提供一个分析、处理海量知识系统的逻辑工具。利用公理 ,可以将知识系统中真知识归为一类,利用公理 ,可以将知识系统中的假知识归为一类,利用公理 (其中 和 相关)可以将相互矛盾知识中的相关真知识演绎出来。
【参考文献】
[1] da Costa, N.C.A. and Dubikajtis, L., “On Ja’skowski’s discussive logic”, in Arruda, A.Y., da Costa, N.C.A. and Computability, R. (eds.), Non-classical Logic, Model Theory and Computability, North-Holland, 1977, pp.37-56.
[2] Newton C.A. da Costa, Décio Krause and Otávio Bueno, Paraconsistent Logic and Paraconsistency: Technical and Philosophical Dezvelopments[M], September 26, 2004.
[3] Priest, G. “Paraconsistent Logic,” in Handbook of Philosophical Logic, Vol.6, 2002. D. M. Gabbay and F. Guenthner. pp.287-393.
[4] 杜国平. 经典逻辑视野中的弗协调逻辑[J]. 逻辑与认知. 2005, (3): 29-33.
[5] 杜国平. 哲思逻辑[J]. 东南大学学报. 2007, (4):43-46.
[6] 在哲学上,该形式也可以理解为:矛盾中蕴涵着相关的真理成分(而不是相关或不相关的任何成分)。
[7] 杜国平. 经典逻辑与非经典逻辑基础[M]. 北京:高等教育出版社, 2006. pp.9-63.
[8] A.G. Hamilton. Logic for Mathematicians[M]. London: Cambridge University Press, 1988. pp.19-42.
(原载《逻辑学研究》2008年第2期)