当前位置:文档之家› 离散数学定义列表

离散数学定义列表

离散数学定义列表(总6页)--本页仅作为文档封面,使用时请直接删除即可----内页可以根据需求调整合适字体及大小--A.定义1.简单命题/原子命题、复合命题2.定义:否定式、否定联结词3.定义:合取式、合取联结词4.定义:析取式、析取联结词定义:蕴含式、前件、后件、蕴含联结词;规定、5.定义:等价式、等价联结词;规定6.联结词的定义(真值表)表、优先级7.命题常项、命题变项(不是命题)、合式公式8.定义:原子命题公式、公式、子公式9.定义:公式层次10.定义:赋值/解释、成真赋值、成假赋值11.定义1..9:真值表12.定义1..10:重言式/永真式、矛盾式/永假式、可满足式13.哑元************************重点:命题逻辑等值演算***************14.定义:等值区别等价式等值式模式:双重否定律、幂等律、交换律、结合律、分配律、德摩根律、吸收律、零律、同一律、排中律、矛盾律、蕴涵等值式、(等价等值式、假言易位、等价否定等值式、归谬论)15.等值演算、置换规则16.定义:文字、简单析取式、简单合取式17.定义:析取范式、合取范式、范式18.定义:极小项、极大项定义:主析取范式、主合取范式********************************一阶逻辑**********************19.个体词、个体常项、个体变项、个体域/论域、全总个体域20.谓词、谓词常项、谓词变项、n元谓词、0元谓词量词、全称量词、存在量词全称蕴含、存在合取 P71********************************集合代数**********************21.定义:子集、包含22.定义:相等23.定义:真子集定义:空集 P139 124.n元集、m元子集、(单元集)25.定义:幂集公式:26.定义:全集27.定义:并集、交集、相对补集、不交28.定义:对称差集29.定义:绝对补集30.定义:广义并231.定义:广义交幂等律、结合律、交换律、分配律、同一律、零律、排中律、矛盾律、吸收律、德摩根律、双重否定律 ,P108 36****************************重点:二元关系***********************32.定义:有序对/序偶33.定义:笛卡尔积性质P11134.定义:二元关系/关系 P139 735.定义:从A到B的二元关系、A上的二元关系、空关系36.定义:A上的全域关系(E)、恒等关系(I)、小于等于关系(L)、整除关系(D)、包含关系(R)37.关系矩阵(x行,y列)、关系图38.定义:定义域、值域、域39.定义:逆关系40.定义:右复合(左复合)41.定义:R在A上的限制、A在R下的像42.定义:关系的n次幂定义:自反、反自反定义:对称、反对称定义:传递43.定义:等价关系(性质) P142 32(4)、4144.定义:等价类45.定义:商集46.定义:划分、划分块 P13447.定义:偏序关系(性质)48.定义:小于、可比49.定义:全序关系/线序关系50.定义:偏序集 P13551.定义:偏序集中顶点的覆盖关系(为画哈斯图) P143 43(2)52.定义:最小元、最大元、极小元、极大元(不懂)定义:上界、下界、最小上界/上确界、最小下界/下确界P143 47***************************函数*******************************53.定义:函数54.定义:函数相等55.定义:从A到B的函数P171 6(8)(9)56.定义:从A到B的函数的集合B A57.定义:A1在ƒ下的像、函数的像、完全原像定义:满射、单射、双射/一一映射 P173 2558.定义: 常函数、恒等函数、单调递增、单调递减、严格单调递减、特征函数、自然映射59.反函数(双射)*************************代数系统*****************************3定义:二元运算(函数)、不封闭P178 P191 T3(2)自身运算60.定义:一元运算定义:可交换/交换律定义:可结合/结合律定义:幂等律、幂等元61.定义:可分配/分配律62.定义:吸收律63.定义:左单位元(右单位元)、单位元/幺元64.定义:左零元(右零元)65.定义:左逆元(右逆元)、逆元、可逆66.定义:消去律、左消去律(右消去律)注意P18367.定义:代数系统/代数、特异元素/代数常数68.定义:具有相同的构成成分/同类型69.定义:子代数系统/子代数、平凡的子代数、真子代数(函数对子集封闭)70.定义:积代数、因子代数************************************群与环***************************************半群与群都是具有一个二元运算的代数系统71.定义:半群()、幺半群/独异点()、群()72.有理数加群、整数加群、实数加群、复数加群、四元群、子代数、语言73.定义:有限群、无限群、平凡群、交换群/Abel群74.定义:n次幂75.定义:(元素的)阶/周期、k阶元、无限阶元***********************************格与布尔代数**********************************格与布尔代数是具有两个二元运算的代数系统定义:格(偏序集定义的) P22176.幂集格、子群格77.定义:对偶命题、格的对偶原理78.定义:格(代数系统定义的)79.定义:子格80.定义:分配格81.定义:全上界、全下界82.定义:有界格83.定义:补元84.定义:有补元定义:布尔格/布尔代数(有补分配格)85.定义:布尔代数(代数系统定义)86.定义:原子**********************************14.图的基本概念********************************87.无序积 A&B488.定义:无向图、顶点集、顶点/结点、边集、无向边/边89.定义:有向图、无向边/边90.(P294)图、阶、n 阶图;零图、平凡图;空图;标定图、非标定图;基图;端点、关联、关联次数、环、相邻;始点、终点、孤立点;邻域、闭邻域、关联集、后继元集、先驱元集91.定义:平行边、重数、多重图、简单图92.定义:度数/度、出度、入度、最大度、最小度、悬挂顶点、悬挂边、偶度(奇度)顶点93.度数列、可图化的、可简单图化的,出度列、入度列94.定义:n阶无向完全图/n阶完全图、n阶有向完全图、n阶竞赛图95.定义:k-正则图96.定义:母图、真子图、生成子图、导出的子图97.定义:删除边e、删除E’、删除顶点v、删除V‘、边的收缩、新加边删点边不留,删边点还在98.定义:通路、始点、终点、长度、回路、简单通路、简单回路、初级通路/路径、初级回路/圈、奇圈、偶圈、复杂通路、复杂回路99.定义:连通、连通图、非连通图100.定义:连通分支、连通分支数101.定义:短程线、距离102.定义:点割集、割点103.定义:边割集/割集、割边/桥104.定义:弱连通图/连通图、单向连通图、强连通图105.定义:二部图/二分图/偶图,完全二部图定义:无向图关联次数、关联矩阵定义:有向图关联矩阵定义:邻接矩阵定义可达矩阵**********************************15.欧拉图与哈密顿图****************************106.定义:欧拉通路、欧拉回路、欧拉图、半欧拉图107.定义:哈密顿通路、哈密顿回路、哈密顿图、半哈密度图**********************************16.树*****************************************108.定义:无向树/树、森林、平凡树、树叶、分支点109.定义:生成树、树枝、弦、余树110.定义16.:5:权、最小生成树111.避圈法(Kruskal算法)B.定理1.定理:简单析取式是重言式的充要条件;简单合取式是矛盾式的充要条件52.定理:析取范式(矛盾式)、合取范式(重言式)3.定理:范式存在定理4.定理:极小项和极大项关系5.定理:主析、主合存在并唯一6.定理:子集是一切集合的子集推论:空集是唯一的7.定理:逆关系性质8.定理:复合结合律、逆9.定理:关系与恒等关系复合10.定理:复合分配律注意交11.定理:限制和像的分配律注意像的交12.定理:有穷集上只有又穷多个不同的二元关系13.定理:关系的幂性质14.定理:有穷集A上的关系R的幂序列R0,R1,R2等是一个呈现周期性变化的序列15.定理:五大性质16.定理:等价关系的性质17.定理:函数的复合(关系的右复合)推论1:函数复合结合律推论2:ƒ:A→B,g:B→C,则ƒ。

