离散数学

这是一篇关于离散数学的思维导图，主要内容包括：集合映射与运算，关系，命题逻辑，谓词逻辑，初等数论，图论，几何特殊的图（了解），组合计数，代数结构（了解）。

离散数学

• 集合映射与运算
  • 集合有关的概念
    • 集合、子集、幂集、n元组、笛卡尔积
  • 映射有关概念
    • 映射的定义、映射的性质、逆映射、复合映射
  • 运算的定义及性质
    • 运算的定义、运算的性质（对合性、幂等性等）
  • 集合的运算：并运算、交运算、补运算、差运算、对称差运算
  • 集合的划分与覆盖
  • 集合的对等定义、无限集合、集合的基数、可数集合、不可数集合、基数的比较
• 关系
  • 关系的概念
    • n元关系的定义、二元关系、关系的定义域与值域、关系的表示、函数的关系定义
  • 关系的运算
    • 关系的集合运算、关系的逆运算、关系的复合运算、关系的其他运算
  • 关系的性质
    • 自反性、反自反性、对称性、反对称性、传递性
  • 关系的闭包
    • 自反闭包、对称闭包、传递闭包
  • 等价关系
    • 等价关系的定义、等价类
  • 相容关系：相容类
  • 偏序关系：定义、偏序关系哈斯图、偏序集中特殊元素
• 命题逻辑
  • 命题的有关概念、逻辑联结词、否定联结词、合取联结词、析取联结词、异或联结词、条件联结词、双条件联结词、与非联结词、或非联结词、条件否定联结词
  • 命题公式及其真值表：命题公式的定义、命题的符号化、命题公式的真值表、命题公式的类型
  • 逻辑等值的命题公式：逻辑等值公式、基本等值式、等值演算法、对偶原理
  • 命题公式的范式：命题公式的析取范式及合取范式、命题公式的主析取范式及主合取范式
  • 联结词集合的功能完备性
  • 命题逻辑中的推理：推理形式有效性的定义、基本推理规则、命题逻辑的自然推理系统
• 谓词逻辑
  • 个体、谓词、量词、函词
  • 谓词公式的命题符号化、谓词公式的解释及类型、逻辑等值的谓词公式、谓词公式的前束范式（定义与计算）
  • 谓词逻辑中的推理（逻辑蕴含式、基本推理规则、谓词逻辑的自然推理系统）
• 初等数论
  • 整除关系与素数（整除关系与带余除法）、素数与素因数分解、最大公因数、最小公倍数
  • 模同余关系、模同余方程组、RSA密码算法（加密与解密过程以及算法）
• 图论
  • 图的基本概念（图的定义、邻接、关联、简单图）、节点的度数
  • 子图、图的运算和图的同构；路与回路、图的连通性（无向图的连通性以及点连通度和边连通度）、有向图的连通性
  • 图的矩阵表示：图的邻接矩阵、可达矩阵与关联矩阵
  • 赋权图以及最短路径
• 几何特殊的图（了解）
  • （1）欧拉图：中国邮递员问题；（2）哈密顿图：有关概念、必要条件、充分条件以及旅行商问题；（3）无向树：定义、性质以及生成树和最小生成树；（4）有向树：定义、根树、m叉树、有序数、定位二叉树（5）平面图：有关概念、欧拉公式、库拉托夫斯基定理、平面图的对偶图（6）平面图的着色（7）二部图及匹配
• 组合计数
  • 计数原理、排列组合与二项式定理；生成函数（组合计数与排列计数）；地柜关系（概念与常用的递归关系求解方法）
• 代数结构（了解）
  • 定义；最简单的代数结构：半群及独异点；子代数；代数结构的同态与同构
  • 群的定义与子群、群的同态；环和域（几种特殊的环、有限域）
  • 格（分配格、有补格）与布尔代数