离散数学

离散数学1－3章 集合、二元关系、函数，集合是作为一个原始概念，集合可以认为是由某些可以互相区分的任意对象组成的一个整体。f为集合X到集合Y的二元关系，且满足：若<x,y1>∈f，则<x,y2>∈f，则y1=y2，则称f为从X到Y的部分函数。

离散数学

• 第一章：集 合
  • 集合的概念和表示
    • 定义：作为一个原始概念，集合可以认为是由某些可以互相区分的任意对象组成的一个整体。
    • 集合中元素的性质
      • 无序性
      • 明确性
      • 不可重复性
    • 表示方法
      • 列举法/部分列举法
      • 命题法
      • 归纳定义法
    • 集合的关系
      • A⊆B（任意a∈A都有a∈B）
      • A=B(A⊆B且B⊆A)
      • A⫋B（A⊆B且A≠B）
    • 常用集合
      • Q：有理数的集合
      • N：自然数的集合
      • I：整数的集合
      • R：实数的集合
      • C：复数的集合
      • Ø：空集
  • 集合的运算
    • 幂集
      • 概念：P（A）={x|x⊆A}
      • 幂集的元素数量：n(P(A))=2^n(A)
      • 运算性质：保号性
    • 基本运算
      • ∩，∪，-，⊕
    • 集类与广义交、并
      • 概念
      • 性质
        • 广义分配律
        • 广义结合律
        • 广义德摩尔根率
    • 运算的基本性质
      • 幂等律
      • 结合律
      • 交换律
      • 分配律
      • 德摩尔根率
      • 同一律，零率，互补率，对合率
    • 笛卡尔乘积
      • 序偶概念
      • 笛卡尔乘积定义
      • 性质
        • 保号性（A⊆B则A×C⊆B×C）
        • 对∩，∪，-的分配律
  • 自然数和归纳法
    • 后继与皮亚诺公理
    • 第一归纳法
    • 第二归纳法
• 第二章：二元关系
  • 关系与关系的基本表达形式
    • 关系的定义
    • 关系矩阵与关系图
  • 关系的运算
    • 逆关系（设R为从集合A到集合B的二元关系，从A到B的二元关系R'满足＜y,x＞∈R'当且仅当＜x，y＞∈R)
    • 关系的合成（设R1为从集合A到集合B的二元关系，R2为从集合B到集合C的二元关系,称A到C的二元关系｛＜x,z＞|有y∈B使＜x,y＞∈R1且＜y,z＞∈R2｝）
    • 关系的闭包
      • 定义：1.包含原集合 2.具有自反（对称，传递）的性质 3.极小性
      • 性质：1.计算方法 2.闭包运算的保号行 3.注意三重闭包运算中st运算和ts运算的包含关系
    • 补关系（设R为从集合A到集合B的二元关系，从A到B的二元关系R'满足＜x,y＞∈R'当且仅当＜x，y＞∉R)
  • 常用重要关系
    • 相容关系（略）
    • 等价关系
      • 性质与证明方法
      • 图与矩阵表示
    • 序关系
      • 半序(自反，反对称，传递)
      • 拟序(反自反，传递)
      • 全序(集合A上的半序R满足:若x,y∈R，则有xRy或yRx)
      • 良序（设R为集合A上的半序，A的每个非空子集都有最小元）
• 第三章：函数
  • 部分函数的定义与分类
    • f为集合X到集合Y的二元关系，且满足：若<x,y1>∈f，则<x,y2>∈f，则y1=y2，则称f为从X到Y的部分函数
    • 函数分类
      • 从X到Y的函数
        • domf = x
      • 从X到Y的严格部分函数
        • domf⊆X
      • 从X到Y上的部分函数
        • ranf = Y
      • 从X到Y的1-1函数
        • 对任意的x1,x2∈domf，当x1 ≠ x2时皆有f(x1)≠f(x2)
    • 原像
      • f为X到Y的部分函数，A⊆X且B⊆Y，f[A] = {y | 有x∈A使y = f(x)}, f-1[B] = {x | 有y ∈ B使f(x) = y}
    • 延括
      • f为X到Y的部分函数，A⊆X，定义f在A上的限制f|`A为从A到Y的部分函数，并且f|`A = f ∩ (A×Y)
  • 函数的合成
    • 定义
      • 若f为从X到Y的部分函数，g为Y到Z的部分函数，则合成关系f·g是一个从X到Z部分函数
    • 有关性质
      • dom(g·f) = f^(-1)[dom g]且ran(g·f) = g[ran f]
      • 若f和g都是全函数，则g·f也是全函数
    • 映射
      • 若ran f = Y，则称f为满射
      • 若f是1-1的，则称f为内射
      • 若f是满射又是内射，则称f为双射
    • 映射性质
      • 若f和g都是满射，则g·f也是满射
      • 若f和g都是内射，则g·f也是内射
      • 若f和g都是双射，则g·f也是双射
      • g·f是满射，则g是满射
      • g·f是内射，则f是内射
      • g·f都是双射，则g是满射f是内射
  • 逆函数
    • 分类
      • 对f:X->Y，若有g:Y->X使g·f = Ix，则称f为左可逆的，并称g为f的一个左逆函数
      • 对f:X->Y，若有g:Y->X使f·g = Iy，则称f为右可逆的，并称g为f的一个右逆函数
      • f同时为左可逆和右可逆则称f为可逆的
    • 有关性质
      • 左可逆等价于
        • f为内射
        • f可左消去，即对任意集合Z及任意的g:Z->X和h:Z->X，当f·g = f·h时，皆有g=h
      • 右可逆等价于
        • f为满射
        • f可右消去，即对任意集合Z及任意的g:Y->Z和h:Y->Z，当g·f = h·f时，皆有g=h
      • 可逆的等价于
        • f为双射
        • f既是左可逆又是右可逆
        • 逆关系f^-1即为f的逆函数
  • 基数
    • 定义
      • 对等
        • 设A和B为二集合，若存在从A到B到双射，则称A和B的双射，则称A和B对等，或称A和B等势，记为A~B
      • 无限集
        • 设A是集合，如果存在n∈N使A~n，则称A为有限集，否则称A为无限集
      • #(A)
        • 如果A~B，就称A和B的基数相等，记为#(A)=#(B)
    • 抽屉原理
      • 任何有限集都不能与它的真子集对等
    • 有关性质
      • 若A和B为任意两个集合，则#(A)<=#(B)和#(B)<=#(A)二者中至少有一个成立
      • 传递性
        • #(A) = #(B)
        • 若#(A = #(B)，则#(B) = #(A)
        • 若#(A) = #(B)且#(B) = #(C), 则#(A) = #(C)
      • 伯恩斯坦定理
        • #(A) <= #(A)
        • 若#(A)<=#(B)且#(B) <= #(A)，则#(A) = #(B)
        • 若#(A) <= #(B) 且#(B)<=#(C)，则#(A) <= #(C)
      • 以下条件等价
        • A为无限集
        • A有可列子集
        • A有与它都等的真子集
      • 若A和B为二集合，则#(B)<=#(A)当且仅当存在从A到B的满射