离散数学重点难点.docx

第一篇 数理逻辑
用数学方法来研究推理的规律称为数理逻辑。这里所指的数学方法，就是引进一套严格定义的符号体系的方法，即建立一套形式语言，来研究形式逻辑。所以数理逻辑又称作符号逻辑，它是从量的侧面来研究思维规律的。
现代数理逻辑可分为逻辑演算，证明论，模型论，递归函数论，公理化集合论。这里介绍的是数理逻辑基本的内容：逻辑演算中的命题逻辑和谓词逻辑。数理逻辑与数学的其它分支、计算机科学、人工智能、语言学等学科均有密切联系。
第一章 命题逻辑 (11学时)
本章是以“命题”为中心，主要讨论：命题的表示、命题的演算；命题演算中的公式，及其应用；命题逻辑推理的方法。
本章要求
1.逻辑联结词，要熟练掌握联结词的真值表定义以及它们在自然语言中的含义。其中特别要注意“∨”和“→”的用法。
2.会命题符号化。
3.掌握永真式的证明方法：
(1).真值表。
(2).等价变换，化简成Ｔ。
(3).主析取范式。
4.掌握永真蕴含式的证明方法，熟练记忆并会应用
43页中表1-8.3中的永真蕴含式。
5.掌握等价公式的证明方法，熟练记忆并会应用
43页表1-8.4中的等价公式。
6.熟练掌握范式的写法及其应用。
7.熟练掌握三种推理方法。
本章主要内容
本章主要有以下章节：
第一节．命题及其表示法
第二节．联结词
第三节．命题公式及命题符号化
第四节．重言式与重言蕴含式
第五节．等价公式
第六节．范式
第七节．命题逻辑推理

本章重点、难点
Ø联结词在自然语言中的含义，命题符号化
Ø永真式、永真蕴含式、等价公式的证明方法，相关公式的熟练应用
Ø范式的写法及其应用
Ø命题逻辑的三种推理方法
第二章 谓词逻辑 (9学时)
在第一章命题逻辑中，把命题作为演算的基本单位，一个原子命题只用一个字母表示，而不再对命题中的句子成分及其内部结构进行分析。这样就无法研究命题的更深层次的结构与意义，鉴于上述局限性，使得我们对于一些常见而又简单的命题无法进行解释与推理。所以就要考虑解决这个问题的方法：在表示命题时，既表示出主语（主词），也表示出谓语（谓词），就可以解决上述问题。这就提出了谓词的概念。
本章将从谓词的相关基本概念出发，主要讨论：谓词公式及命题符号化、谓词的演算；谓词演算中的公式，及其应用；谓词逻辑推理的方法。
本章要求
1.准确掌握有关概念。
2.会命题符号化。
3.掌握常用的谓词演算等价公式和永真蕴涵式，包括:
带量词的公式在论域内展开式,量词否定,量词辖域扩充,
量词分配公式。
4.会用等价公式求谓词公式的真值(如P66题(3))。
5.会写前束范式。
6.熟练掌握谓词逻辑推理的三种推理方法。
本章主要内容
本章主要有以下章节：
第一节．基本概念
第二节．谓词公式及命题符号化
第三节．谓词演算的等价式与蕴涵式
第四节．前束范式
第五节．谓词演算的推理理论

