⑴ 离散数学基本知识
总结 离散数学知识点 命题逻辑
→，前键为真，后键为假才为假；<—>，相同为真，不同为假；
主析取范式：极小项(m)之和；主合取范式：极大项(M)之积；
求极小项时，命题变元的肯定为1，否定为0，求极大项时相反；
求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假；
求范式时，为保证编码不错，命题变元最好按P,Q,R的顺序依次写；
真值表中值为1的项为极小项，值为0的项为极大项；
n个变元共有个极小项或极大项，这为(0~-1)刚好为化简完后的主析取加主合取；
永真式没有主合取范式，永假式没有主析取范式；
推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假)
10.命题逻辑的推理演算方法：P规则，T规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 谓词逻辑
一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n个个体，多元谓词描述个体之间的关系；
全称量词用蕴含→，存在量词用合取^;
既有存在又有全称量词时，先消存在量词，再消全称量词； 集合
N，表示自然数集，1,2,3……，不包括0；
基：集合A中不同元素的个数，|A|；
幂集：给定集合A，以集合A的所有子集为元素组成的集合，P(A)；
若集合A有n个元素，幂集P(A)有个元素，|P(A)|==；
集合的分划：(等价关系) ①每一个分划都是由集合A的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)；
集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 关系
若集合A有m个元素，集合B有n个元素，则笛卡尔A×B的基数为mn，A到B上可以定义种不同的关系；
若集合A有n个元素，则|A×A|=，A上有个不同的关系；
⑵ 离散数学 第二章 集合
一个 集合 是一些对象的整体
序列 和集合的不同之处是要考虑次序数字系统包括众所周知的十进制，二进制等等
关系 是序偶的集合
函数 是关系的一个特例
一个集合是一些对象的整体
可以用枚举法描述它:A={1,2,3,4}
也可以列出其元素的性质来描述:B={x│x是正偶数}
如果X是一个有限集合，令| X |=X中元素的个数，
没有元素的集合称为空集(或零集)用符号∅表示,∅={}，
两个集合X和Y有相同的元素,说两个集合相等，记为X=Y。
子集
设 X 和 Y 是集合。如果X的所有元素都是Y的元素，我们说X是Y的子集,写为X⊆Y。
真子集
如X是Y的子集但X不等于Y,则X是Y的一个真子集。记为：X⊊Y
空集是任何集合的子集。
集合X的所有子集的集合,称为X的幂集，用P(×)表示。
并集、交集、差集
并集XUY={x|x∈X or y ∈Y}
交集X∩Y= {x|x∈X and y∈ Y}
差集X-Y= {x|x∈X or x ∉ Y}
不相交 X∩Y=∅；
U：全集 X：子集
则U-X为X的补集
一个由集合X的非空子集的整体组成的S，如X的每个元素都只属于S的某一个元素，S就称为X的一个划分。
笛卡尔积
—个由两个元素组成的有序对(或序偶)，写为(a,b)
(a,b)=(c,d)当且仅当a=c,b=d. X,Y集合，X×Y称为X和Y的笛卡儿积
一个序列(或有序组)是一个表,要计及其元素出现的次序。
如果s是一个序列，一般的，s.表示序列的第n项。我们把n称为序列的下标。
序列3,5,5,7,8,8,13是增序列。对于所有的n, S n >S n+1 ,则称S n 为增序列。
对于n=m,m+1,..,令{S n }是一个序列，且令n1，n2,...是一个增序列，值在{m,m+1,..}中,满足n k <n k+1 ，称序列{S nk }是{S n }的一个子序列
X 集合
X* X上所有串的集合
α串,| α |串的长度。
如果α和β是两个串，由α后面跟着β所组成的串α β ,称为α和β的连接。
①比特bit ②二进制系统,16进制系统,8进制系统 ③系统的基数
这个就不多阐述了，计组中已经学过了！
关系可以想成一张表，其中列出了一些元素和其他元素之间的关系。
X到Y的关系R,是笛卡儿积X*Y的一个子集。如果(x, y)∈R，我们写为xRy且说x和y有关。当X=Y，我们称R是X上的(二元)关系。
定义 ：
令S是集合X的一个划分。 定义xRy:
对于S的某些集合干,x和y都属于T。则R是自反，对称和传递的。
X上的一个自反的，对称的和传递的关系称为X上的一个等价关系。
令R是集合×上的一个等价关系。对于每个a∈X，
令[a]={x∈X]xRa};则s={[a]la∈X}是X的一个划分。
令R是集合x上的一个等价关系集合[a]，称为由关系R确定的x的等价类。
令R表示一个有限集合x上的等价关系。如每个等价类有r个元素,则共有|X|/r个等价类。
一个表示从X到Y的关系的方法是使用矩阵。如果xRy，则×行y列的元素之值为1,否则，其值为0。这即是关系矩阵。
定理
R₁的关系(X到Y)矩阵A₁，R₂的关系(到Z)矩阵A₂。
R₁○R₂的关系矩阵:
在矩阵的积A₁A₂中，把非0项用1代替而得的矩阵。
函数是特殊的关系。
R的定义域=
{x∈X│|存在y ∈ Y,(×,y) ∈R}f 关系，f函数，f的定义域=X，且.(x,y')在f 中，y=y'。
⑶ 离散数学
集合论
世界上各门学科与各个领域的研究与应用中,都有特定的研究的对象与目标。这些研究对象与目标呈群体形式出现,为研究它的一般性规则与特点,就出现了集合论。
集合论是一门最基础的学科,它对人类社会中的所有学科具有指导性作用。
集合论的基本内容包括三个方面,它们是:
集合论基础。
关系:关系是建立在集合论基础上的一种特殊集合,它研究客观世界中事物间关联的规则。
函数:函数是一种特殊的规范化的关系。
集合之间的关系：相离，相交，相等。
集合概念的基本性质：
1.集合元素的确定性
2.集合元素的相异性:集合中每个元素均是不相同的。如有S={a,b},则a,b必不相同的。
3.集合元素的不重复性:集合中不出现有相重复的元素,如{a,b,b,c}与{a,b,c}是一样的。
4.集合元素的无序性:集合中元素与其排列无关。如{a,b,c}与{ b,a,c}及{ c,a,b }均是一样的。
5.集合与元素的相异性:集合与元素是两个不同概念,集合不等同于元素。
定义三个最基本的运算:并运算、交运算以及补。
给出三个运算的21个规则:
1.交换律:
A∪B=B∪A
A∩B=B∩A
2.结合律:
A∪(B∪C)=(A∪B)∪C
A∩(B∩C)=(A∩B)∩C
3.分配律:
A∪(B∩C)=(A∪B)∩(A∪C)
A∩(B∪C)=(A∩B)∪(A∩C)
4.等幕律:
A∪A=A
A∩A=A
5.双否定律:
~(~A)=A
6.互补律:
A∪~A=E
A∩~A=空集
~E=空集
~空集=E
7.同一律:
A∩E=A
A∪空=A
A∩空=空
A∪E=E
8.吸收律:
A∪(A∩B)=A
(1-18)
A∩(A∪B)=A
(1-19)
9.德.摩根(De Morgan)律:
~(A∪B)=~A∩~B
~(A∩B)=~A∪~B
集合幂运算:由集合S的所有子集(包括空集及S自身)所组成元素的运算称S幂运算,可记为p(S),也可记为2 S ,而其所得到的集合S’则称为S的幂集,即:p(S)= S’。
序偶:两个按一定次序排列的元素a与b组成一个有序序列,称为序偶,并可记为:(a,b),其中a与b分别可称为(a,b)的第一分量与第二分量。
笛卡尔乘:集合A与B中将A中元素作为第一分量,B中元素作为第二分量构作的所有序偶所形成序偶集的过程,称笛卡尔乘。可记为A×B。其所形成的结果集C是一个序偶集,叫A与B的笛卡尔乘积,也可简称笛卡尔积。可表示如下:C=A×B={(a,b)| a属于A,b属于B}。
数理逻辑
数理逻辑是用数学方法(即形式化方法)研究形式逻辑演绎推理规则的科学,是一门研究演绎推理规则的数学。
思维形式化：学习数理逻辑首先要学会将一个形式逻辑问题转换成命题逻辑或谓词逻辑中的公式,即思维的形式化。在思维形式化中用若干基本形式化符号:
(1)个体常量:a,b,c,…;
(2)个体变量:x,y,z,…;
(3)函数符:f,g,h,…;
(4)谓词符:P,Q,R,…;
(5)联结词:,∧,∨,,;
(6)量词符:,;
(7)括号:(,)。
原子公式：
设P是n元谓词符,t 1 ,t 2 ,…,t n 为项,则P(t 1 ,t 2 ,…,t n )是原子公式。
命题公式：
(1)命题是公式;
(2)如果P是公式则(非P)是公式;
( 3 ) 如 果 P , Q 是 公 式 则 ( P∨Q ) ,
(P∧Q),(P->Q)及(P<->Q)是公式;
(4)公式由且仅由有限次应用(1)(2)(3)而得。
谓词逻辑公式:
(1)原子公式是公式;
(2)如A,B是公式,则(非A),(A∨B),
(A∧B),(A->B)及(A<->B)是公式;
(3)如A是公式,x是个体变元,则(任意xA),(存在xA)为公式;
(4)公式由且仅由有限次使用(1)-(3)而得。
推理形式化
(1)初级形式化推理
包括等式推理与蕴含推理,由两部分组成:
推理规则
推理过程
应用命题逻辑、谓词逻辑中的基本等式、基本蕴含式与相应的推理规则
图论
图论用“结点”表示事物,用“边”表示事物间的联系,并用“结点”与“边”所构成的图研究客观事物。
为便于计算,建立了图的矩阵表示。这样可以将图论研究与计算相结合。
图的形式很多,重点对树进行研究。
图论应掌握的:
1、图论的基本概念
2、基本定理
3、图的矩阵运算
4、树
图论中的基本概念
1、图的概念
2、有向图与无向图
3、几种特殊的图(零图、平凡图、完全图、补图、简单图与多重图、有权图、同构图)
4、通路、回路(简单、基本)
5、图的连通性(可达性、连通图、欧拉、哈密尔顿)
图论中的的基本定理
1、结点与边的关系
2、基本通路(回路)长度的定理:(n,m)图基本通路(回路)长度小于等于n-1(n)
3、欧拉图、欧拉通路
4、哈密尔顿图、哈密尔顿通路
图的矩阵计算
1、图的邻接矩阵
2、通路计算
3、连通性计算
树
1、树的定义
2、树的性质
3、外向树与内向树
4、二元树与多元树
5、生成树
6、生成树寻找算法