离散数学II

week1

什么是离散数学

离散数学的研究对象和应用

  • 离散数学研究离散对象，一切以离散现象作为其研究对象或对象之一的数学均称为离散数学，其研究各种各样的离散量的结构及之间的关系。分析、方程等研究连续对象
  • 离散数学在基础数学研究、计算机科学、编码与密码学、物理、化学、生物等领域均有重要应用。
  • 计算机是一种离散结构，离散数学充分面熟计算机科学的离散性特点，是研究计算机科学的基本数学工具和最合适的理论手段

离散数学:基础数学工具

  • 将信息转换成数学符号后，存储、传播、理解
    和处理的速度、效率急剧提升，没有二义性
  • 数学符号带来程序语言

离散数学的发展历史

离散数学主要内容

  • 离散数学是现代数学的一个分支
  • [x] 数理逻辑
  • [ ] 集合论
  • [ ] 图论
  • [ ] 代数系统
  • [ ] 有限状态机

数理逻辑

常用的二元逻辑联结词

合取^、析取v、否定~、蕴含->、等价<->
它们的真值表如下

AA BB A∧BA\wedge B A∨BA\vee B ¬A\lnot A A→BA\rightarrow B A↔BA\leftrightarrow B
T T T T T F T T
T T F F T F F F
T F T F T F T F
T F F F F T T T

谓词

  • 在逻辑学中，将命题中表示思维对象的词称为主
    词，将表示对象性质的词称为谓词。

a：张华 b：李明 H(x)：x 是学生
这两个命题分别表示为 H(a) 和 H(b)，这样的表示就
显示了这两个命题有相同谓词的特征 。

  • 二元谓词:L 表示元素之间的关系，可看作从 D2 到 {0, 1}的函数，称为二元谓词。若 x 爱 y，则 L(x, y) = 1，否则 L(x, y) = 0。

函数与谓词的区别在于：对于一元函数 f， f(x) 是论域中的元素；对于一元谓词 P， P(x) 是 0 或 1。
需要注意：这里的函数 f 是单值函数，并且 f 的自变量和函数值都取自同一个集合 D，还要求 f 是全函数，即对于任意 xÎD， f(x) 有定义。因此，用 f (x) 表示 x 的父亲确实定义了一个函数，因为每个人都有唯一的父亲，并且任何人的父亲也是人。
如果用f(x)表示 x 的舅舅，那么并没有定义一个函数，因为有的人有多个舅舅，即 f 不是单值函数，并且有的人没有舅舅，即 f 不是全函数。
这种自变量和函数值都取自同一个集合 D 的函数称为 D 上的运算。

集合论

  • 合论是研究集合一般性质的数学分支，创始人是康托尔
    （G.Cantor）
  • 康托尔建立的集合论一般称为朴素集合论
  • 在现代数学中，每个对象本质上都是集合，都可以用某种集合来定义。
  • 由于集合论的语言适应于描述和研究离散对象及其关系，
    它也是计算机科学与工程的基础理论和表达工具，而且在程序设计、数据结构、形式语言、关系数据库、操作系统等计算机科学分支领域都有重要的应用。

图论

  • 图论是一个古老的数学分支，它的创始人是18世纪的数学家欧拉（Euler）
  • 1736年欧拉解决了哥尼斯堡七桥问题，奠定图论和拓扑学的基础。
  • 1847年，物理学家基尔霍夫（Kirchhoff）将图论应用于电网，引进“树”的概念。
  • 1859年哈密顿提出周游世界游戏—图论应用于数学游戏研究中
  • 1850年著名难题“四色猜想”，直到1976年由美国的阿普尔（Appel）、黑肯（Hakan）和考齐（Koch）利用电子计算机加以解决。

代数系统

  • 19世纪伽罗瓦（Galois）提出群的概念。
  • 20世纪以来，代数学研究对象和研究方法发生了重大变革，形成了抽象代数学。抽象代数学研究一般的数学结构，它对现代数学研究具有基本的重要性。在计算机科学研究中占有重要的地位和作用，对计算机科学产生和发展具有决定性的影响。
  • 没有抽象代数结构研究和数理逻辑研究的先行发展，图灵不可能在1936年提出图灵机这样的代数结构作为计算的模型。
  • 20世纪50年代，关系代数理论能够作为数据库理论模型。
  • 在计算机算法设计与分析中，代数算法研究占主导地位，便于形式描述、正确性和终止性证明以及复杂性分析。
  • 代数系统是离散数学的重要组成部分。

如何学好离散数学

延伸学习内容:算法

Chapter 1 集合的基本概念及其运算

集合与元素

  • 集合是人们能够明确区分的一些对象(客体)构成的一个整体。 by contor, 1875
  • 集合通常用大写英文字母表示，通常用：
    N 表示自然数集合(含0)， R 表示实数集合，
    Q 表示有理数集合， I (Z) 表示整数,I+表示正整数集合,I-表示负整数集合
  • 元素：集合里含有的对象称为该集合的元素。通常用小写英文字母表示元素。
    如果a 是集合A的元素，则记为 a∈A，否则记为 a∉A

集合的表示方法

  • 枚举法(外延法)：列举出集合中的所有元素，并用花括号括起来。例如：A={a,b,c}
  • 抽象法：用谓词描述集合中元素的属性，其描述形式为{a|P(a)}，例如：A={x|x是自然数}

抽象原则:任给一个性质 P，就确定了一个集合A , A的元素恰好是具有性质P的对象，即:A = { x | P(x) }，也就是说，x ( P(x) <-> xA )

