第1章 数学预备知识
集合论和离散数学为形式语言理论、可计算性理论和计算复杂性分析提供了数学基础。我们首先回顾集合论的表示和基本操作。集合的基数度量集合的大小,并提供无穷集合大小的准确定义。德国数学家George Cantor深入研究集合的属性后得出一条有趣的结论,就是存在不同大小的无穷集。尽管Cantor的工作仅仅表明存在一个完整的无穷集合规模层次,但是这已经足够支持我们把无穷集合分成两类的目的了。这两类分别是可数的和不可数的。如果集合的元素数目与自然数一样多,那么这个集合是可数的无穷集。如果元素数目比自然数多,就是不可数无穷集。 .
在本章中,我们将使用对角化论证(diagonalization argument)结构来证明定义在自然数集合上的函数集合是不可数无穷集。我们在有效过程(effective procedure)和可计算函数(computable func—tion)的意义上达成共识后(这也是本书第三部分的主要目的),将能够确定可以用算法计算的函数集合的大小。通过比较这两个集合的大小,就可以证明存在这样的函数,它们的值不能使用任何算法过程计算得到。
一个集合可能由任意一组对象组成,我们对那些机械化生成元素的集合感兴趣。然后,我们介绍可以产生集合元素的递归定义;接着构造递归生成的集合与数学归纳法之间的关系。归纳已经被证明能够为递归产生的无穷集合中的元素性质提供一个通用的证明技巧。
在本章的*后,我们将复习有向图和树等知识,这是贯穿本书的两种结构,并以图形方式的解释了形式语言理论和计算理论的概念。
……