离散数学总复习课件

1、离散数学,1,期 末 总 复 习,内容提要 考试要求 典型例题,离散数学,2,1、命题及其表示 命题的概念：能够判断真假的陈述句。 2、逻辑联结词 否定、合取、析取、条件、双条件联结词 3、命题公式与翻译 3.1 命题公式的定义 3.2 命题的符号化： 将一个文字描述的命题写成相应命题公式的形式。,第1章 命题逻辑,内容提要,离散数学,3,4、真值表与等价公式 4.1 真值表： 将命题公式在所有赋值下的取值情况列成表。 4.2 等价公式： 若命题公式A和B在任一赋值的情况下对应的真值都相同，则称公式A与B等价。 5、命题公式的分类与蕴含式 5.1 命题公式的分类：重言式、矛盾式和可满足式。 5

2、.2 蕴含式的定义： 设A，B为两个命题公式，若AB为重言式，则称A蕴含B.,离散数学,4,7、推理理论 7.1 直接证法 7.2 间接证法（附加前提证明法、归谬法） 7.3 推理理论的应用,6、范式 6.1 析取范式与合取范式的定义 6.2 主析取范式及其求法（真值表法、等值演算法）,离散数学,5,1、理解命题公式的概念，能正确判断命题公式的类型。 2、掌握常见的逻辑联结词及其定义。 3、理解命题公式的归纳定义，能正确将一个文字描述的命题翻译成命题公式。 4、能正确列出命题公式的真值表，掌握等价公式的证法（等值演算法），能灵活运用等价公式解决实际逻辑问题。 5、掌握命题公式的分类。 6、掌握

3、蕴含式的证法：真值表法、等值演算法、分析法。 7、掌握主析取范式的概念及其求法（真值表法与等值演法）。 8、能灵活应用主析取范式解决实际问题。,考试要求,离散数学,6,典型例题,1: 下列语句中，属于命题的是（ ） A、请勿吸烟！ B、我正在说谎。 C、雪是黑的。 D、明天开会吗？,离散数学,7,典型例题,2: 用等值演算法求以下命题公式的主析取范式：,解：,离散数学,8,3：写出下面推理的证明。 如果今天是星期一，则10点钟要进行离散数学或 数据结构考试。如果数据结构课程的老师生病，则不考数据结构。今天是星期一，并且数据结构课程的老师生病，所以今天进行离散数学的考试。 解： 设p：今天是星期

4、一； q：10点钟要进行离散数学考试； r： 10点钟要进行数据结构考试； s：数据结构课程的老师生病；,解题思想: 将命题符号化；写出前提和可能结论；使用构造证明法推演出正确结论。,p (q r),s r,p s,q,典型例题,离散数学,9,前提：p (q r), s r, p s 结论：q 证明： p s s s r r p p (q r) q r q,前提引入,化简规则,前提引入,析取三段论,假言推理,假言推理,前提引入,化简规则,离散数学,10,第2章 谓词逻辑,内容提要,1、谓词的概念与表示 1.1 个体常元与个体变元：表示具体或特定个体的词称为个体常元，表示抽象或泛指个体的词称为个

5、体变元. 1.2 谓词与谓词填式、个体域的概念 1.3 全称量词与存在量词的概念 2、谓词公式与翻译 2.1 谓词公式的概念 2.2 谓词公式的翻译,离散数学,11,3、谓词演算的等价式与蕴含式 3.1 谓词演算的等价式 量词的消去、量词转换律、量词作用域的扩张与收缩、量词分配律 3.2 谓词演算的蕴含式 4、谓词演算的推理理论 US、UG、ES、EG规则,离散数学,12,1、理解个体常元与变元、谓词与谓词填式的概念。 2、理解全称量词与存在量词的概念，并能将一个文字描述的命题翻译成正确的谓词公式。 3、掌握谓词演算的等价式证明。 4、能正确应用谓词演算的四个规则进行推理，并能将一个实际命题转

6、化为谓词公式命题并进行证明。,考试要求,离散数学,13,典型例题,4:下面给出的谓词逻辑等价式中，正确的是（ ）,离散数学,14,5: 用谓词演算的等价式证明,证明：,离散数学,15,1、集合的基本概念 集合与元素的概念，幂集的概念 2、集合的运算 集合的交、并、补、差、对称差运算 3、集合中元素的计数 容斥原理,内容提要,第3章 集合,离散数学,16,1、理解集合与元素的概念，会求一个有限集的幂集。 2、掌握集合的交、并、补、差与对称差运算。 3、会用容斥原理解决集合中元素计数问题。,考试要求,离散数学,17,典型例题,6：证明下列等式：,证明：,离散数学,18,7：一个班级共有52名学生。

7、其中有24人喜欢打篮球，有15人喜欢下棋，有20人喜欢游泳，有6人既喜欢打篮球又喜欢下棋，有7人既喜欢打篮球又喜欢游泳，有2人这3项活动都喜欢，有9人这3项活动都不喜欢。问有多少人既喜欢下棋又喜欢游泳？,典型例题,离散数学,19,1、序偶与笛卡尔积 1.1 序偶：两个具有固定次序的个体组成一个序偶. 1.2 笛卡尔积：以序偶为元素的集合. 2、关系及其表示 2.1 关系的概念：笛卡尔积的子集。 2.2 关系的表示： 集合表示法、矩阵表示法、关系图表示法。,内容提要,第4章 二元关系与函数,离散数学,20,3、关系的性质及其判定方法 3.1 关系的性质： 自反、反自反、对称、反对称、传递性。 3

