屈婉玲 耿素云 张立昂1前前 言言离散数学是研究离散数量关系和离散结构数学模型的数 学分支的统称.是计算机科学与技术专业的核心基础课程.“离散”和“连续”之间的对立与统一是数学发展的重要动 力之一.古代数学主要讨论整数等离散与离散化了的数量关 系，因而，那时数学被看成是研究上述数量关系的科学.但随着数学理论的发展，处理离散数量关系的数学工具在刻 画和处理某类事务方面显得无能为力，因此出现了处理连 续数量关系的数学工具：微积分.2近代数学主要以研究连续数量关系及其数学结构、数学模型，并取得了极其辉煌的成果，这一特征一直延 续至今，仍在现代数学中占据支配地位（人们现在仍 在学习微积分等经典数学理论）.3然而，近半个世纪以来，计算机的飞速发展与广泛应用，极大地冲击了现代数学.由于计算机是一个离散结构，它只能处理离散或离散化了的数量关系，因此，无论是计算机科学本身，还是与计算机科学极其应用密切相关的现代科学领域，都面临如何更有效地处理离散的对象和离散的数量关系，如何对离散结构建立数学模型以及如何将已用连续数量关系建立起来的 数学模型离散化，从而可由计算机来加以处理.4计算机科学以研究计算领域中的一些普遍规律为其基本任务，在此过程中，涉及和应用了很多现代数学，所以 需要以近代数学作为工具.离散数学的内容一直随着计算 机科学的发展而不断得到扩充与更新.同时，离散数学也 促进了计算机技术和计算机科学的发展.在计算机发展初期，人们利用布尔代数理论研究开关电路，建立了一套 完整的数理逻辑理论，对计算机逻辑设计起了很大作用.于是，人们开始从新认识离散数量关系的研究意义，重 新重视讨论离散数量关系的数学分枝，并取得新的发展.5此外，在计算机科学中普遍采用离散数学中的基本概念、基本思想和方法.例如，集合论的概念和方法，抽象代数的概念和方法等，在计算机科学的各个领域随处都 能碰到.所有这些都使得离散数学在计算机科学中的地位和作用越来越重要，成了必不可少的工具.因此有人把离散数学称为“计算机数学”.6离散数学的内容涵盖很广，到目前为止，它包括的主要内容有：集合论、数理逻辑、抽象代数、图论、自动 机理论等.它们广泛应用于计算机科学的研究中，也大量 应用于数据结构、操作系统、数据库理论等后续课程中.在物理、化学、生物等自然科学以及经济、教育等社会 科学中，也正在获得广泛应用，有人预计，未来社会将 有越来越多的人学习离散数学，就像当今人们学习微积 分一样.7第一部分 数理逻辑 第一章 命题逻辑的基本概念 第二章 命题逻辑等值演算 第三章 命题逻辑的推理理论 第四章 一阶逻辑基本概念第五章 一阶逻辑等值演算与推理第二部分 集合论第六章 集合代数第七章 二元关系 第八章 函 数第三部分 代数结构 第九章 代数系统 第十章 群 与 环 第十一章 格与布尔代数第四部分 图论 第十四章 图的基本概念第十五章 欧拉图与哈密顿图第十六章 树第十七章 平面图第十八章 二分图主要内容8主要内容 l 命题逻辑基本概念 l 命题逻辑等值演算 l 命题逻辑推理理论 l 一阶逻辑基本概念 l 一阶逻辑等值演算与推理第一部分 数理逻辑9数理逻辑数理逻辑是用数学的方法来研究人类推理过程的一门数学 学科.其显著特征是符号化和形式化，即把逻辑所涉及的“ 概念、判断、推理”用符号来表示，用公理体系来刻划, 并基于符号串形式的演算来描述推理过程的一般规律. 又称符号逻辑、现代逻辑. 10第一章 命题逻辑的基本概念主要内容l 命题与联结词命题及其分类联结词与复合命题l 命题公式及其赋值11命题与真值命题：判断结果唯一的陈述句命题的真值：判断的结果真值的取值：真与假真命题与假命题注意： 感叹句、祈使句、疑问句都不是命题 陈述句中的悖论，判断结果不唯一确定的不是命 题1.1 命题与联结词12例1 下列句子中那些是命题 ？(1) 是有理数.(2) 2 + 5 = 7.(3) x + 5 3.(4) 你去教室吗？(5) 这个苹果真大呀！(6) 请不要讲话！(7) 2050年元旦下大雪. (8) 我说的这句话假.假命题命题概念真命题不是命题 不是命题 不是命题不是命题 命题，但真值现在不知道 不是命题（悖论 ）13命题分类：简单命题（也称原子命题）与复合 命题简单命题符号化 l用小写英文字母 p, q, r, , pi, qi, ri (i1)表示简 单命题 l用“1”表示真，用“0”表示假例如，令 p： 是有理数，则 p 的真值为0，q：2 + 5 = 7，则 q 的真值为1命题分类14否定、合取、析取联结词定义1.1 设 p为命题，复合命题“非p”(或“p的否定 ”)称为p的否定式，记作p，符号称作否定联 结词. 规定p 为真当且仅当p为假.可用下表来规定否定词“ ”的意义: p p011 015定义1.2 设p,q为两个命题，复合命题“p并且q”(或“p 与 q”)称为p与q的合取式，记作pq，称作合取 联结词. 规定pq为真当且仅当p与q同时为真.可用下表来规定合取词“”的意义：p q p q00110 101000116定义1.3 设p, q为两个命题，复合命题“p或q”称作 p与q的析取式，记作pq，称作析取联结词. 规定pq为假当且仅当p与q同时为假.可用下表来规定析取词“”的意义：p q p q00110101011117例2 将下列命题符号化.(1) 吴颖既用功又聪明.(2) 吴颖不仅用功而且聪明.(3) 吴颖虽然聪明，但不用功.(4) 张辉与王丽都是三好生.(5) 张辉与王丽是同学.合取联结词的实例18解 令p:吴颖用功, q:吴颖聪明(1) pq(2) pq(3) pq(4) 设p:张辉是三好生, q:王丽是三好生pq(5) p:张辉与王丽是同学(1)(3) 说明描述合取式的灵活性与多样性 (4)(5) 要求分清 “与” 所联结的成分合取联结词的实例19例3 将下列命题符号化 (1) 2 或 4 是素数. (2) 2 或 3 是素数. (3) 4 或 6 是素数. (4) 小元元只能拿一个苹果或一个梨. (5) 王小红生于 1975 年或 1976 年.析取联结词的实例20解 (1) 令p:2是素数, q:4是素数, pq (2) 令p:2是素数, q:3是素数, pq (3) 令p:4是素数, q:6是素数, pq (4) 令p:小元元拿一个苹果, q:小元元拿一个梨(pq)(pq) (5) p:王小红生于 1975 年, q:王小红生于1976 年, (pq)(pq) 或 pq (1)(3) 为相容或，即当 p 和 q 均真时，确认 pq为真.在日常生活中，“或”在有的场合下不 同于上述意义. 析取联结词的实例21例如“人固有一死，或重于泰山，或轻于鸿毛”. 其中的“或”是排斥的，即当发现有人的死既重于泰山又轻于鸿毛时，上述论断被认为假. 这里的“或”用表示不合适.可用下表规定的新联结词“排斥或” 表示之. pq P q0 0 1 10 1 0 10 1 1 022(4)(5) 为排斥或,但是，像上述场合一样的许多场合下，两个析取命题事实上不可能同时为真，即上表的 末行根本无需定义，这时用代替就没有问题，并且能使语句的表示简化. 例如“a 0或a=0或a0a=0a0a=0a0”. 符号化时(5)可有两种形式，而(4)则不能23蕴涵联结词定义1.4 设p, q为两个命题，复合命题“如果p, 则q”称 作p与q的蕴涵式，记作pq，并称p是蕴涵式的前件 ，q为蕴涵式的后件，称作蕴涵联结词. 规定：pq 为假当且仅当p为真q为假.可用下表来规定该蕴涵词“ ”的意义：p q p q00110101110124(1) pq 的逻辑关系：q为 p 的必要条件(2) “如果 p, 则 q” 有很多不同的表述方法：若p，就q只要p，就qp仅当q只有q 才p除非q, 才p 或 除非q，否则非p， (3) 当 p 为假时，pq恒为真，称为空证明(4) 常出现的错误：不分充分与必要条件25例4 设 p：天冷，q：小王穿羽绒服，将下列命题符号化 (1) 只要天冷，小王就穿羽绒服. (2) 因为天冷，所以小王穿羽绒服. (3) 若小王不穿羽绒服，则天不冷. (4) 只有天冷，小王才穿羽绒服. (5) 除非天冷，小王才穿羽绒服. (6) 除非小王穿羽绒服，否则天不冷. (7) 如果天不冷，则小王不穿羽绒服. (8) 小王穿羽绒服仅当天冷的时候.蕴涵联结词的实例pq注意： pq 与 qp 等值（真值相同）pq pq qp qppq qp qp26注意: 上述规定的蕴涵词称为实质蕴涵，因为它不要求pq中的p，q有什么关系，只要p，q为命题，pq就有意义. 例如“如果2+2=5，那么雪是黑的”，就是一个有意义的命题，且据定义其真值为“真”.27定义1.5 设 p, q为两个命题，复合命题“p当且仅当 q”称作p与q的等价式，记作pq，称作等价联 结词. 规定pq为真当且仅当p与q同时为真或同 时为假.pq 的逻辑关系：p与q互为充分必要条件等价联结词可用下表来规定该双向蕴涵词“ ”的意义：p q p q00110101100128例5 求下列复合命题的真值(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 连续. 1010029l 本小节中p, q, r, 均表示命题. l 联结词集为, , , , ，p, pq, pq, pq, pq为基本复合命题. 其中要特别注意理解pq的涵义. 反复使用, , , , 中的联结词组成更为复杂的复合命题.设 p: 是无理数，q: 3是奇数， r: 苹果是方的， s: 太阳绕地球转则复合命题 (pq) (rs) p) 是假命题. 小 结l 联结词的运算顺序：, , , , , 同级按先出现者 先运算.301.2 命题公式及其赋值命题变项与合式公式 l 命题变项 l 合式公式 l 合式公式的层次公式的赋值 l 公式赋值 l 真值表31命题变项与合式公式命题常项：表示具体命题及表示常命题的统称 命题常项命题常项命题变项（命题变元）：以“真、假”或“1，0”为取值范 围的变元，它未指出符号所表示的具体命题 . 常项与变项均用 p, q, r, , pi, qi, ri, , 等表示. 定义1.6 合式公式（简称公式）的递归定义：(1) 单个命题变项和命题常项是合式公式, 称作原子命题 公式(2) 若A是合式公式，则 (A)也是(3) 若A, B是合式公式，则(AB), (AB), (AB), (AB) 也是 (4) 只有有限次地应用(1)(3) 形成的符号串才是合式公式约定公式最外层和不影响运算次序的括号可省去.32合式公式的层次定义1.7 (1) 若公式A是单个命题变项，则称A为0层公式. (2) 称 A 是 n+1(n0) 层公式是指下面情况之一