理论计算机科学基础：逻辑与证明

"Building Blocks for Theoretical Computer Science (UIUC CS173)" 是伊利诺伊大学厄巴纳-香槟分校（UIUC）开设的一门计算机科学课程，主要涵盖了理论计算机科学的基础概念。该课程资料由Margaret M. Fleck编写，内容包括数学回顾、逻辑和证明等核心主题。 在数学回顾部分，课程首先介绍了集合的基本概念，如集合的定义、性质和不同类型的集合。接着，讲解了实数对，这是理解二维空间和向量的基础。此外，还涉及指数和对数运算，这些是计算和分析函数增长的关键工具。课程还讨论了一些实用的函数，如阶乘、指数函数和对数函数。求和（summations）是数学中的重要概念，用于计算序列或函数的总和，这部分也有所涵盖。字符串的处理在计算机科学中至关重要，尤其是在文本处理和数据存储方面。最后，课程提到了不同来源的符号和记法的变体，强调了理解和适应不同风格的重要性。 逻辑部分深入探讨了命题逻辑，包括简单的命题、复合命题及其结构。课程讲解了逻辑联接词如蕴含、逆否命题、双条件等，以及如何构建复杂的逻辑陈述。逻辑等价是这一部分的重点，学习者将掌握一系列有用的逻辑等价关系，用于简化和推理命题。同时，课程还涵盖了否定命题、谓词和变量、其他量词（如存在量词和全称量词），以及量词作用域的理解。此外，还有关于不同记法的使用和2D点的表示方法，以及如何处理含有量词的否定陈述。 证明是理论计算机科学的核心，课程详细介绍了如何证明普遍性陈述和存在性陈述，以及如何直接和间接地证明或反驳这些陈述。直接证明的方法、反例法和构造性证明的框架都得到了阐述。证明过程中，正确地处理量词的范围（binding and scope）至关重要，这在课程中也有详尽的解释。 UIUC CS173课程旨在为学生打下坚实的理论基础，通过学习数学基础、逻辑推理和证明技巧，为他们进一步研究算法、复杂性理论、计算理论等高级计算机科学主题做好准备。