高级数理逻辑第8讲

1、模态逻辑汉语中“模态”是英语词Modal的音译。英语词modality(模态性)源出于拉丁文modalitas，含形态、样式和形式的意思。现代模态逻辑是现代逻辑的重要分支，它在科学和技术领域的应用越来越广泛，它的许多课题不仅受到逻辑学家的注意，而且也受到计算机科学家和计算机工程技术人员以及其他工程技术人员的关注。因此，深入研究和发展这门科学，已成为逻辑工作者的一项重要任务。逻辑学中在两种意义上，即在狭义和广义上使用“模态”这个术语。涉及必然性，或然性（偶然性），遗传性和相容性等模态属于狭义模态。从某种观点来看，它们表达的是命题的真假强度。因此，也称为真值模态。例如：“物体间存在着引力是必然的”

2、；“到本世纪末我国国民生产总值翻两翻是可能的”等都属于这类模态命题。我们这章的模态系统主要研究这类狭义模态性。广义模态性是指命题本身所具有的非真值函项的（或非外延的）种种性质。广义模态词较多，除了必然、可能之外，尚有必须（应该）、允许、禁止；知道、相信、可接受、可疑、可证；曾经、总是、将是、优先、中立等。这些模态词分别是道义逻辑，认识逻辑，时态逻辑，和价值逻辑研究的对象。还有希望、需要等尚未深入研究的模态词。其例子为：“宇宙间存在着黑洞是可信的”；“在商品生产的社会中价值规律起着重要作用是众所周知的”；“子女赡养扶助父母是应该的”；“世界上还存在着野人是可疑的”等。在这章，我们将讨论一些模态命

3、题逻辑的系统，但首先将给出现代模态系统所要表达的某些模态概念的一般叙述。6.1 模态逻辑介绍本章主要来介绍模态逻辑系统基本概念，然后，具体介绍命题模态逻辑和一阶谓词模态逻辑。Modal logic 6.1.1 模态逻辑引入逻辑系统的发展从命题逻辑发展到了一阶谓词逻辑，主要是因为命题逻辑系统的描述能力有限。模态逻辑的出现同样是为了扩充一阶谓词逻辑和命题逻辑的描述能力。1、命题逻辑的缺陷：命题逻辑的原子命题不能细化，层次太高，而不能完全描述世界；例：所有实数的平方是非负的；-是实数；-的平方是非负的；一阶谓词逻辑，利用谓词，函词和量词来解决这样的问题；2、命题逻辑和一阶谓词逻辑的缺陷：这两种逻辑都

4、不能描述有时间概念的变化。任何一个命题都有一个适用的场合的问题；例命题A：汽车是一个必备的生活工具；中国：假；美国：真古代假，现代真；新加坡：假；例如命题B：112命题B在任何时间和任何地点都是成立的，不像命题A只能在一定的时间和场合那成立。因此，可以看出命题是否成立是与其所在的时间和场合有不同的关系。为了表示这种时间与场合上的概念，我们引入了模态逻辑来描述这样的概念。A命题的真假与场合有关；A在不同场合的值不同；因此，对于命题A是否是真成立是不好确定。为了解决这样的问题，对于在某些场合成立的命题，规定为可能真的；除此之外，对于在所有场合为真的命题，我们规定为必然真的。w1,w2为了解决这样命

5、题的描述问题，在模态逻辑中，引入了对必然和可能的描述。可能：A，表示命题A，至少有一个可以实现的场合中，成立。必然：A，表示命题A，在所有能够实现的场合中，成立。3、模态逻辑的实质l 命题逻辑和一阶谓词逻辑的推广n 对命题逻辑和一阶谓词逻辑，引入了两个符号模态词；u 引入的模态词类似于量词n 在不同场合中，分别是一阶谓词逻辑和命题逻辑；l 场合之间的关系n 场合从目前所处的场合是否可以实现（达到）；n 模态词A：表示在当前场合到以后可以达到的场合中都是成立的；n 模态词A：表示从当前场合到以后可以达到的场合中，至少有一个是成立的。n 与场合之间关系有着密切的联系。l 场合与现实之间的关系n 程

6、序设计中的模块可以是不同的场合n 时间段也可以是不同的场合l 这些不同的场合在模态逻辑中，成为可能世界6.1.2 基本模态概念在真命题中，我们可以区分出那些仅仅偶尔(happen)是真的命题和那些必然(bound)是真的（或不可能是假的）命题。同样，在假命题中，我们也可以区分出那些偶尔是假的命题和那些必然(bound)是假的（或不可能是真的）命题。一个必然是真的命题我们称之为必真(necessary true)命题，或必然真理(necessary truth)，或简单的说是必然（necessary）命题；一个必然为假的命题我们称之为不可能(impossible )命题；而既非必然又非不可能的命

