《离散数学》总复习.ppt

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

1、《离散数学》总复习adfadffd第一部分数理逻辑。包括命题逻辑和谓词逻辑。一、离散数学的主要内容有哪些？离散数学的主要内容可以分为四个部分：第二部分集合论。包括集合、关系和函数。第三部分代数系统。包括代数系统的一般概念，几类典型的代数系统。第四部分图论。包括图的基本概念，几种特殊的图。adfadffd二、考试1、题型考试试题的题型有：单项选择题，10道题，占10分。填空题，共10个空，占10分。计算题，共4小题，占20分。证明题，共5题，占30分。2、难易程度考试题的难度不会超过教材、参考书和模拟试题的难度。以简单

2、题占60%，较难题占30%，难题占10%。3、考试范围考试试题覆盖《离散数学》的全部内容。adfadffd第一部分数理逻辑一、内容提要1、命题及其联结词（非、与、或、单条件、双条件）。2、命题公式的析取范式和合取范式（主范式）。3、命题公式间的等价关系和蕴含关系。4、命题演算的推理理论。5、谓词公式的有关概念（量词、谓词、变元、真值指派等）6、谓词公式间的等价关系和蕴含关系。7、谓词演算的推理理论。adfadffd二、重点和难点1、命题公式间的等价关系和蕴含关系。2、命题演算的推理理论(包括命题符号化)。3、谓词公式

3、间的等价关系和蕴含关系。4、谓词演算的推理理论(包括命题符号化)。adfadffd三、例题1、证明推理：(x)(P(x)(Q(x)R(x))),(x)P(x)(x)(P(x)R(x))证：①(x)P(x)P②P(c)ES,①③(x)(P(x)(Q(x)R(x)))P④P(c)(Q(c)R(c))US,③⑤Q(c)R(c)T,②,④,I⑥R(c)T,⑤,I⑦P(c)R(c)T,②,⑥,I⑧(x)(P(x)R(x))EG,⑦adfadffd2、证明推理：(PQ)(RS),(Q

4、P)R,RPQ证：①RP②(QP)RP③(QP)T,①,②,I④RST,①,I⑤(PQ)(RS)P⑥PQT,④,⑤,I⑦PQT,③,⑥,Iadfadffd第二部分集合论集合论包括集合、二元关系和函数，它们之间的关系是：二元关系是一种特殊的集合，集合中的元素都是序偶；函数是一种特殊的二元关系。一、内容提要1、集合的两种表示方法：列举法和描述法。2、特殊的集合：空集、全集、子集和幂集。3、集合的运算：并、交、差和对称差，各种运算的性质。4、集合运算的基本定律：交换律，结合律，分配律，吸收律

5、，德.摩根律等。5、有序n元组、n维笛卡尔积。6、关系的定义：笛卡尔积的子集。adfadffd7、关系的表示方法：集合、矩阵和关系图。8、关系的性质：自反性、反自反性、对称性、反对称性和传递性。9、关系的运算：复合运算、逆运算和闭包运算。10、特殊的二元关系及其相关特性：等价关系（自反性、对称性、传递性）、偏序关系（自反性、反对称性、传递性）、等价类、偏序关系中的特殊元素（极大元、上界等）。11、函数的定义、函数的定义域和值域。12、函数的性质：单射、满射和双射。13、函数的运算：复合函数、逆函数。14、集合的基数。

6、adfadffd二、重点和难点1、掌握元素与集合之间的关系，集合与集合之间的关系。2、运用集合运算的基本定律去化简集合表达式或证明集合等式。3、掌握二元关系的五个性质和二元关系的运算。4、等价关系的证明、等价类的求解，偏序关系的特定元素的求解。5、函数的性质，求复合函数和逆函数。adfadffd三、例题1、这两个关系是否正确？答：正确。在中表示元素；在中表示空集。2、求R={<1,2>,<2,3>,<3,4>}的传递闭包。解：R的传递闭包={<1,2>,<2,3>,<3,

7、4>,<1,3>,<2,4>,<1,4>}。注意：求传递闭包是一个不断重复合并有序对的过程。有序对<1,4>往往被漏掉。3、化简集合表达式：((A∩B)∪A)⊕((B∩~B)⊕A⊕(B∪~B))解：((A∩B)∪A)⊕((B∩~B)⊕A⊕(B∪~B))(吸收律和零律)=A⊕⊕A⊕U(同一律)=A⊕A⊕U(零律)=⊕U=Uadfadffd4、设集合A＝{a,b,c,d,e}，偏序关系R的哈斯图如图所示，若A的子集B={c,d,e}，求：（1）用列举法写出偏序关系R的集合表达式；（2）写出集合B的极大元、极小元、最大

8、元、最小元、上界、下界、上确界、下确界。解：（1）R=IA{,,,,,,}（2）集合B的极大元：c，极小元：d、e，最大元：c，最小元：无，上界：c、a，上确界：c，下界：无，下确界：无。adfadffd5、已知f：RR且f(x)=(x+4)3-2，已知g：RR且g(x