工业大学稿第讲.ppt

《工业大学稿第讲.ppt》由会员分享，可在线阅读，更多相关《工业大学稿第讲.ppt（229页珍藏版）》请在三一文库上搜索。

1、电子科技大学离散数学课程组国家精品课程 1 -理学院 离散数学课程组 TJPU-SS Discrete mathematics 离 散 数 学 * 教师：陈雅颂 天津工业大学 理学院 数学系离散数学课程组 2 简介 离散数学(Discrete mathematics)是研究 离散量的结构及其相互关系的数学学科，是现 代数学的一个重要分支。 它在各学科领域，特别在计算机科学与技 术领域有着广泛的应用，同时离散数学也是计 算机专业的许多专业课程，如程序设计语言、 数据结构、操作系统、编译技术、人工智能、 数据库、算法设计与分析、理论计算机科学基 础等必不可少的先行课程。 天津工业大学 理学院 数学

2、系离散数学课程组 3 通过离散数学的学习，不但可以掌握处理 离散结构的描述工具和方法，为后续课程的学 习创造条件，而且可以提高抽象思维和严格的 逻辑推理能力，为将来参与创新性的研究和开 发工作打下坚实的基础。 天津工业大学 理学院 数学系离散数学课程组 4 随着信息时代的到来，工业革命时代以微 积分为代表的连续数学占主流的地位已经发生 了变化，离散数学的重要性逐渐被人们认识。 离散数学课程所传授的思想和方法，广泛地体 现在计算机科学技术及相关专业的诸领域，从 科学计算到信息处理，从理论计算机科学到计 算机应用技术，从计算机软件到计算机硬件， 从人工智能到认知系统，无不与离散数学密切 相关。 天

3、津工业大学 理学院 数学系离散数学课程组 5 由于数字电子计算机是一个离散结构，它 只能处理离散的或离散化了的数量关系， 因此 ，无论计算机科学本身，还是与计算机科学及 其应用密切相关的现代科学研究领域，都面临 着如何对离散结构建立相应的数学模型；又如 何将已用连续数量关系建立起来的数学模型离 散化，从而可由计算机加以处理。 天津工业大学 理学院 数学系离散数学课程组 6 离散数学是传统的逻辑学，集合论（包括函 数），数论基础，算法设计，组合分析，离散 概率，关系理论，图论与树，抽象代数（包括 代数系统，群、环、域等），布尔代数，计算 模型（语言与自动机）等汇集起来的一门综合 学科。离散数学的

4、应用遍及现代科学技术的诸 多领域。 天津工业大学 理学院 数学系离散数学课程组 7 离散数学课程的教学目的，不但作为计算 机科学与技术及相关专业的理论基础及核心主 干课，对后续课程提供必需的理论支持。更重 要的是旨在“通过加强数学推理，组合分析， 离散结构，算法构思与设计，构建模型等方面 专门与反复的研究、训练及应用，培养提高学 生的数学思维能力和对实际问题的求解能力。 ” 天津工业大学 理学院 数学系离散数学课程组 8 请根据下面事实，找出凶手： 1.清洁工或者秘书谋害了经理。 2.如果清洁工谋害了经理，则谋害不会发生在午夜前 。 3.如果秘书的证词是正确的，则谋害发生在午夜前。 4.如果秘

5、书的证词不正确，则午夜时屋里灯光未灭。 5.如果清洁工富裕，则他不会谋害经理。 6.经理有钱且清洁工不富裕。 7.午夜时屋里灯灭了。 天津工业大学 理学院 数学系离散数学课程组 9 解： 令A:清洁工谋害了经理。 B:秘书谋害了经理 。 C:谋害发生在午夜前。 D:秘书的证词 是正确的. E:午夜时屋里灯光灭了。H:清洁工富裕 . G:经理有钱. 命题符号为： 天津工业大学 理学院 数学系离散数学课程组 10 AB,AC,BC,DC,DE,HA E DE D D DC C AC A AB B n 结果是秘书谋害了经理。 天津工业大学 理学院 数学系离散数学课程组 11 n 第一部分 数理逻辑

6、n 第二部分 集合论 n 第五部分 图论 n 第三部分 代数结构 n 第四部分 组合数学（选讲） n 第六部分 初等数论（选讲） 天津工业大学 理学院 数学系离散数学课程组 12 第一部分 数理逻辑 第一章 命题逻辑基本概念 第二章 命题逻辑等值演算 第三章 命题逻辑的推理理论 第四章 一阶（谓词）逻辑基本概念 第五章 一阶（谓词）逻辑等值演算与推理 天津工业大学 理学院 数学系离散数学课程组 13 第二部分 集合论 第六章 集合代数 第七章 二元关系 第八章 函数（选讲） 天津工业大学 理学院 数学系离散数学课程组 14 第五部分 图论 第十四章 图的基本概念 第十五章 欧拉图与哈密顿图 第