7、题则称为偶然(contingent)命题。当然某些偶然命题将是真的，某些偶然命题将是假的。如果一个命题不是不可能的，则称为可能(possible)命题。这里的“可能”并不意味着“仅仅可能（merely possible）”，如果说p是仅仅可能的，则意指尽管它可能已经是真的，但它实质上是假的。在我们的意义下，可能命题包含着所有的真命题（更不必说包含着所有的必然命题）。事实上，它们包含着除不可能命题以外的所有命题。在当前的上下文中，我们意指的“必然性（necessity）”通常称为逻辑必然性（logical necessity）。我们无意在此详细叙述逻辑必然性的实质总之，这个问题充满着许多哲学上的

8、困难。我们所用的术语“必然（necessary）”的含义通过当我们说某个命题是必然的时候大概就可以得到充分的说明。我们的意思并不是：因为事物是怎样的，或者世界是怎样的，所以这个命题不可能不真；而是，无论事物是怎样的，也无论世界的结果象什么，它都不可能不真。例如，尽管命题：没有物体比光速更快是由很重要的科学证据所支持的，但是我们还是倾向于说在某个重要的意义下，一个物体不可能比光速更快这个命题在我们的意义下仍然不被看作是一个必然命题；因为它的支持是由物质世界是怎样的事实组成，而物质世界推测起来它可能是而事实上它不是。而命题：所有的未婚男子都是独身的，没有任何余地，不管今天是不是“星期四”，在我们的

9、意义下它都被看作是必然真理。类似地，我们意指的“不可能性”称为“逻辑”不可能性；我们意指的“偶然性”称为“逻辑” 偶然性；我们意指的“可能性”称为“逻辑”可能性；对于这些说法的含义，我们从刚说过的必然性的情况应该是完全清楚了。这四个概念：必然性、不可能性、偶然性、可能性，称为“模态”概念。它们显然注：在中世纪，逻辑必然性等概念被认为是一个命题可能是真的或假的方式。是彼此密切相关的；事实上我们可以根据它们中的任一个概念来解释其余三个概念。特别重要的是下列必然性和可能性之间的联系：称一个命题，p，是必然真的，等价于称p是假的是不可能的；称p是可能的（或者可能是真的）等价于称p是假的不是必然为真的。

10、另一个重要的模态概念是“遗传（entailment）”。我们把它理解为“逻辑源于（following logically from）”关系的逆( converse)：即，称命题p遗传（entails）命题q，仅仅是q逻辑源于p的一种替换方法，或者说从p到q的推论是逻辑有效的。“相容(consistence)”也是和“逻辑源于”关系（从而和遗传模态）相关联的一种重要的模态概念。称命题p和命题q是相容的当且仅当它们中任何一个的否定都不逻辑源于另一个，或者说它们中的任何一个都不遗传另一个的否定。直观上，命题p和命题q相容，就是它们中任何一个的真都不会妨碍另一个是真的。任意给定命题p，我们当然可以形成

11、命题：p是必然的，即我们表述为：必然p（It is necessary that p）的命题。这个命题当p本身是必然的时为真。而当p不是必然的时为假。因此“必然”是一个作用于命题上的（一元（monadic）命题形成算子（operator）。无论怎样，它不是一个真值函项（truth-functional）算子；因为虽然从p的假性可得出p不是必然的（即，“必然p”是假的），但仅给出p是真的，我们不能确定p是否是必然的即，从p的真性，我们既不可能演绎出“必然p”的真性，也不可能演绎出它的假性。同样地，“可能（It is possible that）”也是一个作用于命题上的一元命题形成算子，当p是可能

12、的时，命题“可能p”应是真的；当p是不可能的时，命题“可能p”应是假的。它也不是真值函项。事实上，在讲真值函项算子时曾引导我们的注意力到“逻辑源于”（因而“遗传”和“相容”）的非真值函项性。我们把这些算子称作模态算子（modal operator）。这些即将要考虑的逻辑系统称为模态系统或模态逻辑。这些系统将都基于我们在第二章所建立的那样的命题演算上；也就是说，它们将包括所有PC的wff，其解释和以前一样（故PC的有效wff在这些模态系统中仍保留有效性），以及包括PC的初始变形规则，即一致代入规则和分离规则、定义置换规则。但我们已经知道模态算子不是真值函项算子，这意味着它们不可能由PC的算子（诸

