文档介绍：该【IASK离散数学必备知识点总结文档 】是由【雨林书屋】上传分享，文档一共【16】页，该文档可以免费在线阅读，需要了解更多关于【IASK离散数学必备知识点总结文档 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。(word完满版)失散数学必备知识点总结,介绍文档
(word完满版)失散数学必备知识点总结,介绍文档
1/16
(word完满版)失散数学必备知识点总结,介绍文档
总结失散数学知识点
第二章命题逻辑
1.→,前键为真,后键为假才为假;<—>,相同为真,不一样样为假;
:极小项(m)之和;主合取范式:极大项(M)之积;
,命题变元的必然为1,否定为0,求极大项时相反;
,每个变元或变元的否定只能出现一次,求极小项
时变元不够合取真,求极大项时变元不够析取假;
,为保证编码不错,命题变元最好按P,Q,R的序次依次写;
,值为0的项为极大项;
,这2n为(0~2n-1)恰巧为化简完后的主析取加主合取;
,永假式没有主析取范式;
(=>):真值表法;分析法(假设前键为真推出后键
为真,假设前键为假推出后键也为假)
:P规则,T规则
①真值表法;②直接证法;③归谬法;④附加前提法;
第三章谓词逻辑
:谓词只有一个个体,一元谓词描述命题的性质;
多元谓词:谓词有n个个体,多元谓词描述个体之间的关系;
→,存在量词用合取^;
,先消存在量词,再消全称量词;
第四章会集
,表示自然数集,1,2,3,不包括0;
:会集A中不一样样元素的个数,|A|;
:给定会集A,以会集A的所有子集为元素构成的会集,P(A);
,幂集P(A)有2n个元素,|P(A)|=2|A|=2n;
:(等价关系)
①每一个分划都是由会集A的几个子集构成的会集;
②这几个子集订交为空,相并为全(A);
:
分划:每个元素均应出现且仅出现一次在子集中;
覆盖:只要求每个元素都出现,没有要求只出现一次;
第五章关系
,会集B有n个元素,则笛卡尔A×B的基数为mn,A到B上能够定义2mn种不一样样的关系;
,则|A×A|=n2,A上有2n2个不一样样的关系;
:自反性,对称性,传达性;
空关系的性质:反自反性,反对称性,传达性;
(word完满版)失散数学必备知识点总结,介绍文档
(word完满版)失散数学必备知识点总结,介绍文档
2/16
(word完满版)失散数学必备知识点总结,介绍文档
全封闭环的性质:自反性,对称性,反对称性,传达性;
(domR):所有元素x构成的会集;
后域(ranR):所有元素y构成的会集;
:r(R)=RUIx;
对称闭包:s(R)=RUR-1;
传达闭包:t(R)=RUR2UR3U
:会集A上的二元关系R满足自反性,对称性和传达性,
则R称为等价关系;
:会集A上的关系R满足自反性,反对称性和传达性,
则称R是A上的一个偏序关系;
={<x,y>|x,y属于A,y遮住x};
:会集A中没有比它更小的元素(若存在可能不独一);极大元:会集A中没有比它更大的元素(若存在可能不独一);最小元:比会集A中任何其他元素都小(若存在就必然独一);最大元:比会集A中任何其他元素都大(若存在就必然独一);
:B是A的子集
上界:A中的某个元素比B中任意元素都大,称这个元素是B的
上界(若存在,可能不独一);
下界:A中的某个元素比B中任意元素都小,称这个元素是B的
下界(若存在,可能不独一);
上确界:最小的上界(若存在就必然独一);
下确界:最大的下界(若存在就必然独一);
(word完满版)失散数学必备知识点总结,介绍文档
(word完满版)失散数学必备知识点总结,介绍文档
3/16
(word完满版)失散数学必备知识点总结,介绍文档
第六章函数
|X|=m,|Y|=n,则从X到Y有2mn种不一样样的关系,有nm种不一样样的函数;
,能够有2n2种不一样样的关系,有nn种不一样样的函数,有n!种不一样样的双射;
|X|=m,|Y|=n,且m<=n,则从X到Y有Amn种不一样样的单射;
:f:X-Y,对任意x1,x2属于X,且x1≠x2,若f(x1)≠f(x2);
满射:f:X-Y,对值域中任意一个元素y在前域中都有一个或多个元素对应;
双射:f:X-Y,若f既是单射又是满射,则f是双射;
:fog=g(f(x));
:A-B,g:B-C,那么
①若是f,g都是单射,则fog也是单射;②若是f,g都是满射,则fog也是满射;③若是f,g都是双射,则fog也是双射;④若是fog是双射,则f是单射,g是满射;
第七章代数系统
:会集A上的二元运算就是A2到A的照耀;
会集A上可定义的二元运算个数就是从A×A到A上的照耀的个数,即从从A×A到A上函数的个数,若|A|=2,则会集A上的二元运算的
(word完满版)失散数学必备知识点总结,介绍文档
(word完满版)失散数学必备知识点总结,介绍文档
4/16
(word完满版)失散数学必备知识点总结,介绍文档
个数为22*2=24=16种;
判断二元运算的性质方法:①封闭性:运算表内只有所给元素;②交换律:主对角线两边元素对称相等;③幂等律:主对角线上每个元素与所在行列表头元素相同;④有幺元:元素所对应的行和列的元素依次与运算表的行和列相同;⑤有零元:元素所对应的行和列的元素都与该元素相同;
:<A,*>,<B,^>,满足f(a*b)=f(a)^f(b),则f为由<A,*>到<B,^>
的同态照耀;若f是双射,则称为同构;
第八章群
:封闭性;
半群的性质:封闭性,结合律;
含幺半群(独异点):封闭性,结合律,有幺元;群的性质:封闭性,结合律,有幺元,有逆元;
;
(交换群):封闭性,结合律,有幺元,有逆元,交换律;
;
;
(word完满版)失散数学必备知识点总结,介绍文档
(word完满版)失散数学必备知识点总结,介绍文档
5/16
(word完满版)失散数学必备知识点总结,介绍文档
第十章格与布尔代数
:偏序会集A中任意两个元素都有上、下确界;
:
自反性
a≤a对偶:a≥a
反对称性
a≤b^b≥a=>a=b
对偶:a≥b^b≤a=>a=b
传达性
a≤b^b≤c=>a≤c
对偶:a≥b^b≥c=>a≥c
最大下界描述之一
a^b≤a对偶avb≥a
A^b≤b对偶avb≥b
5)最大下界描述之二
c≤a,c≤b=>c≤a^b
对偶c≥a,c≥b=>c≥avb
结合律a^(b^c)=(a^b)^c
对偶av(bvc)=(avb)vc
等幂律
a^a=a对偶ava=a
(word完满版)失散数学必备知识点总结,介绍文档
(word完满版)失散数学必备知识点总结,介绍文档
6/16
(word完满版)失散数学必备知识点总结,介绍文档
汲取律
a^(avb)=a对偶av(a^b)=a
9)a≤b<=>a^b=aavb=b
a≤c,b≤d=>a^b≤c^davb≤cvd
保序性
b≤c=>a^b≤a^cavb≤avc
12)分配不等式
av(b^c)≤(avb)^(avc)
对偶a^(bvc)≥(a^b)v(a^c)
)模不等式
a≤c<=>av(b^c)≤(avb)^c
:满足a^(bvc)=(a^b)v(a^c)和av(b^c)=(avb)^(avc);
:该格没有任何子格与钻石格或五环格同构;
,分配格必然是模格;
:会集A中的某个元素a大于等于该会集中的任何元素,则
称a为格<A,<=>的全上界,记为1;(若存在则独一)
全下界:会集A中的某个元素b小于等于该会集中的任何元素,
则称b为格<A,<=>的全下界,记为0;(若存在则独一)
:有全上界和全下界的格称为有界格,即有0和1的格;
:在有界格内,若是a^b=0,avb=1,则a和b互为补元;
:在有界格内,每个元素都最罕有一个补元;
(布尔格):既是有补格,又是分配格;
(word完满版)失散数学必备知识点总结,介绍文档
(word完满版)失散数学必备知识点总结,介绍文档
7/16
(word完满版)失散数学必备知识点总结,介绍文档
:一个有补分配格称为布尔代数;
第十一章图论
:两点之间有边连接,则点与点毗邻;
:两点之间有边连接,则这两点与边关系;
:只有一个孤立点构成的图;
:不含平行边和环的图;
:n个节点任意两个节点之间都有边相连的简单无向图;
有向完满图:n个节点任意两个节点之间都有边相连的简单有向图;
(n-1)/2条边,有向完满图有n(n-1)条边;
-正则图:每个节点度数均为r的图;
:节点度数的总和等于边的两倍;
,度数为奇数的节点个数必然是偶数个;
,所有节点入度之和等于所有节点的出度之和;
;
:对于图中的两个节点vi,vj,若存在连接vi到vj的路,则称vi与vj相互可达,也称vi与vj是连通的;在有向图中,若存在vi到vj的路,则称vi到vj可达;
:有向图章任意两节点相互可达;
单向连通:图中两节点最罕有一个方向可达;
(word完满版)失散数学必备知识点总结,介绍文档
(word完满版)失散数学必备知识点总结,介绍文档
8/16
(word完满版)失散数学必备知识点总结,介绍文档
弱连通:无向图的连通;(弱连通必然是单向连通)
:删去图中的某些点后所得的子图不连通了,若是删去其
他几个点后子图之间还是连通的,则这些点构成的会集称为点割集;
割点:若是一个点构成点割集,即删去图中的一个点后所得子图
是不连通的,则该点称为割点;
:M(G),mij是vi与ej关系的次数,节点为行,边为列;
无向图:点与边没关系关系数为0,有关系为1,有环为2;
有向图:点与边没关系关系数为0,有关系起点为1终点为-1,
关系矩阵的特点:
无向图:
①行:每个节点关系的边,即节点的度;
②列:每条边关系的节点;
有向图:
③所有的入度(1)=所有的出度(0);
:A(G),aij是vi毗邻到vj的边的数目,点为行,点为列;
:P(G),最少存在一条回路的矩阵,点为行,点为列;
P(G)=A(G)+A2(G)+A3(G)+A4(G)
可达矩阵的特点:表示图中任意两节点之间可否最少存在一条路,
以及在任何节点上可否存在回路;
A(G)中所有数的和:表示图中路径长度为1的通路条数;
A2(G)中所有数的和:表示图中路径长度为2的通路条数;
A3(G)中所有数的和:表示图中路径长度为3的通路条数;
(word完满版)失散数学必备知识点总结,介绍文档
(word完满版)失散数学必备知识点总结,介绍文档
9/16
(word完满版)失散数学必备知识点总结,介绍文档
A4(G)中所有数的和:表示图中路径长度为4的通路条数;
P(G)中主对角线所有数的和:表示图中的回路条数;
:B(G),vi到vj有路为1,无路则为0,点为行,点为列;
:毗邻矩阵元素为1的用权值表示,为0的用无量大表
示,节点自己到自己的权值为0;
:只接见每个节点一次,经过的节点和边构成的子图;
:深度优先;广度优先;
深度优先:
①选定初步点v0;
②选择一个与v0毗邻且未被接见过的节点v1;
③从v1出发按毗邻方向连续接见,当遇到一个节点所
有毗邻点均已被接见时,回到该节点的前一个点,再追求未被接见过的毗邻点,直到所有节点都被接见过一次;
广度优先:
①选定初步点v0;
②接见与v0毗邻的所有节点v1,v2,,vk,这些作为
第一层节点;
③在第一层节点中选定一个节点v1为起点;
④重复②③,直到所有节点都被接见过一次;
:拥有最小权值(T)的生成树;
:
克鲁斯卡尔方法;管梅谷算法;普利姆算法;
(word完满版)失散数学必备知识点总结,介绍文档
(word完满版)失散数学必备知识点总结,介绍文档
10/16
(word完满版)失散数学必备知识点总结,介绍文档