7、十六章 树 第十七章 平面图 第十八章 支配集、覆盖集、独立集与匹配与着色 (选讲) 天津工业大学 理学院 数学系离散数学课程组 15 第三部分 代数结构 第九章 代数系统 第十章 群与环 第十一章 格与布尔代数（选讲） 天津工业大学 理学院 数学系离散数学课程组 16 第四部分 组合数学（选讲） n 第十二章 基本组合计数公式 （选讲） n 第十三章 递推方程与生成函数（选讲） 天津工业大学 理学院 数学系离散数学课程组 17 第六部分 初等数论 （选讲） n 第十九章 初等数论 （选讲） 天津工业大学 理学院 数学系离散数学课程组 18 第一部分 数理逻辑 逻辑： 是人的一种抽象思维，是人

8、通过概念、判断 、 推理、论证来理解和区分客观世界的思维过程。 主要分为： 制约逻辑；形式逻辑；演绎逻辑；归纳逻辑。 本篇数理逻辑，是形式逻辑的一部分。 天津工业大学 理学院 数学系离散数学课程组 19 * 数理逻辑（Mathematical Logic） -是研究演绎推理的一门学科，用数学的方 法来研究推理的规律统称为数理逻辑。 第一部分 数理逻辑 天津工业大学 理学院 数学系离散数学课程组 20 n 所谓数学方法就是指数学采用的一般方法 ，包括使用符号和公式，已有的数学成果和方 法，特别是使用形式的公理方法。 n 用数学的方法研究逻辑的系统思想一般追 溯到莱布尼茨，他认为经典的传统逻辑必须

9、改 造和发展，是之更为精确和便于演算。后人基 本是沿着莱布尼茨的思想进行工作的。 天津工业大学 理学院 数学系离散数学课程组 21 n 简而言之，数理逻辑就是精确化、数学化的 形式逻辑。 n 它是现代计算机技术的基础。新的时代将是 数学大发展的时代，而数理逻辑在其中将会起 到很关键的作用。 天津工业大学 理学院 数学系离散数学课程组 22 数理逻辑的产生 n 利用计算的方法来代替人们思维中的逻辑推 理过程，这种想法早在十七世纪就有人提出过 。莱布尼茨就曾经设想过能不能创造一种“通 用的科学语言”，可以把推理过程象数学一样 利用公式来进行计算，从而得出正确的结论。 n 由于当时的社会条件，他的想

10、法并没有实现 。但是它的思想却是现代数理逻辑部分内容的 萌芽，从这个意义上讲，莱布尼茨可以说是数 理逻辑的先驱。 天津工业大学 理学院 数学系离散数学课程组 23 n 1847年，英国数学家布尔发表了逻辑的数学分析， 建立了“布尔代数”，并创造一套符号系统，利用符号 来表示逻辑中的各种概念。布尔建立了一系列的运算法 则，利用代数的方法研究逻辑问题，初步奠定了数理逻 辑的基础。 n 十九世纪末二十世纪初，数理逻辑有了比较大的发 展，1884年，德国数学家弗雷格出版了数论的基础 一书，在书中引入量词的符号，使得数理逻辑的符号系 统更加完备。对建立这门学科做出贡献的，还有美国人 皮尔斯，他也在著作中

11、引入了逻辑符号。从而使现代数 理逻辑最基本的理论基础逐步形成，成为一门独立的学 科。 天津工业大学 理学院 数学系离散数学课程组 24 数理逻辑的发展 n 数理逻辑这门学科建立以后，发展比较迅 速，促进它发展的因素也是多方面的。比如， 非欧几何的建立，促使人们去研究非欧几何和 欧氏几何的无矛盾性。 天津工业大学 理学院 数学系离散数学课程组 25 n 集合论的产生是近代数学发展的重大事件 ，但是在集合论的研究过程中，出现了一次称 作数学史上的第三次大危机。这次危机是由于 发现了集合论的悖论引起。什么是悖论呢？悖 论就是逻辑矛盾。集合论本来是论证很严格的 一个分支，被公认为是数学的基础。 天津工