13、如，及它们的复合）来表达，这是因为PC的算子都是真值函项。所以要得到一个模态逻辑（在它里面我们可以表达诸如“必然p” 这样的命题），为此，我们不得不增加进一步的算子到PC，并扩张我们的公式的种类。我们将引进符号（L）和（M）（作为一元算子），符号（作为二元算子），并分别解释它们的意义为“必然”、“可能”和“遗传”，并允许它们把任何公式作为自变元。这样我们就有了诸如下列这样的wff：p q（意思是“或p是必然的或q（是真的）”），(pq) q（意思是“命题q是可能的 逻辑源于命题p 且q是可能的”），等等。按照预定的解释，我们将称是必然性算子（necessity operator）和称是可能性算

14、子（possibility operator）。6.1.3 模态逻辑系统特性我们认为什么样的模态公式是有效的？很容易给出一个一般的、直观的有效性的描述。恰与我们当初为PC给出的描述一样，称一个公式是有效的，当且仅当对于它的变项们的所有取值它皆为真。在PC中，因为算子的本质是真值函项，这个最初的描述直接导致了一个十分简单的有效性的形式定义。接下来我们就能够建立起一个公理化系统，并检查它是否符合命题类应该与已定义的有效公式类恰好一致的标准。然而，由于模态算子的非真值函项特性，最初的描述并不能为我们给出一个总能给予一个清楚结果的模态公式有效性的显而易见的形式定义。但是，有某些条件，如果它有将系统解释

15、为模态系统的能力，那么我们要求系统满足这些条件，从直观上来说是合乎情理的。这些条件，我们随后将列出。它们将要求某些公式被看作是有效的（或是命题，如果这个系统是用公理化表示的），同时要求另外一些公式不被看作是有效的；但对于某些公式其有效性和无效性的未确定性将遗作一个问题。下面（在这一章和第六章）我们将构造一系列的公理化模态系统，每个系统都将满足所有这些要求。但是在象某些不太明显的有效公式作为命题时，它们的出现或缺省上，这些系统彼此又互不相同。在这之后，我们将回到用一个精确的方式来定义有效性的问题上。因此，象我们在PC中所做的那样，我们不是衡量一个公理化系统是否符合一个有效性的定义，而是相反，我们

16、将衡量各种有效性的定义是否符合已构造出的公理化系统。我们已经谈到的直观要求如下（其中一些在我们早期的叙述中已经预示过）：注：众所周知，直观上似乎合情合理的事物往往是因人而异的。在我们的合理的表中未发现所有要求的读者。1. 我们已经提到必然性和可能性之间的联系。这就导致我们要求：如果和被解释为必然性和可能性算子，则下面的等价式应该是有效的，p p，p p；包含这些等价式的系统无须将和都作为初始符号：这种系统可以将作为初始符号，并通过下面的定义引入a = a；或者选取作为初始符号，并定义a = a；具有前者的系统我们称为一个-基系统；具有后者的系统，我们称之为-基系统。在下面的几章中，我们将要研究

17、的系统事实上是-基系统。但在每种情况下，通过选取而不是作为初始符号，我们都能够给出一个恰当的、平行的系统。2.我们也已经指出模态算子不是真值函项。这意味着在任一直观上似乎合理的模态系统中，p必定不与p的任何真值函项等价（由于所有其它模态算子都可借助来定义，故只须说明要求、如同它适用于一样，就足够了）。现在，只有四个性质不同的p的真值函项：第一个是大家熟悉的p的否定；第二个是p自身（它为真当且仅当p为真）；第三个是当p是真的和p是假的时皆为真的一个真值函项；第四个是当p是真的和p是假的时皆为假的一个真值函项。因此，我们就要求下面所列出的任何一个都不应该被看作是有效的（或是命题）：pp；pp；p

18、pp；p pp。3.尽管pp不是有效的，但是很明显，它的半边蕴涵、即pp是有效的；因为这简单的表达了必然真为真的原理。这个公式通常称为必然性公理。一个似的原理是真是可能的；这点可用公式pp（可能性可能）来表达，这个公式我们同样认为是有效的。pp和pp可以用PC的等价式和联系、的等价式而很容易地互相导出。4.另一个直观上可以接受的原理是任何一个具有有效公式形式的命题不仅是真的而且是必然真的东西。这也就是说如果a是一个有效的公式，那么不仅具有形式a的每个命题都是真的，而且具有形式a的每个命题也都是真的；而且在这种情况下a本身将是有效的。因此，我们希望在一个模态逻辑中得到这样一个原理：如果a是有效的

