《离散数学》教学⼤纲
《离散数学》课程教学⼤纲
课程编号：
课程中⽂名称：离散数学
课程英⽂名称：Discrete mathematics
课程类型：考查课
课程性质：专业技术基础课
总学时： 54学时理论授课学时： 46学时实验（实践）学时：8学时
学分：3分
适⽤对象：信息管理与信息系统、信息⼯程本科
先修课程：⾼等数学线性代数
⼀、编写说明
（⼀）制定⼤纲的依据
依据我系信息管理与信息系统、信息⼯程专业学科体系和特⾊化⼈才培养⽬标的要求，制定编写了该教学⼤纲，在内容上突出了《离散数学》课程的基本理论、基本知识和基本技能，反映现代科学技术的发展趋势，体现了我系的特⾊化⼈才培养模式。
（⼆）课程简介
离散数学，是现代数学的⼀个重要分⽀，是以研究离散量的结构和相互间的关系为主要⽬标，其研究对象⼀般是有限个或可数个元素。
《离散数学》内容主要包括: 数理逻辑中命题演算、谓词演算等形式逻辑的推理规律；集合的概念、运算及应⽤，集合内元素间的关系以及集合之间的关系,⽆限集的特性；抽象代数的基本理论和应⽤,格与布尔代数图论学科的基本概念、欧拉图、哈密尔顿图、最⼩路径算法、中国邮路问题、树及平⾯图的基本理论；
通过该课程可以培养学⽣的抽象思维和慎密的概括能⼒，该课程主要适⽤于⾃动控制、电⼦⼯程、管理科学等有关专业，是计算机专业的必修课。
（三）课程性质、⽬的和任务
《离散数学》课程是为计算机科学与技术专业的学⽣开设的⼀门专业基础课程。随着计算机科学的发展和计算机应⽤领域的⽇益⼴泛，迫切需要适当的数学⼯具来解决计算机科学各个领域中提出的有关离散量的理论问题，离散数学就是适应这种需要⽽建⽴的，它综合了计算机科学中所⽤到的研究离散量的各个数学课题，并进⾏系统、全⾯的论述，从⽽为研究计算机科学及相关学科提供了有利的理论基础和⼯具。是学习后续专业课程不可缺少的数学⼯具，如：⾼级语⾔、数据结构、编译原理、操作系统、可计算性理论、⼈⼯智能、形式语⾔与⾃动机、信息管理与检索以及开关理论等，离散数学也是研究⾃动控制、管理科学、电⼦⼯程等的重要⼯具。
离散数学知识点总结
离散数学是数学中的一个分支，研究离散对象及其关系的数学理论。它与连续数学形成鲜明的对比，连续数学主要研究连续对象和其性质。离散数学在计算机科学、信息科学、电子工程等领域具有重要的应用价值。下面将对离散数学的主要知识点进行总结。
1.命题逻辑：命题逻辑研究由命题符号组成的复合命题及其逻辑关系。其中命题是一个陈述性的语句，可以是真或假。命题逻辑包括命题的逻辑运算、真值表、命题的等价、充分必要条件等。
2.谓词逻辑：谓词逻辑是对命题逻辑的扩充，引入了量词、谓词和项。它的研究对象是命题函数，可以表示个体之间的关系。谓词逻辑包括谓词的运算、量词的运算、公理化和推理规则等。
3.集合论：集合论是研究集合及其操作的数学分支。集合是一种由确定的对象组成的整体。集合论包括集合的基本运算（交、并、差、补）、集合的关系（包含、相等、子集、真子集）以及集合的运算律和推导定理等。
5.组合数学：组合数学是研究物体的组合与排列问题的数学分支。它包括排列、组合、分配、生成函数等内容，经常应用于计数和概率问题中。
6.图论：图论是用来描述物体间其中一种关系的图形结构的数学理论。它研究的对象是由顶点和边构成的图，包括无向图、有向图、带权图等。图论研究的内容包括图的性质、连通性、路径、回路、树、图的着色等。
7.代数系统：代数系统是一种由一组元素及其相应的运算规则构成的数学结构。常见的代数系统有群、环、域、格等，它们分别研究了集合上的不同运算规律和结构。 8.布尔代数：布尔代数是一种应用于逻辑和计算机的代数系统。它以真和假为基础，通过逻辑运算（与、或、非）构成了布尔代数。布尔代数在计算机硬件设计和逻辑推理中广泛应用。
9.图的同构与图的着色：图的同构是指两个图在结构上相同，也就是说，它们具有相同的顶点和边的连接关系。图的同构判断是一个NP难问题，需要借助于图的着色等方法来判断。图的着色是给图的顶点分配颜色，使得相邻顶点的颜色不同。图的着色问题也是一个经典的组合优化问题。
离散数学问题
1.离散数学学的什么？
集合论、代数系统、图论、数理逻辑等。
2.什么是集合？
由离散个体构成的整体的称为集合，称这些个体为集合的元素。
集合元素的性质：无序性、相异性、确定性、任意性
3.什么是幂集？
集合的全体子集构成的集合叫做幂集。∣P(A)=2n∣|P(A)=2^n|∣P(A)=2n∣
4.什么是笛卡尔乘积？
5.二元关系的定义
如果一个集合满足下列条件之一：
集合非空，且它的元素都是有序偶；
集合是空集；
则称该集合为一个二元关系，简称为关系，记作RRR.
6.等价关系和等价类的定义
等价关系：设RRR为非空集合AAA上的一个关系，如果RRR是自反的、对称的和传递的，则称RRR为AAA上的等价关系。
等价类：设RRR是集合AAA上的等价关系，与AAA中的一个元素aaa有关系的所有元素的集合叫做aaa的等价类。 7.偏序关系的定义
设 R R R 为非空集合 A A A 上的一个关系，如果 R R R 是自反的、反对称的和可传递的，则称 R R R 是集合 A A A 上的偏序关系，简称偏序，记作 “ ⩽ \leqslant ⩽”.
偏序关系 ⩽ \leqslant ⩽——自反性、反对称性、传递性
逆序关系<<<——反自反、反对称性、传递性
逆序关系的自反闭包是偏序关系。
8.空关系
空关系是一种特殊关系，指关系集 A × B A×B A×B 中的子集 ϕ
\phi ϕ。非空集合中的空关系是反自反的、对称的、反对称的和传递的，但不是自反的；空集合中的空关系则是自反的、反自反的、对称的、反对称的和传递的。
9.怎么判断两个无穷集合的大小？
对无限集，通过建立一一对应的方法可以比较它们元素个数的大小（在集合论中称为势），以整数集ZZZ和偶数集AAA为例，如果将ZZZ中的每一个元素都乘以222，则都可以在AAA中找到对应的偶数元素，即ZZZ和AAA中的元素是一一对应的，也就是说这两个集合是等势的。值得注意的是，偶数集合是整数集合的一部分，但它包含的元素个数却跟整数集合一样多。
【半群】G非空，·为G上的二元代数运算，满足结合律。
【群】（非空，封闭，结合律，单位元，逆元）恰有一个元素1适合1·a=a·1=a,恰有一个元素a-1适合a·a-1=a-1·a=1。
【Abel群/交换群】·适合交换律。可能不只有两个元素适合x2=1
【置换】n元置换的全体作成的集合Sn对置换的乘法作成n 次对称群。
【子群】按照G中的乘法运算·,子集H仍是一个群。单位子群{1}和G称为平凡子群。
【循环群】G可以由它的某元素a生成,即G=（a）。a所有幂的集合an，n=0，±1，±2，…
做成G的一个子群，由a生成的子群。若G的元数是一个质数，则G必是循环群。
n元循环群（a）中,元素ak是（a）的生成元的充要条件是（n，k）=1。共有（n）个。
【三次对称群】{I（12）（13）（23）（123）（132）}
【陪集】a，b∈G，若有h∈H，使得a =bh，则称a合同于b（右模H），a≡b（右mod H）。H有限，则H的任意右陪集aH的元数皆等于H的元数。任意两个右陪集aH和bH或者相等或者不相交。
求右陪集：H本身是一个；任取aH而求aH又得到一个；任取bH∪aH而求bH又一个。G=H∪aH∪bH∪…
【正规子群】G中任意g，gH=Hg。（H=gHg-1对任意g∈G都成立）
Lagrange定理 G为有限群，则任意子群H的元数整除群G的元数。
1有限群G的元数除以H的元数所得的商，记为（G：H），叫做H在G中的指数，H的指数也就是H的右（左）陪集的个数。
2设G为有限群,元数为n,对任意a∈G，有an=1。
3若H在G中的指数是2，则H必然是G的正规子群。证明：此时对H的左陪集aH，右陪集Ha，都是G中元去掉H的所余部分。故Ha=aH。
4G的任意多个子群的交集是G的子群。并且，G的任意多个正规子群的交集仍是G的正规子群。
5 H是G的子群。N是G的正规子群。命HN为H的元素乘N的元素所得的所有元素的集合，则HN是G的子群。