12、业大学 理学院 数学系离散数学课程组 26 n 1903年，英国唯心主义哲学家、逻辑学家 、数学家罗素却对集合论提出了以他名字命名 的“罗素悖论”，这个悖论的提出几乎动摇了 整个数学基础。 天津工业大学 理学院 数学系离散数学课程组 27 罗素悖论中有许多例子，其中一个很通俗 也很有名的例子就是“理发师悖论”： 某乡村有一位理发师，有一天他宣布：只 给不自己刮胡子的人刮胡子。那么就产生了一 个问题：理发师究竟给不给自己刮胡子？如果 他给自己刮胡子，他就是自己刮胡子的人，按 照他的原则，他又不该给自己刮胡子；如果他 不给自己刮胡子，那么他就是不自己刮胡子的 人，按照他的原则，他又应该给自己刮胡子

13、。 这就产生了矛盾。 天津工业大学 理学院 数学系离散数学课程组 28 n 悖论的提出，促使许多数学家去研究集合论 的无矛盾性问题，从而产生了数理逻辑的一个 重要分支-公理集合论。 天津工业大学 理学院 数学系离散数学课程组 29 n 数理逻辑新近还发展了许多新的分支，如 递归论、模型论等。递归论主要研究可计算性 的理论，它和计算机的发展和应用有密切的关 系。模型论主要是研究形式系统和数学模型之 间的关系。 天津工业大学 理学院 数学系离散数学课程组 30 n 数理逻辑近年来发展特别迅速，主要原因是 这门学科对于数学其它分支如集合论、数论、代 数、拓扑学等的发展有重大的影响，特别是对新 近形成

14、的计算机科学的发展起了推动作用。反 过来，其他学科的发展也推动了数理逻辑的发展 。 天津工业大学 理学院 数学系离散数学课程组 31 数理逻辑论的体系 n 数理逻辑的主要分支包括：逻辑演算(包括 命题演算和谓词演算)、模型论、证明论、递归 论和公理化集合论。 n 数理逻辑和计算机科学有许多重合之处， 这是因为许多计算机科学的先驱者既是数学家 、又是逻辑学家，如阿兰图灵、邱奇等。 简介：阿兰麦席森图灵，1912年生于英国伦敦，1954年死于英国的曼彻斯特，他是计算机 逻辑的奠基者，许多人工智能的重要方法也源自于这位伟大的科学家。他对计算机的重要贡献 在于他提出的有限状态自动机也就是图灵机的概念，

15、对于人工智能，它提出了重要的衡量标准 “图灵测试”，如果有机器能够通过图灵测试，那他就是一个完全意义上的智能机，和人没有 区别了。 阿隆佐邱奇（1903年6月14日1995年8月11日）是美国数学家，1936年发表可计算函 数的第一份精确定义，对算法理论的系统发展做出巨大贡献。邱奇在普林斯顿受教并工作四十 年，曾任数学与哲学教授。1967年迁往加利福尼亚大学洛杉矶分校。 天津工业大学 理学院 数学系离散数学课程组 32 n 程序语言学、语义学的研究从模型论衍生 而来，而程序验证则从模型论的模型检测衍生 而来。 天津工业大学 理学院 数学系离散数学课程组 33 数理逻辑的内容 n 数理逻辑包括哪

16、些内容呢？这里我们先介绍 它的两个最基本的也是最重要的组成部分，就 是“命题演算”和“谓词演算（在本教材中也 称作一阶逻辑演算）”。 天津工业大学 理学院 数学系离散数学课程组 34 学习逻辑学的意义 学习逻辑学的根本意义，是 训 练和提高人们的逻辑思维能力，促进其自觉地运用 逻辑知识，提高学习和工作的质量。 具体来说， 学 习逻辑学的意义主要有： 第一，有助于正确认识事物，从已知进到未知。 第二，有助于准确、严密地表达和论证思想。 第三，有助于揭露谬误，驳斥诡辩。 第四，有助于培养分析理性精神和创新意识。 天津工业大学 理学院 数学系离散数学课程组 35 * 主要研究内容：推理 着重于推理过

17、程是否正确 着重于语句之间的关系 主要研究方法：数学的方法 就是引进一套符号体系的方法，所以数 理逻辑又叫符号逻辑（Symbolic Logic）。 天津工业大学 理学院 数学系离散数学课程组 36 * 什么是数理逻辑 ？ 用数学的方法来研究推理的规律统称为数理逻辑 。 为什么要研究数理逻辑？ 程序算法数据 算法逻辑控制 小结 天津工业大学 理学院 数学系离散数学课程组 37 * 命题逻辑 命题逻辑基本概念 命题逻辑等值演算 命题逻辑推理理论 主要研 究内容 一阶逻辑 （谓词逻辑） 一阶逻辑基本概念 一阶逻辑等值演算 一阶逻辑推理理论 天津工业大学 理学院 数学系离散数学课程组 38 * 第一

