跳转至

1 Sets, Relations, and Languages

1.1 Some concepts

这些内容在离散数学课程中基本都有涉及，这里仅仅做一个罗列。

下面是涉及到集合和关系的一些概念

  • Power Set 幂集
  • Properties of Relations (Reflexive, Symmetric, Antisymmetric, Transitive)
  • Equivalence Relation (Reflexive, Symmetric, Transitive)
  • Partial Order (Reflexive, Transitive, Antisymmetric)
  • Total Order
  • Closure

涉及到集合的大小的概念

  • Equinumerous 等势（可以构成双射）
  • 可数集和不可数集
  • \(|\mathbb{R}|> |\mathbb{N}|\)
  • Continuum hypothesis (by Cantor) 没有一个集合的势大于自然数集且小于实数集
  • Cantor’s Theorem 任意集合的幂集的势比原集合的势要大【考虑集合 \(\{x\in A | x\notin f(x)\}\) ，其中 \(f(x)\) 是假设的从 \(A\) 到 \(P(A)\) 的映射，这个集合没有从 \(A\) 映射过来的元素】
  • The Diagonalization Principle
Note

1.2 Alphabet and Language

Alphabet 字母表，任意有限的集合都可以被称为字母表，用 \(\Sigma\) 来表示。

String 字符串，由字母表组成的有限序列

  • \(e\) 代表空串
  • \(\Sigma^*\) 代表由字母表 \(\Sigma\) 组成的所有字符串的集合

字符串的一些操作

  • Concatenation: \(x \circ y\) or \(xy\)

  • Substring, suffix, prefix

  • Example: \(\forall w, we = ew = w\)

  • String exponentiation

  • \(w^0 = e\), the empty string

  • \(w^{i+1} = w^i \circ w\), for each \(i \geq 0\)

  • Reversal

  • If \(w\) is a string of length 0, then \(w^R = w = e\)

  • If \(w\) is a string of length \(n + 1 > 0\), then \(w = ua\) for some \(a \in \Sigma\), and \(w^R = au^R\)

Language 语言，是字符串的集合，也就是 \(\Sigma^*\) 的子集

  • 有限语言可以通过列举展示，无限的语言可展示为 \(L = \{w\in \Sigma^*:w \text{ has property } P\}\)

Theorem: If \(Σ\) is a finite alphabet, then \(Σ^∗\) is countably infinite.

Operations of Languages:

  • Union, Intersection, Difference, Complement (\(\bar{L} = \Sigma^* - L\))

  • Exponentiation

  • \(L^0 = \{e\}\)

  • \(L^{i+1} = LL^i\), for each \(i \geq 0\)

  • Concatenation 拼接符号也可以是 ∘，即 \(L_1 ∘L_2\)

\[ L_1L_2 \equiv \{w_1w_2 \mid w_1 \in L_1 \land w_2 \in L_2\} \]

Kleene Star，也是 L 在拼接运算下包含 L 的最小闭包

\[ L^* = \{w \in \Sigma^* : w = w_1 \cdots w_k, k \geq 0, w_1, \dots, w_k \in L\} = L^0 \cup L^1 \cup L^2 \cup \cdots \]

We write \(L^+\) for the language \(LL^*\). Equivalently,

\[ L^+ = \{w \in \Sigma^* : w = w_1 \cdots w_k, k \geq 1, w_1, \dots, w_k \in L\} = L^1 \cup L^2 \cup L^3 \cup \cdots \]

评论区

对你有帮助的话请给我个赞和 star => GitHub stars
欢迎跟我探讨！！！