离散数学

这是大学课程《离散数学》其中的一章，是我在复习过程中整理出来的其中一章，希望对大家有帮助！

集合论

• 集合
  • 基本概念
    • 集合的概念
      • 集合就是人们直观上或思想上能够明确区分的一些确定的、彼此不同的事物所构成的整体。把组成这个集合的个别事物称为集合的元素。通常用大写英文字母A,B,…表示集合的名称,用小写英文字母a,b,…表示集合的元素.
    • 集合的性质
      • .集合元素所表示的事物可以是具体的,也可以是抽象的.集合的元素既是任意的,又必须是确认的和可区分的
      • 一个集合,若其组成的元素的个数是有限的,则称该集合为有限集;否则,称其为无限集
      • 有限集S 中所含元素的数目称为集合S 的元数或基数,记作|S|.若|S|=0,则称S 为空集,记为Ø
    • 集合的表示
      • 列举法
        • 列举法就是将集合的元素按某一次序逐一列在花括号内,并用逗号分开的方法.例如 A={a,b,c},B={1,2,3,…},C={2,4,6,…}.
      • 描述法
        • 用谓词描述出集合元素的公共特征,其形式为S={x|P(x)},即S 是使P(x)为真的x 的 全体.例如A={x|∃y(y∈Z∧x=2y)}
      • 归纳定义法
        • 定义
          • 归纳定义法通常包括以下3步: (1)基本步:S0 非空且S0 中的任意元素均是A 的元素; (2)归纳步:给出一组规则,从A 的元素出发,依据这些规则所得到的仍是A 的元素; (3)极小化:若S 的任意元素均是A 的元素,并且S 满足(1)和(2),则S 与A 含有相同的元素
        • 应用
          • 自然数N的归纳定义
          • 归纳法
            • 第一归纳法
            • 第二归纳法
    • 集合的符号
      • 子集
        • 设有集合A 和B.若∀x(x∈A→x∈B),则称 A 是B 的子集,也称 A 包含于 B,或者B 包含A,记为AÍB 或BÊA;否则,称A 不是B 的子集
      • 相等
        • 设有集合A,B.若AÍB,且BÍA,则称 A 与B 相等,记为 A=B;否则,称 A与B不等
      • 真子集
        • 设有集合A,B.若 AÍB,且 A不等于B,则称 A 是B 的真子集,也称 A 真包含于B,或B 真包含A,记为AÌB 或BÉA
      • 全集
        • 若集合E 包含我们讨论的每一个集合,则称 E 是所讨论问题的完全集,简称 全集(或论述域).
          • 全集是一个相对的概念,它根据所讨论的问题的不同而有所不同。
      • 定理1：设A,B,C 是任意集合,则 (1)FÍA; (2)AÍA; (3)AÍE; (4)若AÍB 且BÍC,则AÍC; (5)若AÌB 且BÌC,则AÌC
      • 空集
        • 空集是存在的并且是唯一的，记为F
      • 幂集
        • 设A 是集合,则称{x|xÍA}为A 的幂集,记为r(A),有时记为2^A ,即 A 的幂 集是由A 的所有子集组成的集合
        • 定理2：如果有限集A 的元数为n,则 |r(A)|=2Ùn =2Ù|A|.
  • 集合的运算
    • 基本运算符
    • 文氏图（韦恩图）
      • 文氏图是用点的集合作为集合的示意表示.通常用一个矩形区域表示全集E,矩形中的点表示全集E 中的元素.E 的子集用矩形内的圆形区域表示
    • 包含排斥定理
      • 设A,B 是两个有限集合,则 |AÈB|=|A|+|B|-|AÇB|.
        • • 定理5：设A1,A2,…,An 为有限集合,其元数分别为|A1|,|A2|,…|A2|，则
    • 基本定律
    • 环和、环积
  • 集合的分类
    • 有限集与无限集
      • 等势
      • 判定
    • 可数集（可列集）与不可数集
      • 可数集（可列集）
        • 定义一
        • 定义二
        • 性质
      • 不可数集
      • 无限集关系
  • 集合基数的比较
    • 集合基数的关系
      • • 由|A|=|B|的定义可知,要证明A 和B 有相同基数,则要找一个从 A 到B 的双射,只要找一个从A 到B 的单射和一个从B 到A 的单射即可
    • 集合基数的比较
