离散数学总复习ppt课件.ppt

《离散数学总复习ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、含B.离散数学47、推理理论7.1直接证法7.2间接证法（附加前提证明法、归谬法）7.3推理理论的应用6、范式6.1析取范式与合取范式的定义6.2主析取范式及其求法（真值表法、等值演算法）离散数学58、谓词的概念与表示个体常元与个体变元：表示具体或特定个体的词称为个体常元，表示抽象或泛指个体的词称为个体变元.9、谓词演算的等价式与蕴含式谓词演算的等价式谓词演算的蕴含式10、谓词演算的推理理论US、UG、ES、EG规则离散数学61、理解命题的概念。2、掌握常见的逻辑联结词及其定义。3、能正确列出命题公式的真值表，掌握等价公式的证法（等值演算法。4、掌握主析（合）取范式的概

3、念及其求法（真值表法与等值演法）。5、能正确将一个文字描述的命题翻译成命题公式，并证明其有效性。6、理解全称量词与存在量词的概念，并能将一个文字描述的命题翻译成正确的谓词公式。并能将一个实际命题转化为谓词公式命题并进行证明。考试要求离散数学7典型例题1:下列语句中，属于命题的是（）A、请勿吸烟！B、我正在说谎。C、雪是黑的。D、明天开会吗？离散数学8典型例题2:用等值演算法求以下命题公式的主析取范式：解：离散数学93：写出下面推理的证明。如果今天是星期一，则10点钟要进行离散数学或数据结构考试。如果数据结构课程的老师生病，则不考数据结构。今天是星期一，并且数据结构课程的

4、老师生病，所以今天进行离散数学的考试。解：设p：今天是星期一；q：10点钟要进行离散数学考试；r：10点钟要进行数据结构考试；s：数据结构课程的老师生病；解题思想:将命题符号化；写出前提和可能结论；使用构造证明法推演出正确结论。p(qr)srpsq典型例题离散数学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.2笛卡尔积：以序偶为元

5、素的集合.2、关系及其表示2.1关系的概念：笛卡尔积的子集。2.2关系的表示：集合表示法、矩阵表示法、关系图表示法。内容提要二、二元关系离散数学123、关系的性质自反、反自反、对称、反对称、传递性。4、复合关系和逆关系5、关系的闭包运算自反、对称、传递闭包的概念和求法离散数学136、等价关系6.1集合的划分与覆盖6.2等价关系与等价类的概念6.3等价关系与划分的一一对应关系7、次序关系，尤其偏序关系7.1偏序关系与偏序集的概念7.2偏序关系的哈斯图7.3偏序集特殊位置的元素（极大、小元，最大、小元，上、下界，上下确界）离散数学141、理解关系的概念，掌握关系的矩阵表示法

6、与关系图表示法。2、理解关系的五个性质，判断关系性质。3、理解自反、对称、传递闭包的概念。4、理解等价关系、及其与划分的相互诱导。5、理解偏序关系的概念，哈斯图表示，最大最小值，极大极小值和上下界。考试要求离散数学15典型例题设R是非空集合A上的二元关系，如果R是自反的、________和传递的，则称R是A上的一个等价关系．对称的A＝{1,2,3,4,5,6}，D是整除关系，哈斯图为：则若B＝{1,2,3,6}6为B的最大元。1为B的最小元。531246则若B＝{1,2,4}4为B的最大元。1为B的最小元。6312124离散数学171、理解代数、子代数、幺元、逆元和等幂

7、元等概念。2、理解同态的概念。3、理解群、半群、循环群等概念。4、能证明某个结构是代数、群、半群等。5、能够证明代数结构间的同态。内容提要三、代数1：代数A=<{a,b,c},*>如下表所示，指出其中的幺元，零元。*abcaabbbabccabab为左幺元。无右幺元。a,b为右零元。无左零元。无幺元，零元。2：函数f:II,f(x)=kx,这里kI，是从到的自同态。证明：（1）x,yI，有f(x+y)=k(x+y)=kx+ky=f(x)+f(x)（2）f(0)=k(0)=0所以，f是从到<