数理逻辑-余俊伟（一）

目录

第1章 哲学缘起 ▹

1.1哲学求真 ▹

1.2从哲学到逻辑 ▹

第2章 命题逻辑 ▹

2.1导言 ▹

2.2 语言 ▹

2.3语义 ▹

2.4公理系统 ▹

2.5可靠性和完全性 ▹

第3章一阶逻辑 ▹

3.1导言 ▹

3.2语法 ▹

3.3语义 ▹

3.4公理系统 ▹

3.5完全性定理 ▹

3.6紧致性定理（紧性定理） ▹

3.7哲学的应用 ▹

第4章 一阶理论 ▹

4.1导言 ▹

4.2 结构与理论 ▹

4.3 无端点稠密线序理论DLO ▹

4.4随机图理论RG ▹

4.5算术真理论 ▹

4.6公理集合论 ▹

4.7相对一致性 ▹

第5章 不完全性 ▹

5.1希尔伯特纲领 ▹

5.2图灵可计算性 ▹

5.3第一不完全性 ▹

5.4第二不完全性 ▹

5.5希尔伯特纲领所受影响 ▹

第6章 模态逻辑 ▹

6.1现代模态逻辑的产生背景 ▹

6.2模态命题逻辑简介 ▹

6.3 从逻辑到哲学 ▹

第1章 哲学缘起

1.1 哲学求真

哲学前期人们用神话解释自然，后来出现超出神话的解释即科学，此阶段的科学以哲学形式呈现。哲学从研究事物本原及第一原理开始即形而上学。找普遍原理体现了哲学求真性，并要求内在连贯性和满足符合论，也就是合乎逻辑。也就是说哲学孕育了逻辑学。

巴门尼德时期人们认识到语言作为论证媒介有重要性，认为外界事物要进入思维领域才能成为思考的对象，于是开始研究语言与思维的关系。这种研究到亚里士多德时期为高峰，即《形而上学》研究being，其他学科只研究being的一个方面。being在希腊语中为语词einai，有多种变化形式，一方面承载谓述功能，另一方面具有实体涵义。该词所陈述的内容有本质和偶性方面，则einai也随之变为是（什么本质）和有（什么性质）两种意思。einai的现在分词ousia即实体的意思，表明“是”与本体关联。因此围绕之展开，确认底基并围绕底基论述性状，于是有了《范畴篇》十范畴。判断实体有两标准：是否谓述、是否位于主体中。研究是否谓述发展出逻辑理论如四谓词、三段论。研究是否位于主体之中也就是研究底基本身，研究“是者”，发展出形而上学，在《形而上学》中终极实体不再是可感个体而是形式。这是亚氏的两条路线。

1.2 从哲学到逻辑

1.2.1 亚氏逻辑与哲学‬

根据判断实体的两标准分出四类存在者：谓述主体且在主体中、谓述且不在主体中、不谓述且在主体中、不谓述也不在主体中。不谓述也不在主体中的为第一实体。第二实体是第一实体上归的种属（例：第一实体为一个人，第二实体则是集体人这种动物，或者说第二实体是抽出共性后的概念），也就是开始研究范畴。然后根据是否谓述得到十范畴：实体、数量、性质、关系、处所、时间、状态、姿态、能动、受动。然后又把十范畴概括为《工具论·论题篇》的四谓词：定义（表本质）、固有特性（表固有性质）、种（上归的范畴）、偶性（表偶然性质），讨论四谓词时已经涉及语法（如换位）。四谓词是一种方法论，开始远离形而上学。《工具论》要求专门研究推理论证。

《工具论》中说，推理是一种论证，有些被设定为前提，另外的判断则必然由它们发生。然后区分了证明的推理、辨证的推理、虚假的推理。前提真是指不证自明且独立的或普遍的。推理探索能训练智力、促进交谈、哲学思考。推理意味着我们有了从两方面探讨问题的能力。该理论特别适用于初始原理。

四谓词和十范畴的关系：四谓词总是十范畴之一，一词多义，有时候表示实体，有时候表性质。从十范畴过渡到四谓词表示亚氏开始思考命题，即考察谓项陈述主项的一般特征。《工具论·解释篇》开始研究命题，不是每个句子都能作命题，命题要有真假。

然后开始构建三段论。亚氏三段论要求结构异于前提，认为全称特称外还有不定称（即没有说清楚量）且没有单称（因为要求第一实体不谓述任何一个主体也不在任一主体中）且排除了既可以作主项又可以作谓项的词。随着深入，由研究内涵到了研究外延，研究外延后不定称就失去了意义，到今天被归到全称里了。

1.2.2 弗雷格逻辑与哲学

然后是漫长的历史，如斯多葛学派克吕希波把斯多葛逻辑发展成命题逻辑并给出公理系统。