• 二元关系
  • 关系的基础
    • 笛卡尔积
      • 有序n元组
        • 对于自然数n,n个客体a1,a2,…,an,按一定的次序排列成的一个序列,称为有序n元组,简称n元组,记为(a1,a2,…,an).ai 称为n 元组的第i个元素.
        • (a1,a2,…,an)=(b1,b2,…,bn)当且仅当ai=bi(i=1,2,…,n). 当n=2时的有序二元组称为序偶.
      • 笛卡尔积概念及例子
      • 笛卡尔积的性质
  • 关系的基本概念
    • 关系的概念
    • 关系的表示法
      • 集合表示法
      • 关系图
      • 关系矩阵
    • 关系的性质
      • 自反与反自反
        • • 1、在R里面，如果全部在X中的元素都有自己跟自己的关系，那他就是自反的 2、在R里面，如果全部在X中的元素都没有自己跟自己的关系，那他就是反自反 3、若两者都不是，那就是既不是自反的又不是反自反的
      • 对称与反对称
        • • 1、在R里，若同时存在（x，y）和（y，x），则R是对称的 【x，y可以相等也可以不相等】 2、在R里，若只有（x，y）而没有（y，x）【x不等于y】， 那么R就是反对称的，不是对称的 特殊地，若直接没有（x，y）【x不等于y】，即恒等关系和 空关系，那么R还是反对称的
      • 传递
        • • 1、在R里面，如果有（x，y）和（y，z）【首尾相接】的前提下同时有（x，z）那就是传递的 2、如果在R里面直接没有首尾相接的两个序偶 ，那还是传递的 【有首尾相接却不接起来就不是传递的，其余为传递的】
      • 概要
    • 关系的合成
      • 关系的交、并、补、差
      • 复合关系
        • 定义
        • 定理
          • • 满足结合律，不满足交换律
        • 关系的幂
          • 定义
          • 定理
      • 逆关系
        • 定义
        • 定理
    • 闭包
      • 闭包概念
        • • r取自reverse 使次序颠倒的 s取自symmetry 对称 t取自transmit 传递
      • 闭包性质
        • • 如果R是自反（对称或者传递）的，那么R的自反（对称或者传递）闭包是它自己
        • • （1）中原因是当一个集合是自反时，任意添加其他序偶（闭包的原则就是向原集合中添加序偶），这个集合还是自反的 （2）中原因是（a，a）是对称的，当一个集合是对称是，它的自反和传递闭包必是在原集合的基础上添加若干（a，a） （3）中若R同时是传递和对称的，则r（R）也是传递的，若R只是传递的，则r（R）不是传递的
  • 关系的划分
  • 特殊的关系
    • 次序关系
      • 概念
        • 次序关系是满足反对称的、传递的关系,根据其是自反的还是反自反的,可以把次序分为偏序关系和拟序关系
      • 偏序关系
        • 概念
        • 分类
        • 偏序集
          • 偏序集的概念
          • 偏序集中的特殊元素
            • • 注意： 1、y在Y之中 2、在确定各元之前先画出哈斯图 3、若存在极大元（同时存在多个最大值），那么就不会存在最大元
            • • 注意： 1、y在X或者Y中都有可能 2、在确定各界之前先画出哈斯图 3、留意确定上（下）界时，y必须是小于（大于）或等于所有Y中的元素，不满足此条件就是无上（下）界 4、上（下）界可以有多个，但是上（下）确界只能有一个或者没有 5、若没有上（下）界，那么就不会有上（下）确界
        • 哈斯图
      • 拟序关系
    • 等价关系
      • 概念
      • 等价类
        • 概念
        • 重要举例
        • 性质
          • • 根据等价类的性质,集合 X 上的等价关系R 所构成的类,它们两两互不相交而且覆盖整个集合 X.由它们构成一个新的集合———商集.
        • 商集
    • 函数关系
      • 函数的概念
      • 相等函数的判定
      • 函数的集合
        • • Y中元素数目是X中元素可以做选择的数目，X中元素数目表示可选择的次数
        • • 当A 或B 中至少有一个集合是空集时,可以分成左边的3种情况
      • 特殊函数
        • 常函数
        • 恒等函数
        • 单调函数
        • 特征函数
        • 自然映射
        • 复合函数
        • 逆函数
          • 概念
          • 性质