18、章 命题逻辑的基本概念 命题逻辑也称命题演算，或语句逻辑。 研究内容： （1）研究以命题为基本单位构成的前提和结 论之间的可推导关系 （2）研究什么是命题？ （3）研究如何表示命题？ （4）研究如何由一组前提推导一些结论？ 天津工业大学 理学院 数学系离散数学课程组 39 * 第一章 命题逻辑的基本概念 命题逻辑的特征： 在研究逻辑的形式时，我们把一个命题只 分析到其中所含的命题成份为止，不再分析下 去。 不把一个简单命题再分析为非命题的集合， 不把谓词和量词等非命题成份分析出来。 天津工业大学 理学院 数学系离散数学课程组 40 * 1.0 本章学习要求 深刻理解:命题、联结词、复合命题、命

19、题公式、 等值（等价）式、等值（等价）演算、推理及证明等 概念。 熟练进行:等值（等价）演算与构造证明。 天津工业大学 理学院 数学系离散数学课程组 41 * 1.1.1 命题 定义1.1.0 具有非真即假的陈述句称为命题, 该命题可以取一个“值”，称为真值。 真值只有“真”和“假”两种， 分别用“1”(或“T”)和“0”(或“F”)表示 。 1.1 命题与命题联结词 天津工业大学 理学院 数学系离散数学课程组 42 * （1）太阳是圆的； （2）成都是一个旅游城市； （3）北京是中国的首都； （4）这个语句是假的； （5）1110； （6）+y； （7）我喜欢踢足球； （8）3能被2整除；

20、（9）地球外的星球上也有人； （10）中国是世界上人口最多的国家； （11）今天是晴天； 例1.1.1 T T T/F 非命题 T/F F T/F T T T 非命题 天津工业大学 理学院 数学系离散数学课程组 43 * 例1.1.1（续） （12）把门关上； （13）你快上学去！ （14）你要出去吗？ （15）今天天气真好啊！ 非命题 非命题 非命题 非命题 注意： 一切没有判断内容的句子都不能作为命题，如命令 句、感叹句、疑问句、祈使句、二义性的陈述句等 。 天津工业大学 理学院 数学系离散数学课程组 44 * 命题一定是陈述句，但并非一切陈述句都是命题。 命题的真值有时可明确给出，有时还

21、需要依靠环境 、条件、实际情况、时间才能确定其真值。 结论： 在数理逻辑中像字母“x”、“y”、“z”等字 母总是 表示变量。 约定： 天津工业大学 理学院 数学系离散数学课程组 45 * 下列语句是否是命题？并判断其真值结果？ （1）四川不是一个国家； （2）3既是素数又是奇数； （3）张谦是大学生或是运动员； （4）如果周末天气晴朗，则我们将到郊外旅游； （5）2+24当且仅当雪是白的。 例1.1.2 天津工业大学 理学院 数学系离散数学课程组 46 * 一般来说，命题可分两种类型： 1)原子命题(简单命题)：不能再分解为更为简单 命题的命题。 2)复合命题：可以分解为更为简单命题的命题。

22、 而且这些简单命题之间是通过如“或者”、“ 并且”、“不”、“如果.则.”、“当且 仅当”等这样的关联词和标点符号复合而构成 一个复合命题。 命题的分类 天津工业大学 理学院 数学系离散数学课程组 47 * 1)今天天气很冷。 2)今天天气很冷并且刮风。 3)今天天气很冷并且刮风，但室内暖和。 例1.1.3 通常用大写（或小写的）的带或不带下标的英文字 母、.P、Q、R、. Ai、Bi 、Ci、 .Pi、Qi、Ri、.等表示命题 天津工业大学 理学院 数学系离散数学课程组 48 * 定义：1.1.1 命题联结词 设命题P,Q表示任意两个命题,则最常见的命题联结词有： 联接词记号 复合命题读法

23、记法真值结果 3.析取 P或者QP与Q的析取PQPQ1P1 或Q1 2.合取 P并且Q P与Q的合取 PQ PQ1P1且 Q1 1.否定 非PP的否定 PP1 P0 4.蕴涵若P,则Q P蕴涵Q PQ PQ0 P1,Q0 5.等价 P当且仅当QP等价于QPQ PQ1P1,Q1或P0,Q0 天津工业大学 理学院 数学系离散数学课程组 49 * 总结 P Q P PQPQPQ PQ 0 010011 0 110110 1 000100 1 101111 天津工业大学 理学院 数学系离散数学课程组 50 * 说明 1、联结词是句子与句子之间的联结，而非单纯 的名词、形容词、数词等地联结； 2、联结词

