下载文档原格式
《离散数学》教案第一章集合与关系集合是数学中最基本的概念，又是数学各分支、自然科学及社会科学各领域的最普遍采用的描述工具。
集合论是离散数学的重要组成部分，是现代数学中占有独特地位的一个分支。
G. Cantor(康脱)是作为数学分支的集合论的奠基人。
1870年前后，他关于无穷序列的研究导致集合论的系统发展。
1874年他发表了关于实数集合不能与自然数集合建立一一对应的有名的证明。
1878年，他引进了两个集合具有相等的“势”的概念。
然而，朴素集合论中包含着悖论。
第一个悖论是布拉利-福尔蒂的最大序数悖论。
1901年罗素发现了有名的罗素悖论。
1932年康脱也发表了关于最大基数的悖论。
集合论的现代公理化开始于1908年策梅罗所发表的一组公理，经过弗兰克尔的加工，这个系统称为策梅罗-弗兰克尔集合论（ZF），其中包括1904年策梅罗引入的选择公理。
另外一种系统是冯·诺伊曼-伯奈斯-哥德尔集合论。
公理集合论中一个有名的猜想是连续统假设（CH）。
哥德尔证明了连续统假设与策梅罗-弗兰克尔集合论的相容性，科恩证明了连续统假设与策梅罗-弗兰克尔集合论的独立性。
现在把策梅罗-弗兰克尔集合论与选择公理一起称为ZFC系统。
一、学习目的与要求本章目的是介绍集合的基本概念，讲授集合运算的基本理论，关系的定义与运算。
通过本章的学习，使学生了解集合是数学的基本语言，掌握主要的集合运算方法和关系运算方法，为学习后续章节打下良好基础。
二、知识点1．集合的基本概念与表示方法；2．集合的运算；3．序偶与笛卡尔积；4．关系及其表示、关系矩阵、关系图；5．关系的性质，符合关系、逆关系；6．关系的闭包运算；7．集合的划分与覆盖、等价关系与等价类；相容关系；8．序关系、偏序集、哈斯图。
三、要求1．识记集合的层次关系、集合与其元素间的关系，自反关系、对称关系、传递关系的识别，复合关系、逆关系的识别。
2．领会领会下列概念：两个集合相等的概念几证明方法，关系的闭包运算，关系等价性证明。
（完整版）离散数学电子教材1（可编辑修改word版）第1 章命题逻辑逻辑是研究人的思维的科学，包括辩证逻辑和形式逻辑。
辩证逻辑是研究反映客观世界辩证发展过程的人类思维的形态的。
形式逻辑是研究思维的形式结构和规律的科学，它撇开具体的、个别的思维内容，从形式结构方面研究概念、判断和推理及其正确联系的规律。
数理逻辑是用数学方法研究推理的形式结构和推理的规律的数学学科。
所谓的数学方法也就是用一套有严格定义的符号，即建立一套形式语言来研究。
因此数理逻辑也称为符号逻辑。
数理逻辑的基础部分是命题逻辑和谓词逻辑。
本章主要讲述命题逻辑，谓词逻辑将在第2 章进行讨论。
1.1命题及其表示1.1.1命题的基本概念数理逻辑研究的中心问题是推理（Inference)，而推理就必然包含前提和结论，前提和结论都是表达判断的陈述句，因而表达判断的陈述句就成为推理的基本要素。
在数理逻辑中，将能够判断真假的陈述句称为命题。
因此命题就成为推理的基本单位。
在命题逻辑中，对命题的组成部分不再进一步细分。
定义1.1.1 能够判断真假的陈述句称为命题（Proposition）。
命题的判断结果称为命题的真值，常用T(True)（或1）表示真，F(False)（或0）表示假。
真值为真的命题称为真命题，真值为假的命题称为假命题。
从上述的定义可知，判定一个句子是否为命题要分为两步：一是判定是否为陈述句，二是能否判定真假，二者缺一不可。
例1.1.1 判断下列句子是否为命题（1）北京是中国的首都。
（2）请勿吸烟！（3）雪是黑的。
（4）明天开会吗？（5）x+y=5。
（6）我正在说谎。
（7）9+5≤12 。
（8）1+101=110 。
（9）今天天气多好啊！（10）别的星球上有生物。
解在上述的十个句子中，（2）、（9）为祈使句，（4）为疑问句，（5）、（6）虽然是陈述句，但（5）没有确定的真值，其真假随x、y 取值的不同而有改变，（6）是悖论(Paradox)（即由真能推出假，由假也能推出真），因而（2）、（4）、（5）、（6）、（9）均不是命题。
离散数学模型分析——覆盖问题ylyang@youlongy@Email 2010年7月22日时间杨有龙教授报告人2008年国家一等奖西安电子科技大学理学院数学系杨有龙2009年国家二等奖西安电子科技大学理学院数学系杨有龙2009年国家二等奖西安电子科技大学理学院数学系杨有龙2008年陕西省一等奖西安电子科技大学理学院数学系杨有龙2008年陕西省一等奖西安电子科技大学理学院数学系杨有龙2009年陕西省一等奖西安电子科技大学理学院数学系杨有龙2009年陕西省一等奖西安电子科技大学理学院数学系杨有龙2009年国际数模ICM 一等奖西安电子科技大学理学院数学系杨有龙2009年国际数模ICM 二等奖西安电子科技大学理学院数学系杨有龙西安电子科技大学理学院数学系杨有龙近年赛事成绩33(1)2010年321717(2)5(2)13(1)42009年220812(2)33(1)532008年国家三等奖国家二等奖国家一等奖陕西省二等奖陕西省一等奖国家二等奖国家一等奖国际二等奖国际一等奖奖项全国研究生数学建模竞赛全国大学生数学建模竞赛国际大学生数学建模竞赛赛事内容提要背景问题覆盖问题覆盖问题的求解西安电子科技大学理学院数学系杨有龙内容提要背景问题覆盖问题覆盖问题的求解西安电子科技大学理学院数学系杨有龙问题1某城市的城建部门计划在每条街的拐角处或另一个尽头装一个消防水龙头，需要水龙头的个数是多少？请建立模型并给出解决的方案。
西安电子科技大学理学院数学系杨有龙问题2根据菜单和对应的营养表，怎么点菜使得营养全、费用少？西安电子科技大学理学院数学系杨有龙问题2A西班牙煎蛋B炒鸡丁C色拉D牛排E土豆F 洋葱炒肝菜单101516261224欢迎用餐西安电子科技大学理学院数学系杨有龙西安电子科技大学理学院数学系杨有龙1001F 0110E 0001D 1100C 0011B 1101A 矿物质维生素碳水化合物蛋白质营养成分列表内容提要背景问题覆盖问题覆盖问题的求解西安电子科技大学理学院数学系杨有龙2 /30西安电子科技大学理学院数学系杨有龙背景知识——图的表示一个图是由“顶点”集合和“边”集合所构成，边被看成图的不同顶点的无序对.v 5v 1v 4v 2v 3e 2e 7e 3e 4e 6e 5e 1(,)G V E =(,)v w E ∈V E西安电子科技大学理学院数学系杨有龙12345{,,,,}V v v v v v =五个顶点1234567{,,,,,,}E e e e e e e e =七条边西安电子科技大学理学院数学系杨有龙V 1 V 2V 3V 4 V 501001*0110**011***01****0⎛⎞⎜⎟⎜⎟⎜⎟⎜⎟⎜⎟⎜⎟⎝⎠V 1V 2V 3V 4V 5图的表示矩阵用一个上三角形矩阵表示图的顶点之间是否有边相连，若有边则矩阵元素为1，否则为0，此矩阵称为图的表示矩阵。
离散模型q值法数学建模
!
基于q值的离散数学建模是一种在控制工程和智能决策中用于解决决策问题的常用方法。
它将每一种可行的决策都与其相关的期望值产生的“好坏”进行比较，以分析问题并找出好的决策。
大多数Q值方法都是针对不同可能的非确定性模型，例如驱动器分类、动作点击和偏好收购等，以确定“最好”的行动或策略，并以关联参数对比不同结果状态来比较。
q值方法表达类似概率偏好的关系，可以在多种类型的离散模型中应用。
互联网领域充满许多非确定性模型，以及不同的结果状态，并且q值法可以用来优化决策的效率。
例如，在单机游戏中，玩家可以使用q值法来对不同的状态行动进行确定性的估计，从而找出最好的行动。
另外，在自然语言处理（NLP）中，q值可以用于计算和识别搜索引擎上搜索结果状态的相似性和差异。
此外，用户调查满意度也可以采取此方法，例如在实验室测试和其他专业仿真分析环境中，使用q值可以更快地对当前结果进行分析和行动。
总而言之，基于q值的离散数学建模是一种常用的决策方法，可以在互联网领域中大量应用，帮助优化能源分配选择，并确定最优的行动策略和解决方案。
第七章图在自然界和人类社会的实际生活中，用图形来描述和表示某些事物之间的关系既方便又直观。
例如用工艺流程图来描述某项工程中各工序之间的先后关系，用网络图来描述某通讯系统中各通讯站之间信息传递关系，用开关电路图来描述IC中各元件电路导线连接关系等等。
图论起源于18世纪，它是研究由线连成的点集的理论。
一个图中的结点表示对象，两点之间的连线表示两对象之间具有某种特定关系(先后关系、胜负关系、传递关系和连接关系等)。
事实上，任何一个包含了某种二元关系的系统都可以用图形来模拟。
由于我们感兴趣的是两对象之间是否有某种特定关系，所以图形中两点之间连接与否最重要，而连接线的曲直长短则无关紧要。
由此经数学抽象产生了图的概念。
研究图的基本概念和性质、图的理论及其应用构成了图论的主要内容。
7.1 图的基本概念7.1.1图的定义7.1.1.1无向图定义7.1.1 设A，B是任意集合。
集合{(a,b)|aA且bB}称为A和B的无序积，记为A＆B。
在无序积中，两个元素间的顺序是无关紧要的，即(a,b)＝(b,a)。
定义7.1.2 无向图G是一个二元组<V，E>，记作G＝<V，E>，其中V是一个非空有限集合，其元素称为结点(顶点)。
E是一个V＆V的多重子集，其元素称为边(无向边)。
我们可用平面上的点来表示顶点，两点间的连线表示边，从而将任一个无向图用图形表示出来。
［例7.1.1］无向图G＝<V，E>，其中V={a，b，c，d，e，f}，E={(a,b)，(a,c)，(a,d)，(b,b)，(b,c)，(b,c)，(b,d)，(c,d)}。
7.1.1.2有向图定义7.1.3 有向图G是一个二元组<V，E>，记作G＝<V，E>，其中V是一个非空有限集合，其元素称为顶点，E是一个V V的多重子集，其元素称为有向边或弧，简称为边。
注：1)在有向图G＝<V，E>中，若e=〈u，v〉，则称u和v为e的起点和终点；2)自回路既可看成是有向边又可看成是无向边；3)去掉有向图中边的方向得到的图称为该有向图的基图。
离散建模专业计算机科学与技术班级姓名学号授课教师二 O一七年十二月离散建模就是离散数学与计算机科学技术及ＩT技术应用间得联系桥梁。
也就是学习离散数学得根本目得。
它有两部分内容组成：1、离散建模概念与方法2、离散建模应用实例一、离散建模概念与方法１、１离散建模概念在客观世界中往往需要有许多问题等待人们去解决。
而解决得方法很多,最为常见得方法就是将客观世界中得问题域抽象成一种形式化得数学表示称数学模型，从而将对问题域得求解变成为对数学表示式得求解。
而由于人们对数学得研究已有数千年历史,并已形成了一整套行之有效得对数学求解得理论与方法，因此用这种数学方法去解决实际问题可以取得事倍功半得作用。
而采用这种方法得关键之处就是数学模型得建立，它称为数学建模，而当这种数学模型就是建立在有限集或可列集之上时,此种模型得建立称离散建模。
１、2、离散建模方法（1）两个世界理论在离散建模中有两个世界，一个就是现实世界另一个就是离散世界。
现实世界就是问题域产生得世界,离散世界则就是一种数学世界，它有三个特性：离散世界采用离散数学语言,该语言具有简洁性且表达力丰富。
离散世界所表示得就是一种抽象符号，它就是一种形式化符号体系。
离散世界中得环境简单,它在离散建模时设立，可以屏蔽大量无关信息对问题求解得干扰.为求解问题须将问题域转换成离散模型，然后对离散模型求解,再逆向转换成现实世界中得解、（2)两个世界得转换在离散建模方法中需要构作两种转换，即由现实世界到离散世界得转换以及由离散世界到现实世界得逆转换，而其中第一种转换尤为重要,这种转换我们一般即称之为离散建模。
下面对两种转换作介绍：现实世界到离散世界得转换该转换又称离散建模或简称转换.这种转换就是离散建模方法得核心.它实际上就是将现实世界中得问题转换成离散世界中得离散模型。
这种过程就是将问题域中问题采取屏蔽语义、简化环境、强化关系所形成得一种抽象化、形式化过程,在转换时所要采用下面几种手段:１、选取一种离散语言，亦即就是选择一个离散数学学科门类，(如图论，代数系统，数理逻辑及关系等,也可以选择其中得一些子门类如图论中得树，代数系统中得群论等等）,以此学科得符号体系作为一种形式语言称离散语言。
离散建模专业计算机科学与技术班级姓名学号授课教师二 O 一七年十二月离散建模是离散数学与计算机科学技术及IT技术应用间的联系桥梁。
也是学习离散数学的根本目的。
它有两部分内容组成:1.离散建模概念与方法2.离散建模应用实例一.离散建模概念与方法1.1离散建模概念在客观世界中往往需要有许多问题等待人们去解决。
而解决的方法很多，最为常见的方法是将客观世界中的问题域抽象成一种形式化的数学表示称数学模型，从而将对问题域的求解变成为对数学表示式的求解。
而由于人们对数学的研究已有数千年历史，并已形成了一整套行之有效的对数学求解的理论与方法，因此用这种数学方法去解决实际问题可以取得事倍功半的作用。
而采用这种方法的关键之处是数学模型的建立，它称为数学建模，而当这种数学模型是建立在有限集或可列集之上时，此种模型的建立称离散建模。
1.2.离散建模方法（1）两个世界理论在离散建模中有两个世界，一个是现实世界另一个是离散世界。
现实世界是问题域产生的世界，离散世界则是一种数学世界，它有三个特性：离散世界采用离散数学语言，该语言具有简洁性且表达力丰富。
离散世界所表示的是一种抽象符号，它是一种形式化符号体系。
离散世界中的环境简单，它在离散建模时设立，可以屏蔽大量无关信息对问题求解的干扰。
为求解问题须将问题域转换成离散模型,然后对离散模型求解,再逆向转换成现实世界中的解.（2）两个世界的转换在离散建模方法中需要构作两种转换，即由现实世界到离散世界的转换以及由离散世界到现实世界的逆转换，而其中第一种转换尤为重要，这种转换我们一般即称之为离散建模。
下面对两种转换作介绍：现实世界到离散世界的转换该转换又称离散建模或简称转换。
这种转换是离散建模方法的核心。
它实际上是将现实世界中的问题转换成离散世界中的离散模型。
这种过程是将问题域中问题采取屏蔽语义、简化环境、强化关系所形成的一种抽象化、形式化过程，在转换时所要采用下面几种手段：1.选取一种离散语言，亦即是选择一个离散数学学科门类，（如图论，代数系统，数理逻辑及关系等，也可以选择其中的一些子门类如图论中的树，代数系统中的群论等等），以此学科的符号体系作为一种形式语言称离散语言。
从问题域中确定离散模型的基本对象集合。
从问题域中确定离散模型的静态结构、动态行为以及约束规则。
用离散语言描述这些集合、结构，行为与规则并组成离散模型。
在转换过程中要注意如下几点：所选用的离散语言并不是唯一的，有时可以有多种选择。
所建的离散模型有时可能与传统的数学结构不完全一致，此时须构造新的数学结构以适应建模的需要。
问题域中的环境与平台一般可用离散模型中的约束规则实现。
2.从离散世界到现实世界的转换该转换是一种语义化的转换，它是一种逆向转换，因此又称逆转换，在该转换中是将离散模型的解转换成问题域中的解。
由于离散世界中解的形式是一种抽象的形式化符号体系，没有任何语义，只有赋予问题域中语义后才成为问题域中的解。
两个世界理论与两个世界转换构成了完整的离散建模方法，它可以用下面的图表示。
而离散建模方法的整个过程可以用下面几个步骤表示：在现实世界中给出问题域；将问题域抽象成离散模型；离散模型求解；解的语义化；问题域的解。
1.3.离散建模的步骤在离散建模实际操作中须有若干个步骤的操作过程，它们是：需求描述—问题域形成；离散模型形成；离散模型检验与修改；离散模型求解；解的语义化及问题域解的获得。
二 . 离散建模应用实例1.需求描述死锁检测为操作系统中死锁现象出现提供实时报警信号。
操作系统是管理计算机资源，协调计算机用户与资源间的关系，为用户在计算机中顺利运行提供支撑的一种软件系统。
而死锁现象则是用户间为争夺资源而产生的一种矛盾，因此及时发现矛盾及化解矛盾是操作系统重要职能之一。
在操作系统中有两种重要的注视目标，它们是“资源”与“进程”：（1）资源：操作系统是管理计算机中资源的机构，而计算机中的资源包括有CPU资源，内存资源，外部设备资源（如打印机等），通道资源等多种。
（2）进程：在一台计算机中往往可以运行多个程序，而一般运行的程序称为进程。
在资源与进程之间存在着紧密的关联，其中主要的关联是：进程需要资源，只有有了充足的资源，进程才能运行。
在一般情况下，进程在运行前需申请资源，只有获得资源后才能运行，在运行过程中还不断申请资源以获得继续运行的权力，同时也不断释放资源，使资源能得以充分利用；而当进程所申请的资源无法得到时（即表示此资源被它进程所占有），它必须等待，直到它进程对该资源使用完毕并释放后此进程才能获得该资源并继续运行直至进程结束。
因此，进程与资源的关系是一种动态关系，其演化过程可以用下面的图1表示之。
而死锁的产生则是进程演化中的一种特殊现象。
如进程甲占有资源A同时又申请资源B，与此同时进程乙占有资源B同时又申请资源A，此时两进程都无法申请到所需资源，因此只能等待，而等待是无期限的，因而称为死锁。
推而广之，对多个进程与多个资源可能还会出现循环等待的现象，这就是一般意义上的死锁。
2.离散建模及模型建立（1）选择一种离散语言：根据问题域描述，该项死锁检测主要研究资源间的一种特殊关系，因此用关系或图论较为合适，而考虑到图的方法结构性好，直观性强，因而以图论作为建模工具较为合理。
（2）确定研究对象：在离散建模中，操作系统的基本研究对象集合为资源集合与进程集合，设有n个资源与m个进程，它们可表示为：资源集合：R={R1，R2，…，Rn}进程集合：P={P1，P2，…，Pm}（3）资源间的关系：进程P已占有资源Ri且申请资源Rj并处等待中，可用有序偶（Ri，Rj）表示。
而它们的全体则构成一个关系，称资源申请关系S。
（4）模型的建立：以R为结点以S为边可以构成一个有向图G=（R，S）。
它组成了进程资源申请的图模型。
在这个图中的每个边均有权Pi，它表示申请资源的进程。
3.模型求解在问题域中死锁检验的解是资源循环等待，而在图论模型中资源循环等待相当于图中存在回路。
进一步，可以用可达性矩阵计算方法判别是否出现回路，即可达性矩阵的对角线中出现有“1”。
如设可达性矩阵为如图3所示，则判别产生回路的计算公式为D’=d11（+）d22（+）…（+）dnn=1.4.解的语义化最后在模型中所产生的判别公式D’，可将其语义化为：当D’为1时表操作系统已产生死锁；当D’为0时表操作系统未产生死锁。
在例中我们有该图的可达性矩阵为：从而有D’=1，这表明在时刻t时系统产生死锁。
5. 死锁检测的离散建模特点是：（1）该离散建模所建模型简单，可计算且效果好。
（2）该离散建模可以同时用图论与关系实现，但由于在图论中对回路的研究与表示都优于关系，因此用图论较为合适。
（3）在该离散模型中运用图论中的通路与回路以及相应的矩阵计算方法较为方便的解决了死锁问题。
2.3数据库中关系数据模型的离散建模1.需求描述关系数据理论就是用关系理论研究数据模型，在这里涉及到两方面的问题，它们是：数据模型关系模型（1）数据模型数据模型是对数据存储与操纵的抽象表示。
其主要内容是用于存储数据的数据结构表示以及建立在该结构上的数据操作表示。
（2）关系数据模型关系数据模型是一种以二维表的形式表示数据结构又以二维表上的数据操作为特点的数据模型。
1）首先介绍二维表。
二维表又称表，它由表框架及表元组两部分组成。
表框架由表名及n个命名属性列所构成。
表12.1给出了一个表名为student的表框架表1 表名为student的表框架其中sno，sn，sd及sa分别表示属性学号、学生姓名，学生系别及学生年龄等。
在表框架中可以按行存放数据，表中每个数据称元组。
元组由若干个分量组成，其每个分量对应表框架中的一个属性值，如在表框架student中可以有如下的元组：它表示一个学生的相应信息，该学生学号为07001，姓名为张曼英，计算机系，年龄为18岁，它们分别是一个元组中的四个元组分量。
一个表框架可以存储若干个元组。
它们构成了一个完整的二维表。
表12.2给出了二维表的例。
表2 二维表student的例2）接下来，介绍建立在二维表上的数据操作:○1查询操作○2删除操作○3插入操作○4修改操作关系数据模型中的基本逻辑操作共六种：○1表的列指定○2表的行选择○3两表的合并○4查询操作○5删除操作○6插入操作3）关系数据模型的基本面貌：关系数据模型是以二维表为数据结构，以元组为基本数据单位，在它的上面可以有六种基本操作。
它构成了一个数据库系统的基本面貌。
3.关系数据模型离散建模之一—关系代数模型关系代数模型以关系与代数系统为工具研究关系数据模型。
（1）首先从二维表讨论起，二维表实际上是元组的集合，而元组则可视为n 元有序组，因此二维表是n元有序组的集合亦即二维表即是n元关系。
（2）其次，二维表上的操作即是关系的运算。
二维表上的六种基本操作可对应关系的五种运算。
1）插入：R∪R’2）删除R－R’3）两表合并R× S4）列指定：∏Ai1, Ai2,…,Aim ( R )5）行选择σF（R）（3）关系代数由关系所组成的集合A上的五种运算，它们分别是三种二元运算—并，差及笛卡尔运算，以及两种一元运算—投影及选择运算，且都是封闭的，从而构成一个代数系统：（A，∏，σ，∪，－，×）该代数系统称关系代数。
（4）关系代数的运算规则1）并运算满足结合律与交换律：R1∪（R2∪R3）=（R1∪R2）∪R3R1∪R2= R2∪R12）投影运算满足交换律、吸收律及归零律当a1, a 2,…, an与R无关时有∏a1, a 2,…, am (R)=?∏a1, a 2,…, am（∏b1, b 2,…, bn(R)）=∏b1, b 2,…, bn（∏a1, a 2,…, am(R)）当a1, a 2,…, an与R无关而b1, b 2,…, bm与R有关时，∏a1, a 2,…, an, b1, b 2,…, bmR=∏b1, b 2,…, bmR∏a1, a 2,…, am（∏b1, b 2,…, bn(R)）=∏a1, a 2,…, am (R)3）选择运算满足交换律、串接律：σF1（σF2(R)）=σF2（σF1(R)）σF1（σF2(R)）=σF1∧F2(R)4）选择与投影运算满足交换律：σF（∏a1, a 2,…, am(R)）=∏a1, a 2,…, am（σF（R））5）选择对笛卡尔乘积满足分配律：σF（R1×R2）=σFR1×σFR2当F与R无关，此时有：σFR= R，因此有：若F仅涉及R1有：σF（R1×R2）=σF（R1）×R2若F仅涉及R2有：σF（R1×R2）= R1×σF（R2）若F= F1∧F2，而F1仅涉及R1；F2仅涉及R2，有：σF（R1×R2）=σF1（R1）×σF2（R2）6）投影对笛卡尔乘积满足分配律：∏a1, a 2,…, an（R1×R2）=∏a1, a 2,…, anR1×∏a1, a 2,…, an R2（5）关系代数模型关系代数及其七组运算规则组成了关系代数模型。
