2015年大连海事大学085212软件工程考研大纲

　　考试科目：离散数学
　　试卷满分及考试时间:试卷满分为100分，考试时间为180分钟。
　　一、命题逻辑
　　考试内容
　　命题，连接词的真值，重言式/矛盾式/可满足式，代入规则与替换规则，等价与蕴含，对偶式与对偶原理，连接词的最小功能完备集，范式与主范式，命题逻辑的推理规则法
　　考试要求
　　1．理解命题的概念，理解连接词的真值（特别是单条件连接词的真值）。
　　2．简要了解重言式/矛盾式/可满足式，以及代入规则与替换规则。
　　3．掌握等价式和蕴含式的的推导，掌握常见的基本等价式和基本蕴含式。
　　4．简要了解对偶式的概念与对偶原理的公式。
　　5．了解连接词的最小功能完备集。
　　6．掌握范式的概念，特别是主范式的概念，会求命题公式的主析取范式和主合取范式，并能表示成mi和ΠMj的形式。
　　7．重点掌握推理规则法的证明题。
　　二、谓词逻辑
　　谓词，量词与全总个体域与特性谓词，谓词公式，自由变元与约束变元，谓词公式的等价式与蕴含式，谓词逻辑的推理规则法
　　考试要求
　　1．理解谓词的概念，会使用谓词和量词对一个问题符号化，特别要理解符号化时默认个体域是全总个体域时的处理。
　　2．简要了解什么是自由变元与约束变元。
　　3．掌握谓词公式的等价推导和蕴含推导（重点是一元量词公式的量词转换律，量词辖域扩大收缩律和量词分配律）
　　4．重点掌握谓词逻辑的推理规则法的证明题
　　三、集合
　　集合的基本概念和基本定理，集合的运算，容斥原理，笛卡尔积
　　考试要求
　　1．理解空集、全集、幂集的概念的理解，会熟练求幂集。掌握集合相等的判定定理、空集的属性定理以及幂集计数定理。
　　2．掌握集合的基本运算和常见的集合等式，会做集合等式的证明推导。
　　3．了解容斥原理，会做简单的利用容斥原理的计算问题。
　　4．掌握笛卡尔积的概念及其性质，笛卡尔积元素计数公式。
　　四、二元关系
　　关系的概念及其性质，关系图与关系矩阵，关系的运算，等价关系与划分，偏序关系
　　考试要求
　　1．理解关系的概念，集合上能建立有多少种不同的二元关系的计算
　　2．从定义、关系图、关系矩阵三个角度理解关系的5个性质（自反、反自反、对称、反对称和传递性）
　　3．掌握关系的的合成运算、逆运算和闭包运算（自反闭包、对称闭包、传递闭包）
　　4．掌握划分、等价关系、等价类的概念，理解非空集合X上的等价关系与X的划分是一一对应的。
　　5．给定等价关系，会求对应的划分；给定划分，会求的对应的等价关系（掌握笛卡尔积的概念及其性质，笛卡尔积元素计数公式。
　　6．重点掌握等价关系相关的证明题。
　　7．偏序关系的定义，会画偏序关系的的哈斯图，并会求最大元和最小元、极大元和极小元、上界和下界、上确界和下确界。
　　五、函数
　　函数的概念，满射、单射、双射函数，复合函数，逆函数
　　考试要求
　　1．理解函数的概念，特别是函数（或映射）的全域性和惟一性。
　　2．会计算函数个数：设X和Y都为有限集,则从X到Y共有|Y||X|不同的函数。
　　3．理解满射、单射、双射函数。
　　4．会求复合函数。
　　5．了解逆函数的概念。
　　六、代数系统
　　代数运算的性质，特异元，可约性，代数系统的概念，同态/同构，代换性质与同余关系。
　　考试要求
　　1．理解代数运算的封闭性，交换性、结合性、分配性等。会做性质判断的计算题。掌握常见的特异元（幺元、零元、逆元等），并会熟练计算。了解可约性及其可约性的判定定理。
　　2．代数系统的概念和子代数系统的概念，要会证一个代数系统A是代数系统B的子代数。
　　3．重点理解同态、同构，理解同态与同构的性质，会做同态、同构的证明题。
　　4．简要了解代换性质与同余关系的概念。
　　七、群
　　半群、子半群、循环半群，群，阿贝尔群，群同态，循环群，子群。
　　考试要求
　　1．了解半群、子半群、循环半群的概念。
　　2．理解群的概念及群的基本性质，会证明给定的代数系统是否是群，会证明阿贝尔群以及群同态（同构）问题的证明。
　　3．理解循环群概念以及循环群的分类
　　4．理解子群的概念，掌握子群的证明方法。
　　八、图
　　图的相关基本概念，子图，路径与连通性，图的矩阵表示
　　考试要求
　　1．理解简单图的概念、特别度相关的概念、掌握握手定理与奇结点个数必是偶数的定理，零图、平凡图、正则图、完全图的概念，以及完全图的边数定理。会判断图同构的问题。
　　2．理解常见的几种子图的概念，特别是生成子图和导出子图，会求相对于完全图的补图。
　　3．理解基本路径/简单路径，可达性，掌握无向图和有向图的连通性及分图（分支）的概念以及相关的定理。
　　4．图的矩阵表示中主要理解邻接矩阵A（无向图/有向图）、AAT、ATA、Am表示的意义。
　　九、特殊图
　　欧拉图与哈密顿图，平面图，树与生成树
　　考试要求
　　1．理解欧拉图的概念，掌握判断无向图是欧拉图的欧拉定理。
　　2．了解哈密顿图的概念。
　　3．会用简单连通平面图的欧拉不等式结合握手定理做计算或证明。会用库拉托夫斯基定理判断平面图还是非平面图。
　　4．理解树的概念以及树的六个等价定义、（最小）生成树、根树、（完全）m叉树的概念。
　　5．会做树相关的计算题，会求最小生成树，会求最优二叉树（Huffman树）。
　　参考书目：
　　《离散数学》赵广利 大连海事大学出版社

　　点击【2015年大连海事大学考研大纲】查看更多考研大纲。
【相关阅读】
研究生招生专业索引
2015年全国各学校考研大纲汇总