8、.2 由关系图、关系矩阵判别关系的性质。 4、复合关系和逆关系 4.1 复合关系的概念、性质用矩阵表示 4.2 逆关系的概念及其性质 5、关系的闭包运算 5.1 自反、对称、传递闭包的概念 5.2 闭包运算的求法 5.3 求传递闭包的Warshall算法,离散数学,21,6、等价关系 6.1 集合的划分与覆盖 6.2 等价关系与等价类的概念 6.3 等价关系与划分的一一对应关系 7、偏序关系 7.1 偏序关系与偏序集的概念 7.2 偏序关系的哈斯图 7.3 偏序集特殊位置的元素（极大、小元，最大、小元，上、下界，上下确界）,离散数学,22,8、函数 8.1 函数的概念 函数的概念，有限集的函数

9、个数问题 8.2 特殊映射 单射、满射、双射的概念 8.3 复合函数与逆函数 复合函数与逆函数的概念及其性质,离散数学,23,1、掌握笛卡尔积对并集与交集运算的分配律证明。 2、理解关系的概念，掌握关系的矩阵表示法与关系图表示法。 3、理解关系的五个性质，掌握利用关系矩阵与关系图判断关系性质的方法。 4、理解复合关系与逆关系的概念，掌握逆关系的性质证明。 5、理解自反、对称、传递闭包的概念，掌握闭包运算律的证明. 6、理解等价关系、相容关系、偏序关系的概念。 7、理解函数的概念，掌握有限集的函数个数解法。 8、理解单射、满射、双射的概念，能正确判断映射的类型。 9、理解复合函数与逆函数的概念与

10、性质，掌握复合函数与逆函数的求法。,考试要求,离散数学,24,典型例题,8：设R、R1、R2都是从 X 到 Y 的二元关系，证明：,9：设R是非空集合A上的二元关系，如果R是自反的、_和传递的，则称R是A上的一个等价关系,对称的,10：设A, B是集合且|A|=3、|B|=4，则从A到B可定义_个不同的映射,64,离散数学,25,内容提要,1、图的基本概念 1.1 图的定义与分类 1.2 子图与生成子图、补图的概念 1.3 节点的度数与握手定理 1.4 图的同构概念 2、路与图的连通性 2.1 路与回路，简单路与基本路的概念 2.2 无向图的连通性与连通分支，有向图的强连通性、单侧连通性、弱连

11、通性。,第7、8、9章 图论,离散数学,26,3、图的矩阵表示 邻接矩阵、可达矩阵的概念的求法，完全关联矩阵的概念 4、欧拉图与哈密尔顿图 欧拉图的概念与判定，哈密尔顿图的概念 5、树与生成树 5.1 无向树的概念及其三个等价定义 5.2 无向图的生成树，最小生成树的求法 6、根数及其应用 6.1 有向树的概念，二叉树的概念与最优二叉树 6.2 二叉树在计算机中的应用,离散数学,27,1、掌握图的定义，理解有向图与无向图、简单图与多重图、零图与平凡图、完全图的概念。 2、能灵活运用握手定理解决节点度数问题。 3、理解路与回路、简单路与基本路的概念。 4、能判定无向图与有向图的连通性。 5、掌握

12、邻接矩阵、可达矩阵的求法，了解完全关联矩阵的概念. 6、掌握无向图与生成树的定义，掌握最小生成树的算法。 7、理解根树与二叉树的概念，掌握最优二叉树的Huffman算法。 8、掌握二叉树在计算机中的应用（前缀码的设计）。,考试要求,离散数学,28,11：假设在通讯中，十进制数字出现的频率是 0：20%； 1：15%； 2：10%； 3：10%； 4：10%； 5：5%； 6：10%； 7：5%； 8：10%； 9：5% （1）求传输它们的最佳前缀码。 （2）用最佳前缀码传输10000个按上述频率出现的数字需要多少个二进制码？ （3）它比用等长的二进制码传输10000个数字节省多少个二进制码？,

13、典型例题,离散数学,29,解：（1）令i对应树叶权为wi，wi=100i，则 w0=20；w1=15； w2=10；w3=10； w4=10；w5=5； w6=10；w7=5； w8=10；w9=5。 构造一棵带权5,5,5,10,10,10,10,10,15, 20的最优二叉树。,离散数学,30,图 9.2.11,w0=20；,w1=15；,w2=10；,w3=10；,w4=10；,w5=5；,w6=10；,w7=5；,w8=10；,w9=5。,离散数学,31,即最佳前缀码为：10，010，111，110，001，0111，0001，0110，00000，00001。,(2) (220%+3(10%+15%+10%+10%)+4(5%+10%+10%)+5(5%+5%)10000=32500 即传输10000个数字需32500个二进制码。,（3）因为用等长码传输10个数字码长为4，即用等长的码传10000个数字需40000个二进制码，故用最佳前缀码传节省了7500个二进制码。,离散数学,32,1、考试题型,单项选择题；填空题；计算证明题；综合应用题,2、考试范围及分数比例,考试范围包