子集空间中的邻域扩张_语义学论文

子集空间下的邻域扩张，本文主要内容关键词为：邻域论文,子集论文,空间论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。

中图分类号：B81 文献标识码：A 文章编号：1674-3202(2014)-02-0020-19

1 引言

子集空间逻辑(Subset Space Logic)的研究始于摩斯(L.S.Moss)和帕里克(R.Parikh)。([19])其初始研究动机是找到一个相对比较简单的架构用以刻画认知努力，该架构最终采用了拓扑逻辑的风格。然而，与模态逻辑的经典拓扑语义学([16，17])不同的是，子集空间逻辑所使用的“拓扑语义学”并非将一个点(通常亦称为状态或世界)作为一个完全信息状态(即任意公式在该状态下的真假是确定的)，而是使用由一个点和包含该点在内的一个认知域所组成的有序对来实现。认知域并非一成不变：当主体通过认知努力(或者是获得新的证据)从而引起知识更新时，认知域就会变窄(说明了主体掌握更多的确定信息)。“知道φ”被解释为φ在当前认知域中所有的点上为真，因此认知努力可以引发知识状况的变化。子集空间逻辑的语义学简称为子集语义学。子集语义学所使用的语义模型称为子集模型，它是与拓扑模型非常相似但外延更广的概念。

对子集空间逻辑的后续研究的一个方面是在子集模型上添加额外的条件，尤其是考虑如拓扑模型这样一类特殊子集模型的情形；关于这个方面的相关成果可以参见[6，8，9]。[10－13，22]则关注子集空间逻辑的混合语言扩充，在语言中设置子集模型中的点乃至认知域的专名。子集空间逻辑的多主体扩充多年来一直受到关注，[4，13，14，27]等都曾尝试为此给出解决方案，但真正如经典单主体认知逻辑到多主体认知逻辑的自然扩充(参见[7，18])见于[25]。除此以外，最近出现的文章[2，26]已经开始探讨子集空间逻辑的动态扩充。

这里采用改编自[20]的一个例子以展示子集空间逻辑的直观思想。一位交警手持雷达测速设备以监测高速公路上的超速行为。测速雷达的精确度为±3千米/时，且高速公路限速120千米/时。假设现在有一辆汽车驶过，而交警手上的测速雷达显示车速为122千米/时。那么汽车是否确实超速了？对于这点，该交警并不确知。假如测速雷达的精确度为±1千米/时，并且读数仍为122千米/时的话，那么交警就知道汽车超速了。在子集空间逻辑中，如果以p表示“汽车超速”，则公式

刚好刻画了上述情形。该公式的第一个合取支是说交警不知道汽车超速，而第二个合取支则表示交警在证据支持度提升时有可能知道汽车超速。子集空间逻辑的语言是在命题逻辑的语言基础上扩充以两个一元模态算子：K和

。

上例中证据支持度的提升是知识增进的途径。有些时候证据支持度会下降，从而引发知识的退化。比如上例中如果交警的手持雷达损坏，原有证据可能不复存在。研究证据支持度下降时的认知状况，尤其是极端情形(最坏情形)下的认知状况，具有现实的意义。本文引入一个模态算子

。公式

将用于表示“

在证据支持度下降的任意情况下都成立”。在前面的例子中，公式

Kp显然成立。

虽然用子集空间逻辑这一框架来刻画知识增进相当顺理成章，其形式语义也很容易给出，但跟经典子集空间逻辑一样，证明新逻辑的公理系统的完全性并非易事。本文采用[23－25]中提出的方法，首先为新逻辑引入一个二维关系语义学，然后使用逐步构造法证明在关系语义学下的完全性，最后将完全性结论转移到子集语义学。这是文章的主要成果。

本文的结构安排如下：下一节介绍经典的子集空间逻辑；第3节讨论邻域的扩张，主要探讨将经典子集空间逻辑中的邻域收缩算子替换为邻域扩张算子而得到的逻辑，以及该逻辑的可靠且完全的公理系统；文章最后一节讨论一些相关的开放性问题和后续研究计划。

2 背景：子集空间逻辑

这里首先简单介绍子集空间逻辑([19])的一些基本概念、思想和结论。全文中约定以PROP表示一个可数的命题变元集。

上面的直观解读有助于加深对算子K和

的理解，但这些算子的准确含义则由接下来给出的形式语义来定义。下面首先定义子集模型和认知情境，然后再给出满足的定义。这套语义解释称为子集语义学。

*这里忽略空集的存在。根据[23]命题6.1.3，在子集空间中禁止使用空集并不会对语义解释造成影响。

3 邻域的扩张

第2节中介绍的经典子集空间逻辑带有邻域收缩算子，但却没有邻域扩张算子。本节讨论将邻域收缩算子替换为邻域扩张算子时得到的逻辑。下面首先引入新逻辑的语言和语义，之后给出该逻辑的公理系统，为其引入关系语义学，并使用逐步构造法证明其完全性。

3.1 语言、语义和公理系统

其余情形与定义3类似。

的完全性则是说，逻辑

的有效式都是

的定理。它的一个等价条件是，

所有的理论(即极大一致的公式集)皆可被满足。考虑到

和经典子集空间逻辑的相似性，不难相信

的完全性证明可以使用子集空间逻辑完全性定理的证明思路。

