您的位置:自考365 > 复习指导 > 笔记串讲 > 理学 > 离散数学自学笔记第一章

离散数学自学笔记第一章

2006-09-15 16:06   【 】【我要纠错

  第一篇 数理逻辑

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

  在我国,逻辑学(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表示恒真命题。

本文转载链接:离散数学自学笔记第一章

分享到:
  • 站内搜索
  • 课程搜索
  • 试题搜索

热门搜索:教材 报名 查分 免考 考试计划