离散数学总复习

1、期末总复习期末总复习离散数学离散数学1期期 末末 总总 复复 习习内容提要内容提要考试要求考试要求期末总复习期末总复习离散数学离散数学21 1、命题及其表示、命题及其表示命题的概念：能够判断真假的陈述句。命题的概念：能够判断真假的陈述句。2 2、逻辑联结词、逻辑联结词否定、合取、析取、蕴含、等值否定、合取、析取、蕴含、等值3 3、命题公式与翻译、命题公式与翻译 3.1 3.1 命题公式的定义命题公式的定义 3.2 3.2 命题的符号化：命题的符号化：将一个文字描述的命题写成相应命题公式的形式。将一个文字描述的命题写成相应命题公式的形式。一、数理逻辑一、数理逻辑内容提要内容提要期末总复习期末总复

2、习离散数学离散数学34 4、真值表与等价公式、真值表与等价公式 4.1 4.1 真值表：真值表： 将命题公式在所有赋值下的取值情况列成表。将命题公式在所有赋值下的取值情况列成表。 4.2 4.2 等价公式：等价公式：若命题公式若命题公式A A和和B B在任一赋值的情况下对应的真值都相同，在任一赋值的情况下对应的真值都相同，则称公式则称公式A A与与B B等价。等价。5 5、命题公式的分类与蕴含式、命题公式的分类与蕴含式 5.1 5.1 命题公式的分类：重言式、矛盾式和可满足式。命题公式的分类：重言式、矛盾式和可满足式。 5.2 5.2 蕴含式的定义：蕴含式的定义：设设A A，B B为两个命题公

3、式，若为两个命题公式，若ABAB为重言式，则称为重言式，则称A A蕴含蕴含B.B.期末总复习期末总复习离散数学离散数学47 7、推理理论、推理理论 7.1 7.1 直接证法直接证法 7.2 7.2 间接证法（附加前提证明法、归谬法）间接证法（附加前提证明法、归谬法） 7.3 7.3 推理理论的应用推理理论的应用6 6、范式、范式 6.1 6.1 析取范式与合取范式的定义析取范式与合取范式的定义 6.2 6.2 主析取范式及其求法（真值表法、等值演算法）主析取范式及其求法（真值表法、等值演算法）期末总复习期末总复习离散数学离散数学58 8、谓词的概念与表示、谓词的概念与表示个体常元与个体变元：表

4、示具体或特定个体的词称为个个体常元与个体变元：表示具体或特定个体的词称为个体常元，表示抽象或泛指个体的词称为个体变元体常元，表示抽象或泛指个体的词称为个体变元. .9 9、谓词演算的等价式与蕴含式、谓词演算的等价式与蕴含式谓词演算的等价式谓词演算的等价式谓词演算的蕴含式谓词演算的蕴含式1010、谓词演算的推理理论、谓词演算的推理理论 US、UG、ES、EG规则规则期末总复习期末总复习离散数学离散数学61 1、理解命题的概念。、理解命题的概念。2 2、掌握常见的逻辑联结词及其定义。、掌握常见的逻辑联结词及其定义。3 3、能正确列出命题公式的真值表，掌握、能正确列出命题公式的真值表，掌握等价公式的

5、证法等价公式的证法（等值（等值演算法。演算法。4 4、掌握、掌握主析（合）取范式主析（合）取范式的概念及其求法（真值表法与等值演的概念及其求法（真值表法与等值演法）。法）。5 5、能正确将一个文字描述的命题、能正确将一个文字描述的命题翻译成命题公式，并证明其有翻译成命题公式，并证明其有效性效性。6 6、理解全称量词与存在量词的概念，并能将一个文字描述的命、理解全称量词与存在量词的概念，并能将一个文字描述的命题题翻译翻译成正确的谓词公式。并能将一个实际命题转化为谓词成正确的谓词公式。并能将一个实际命题转化为谓词公式命题并进行证明。公式命题并进行证明。考试要求考试要求期末总复习期末总复习离散数学离

