离散数学 Discrete Mathematics

引言 为什么要学习离散数学？     离散数学是现代数学的一个重要分支，它充分描述了计算机科学离散性的特点，是计算机学科的数学基础，是计算机专业必修的专业基础课。     20世纪，计算机学科及其它学科为应用数学提出了越来越多的问题，而几乎所有这些问题都具有离散的性质，亦具有有限结构，在解决和转换这些问题的过程中应用数学的新学科——离散数学诞生和发展了。     什么是离散的性质呢？简单地说，是问题本身具有离散的结构，它们涉及的函数是定义在离散的点而不是连续的点的集合上，即它们涉及离散的量，因而需要离散地求解这些问题。     数字计算机本身就是点量的机器，它仅涉及整数，而离散数学恰好提供点量的模型，于是它成为计算机学科的一个极其有用且容易理解的工具。            

一、内容简介 离散数学主要讲授数理逻辑、集合论、近世代数与图论四个部分。      离散数学是现代数学的一个重要分支，是计算机科学中基础理论的核心课程，是计算机及应用专业的重要基础课程。离散数学与计算机科学中的数据结构、操作系统、编译原理、算法设计与分析、逻辑设计、系统结构、容错诊断、人工智能等课程紧密联系。 离散数学主要讲授数理逻辑、集合论、近世代数与图论四个部分。        

二、本课程的目的和任务       由于离散数学的重要地位，因此通过本课程的教学，使计算机及应用专业的学生能够掌握数理逻辑、集合论、近世代数与图论的基本概念、基本定理、基本方法，并且培养学生具有一定的抽象思维能力和逻辑推理能力。同时为计算机及应用专业的其它重要后续课程（如数据结构、操作系统、编译原理等课程）奠定比较坚实的基础。

三、本课程与其它课程的关系      学生在进入本课程之前，应学习下列课程：          ·高等数学（一元微积分部分）          ·工程数学（线性代数部分）      本课程学习结束后，学生才能进入下列课程学习阶段：          ·数据结构          ·操作系统          ·编译原理      因此，本课程是一门重要的理论基础课，理论性强并且与许多专业基础课有着十分密切的联系，学生应对本门课程产生足够的重视。

 四、本门课的基本要求      1、数理逻辑      熟练掌握命题的连结词及其真值表、恒等式及永真蕴含式，掌握对偶与范式，了解其它连结词，熟练地进行命题逻辑的推理。      掌握谓词的概念及量词，对自然语言与逻辑语言能进行翻译，了解变元的约束，熟练掌握谓词演算的等价式与蕴含式，了解前束范式，熟练掌握谓词的推理理论与推理方法。      2、集合论      了解集合的运算、序偶、笛卡儿乘积，掌握关系及表示，关系的复合与逆关系，熟练掌握关系的性质、关系的闭包运算，了解集合的划分与覆盖，熟练掌握等价关系与等价类，掌握相容关系与序关系。了解映射的概念、逆映射与映射的复合，了解基数的概念、可数集与不可数集、基数的比较。      3、代数系统      了解代数的概念、运算及性质，掌握半群、独异点，掌握群与子群，熟练掌握阿贝尔群与循环群，熟练掌握陪集与拉格朗日定理，熟练掌握同态与同构，了解环与域。      了解格的概念，掌握分配格、有补格，熟练掌握布尔代数，了解布尔表达式。      4、图论      了解图的概念、路与回路，熟练掌握图的矩阵表示，掌握欧拉图与哈密顿图，掌握平面图、对偶图与着色，熟练掌握树与生成树，掌握树根与应用。

第一篇 数理逻辑 现代数理逻辑可分为证明论、模型论、递归函数论、公理化集合论等，这里介绍的是数理逻辑最基本的内容：命题逻辑和谓词逻辑。 第一篇　数理逻辑    逻缉学是一门研究思维形式及思维规律的科学。逻辑规律就是客观事物在人的主观意识中的反映。     逻辑学分为辩证逻缉与形式逻辑两种，前者是以辩证法认识论的世界观为基础的逻辑学，而后者主要是对思维的形式结构和规律进行研究的类似于语法的一门工具性学科。思维的形式结构包括了概念，判断和推理之间的结构和联系，其中概念是思维的基本单位，通过概念对事物是否具有某种属性进行肯定或否定的回答，这就是判断；由一个或几个判断推出另一判断的思维形式，就是推理。研究推理有很多方法，用数学方法来研究推理的规律称为数理逻辑，即通过引入表意符号研究推理，因此，数理逻辑又名符号逻辑。     现代数理逻辑可分为证明论、模型论、递归函数论、公理化集合论等，这里介绍的是数理逻辑最基本的内容：命题逻辑和谓词逻辑。 命题逻辑，也称命题演算，记为Ls。它与谓词逻辑构成数理逻辑的基础，而命题逻辑又是谓词逻辑的基础。           