19、，那么a也是有效的；并且在一个公理化模态系统中我们希望有这样一个（初始的或导出的）变形规则：如果a是一个命题，那么a也是一个命题。用现代数理逻辑工具研究模态逻辑领域的问题始于美国逻辑学家路易斯（Lewis）。他在符号逻辑概观（1918年）一书中建立了第一个模态逻辑系统。6.1.4 模态逻辑的简单(语义)性质为了充分理解模态逻辑的含义，我们首先介绍模态逻辑的知觉上的语义关系。通过以上的 、的语义解释有：l l l l l l 和可能同时成立Al 和不可能同时成 不 （、）Al 1，2，3，4A,B A,B,A,B, ABl l ()l 在未来的场合中，至少有一个场合或者使A成立，或者使B成立。在

20、未来的场合中，或者至少有一个场合使A成立，或者至少有一个场合使B成立。 从以上的关系上，我们可以知道模态词与量词在某些性质上是相同的。而且对于模态词来说，我们可以只有一个模态词，或者，因此，、可以进行等价的转换。6.2 模态命题逻辑的形式系统以上我们简单介绍了模态逻辑系统的中，模态词的一些知觉关系。下面我们遵从形式系统描述方式来，描述模态命题形式系统。模态逻辑形式系统与FSPC的形式系统类似，模态形式系统根据对模态词不同的解释形成不同形式系统，这些又被成为正规系统（Normal System）。下面我们就以各种不同正规系统为背景介绍模态形式系统。6.2.1 NSK系统构成模态逻辑是研究各种不同