6、散数学7典型例题典型例题1: 1: 下列语句中，属于命题的是（下列语句中，属于命题的是（ ） A A、请勿吸烟！、请勿吸烟！ B B、我正在说谎。、我正在说谎。 C C、雪是黑的。、雪是黑的。 D D、明天开会吗？、明天开会吗？C期末总复习期末总复习离散数学离散数学8典型例题典型例题2: 2: 用等值演算法求以下命题公式的主析取范式：用等值演算法求以下命题公式的主析取范式：().PQR解：解：13457 ()()()()()()()()() ()()()PQRPQRPQRPQRRPPQQRPQRPQRPQRPQRPQRPQRmmmmm 期末总复习期末总复习离散数学离散数学93：写出下面推理的证

7、明。写出下面推理的证明。 如果今天是星期一，则如果今天是星期一，则10点钟要进行离散数学或点钟要进行离散数学或数据结构考试。如果数据结构课程的老师生病，则不数据结构考试。如果数据结构课程的老师生病，则不考数据结构。今天是星期一，并且数据结构课程的老考数据结构。今天是星期一，并且数据结构课程的老师生病，所以今天进行离散数学的考试。师生病，所以今天进行离散数学的考试。解：解： 设设p：今天是星期一；：今天是星期一； q：10点钟要进行离散数学考试；点钟要进行离散数学考试； r： 10点钟要进行数据结构考试；点钟要进行数据结构考试； s：数据结构课程的老师生病；：数据结构课程的老师生病； 典型例题典

8、型例题期末总复习期末总复习离散数学离散数学10 前提：前提：p (q r), s r, p s 结论：结论：q证明：证明： p s s s r r p p (q r) q r q期末总复习期末总复习离散数学离散数学111 1、序偶与笛卡尔积、序偶与笛卡尔积 1.1 1.1 序偶：两个具有固定次序的个体组成一个序偶序偶：两个具有固定次序的个体组成一个序偶. . 1.2 1.2 笛卡尔积：以序偶为元素的集合笛卡尔积：以序偶为元素的集合. .2 2、关系及其表示、关系及其表示 2.1 2.1 关系的概念：笛卡尔积的子集。关系的概念：笛卡尔积的子集。 2.2 2.2 关系的表示：关系的表示：集合表示法

9、、矩阵表示法、关系图表示法。集合表示法、矩阵表示法、关系图表示法。内容提要内容提要二、二元关系二、二元关系期末总复习期末总复习离散数学离散数学123 3、关系的性质、关系的性质 自反、反自反、对称、反对称、传递性。自反、反自反、对称、反对称、传递性。4 4、复合关系和逆关系、复合关系和逆关系5 5、关系的闭包运算、关系的闭包运算 自反、对称、传递闭包的概念和求法自反、对称、传递闭包的概念和求法 期末总复习期末总复习离散数学离散数学136 6、等价关系、等价关系 6.1 6.1 集合的划分与覆盖集合的划分与覆盖 6.2 6.2 等价关系与等价类的概念等价关系与等价类的概念 6.3 6.3 等价关

10、系与划分的一一对应关系等价关系与划分的一一对应关系7 7、次序关系，尤其偏序关系、次序关系，尤其偏序关系 7.1 7.1 偏序关系与偏序集的概念偏序关系与偏序集的概念 7.2 7.2 偏序关系的哈斯图偏序关系的哈斯图 7.3 7.3 偏序集特殊位置的元素（极大、小元，最大、偏序集特殊位置的元素（极大、小元，最大、小元，上、下界，上下确界）小元，上、下界，上下确界）期末总复习期末总复习离散数学离散数学141 1、理解关系的概念，掌握关系的、理解关系的概念，掌握关系的矩阵表示法矩阵表示法与与关系图表示法关系图表示法。2 2、理解关系的五个性质，判断、理解关系的五个性质，判断关系性质关系性质。3 3

