笔记｜集合论

阅读资料:

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

容斥原理

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

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

字符串

一些术语

字母表 $\mathrm{\Sigma }$ : 字母的 非空有限 集合

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

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

空串: 若 $|x|=0$，则称 $x$ 为空串，记作 $\epsilon$

连接: $x=a_1{a}_2\cdots a_n,y=b_1{b}_2\cdots b_m$，$x$ 和 $y$ 的连接记作 $xy,xy=a_1{a}_2\cdots a_n{b}_1{b}_2\cdots b_m$。另外，$n$ 个 $x$ 的连接记作 $x^n$

${\mathrm{\Sigma }}^{\ast }$ 与 $\mathrm{\Sigma }$

$\mathrm{\Sigma }$ 上的所有字符串构成的集合记作 ${\mathrm{\Sigma }}^{\ast }$，所有非空字符串的集合记作 ${\mathrm{\Sigma }}^{+}$

${\mathrm{\Sigma }}^{\ast }$ 和 $\mathrm{\Sigma }$ 是无穷的

${\mathrm{\Sigma }}^{\ast }$ 的归纳定义:

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

语言

$\mathrm{\Sigma }$ 上的语言: ${\mathrm{\Sigma }}^{\ast }$ 的子集

语言的运算: 设 $A$ 和 $B$ 是 ${\mathrm{\Sigma }}^{\ast }$ 上的语言

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

罗素悖论