学习《数理逻辑》这一篇的要求 一、学习目的与要求   一、学习目的与要求 本章目的是介绍命题逻辑的基本概念。掌握利用命题逻辑表示自然语言，描述概念、判断和推理。建立初步的语言形式化方法。

 二、知识点 1．命题的概念、表示方法；联结词的逻辑意义。 2．命题公式的递归定义，自然语言翻译成命题公式 3．真值表的构造、命题公式等价的概念。 4．重言式与蕴涵式的定义、逻辑意义，逻辑等价与逻辑蕴涵的意义和证明方法。常用的逻辑等价公式和逻辑蕴涵公式。

5．命题公式的对偶式、合取范式、析取范式、主合取范式、主析取范式。逻辑小项、逻辑大项。任给公式化为析取范式、任给公式化为主析取范式、任给公式化为合取范式、任给公式化为主合取范式。 6．命题逻辑的推理理论，主要的推理方法：真值表法、直接证明法、间接证明法。常用推理规则：P规则、T规则、CP规则。 7．命题逻辑的应用示例。

 三、要求 1．识记 命题表示方法、真值判断、命题公式的递归定义。 2．领会 联结词真值确定、翻译、命题公式的等价性和蕴涵性证明、任给公式化为析取范式、任给公式化为主析取范式、任给公式化为合取范式、任给公式化为主合取范式。 3．简单应用 命题逻辑推理规则。

第一章 命题逻辑 学时安排（14学时，共7讲） 教 学 内 容 学时 §1—1 命题及其表示法 §1—2 联结词 2     第一章 命题逻辑 学时安排（14学时，共7讲） 教 学 内 容 学时 §1—1 命题及其表示法 §1—2 联结词 2 §1—3 命题公式与翻译 §1—4 真值表与等价公式 §1—5 重言式与蕴含式 §1—6 其它连结词 §1—7 对偶与范式 §1—8 推理理论 4

        第一章 命题逻辑 第1讲 §1—1 命题及其表示法 §1—2 联结词 要求：深刻理解命题、真值、 原子命题 、复合命题 、命题标识符、命题常量、 命题变元、原子变元等概念， 熟练掌握命题的联结词及其真值表。

§1—1 命题及其表示法 一、命题 1、定义 能表达判断的陈述句称作命题（Proposition）。 例：判断下列语句是否为命题: 陈述句：述说一件事情的句子，句末用句号。 祈使句：要求或者希望别人做什么事或者不做什么事时用的句子，句末用句号或感叹号。 疑问句：提出问题的句子，句末用问号。 感叹句：带有浓厚感情的句子，句末用感叹号。 悖：相反。悖论：自相矛盾的陈述。 §1—1 命题及其表示法 一、命题 1、定义 能表达判断的陈述句称作命题（Proposition）。 例：判断下列语句是否为命题: (1)地球外存在智慧生物。 (2)1＋1=10。 (3)逻辑是枯燥无味的。 (4)你今年暑假去旅行吗？（疑问句） (5)克里特岛人说：“克里特岛人都是说谎话者”。（悖论）    

2、真值：命题所表达的判断结果称为命题的真值。真值只有“真”和“假”两种，记作True（真）和False（假），分别用符号T和F表示。 由于命题只有两种真值，所以称这种逻辑为二值逻辑。命题的真值是具有客观性质的，而不是由人的主观决定的。

