2011复习提纲.docVIP

复习提纲 一、命题逻辑 1. 5个连接词，是运算，运算的优先级别及运算的性质 合式公式的定义方法（归纳定义法，P57） 3. 含n个命题变元的合式公式的解释的个数（P8倒数第14行）， 它的真 值表有多少行？ 主范式：任何一个合式公式的主范式都是存在的且唯一；永假式与永真 式的主范式有点特殊，是规定的（P20第15行，P23第1行）。求一个公 式的主范式的过程，最后的结果的表达； 参考练习题：P24第2题的第2小题，第3题的第2小题 5. 推理证明应注意的事项（推理规则，三种证明方法），注意表达的规范 二、谓词逻辑 1. 一个公式的解释的个数是无穷的。 2. 对量词的理解：P38 4. 3. 在合式公式中变元的约束出现与自由出现 参考练习：P40的第1题 三、集合与关系 1. 集合的运算：交、差、并和补，幂集，笛卡尔积的基数相关知识 2. 关系的定义，二元关系的前域、定义域、陪域、值域的概念 3. 关系的三种表示方法，给出一个具体的二元关系，会正确地 画出其关系图和关系矩阵。 恒等关系及其表示符号（IA）、关系矩阵(单位矩阵)及关系图的特征； 全域关系的关系矩阵和关系图的特征 关系的五个性质及其在关系矩阵和关系图中的特征（仔细读P80倒数第18行开始的一整个自然段。） 关系的自反性与反自反性是完全排斥的吗？关系的对称性与 反对称性呢？ （P80倒数第9行开始的整个自然段及例4.2.3） 9 Warshall算法的作用是什么？（有限集合上的二元关系的传递闭包） 等价关系的定义，等价关系中每个元素的等价类的定义及求法 等价关系中商集的概念及求商集的方法 一个集合的划分的概念。 一个集合上的等价关系与该集合上的划分之间的关系 一个集合上划分的个数与等价关系的个数（P96例4.4.7） 偏序关系、覆盖（P100例4.5.2）及其Hasse图的画法，及偏序集合的任意子集中最元、极元、上下界、上下确界的概念及求法（P104第1题） 函数的定义。恒等函数的概念。函数中前域与定义域的关系，陪域与值域间的关系 X、Y是有限集合，Y的X次方所表达的意思？（P112定义5.1.3） 单射、满射及双射的定义。 当函数的前域与陪域均为有限集合时，函数的性质与集合的基数之间的关系。（P114定理5.1.1） 代数运算的定义，运算的阶的概念。 运算的性质。 特殊元的定义及求法（P146第4题、第7题） 同态与同构是用来描述两个代数系统的关系的 半群、独异点的定义（P160第2题，P164第2题）