离散数学-第一章(3.5周)

1引言离散数学的概念离散数学的内容离散数学的由来与发展离散数学的应用2离散数学的概念离散数学（DiscreteMath）研究离散量的关系的一门科学。研究离散结构的数学分科计算机科学、信息科学、数字化科学的数学基础它为计算机科学中的数据结构、编译理论、操作系统、算法分析、人工智能等提供了必要的数学知识。3离散数学的内容研究对象：离散量（真假值、自然数、集合、字母表、图等）之间的关系和结构。具体内容：数理逻辑（MathematicsLogic)集合论(Sets)组合论（Combination)图论（GraphTheory)代数结构（AlgbraStructure)线性代数(LinearAlgbra)概率论（PropobilityTheory)……4离散数学的由来与发展古老计数:自然数图论:Konigsberg哥尼斯堡七桥问题年青计算机:二进制运算离散数学是随着计算机科学与技术的产生发展和应用领域的不断发展而逐步形成和发展起来的一门新兴学科，作为一门课程开设于上世纪70年代初。5离散数学的应用广泛应用于计算机科学和工程的各个方面，如：数理逻辑——程序设计、逻辑(电路)设计、人工智能集合论——算法设计和分析、密码、编码、数据库代数结构——编码、密码、容错分析图论———计算机科学和应用的所有领域离散数学为计算机应用专业的绝大多数课程提供了必备的数学工具，有助于培养我们抽象的思维和逻辑推理的能力。6离散数学课程设置离散数学的重要地位:计算机系核心课程信息类专业必修课程其它类专业的重要选修课程离散数学的先修课程：高等数学、线性代数。离散数学的后继课程：数据结构、编译技术、算法分析与设计、人工智能、数据库、……7离散数学课程的学习特点及方法特点:强调：逻辑性、抽象性；注重：概念、方法与应用方法:1．该课程概念名词多，定义多，公式多，要求记忆准确。2．认真/仔细做好课堂笔记。3．完成大量习题。4．与程序语言及算法设计相结合，思考、理解并应用所学知识。8资料教材：《离散数学》左孝凌李为鑑刘永才编,上海科学技术文献出版社,18.00元/本该教材另配习题解答指导书参考教材：1、《离散数学》(耿素云屈婉玲张立昂清华大学出版社)2、DiscreteMathematics（ForthEdition:RichardJohnsonbaugh)3、DiscreteMathematics（RevisedEdition:Biggs)9本课程学习内容本课程将学习数理逻辑、集合论、图论、代数结构等基本部分内容。数理逻辑的重点是公式演算与推理证明；集合论的重点是关系理论与映射的描述；图论则着重于讨论结点之间的关系以及图论方法的各种实际应用；代数结构侧重于用适宜的数学结构去描述具体的问题,即”数学建模“。10课程内容第一篇数理逻辑11第一篇数理逻辑逻辑学是一门研究思维形式及思维规律的科学。逻辑规律就是客观事物在人的主观意识中的反映。逻辑学分类：辨证逻辑学：是以辩证法认识论的世界观为基础的逻辑学形式逻辑学：是对思维的形式结构和规律进行研究的，类似于语法的一门工具性科学12第一篇数理逻辑思维的形式结构包括概念、判断和推理之间的结构和联系数理逻辑是用数学方法来研究推理过程的科学。主要是指引进一套符号体系的方法，因此数理逻辑一般又叫符号逻辑。基本内容是：命题逻辑（演算）和谓词逻辑（演算）。第1章命题逻辑1命题及命题符号化2联结词3命题公式与翻译4真值表与等价公式5等值演算6重言式与蕴含式7其它联结词8对偶与范试9推理理论1.1命题及命题符号化命题与真值原子命题复合命题命题常项命题变项联结词一、命题的定义1、命题：能判定真假的陈述句2、命题的定义中包含二层含义(1)在语法上；命题必须是陈述句。而疑问句、祈使句和感叹句等无所谓真假，所以不是命题。(2)命题具有唯一的真值，这与我们是否知道它的真假是两回事。二、命题的真值命题的真值：陈述句为真或为假的这种性质，称为命题的真值。真命题：与事实相符的命题为真命题，其真值为真，用l(或T)表示；假命题：与事实不相符的命题则称为假命题，其真值为假，用0(或F)表示。例下列句子中那些是命题？(1)地球是圆的.(2)2+5＝8.(3)x+5＞3.(4)你有铅笔吗？(5)这只兔子跑得真快呀！(6)请不要讲话！(7)我正在说谎话.真命题假命题真值不确定疑问句感叹句祈使句悖论(3)~(7)都不是命题三、命题的分类1、简单命题(原子命题)：不能分解为更简单的陈述语句的命题2、复合命题：由简单命题与联结词按一定规则复合而成的命题四、简单命题符号化用大写英文字母A，B，C,…;A1，A2,…;[n]表示简单命题，这些表示命题的符号称为命题标识符。例如，令P：3是有理数，则p的真值为1Q：2+57，则q的真值为020再次注意：命题是具有唯一真值的陈述句。命题常量：一个命题标识符如表示确定的命题，就称为命题常量。命题变元：命题标识符只表示任意命题的位置标志，称为命题变元命题变元不是命题指派：当命题变元Ｐ用一个特定命题取代时，Ｐ才能确定真值，这时称为Ｐ进行指派1.2联结词与复合命题一、常用联结词1.否定式与否定联结词“”定义设p为命题，复合命题“非p”（或“p的否定”）称为p的否定式，记作p，符号称作否定联结词，并规定p为真当且仅当p为假P与P的真值关系：TFPFTP例1P：地球是圆的，则¬P：地球不是圆的。注意：否定词“¬”是一个一元运算，它的意义是“否定”被否定命题的全部，而不是一部分。日常用语中，诸如“并非”，“永不”，“绝不”等联结词，尽管它们的含义并不完全相同，但除否定外，没有其他的逻辑内容，因而都可用否定词表示。2.合取式与合取联结词“∧”定义设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q的合取式，记作p∧q，∧称作合取联结词，并规定p∧q为真当且仅当p与q同时为真FFFFFTFTPQTFTTPQPQ的真值关系：例将下列命题符号化.(1)王晓既用功又聪明.(2)王晓不仅聪明，而且用功.(3)王晓虽然聪明，但不用功.(4)张辉与王丽都是三好生.(5)张辉与王丽是同学.例将下列命题符号化.(1)王晓既用功又聪明.(2)王晓不仅聪明，而且用功.(3)王晓虽然聪明，但不用功.解令p：王晓用功，q：王晓聪明，则(1)p∧q(2)p∧q(3)p∧q.例将下列命题符号化.(4)张辉与王丽都是三好生.(5)张辉与王丽是同学.解令r:张辉是三好学生，s:王丽是三好学生(4)r∧s.(5)令t:张辉与王丽是同学，t是简单命题.说明:(1)~(4)说明描述合取式的灵活性与多样性.(5)中“与”联结的是句子的主语成分，因而(5)中句子是简单命题.3.析取式与析取联结词“∨”定义设p,q为二命题，复合命题“p或q”称作p与q的析取式，记作p∨q，∨称作析取联结词，并规定p∨q为假当且仅当p与q同时为假.P∨P的真值关系：FFFTFTTTP∨QTFTTPQ例将下列命题符号化(1)2或4是素数.(2)2或3是素数.(3)4或6是素数.(4)小元元只能拿一个苹果或一个梨.(5)王晓红生于1975年或1976年.3.析取式与析取联结词“∨”解令p:2是素数,q:3是素数,r:4是素数,s:6是素数,则(1),(2),(3)均为相容或（可兼或）.分别符号化为:p∨r,p∨q,r∨s,它们的真值分别为1,1,0.而(4),(5)为排斥或.令t:小元元拿一个苹果，u:小元元拿一个梨，则(4)符号化为(t∧u)∨(t∧u).令v:王晓红生于1975年,w:王晓红生于1976年,则(5)既可符号化为(v∧w)∨(v∧w.4.条件(蕴涵式与蕴涵联结词)“”定义设p,q为二命题，复合命题“如果p,则q”称作p与q的蕴涵式，记作pq，并称p是蕴涵式的前件，q为蕴涵式的后件.称作蕴涵联结词，并规定，pq为假当且仅当p为真q为假.TTFTPQFFFTTFTTPQ真值关系：“善意的推定”pq的逻辑关系：q为p的必要条件“如果p，则q”的不同表述法很多：若p，就q只要p，就qp仅当q只有q才p除非q,才p或除非q,否则非p，当p为假时，pq为真善意的推定：前件为假，结论无论真/假，命题为真。例设p:天冷，q:小王穿羽绒服，将下列命题符号化(1)只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷.(4)只有天冷，小王才穿羽绒服.(5)除非天冷，小王才穿羽绒服.(6)除非小王穿羽绒服，否则天不冷.(7)如果天不冷，则小王不穿羽绒服.(8)小王穿羽绒服仅当天冷的时候.注意：pq与qp等值（真值相同）pqpqpqpqqpqpqpqp定义设p，q为二命题，复合命题“p当且仅当q”称作p与q的等价式，记作pq，称作等价联结词.并规定pq为真当且仅当p与q同时为真或同时为假.5.双条件(等价式与等价联结词)“”真值关系：TFFTFFFTTFTTPQP↔Q定义设p，q为二命题，复合命题“p当且仅当q”称作p与q的等价式，记作pq，称作等价联结词.并规定pq为真当且仅当p与q同时为真或同时为假.说明:(1)pq的逻辑关系:p与q互为充分必要条件(2)pq为真当且仅当p与q同真或同假5.等价式与等价联结词“”例求下列复合命题的真值(1)2+2＝4当且仅当3+3＝6.(2)2+2＝4当且仅当3是偶数.(3)2+2＝4当且仅当太阳从东方升起.(4)2+2＝4当且仅当美国位于非洲.它们的真值分别为1，0，1，0以上给出了5个联结词：,,,,，组成一个联结词集合{,,,,}。联结词的优先顺序为：,,,,;如果出现的联结词同级，又无括号时，则按从左到右的顺序运算;若遇有括号时，应该先进行括号中的运算.二、命题的符号化命题的符号化的步骤：1、分析出简单命题，将它们符号化。2、使用合适的联结词，将简单命题联结起来，组成复合命题的符号化表示。例用符号形式表示下列命题。（1）如果明天早上下雨或下雪，那么我不去学校（2）如果明天早上不下雨且不下雪，那么我去学校。（3）如果明天早上不是雨夹雪，那么我去学校。（4）只有当明天早上不下雨且不下雪时，我才去学校。解令P：明天早上下雨；Q：明天早上下雪；R：我去学校。（2）（¬P∧¬Q）→R；（1）（P∨Q）→¬R；（4）R→（¬P∧¬Q）（3）¬(P∧Q）→R；1.3命题公式与翻译预备知识原子命题：不能分解为更简单的陈述语句的命题，即它不含任何联结词。复合命题：至少含一个的联结词命题。如：若P和Q是两个命题，则¬P，P∧Q，P∨Q，P→Q等均是复合命题。若P和Q是命题变元，则¬P，P∧Q，P∨Q，P→Q，P→Q等式子就称作命题公式。命题公式没有真假值，只有进行指派后，它才是命题。一、命题公式1、命题公式(wellformedfomula，wff)的定义将命题变元用联结词和括号按照一定的逻辑关系连接起来的符号串称为命题演算的合式公式（命题公式，公式）。其定义规定如下：(1)单个命题变元本身是一个合式公式。(2)若A是合式公式，则¬A也是合式公式。(3)若A，B是合式公式，则A∧B，A∨B，A→B和AB也是合式公式。(4)当且仅当经过有限次地使用(1)-(3)所形成的符号串才是合式公式。二、翻译翻译定义：把自然语言中的一些语句变成数理逻辑中的符号形式。二、翻译自然语句形式化的过程主要包括两个步骤：a.分析出各简单命题，将它们符号化；b.根据自然语句中的逻辑关系，使用恰当的命题联结词，把简单命题逐个联结起来，构成复合命题的特号化表示。二、翻译3．翻译(3)语句形式化要注意：a、要善于确定简单命题，不要把一个概念（如“我和他是同学”是一个简单命题）硬拆成几个概念。“我和他是同学”是一个简单命题；b、要善于识别自然语言中的联结词(有时它们被省略)。