离散数学考试大纲

  1 命题演算基础

  1.1 命题与联结词
  ①命题 ②联结词 ③合式公式 ④命题的符号化
  1.2 真假性
  ①解释 ②等价公式 ③联结词的完备集 ④对偶式和内否式。
  1.3 范式及其应用
  ①范式 ②主范式
  2 命题演算的推理理论
  2.1 命题演算的公理系统
  ①公理系统的组成部分 ②公理系统的推理过程
  2.2 命题演算的假设推理系统
  ①假设推理系统的组成 ②假设推理系统的推理过程
  2.3 命题演算的归结推理法
  ①归结证明过程②归结证明方法
  3 谓词演算基础
  3.1 谓词和个体
  ①个体 ②谓词 ③语句的符号化
  3.2 函数和量词
  ①函数项 ②量词
  3.4 永真性和可满足性
  ①真假性 ②同真假性 ③永真性和可满足性 ④范式
  4 谓词演算的推理理论
  4.1 谓词演算的永真公理系统
  ①公理系统的组成部分 ②公理系统的推理过程
  4.2 谓词演算的假设推理系统
  ①假设推理系统的组成及证明方法 ②定理的推导过程
  4.3 谓词演算的归结系统
  ①置换 ②归结反演系统 ③霍恩子句逻辑程序
  5递归函数论
  5.1 数论函数和数论谓词
  5.2 函数的构造
  6 集合
  6.1 集合的基本概念
  ①集合;②子集合;③空集合;④集合的相等。
  6.2 集合的基本运算
  ①集合的运算;②集合的交;③集合的并;④集合的差;⑤集合的对称差;⑥集合的广义交;
  ⑦集合的广义并;⑧幂集合。
  6.3 全集和集合的补
  ①全集;②集合的补;③德·摩根定律。
  6.4 自然数与自然数集
  ①自然数;②自然数集;③数学归纳法;④集合的归纳定义。
  6.5 包含与排斥原理
  ①有限集;②包含与排斥原理。
  7 关系
  7.1 集合的笛卡尔积集
  ①有序对;②集合的笛卡尔积集;③有序n(n2)元组;④n重(n2)笛卡尔积集。
  7.2 二元关系的基本概念
  ①二元关系;②二元关系的表示;③二元关系的图形表示;④二元关系的矩表示;⑤二元关系的运算;⑥二元关系的复合运算;⑦二元关系的逆关系。
  7.3 二元关系的性质
  ①二元关系的性质;②自反的二元关系;③反自反的二元关系 ;④对称的二元关系;⑤反对称的二元关系;⑥传递的二元关系。
  7.4 二元关系的闭包运算
  ①二元关系的闭包运算;②自反闭包;③对称闭包;④传递闭包。
  7.5 等价关系与集合的划分
  ①等价关系;②等价类;③集合的划分;④商集合。
  7.6 偏序关系和格
  ①偏序关系;②偏序集;③极大元;④极小元;⑤最大元;⑥最小元; ⑦最小上界;⑧最大下界;⑨可比;⑩覆盖;⑾有序集;⑿良序集;⒀格。
  8 函数与集合的势
  8.1 函数的基本概念
  ①函数(映射);②定义域;③陪域;④值域;⑤象集;⑥原象集;⑦单射函数;⑧满射函数;⑨双射函数。
  8.2 函数的复合与可逆函数
  ①函数的复合;②左可逆函数;③右可逆函数;④可逆函数。
  8.3 无限集
  ①集合的势;②无限集;③集合的势相等;④可数无限集;⑤不可数无限集; ⑥集合势大小的比较。
  9 图论
  9.1 图的基本概念
  ①有向图;②无向图;③顶点集;④边集;⑤自环;⑥孤立点;⑦多重边;⑧简单图;⑨完全图;⑩关联;⑾邻接;⑿图的同构;⒀子图;⒁生成子图;⒂补图;⒃图的顶点度数(次数);⒄图的顶点度数和与边数关系。
  9.2 图中的通路、图的连通性与图的矩阵表示
  ①图中的通路;②简单通路;③初等通路;④回路;⑤简单回路;⑥初等回路(圈);⑦连通图;⑧有向连通图;⑨有向单侧连通图;⑩有向强连通图;⑾ 图的邻接矩阵;⑿图的关联矩阵;⒀图的可达矩阵。
  9.3 带权图与带权图中最短通路
  ①带权图;②带权图的最短通路;③狄克斯瑞(Dijkstra)算法。
  9.4 欧拉图
  ①欧拉图;②欧拉通路;③欧拉回路;④欧拉定理。
  9.5 哈密尔顿图与货郎担问题
  ①哈密尔顿通路;②哈密尔顿回路(圈);③哈密尔顿图;④哈密尔顿图的必要条件;⑤哈密尔顿图的充分条件;⑥货郎担问题;⑦最邻近算法。
  9.6 二部图
  ①二部图(偶图);②二部图的充要条件;③二部图的匹配;④二部图的极大匹配;⑤二部图的完美匹配。
  9.7 平面图
  ①平面图;②平面图的欧拉定理;③平面图的必要条件;④平面图的区域着色。
  10 树
  10.1 树的基本概念
  ①树;②树中顶点与边关系公式;③树的等价定义。
  10.2 连通图的生成树与带权图的最小生成树
  ①连通图的生成树;②割集;③割集与生成树的关系;④带权图最小生成树的算法。
  10.3 有序树
  ①有向树;②根树;③有序树;④有序n (n2)分树;⑤正则有序n (n2) 分树。
  10.4 前缀码和最优二分树
  ①前缀码;②带权图的最优二分树;③霍夫曼(Huffman)算法。
  11 群和环
  11.1 代数运算的基本概念
  ①二元运算;②封闭的二元运算;③可结合的二元运算;④可交换的二元运算;⑤n元运算
  11.2 代数系统和半群
  ①代数系统;②左么元;③右么元;④么元;⑤半群;⑥含么半群(独异点);⑦半群的同态;⑧子半群;⑨子含么半群。
  11.3 群的基本概念
  ①左逆元;②右逆元;③逆元;④群;⑤有限群;⑥交换群;⑦群同态;⑧群同构;⑨群中元素的阶。
  11.4 变换群和置换群
  ①变换含么半群;②变换群;③置换群;④n个文字对称群。
  11.5 循环群
  ①循环群。
  11.6 子群、群的子集生成的群
  ①子群。
  11.7 子群的陪集
  ①子群的陪集;②子群在群中的指数;③群中拉格朗日定理。
  11.8 正规子群、商群、群同态
  ①正规子群;②商群;③群的同态基本定理。
  主要参考教材:朱保平,叶有培,张琨.离散数学.北京:北京理工大学出版社,2006