康德认为亚氏形而上学没建立完于是想建立科学形而上学，认为首先考察人的认识能力本身，然后构建了名为逻辑实则为认识论的先验逻辑，他认为直观与概念结合才是知识。康德摆脱了神学、批判了独断论。康德称亚氏的逻辑为普遍逻辑，然后分析了分析与综合两个范畴，包含在主词中的为分析，不包含的为综合。

弗雷格继承了亚氏第一实体的标准。为澄清数的概念和理解如何获得数命题及性质需要概念文字这种推理工具。弗雷格只研究数学领域的being。

符号体系只是形而上学工程的一个子项目，特色即形式化。自然语言一词多义使它表面的语言语法结构掩盖了深层的逻辑语法结构。弗雷格就抛弃了主谓式改用函数式，并引入概念-对象范畴。概念是值为真值的函数，可以被谓述，对象不能被谓述。然后引入逻辑联词，引入涵义-所指范畴，与内涵逻辑学派和心理主义斗争。造完推理工具后，化归失败了。

函数式的实质是把“是”字取消了，把关系藏起来了，于是形而上学问题被遮盖了。弗雷格后人们研究形式化，如塔斯基的形式语义学（真不可定义性），如哥德尔形式系统证明（哥德尔完全性定理和不完全性定理）。

比较康德与弗雷格的工作：康德在逻辑外设范畴再来审视数学，弗雷格则基于数学再还原（倒推，找数学本原）。弗雷格认为算术真是分析的。弗雷格考察面更窄，步骤保分析性。创立了数理逻辑。

第2章 命题逻辑

2.1 导言

2.1.1 什么是命题逻辑

命题逻辑研究以简单命题为最小单位的关于联词的逻辑规律及其推理。命题是有真值的陈述句。联词连接命题。推理是依据规则由若干命题得到一个命题。推理有层次，暂不考虑一个命题内部结构。命题有真假，偶然性真假暂不考虑。有效通过真来定义。

2.1.2 命题逻辑发展简史

亚氏重视量词，没有重视命题逻辑，但提到的排中律等逻辑律与命题逻辑有关。斯多葛派哲学家对命题算子研究。斐洛对条件句前后件做了研究。斯多葛克吕希波为论证给出了形式化复杂前提的不同方法及其推理模式，如分离规则等。阿贝拉德区分相容和不相容析取。

德摩根后，布尔用布尔代数取代三段论，引入0和1，造了很多联词，被用于计科真值函数命题逻辑基础。弗雷格给出现代第一个公理演算系统，也第一次论证所有联词都能用否定和实质蕴涵定义。罗素给出其他公理系统。皮尔士、谢费尔得出用一个二元算子能定义所有真值算子。尼可德发现只用谢费尔竖一个联词、一个公理模式、一个推理规则就能给出命题逻辑的公理化。多人给出真值表，以及后来重视元理论。根岑给出古典真值命题逻辑的完全自然演绎系统。

模态命题逻辑是非真值函数命题逻辑形式，亚氏到刘易斯都有研究。其他非经典命题逻辑也很快发展。

2.1.3 本章基本脉络

构建一个人工语言，以此为基础给出命题逻辑的形式语义和命题逻辑的一个公理系统，再用可靠性和完全性探讨两者关系。此外还介绍公理独立性、紧致性、可判定性。

2.2 语言

所谓语言，就是自然语言、人工语言这样的一个系统，载体为语句。构建人工语言要满足充分性（即表达力能满足要求）、简洁性、无歧义性。首先给出初始符号，包括命题变元、联词（未解释前无意义）、技术性符号（如括号）。这是对象语言层的符号。然后还有谈论对象语言的元语言符号，如任意命题变元、任意公式、任意公式集。然后给出公式形成规则，也就是合式公式。再给出公式定义，即表达式根据公式形成规则形成公式。然后根据联词定义引入联词，可略去，规定一些能省略的括号、联词结合力度、结合顺序等。还有其他构建方法，如波兰式等。这些方法的相同点：定义公式集合的形式化规则是递归的。

2.3 语义

2.3.1 真值

命题逻辑的真值符合二值原则，即真假二值。命题逻辑语义提供一种形式化方法来表达真值和真值条件，即符合论下一个原子命题一个真值，原子命题通过联词组合得到复合命题，从而能确定复合命题的真值。

一直真的命题为重言式，反之矛盾式，分情况的为偶然式。

2.3.2 组合性

组合原则：复合命题的真值由语法构成的真值及语法结构决定。语法结构包括联词和位置两方面。复合命题的公式可根据命题逻辑公式形成规则构建。

因为联词未解释前无意义（2.2节的内容），因此要定义联词，然后才能知道复合命题的真值，

