离散数学总复习.

期末总复习离散数学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蕴含B.期末总复习离散数学47、推理理论7.1直接证法7.2间接证法（附加前提证明法、归谬法）7.3推理理论的应用6、范式6.1析取范式与合取范式的定义6.2主析取范式及其求法（真值表法、等值演算法）期末总复习离散数学58、谓词的概念与表示个体常元与个体变元：表示具体或特定个体的词称为个体常元，表示抽象或泛指个体的词称为个体变元.9、谓词演算的等价式与蕴含式谓词演算的等价式谓词演算的蕴含式10、谓词演算的推理理论US、UG、ES、EG规则期末总复习离散数学61、理解命题的概念。2、掌握常见的逻辑联结词及其定义。3、能正确列出命题公式的真值表，掌握等价公式的证法（等值演算法。4、掌握主析（合）取范式的概念及其求法（真值表法与等值演法）。5、能正确将一个文字描述的命题翻译成命题公式，并证明其有效性。6、理解全称量词与存在量词的概念，并能将一个文字描述的命题翻译成正确的谓词公式。并能将一个实际命题转化为谓词公式命题并进行证明。考试要求期末总复习离散数学7典型例题1:下列语句中，属于命题的是（）A、请勿吸烟！B、我正在说谎。C、雪是黑的。D、明天开会吗？C期末总复习离散数学8典型例题2:用等值演算法求以下命题公式的主析取范式：().PQR解：13457()()()(())(()())()()()()()()PQRPQRPQRPQRRPPQQRPQRPQRPQRPQRPQRPQRmmmmm期末总复习离散数学93：写出下面推理的证明。如果今天是星期一，则10点钟要进行离散数学或数据结构考试。如果数据结构课程的老师生病，则不考数据结构。今天是星期一，并且数据结构课程的老师生病，所以今天进行离散数学的考试。解：设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笛卡尔积：以序偶为元素的集合.2、关系及其表示2.1关系的概念：笛卡尔积的子集。2.2关系的表示：集合表示法、矩阵表示法、关系图表示法。内容提要二、二元关系期末总复习离散数学123、关系的性质自反、反自反、对称、反对称、传递性。4、复合关系和逆关系5、关系的闭包运算自反、对称、传递闭包的概念和求法期末总复习离散数学136、等价关系6.1集合的划分与覆盖6.2等价关系与等价类的概念6.3等价关系与划分的一一对应关系7、次序关系，尤其偏序关系7.1偏序关系与偏序集的概念7.2偏序关系的哈斯图7.3偏序集特殊位置的元素（极大、小元，最大、小元，上、下界，上下确界）期末总复习离散数学141、理解关系的概念，掌握关系的矩阵表示法与关系图表示法。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、理解代数、子代数、幺元、逆元和等幂元等概念。2、理解同态的概念。3、理解群、半群、循环群等概念。4、能证明某个结构是代数、群、半群等。5、能够证明代数结构间的同态。内容提要三、代数期末总复习1：代数A={a,b,c},*如下表所示，指出其中的幺元，零元。*abcaabbbabccabab为左幺元。无右幺元。a,b为右零元。无左零元。无幺元，零元。期末总复习2：函数f:II,f(x)=kx,这里kI，是从I,+,0到I,+,0的自同态。证明：（1）x,yI，有f(x+y)=k(x+y)=kx+ky=f(x)+f(x)（2）f(0)=k(0)=0所以，f是从I,+,0到I,+,0的自同态。期末总复习离散数学203：代数〈Nk,+k,-1,0〉是群吗？这里x-1=k-x。代数〈Nk,×k〉是群吗？期末总复习离散数学21内容提要1、图的基本概念1.1图的定义与分类1.2子图与生成子图、补图的概念1.3节点的度数2、路与图的连通性2.1路与回路，简单路与基本路的概念2.2无向图的连通性与连通分支，有向图的强连通性、单侧连通性、弱连通性。四、图论期末总复习离散数学223、图的矩阵表示邻接矩阵的概念。4、欧拉图欧拉图的概念与判定5、树与生成树5.1无向树的概念及其等价定义5.2无向图的生成树，最小生成树的求法5.3理解最短路径的求法6、根树有向树（根树）的概念期末总复习离散数学231、掌握图的定义，理解有向图与无向图概念。2、理解路与回路、简单路与基本路的概念。3、能判定无向图与有向图的连通性。6、掌握无向图与生成树的定义，掌握最小生成树的算法。7、理解根树概念。考试要求期末总复习离散数学241、考试题型单项选择题；填空题；解答题；证明题考试为闭卷考试平时成绩占30%，卷面成绩占70%期末总复习离散数学25结语：离散数学课程至此结束，感谢同学们这一学期来的支持与配合.祝各位同学考得好成绩！