24、是两个句子真值之间的联结，而非句 子的具体含义的联结，两个句子之间可以无任 何地内在联系； 天津工业大学 理学院 数学系离散数学课程组 51 * 说明 3、联结词与自然语言之间的对应并非一一对应； 联结词自然语言 既又、不仅而且、虽然但是 、并且、和、与，等等； PQ若P则Q、只要P就Q、P仅当Q、只有Q才P 、除非Q否则P，等等 等价、当且仅当、充分必要、等等； 相容（可兼）的或 天津工业大学 理学院 数学系离散数学课程组 52 1.否定式与否定联结词“” 记作p，符号称作否定联结词，并规定 p 为真当且仅当p为假. 2.合取式与合取联结词“” 使用合取联结词时要注意两点： (1) 描述合取

25、式的灵活性与多样性 (2) 分清简单命题与复合命题 天津工业大学 理学院 数学系离散数学课程组 53 例 将下列命题符号化. n 吴颖既用功又聪明. n 吴颖不仅用功而且聪明. n 吴颖虽然聪明，但不用功. n 张辉与王丽都是三好生. n 张辉与王丽是同学. （1）（3）说明描述合取式的灵活性与多样性 （4）（5）要求分清联结词“与”，联结的复 合命 题与简单命题将各命题符号化 天津工业大学 理学院 数学系离散数学课程组 54 3. 析取式与析取联结词“” 记作pq，称作析取联结词，并规定pq 为假当且仅当p与q同时为假. 注意： 此“或”，称作相容或，也称可兼或。 还有一种“或”，称作排斥或

26、，也称作不可兼或 。 天津工业大学 理学院 数学系离散数学课程组 55 例 将下列命题符号化 （1）2或4是素数. （2）2或3是素数. （3）4或6是素数. （4）小元元只能拿一个苹果或一个梨. （5）王小红生于1975年或1976年. n （1）（3）为相容或 n （4）（5）为排斥或 天津工业大学 理学院 数学系离散数学课程组 56 n 4. 蕴涵式与蕴涵联结词“” 定义1.4 设p, q为二命题，复合命题“如果p, 则q”称作p与q的蕴涵式，记作pq，并称p是 蕴涵式的前件，q为蕴涵式的后件，称作蕴涵 联结词，并规定，pq为假当且仅当p为真q为 假. 天津工业大学 理学院 数学系离散数

27、学课程组 57 说明： （1）pq的逻辑关系：q为p的必要条件 （2）“如果p, 则q的不同表述法很多： n 若p，就q； n 只要p，就q； n p仅当q； n 只有q，才p； n 除非q， 才p； n 除非q，否则非p， 天津工业大学 理学院 数学系离散数学课程组 58 （3）当p为假时，pq为真，可称为空证明 （4) 常出现的错误：不分充分与必要条件 天津工业大学 理学院 数学系离散数学课程组 59 例 设p：天冷，q：小王穿羽绒服，将下列命题 符 号化 （1）只要天冷，小王就穿羽绒服. （2）因为天冷，所以小王穿羽绒服. （3）若小王不穿羽绒服，则天不冷. （4）只有天冷，小王才穿羽绒

28、服. （5）除非天冷，小王才穿羽绒服. （6）除非小王穿羽绒服，否则天不冷. （7）如果天不冷，则小王不穿羽绒服. （8）小王穿羽绒服仅当天冷的时候. 天津工业大学 理学院 数学系离散数学课程组 60 n 注意： pq与qp等值（真值相同） （1），（2），（3），（6）符号化为pq 其余的符号化为qp 思考，为什么？ 天津工业大学 理学院 数学系离散数学课程组 61 n 5. 等价式与等价联结词“” 定义1.5 设p，q为二命题，复合命题“p当且仅当 q”称作p与q的等价式，记作pq，称作等价 联结词. 并规定为真当且仅当p与q同时为真 或同时为假. （1）pq的逻辑关系：p与q互为充分必要

29、条件 （2）pq为真当且仅当p与q同真或同假 天津工业大学 理学院 数学系离散数学课程组 62 例 符号化，并求下列复合命题的真值 （1）2 + 2 4当且仅当3 + 3 6. （2）2 + 2 4当且仅当3 是偶数. （3）2 + 2 4当且仅当太阳从东方升起. （4）2 + 2 4当且仅当美国位于非洲. （5）函数f(x)在x0 可导的充要条件是它在x0连 续. n 它们的真值是显而易见的. 天津工业大学 理学院 数学系离散数学课程组 63 什么是必要条件，充分条件，充分必要条件。 必要： PQ 字面理解很容易，没它不行的意思。用你的 题目，P要成立，Q必须要成立，可能还需要其他 的 条件

