离散数学笔记

—1—《《《《离散数学离散数学离散数学离散数学》》》》教案教案教案教案课程性质课程性质课程性质课程性质离散数学（又称计算机数学）是现代数学的重要分支，是计算机专业核心基础课程之一。课程目标课程目标课程目标课程目标离散数学是以研究离散量的结构和相互之间的关系为主要目标，其研究对象一般为：有限或可数个元素（例如：自然数、整数、真假值、有限个结点等），而离散性也是计算机科学的显著特点。与其他课程的关系与其他课程的关系与其他课程的关系与其他课程的关系离散数学与计算机科学的其他课程,如：数据结构、操作系统、编译原理、算法分析、逻辑设计、系统结构、容错技术、人工智能等有密切的联系。它是这些课程的先导和基础课程。教材与参考书教材与参考书教材与参考书教材与参考书《离散数学》上海科学技术文献出版社，1982，左孝凌等编著《DiscreteMathematicalStructures（FourthEdition）》HigherEducationPress，2001BernardKolman，RobertC.Busby，SharonCutlerRoss课程内容课程内容课程内容课程内容本课程根据大纲的内容和相关独立性，可分为四大部分。第一部分数理逻辑。包括命题逻辑、谓词逻辑第二部分集合论。包括集合与关系、函数第三部分代数系统。包括代数结构、格与布尔代数第四部分图论第一篇第一篇第一篇第一篇数理逻数理逻数理逻数理逻辑辑辑辑逻辑学逻辑学逻辑学逻辑学：研究思维形式及思维规律的科学。逻辑学分为二类：辩证逻辑和形式逻辑。辩证逻辑辩证逻辑辩证逻辑辩证逻辑：是研究事物发展的客观规律。形式逻辑形式逻辑形式逻辑形式逻辑：对思维的形式结构和规律进行研究。数数数数数数数数理理理理理理理理逻逻逻逻逻逻逻逻辑辑辑辑辑辑辑辑是用数学的方法研究概念、判断和推理的科学，属于形式逻辑属于形式逻辑属于形式逻辑属于形式逻辑。在数理逻辑中，用数学的方法是指引进一套符号体系的方法来研究概念、判断和推理。即对符号进行判断和推理。数理逻辑分为四大分支：证明论、模型论、递归论和公理集合论。我们这里介绍的是属于四大分支的共同基础——古典数理逻辑(命题逻辑和谓词逻辑)。第第一一章章命命题题逻逻辑辑目目录录§§11..11命命题题§§11..22命命题题联联结结词词§§11..33命命题题公公式式§§11..44等等价价式式§§11..55永永真真蕴蕴含含式式§§11..66其其他他命命题题联联结结词词§§11..77范范式式§§11..88推推论论理理论论第一章第一章第一章第一章命题逻辑命题逻辑命题逻辑命题逻辑教学目的及要求教学目的及要求教学目的及要求教学目的及要求：深刻理解和掌握命题逻辑中基本概念和基本方法。教学内容教学内容教学内容教学内容：命题及表示、联结词、命题公式与翻译、真值表与等价公式、重言式与蕴涵式、对偶与范式、推理理论。教学重点教学重点教学重点教学重点：命题逻辑中的基本概念和基本推理方法。教学难点教学难点教学难点教学难点：推理理论。§§§§1.1命题命题命题命题【定义】具有确定真假值的陈述句叫命题。讨论定义讨论定义讨论定义讨论定义：：：：（1）命题可以是真的，或者是假的，但不能同时为真又为假。（2）命题分类：—2—①原子命题（基本命题、本原命题）：不能分解成为更简单的命题。例例例例：：：：我是一位学生。②分子命题（复合命题）：若干个原子命题使用适当的联结词所组成的新命题。例例例例：：：：我是一位学生和他是一位工人（3）命题所用符号：常用大写26个英文字母表示命题。用A、B、C、……、Z表示。（4）命题中所有的“真”用“T”表示，命题中所有的“假”用“F”表示。例例例例：判断下列语句是否为命题。＊＊＊＊＊＊＊＊陈陈述述句句一一般般为为命命题题。。例如：①十是整数。（T）②上海是一个村庄。（F）③今天下雨。④加拿大是一个国家。（T）⑤2是偶数而3是奇数。⑥她不是护士。⑦1＋101＝110⑧今天是星期天。＊＊＊＊＊＊＊＊命命令令句句，，感感叹叹句句，，疑疑问问句句均均不不是是命命题题。。例如：①把门关上！②你到哪里去？＊＊＊＊＊＊＊＊语语句句既既为为真真，，同同时时又又包包含含假假的的不不是是命命题题，，这这样样的的句句子子称称为为““悖悖论论””。。（在命题逻辑中不讨论这类问题）。例如：他正在说谎。（悖论）§§§§1.2命题联结词命题联结词命题联结词命题联结词在命题演算中也有类似的日常生活中的联结词称做“命题联结词命题联结词命题联结词命题联结词”,下面先介绍五个常用的命题联结词。1、、、、否定词否定词否定词否定词：（：（：（：（否定运算否定运算否定运算否定运算、、、、非运算非运算非运算非运算））））（1）符号：“¬”，读作“非”，“否定”设命题为P，则在P的前面加否定词¬，变成¬P，¬P读做“P的否定”或“非P”。（2）定义：（由真值表给出）P的真值表：略（3）举例：Q：每一种生物均是动物。F¬Q：有一些生物不是动物。T这里¬Q不能讲成“每一种生物都不是动物”。对对量量化化命命题题的的否否定定，，除除对对动动词词进进行行否否定定外外，，同同时时对对量量化化词词也也要要加加以以否否定定。2、、、、合取词合取词合取词合取词（（（（““““合取合取合取合取””””、、、、““““积积积积””””、、、、““““与与与与””””运算运算运算运算））））（1）符号：“∧”设P，Q为两个命题，则P∧Q称P与Q的合取，读作：“P与Q”、“P与Q的合取”、“P并且Q”等。（2）定义：（由真值表给出）P∧Q的真值表：PQP∧QQ∧PTTTTTFFFFTFFFFFF当且仅当P和Q的真值均为“T”，则（P∧Q）的真值为“T”。否则，其真值为“F”。注意注意注意注意：P和Q是互为独立的；地位是平等的，P和Q的位置可以交换而不会影响P∧Q的结果。—3—（3）举例：①P：王华的成绩很好Q：王华的品德很好。则P∧Q：王华的成绩很好并且品德很好。②P：我们去种树Q：房间里有一台电视机则P∧Q：我们去种树与房间里有一台电视机。③P：今天下大雨Q：3+3=6则P∧Q：今天下大雨和3+3=6由例②③可见，在日常生活中，合取词应用在二个有关系的命题之间。而在逻辑学中，合取词可以用在二个毫不相干的命题之间。④P：王大和王二是亲兄弟。Q：他打开箱子然后拿出一件衣服来。两个语句均不是合取联结词组成的命题。3、、、、析取词析取词析取词析取词（（（（或运算或运算或运算或运算））））（1）符号：“∨”设P、Q为二个命题，则（P∨Q）称作P与Q的“析取”，读作：“P或Q”。（2）定义：（由真值表给出）当且仅当P、Q均为“F”时，（P∨Q）为“F”。否则，其真值为“T”。P∨Q的真值表：PQP∨QQ∨PTTTTTFTTFTTTFFFF区分“可兼或”与“不可兼或（异或，排斥或）”：①“可兼或”即P或Q为“T”时（P∨Q）为“T”。例如例如例如例如：灯泡有故障或开关有故障。今晚写字或看书。今天下雨或打雷。以上例句均为可兼或。②“不可兼或”即P和Q的真值不同时，P▽Q为T。（异或用“▽”表示）P▽Q的真值表：PQP▽QQ▽PTTFFTFTTFTTTFFFF例如例如例如例如：他通过电视看杂技或或或或到剧场看杂技。他乘火车去北京或或或或乘飞机去北京。以上两句均为不“可兼或”。4、、、、单条件联结词单条件联结词单条件联结词单条件联结词：（：（：（：（““““蕴含蕴含蕴含蕴含””””联结词联结词联结词联结词、、、、蕴含词蕴含词蕴含词蕴含词））））（1）符号：“→”，读作“如果…则…”、“蕴含”P、Q为二个命题，（P→Q）为新的命题，读作：“如果P则Q”，“P蕴含Q”，“P仅当Q”，“Q当且P”，“P是Q的充分条件”。—4—（2）定义：（由真值表给出）P→Q的真值表：PQP→QQ→PTTTTTFFTFTTFFFTT当当PP为为““TT””，，QQ为为““FF””时时，，则则（（PP→→QQ））为为““FF””，，否否则则（（PP→→QQ））均均为为““TT””。PP：：称称为为前前件件、、条条件件、、前前提提、、假假设设。。QQ：：称称为为后后件件、、结结论论。。（3）举例：(a)P：我拿起一本书。Q：我一口气读完了这本书。P→Q：如果我拿起一本书，则我一口气读完。了这本书。(b)P：月亮出来了Q：3×3=9P→Q：如果月亮出来了，则3×3=9。通通通通通通通通常常常常常常常常称称称称称称称称：：：：(a)为形式条件命题——前提和结果有某种形式和内容上的联系。(b)为实质条件命题——前提和结果可以有联系，也可以没有联系，只要满足单条件命题的定义。所所以以，，是是形形式式条条件件命命题题一一定定是是实实质质条条件件命命题题,,反反之之不不一一定定。。““→→””是是实实质质条条件件命命题题。例例例例：：：：P：我买到了鱼；Q：我吃鱼。P→Q：如果我买到了鱼，则我吃鱼。但“如果我没买到鱼，则我吃鱼”，在日常生活中不可能，但在单条件命题的定义中是允许的。可以证明可以证明可以证明可以证明：P→Q⇔¬Q→¬P原命题⇔逆反命题Q→P⇔¬P→¬Q逆命题⇔反命题列出真值表,由真值表得：原命题⇔逆反命题逆命题⇔反命题PQP→Q¬Q→¬PQ→P¬P→¬QTTTTTTTFFFTTFTTTFFFFTTTT5555、、、、双条件联结词双条件联结词双条件联结词双条件联结词：（：（：（：（““““等价等价等价等价””””词词词词、、、、““““同同同同””””联结词联结词联结词联结词、、、、““““等同等同等同等同””””词词词词））））（1）符号：“↔”。设P、Q为二个命题，则“P↔Q”读作“P当且仅当Q”，“P等价Q”，“P是Q的充分必要条件”。（2）定义：（由真值表给出）P→Q的真值表：PQP↔QQ↔PTTTTTFFFFTFFFFTT每每当当PP和和QQ的的真真值值相相同同时时，，则则（（PP↔↔QQ））的的真真值值为为““TT””，，否否则则（（PP↔↔QQ））的的真真值值为为““FF””。（3）举例：—5—（a）设P：△ABC是等腰三角形Q：△ABC有两只角相等P↔Q：△ABC是等腰三角形当且仅当有两只角相等。（b）下面均为等价联结词：春天来了当且仅当燕子飞回来了。平面上二直线平行，当且仅当二直线不相交。2＋2＝4当且仅当雪是白色的。（4）P、Q中，P、Q的地位是平等的，P、Q交换位置不会改变真值表中的值。（5）P当且仅当QP↔QP仅当QP→QP当且QQ→P6、、、、命题联结词在使用中的优先级命题联结词在使用中的优先级命题联结词在使用中的优先级命题联结词在使用中的优先级（1）先括号内，后括号外；（2）运算时联结词的优先次序为：¬、∧、∨、→、↔（由高到低）；（3）联结词按从左到右的次序进行运算；（4）最外层的括号一律均可省去；如：（P→Q∨Ｒ）可写成P→Q∨Ｒ。例如例如例如例如：：：：¬P∨(Q∨Ｒ)可省去括号，因为“Ｖ”运算是可结合的。而P→(Q→Ｒ)中的括号不能省去，因“→”不满足结合律。7、、、、命题联结词小结命题联结词小结命题联结词小结命题联结词小结（1）五个联结词的含义与日常生活中的联结词的含义大致相同。（2）“或”可分为可兼或（∨）和异或（▽）（不可兼或）。（3）“¬”为一元运算，其余四个均为二元运算。（4）“→”分为形式条件和实质条件命题，当前件为“F”时，不论后件怎样，则单条件命题的真值均为“T”。（5）命题联结词是命题或命题之间的联结词，而不是名词之间、数字之间和动词之间的联结词。以上介绍了五种常用的联结词及其相应的复合命题形式。数理逻辑的特点是把逻辑推理变成类似数学演算的完全形式化了的逻辑演算，为此，首先要把推理所涉及到的各命题符号化命题符号化命题符号化命题符号化。步骤如下步骤如下步骤如下步骤如下：①找出各简单命题，分别符号化。②找出各联结词，把简单命题逐个联结起来。例例例例将下列命题符号化：（1）李明是计算机系的学生，他住在312室或313室。（2）张三和李四是朋友。（3）虽然交通堵塞，但是老王还是准时到达了车站。（4）只有一个角是直角的三角