大家好！

离散数学自学笔记第一章

来源:河南自考网加入时间：[2019-07-25 15:54] 点击数：

　　第一篇数理逻辑

　　第一章命题演算及其形式系统

　　在我国，逻辑学（logic）旧称“名学”，也称为“论理学”，是研究人类推理过程的科学，而数理逻辑（mathematical logic）则是用数学的方法来进行这一研究的一个数学学科，其显著特征是符号化和形式化，即把逻辑所涉及的“概念、判断、推理”用符号来表示，用公理体系来刻划，并基于符号串形式的演算来描述推理过程的一般规律。因此数理逻辑又称符号逻辑、现代逻辑。

　　虽然在17世纪莱布尼兹（Leibniz）已经提出仿数学的方法发展逻辑的思想，但由于社会条件等原因，近半个多世纪才开始得以迅速发展。1930年，Godel完全性定理的证明完善了数理逻辑基础，建立了逻辑演算，并在此基础上发展出公理集合论、证明论、模型论和递归论四个分支，成为现代科学特别是计算机科学不可缺少的基础理论之一。

　　在传统的形式逻辑中，先讨论概念，后讨论判断（即命题），再讨论推理，这是因为概念组成判断，判断又组成推理。但是，这未必是一种好的次序安排。事实上，如果我们把推理作为研究的根本目标，先忽略判断的细节——概念，把判断看作不可分的整体——命题来讨论，也就是以命题演算入手，那么更便于对推理规律进行分析；而在此基础上，再引入概念的形式表示——谓词，讨论概念、关系的理论——谓词演算，把推理的研究引向更加深刻的层次，其内容编排就显得格外顺理成章。本章的阐述正是遵循这一次序，先讨论命题、命题演算及其形式系统。

　　1.1 命题与联结词

　　1.1.1 命题

　　我们把对确定的对象作出判断的陈述句称作命题（propositions），当判断正确或符合客观实际时，称该命题真（true），否则称该命题假（false）。“真、假”常被称为命题的真值。古典逻辑认为，命题或真或假，但不兼而有之（我们也作此约定），这就是逻辑学的一个基本假设——排中律。非经典逻辑，如直觉主义逻辑、多值逻辑不接受排中律，本书不作讨论。我们确认排中律。

　　例1.1 考虑下列语句：

　　（1）雪是白的。

　　（2）2+2=5

　　（3）2是偶数且3也是偶数。

　　（4）陈胜吴广起义那天杭州下雨。

　　（5）第28届奥林匹克运动会开幕时北京天晴。

　　（6）大于2的偶数均可分解为两个质数的和（哥德巴赫猜想）。

　　（7）真舒服啊！

　　（8）您去学校吗？

　　（9）x+y <0

　　（10）我说的这句话（例1.1之（10））假。

　　显然（1），（2），（3）都是命题，（1）为真命题，（2），（3）为假命题。事实上（4），（5），（6）也是命题，虽然它们的真值未必在现在或将来可以得知，但它们所作判断是否符合客观实际这一点是确定的。

　　（7），（8）不是陈述句，因此它们都不是命题。（9）也不是命题，因为通常 x，y表示变元，它们不是确定的对象，从（9）没有确定的真值。只有当x，y取得确定的值时，（9）才成为命题，才有相应的真值。

　　（10）不是命题，因为它是一个悖论，即一种病态的语句，我们不承认此类语句为陈述句。由于（10）对本身的真假作了否定的判断，从而使对（10）真值的判定变得没有意义了。当判定（10）真时，（10）对本身的判断成立，即（10）假；当判定（10）假时，（10）对本身的判断则不成立，即（10）真。

　　我们注意到，命题（1）—（6）中的（3）与其它命题不同，（3）实际上是由两个命题与一个联结词“且”所组成的。命题（3）的真值不仅依赖于这两个组成它的命题，而且还依赖于这个联结词的意义。像这样的联结词称为逻辑联结词（logical connectives）。通常把不含有逻辑联结词的命题称为原子命题或原子（atoms），而把由原子命题和逻辑联结词共同组成的命题称为复合命题（compositive propositions）。

　　例1.2 下列命题都是复合命题，其中楷体字为逻辑联结词：

　　（1）雪不是白的（并非雪是白的）

　　（2）今晚我看书或者去看电影。

　　（3）你去了学校，我去了工厂（省略了逻辑联结词“且”）。

　　（4）如果天气好，那么我去接你。

　　（5）偶数a是质数，当且仅当a=2（a是常数）。

　　在形式化表示中，原子命题通常记为p，q，r，s等小写拉丁字母。f表示恒假命题，t表示恒真命题。

在线报名，立刻定制专属提升方案。