2.3.3 联词与真值表

常用联词有五个，每个都有真值表。析取常用的是相容析取，蕴涵是实质蕴涵。

真值表的优点是直观，缺点是使我们忽略联词本质。联词的本质是函数。真值表法只是一种形式化语义的方法，变元很多时真值表法很困难，因此需要另一种更一般化的表达联词真值的严格语义解释。

2.3.4 形式语义

这种新语义方法如下：语义赋值函数给每个命题赋一个真值。归纳定义后穷尽了所有公式情况。在一个赋值下所有命题都有唯一解释，因此被称为一个模型。因为原子命题无穷所以模型无穷。

然后定义可满足性就是是否存在满足赋值为1的情况，以此定义重言式等。语义后承即真值表里可满足的种种情况。公式、公式集的可满足性都同理。

所谓语法，即句法，即符号集和规则。语法后承是一个公式集根据规则得到的公式。所谓语义，是给语句赋值，也就是真值。比如语句代入值。赋值的本质是函数，函数代入后可得所有公式集。语义后承可以视为真值表法。对形式系统的研究有两种方法：语义方法（模型论方法）和语法方法（证明论方法）。语义方法研究重言式，语法方法研究形式定理。两方法等价。

2.3.5 常见重言式

构建命题逻辑的主要目标就是把范围里的全部重言式找出来。可以一个个解释，也可以构建公理系统或自然演绎系统解释。下面尝试构建一个公理系统。

2.4 公理系统

给出公理、推理规则、证明的定义，能得出内定理。

2.4.1 命题演算‬

例如给出三条公理和一条初始推理规则（分离规则）。

2.4.2 证明和内定理

公理用分离规则得到的序列即证明。即证明是从公理出发通过分离规则得到一个又一个公式。证明的名称以最后一项定，比如最后一项为φ，则叫φ的证明。

如果φ有一个证明，则称φ为一个内定理。每个公理都是内定理。内定理也是模式，即每个内定理模式中都包含了无穷多个内定理。

2.4.3 演绎规则

推广证明的定义，得到演绎。演绎比证明多一个条件，要求φi为给定公式集中的公式。

一步步推下来的序列可视为一个演绎规则。常见演绎规则如德摩根律等。

2.4.4 演绎定理‬

证内定理时不能用假设，演绎规则的假设必须是前面就得到的。因此还要一些能消去假设的原则如演绎定理，可以从有假设的演绎得到内定理。演绎定理有逆。演绎定理和逆揭示了内定理和有前提（假设）间的关系。

2.4.5 公理的独立性

公理系统的出发点是公理，公理是否冗余即公理独立性问题。演绎规则不变，一条公理不能由其他公理推出，则该公理为独立的。如果一公理系统的每条公理都独立则该公理系统独立。演绎规则不变，一公理模式不能由其他公理模式推出则该公理模式独立。公理系统中每个公理模式都独立则该公理系统独立。

如果想证“不能推出”，用语义赋值方法。想证“推出”，用形式证明方法。

2.5 可靠性和完全性

前面给出了语言和语义，定义了重言式和语义后承。然后给出了一个公理系统（公理、推理规则），讨论如何进行形式证明和演绎来获得内定理和演绎规则。接下来检查该公理系统是否是命题逻辑的形式化，即检查可靠性和完全性。如果该公理系统的内定理都是语义解释所肯定的公式则可靠，如果该公理系统在语义解释下的肯定公式都是内定理则完全。

2.5.1 可靠性证明

即证明命题演算的所有内定理都是重言式。

2.5.2 完全性证明

完全性有两种证法，一是亨金证明（用极大一致集），二是哥德尔证明。

公式集中某公式推出矛盾则该公式集是不一致的，反之则是一致的。极大一致集是该公式集本身为一致集，并上任意公式后仍然一致。可数语言的系统往往有不可数个极大一致集。不同系统的极大一致集不同。一个公理系统的极大一致集可以不是另一公理系统的一致集。极大一致集的重要引理即林登鲍姆引理，即每个一致集都能扩张成极大一致集。极大一致集不再有一致的真扩张。还有一个定理：φ是任意公式，演绎推出φ，当且仅当φ属于每个极大一致集。命题演算的内定理集恰好是所有命题殴极大一致集的公共部分。

亨金证明：φ不是内定理等值于φ不是重言式，用林登鲍姆引理和上面那个定理证。完全性定理：若φ不是内定理则其矛盾式~φ一致，再由林登鲍姆引理的存在极大一致集使得~φ属于极大一致集，存在赋值使得~φ为1则φ为0。

2.5.3 广义完全性定理

根据可靠性和完全性定理，对于命题逻辑，语法内定理和语义重言式对应。继续进一步考虑语法演绎与语义后承的对应性。

