离散数学复习提纲

《离散数学复习提纲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、数理逻辑（第1章、第2章）·命题定义、联结词（与、或、非、单条件、双条件）·命题公式、真值、真值表、符号化·谓词、量词（全称、存在）、谓词公式·一阶逻辑符号化（所有的。。。是。。。，、和有些。。。是。。。。特性谓词）·谓词公式求真值（在某种解释下）·命题公式的等值（等价）演算（十大定律）·命题公式的主范式·谓词公式的前束范式·命题逻辑应用·命题逻辑推理（推理定律、推理规则：P，T，CP）·谓词逻辑推理（推理定律、推理规则：P，T，CP，UI，EI,UG,EG）····························二、集合论（第3章）·集合的定义与表示方法（解

2、析法、枚举法、文氏图法）·集合间的相互关系（定义，符号：ÍÌ=）·集合的运算定义与图示（ÇÈ-~Å´P/）——入集条件·集合定律（十大定律）·集合恒等式的证明法一：直接利用定律及已证等式法二：利用集合相等的定义（①左Í右Ù右Í左②xÎ左ÛxÎ右）·集合的元素计数与应用（包容排斥原理）·································三、关系论（第4章）·二元关系的定义及其表示（解析法、集合法、图示法、矩阵法）·关系的运算（集合的所有运算+左复合、求逆、求闭包）·关系的性质（定义、关系图特点、矩阵的特点、证明）·等价关系（定义、等价类、上集、划分）·

3、偏序关系与偏序集（定义、哈斯图）·全序集（线序集、定义、最元、极元、界元、确界）·································四、函数论（第4章）·定义（唯一性）·A到B的函数（唯一性、良定性）·特殊函数（常、恒等、单增、单减、特征、自然映射）·BA的计数·函数的性质（单、满、双，判断）·函数的复合（左复合）·反函数（只有双设才有）·······························一、代数系统（第5章、第6章）·二元运算（定义，封闭性）、运算表·各种定律（交换、结合、幂等、分配、吸收、消去、幺元、零元、逆元）·代数系统、子代数、积代

4、数（定义、特殊元素、代数常数）·同态与同构（同态等式、证明）·半群、独异点·群、子群、阿贝尔群、生成子群、元素的阶（周期）、循环群（定义与证明）·环、含幺环、零因子、无零因子环、整环、除环与域·格（两种定义）、分配格、有界格、布尔格（判断）·······························二、图论（第7张、第8张、第9张）·无向图、有向图、零图、平凡图、完全图、子图、生成子图、补图·第一握手定理、度数序列·通路、回路、简单。。。、基本。。。·连通图、强连通图、单连通图、弱连通图·点割集、边割集·最短路径及求法（Dijkstra）·欧拉图、哈密顿图、二部

5、图、平面图（定义、判定）·完备匹配、完美匹配·欧拉公式·第二握手定理·对偶图的求法·树、有根树、有序树、正则树、完全正则树、有序完全正则树·植树原理·有序二叉树的遍历（行遍、周游）（先序——前缀码波兰码、中序——还原原式、后序——后缀码逆波兰码）（详见P198例9.4）·最优二元树、Huffman算法、最佳前缀码························三、温馨提示·结合各章题例分析复习······················一、判断题1.一个关系不是对称的，则它一定是反对称的。2.在群中，除幺元e外，还有其它的等幂元。3.可能有某种关系，既不

6、是自反的，也不是反自反的。4.5.n元组也不是序偶。6.一个函数要有逆函数则它必须为双射函数。7.S={a,b,c},则S有3个划分。8.A={Φ,{Φ}}，则ρ(A)={Φ，{Φ}，{Φ,{Φ}}}9.命题公式是重言式10、(x)((y)Q(y)W(x))中(y)的辖域为Q(y)W(x)11.陈述句“4是素数仅当8是素数”是真命题．12.13.n个命题变元可产生2n种命题公式．14.15.如果一个关系为自反的则不可能是反自反的．16.当一个函数为双射时，其逆关系为双射函数．17.如果AB，则A不可能为B的子集．18.19.题公式是一个矛盾式。20.循环群必定是阿

7、贝尔群，反之亦真。21.设A.B.C是任意三个集合。（1）若AB且BC，则AC。（）（2）若AB且BC，则AC。（）（3）若AB且BC，则AC。（）（4）。（）（5）(A–B)C=(AC)-(BC)。（）22.可能有某种关系，既不是自反的，也不是反自反的。（　　）23.集合A上的一个等价关系，决定了A的一个划分，该划分不一定是商集A/R。（）24.集合A上的恒等关系是一个双射函数。（）25.代数系统中一个元素的左逆元并一定等于该元素的右逆元。（）26.群是每个元素都有逆元的半群。（）27.可能有某种关系，既不是自反的，也不是反自反的。（　　）28.集合A上的一个等

8、价关系，决