本章重点、难点
Ø谓词公式及命题符号化
Ø谓词演算的等价公式和永真蕴涵式的证明方法，相关公式的熟练应用
Ø谓词逻辑的三种推理方法
第二篇 集 合 论
集合是数学中最基本的概念，又是数学各分支、自然科学及社会科学各领域的最普遍采用的描述工具。集合论是离散数学的重要组成部分，是现代数学中占有独特地位的一个分支。
本部分主要介绍朴素集合论的主要内容，其中包括集合论基础（第三章）、二元关系（第四章）、函数（第五章）。
第三章 集合论基础 (4学时)
集合是一个不能精确定义的基本概念.一般地说把具有共同性质的东西,汇集成一个整体,就形成了一个集合.
本章主要介绍朴素集合论的基本内容，包括：什么是集合以及有关子集、空集、全集、补集等概念；集合的基本运算和集合代数的有关公式，在组合计数的有关公式，在组合计数中有着广泛应用的包含排斥原理等。
本章要求
1.掌握集合间三种关系的定义、谓词定义、证明方法。
2.掌握三个特殊集合，会求集合的幂集。
3.掌握集合的五种运算定义、计算方法及性质。
4.会用包含排斥原理解决集合计数问题。
本章主要内容
本章分以下内容来进行讲述：
第一节 集合的概念和表示法
第二节 集合间的关系
第三节 三个特殊集合
第四节 集合的运算
第五节 包含排斥原理

本章重点、难点
Ø集合间三种关系的证明方法
Ø集合的幂集
Ø集合五种运算的计算方法及性质
第四章 二元关系 (11学时)
现实世界中，任何两个或多个事物之间总是存在这样或那样的联系，在逻辑学中我们称这种联系为关系。
关系以集合理论为基础，是关系数据库的理论基础。
本章主要讨论有关二元关系的定义和二元关系的运算及各种性质，其中包含的复合关系和逆关系，等价关系及相容关系都是本章学习的重点。
本章要求
1．关系的概念，表示方法。
2．二元关系的性质的定义，熟练掌握性质的判断及证明。
3．掌握关系的复合、求逆运算(计算方法及有关性质)，了解关系的闭包运算。
4．掌握等价关系的判断，证明，求等价类和商集。
5．掌握相容关系定义，简化图和简化矩阵，相容类，最大相容类，完全覆盖。
6．偏序关系的判断，会画Hasse图，会求一个子集的极小(大)元、最小(大)元、上界与下界、最小上界及最大下界。
本章主要内容
本章分以下内容来进行讲述：
第一节 序偶与笛卡尔定理
第二节 关系及其表示
第三节 关系的性质
第四节 复合关系
第五节 逆关系
第六节 关系的闭包运算*
第七节 集合的划分和覆盖
第八节 等价关系与等价类
第九节 相容关系
第十节 次序关系

本章重点、难点
Ø二元关系性质的判断及证明
Ø关系的运算：关系的复合, 逆关系
Ø等价关系、等价类的划分和商集
Ø偏序关系
第五章 函　　数 (5学时)
函数是数学中的一个基本概念，也是一个重要概念，它广泛应用在数学的多个分支中，在数学的应用和发展中起着十分重要的作用。
函数在计算机领域内有很多应用。如开关理论，自动机理论和可计算性理论等。
本章要求
1.掌握函数的定义。
2.掌握函数的类型, 会判断、会证明。
3.会计算函数的复合(左复合)，求逆函数，知道有关性质。
4.了解集合的特征函数，了解集合的基数、可数集合。
本章主要内容
本章有以下主要章节：
第一节．函数的概念
第二节．函数的复合函数
第三节．逆函数
第四节．集合特征函数与模糊子集*
第五节．集合的基数*

