离散结课论文.docx

离散结课论文学生姓名：张子涵学 号：201514620109专业班级：15网络技术一班学 院：信息工程学院指导教师：王新春2016年05月12日目录第一章 集合、关系与函数简介 3包含排斥原理在生活中的应用 4关于集合论的历史 7历史上关于集合论的异议 7第二章 图论简介 8起源 8著名的“四色猜想” 8欧拉图和哈密顿图 11树 11生活中的应用 11第三章数理逻辑简介 17产生 17谓词命题 18数理逻辑对计算机科学的影响 18电路中的数理逻辑 18数理逻辑在生活中的应用 19第四章 学习心得 20第五章 作业展示 22全文摘要离散数学是传统的逻辑学，集合论（包括函数），数论基础，算法设计，组合分析，离散概率，关系理论，图论与树，抽象代数（包括代数系统，群、环、域等），布尔代数，计算模型（语言与自动机）等汇集起来的一门综合学科。离散数学的应用遍及现代科学技术的诸多领域，它通常研究的领域包括：数理逻辑、集合论、代数结构、关系论、函数论、图论、组合学、数论等。本文主要由集合论、数理逻辑、和图论三部分组成，从这几方面描述了离散数学在生活学习各方面的应用，以及一些有趣的小故事。然后写了自己对于学习离散数学的心得体会，和在学习过程中遇到的典型例题以及整理的笔记。最后还附上了写过的作业。 集合、关系与函数 简介集合是指具有某种特定性质的具体的或抽象的对象汇总成的集体，这些对象称为该集合的元素。确定的对象体聚集一起，对这类总体称为集合。 集合论是从一个对象o和/wiki/%E9%9B%86%E5%90%88_(%E6%95%B0%E5%AD%A6)集合A之间的/wiki/%E4%BA%8C%E5%85%83%E5%85%B3%E7%B3%BB二元关系开始：若o是A的/wiki/%E5%85%83%E7%B4%A0_(%E6%95%B8%E5%AD%B8)元素，可表示为o?∈?A。由于集合也是一个对象，因此上述关系也可以用在集合和集合的关系。 另外一种二个集合之间的关系，称为包含关系。若集合A中的所有元素都是集合B中的元素，则称集合A为B的/wiki/%E5%AD%90%E9%9B%86子集，符号为A???B。例如{1,2}?是{1,2,3}?的子集，但{1,4}?就不是{1,2,3}?的子集。依照定义，任一个集合也是本身的子集，不考虑本身的子集称为真子集。集合A为集合B的真子集/wiki/%E8%8B%A5%E4%B8%94%E5%94%AF%E8%8B%A5当且仅当集合A为集合B的子集，且集合B不是集合A的子集。/wiki/%E6%95%B0数的/wiki/%E7%AE%97%E8%A1%93算术中有许多一元及二元运算，集合论也有许多针对集合的一元及二元运算：集合A和B的/wiki/%E8%81%AF%E9%9B%86联集，符号为A?∪?B，是在至少在集合A或B中出现的元素，集合{1,2,3}?和集合{2, 3, 4}?的联集为集合{1, 2, 3, 4}?。集合A和B的/wiki/%E4%BA%A4%E9%9B%86交集，符号为A?∩?B，是同时在集合A及B中出现的元素，集合{1,2,3}?和集合{2, 3, 4}?的交集为集合{2, 3}?。集合U和A的/wiki/%E8%A1%A5%E9%9B%86相对差集，符号为U?\?A，是在集合U中，但不在集合A中的所有元素，相对差集{1,2,3} \ {2,3,4}?为{1}?，而相对差集{2,3,4} \ {1,2,3}?为{4}?。当集合A是集合U的子集时，相对差集U?\?A也称为集合A在集合U中的/wiki/%E8%A3%9C%E9%9B%86补集。若是研究/wiki/%E6%96%87%E6%B0%8F%E5%9B%BE文氏图，集合U为/wiki/%E5%85%A8%E9%9B%86全集，且可以借由上下文找到全集定义时，会使用Ac来代替U?\?A。集合A和B的/wiki/%E5%AF%B9%E7%A7%B0%E5%B7%AE对称差，符号为A?△?B或A???B，是指只在集合A及B中的其中一个出现，没有在其交集中出现的元素。例如集合{1,2,3}?和{2,3,4}?的对称差为{1,4}?，也是其联集和交集的相对差集(A?∪?B) \ (A?∩?B)，或是二个相对差集的联集(A?\?B) ∪ (B?\?A)。集合A和B的/wiki/%E7%AC%9B%E5%8D%A1%E5%84%BF%E7%A7%AF笛卡儿积，符号为A?×?B，是一个由所有可能的/wiki/%E6%9C%89%E5%BA%8F%E5%AF%B9有序对(a,b)形成的集合，其中第一个对象是A的成员，第二个对象是B的成员。{1, 2}和{red, white}的笛卡儿积为{(1, red), (1, white)