离散数学总复习 1.ppt

第1章 命题逻辑 1、命题及其表示 命题的概念：能够判断真假的陈述句。 2、逻辑联结词 否定、合取、析取、条件、双条件联结词 3、命题公式与翻译 3.1 命题公式的定义 3.2 命题的符号化： 将一个文字描述的命题写成相应命题公式的形式。 1、理解命题公式的概念，能正确判断命题公式的类型。 2、掌握常见的逻辑联结词及其定义。 3、理解命题公式的归纳定义，能正确将一个文字描述的命题翻译成命题公式。 4、能正确列出命题公式的真值表，掌握等价公式的证法（等值演算法），能灵活运用等价公式解决实际逻辑问题。 5、掌握命题公式的分类。 6、掌握蕴含式的证法：真值表法、等值演算法、分析法。 7、掌握主析取范式的概念及其求法（真值表法与等值演法）。 8、推理理论：掌握构造证明法证明逻辑推理题。 3）在一起凶杀案中，公安人员掌握了如下情况： （1）甲或乙是凶手； （2）如果甲是凶手，那么作案地点不在办公室； （3）如果丙的证词真实，则办公室里有枪声； （4）只有作案地点在办公室，丙的证词才不真实。 公安人员因此得出: 如果办公室里无枪声, 那么凶手是乙不是甲. 问：此推理是否有效？ 7）.李明或王平参加这场排球賽，那么红队一定赢这场球赛，如果红队赢了这场球赛，红队将参加全校冠亚军决赛。但红队未能进入全校决赛，故此李明或王平没有参加这场排球赛。 8）.如果乙不参加篮球赛，那么甲就不参加；如果乙参加篮球赛，那么甲和丙就参加；因此，如果甲参加球赛，那么丙就参加。 9）.如果李敏来华工，若王军不生病，则王军一定去看李敏。如果李敏出差广州，则李敏一定来华工。王军没有生病，所以，如果李敏出差广州，王军一定去看望李敏。 3、谓词演算的等价式与蕴含式 3.1 谓词演算的等价式 量词的消去、量词转换律、量词作用域的扩张与收缩、量词分配律 3.2 谓词演算的蕴含式 4、谓词演算的推理理论 US、UG、ES、EG规则 1、理解个体常元与变元、谓词与谓词填式的概念。 2、理解全称量词与存在量词的概念，并能将一个文字描述的命题翻译成正确的谓词公式。 3、掌握谓词演算的等价式证明。 4、能正确应用谓词演算的四个规则进行推理，并能将一个实际命题转化为谓词公式命题并进行证明。 5: 用谓词演算的等价式证明 1、理解集合与元素的概念，会求一个有限集的幂集。 2、掌握集合的交、并、补、差与对称差运算。 3、会用容斥原理解决集合中元素计数问题。 7：一个班级共有52名学生。其中有24人喜欢打篮球，有15人喜欢下棋，有20人喜欢游泳，有6人既喜欢打篮球又喜欢下棋，有7人既喜欢打篮球又喜欢游泳，有2人这3项活动都喜欢，有9人这3项活动都不喜欢。问有多少人既喜欢下棋又喜欢游泳？ 1、掌握笛卡尔积对并集与交集运算的分配律证明。 2、理解关系的概念，掌握关系的矩阵表示法与关系图表示法。 3、理解关系的五个性质，掌握利用关系矩阵与关系图判断关系性质的方法。 4、理解复合关系与逆关系的概念，掌握逆关系的性质证明。 5、理解自反、对称、传递闭包的概念，掌握闭包运算律的证明. 6、理解等价关系、相容关系、偏序关系的概念。 7、理解函数的概念，掌握有限集的函数个数解法。 8、理解单射、满射、双射的概念，能正确判断映射的类型。 9、理解复合函数与逆函数的概念与性质，掌握复合函数与逆函数的求法。 1、掌握图的定义，理解有向图与无向图、简单图与多重图、零图与平凡图、完全图的概念。 2、能灵活运用握手定理解决节点度数问题。 3、理解路与回路、简单路与基本路的概念。 4、能判定无向图与有向图的连通性。 5、掌握邻接矩阵、可达矩阵的求法，了解完全关联矩阵的概念. 6、掌握无向图与生成树的定义，掌握最小生成树的算法。 7、理解根树与二叉树的概念，掌握最优二叉树的Huffman算法。 8、掌握二叉树在计算机中的应用（前缀码的设计）。 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个数字节省多少个二进制码？ 解：（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的最优二叉树。 即最佳前缀码为：{10，010，111，110，001，011