离散数学知识点.docx

说明: 定义:红色表示。 定理性质:橙色表示。 公式:蓝色表示。 算法:绿色表示 页码:灰色表示数理逻辑:命题公式:命题,联结词(Ø,Ù,Ú,®,«),合式公式,子公式公式的真值:赋值,求值函数,真值表,等值式,重言式,矛盾式范式:析取范式,极小项,主析取范式,合取范式,极大项,主合取范式联结词的完备集:真值函数,异或,条件否定,与非,或非,联结词完备集推理理论:重言蕴含式,有效结论,P规则,T规则,CP规则,推理谓词与量词:谓词,个体词,论域,全称量词,存在量词项与公式:项,原子公式,合式公式,自由变元,约束变元,辖域,换名,代入公式语义:解释,赋值,有效的,可满足的,不可满足的前束范式:前束范式推理理论:逻辑蕴含式,有效结论,"-规则(US),"+规则(UG),$-规则(ES),$+规则(EG),推理集合论:集合:集合,外延性原理,Î,Í,Ì,空集,全集,幂集,文氏图,交,并,差,补,对称差关系:序偶,笛卡尔积,关系,domR,ranR,关系图,空关系,全域关系,恒等关系关系性质与闭包:自反的,反自反的,对称的,反对称的,传递的,自反闭包r(R),对称闭包s(R),传递闭包t(R)等价关系:等价关系,等价类,商集,划分偏序关系:偏序,哈斯图,全序(线序),极大元/极小元,最大元/最小元,上界/下界函数:函数,常函数,恒等函数,满射,入射,双射,反函数,复合函数集合基数:基数,等势,有限集/无限集,可数集,不可数集代数结构:运算及其性质:运算,封闭的,可交换的,可结合的,可分配的,吸收律,幂等的,幺元,零元,逆元代数系统:代数系统,子代数,积代数,同态,同构。群与子群:半群,子半群,元素的幂,独异点,群,群的阶数,子群,平凡子群,陪集,拉格朗日(Lagrange)定理阿贝尔群和循环群:阿贝尔群(交换群),循环群,生成元环与域:环,交换环,含幺环,整环,域格与布尔代数:格,对偶原理,子格,分配格,有界格,有补格,布尔代数,有限布尔代数的表示定理图论:图的基本概念:无向图、有向图、关联与相邻、简单图、完全图、正则图、子图、补图,握手定理,图的同构图的连通性:通路,回路,简单通路,简单回路(迹)初级通路(路径),初级回路(圈),点连通,连通图,点割集,割点,边割集,割边,点连通度,边连通度,弱连通图,单向连通图,强连通图,二部图(二分图)图的矩阵表示:关联矩阵,邻接矩阵,可达矩阵欧拉图与哈密顿图:欧拉通路、欧拉回路、欧拉图、半欧拉图,哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图无向树与根树:无向树,生成树,最小生成树,Kruskal,根树,m叉树,最优二叉树,Huffman算法平面图:平面图,面,欧拉公式,Kuratoski定理数理逻辑:命题:具有确定真值的陈述句。否定词符号Ø:设p是一个命题,Øp称为p的否定式。Øp是真的当且仅当p是假的。p是真的当且仅当Øp是假的。【】合取词符号Ù:设p,q是两个命题,命题“p并且q”称为p,q的合取,记以pÙq,读作p且q。pÙq是真的当且仅当p和q都是真的。【】析取词符号Ú:设p,q是两个命题,命题“p或者q”称为p,q的析取,记以pÚq,读作p或q。pÚq是真的当且仅当p,q中至少有一个是真的。【】蕴含词符号®:设p,q是两个命题,命题“如果p,则q”称为p蕴含q,记以p®q。p®q是假的当且仅当p是真的而q是假的。【】等价词符号«:设p,q是两个命题,命题“p当且仅当q”称为p等价q,记以p«q。p®q是真的当且仅当p,q或者都是真的,或者都是假的。【】合式公式:命题常元和变元符号是合式公式;若A是合式公式,则(ØA)是合式公式,称为A的否定式;若A,B是合式公式,则(AÚB),(AÙB),(A®B),(A«B)是合式公式;所有合式公式都是有限次使用(1),(2),(3)、(4)得到的符号串。子公式:如果X是合式公式A的一部分,且X本身也是一个合式公式,则称X为公式A的子公式。【】赋值(指派,解释):设å是命题变元集合,则称函数v:å®{1,0}是一个真值赋值。【】真值表:公式A在其所有可能的赋值下所取真值的表,称为A的真值表。【】重言式(永真式):任意赋值v,vA矛盾式(永假式):任意赋值v,有vA【】等值式:若等价式A«B是重言式,则称A与B等值,记作AÛB。【】基本等值式 双重否定律 ØØAÛA幂等律AÚAÛA,AÙAÛA交换律AÚBÛBÚA,AÙBÛBÙA结合律(AÚB)ÚCÛAÚ(BÚC),(AÙB)ÙCÛAÙ(BÙC)分配律AÚ(BÙC)Û(AÚB)Ù(AÚC),AÙ(BÚC)Û(AÙB)Ú(AÙC)德摩根律 Ø(AÚB)ÛØAÙØB ,Ø(AÙB)ÛØAÚØB^^吸收律A