再看下面的语句中，哪些语句是命题，如果是命题，指出它的真值： （1）能整除2的正整数是偶数。     （1）能整除2的正整数是偶数。  （2）对于每一个正整数n存在一个大于n的素数。   （3）煤是白的。（F）   （4）雪是黑的。（F）    （5）我学英语，或者我学日语。（T）   （6）在宇宙中地球是唯一有生命的地球。    （7）1+101=110   （8）买两张星期六的电影票。（祈使句）   （9）全体立正！（祈使句）   （10）明天是否开会？（疑问句）   （11）天气多好啊！（感叹句）   （12）我正在说谎。（悖论）      （1）、（2）和（5）是命题，真值为T。 （3）和（4）是命题，真值为F。 （6）是命题，有确定真值，只是目前还不知道。 （7）不是命题，在二进制中为T，在十进制中为F， 祈使句、疑问句、感叹句等都不能作为命题，悖论无真值，也不能作为命题。语句（8）—（12）都不是命题。

3、分类 命题有两种类型：原子命题和复合命题 (1)原子命题：不能分解为更简单的陈述句。 (2)复合（分子）命题：由联结词、标点符号和原子命题复合构成的命题。 前面例子中的（1），（2），（3），（4），（6），（7）是原子命题，（5）是复合命题。

练习：指出下列语句哪些是命题，哪些不是命题，如果是命题，指出它的真值。（见教材第8页习题（1）） a）离散数学是计算机科学系的一门必修课。      b）计算机有空吗？      c）明天我去看电影。      d）请勿随地吐痰！      e）不存在最大质数。      f）如果我掌握了英语、法语，那么学习其他欧洲语言就容易的多。      g）9+5≤12      h）x=3      i）我们要努力学习。

a），e），g），h）是原子命题，f）是复合命题。 解： a）离散数学是计算机科学系的一门必修课。 是命题，真值为T。      b）计算机有空吗？ 疑问句，不是命题。      c）明天我去看电影。 是命题，真值要根据具体情况确定。      d）请勿随地吐痰！ 祈使句，不是命题。      e）不存在最大质数。 是命题，真值为T。      f）如果我掌握了英语、法语，那么学习其他欧洲语言就容易的多。 是命题，真值为T。      g）9+5≤12 是命题，真值为F。      h）x=3 不是命题，x=3的真假由x确定，当x取3时句子为真，当x取其他值时句子为假。      i）我们要努力学习。 祈使句，不是命题。

三、命题的表示法     1、命题标识符：表示命题的符号称为命题标识符。在数理逻辑中，使用大写字母，或带下标的大写字母，或用方括号括起的数字表示表示命题。     例：P：今天下雨。     “今天下雨”是一个命题，P是命题标识符。 A1：今天下雨。     [12]：今天下雨。    A1  ， [12]也是命题标识符。     2、命题常量：一个命题标识符如表示确定的命题，就称为命题常量。 3、命题变元：如果命题标识符只表示任意命题的位置标志，就称为命题变元。 命题变元可以表示任意命题，所以它不能确定真值，故命题变元不是命题。当命题变元用一个特定命题取代时，才能确定真值，这称为对命题变元进行指派。 4、原子变元：当命题变元表示原子命题时，该变元称为原子变元。

四、小结     学习本节要掌握下列概念：     命题 能表达判断的语句，并具有确定真值的陈述句。     真值 一个命题总具有一个“值”，称为真值。真值只有真和假两种，分别记为T和F。     原子命题 不能分解为更简单的陈述句，称为原子命题。     复合命题 由联结词、标点符号和原子命题复合构成的命题，称为复合命题。复合命题亦称分子命题。     命题标识符 表示命题的符号。     命题常量 一个命题标识符表示确定的命题，该标识符称作命题常量。     命题变元 题标识符如仅是表示任意命题的位置标志，就成为命题变元。     原子变元 当命题变元表示原子命题时，该变元称原子变元。          

§1—2 联结词     在数理逻辑中，复合命题是由原子命题与逻辑联结词组合而成，命题的连接方式叫做命题联结词或命题运算符。联结词是复合命题中的重要组成部分，为了便于书写和进行推演，必须对联结词作出明确规定并符号化。我们主要讨论下述五种联结词（亦称真值联结词，逻辑联结词或逻辑运算符），借助它们组成复合命题。  

