数理逻辑讲稿

《数理逻辑讲稿》由会员分享，可在线阅读，更多相关《数理逻辑讲稿（22页珍藏版）》请在装配图网上搜索。

1、数理逻辑讲稿数理逻辑 又称符号逻辑、理论逻辑。它是数学的一个分支，是用数学方法研究 逻辑或形式逻辑的学科。其主要特征之一是“形式 化”，就是将数理逻辑的研究对象“数学推理形式化，推理都有前提 结论和推理规则，这些前提和结论都是命题。一个推理系统包含命题、 公理和推理规则，“形式化”即为将这样的推理系统符号化而形成一 个形式系统。用数学的方法研究逻辑的系统思想一般追溯到十七世纪莱布 尼茨，他设想过能不能创造一种“通用的科学语言”可以把推理过 程象数学一样利用公式来进行计算，从而得出正确的结论。由于 当时的社会条件，他的想法并没有实现。但是它的思想却是现代 数理逻辑部分内容的萌芽，从这个意义上讲，

2、莱布尼茨可以说是 数理逻辑的先驱。后人基本是沿着莱布尼茨的思想进行工作的。1847年，英国数学家布尔发表了逻辑的数学分析，建立 了“布尔代数”并创造一套符号系统，利用符号来表示逻辑中的各 种概念。布尔建立了一系列的运算法则，利用代数的方法研究逻 辑问题，初步奠定了数理逻辑的基础。十九世纪末二十世纪初，数理逻辑有了比较大的发展， 1884 年，德国数学家弗雷格出版了数论的基础一书，在书中引入 量词的符号，使得数理逻辑的符号系统更加完备。对建立这门学 科做出贡献的，还有美国人皮尔斯，他也在著作中引入了逻辑符 号。从而使现代数理逻辑最基本的理论基础逐步形成，成为一门独立的学科。数理逻辑就是精确化、数

3、学化的形式逻辑。它是现代计算机技术的基础。数理逻辑的内容两个最基本的也是最重要的组成部分，就是“命题演算”和“谓词 演算。命题演算是研究关于命题如何通过一些逻辑连接词构成更复 杂的命题以及逻辑推理的方法。命题是指具有具体意义的又能判 断它是真还是假的句子。在谓词演算里，把命题的内部结构分析成具有主词和谓词的逻辑形式，然后研究这样的命题之间的逻辑推理关系。数理逻辑的发展数理逻辑这门学科建立以后，发展比较迅速，促进它发展的 因素也是多方面的。比如，非欧几何的建立，促使人们去研究非 欧几何和欧氏几何的无矛盾性。集合论的产生是近代数学发展的重大事件，但是在集合论的 研究过程中，出现了一次称作数学史上的

4、第三次大危机。这次危 机是由于发现了集合论的悖论引起。什么是悖论呢？悖论就是逻 辑矛盾。集合论本来是论证很严格的一个分支，被公认为是数学 的基础。1903 年，英国唯心主义哲学家、逻辑学家、数学家罗素却对 集合论提出了以他名字命名的“罗素悖论”这个悖论的提出几乎动 摇了整个数学基础。罗素悖论中有许多例子，其中一个很通俗也很有名的例子就是“理发师悖论”某乡村有一位理发师，有一天他宣布：只给不自己刮胡子的人刮胡子。那么就产生了一个问题：理发师究竟给不 给自己刮胡子？如果他给自己刮胡子，他就是自己刮胡子的人， 按照他的原则， 他又不该给自己刮胡子； 如果他不给自己刮胡子， 那么他就是不自己刮胡子的人

5、，按照他的原则，他又应该给自己 刮胡子。这就产生了矛盾。悖论的提出，促使许多数学家去研究集合论的无矛盾性问题， 从而产生了数理逻辑的一个重要分支 公理集合论。非欧几何的产生和集合论的悖论的发现，说明数学本身还存 在许多问题，为了研究数学系统的无矛盾性问题，需要以数学理 论体系的概念、命题、证明等作为研究对象，研究数学系统的逻 辑结构和证明的规律，这样又产生了数理逻辑的另一个分支 证明论。数理逻辑新近还发展了许多新的分支， 如递归论、模型论等 递归论主要研究可计算性的理论，它和计算机的发展和应用有密 切的关系。模型论主要是研究形式系统和数学模型之间的关系。本课内容经典逻辑(命题逻辑、谓词逻辑)

