笔记｜集合论

阅读资料:

• 博客园｜计算机起源的数学思想

容斥原理

引理 若 \(A\) 和 \(B\) 是集合，且 \(A \cap B = \varnothing\)，则 \(\#(A \cup B) = \# (A) + \#(B)\)

定理 若 \(A\) 和 \(B\) 是集合，则 \(\# (A \cup B) = \# (A) + \#(B) - \#(A \cap B)\)

字符串

一些术语

字母表 \(\Sigma\) : 字母的 非空有限 集合

字符串: 由 \(\Sigma\) 中的字母组成的有穷序列。例如: \(a, b, aabb\) 是 \(\Sigma = \{a, b, c\}\) 上的字符串

字符串的长度: 所含字母的个数，记作 \(|x|\)

空串: 若 \(|x| = 0\)，则称 \(x\) 为空串，记作 \(\varepsilon\)

连接: \(x = a_1a_2\cdots a_n, y = b_1b_2\cdots b_m\)，\(x\) 和 \(y\) 的连接记作 \(xy, xy = a_1a_2\cdots a_n b_1b_2\cdots b_m\)。另外，\(n\) 个 \(x\) 的连接记作 \(x^n\)

\(\Sigma^*\) 与 \(\Sigma\)

\(\Sigma\) 上的所有字符串构成的集合记作 \(\Sigma^*\)，所有非空字符串的集合记作 \(\Sigma^+\)

\(\Sigma^*\) 和 \(\Sigma\) 是无穷的

\(\Sigma^*\) 的归纳定义:

1. \(\varepsilon \in \Sigma^*\)
2. 若 \(x \in \Sigma^*\) 且 \(a \in \Sigma\)，则 \(xa\in \Sigma^*\)
3. \(\Sigma^*\) 中的每一个元素都可以有限次应用 (1)(2) 得到

语言

\(\Sigma\) 上的语言: \(\Sigma^*\) 的子集

语言的运算: 设 \(A\) 和 \(B\) 是 \(\Sigma^*\) 上的语言

1. 乘积/连接 \(AB\): \(AB = \{xy | x \in A \wedge y \in B\}\)
2. 幂 \(A^n\): \(A^0 = \{\varepsilon\}, A^{n+1} = A^n A\)
3. 闭包 \(A^*\): \(A^* = \{\varepsilon\} \cup A \cup A^2 \cup \cdots\)

罗素悖论