30、，P才能成立，但是没有Q，P肯定是不成立。 比如，人活着，喝水这两件事，喝水就是人活着 的 必要条件，没水不行活不了，有水也不一定能活 着 （必要条件强调必须要有，没有不成立，至于有 了以后的事情就不关心了）。 人活着要喝水 天津工业大学 理学院 数学系离散数学课程组 64 充分： PQ P是Q的充分条件，字面去理解（有它就行） ， 有P就一定会有Q发生。联想： 人活着要喝水 天津工业大学 理学院 数学系离散数学课程组 65 首先，对以下三个词的释意要有所明确:(摘自 金 山词霸)。 只要：表示具有充分的条件,正句常用“就”、“ 也” 、“都”、“便”相呼应,表明由这种条件产生的 一种 结果。

31、 只有：表示必需的条件,下文常用“才”、“方” 呼 应。 除非：表示唯一的条件,常跟“才”、“否则”、 “不 然”等合用,相当于“只有”。 继续解释： 天津工业大学 理学院 数学系离散数学课程组 66 n 由于“只要”表充分条件（即前件），相当于 “如果”，根据定义： “只要p就q”的数理逻辑表示是p-q，而“ 只有”表必要条件（即后件），根据命题逻辑 中相关的证明（如形式系统N）: p-q等价于!q-!p（!表联结词非），你也可 以通过真值表进行验证。 从而，“只有q才p” 的表示是： p-q 天津工业大学 理学院 数学系离散数学课程组 67 n 根据“除非”与“只有”的等价性即“除非q，

32、否则p”等价于“只有q,才p”。 再根据“除非”与“如果不”、“否则” 与否“则”的等价性（unlessif not），“ 除非q，否则p”即可表为!q!p，那么，“只 有q，才p”也可以表示为!q!p，这就证明了 “只要p就q”和“只有q才p”的等价性。 至于“p仅当q”它是“只有q才p”的另一 种表述，自然也等价了。 天津工业大学 理学院 数学系离散数学课程组 68 符号化： A：下雨，B：骑车上班。 1、只有不下雨，我才骑自行车上班。 B-A 2、如果下雨，我就不骑自行车上班。 A-B 3、除非下雨，否则我骑自行车上班。 B-A 天津工业大学 理学院 数学系离散数学课程组 69 * 符号

33、化下列命题 （1）四川不是人口最多的省份； （2）王超是一个德智体全面发展的好学生； （3）教室的灯不亮可能是灯管坏了或者是停电了 ； （4）如果周末天气晴朗，那么学院将组织我们到 石像湖春游； （5）两个三角形全等当且仅当三角形的三条边全 部相等。 例1.1.4 天津工业大学 理学院 数学系离散数学课程组 70 * 例1.1.4 解 （1）设：四川是人口最多的省份。 则命题（1）可表示为。 （2）设：王超是一个思想品德好的学生； ：王超是一个学习成绩好的学生； R：王超是一个体育成绩好的学生。 则命题（2）可表示为R。 （3）设：教室的灯不亮可能是灯管坏了 ：教室的灯不亮可能是停电了 则命题

34、（3）可表示为。 天津工业大学 理学院 数学系离散数学课程组 71 * （4）设：周末天气晴朗； ：学院将组织我们到石像湖春游。 则命题（4）可表示为。 （5）设：两个三角形全等； ：三角形的三条边全部相等。 则命题（5）可表示为。 例1.1.4 解(续) 天津工业大学 理学院 数学系离散数学课程组 72 * 为了不使句子产生混淆，作如下约定，命题联 结词之优先级如下： 1. 否定合取析取蕴涵等价 2. 同级的联结词，按其出现的先后次序(从左 到右) 3. 若运算要求与优先次序不一致时，可使用 括号；同级符号相邻时，也可使用括号。 括号中的运算为最优先级。 约 定 天津工业大学 理学院 数学系

35、离散数学课程组 73 * 设命题P：明天上午七点下雨； Q：明天上午七点下雪； R：我将去学校。 符号化下述语句： 1)如果明天上午七点不是雨夹雪，则我将去学校 2)如果明天上午七点不下雨并且不下雪，则我将去 学校 3)如果明天上午七点下雨或下雪，则我将不去学校 4)明天上午我将雨雪无阻一定去学校 可符号化为： (PQR)(PQR) (PQR)(PQR)。 或 (PQ)(PQ)(PQ) (PQ)R。 例1.1.5 可符号化为：(PQ)R。 可符号化为:(PQ)R。 可符号化为:(PQ)R。 天津工业大学 理学院 数学系离散数学课程组 74 * 例1.1.6 设命题P：你陪伴我； Q：你代我叫车

