邻域语义学与推演系统的完全性，本文主要内容关键词为：邻域论文,语义学论文,完全性论文,系统论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
推演系统并不一定是逻辑系统，在讨论一个推演系统是不是逻辑系统时，完全性是一个重要的标准。然而，完全性是相对于语义解释的，如果允许任意的语义解释，则完全性标准可能是无用的。设想这样的情况，有一种语义解释，使得所有的推演系统对于它都是完全的。实际上，确实有这样的语义解释。
在本文中，我们构造一种适合于一切命题逻辑的语义学，在这种语义学中讨论推演系统的完全性。并利用这种完全性简单地讨论怎样的推演系统是逻辑系统。
一、从模态逻辑谈起
每个关系都可以转化为邻域映射，但并非所有的邻域映射都是由关系转化而来，所以模态逻辑的邻域语义学是比关系语义学更为广泛的一种语义学。
邻域语义学的意义在于它不仅能用于模态逻辑，而且能用于极大多数的命题逻辑。用以上类似的方法可以将广义模态逻辑、时态逻辑、相干逻辑、直觉主义逻辑（及其极小逻辑、初基演算等）、部分条件句逻辑（命题型的条件句逻辑）等逻辑系统的语义转化为邻域语义。
二、形式语言
我们抽象地考虑命题逻辑的形式语言，它适合一切命题逻辑。
2.1定义 形式语言
一个（命题）形式语言由初始符号和形成规则组成：
初始符号 （1）命题变项；（2）命题常项集C；（3）命题算子集F。
命题变项有可数个，用p，q等表示。C的元素用a，b等表示，C可以是空集。F的元素用f，g等表示，每个f∈F，有元数n≥1，f称为n 元算子，F中至少有元数≥2的算子。
形成规则 （1）命题变项和命题常项是公式；（2）如果f是n元命题算子，α[,1]，…，α[,n]是n个公式，则fα[,1]…α[,n]是公式；（3）只有以上的是公式。
不同的形式语言的区别在于命题常项集C和命题算子集F。所以可以将形式语言记为P＝〈C，F〉。P的全体公式记为Form（P）。
2.2定义 代入 α，β[,1]…，β[,n]是公式，p[,1]，…，p[,n]是命题变项。α（β[,1]／p[,1]，…，β[,n]／p[,n]）（在中将i代入p[,i]）归纳定义如下：
（2）α是命题常项，α（β[,1]／p[,1]，…，β[,n]／p[,n]）＝α；
（3）α＝fα[,1]…α[,m]，α（β[,1]／p[,1]，…，β[,n]／p[,n]）＝fα[,1]（β[,1]／p[,1]，…，β[,n]／p[,n]）…α[,m]（β[,1]／p[,1]，…，β[,n]／p[,n]）。
2.3定义 置换 α，β，γ是公式。 α〔γ／β〕（在α中将γ置换β）归纳定义如下：
（1）β不是α的子公式，则α〔γ／β〕＝α；
（2）β＝α，则〔γ／β〕＝γ
（3）α＝fα[,1]…α[,n]，β是α[,i]的子公式，则α〔γ／β〕＝fα[,1]…α[,i]〔γ／β〕…α[,n]。
三、框架和模型
（1）任给α∈C，都有V（α）＝C[,α]；
（2）任给f∈F，任给公式α[,1]，…，α[,n]，任给x∈W，都有
x∈V（f[,α1]…α[,n]）当且仅当〈V（α[,1]），…，V（α[,n]）〉∈N[,f]（x）。
M＝〈K，V〉称为P的模型。记‖M‖＝‖K‖。
3.5定理 组合原理
（1）如果V（α[,1]）＝V'（α[,n]），…，V（α[,n]）＝ V'（α[,n]），则V（fα[,1]…α[,n]）＝V'（fα[,1]…α[,n]）。
（2）如果V（α[,1]）＝V（β[,1]），…，V（α[,n]）＝V（β[,n]），则V（fα[,1]…α[,n]）＝V（fβ[,1]…β[,n]）。
由组合原理（1）可得：赋值V由V在命题变项上的值所确定。
由组合原理（2）可得：如果V（β）＝V（γ），则任给公式α， 都有V（α）＝V（α〔γ／β〕）。
3.6定义 满足和模型有效M＝〈K，V〉是模型，W＝‖M‖。
3.7定义 框架有效 K是框架，г是框架类。
四、完全性和典范模型
A称为公理集，A中的元素称为公理。R称为推演规则集，R中的元素称为推演规则。
4.2定义 证明 D是推演系统。D 的一个证明是一个有限的公式序列α[,1]，…，α[,n]，其中每个α[,i]满足以下条件之一：
（1）α[,i]∈A；
（2）存在公式集A，使得A｛α[,1]，…，α[,i-1]｝且〈A，α[,i]〉∈R。
4.3定义 内定理 D推演系统。如果存在D的证明α[,1]，…，α[,n]，使得α[,n]＝α，则称α是D的内定理，记为├α。D的全体内定理的集合记为T（D）。
4.4定义 完全性 D是推演系统。
（1）如果存在模型M，使得├α当且仅当M├α，则称D是模型完全的。
（2）如果存在框架类┏，使得├α当且仅当Г├α，则称D是框架完全的。
可以证明，如果D是框架完全的，则存在框架K，使得├α当且仅当K├α。
证明模型完全性最主要的工具是典范模型。
（4）任给a∈C，都有C[,a]＝│a│；
（5）任给f∈F，都有〈│α[,1]│，…，│α[,n]│〉∈N[,f]（u）当且仅当fα[,1]…α[,n]∈u；
（6）任给命题变项p，都有V（p）＝│p│。
4.6定理 典范模型的性质 如果M＝〈K，V〉是D的典范模型，W＝‖K‖，则
（1）任给公式α，都有V（α）＝│α│（也就是u∈V（α）当且仅当α∈u）。
（2）├α当且仅当│α│＝W。
4.7定理 如果D有典范模型M，则D是模型完全的。①
M＝〈K，V〉是D的典范模型，则称K是D的典范框架。和典范模型不一样，D的典范框架并不一定是T（D）的的框架。但如果D 有典范框架K是T（D）的框架，则D是框架完全的。
五、一般框架
5.1定义 合适 P是形式语言，K＝〈W，C[,a]，N[,f]，〉是P的框架，π
（W）称为K上一个合适的子集族，如果π满足以下条件：
（1）任给a∈C，都有C[,a]∈π；
（2）任给f∈F，都有如果S[,1]，…，S[,n]，则N[,f]*（〈S[,1]，…，S[,n]〉）∈π。
5.2定义 一般框架 P是形式语言，P 的一个一般框架是四元组GK＝〈W，C[,a]，N[,f]，π〉，其中K＝〈W，C[,a]，N[,f]〉是P的框架，π是K上一个合适的子集族。
5.3定义 赋值和模型GK＝〈W，C[,a]，N[,f]，π〉是一般框架，V是K上的赋值，如果V满足：任给命题变项p，都有V（p）∈π，则称V是GK上的一个赋值。称M＝〈GK，V〉为模型。
GK上的赋值也是K上的赋值，所以一般框架上的满足、 模型有效等概念和框架上的相应概念一样。一般框架有效和框架有效稍有差别。
5.4定义 一般框架有效GK是一般框架，α是公式。如果任给GK 上赋值V，都有〈GK，V〉
5.5定义 一般框架完全性 D是推演系统。如果存在一般框架GK，使得├α当且仅当GK
α，则称D是一般框架完全的。
5.6定理 GK是一般框架，V是GK上的赋值，则任给公式α， 都有V（α）∈π。
六、弱框架
6.1定义 弱框架 P是形式语言，P的一个弱框架是四元组WK＝〈W，W[,0]，C[,a]，N[,f]〉，其中：K＝〈W，C[,a]，N[,f]〉是P的框架，W[,0]是W的子集。
6.2定义 赋值和弱模型 WK＝〈W，W[,0]，C[,a]，N[,f]〉是弱框架，K上的赋值也称为WK上的赋值。WM＝〈WK，V〉称为弱模型。
弱框架上的模型在可能世界x 满足的概念和框架上的相应概念一样，其它概念和框架上的相应概念稍有差别。
6.3定义 弱模型有效 WM＝〈WK，V〉是弱模型，α是公式。如果任给x∈W[,0]，都有WM
6.4定义 弱框架有效 WK是弱框架，W是弱框架类，α是公式。
如果D是弱框架完全的，则存在弱框架WK，使得D是弱框完全的。
证明模型完全性用的是典范模型，证明弱模型完全性用的是弱典范模型。
6.6定义 弱典范模型 D是推演系统，WK＝〈W，W[,0]，C[,a]，N[,f]〉是弱框架，弱模型WM＝〈WK，V〉称为D的弱典范模型，如果WM满足以下条件：
（4）任给a∈C，都有C[,a]＝│a│；
（5）任给f∈F，都有〈│α[,1]│，…，│α[,n]│〉∈N[,f]（u）当且仅当fα[,1]…α[,n]∈u；
（6）任给命题变项p，都有V（p）＝│p│。
弱典范模型和典范模型的差别在于条件（2）和（3），（2 ）的要求减弱了，而（3）的要求加强了。
6.7定理 弱典范模型的性质 如果M＝〈K，V〉是D的典范模型，W＝‖K‖，则
（1）任给公式α，都有V（α）＝│α│（也就是u∈V（α）当且仅当α∈u）。
（2）├α当且仅当W[,0]
V（α）。
6.8定理 如果D有弱典范模型M，则D是弱模型完全的。
6.9定义 一般弱框架 P＝〈C，F〉是形式语言，P 的一个一般弱框架是五元组GWK＝〈W，W[,0]，C[,a]，N[,f]，π〉，其中K＝〈W，C[,a]，N[,f]〉是P的框架，W[,0]是W的子集，π是K上一个合适的子集族。
6.11定义 赋值和弱模型GWK＝〈W，W[,0]，C[,a]，N[,f]，π〉是一般弱框架，V是WK上的赋值，如果V满足：任给命题变项p，都有V（p）∈π，则称V是GWK上的一个赋值。
M＝〈GWK，V〉称为弱模型。
GWK上的赋值也是WK上的赋值，所以一般弱框架上的满足、 模型有效等概念和弱框架上的相应概念一样。一般弱框架有效和弱框架有效稍有差别。
6.12定义 一般弱框架有效 GWK是一般弱框架，α是公式。 如果任给GWK上赋值V，都有〈GWK，V〉
α，则称D是一般弱框架完全的。
七、完全性的性质和意义
框架完全性、一般框架完全性和模型完全性依次减弱。弱完全性要比相应的完全性弱。
弱模型完全性 → 一般弱框架完全性 → 弱框架完全性
↓ ↓ ↓
模型完全性 → 一般框架完全性→ 框架完全性
前四种完全性有一般的刻画。
7.1定义 置换封闭性 D是推演系统。如果D 满足：任给α，β，γ∈T（D），都有α〔γ／β〕∈T（D），则称D 有（内定理）置换封闭性。
7.2定义 代入封闭性 D是推演系统，如果从α∈T（D）能得到α（β[,1]／p[,1]，…，β[,n]／p[,n]）∈T（D），则称D有代入封闭性。
7.3定理 任何推演系统D都是是弱模型完全的。
7.4定理 推演系统D是模型完全的当且仅当D有置换封闭性。②
7.5定理 推演系统D是一般弱框架完全的当且仅当D有代入封闭性。
7.6定理 推演系统D是一般框架完全的当且仅当D 有置换封闭性和代入封闭性。
下面，我们从更一般的语义学角度来看以上六种完全性的意义。
任何一种语义都是由值域R（一个非空集合）、 赋值（全体公式集到值域的映射）和有效性的定义三部分组成。赋值和有效性定义中有一些基本的原则。
赋值的基本原则有：
（1）组合原则 赋值V由V在命题变项上的值所确定。这样， 所有的赋值都是全体命题变项到值域的映射的扩充。
（2）普遍性原则 命题变项可以取值域中的任何值。这样， 任何一个全体命题变项到值域的映射都可以扩充为一个赋值。
（3）值域是非空集合的幂集。这只是一个要求而不是一个原则。
有效性定义的基本原则有：
（1）值确定原则（弱） 有效性是由值所确定的。就是说， 如果两个公式在任何赋值下的值都相同，则它们的有效性是一样的。
（2）值确定原则（强） 存在R的子集I（特指集），使得：一个公式是有效的当且仅当它在任何赋值下的值都在I中。
（3）唯一性原则 特指集I只有一个元素。
组合原则和强的值确定原则是建立邻域语义学的基础，它对应的是弱模型完全性。普遍性原则区分了模型完全和一般框架完全。赋值的原则（3）区分了一般框架完全和框架完全。唯一性原则区分了强和弱。
(2)
弱模型完全性一般弱框架完全性弱框架完全性
(3)
模型完全性 一般框架完全性 框架完全性
(1)(2)(3)
反之，任何满足组合原则和强的值确定原则的语义学都可以转化成邻域语义学，所以邻域语义学是满足组合原则和强的值确定原则的最一般的语义学。
八、什么是逻辑系统？
要在邻域语义学内讨论什么是逻辑系统，首先要解决为何逻辑系统必须有组合原则和强的值确定原则。
组合原则是弗雷格创立现代逻辑的重要原则之一，也是现有的大多数逻辑语义学的基本原则。然而，现在也有不少被称为“逻辑”的推演系统的语义学不满足组合原则。也有学者对组合原则提出了批评，但他们的批评是对某些语言现象的某种语义分析来说的，所以他们的批评至多说明了这种特定的语义分析不满足组合原则，并不能说明逻辑系统可以不满足组合原则。
逻辑分析是一种语义分析，但语义分析不一定是逻辑分析。逻辑分析是一种彻底的语义分析。所谓彻底，就是说我们提出的语义概念能够完全说明系统在这种语义下的性质。
如用真值（真和假）去分析古典逻辑系统，就是一种彻底的语义分析，因为用真值可以完全说明系统在真值意义下的全部性质。而用真值去分析模态逻辑系统，就不是一种彻底的语义分析，因为仅用真值一般无法确定必然命题的真假。
既然一般命题逻辑系统中的公式是由命题变项和算子组成，所以公式的语义就应该由命题变项和算子的语义所确定，这就是组合原则。
弱的值确定原则是类似的。在彻底的语义分析中，有效性也应该由语义完全确定，所以两个语义完全相同的公式，它们的有效性当然是一样的。
以上讨论说明了，如果一种语义学不满足组合原则和弱的值确定原则，就不是一种彻底的分析，因而不能充当一种逻辑意义上的语义学。
我不能为强的值确定原则作辩护，幸运的是命题逻辑中还没有发现不符合强的值确定原则的语义学。
作为逻辑系统，仅有组合原则和弱的值确定原则还是不够的，普遍性原则也是必须的。这就是说仅有模型完全性是不够的，至少要有一般框架完全性。
从一般框架完全性到框架完全性还可以作更细的分类。首先来看框架完全性的意义。
按“内涵是可能世界到真值的函数”的看法，可以对赋值的条件（3）作出分析。经过简单的转化，内涵也可以看成可能世界的子集。赋值的条件（3）实际上包含两个关于内涵的原则。
原子性原则。任何内涵都是由一些互相独立的极小的内涵（单元集）组合而成。
完备性原则。内涵的任何组合还是内涵。
这里说的组合是指广义的布尔运算（广义交、广义并、差）。
从框架完全性的意义来看，具有框架完全性的系统是逻辑系统是没有问题的，而且还是一类较强的逻辑。至于从一般框架完全性到框架完全性，承认那一类是逻辑，仅在邻域语义学的范围内很难找到标准。