本章重点、难点
Ø函数及函数类型的判断和证明
Ø函数的复合、求逆
第三篇 代数系统
通常所说的“系统”，是在一定情况下，指对某一相对独立或封闭的环境中的集合的元素间的性质、行为和联系。现实世界中存在各种各样的系统。例如：商品交易、军事指挥系统、计算机系统、管理系统等等。
而在数学中所说的系统是指具有某种性质的数学结构。也就是在一个非空集合上，定义了元素间的算法法则和运算所满足的运算律，把这个集合及其上的定义的算法法则叫做一个代数系统。数学中所研究的是抽象的代数系统，它的元素暂时不必代表任何具体对象，而是一个集合中的元素，并且抽象代数系统上的运算也是抽象的函数。
代数系统是数学的一个重要分支，在计算机科学中有广泛的应用，而且计算机科学的发展，也促进了代数学的进一步发展。
第六章 代数系统 (7学时)
针对某个具体问题选用适宜的数学结构去进行较为确切的描述，这就是所谓的“数学模型”。可见，数学结构在数学模型中占有极为重要的位置。我们这里所要研究的是一类特殊的数学结构—由集合上定义若干个运算而组成的系统。我们通常称它为代数系统。它在计算机科学中有着广泛的应用。
本章将从一般代数系统的引入出发，研究一些特殊的代数系统，而这些代数系统中的运算具有某些性质，从而确定了这些代数系统的数学结构。
本章要求
1.掌握二元运算的定义。
2.熟练掌握二元运算的性质的判断及证明。
3.掌握代数系统的同态、同构定义，会证明。了解同构性质的保持。
4.熟练掌握半群、独异点、群、子群、交换群(会证明), 了解循环群。
5.了解子群的陪集, Lagrange定理及其推论。
6.了解环、域的概念。

本章主要内容
本章有以下主要章节：
第一节．代数系统的概念
第二节．二元运算及其性质
第三节．同态与同构
第四节．同余关系*
第五节．半群与独异点
第六节．群与子群
第七节．循环群与置换群*
第八节．陪集与拉格朗日定理*
第九节．环与域*

本章重点、难点
Ø二元运算及其性质
Ø同态与同构的证明
Ø群与子群的性质及证明
第七章 格与布尔代数 (5学时)
从代数的观点出发，我们是否能对一种更为抽象的代数系统进行研究，而这种抽象的代数系统又具有象集合代数，命题代数那样具体的代数系统所具的一些最本质的性质？回答是肯定的，这种抽象的代数系统就是格（Lattice）和布尔代数（Boolean Algebra）
格和布尔代数的理论成为计算机硬件设计和通讯系统设计中的重要工具。在保密学、开关理论、计算机理论和逻辑设计以及其他一些科学和工程领域中，都直接应用了格与布尔代数。
本章要求
1.掌握格的定义, 格的性质，格的同构。
2.会判断格、分配格、有补格和布尔格。
3.重点掌握两个元素的布尔代数的性质(10个)。
4.会写两个元素的布尔表达式的范式(实质是第一章的主析取和主合取范式)。
本章主要内容
本章有以下主要章节：
第一节．格的概念
第二节．几个特殊格
第三节．布尔代数
第四节．布尔表达式与布尔函数

本章重点、难点
Ø格的性质、判断，格的同构
Ø分配格、有界格、有补格、布尔格的判断、性质
第八章 图　　论 (12学时)
图论是个应用十分广泛而又极其有趣数学分支, 物理、学、生物、经济、管理科学、信息论、计算机等各个领域都可以找到图论的足迹。
本章要求
1.掌握图的基本概念(特别注意相似的概念)。
2.熟练掌握图中关于结点度数的定理 (会应用)。
3.无向图的连通性的判定，连通分支及连通分支数的概念。
4.有向图的可达性、强连通、单侧连通和弱连通的判定，求强分图、单侧分图和弱分图。
5.会求图的矩阵。
6.会判定欧拉图和汉密尔顿图。
7.了解平面图。
8.了解着色与对偶图。
9.掌握树的基本定义，v和e间的关系式。会画生成树，会求最小生成树。
10.掌握根树的概念，完全m叉树的公式，会画最优树，会设计前缀码。
本章主要内容
本章主要分以下各节来论述：
第一节 图的基本概念
第二节 路与回路
第三节 图的矩阵表示
第四节 赋权图的最短路与关键路
第五节 欧拉图与汉密尔顿图
第六节 二部图
第七节 平面图
第八节 对偶图与着色
第九节 树与生成树
第十节 根树及其应用

本章重点
Ø图的若干基本概念及相关定理
Ø路与回路
Ø欧拉图和汉密尔顿图的判定及应用
Ø树的等价定义，树与生成树的应用
Ø根树及其应用