11、、理解自反、对称、传递闭包的概念。、理解自反、对称、传递闭包的概念。4 4、理解等价关系、及其与划分的相互诱导。、理解等价关系、及其与划分的相互诱导。5 5、理解偏序关系的概念，哈斯图表示，最大最小值，极大极小、理解偏序关系的概念，哈斯图表示，最大最小值，极大极小值和上下界。值和上下界。考试要求考试要求期末总复习期末总复习离散数学离散数学15典型例题典型例题设设R是非空集合是非空集合A上的二元关系，如果上的二元关系，如果R是自反的、是自反的、_和传递的，则称和传递的，则称R是是A上的一个等价关系上的一个等价关系 对称的对称的期末总复习期末总复习A A1,2,3,4,5,61,2,3,4,5,6

12、，D D是整除是整除关系，哈斯图为：关系，哈斯图为：则则 若若 B B 1,2,3, 61,2,3, 6 6 6为为B B的最大元。的最大元。 1 1为为B B的最小元。的最小元。5 53 31 12 24 46 6则则 若若 B B 1,2,41,2,4 4 4为为B B的最大元。的最大元。 1 1为为B B的最小元。的最小元。6 63 31 12 21 12 24 4期末总复习期末总复习离散数学离散数学171 1、理解代数、子代数、幺元、逆元和等幂元等概念。、理解代数、子代数、幺元、逆元和等幂元等概念。2 2、理解同态的概念。、理解同态的概念。3 3、理解群、半群、循环群等概念。、理解群、

13、半群、循环群等概念。4 4、能证明某个结构是代数、群、半群等。、能证明某个结构是代数、群、半群等。5 5、能够证明代数结构间的同态。、能够证明代数结构间的同态。内容提要内容提要三、代数三、代数期末总复习期末总复习1 1：代数：代数A=A= 如下表所示，指出其中如下表所示，指出其中的幺元，零元。的幺元，零元。* a b ca a b bb a b cc a b ab b为左幺元。为左幺元。 无右幺元。无右幺元。a,ba,b为右零元。为右零元。 无左零元。无左零元。无幺元，零元。无幺元，零元。期末总复习期末总复习2：函数：函数f :II, f (x) = kx, 这里这里k I ，是从，是从 到到

14、的自同态。的自同态。证明：（证明：（1） x,y I ，有，有 f (x+y) = k (x+y)= kx+ ky= f (x)+ f (x) （2）f (0) = k (0)= 0 所以，所以， f 是从是从 到到的自同态。的自同态。期末总复习期末总复习离散数学离散数学203：代数：代数Nk, +k, -1, 0是群吗？是群吗？ 这里这里x-1=k-x。 代数代数Nk, k是群吗？是群吗？ 期末总复习期末总复习离散数学离散数学21内容提要内容提要1 1、图的基本概念、图的基本概念 1.1 1.1 图的定义与分类图的定义与分类 1.2 1.2 子图与生成子图、补图的概念子图与生成子图、补图的概

15、念 1.3 1.3 节点的度数节点的度数2 2、路与图的连通性、路与图的连通性 2.1 2.1 路与回路，简单路与基本路的概念路与回路，简单路与基本路的概念 2.2 2.2 无向图的连通性与连通分支，有向图的强连通无向图的连通性与连通分支，有向图的强连通性、单侧连通性、弱连通性。性、单侧连通性、弱连通性。四、图论四、图论期末总复习期末总复习离散数学离散数学223 3、图的矩阵表示、图的矩阵表示 邻接矩阵的概念。邻接矩阵的概念。4 4、欧拉图、欧拉图 欧拉图的概念与判定欧拉图的概念与判定5 5、树与生成树、树与生成树5.1 5.1 无向树的概念及其等价定义无向树的概念及其等价定义5.2 5.2 无向图的生成树，最小生成树的求法无向图的生成树，最小生成树的求法5.3 5.3 理解最短路径的求法理解最短路径的求法6 6、根树、根树 有向树（根树）的概念有向树（根树）的概念期末总复习期末总复习离散数学离散数学231 1、掌握图的定义，理解有向图与无向图概念。、掌握图的定义，理解有向图与无向图概念。2 2、理解路与回路、简单路与基本路的概念。、理解路与回路、简单路与基本路的概念。3 3、能判定无向图与有向图的连通性。、能判定无向图与有向图的连通性。6 6、掌握无向图与生成树的定义，掌握、掌握无向图与生成树的定义，掌握最小生成树最小生成树的算法。的算