36、子； R：我将出去。 符号化下述语句： 除非你陪伴我或代我叫车子，否则我将不出去 如果你陪伴我并且代我叫辆车子，则我将出去 如果你不陪伴我或不代我叫辆车子，我将不出去 R(PQ) 或 (PQ)R (PQ)R (PQ)R 天津工业大学 理学院 数学系离散数学课程组 75 * 例 设P:雪是白色的;Q:2+24。将下列命题符号化 ： （1）因为雪是白色的，所以2+24； （2）如果2+24，则雪是白色的； （3）只有雪是白色的，才有2+24； （4）只有2+24，雪才是白色的； （5）只要雪不是白色的，就有2+24； （6）除非雪是白色的，否则2+24； （7）雪是白色的当且仅当2+24； 天津工

37、业大学 理学院 数学系离散数学课程组 76 * 例 设P:雪是白色的;Q:2+24。将下列命题符号化 ： （1）因为雪是白色的，所以2+24； PQ （2）如果2+24，则雪是白色的； QP （3）只有雪是白色的，才有2+24； QP （4）只有2+24，雪才是白色的； PQ （5）只要雪不是白色的，就有2+24； PQ （6）除非雪是白色的，否则2+24； P Q或QP （7）雪是白色的当且仅当2+24； P Q 天津工业大学 理学院 数学系离散数学课程组 77 * 1.1.4 命题联结词的应用 例 1.2.7 用复合命题表示如下图所示的开关 电路： 图1.2.1 图1.2.2 图1.2.3

38、 ABAB A 设：开关闭合；：开关闭合。 天津工业大学 理学院 数学系离散数学课程组 78 第一节 小 结 1.本小节中p, q, r, A,B,C,均表示命题. 2.联结词集为, , , , ，每个联结词 联结的p, pq, pq, pq, pq为基本复合 命题. 其中pq最难理解，要特别注意. 反复 使用, , , , 中的联结词组成更为 复杂的复合命题. 3. 设p: 是无理数， q: 3是奇数， r: 苹果是方的， s: 太阳绕地球转 则复合命题(pq) (rs) p)是假命题 . 4.联结词的运算顺序：, , , , , 同级 按先出现者先运算. 天津工业大学 理学院 数学系离散数

39、学课程组 79 练习： n 课本 P12-14 n 114题 天津工业大学 理学院 数学系离散数学课程组 80 * 第一章 第二节 命题公式及其赋值 定义1.2.0 一个特定的命题是一个命题常项，它不是具有 值“T”(“1”)，就是具有值“F”(“0”)。 而一个任意的没有赋予具体内容的原子命题是一个变量命题 ，常称它为命题变项(或命题变元)，该命题变量无具体的真值 ，它的变域是集合T，F(或0，1) 注意 (1)常项与变项均用p, q, r, , pi, qi, ri, , 等表示 . (2) 复合命题为命题变元的“函数”,其函数值仍为“真“或 “假”值。 (3)真值函数或命题公式，没有确切

