离散数学复习提纲离数学复习提纲.doc

数理逻辑（第1章、第2章） ·命题定义、联结词（与、或、非、单条件、双条件） ·命题公式、真值、真值表、符号化 ·谓词、量词（全称、存在）、谓词公式 ·一阶逻辑符号化（所有的。。。是。。。，、和 有些。。。是。。。。 特性谓词） ·谓词公式求真值（在某种解释下） ·命题公式的等值（等价）演算（十大定律） ·命题公式的主范式 ·谓词公式的前束范式 ·命题逻辑应用 ·命题逻辑推理（推理定律、推理规则：P，T，CP） ·谓词逻辑推理（推理定律、推理规则：P，T，CP，UI，EI,UG,EG） ···························· 集合论（第3章） ·集合的定义与表示方法（解析法、枚举法、文氏图法） ·集合间的相互关系（定义，符号：( ( =） ·集合的运算定义与图示（( ( - ( ( ( P / ）——入集条件 ·集合定律（十大定律） ·集合恒等式的证明 法一：直接利用定律及已证等式 法二：利用集合相等的定义（①左(右 ( 右(左 ②x(左 ( x(右） ·集合的元素计数与应用（包容排斥原理） · · ······························· 关系论（第4章） ·二元关系的定义及其表示（解析法、集合法、图示法、矩阵法） ·关系的运算（集合的所有运算+左复合、求逆、求闭包） ·关系的性质（定义、关系图特点、矩阵的特点、证明） ·等价关系（定义、等价类、上集、划分） ·偏序关系与偏序集（定义、哈斯图） ·全序集（线序集、定义、最元、极元、界元、确界） ································· 函数论（第4章） ·定义（唯一性） ·A到B的函数（唯一性、良定性） ·特殊函数（常、恒等、单增、单减、特征、自然映射） ·BA的计数 ·函数的性质（单、满、双，判断） ·函数的复合（左复合） ·反函数（只有双设才有） ······························· 代数系统（第5章、第6章） ·二元运算（定义，封闭性）、运算表 ·各种定律（交换、结合、幂等、分配、吸收、消去、幺元、零元、逆元） ·代数系统、子代数、积代数（定义、特殊元素、代数常数） ·同态与同构（同态等式、证明） ·半群、独异点 ·群、子群、阿贝尔群、生成子群、元素的阶（周期）、循环群（定义与证明） ·环、含幺环、零因子、无零因子环、整环、除环与域 ·格（两种定义）、分配格、有界格、布尔格（判断） ······························· 图论（第7张、第8张、第9张） ·无向图、有向图、零图、平凡图、完全图、子图、生成子图、补图 ·第一握手定理、度数序列 ·通路、回路、简单。。。、基本。。。 ·连通图、强连通图、单连通图、弱连通图 ·点割集、边割集 ·最短路径及求法（Dijkstra） ·欧拉图、哈密顿图、二部图、平面图（定义、判定） ·完备匹配、完美匹配 ·欧拉公式 ·第二握手定理 ·对偶图的求法 ·树、有根树、有序树、正则树、完全正则树、有序完全正则树 ·植树原理 ·有序二叉树的遍历（行遍、周游）（先序——前缀码波兰码、中序——还原原式、后序——后缀码逆波兰码）（详见P198例9.4） ·最优二元树、Huffman算法、最佳前缀码 ························ 温馨提示 ·结合各章题例分析复习 ······················ 一、判断题 1.一个关系不是对称的，则它一定是反对称的。 2.在群H,*中，除幺元e外，还有其它的等幂元。 3.可能有某种关系，既不是自反的，也不是反自反的。 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.循环群必定是阿贝尔群，反之亦真。 21.设A.B. C是任意三个集合。 （1）若A B且B C，则A C。 （ ） （2）若A B且B C，