（1）否定（Negation） （一元联结词） 1.定义 定义1-2.1 设P为一命题，P的否定是一个新的命题，记作 ┐P。若P为T，┐P为F；若P为F，┐P为T。联结词“┐”表示命题的否定，称为否定联结词或否定词，读作“非”或“not”。否定联结词有时亦可记作“ˉ”。 2.真值表 表1-2.1 命题P与其否定┐P的关系如表 1-2.1所示。 P ┐P T F

“否定”的意义仅是修改了命题的内容，它是一个一元运算，我们仍把它看作为联结词。 自然语言中的“不”、“无”、“没有”等词在命题演算中常与“非”相当。 例：P：今天下雨。 ┐P：今天不下雨。 ┐P：今天无雨。 ┐P：今天没有下雨。 P：上海是一个大城市。 ┐P：上海不是一个大城市。 ┐P：上海是一个不大的城市。 练习：P：一个世纪是一百年。写出┐P。

（2）合取（Conjunction） （二元联结词） 1.定义 定义1-2.2 两个命题P和Q的合取是一个复合命题，记作P∧Q。当且仅当P、Q同时为T时，P∧Q为T，在其他情况下，P∧Q的真值都是F。联结词“∧”称为合取词，读作“和”或“and”。 表1-2.2 P Q P∧Q T F 2.真值表 联结词“∧”的定义如表1-2.2所示。 表1-2.2中给出复合命题P∧Q为T当且仅当P、Q同时为T。

与“和”有相同意义的汉字还有“与”、“以及”、“并且”、“而且”等。 例：P：今天下雨。 Q：明天下雨。 上述命题的合取为 P∧Q：今天下雨而且明天下雨。 P∧Q：今天与明天都下雨。 P∧Q：这两天都下雨。 显然只有当“今天下雨”与“明天下雨”都是真时，“这两天都下雨”才是真的。

合取的概念与自然语言中的“与”意义相似，但并不完全相同。例如 P：我们去看电影。 Q：房间里有十张桌子。 上述命题的合取为 P∧Q：我们去看电影与房间里有十张桌子。 在自然语言中，上述命题是没有意义的，因为P与Q没有内在联系，但作为数理逻辑中P和Q的合取P∧Q来说，它仍可成为一个新的命题，只要按照定义，在P、Q分别取真值后，P∧Q的真值也必确定。

例如 ①P：1+1=2 Q：地球是行星。 P∧Q：1+1=2与地球是行星。 P∧Q的真值为T。 ②P：1+1=2 Q：地球是恒星。 P∧Q：1+1=2与地球是恒星。 P∧Q的真值为F。

③P：1+1=3 Q：地球是行星。 P∧Q：1+1=3与地球是行星。 P∧Q的真值为F。 ④P：1+1=3 Q：地球是恒星。 P∧Q：1+1=3与地球是恒星。

命题联结词“合取”甚至可以将两个互为否定的命题联结在一起。这时，其真值永为F。 P：今天下雨。 Q：今天不下雨。（此时Q既是┐P） P∧Q：今天下雨与今天不下雨。 P∧Q的真值为F。 命题联结词“合取”也可以将若干个命题联结在一起。 “合取”是一个二元运算。

注意，并非所有的“和”、“与”、“并且”均可用“∧”表示。例如“李华和张南是表兄弟。”“王丽与王萍是堂姐妹”“他打开箱子并且取出一件衣服来。”这三句中的“和”、“与”、“并且”就不能用“∧”表示。 练习：P：一个世纪是一百年。 Q：4是偶数。 写出P∧Q并确定其真值。

（3）析取（Disjunction） （二元联结词） 1.定义 定义1-2.3 两个命题P和Q的析取是一个复合命题，记作P∨Q。当且仅当P、Q同时为F时，P∨Q为F，否则P∨Q的真值为T。联结词“∨”称为合取词，读作“或”或“or”。 表1-2.3 2.真值表 联结词∨的定义如表1-2.3所示。 P Q P∨Q T F 表1-2.3中给出复合命题P∨Q为F当且仅当P、Q同时为F。

例：P：灯泡坏了。 Q：开关坏了。 上述命题的析取为 P∨Q：灯泡坏了或开关坏了。