6、非经典逻辑(程序逻辑、时态逻辑、模态逻辑)第 1章 命题逻辑命题逻辑是数理逻辑中最简单、最基本的部分。11 命题联结词一个能判断真或假的陈述句是命题。例如：5 大于 9。今天下雨了。但是，“a大于b”，“请勿吸烟”，“我正在说谎”都不是命题。 将命题符号化，记为 p,q,r. 。真命题记为1 (T)，假命题记为(F)。不能分解为更简单的语句称为原子的，通过联结词可以构成复合命 题。定义：设p,q为命题。P的否定(negation)，记作-p，-p为真当且仅 当p为假；“ p或者q”称为p和q的析取(disjunc tion，记为p v q， p v q为真当且仅当它们至少有一个为真；“ p并且

7、q”称为p和q的合 取(conjunction)，记为p Aq，p Aq为真当且仅当它们都为真；”如果p， 则q”称为p和q的蕴涵(implication)，记为p q，并称p是p q 的假设(assumption)，而q是其结论(conclusion。p q为假当且 仅当p为假，而q为真。注:(1)关于p - q，我们感兴趣的是数学推理和证明的方法，即p为 真能推出q为真，而没必要考虑p为假时推出什么来。例如，“对于某个实数n，如果n 2,那么n 2 4 ”是真命题。 (2)蕴涵词可以连接两个毫不相干的命题，例如：如果地球停止了转动，那么大熊猫产在中国。1.2 自然演绎假定有一组称之为前提(

8、premises)的公式帚02，%，以 及另一个称之为结论(conclusion)的公式屮。通过将证明规则应用于前 提，我们希望能得出更多的其他公式，再将更多的证明规则应用于这 些公式，最终得到结论，记为%，札，札z屮这个表达式称为矢列(sequent)，如果可以找到它的一个证明，称 此矢列为有效的(valid)。例矢列p a - q f r， r，p Z q。1.2.1 自然演绎规则合取规则(a)：合取引入。将这个规则写为：0 屮 a ie a屮横线的上面是该规则的两个前提，横线的下面是结论，在横线的右方 写下了该规则的名称， ai 读做“合取引入”。合取消去的规则有两个0 A屮ae1ae2

9、(1_1)0屮规则A勺说的是：如果有了0 A屮的证明，然后通过应用该规则就可以得到0的一个证明例证明p a q，r Z q a r有效。证明：1 pAq前提2 r前提3 qA e2 14 q A rA i 3 ，2练习： (p A q) Ar， sA t Z qA s 是有效的。双重否定规则 双重否定的消去和引入规则：i40ii eii i00蕴涵消去规则 在自然演绎中，将此规则写为00 屮e屮反证规则(modus tollens)，或缩写为MT：0 屮屮i0MT例 证明矢列p (q r), p, - r Z - q的有效性:1p (qr)前提2p前提3r前提4qre 1， 25qMT 4，

10、3蕴涵引入规则 假定有p q,若临时假定-q成立，我们可以应用 MT推断出-p。于是，假定p q，我们可以证明-q蕴涵-p，因 此,有 p q Z q p 的一个论证:1p q前提2-q假设3-pMT 1，24q pi 2-3现在，使用规则i证明p q被称为类型检测(type checking),在构造带类型编程语言的编译器时，类型检测是一个重要的论题。于是，我们将规则i形成固定格式如下：i例证明矢列-q -p Zp - q的有效性:1-q - p前提2p假设3pi 24-qMT 1，35p qi 2-4定义若逻辑公式e具有有效的矢列ze，则称e是定理。例 下面是定理的一个例子.1234567

11、8(-q p) (p r)i2-89q r假设q - p假设p假设pi 3qMT 2，4qe 5r-e 1，6p ri 3-710(q r) ( q p) (p r)i1-9事实上，可以将帚 ，札也屮的任何证明变换为定理Z % f 2 f （% f （f （紂 f 屮） 的一个证明。例证明矢列p a q f r Zp f (q f r)的有效性：123456p假设q假设p a qAi2,3Rfe 1， 4p a qfr前提q f rfi 3-57p f(qfr)fi 2-6例证明上面矢列“逆”的有效性1p (q r )前提2p a q假设3pAex 24qAe225q re 1，36re 5，

12、47p a q ri 26p a q r Z p (q r)和 p (q r) Z p a q r 的有效性说明这两个公式是等价的，即可以从一个证明另一个。把这种情况表示为p a q r QZ p (q r)符号Z的右边只对应一个公式，而符号QZ对应两个公式。析取规则从前提e出发，可以得到讪或屮成立，因为我们知道e成立。我们有证明规则：eVIe v屮vie v屮1“或消去” (or-elimination)规贝Uve:也就是说：如果ev屮是真的，并且一不管假设e还是屮一我们 都可以得到c的证明。例证明矢列q r Zp v q fp v r的有效性。12345678qfr前提p v q假设p假设

13、p v rvi 3q假设re 1，5p v rvi2 6p v rve 2， 34，57pv qfpv rfi 28否定规则 公式 代表矛盾。定义 矛盾是形如e a -1或-1 a e的表达式，其中e是任意公 式。事实上，矛盾不仅能推出矛盾，矛盾还可以推导出任何公式。丄（矛盾）可以证明论证中的任何编码公式：丄丄ee例应用规则证明-p v q Zp f q是有效的：1- pv q23456-p前提p假设丄e 3， 2qe 4p qi 3 5q前提p假设q复制2p f qi 3 4ve 1，2 67 pfq规则-i：例证明矢列p f q, p f -q p 的有效性：1pfq前提2p fq前提3p

14、假设4qfe 1,35e 2,36丄-e 4,57p-1, 3-61.2.2 派生规则有些规则不是原始规则，可以从其他规则推倒出来。例如反证规则(MT)：e 屮一i屮MT1e f屮前提2-屮前提3假设4屮fe 1, 35丄e 4, 26-e- 1 3- 5同样，规则：0iii十0也可以从规则-i和-e得到，推导如下:10前提2-0假设3丄i e 1， 240-i 2 3还有反证法(proof by contradiction),简记为PBC。该规则的含义为：如果由-0能够推出矛盾，那么就可以判断0成立：丄PBC0可以把这个证明转化为-0丄的一个证明，过程如下：1-0 丄已知2-0假设3丄-e

15、1，240-i 2 350-e 4这说明 PBC可以有i，- i， e和-e推导。1.2.3逻辑等价定义设0和屮是命题逻辑的公式。我们说0和屮是逻辑等价(provably equivalent)的，当且仅当矢列Q Z屮和屮Z Q都是有效的； 即可以从Q出发证明屮，反之亦然。正如前面看到的，我们用Q QZ屮 表示Q和屮是逻辑等价的。1.2.4 反证法有时我们不能直接利用已知的假设和推理方法给出证明。可以使用间接证明：例如，规则丄pbc这是经典逻辑学家主张的，但直觉主义逻辑学家-认为：为了证明Q,你必须直接去做，而不能只是证明Q不可能。经典逻辑学家与直觉主义逻辑学家在另外两个规则上的观点也不一致：

16、十QLEM 1 直觉主义逻辑学家认为，要证明Qv - Q必须证明Q，或者-Q。如果二者都不能被证明，那么析取的真值就不能被确定。定理 存在无理数 a 和 b， 使得 ab 是有理数。证明：我们选择b为込，并通过对各种情形的分析来进行证明。 bb 或者是无理数，或者不是。假设bb是有理数，那么结论成立。(ii)假设bb是无理数。那么我们稍微改变一下策略，选择a 是.门。很清楚，由情形（ii）的假设，a是无理数。但我们知道b是无理数, 因此，a和b都是无理数，并且：J- L（L yL_ab = （122 = ；22- 2） = （、2）2 = 2是有理数。因为上面两种情形无遗漏（b b或者是无理数

17、，或者不是），故我们 证明了定理。1.3 作为形式语言的命题逻辑命题逻辑中的公式一定是字母表p, q，r, c P, p2, P3， c ，A, v, f （, ）上的符号串。仅这种描述还不够，例如，（） （）vp q f是上述字母表上的符号串，但是就我们目前所关心的命题 逻辑来说它没有什么意义。因此，必须严格定义我们称之为公式的那 些符号串，称这样的公式为合式的（well-formed）。定义 命题逻辑的合式公式是且仅是那些有限次使用下面构造规 则所得到的符号串：原子：每个命题原子 p， q， r， 和 p， p2， p3， 是合式公式。-:如果是合式公式，那么（）也是合式公式。a：如果和屮

18、是合式公式，那么e a屮也是合式公式。V：如果和屮是合式公式，那么V屮也是合式公式。:如果和屮是合式公式，那么 f屮也是合式公式。上述定义命题逻辑合式公式的归纳定义经常以定义语法 的Backus Naur范式（BNF）的形式给出。使用这种形式，上面的定义可以 更紧凑地写为：e: = p i（1Q）i（ a ）i（ v ）i（QQ）其中p代表任意原子命题,，:=右边的e的每一次出现都表示任何已 经构造好的公式。1.4 命题逻辑的语义1.4.1 逻辑联结词的含义前面讨论矢列e1, e2,，en也屮有效的一种推理演算，即从前 提e1，e2，en，我们可以得到结论屮。在本节中，我们给出前提e1，e2，

19、比和结论屮之间关系的另 一种描述。定义一个新的关系，记为：%，%，enC 屮这种描述基于考虑前提和结论中的原子公式的“真值”，以及逻辑连 结词如何影响这些真值。定义1.真值集合包含两个元素T和F,其中T表示“真” F表示“假”。2.公式e的一个赋值或模型（valuation or model）是对e中的每个命题原子指派一个真值。eTFFTe屮TTTFFTFF0屮TFTT可以看到e屮是真的当且仅当e v屮是真的。这说明o 屮和o v 屮是语义等价的(semantically equivalent)。给一个含命题原子,p2,pn的公式e，至少可以从原理上 构建真值表，真值表有2n行，每一行是pi,

20、 p2,，pn真值的一个组 合。1.4.2 数学归纳法假设有某种我们认为对所有自然数成立的性质M。对于性质M，下 面两个情形成立：1基本情况：自然数1有性质M，即有M(1)的证明。 2归纳步骤：有一个 M(n) M(n + 1)的证明。定义 数学归纳原理就是说，基于上面两个信息，每一个自然数都有 性质M(n)。归纳步骤中的假设M(n)称为归纳假设(induction hypothesis)。串值归纳(Course-of-value induction)。数学归纳法的一个变化是关于归纳假设的，即证明M(n + 1)不只需要M(n),而需要合取M(1) a M(2) aa M(n)。称这种变种的归

21、纳为串值归纳。图 1-10 高度为 5 的语法分析树定义给定一个合式公式咖定义它的高度为1加上它的语法分 析树中最长路径的长度。因为每一个合式公式都有有限高度，我们可以对合式公式的高度 运用数学归纳法来证明命题。这种技巧常被称为结构归纳法(structural induction)，这是计算机科学中很重要的推理方法。定理 对命题逻辑的每个合式公式，左括号的个数等于右括号的个数。证明：对合式公式的高度使用串值归纳法。令M(n)表示“所 有高度为n的公式的左括号数与右括号数相等”假设对每个k 1，对于合式公式 ， 的语法分析树的根一 定是，f V或Ao假设根是另外三种情况的讨论类似。那么是 f 2

22、)，其中1和2是合式公式。很清楚， 1和2的高度严格小于no使用归纳假设，我们得到1的左、右括号数相等，同理对2也成立。但对(1 f 2)，我们增加了两个括号(和)。这样， 中出现的(和)个数相同。1.4.3 命题逻辑的合理性假设我们有，2，n力屮的一个证明，是否有可能出现一个 赋值，尽管所有命题，2，n是真的，而屮的是假的？定义 若对使所有命题虬，2，n都赋值为T的一切赋值，屮 也赋值为T，则我们说1，2，n C 屮成立，称C 为语义推导关系(semantic entailment relation)。合理性论证就是证明：若，2,，n也屮是有效的，贝I，2,， n C屮成立。定理(合理性)设

23、,e”和屮是命题逻辑公式。右0,鴨，札z屮是有效的，则0, 02，札C屮成立。证明：因为0， 02，0nz屮是有效的，则存在一个由前提0， 02,，札得到屮的证明。对这个证明的长度使用数学归纳法进行推 理。M(k): “对所有存在一个长度为k的证明的矢列0，02，0n z屮, 有0， 02，0n C屮成立。”假设对每个ky k，有M(k)，我们试图证明m閃。 基本情况：仅有一行的证明。若证明的长度为 (k= )，则它一 定是如下形式的：e前提讨论的矢列是e z e。当然，因为e赋值为t，故e也是t。于是，如我 们所断言的那样， eCe。串值归纳步骤：假设矢列e，e2，enz屮的证明长度是k，而

24、 要证明的命题对于证明长度小于k时成立。证明有下面结构：e 前提2e 2前提ne n前提nk屮理由需要讨论最后一行是应用什么规则得到的。一般地，因为我们不知道 应用了什么规则，因此，需要依次讨论各种规则。1. 假设最后规则是Y。那么，屮应该是形式屮人屮2,第k行的理 由是上面有两行分别是屮和屮2,屮作为它们的结论。假设这两行 是和k2，因为%和k2小于k，所以有两个长度小于k的矢列， %，紂Z屮和，%，紂力屮2的证明，它们分别在原来证 明的第k和k2行。由归纳假设，得到，%，0n C屮和， %，n C屮2成立。这两个关系也能推出0，%，n C屮人 屮2成立。2. 如果证明屮需要使用规则ve，那么一定在证明中有一个矢列 01，02，0n力q v n2的更短的证明，以及矢列01，%，0n， m z屮和01， 02，0n，耳2力屮的证明。由归纳假设，得到关系 %，%，enC vm2，%，%，札，mC 屮和1，%， 0n，耳2 C屮成立。这三个关系合起来得到01， 02，0n C屮也成 立。3. 现在你可以猜测讨论的其余部分就是依次检查可能的证明规则， 最终证明自然演绎规则在语义上与真值表求值一致。怎么说明, 4，札 屮不是有效的呢？这相当于要找一个赋 值，使得电的赋值为T而屮的赋值为F。由合理性，这个矢列没有 证明。