离散数学 第1章 数学语言与证明方法

1《离散数学》总评成绩：作业：10%（上课前上交，不可补交）期中成绩：30%，笔试考试期末成绩：60%，笔试考试2离散数学(Discretemathematics)是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。引言3计算机科学与技术专业方向CCC2004CS2004计算机科学方向CE2004计算机工程方向SE2004软件工程方向IT2004信息技术方向计算机科学与技术专业本科教育类型：科学型（计算机科学）工程型（计算机工程与软件工程）应用型（信息技术）4离散数学知识框架(科学型)基本逻辑证明技术集合关系函数图树基本计数核心知识单元推荐知识单元高级计数代数结构特殊的图形式系统集合基数计算理论初等数论可选知识单元应用应用应用5离散数学知识框架(工程型)基本逻辑证明技术集合关系函数图树基本计数核心知识单元推荐知识单元代数结构特殊的图形式系统高级计数初等数论可选知识单元应用应用应用6离散数学知识框架(应用型)基本逻辑集合关系函数图树核心知识单元推荐知识单元证明技术特殊的图基本计数代数系统简介初等数论可选知识单元应用应用应用77离散数学与其他课程的关系高等代数数学分析概率统计概率统计离散数学算法设计与分析算法与数据结构编译技术网络技术软件工程人工智能基础数学的延伸算法与数据结构的理论基础概率统计、算法设计与分析的理论基础其他专业课程的描述和建模工具8应用实例一个应用型方向的教学计划基本逻辑基础概念工具方法应用集合关系函数图树基本计数特殊的图知识单元：5个学时：549教学内容本次上课内容：前八章10离散数学课程教学目标具有良好的知识结构，为学习其他课程打下基础：知识获取能力掌握离散数学的语言，能对实际问题给出清晰的描述（建模）：基本应用能力掌握离散数学的分析方法，针对实际问题设计解决方案并加以实施：工程实践能力培养思维严谨性，提升抽象思考和严格推理能力：研究能力了解现代数学思想和学科进展，培养创新意识11离散数学中的学科方法什么是计算机科学中的数学方法以数学为工具进行计算机科学与技术研究的方法用数学语言表达事物的状态、关系和过程，经推导形成解释和判断特点是：高度抽象、高度精确、具有普遍意义主要的数学方法描述方法：模型分析方法：变换、数量化等证明方法：演绎推理、公理化方法、构造性方法等12系统建模——关系关系数据库——n元关系图的连通性——等价关系集合的聚类划分——等价关系流程的拓扑排序——偏序关系计划评审技术PERT——偏序关系问题类复杂度的归约——偏序关系13系统建模——图通信网络——无向图Internet上的超链接——有向图社会网络（群体之间影响）——有向图依赖网络（食物链）——有向图基于Petri网的工作流模型——有向图有源网络的最大流问题——有向图计算机文件系统——树决策——决策树多处理机调度——图的着色14系统建模——代数系统计算机硬件设计的基础——布尔代数编码系统——群码数据仓库OLAP分析——物化视图的格结构多维数据立方体包含n个维属性，1个度量属性在聚类操作中，需要物化的聚类层子方体构成一个格结构软件形式化方法——用进程代数描述并发系统基本元素是进程进程之间顺序、并发、通信都表示成运算1415示例1试题证明或推翻下列命题：“设平面上有100个点，其中任意两点间的距离至少是1.则最多有300对点距离恰好是1”.参考答案命题成立建模：无向图G=V,E，V是100个点的集合，两个点相邻当且仅当距离恰好为1.性质证明：每个顶点度数d(v)6，根据握手定理3006001006)(2mvdmVv16面向不同培养类型的离散数学定位类型科学型工程型应用型培养要求基础理论和核心技术研究原始创新基本理论与原理的综合应用（创新性应用）计算机应用人才定位学术研究IT企事业应用领域信息化人才人数少较多多离散数学的基础熟练掌握形式描述、变换、推理和证明方法熟练掌握离散系统的描述与分析方法了解实际离散系统的建模熟悉形式描述、变换、推理和证明方法熟练掌握离散系统的描述与分析方法了解实际离散系统建模简要了解形式描述、变换、推理和证明方法掌握离散系统描述与分析方法熟悉常用实际离散系统模型涉及其他专业课数据结构与算法,数据库系统原理,操作系统,编译原理,软件工程,人工智能,数字逻辑,计算机网络,…数据结构与算法,数据库系统原理,操作系统,编译原理,软件工程,数字逻辑,计算机网络,…数据结构与算法,数据库与信息管理技术,计算机网络与互联网,…学时安排建议学时72-108建议学时72-90建议学时51-7217能力培养体系理论课程（课堂教学）实验课程（实验教学）科研训练（科研项目）奖励基金竞赛（ACM竞赛、电子设计竞赛）实验室课题毕业论文创新能力综合能力实践能力18特点定位于应用型人才的培养教学内容及其安排以离散数学的基本概念、描述方法为主引入较多的离散数学在计算机科学技术中的应用实例介绍一些基本的证明技术教学方式以课堂讲授为主，辅以习题及网上教学习题及考核要求以概念题、计算题、应用题为主，辅以少量简单的证明题19第1章数学语言与证明方法1.1常用的数学符号1.2集合及其运算1.3证明方法概述201.1常用的数学符号1.1.1集合符号1.1.2运算符号1.1.3逻辑符号211.1.1集合符号集合是数学中最基本的概念,没有严格的定义理解成某些个体组成的整体,常用A,B,C等表示元素:集合中的个体xA(x属于A):x是A的元素xA(x不属于A):x不是A的元素包含(子集)AB即A中的每个元素都是B的元素不包含A⊈B即合B不包含集合A相等A=B即AB且BA不相等ABA⊈B或B⊈A真包含(真子集)AB即AB且AB221.1.1集合符号续复数集非零实数集，即实数集非零有理数集，即有理数集整数集自然数集非含自然数集C}0{RR}0{QQQZ00)(**RNN空集的幂集的对称差与的相对补对之交交之并并有相同的元素与的真子集是不包含的子集，或不是包含包含于的子集，或是的元素不是的元素是————)(PBA——AB——,,,——BA——BA,,,——ABA——BABA——BABA——BABBA——BA)B(BABA——BA——A——21121n1iiAABABAAAAAAAAAAAxAxxAxnniin（1）NZQRC（2）NZQRC231.1.2运算符号中的小者为或中的大者为或除余数相同，如被与如不能整除如整除之积，即之积，即之和，即之和，即babababababanbababababaaaaaaaaaaaaaaaaaaaaaaaaaiinnniiiinnnii,},min{),min(,},max{),max()3(mod74n)b(moda8|3,|9|3,|,,,,,,,,,,21211212112121121211241.1.2运算符号(续)中的元素个数有穷集合下限函数，如的最大整数，小于等于上限函数，如的最小整数，大于等于的绝对值，如的最小公倍数，如与的最大公约数，如与A||0,0.732.2-1,0.722.2-2.5|-2.5|||70)14,10(),(2)6,8gcd(),gcd(Axxxxxxlcmbabalcmbaba251.1.3逻辑符号命题与真值联结词(¬,,,,,)命题公式(重言式,矛盾式,可满足式)重要等值式重要推理规则个体,个体域与谓词全称量词与存在量词26命题:具有确定真值的陈述句,如:2+2=4;3是偶数；命题的符号化：用p,q,r等表示命题，如p:2+2=4;q:3是偶数;真与假的符号化:用1表示真,用0表示假真命题:真值为真的命题假命题:真值为假的命题例如,p:2+2=4,q:3是偶数它们都是命题,p是真命题,q是假命题.1.1.3逻辑符号27联结词(续)否定联结词否定式p:非p(p的否定)p为真当且仅当p为假合取联结词合取式pq:p并且q(p与q)pq为真当且仅当p与q同时为真析取联结词析取式pq:p或qpq为假当且仅当p与q同时为假28联结词(续)排斥或联结词排斥或pq:p并且非q,或者q并且非ppq为真当且仅当p与q中一个为真,另一个为假蕴涵联结词蕴涵式pq:如果p,则qpq为假当且仅当p为真q为假等价联结词等价式pq:p当且仅当qpq为真当且仅当p与q同时为真或同时为假29实例:设p:2是偶数,q:1+1=3,则p的真值为1q的真值为¬p的真值为¬q的真值为pq的真值为p¬q的真值为pq的真值为¬pq的真值为p¬q的真值为¬p¬q的真值为pq的真值为¬pq的真值为p¬q的真值为¬p¬q的真值为0010110111001pq的真值为p¬q的真值为0030实例(续)pq的真值为0p¬q的真值为1¬pq的真值为1¬p¬q的真值为1又设r:今天是星期一,s:明天是星期二,t:明天是星期三rs的真值为1rt的真值为不定31命题公式基本复合命题：设p,q为命题，称p,pq,pq,pq,pq为基本复合命题。命题变项:取值为0或1的变元,也用p,q,r等表示.命题公式:用联结词和圆括号把命题和命题变项按照一定规则连接起来的符号串,常用A,B,C等表示.例如,A=(pq)(rp)公式的赋值:对公式中每一个命题变项给定一个值(0或1).公式的成真赋值:使公式为真的赋值.公式的成假赋值:使公式为假的赋值.例如,p=1,q=1,r=1是A的成真赋值,p=0,q=1,r=0是A的成假赋值.32重言式,矛盾式与可满足式重言式(永真式):无成假赋值的命题公式矛盾式(永假式):无成真赋值的命题公式可满足式:不是矛盾式的命题公式例如,A=(pq)(rp)是可满足式,但不是重言式,B=(pq)(pq)(pq)(pq)是重言式,C=p(pq)(pq)是矛盾式.AB:蕴涵式AB是重言式的简记.AB:等价式AB是重言式的简记，称A与B等值，AB是等值式.33基本等值式双重否定律AA幂等律AAA,AAA交换律ABBA,ABBA结合律(AB)CA(BC)(AB)CA(BC)分配律A(BC)(AB)(AC)A(BC)(AB)(AC)德·摩根律(AB)AB(AB)AB34基本等值式(续)吸收律A(AB)A,A(AB)A零律A11,A00同一律A0A,A1A排中律AA1矛盾律AA0蕴涵等值式ABAB等价等值式AB(AB)(BA)假言易位等值式ABBA等价否定等值式ABAB归谬论(AB)(AB)A35重要推理规则(推理定律)附加律A(AB)化简律(AB)A假言推理