40、真值。 真值函数 天津工业大学 理学院 数学系离散数学课程组 81 * 1.2.1命题公式 定义1.2.1 (命题公式/合式公式) 1.命题变元本身是一个公式； 2.如G是公式，则(G)也是公式； 3.如G，H是公式，则(GH)、(GH)、(GH)、 (GH)也是公式； 4. 有限次地应用（1）-（3）形成的符号串是公式 。 天津工业大学 理学院 数学系离散数学课程组 82 * 符号串：(P(QR)(Q(SR)； (PQ)； (P(PQ)； (PQ)(RQ)(PR)。 等都是命题公式。 例1.2.1 例1.2.2符号串： (PQ)Q)； (PQ； (PQ(R； PQ。 等都不是合法的命题公式。

41、 天津工业大学 理学院 数学系离散数学课程组 83 * 例1.2.3 试用符号形式写出下列命题： （1）虽然今天天气晴朗，老陈还是不来； （2）除非你陪伴我或代我叫车子，否则我将不出去 ； （3）停机的原因在于语法错误或者程序错误； （4）若a和b是偶数，则a+b是偶数； （5）我们要做到身体好、学习好、工作好，为祖国 四化建设而奋斗。 天津工业大学 理学院 数学系离散数学课程组 84 * 例1.2.3 解 （1）P：今天天气晴朗,Q：老陈要来,则有：PQ； （2）P：你陪伴我； Q：你代我叫车子；R：我出去 。则有：RPQ或PQR； （3）P：停机的原因在于语法错误，Q：停机的原因 在于程序

42、错误，则有：PQ； （4）P：a是偶数；Q：b是偶数，R：a+b是偶数，则 有：PQR； （5）P：我们要做到身体好,Q：我们要做到学习好, R：我们要做到工作好，S：我们要为祖国四化建设而 奋斗，则有：PQR S。 天津工业大学 理学院 数学系离散数学课程组 85 * 公式(P(QR)(Q(SR)可表示 如下： (P(QR)(Q(SR) P(QR) Q(SR) P QR Q SR Q R S R S 例1.2.4 天津工业大学 理学院 数学系离散数学课程组 86 注意： 几点说明： 归纳或递归定义 元语言与对象语言 外层括号可以省去 天津工业大学 理学院 数学系离散数学课程组 87 n 定义

43、1.2.2：合式公式的层次 （1）若公式A是单个的命题变项，则称A为0层合式. （2）称A是n+1(n0)层公式是指下面情况之一： (a) A=B, B是n层公式； (b) A=BC, 其中B,C分别为i层和j层公式，且 n=max(i,j)； (c) A=BC, 其中B,C的层次及n同(b)； (d) A=BC, 其中B,C的层次及n同(b)； (e) A=BC, 其中B,C的层次及n同(b). （3）若公式A的层次为k, 则称A为k层公式. 天津工业大学 理学院 数学系离散数学课程组 88 n 例如： 公式A=p, B=p, C=pq, D=(pq)r, E=(pq) r) (rs) 分别

44、为0层，1层，2层，3层，4层公式. 天津工业大学 理学院 数学系离散数学课程组 89 * 1.2.2 公式的解释与真值表 定义1.2.3 设P1、P2、Pn是出现在公式G中的所 有命题变元，指定P1、P2、Pn一组真值，则这组 真值称为G的一个赋值或解释,常记为。 一般来说，若有个命题变元，则应有2n个不 同的解释。 如果公式G在解释下是真的，则称成真赋值 ；如果G在解释下是假的，则称成假赋值。 天津工业大学 理学院 数学系离散数学课程组 90 定义1.2.4 将公式G在其所有可能解释下的真值情 况列成的表，称为G的真值表。 天津工业大学 理学院 数学系离散数学课程组 91 易知 000,

45、010, 101, 110是 (pq)r的成真赋值， 而001, 011, 100, 111是成假赋值. 天津工业大学 理学院 数学系离散数学课程组 92 构造真值表的方法： n 见P9,定义1.9 1）找出所含全部命题变元，从000开始，直到 111为止，进行赋值。 2）从低到高顺序写出公式的各个层次。 3）对应各个赋值，计算各层次的真值。 注意： 公式A与公式B最后一列相同，称两公式的真值表 相 同。 天津工业大学 理学院 数学系离散数学课程组 93 * 例1.2.5 求下面公式的真值表： (P(PQ)R)Q 其中，、是的所有命题变元。 P Q R PPQ(PQ)RP(PQ)R)G 0 0

46、 0 10 0 11 0 0 1 10 0 11 0 1 0 1 1 0 1 1 0 1 1 1 1 1 11 1 0 0 0 1 0 00 1 0 1 0 1 1 11 1 1 0 0 0 0 01 1 1 1 0 0 0 01 天津工业大学 理学院 数学系离散数学课程组 94 * 例1.2.5（续） P Q R(P(PQ)R) Q 0 0 01 0 0 11 0 1 01 0 1 11 1 0 00 1 0 11 1 1 01 1 1 1 1 进一步化简为： 天津工业大学 理学院 数学系离散数学课程组 95 * 例1.2.6 P Q () () () ( Q) 0 0 1 00 0 1 1

47、 00 1 01 00 1 11 10 求下面这组公式的真值表： 1 ()； 2()； 3 () (Q)。 天津工业大学 理学院 数学系离散数学课程组 96 * 从这三个真值表可以看到一个非常有趣的事实 ： 公式G1对所有可能的解释具有“真”值 公式G3对所有可能的解释均具有“假”值 公式G2则具有“真”和“假”值 结论 天津工业大学 理学院 数学系离散数学课程组 97 * 定义1.2.5 1.公式G称为永真公式(重言式)，如果在它的所有 解释之下都为“真”。 2.公式G称为永假公式(矛盾式),如果在它的所有 解释之下都为“假”。 3.公式G称为可满足的，如果它不是永假的。 天津工业大学 理学院 数学系离散数学课程组 98 * 从上述定义可知三种特殊公式之间的关系： 1) 永真式G的否定G是矛盾式；矛盾式G的否定G是 永真式。 2) 永真式一定是可满足式,可满足式不一定是永真式 3) 可满足式的否定