广义可靠性定理：如果极大一致集演绎推出φ，则极大一致集推出的是重言式φ。

广义完全性定理：如果极大一致集推出的是重言式φ，则极大一致集演绎推出φ。

2.5.4 证明公理的独立性

证明公理独立性与证明可靠性相似。证明思路：要证某公理模式有独立性，先选一性质使得其他公式有该性质，演绎规则保持该性质不变，但公理模式中能找出一个公式没有该性质，因此该公理模式不能从其他推理模式中推出，因此该公理模式有独立性。

2.5.5 紧致性和可判定性

紧致性定理：某公式集可满足当且仅当该公式集的每个有穷自己都是可满足的。

可判定性：如果存在一个算法告诉我们某公式是否是内定理，则该逻辑可判定。命题逻辑的真值表算法能判定重言式，因此命题逻辑可判定。而一阶逻辑不可判定。用此可区分命题逻辑和一阶逻辑。

除了公理系统还有自然演绎系统。

第3章 一阶逻辑

3.1 导言

3.1.1 问题引入

命题逻辑有缺陷：不处理原子命题内部结构。因此推广命题逻辑为一阶逻辑。

3.1.2 早期简史

一阶逻辑源自两个传统：英美代数传统、德国实分析传统。发现过程三条路径：布尔-德摩根-皮尔士，弗雷格，布尔-皮亚诺。地位确立有三点：独立的主体地位、与高阶逻辑比的优势地位、与集合论共同的数学基础地位。历史为网状结构。

布尔把三段论转为代数演算，把符号理解成类或命题，量词被归约，不处理量词和多元谓词，也不处理叠置量词，即命题逻辑的一元一阶逻辑片段。德摩根、皮尔士、皮亚诺扩充布尔的系统：引入n元谓词和引入量词。弗雷格也独立完成了这些步骤。

德摩根引入关系逻辑定义关系的逆关系和对立关系，并讨论复合关系，扩展了三段论逻辑。缺点是只处理二元关系，符号也笨，无布尔联词符号。

皮尔士简化了布尔的系统，重新定义并集（逻辑加）使得交集非空时能用，也研究复合关系，且可以n元关系。后来引入量词，把量词视为联词的推广。把全称量词视为多个公式的合取，存在量词则是多个公式的析取，从此可将多个量词叠置来构造任意深度的量词，后来启发勒文海，得到勒文海-斯库伦定理确立了一阶对高阶的优势地位。皮尔士还讨论命题逻辑，给出命题逻辑重言式判定顺序。讨论第一内涵逻辑（一阶逻辑），量词只能作用于个体变元不可作用于谓词，并给出公式转为前束范式的规则。讨论第二内涵逻辑，量词可作用于谓词。他从唯名论立场支持第一内涵逻辑反对第二内涵逻辑。

施罗德介绍布尔和皮尔士时不区分一阶二阶量词，有次将某个二阶全称量词视为无穷多个一阶量词的合取启发了勒文海得到勒文海定理。

弗雷格则独立发现一阶逻辑，他认为实分析数学基础不够可靠因此要从逻辑中推出。对函数（可视为关系）和变元分析促使引入关系（谓词），实分析中有大量含量词的命题则又引入量词。他还区分了阶：如果概念A落在概念B下，则相对的B即二阶，还考虑过三阶。

弗雷格比皮尔士早，且独立，公理化更精确，逻辑更普遍，对后世影响更大。但弗雷格不区分第一内涵逻辑这些，以及符号系统复杂。

皮亚诺独立把关系和量词引入逻辑，还做了算术公理化。他的公理化是二阶的但他没有意识到阶。引入了各种符号。

罗素发现罗素悖论，认为要避免类，于是创立了类型论，型即阶，区分了第一层次型和高层析型，这与将第一层次型对应的一阶逻辑视为独立的研究对象不同。虽然罗素和怀特海提供了类型化的公理系统，但它们将其视为陈述逻辑真概念的解释性系统而不是形式演算，因此没有区分逻辑和元逻辑，就发现不了一阶逻辑有别于高阶逻辑的元逻辑性质，因此不能给予一阶逻辑足够的地位。

综上所述，一阶逻辑高于高阶逻辑地位还没确立，要么被包含在高阶里要么被视为和高阶同等。后来勒文海-斯库伦定理和完全性等重要元逻辑性质被发现，才确立主体地位。

希尔伯特最早谈论元逻辑，并提出希尔伯特问题。希尔伯特还做了一些不含归纳法算术一致性的工作，标志着证明论开始。

数学联邦政治世界观提示您：看后求收藏（笔尖小说网http://www.bjxsw.cc），接着再看更方便。