离散数学复习与应试指导

　　本书是根据全国高等教育自学考试指导委员会审定的"离散数学考试大纲"编写的自学指导用书，主要内容包含命题逻辑、谓词逻辑、集合与函数、代数结构、图论五章。本书针对考试要求按章系统总结了主要的概念、定理、公式，针对不同的知识点明确列出了解题要求，并通过大量的典型例题及其求解过程分析了解题的方法、步骤以及书写规范。为了帮助读者进一步掌握离散数学的概念和解题技巧，本书在每章的后面给出了大量的练习并在第六章提供了6套综合练习。这些练习包含了自学考试离散数学的主要题型，全部练习都附有答案或解答，以供读者在总复习时进行模拟测试。
　　

第一章 命题逻辑
1．1 内容提要
1．2 题例分析
1．3 习题
1．4 习题解答
第二章 谓词逻辑
2．1 内容提要
2．2 题例分析
2．3 习题
2．4 习题解答
第三章 集合与函数
3．1 内容提要
3．2 题例分析
3．3 习题
3．4 习题解答
第四章 代数结构
4．1 内容提要
4．2 题例分析
4．3 习题
4．4 习题解答

　　本书是以全国高等教育自学考试指导委员会审定的"离散数学"考试大纲为依据，参考全国高等教育自学考试指导委员会组编的考试指定教材(《离散数学》，左孝凌，经济科学出版社，2000年9月)编写的，本书行文中出现的"指定教材"均指这本书。
　　和经典的高等数学不同，离散数学的内容比较分散。一般的离散数学教材都由若干个相对独立的部分构成，主要有数理逻辑、集合论、代数结构与图论。它的特点就是概念、定义、定理多，全部内容缺乏一个完整的体系，复习时不知如何下手。此外，离散数学的题型比较丰富，解题方法比较灵活，这些对于初次接触离散数学的考生而言确实有较大的难度。很多考生反映教材看得懂，就是不知道题目怎么做，做了也不知道对不对。为此，我们根据多年来参加北京市自学考试离散数学命题及阅卷的经验和从事离散数学教学所积累的大量习题资料编写了这本复习和应试指南。
　　本书不是一本系统讲授离散数学概念和理论的书籍，它可以作为指定教材的配套辅导书。写作本书的目的就是为了对所有自学离散数学的人在复习和解题方面提供细致深入的帮助。全书总计提供了300多道例题和习题，包含了离散数学的主要题型。本书的特点是：
　　1．根据考试要求按章系统地列出了应该掌握的主要知识点(定义、定理、公式等)并进一步解释了它们之间的区别和联系，系统总结了所有的重要公式和结论。
　　2．按章将考试大纲细化，列出了对考生的具体解题要求，包括：基本概念、基本计算、基本的证明方法，基本的应用，等等。
　　3．根据解题要求和离散数学考试的常见题型按章给出了大量的典型例题、答案和解题过程；并根据不同的题型，进一步分类说明了解题中常见的错误或应该注意的问题。同时通过系列习题的分析，总结了常用的解题方法、步骤和书写规范。
　　4．在每章后面提供了大量的配套练习和解答，以帮助考生作阶段复习，巩固和练习通过例题所学到的基本解题方法。
　　5．全书最后给出了6套综合练习和解答，以供考生在总复习时进行模拟测试。
　　本书包含五章，即命题演算、谓词演算、集合与函数、代数结构和图论。其中第一、二、五章由耿素云完成，第三、四章由屈婉玲完成，第六章的综合练习由两人合作完成。书中选题主要取自书后的参考书。考虑到指定教材中的部分内容和习题，特别是证明题，难度超出了自学考试的基本要求，我们在相应的部分加了*号，对其中的难点和容易混淆的概念进一步做了阐述，并对习题做出了详细的解答。
　　出版这本书仅仅是期望能够对自学离散数学的考生有所帮助。我们诚恳地欢迎读者提出宝贵意见!
　　作 者
　　2001年10月于北京大学
　　

　　二十多年高等教育自学考试事业的蓬勃发展已经证明，自学考试是继续教育的一种重要形式，它为我国社会主义建设事业培养了大量的有用人才。特别是近年来各行各业对于计算机专业人才的大量需求使得普通高校计算机专业的毕业生供不应求。因此，高教自考的"计算机与应用"专业受到了广大考生的热烈欢迎。但是对于自学考生来说，这个专业的学习并不是一件轻松的事情。它要求考生必须熟练掌握所学课程的基本概念、基本理论以及基本的解题方法和技巧。
　　北京大学计算机科学技术系多年来一直承担着北京市"计算机软件与应用"专业·(自2001年按照全国统考的新计划，改为"计算机与应用"专业)的主考任务，许多教师直接参与了大量的命题、阅卷等项工作。他们不仅有着丰富的教学经验，同时在多年的主考工作中积累了大量的试题资料。他们对于自考的特点和自学考生在学习中的困难有着比较深入的了解和切身的体会。为了帮助自学考生切实掌握"计算机与应用专业"考试课程的重点和难点，北京大学出版社组织计算机系的教师编写了这套专业课程的辅导丛书。它按照考试计划所规定的课程来组织，每本辅导书都包含下述主要内容：
　　1．以每门课程的考试大纲为基础，按照章节进行总结，提纲挈领，将零散的知识点串起来，为每个考生列出了包含课程主要知识点的系统的复习提纲。
　　2．在每一章后面都通过大量的例题讲解各种试题的题型、相关的解题方法和规范，并根据历年阅卷的经验，进一步说明考生在解题中容易发生的错误和应该注意的问题。
　　3．针对每一章的要求，为考生提供大量的练习题和答案，以方便考生循序渐进地巩固所学的知识，掌握解题的技巧。
　　4．为了进一步培养比较灵活的分析问题和解决问题的能力，在全书的后面附有综合练习。在系统复习了全部内容后，考生可以用它进行自我测试和考前的模拟冲刺。
　　这套丛书配合考试用书，既可以在日常自学中作为辅导书，也可以用于考前的总复习，同时也为其他在校学生和科技人员学习相关课程提供指导和帮助。
　　我们期望这套丛书能够成为广大考生的良师益友，我们更诚挚地期待着读者的批评和指正。
　　北京大学计算机科学技术系
　　副系主任 屈婉玲
　　2001年7月5日