并非所有的“或”可用“∨”表示。例如，“我向东行或向西行。”该语句中的“或”称为“排斥或”，因为事实上一个人不会既向东行，又向西行。 析取“∨”指的是“可兼或”。例如，他可能是100米或400米赛跑的冠军。这里 P：他可能是100米赛跑的冠军。 Q：他可能是400米赛跑的冠军。 P∨Q：他可能是100米或400米赛跑的冠军。

还有一些汉语中的“或”字实际上不是命题联结词。例如，他昨天做了二十或三十道习题。这里的“或”字只表示了习题的近似数目，不能用联结词“∨”表达。 练习：P：雪是黑的。 Q：4是偶数。 写出P∨Q并确定其真值。

（4）条件（Condition） （二元联结词） 1.定义 定义1-2.4 给定两个命题P和Q，其条件命题是一个复合命题，记作P→Q，读作“如果P，那么Q”或“若P则Q”。当且仅当P的真值为T，Q的真值为为F时，P→Q的真值为F，否则P→Q的真值为T。我们称P为前件，Q为后件。 P Q P→Q T F 表1-2.4 2.真值表 联结词→的定义如表1-2.4所示。

例1 如果某动物为哺乳动物，则它必胎生。 例2 如果我得到这本小说，那么我今夜就读完它。 例3 如果雪是黑的，那么太阳从西方出。 上述三个例子都可用条件命题P→Q表达。 在例1中，P：某动物为哺乳动物，Q：它必胎生。P的真值为T，Q的真值为T，P→Q的真值为T。 在例2中，P：我得到这本小说，Q：我今夜就读完它。P的真值为T，Q的真值为T，P→Q的真值为T。如果P的真值为T，Q的真值为F，P→Q的真值为F。如果P的真值为F，Q的真值为T，P→Q的真值为T。 在例3中，P：雪是黑的，Q：太阳从西方出。P的真值为F，Q的真值为F，P→Q的真值为T。

在自然语言中，“如果…”与“那么…”之间常常是有因果联系的，否则就没有意义，但对条件命题P→Q来说，只要P、Q能够分别确定真值，P→Q即成为命题。此外，自然语言中对“如果…、则…”这样的语句，当前提为假时，结论不管真假，这个语句的意义，往往无法判断。而在条件命题中，规定为“善意的推定”，即前提为F时，条件命题的真值都取为T。

在数学上和有些逻辑学的书籍中，“若P则Q”亦可叫作蕴含Q，而本书在条件命题中将避免使用“蕴含”一词，因为在以后将另外定义“蕴含”这个概念。 命题联结词“→”亦可记作“ ”。

(5)双条件（Double Condition） （二元联结词） 1.定义 定义1-2.5 给定两个命题P和Q，其复合命题P Q称作双条件命题，读作“P当且仅当Q”，当P和Q的真值相同时，P Q的真值为T，否则P Q的真值为F。 表1-2.5 2.真值表 联结词“ ”的定义可如表1-2.5所示。 P Q P Q T F

例1 两个三角形全等，当且仅当它们的三组对应边相等。 例2 燕子飞回南方，春天来了。 例3 2+2＝4当且仅当雪是白的。 例1 两个三角形全等，当且仅当它们的三组对应边相等。 例2 燕子飞回南方，春天来了。 例3 2+2＝4当且仅当雪是白的。 上面三个例子都可用双条件命题P Q来表示。与前面的联结词一样，双条件命题也可以不顾其因果联系，而只根据联结词定义确定真值。双条件联结词亦可记作“ ”或“iff”。它亦是二元运算。有时也用符号€表示双条件。 应强调指出的是：复合命题的真值只取决于各原子命题的真值，而与它们的内容、含义无关，与原子命题之间是否有关系无关。理解和掌握这一点是至关重要的。

小结 本节给出了如下五种联结词的定义： 否定 设P为一命题，P的否定是一个新的命题，记作 ┐P。若P为T，┐P为F；若P为F，┐P为T。 合取 两个命题P和Q的合取是一个复合命题，记作P∧Q。当且仅当P、Q同时为T时，P∧Q为T，在其他情况下，P∧Q的真值都是F。 析取 两个命题P和Q的析取是一个复合命题，记作P∨Q。当且仅当P、Q同时为F时，P∨Q为F，否则P∨Q的真值为T。 条件 给定两个命题P和Q，其条件命题是一个复合命题，记作P→Q，读作“如果P，那么Q”或“若P则Q”。当且仅当P的真值为T，Q的真值为为F时，P→Q的真值为F，否则P→Q的真值为T。 双条件 给定两个命题P和Q，其复合命题P Q称作双条件命题，读作“P当且仅当Q”，当P和Q的真值相同时，P Q的真值为T，否则P Q的真值为F。