g:A→ C,且……定理:函数复合能够保持单射、满射、双射的性质18.定理:函数和恒等关系复合19.定理:函数双射,反函数也是双射20.定理:双射函数与反函数的复合21.定理:左右单位元相等22.定理:左右零元相等23.定理:单位元和零元不相等24.定理:左逆元等于右逆元25.定理:积代数的性质26.定理:群的幂运算27.定理:群的消去律28.定理:元素阶的性质29.定理:运算∨和∧满足交换律、结合律、幂等律、吸收律30.定理:P22531.定理:格的上下确界32.定理:P22633.定理:补元唯一定理34.定理:布尔代数的双重否定律、德摩根律635.定理:握手定理(无向图)36.定理:握手定理(有向图)推论:奇度顶点个数37.定理:可图化的充要条件38.定理:最大度取值39.定理:通路存在,长度40.定理:无向图欧拉图的充要条件41.定理:无向图半欧拉图的充要条件42.定理:有向图欧拉图的充要条件43.定理:有向图半欧拉图的充要条件44.定理:非平凡的欧拉图充要条件45.定理:无向哈密顿图连通分支数性质推论:无向半哈密顿图连通分支数性质46.定理:哈密顿通路存在定理推论:哈密顿回路存在定理47.定理:无向图哈密顿图充要条件48.定理:P32949.定理:树和树叶50.定理:无向图有生成树的充要条件推论:无向连通图的边数大于等于生成树的边数7。

相关主题