然而，子集空间逻辑完全性定理的证明并不简单。常用的典范模型方法失效。该方法首先定义典范模型，使用理论作为模型的个体域，巧妙地定义模型中的关系和赋值函数，以使得该模型可以满足公理系统的任何理论，最后经过简单变形即得到完全性定理。但是对于子集空间逻辑，定义典范子集模型首先就成了问题，因为其中“邻域类”的定义存在困难。

为了能给任意理论造出模型，[6，19]提出一种抽象构造方法：构造具备某些条件的抽象模型(其个体域是一些抽象的状态，而非理论)，使其既满足给定理论，又可以映射为满足该理论的一个等价的子集模型。这样一来，子集语义学下的完全性就转化为抽象模型语义学下的完全性。构造这样的抽象模型并不容易，需要首先构造初步的模型，逐步修改，最终才能满足所需的条件。该方法的证明思路类似于模态逻辑完全性证明的逐步构造法(参见[5]，第4.6节)。主要差别在于，逐步构造法一般直接使用理论作为所构造模型的个体域中的状态，从而使一些定义、条件和证明得以简化。

[23－25]中则引入子集语义学的对应理论，找到与子集模型类一一对应的关系模型类(称为：

)，然后使用经典的逐步构造法为给定理论构造一个

模型，从而得到完全性定理。如果仅仅是为了得到完全性定理，则只需找到一个更容易定义的

模型(参见[23，第6.2节])。如果仅仅从完全性证明的角度来看，[23－25]中的证明方法采用了标准的逐步构造法，较之于[6，19]中的证明更为简单，条理更清晰，且更适于应用到其它的逻辑。下文中将采用[23－25]中的方法来定义适当的

模型。

3.2

的关系语义学

子集空间逻辑

的语义学可以视为一种二维的关系语义学。本节将对这一观点加以解释。

值得注意的是，上述定义中的状态σ和τ都是二维平面上的点，因此当需要明确写出时会以一个有序对来表示。下文中出现的所有σ和τ都是这样使用的。

3.3 完全性定理

本节给出

完全性定理的证明。考虑到文章的篇幅和可读性，一些简单证明将被略去。这里预设读者熟悉公理系统的证明或推演、一致、极大一致等概念，并最好了解模态逻辑完全性证明的典范模型方法。极大一致的公式集被称为理论。所有理论的集合记为MCS。

完全性定理的证明思路如图4所示。

3.3.1 典范关系及其性质

与经典模态逻辑完全性证明的存在引理类似(第(2)项稍微复杂一些)。证明从略。

在上面这种二维的设定下构造典范模型难以使用类似于典范模型方法那样的构造，因为我们需要将理论摆成一个二维平面并满足成为

模型的三个条件。为了做到这一点，这里引入网络概念(这一概念在[15]中被称为矩阵)。

3.3.2 网络

由上述定义不难发现，无瑕网络就是没有缺陷的融贯网络。接下来的两条引理要证明：任何有缺陷的融贯网络总是可以修补为无瑕网络。

引理5(修补引理) 令μ为一有穷融贯网络，且D是它的缺陷。总是存在有穷融贯网络

使得D不是μ′的缺陷。

证明：首先注意，这里构造的网络满足：

·任意一列(具有相同第二维度的点的序列)通过关系

形成一个树结构；这一条保证融贯网络的条件(C3)。

这样的要求非但不会增加构造的难度，反而使构造过程变得清晰而简单。

直观上来看，引理5和6中对缺陷的修补与一阶逻辑完全性证明中补足证据具有一定的相似性。不过这里的修补因为需要考虑一些框架上的性质而更为细致。下面的定理很容易由引理4、6和推论l得到。

4 讨论

当我们使用关系语义学的视角来处理子集空间逻辑时，很多问题豁然开朗。比如，原本复杂繁琐的完全性证明变得清楚明晰、条理分明，而原本无从下手的多主体系统问题也得以迎刃而解。([25])因此，很自然的一个问题是，这样的结果究竟是源自基于子集语义学的模型论方法的缺失，还是源自子集空间逻辑的关系语义学本质？本文无法给出答案，但有一点是明确的：通过对子集语义学与关系语义学对应理论的研究，我们将原本相距甚远的两个分支(子集空间逻辑和二维模态逻辑)拉近到一起，从而使这种对比的意义得以彰显。

就子集空间逻辑完全性定理的证明而言，原子保持性质是一条模型性质，这导致完全性的很多经典证明方法不适用，因为那些方法多数都要求模型类上的所有性质都是框架性质(或者说统一代入规则是所讨论逻辑的一条保持有效性的规则)。对模型上的某些特殊性质(比如原子保持性质)的系统的、方法论角度的研究应当是很有价值的一项工作。在很多其它方法无法使用的时候，典范模型方法成为子集空间逻辑完全性证明的首选方法，只是同样无法用于子集空间逻辑。典范模型方法失效的主要原因在于未能找到合适的方法定义典范模型。但其实，逐步构造法在某种意义上就是一种构造典范模型的方法，只不过由此得到的“典范模型”仅仅是经典意义上典范模型的一个子模型而已。不管怎样，对完全性证明的研究是进行子集空间逻辑研究难以回避的任务，同时也是众多逻辑分支下的学者长期从事的工作。

与完全性问题类似，对子集空间逻辑的可计算性与计算复杂性问题的研究同样不是常规性的工作。完全性定理的证明中构造的网络是一个无穷的网络，而且由于