练习 8页（2）--（6） (2)举例说明原子命题和复合命题。 (3)设P表示命题“天下雪 Q表示命题“我将去镇上。 R表示命题“我有时间” 练习 8页（2）--（6） (2)举例说明原子命题和复合命题。 (3)设P表示命题“天下雪 Q表示命题“我将去镇上。 R表示命题“我有时间” 以符号形式写出下列命题。 a)如果天不下雪和我有时间，那么我将去镇上。 b)我将去镇上，仅当我有时间时。 c)天不下雪。 d)天下雪，那么我不去镇上。

(4)用汉语写出一句子，对应下列每一个命题。 a)Q (R∧┐P) b)R∧Q c)(Q→R )∧(R→Q) (5)将下列命题符号化。 8)王强身体很好，成绩也很好。 b)小李一边看书，一边听音乐。 c)气候很好或很热。 d)如果a和b是偶数，则a+b是偶数。 e)四边形ABCD是平行四边形，当且仅当它的对边平行． f)停机的原因在于语法错误或程序错误。

(6)将下列复合命题分成若干原子命题， a)天气炎热且正在下雨。 b)天气炎热但湿度较低。 c)天正在下雨或湿度很高。 d)刘英与李进上山。 e)老王或小李是革新者。 f)如果你不看电影，那么我也不看电影。 g)我既不看电视也不外出，我在睡觉。 h)控制台打字机既可作输入设备，又可作输出设备。

解答 (2)举例说明原子命题和复合命题。 原子命题：北京是中国的首都。 复合命题：李毅和王强都是优秀学生。

(3)设P表示命题“天下雪” Q表示命题“我将去镇上。 R表示命题“我有时间” 以符号形式写出下列命题。 a)如果天不下雪和我有时间，那么我将去镇上。（┐P∧R ）→Q b)我将去镇上，仅当我有时间时。 R→Q c)天不下雪。 ┐P d)天下雪，那么我不去镇上。 P→┐Q

(4)用汉语写出一句子，对应下列每一个命题。 a)Q （R∧┐P) b)R∧Q 王强的数学和计算机都很好。 c)(Q→R) ∧(R→Q) 一个数是奇数，则它不能被2整除并且一个数不能被2整除，则它是奇数。

(5)将下列命题符号化。 a)王强身体很好，成绩也很好。 设P：王强身体很好。 Q：王强成绩很好。 P∧Q 设P：小李看书。 Q：小b)小李一边看书，一边听音乐。 李听音乐。 R∧Q c)气候很好或很热。 设P：气候很好。 Q：气候很热。 R∨Q d)如果a和b是偶数，则a+b是偶数。 设P：a和b是偶数。 Q：a+b是偶数。 P→Q e)四边形ABCD是平行四边形，当且仅当它的对边平行。 设P：四边形ABCD是平行四边形。 Q：四边形ABCD的对边平行。 P Q f)停机的原因在于语法错误或程序错误。 设P：语法错误。 Q：程序错误。 S：停机。（R∨Q）→S

(6)将下列复合命题分成若干原子命题， a)天气炎热且正在下雨。 P：天气炎热。Q：正在下雨。 P∧Q b)天气炎热但湿度较低。 P：天气炎热。R：湿度较低。 P∧R c)天正在下雨或湿度很高。 d)刘英与李进上山。 S：刘英上山。G：李进上山。

e)老王或小李是革新者。 W：老王是革新者。A：小李是革新者。W∨A f)如果你不看电影，那么我也不看电影。 B：你看电影。C：我看电影。 ┐B→┐C g)我既不看电视也不外出，我在睡觉。 D：我看电视。E：我外出。F：我睡觉。┐D∧┐E∧F h)控制台打字机既可作输入设备，又可作输出设备。 H：控制台打字机可作输入设备。 I：控制台打字机作输出设备。 H∧I