21、的正规系统，这些正规系统中，最简单的是NSK系统。下面我们给出NSK系统的构成。1、 NSK系统语言部分l 符号表：,(,) ；其中为原子命题，为联接词，,为模态词，(,)技术符号。l 项集：空集。l 公式集：由以下递归定义：1) 为公式(i=1,2,3,4)2) 如A,B为公式,那么,()都是公式 3) 除由1,2得到外,无其它公式2、NSK推理部分l 公理集：包含以下公理：；通常被成为K公理(A1A2)( A1A2)(A1(A2A3)( A1(A2A3)( A1(A2A3)(AB) (AB)(A1(A2(A3A4)( A1(A2(A3A4) A1A2(A3A4) (A1A2A3A4)全部重

22、言式 (当A为公理)（A(BA)）l 推理规则：分离规则 ,其他概念与FSPC的概念相同，如定理、证明序列等。6.2.2 NSK性质1、如果公式A式NSK的定理，那么也式NSK的定理；即如A,则。证明:由已知有,存在A的证明序列对证明序列的长度n归纳证明:当n=1时,A为公理,所以A成立；假设nk时，命题成立；当n=k时,设Ak由Ai,Aj由分离规则得到,不妨设；由于(是定理，是定理（根据归纳假设）；由K公理可知，AiAk为定理。根据分离规则有：Ak是定理。因此，命题成立。2、设和为NSK公式，如果，则(成立。3、如果公式是NSK定理，那么A为NSK定理。证明:由于是NSK的定理，即；根据性质

23、1有是定理，即；利用公理有：,因此成立。所以是NSK的定理。4、如果,则B；推广则()。5、其他相关性质：(1) (2) (3) (4) (5)( )(6) ()()证明（1）：充分性证明：()()()K必要性证明：6、把公式A中的, 分别改为和,所得公式为；如果,则成立。AB6.2.3 正规系统语义1、正规结构定义我们知道，对于每个命题的真假都是和可能世界之间有着密切的关系。对于正规系统的语义，必须考虑可能世界。可能世界是非常多的，可能世界构成一个集合。每个可能世界对应于不同的场合，可能世界之间是可变换的。能够从一个可能变换到另一个可能世界。从一个可能世界，能否变换到另一个可能世界在赋予真值

24、时是非常重要的。例如，如果一个可能世界不能变换到其他的可能世界上，那么在这个可能世界所讨论的A和A真都是指A真这一个概念（当然，我们假设这种关系具有自反性的条件下）。可能世界之间的这种关系，实际上是可能世界的集合中的元素之间的关系。有了这种可能世界的集合和可能世界之间的关系，那么我们就可以对正规系统中任何公式赋予一定的真值。KRIPC正规结构：有以上分析可知，对于正规系统语义被成为正规结构，正规结构是指三元组，其中：l U为一非空集合，称为宇宙；其成员为可能世界，可能世界用来标记；l R为U上的一个二元关系，称为可能世界间的可达关系；l I为赋值映射，是上的映射；即对在每一个可能世界中，对原子

25、命题Pi赋值；P1,P2,P3 I(P1)=?w1w2,w1w3 w1, w2,w32、 正规结构的一些解释我们对正规系统中的一些公式进行解释，从而能够更加了解可能世界的概念。l |=表示：指在宇宙中k的w可能世界中，A为假.w1,w2,w3l |=1表示：|=对于所有，即A为真；w2,w3l 表示：存在，且使成立，即A为真；l 从以上结果可以看出，实际上，模态逻辑对于以前的结果不关心的。3、 例子：通过三个例子，使大家清楚的理解什么是正规结构。例1：设宇宙；可达关系，其中用表示可达关系，并不是说就是偏序关系或者小于关系。可达关系的机构，可以用下图来表示：AA AR: A=1 A A在W4后继

26、集合 AAAAAA=1: A=1 & A=1 ?A=1: A=1 & A:(PP) w3 (A=PvP) AA=1:A V AA A=0 v AA (PVP)=0A:A A=1AAA在w2成立. A指的是 A在W4可达集合中至少有一个成立。W2=w4 w4=w6,w2A,说明，A在和中真；A，；B;(A&A)=1, (A&A)=0,A，是真命题；根据赋值定义可以得到；(PP)A，是假命题；根据赋值定义可以得到；A，等价于A成立；例2：A在可能世界中表示：存在，使得对于所有的，A。例3：证明：（AB）是永真式。只需证明对于任意的宇宙K和可能世界，（AB）=1。根据演绎定理有：只需证明（AB）；只

27、需证明，B。对于任意的，因为=1成立且成立，因此，在中成立，因此成立。从而命题成立。6.3 NSk元理论对于NSK的元理论，我们还是从语法构成、语法语义关系等方面来论述。6.3.1 语法构成1、 NSK是独立的,若把公理A从NSk中删除后,所得系统不满足A；2、 NSK是一致的,不存在NSk的公式A,使得NSkA和NSkA同时成立；3、 NSk是不完全的,存在公式A,使NSkA和NSkA都不成立；4、 NSk使可判定的,即对公式A,存在一个算法,判定A使否为定理(定理集合为递归集合)；5、 演绎定理：对于任何NSk对公式集及公式A,B, ,当且仅当,；6、 替换原理：在NSk中,如果AB,A为

28、C的子公式,将C中若干个A替换为B,得 到公式D,则CD；7、 对偶原理：对任何NSk中公式A, NSk,其中为A的对偶,且A*递归定义如下: (6)(A)*=A* (7) (A)*= A*例: (AB)( AB)(AB)V(AB)(AB)V(AVB)(AVB)V(AVB) (AVB)V(AVB) (A&B)V(A&B) =() =(=(AB) (AB)6.3.2 语法语义关系1、 合理性: NSk是合理的,即如果对公式A有A ,则|=A；2、 完备性: NSk是完备的,即如果对公式A有|=A, 则A。6.4 其它正规系统6.4.1 其他公理正规系统的区别在于公理系统不同，由于公理系统的差别带

29、来了可达关系的不同。下面介绍其他正规系统中的公理。NSKTD：AA T：AA, AAB：AA4：AA5：AAw, w11,w12,w13, 包含于w111,w112，并且包含于w121,w122，并且包含于w131,w132|=v(w11,w12,w13) A=1;|=w11,12,13 A=1; |=w111,w112, A=16.4.2 可达关系1、连续性：对于宇宙上的可达关系R，如果对于宇宙中的每个可能世界都有一个后继，则称R是连续的。AA D有R的连续性可知，对于AA是永真式。在通常的情况下，A 则 A是成立的，例如： 但是当w为U中最后一个元素时，(A)=1而(A)=0，因此，A 则 A不成立。 为了使AA，在任何情况下都成立,则必须限制R为连续的；因此连续性保证：从而D 连续2、自反性：对于宇宙上的可达关系R，如果满足，则称R为自反的。我们知道对于A成立，而A未必成立。如下图所示：A 解释:而A不一定为真;对于模态逻辑，评直觉通常认为AA，AA都应该是成立的。但是在模态逻辑中，这个公式未必成立（对偶