week 2

集合间的相等和包含关系

集合的相等

  • 定义:设 A, B为任意两集合，若A和B含有相同的元素，则称A和B相等, 记作：A=BA=B
    • 集合与其元素排列次序无关
    • 集合与其元素重复出现次数无关
    • 集合的元素可以是一个集合

集合的包含关系

  • 定义(子集或包含):若集合A的每一个元素都是集合 B 的元素，则称 A是 B 的子集，也称 A 包含于 B 或 B 包含 A 。记作：A⊆BA\subseteq B，即：
    A⊆B⇔∀x(x∈A→x∈B)A\subseteq B \Leftrightarrow \forall x(x\in A \rightarrow x\in B)
  • 定义(真子集):若集合A是集合B的子集，且A不等于B，则称A是B的真子集，记作：A⊂BA\subset B，即：
    A⊂B⇔∀x(x∈A→x∈B)∧∃x(x∈B∧x∉A)A\subset B \Leftrightarrow \forall x(x\in A \rightarrow x\in B) \wedge \exists x(x\in B \wedge x\notin A)

属于与包含的区别

  • 关系"∈\in“和”⊆\subseteq"的区别

∈\in：构成集合A的元素a与A是"∈\in“关系
⊆\subseteq：集合A的子集B与A是”⊆\subseteq"关系

问题：设A，B为集合，A∈BA\in B与A⊆BA \subseteq B是否能同时成立？
答：可以同时成立，设S={ {1，3}，4}，T={ {1，3}，4，{ {1，3}，4} }，则S∈TS\in T且S⊆TS\subseteq T

例题

定理1：设A，B为集合，则A=BA=B 当且仅当A⊆B⇔B⊆AA\subseteq B\Leftrightarrow B\subseteq A
定理2：设A、B、C为集合，若A⊆BA\subseteq B且B⊆CB\subseteq C，则A⊆CA\subseteq C

两个特殊集合

全集

定义：在对集合的研究中，如果所讨论的
集合，都是某一固定集合U的子集，称集合U为全集，
记作 U，即
U={x∣P(x)∨¬P(x)}U=\{x|P(x)\vee \lnot P(x) \}

空集

  • 定义：不含有任何元素的集合称为空集, 记作 $\varnothing $ ，即 ∅={x∣P(x)∨¬P(x)}\varnothing = \{x | P(x)\vee \lnot P(x) \}，其中P(x)是任意谓词。
  • 定理3：设A是任意集合，则∅⊆A\varnothing \subseteq A。
  • 定理4：空集是唯一的。

幂集

幂集的定义

  • 定义：集合 A 的全部子集构成的集合称为A的幂集， 记作 P(A)，即
    P(A)={X│X⊆A}P(A) = \{X│X⊆A \}

有穷集的幂集的基数

  • 有穷集的基数的定义：
    有穷集合A中所含有元素的个数称为 A 的基数。 记作 #A(或 |A|，n(A))。

  • 定理5：设A为有穷集，则#P(A)=2#A

集合的运算

∩（交）、∪（并）、－（差 ，也称相对补）、~（补，也称绝对补）、 ⊕\oplus （对称差）、$\bigcap （广义交）、（广义交）、\bigcup $（广义并）

交、并、差

  • 定义：设 A 和 B 是任意两个集合，
    (1) A∩B={x∣x∈A∧x∈B}A∩B = \{ x | x∈A ∧ x∈B \}
    (2) A∪B={x∣x∈A∨x∈B}A∪B = \{ x | x∈A ∨ x∈B \}
    (3) A－B={x∣x∈A∧x∉B}A－B = \{ x | x∈A ∧ x\notin B \}
  • 定义：若集合 A 和 B 没有公共元素，即$ A∩B =\varnothing $，则称 A 和 B 是不相交的。

补集

  • 定义：设A是全集U的子集，A 相对于 U 的补
    集$ U－A $称为 A 的绝对补集，简称A的补集，记作 ∼A\sim A ，即
    ∼A={x∣x∈U∧x∉A}={x∣¬(x∈A)}\sim A = \{ x | x∈U ∧ x\notin A \}= \{x | \lnot (x\in A) \}

对称差集

  • 定义：: 设 A 和 B 是任意两个集合，A
    和 B 的对称差集，记为 AÅB ，定义为
    A⊕B=(A－B)∪(B－A)A\oplus B = ( A－B)\cup (B－A)

A⊕B=(A∩∼B)∪(B∩∼A)A \oplus B = ( A\cap \sim B )∪ (B \cap \sim A )
A⊕B=(A∪B)－(A∩B)A\oplus B = (A\cup B) －(A\cap B)

集合运算的性质

  • 定理6：设A、B、C为任意集合，则
    1. A⊆A∪BA \subseteq A\cup B 且B⊆A∪BB\subseteq A\cup B;
    2. A∩B⊆AA\cap B \subseteq A且 A∩B⊆BA\cap B\subseteq B；
    3. A－B⊆AA－B \subseteq A;
    4. A－B=A∩∼BA－B = A\cap \sim B；
    5. 若$ A \subseteq B$，则 ∼B⊆∼A\sim B\subseteq \sim A；
    6. 若$A \subseteq C 且且 B \subseteq C，则，则 A\cup B \subseteq C$；
    7. 若$ A \subseteq B 且且 A \subseteq C，则，则 A \subseteq B\cap C$。