离散数学期末复习要点与重点.doc

《离散数学期末复习要点与重点.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、离散数学期末复习要点与重点离散数学计算机科学与技术专业的一门统设必修学位课程，共60学时，开设一学期．该课程的主要内容包括：数理逻辑、集合论、图论等．第1章命题逻辑复习要点1．理解命题概念，会判别语句是不是命题．理解五个联结词：否定ØP、析取Ú、合取Ù、条件®、和双条件«及其真值表，会将简单命题符号化．具有确定真假意义的陈述句称为命题．命题必须具备：其一，语句是陈述句；其二，语句有唯一确定的真假意义.2．了解公式的概念(公式、赋值、成真赋值和成假赋值)和公式真值表的构造方法．能熟练地作公式真值表．理解永真式和永假式概念，掌握其判别方法．判定命题公式类型的方法：其一是真值表法，其二

2、是等值演算法.3．了解公式等价概念，掌握公式的重要等价式和判断两个公式是否等价的有效方法：等值演算法、列真值表法和主范式方法．4．理解析取范式和合取范式、极大项和极小项、主析取范式和主合取范式的概念以及和成真赋值、成假赋值的关系，熟练掌握它们的求法．命题公式的范式不惟一，但主范式是惟一的．5．了解C是前提集合{A1,A2,…,Am}的有效结论或由A1,A2,…,Am逻辑地推出C的概念．要理解并掌握推理理论的规则、重言蕴含式和等价式，掌握命题公式的证明方法：真值表法、直接证法、间接证法．重点：命题与联结词，公式与解释，真值表，公式的类型及判定，主析取(合取)范式，命题演算的推理理论

3、.第2章谓词逻辑复习要点1．理解谓词、量词、个体词、个体域，会将简单命题符号化．原子命题分成个体词和谓词，个体词可以是具体事物或抽象的概念，分个体常项和个体变项．谓词用来刻划个体词的性质或之间的关系．量词分全称量词"，存在量词$.命题符号化注意：使用全称量词"，特性谓词后用®；使用存在量词$，特性谓词后用Ù．2．了解原子公式、谓词公式、变元(约束变元和自由变元)与辖域等概念．掌握在有限个体域下消去公式的量词和求公式在给定解释下真值的方法．由原子公式、联结词和量词构成谓词公式．谓词公式具有真值时，才是命题．在谓词公式"xA或$xA中，x是指导变元，A是量词的辖域．会区分约束变元和自

4、由变元．在非空集合D(个体域)上谓词公式A的一个解释或赋值有3个条件．在任何解释下，谓词公式A取真值1，A为逻辑有效式(永真式)；公式A取真值0，A为永假式；至少有一个解释使公式A取真值1，A称为可满足式．会求谓词公式的真值，量词的辖域，自由变元、约束变元，以及换名规则、代入规则等．掌握谓词演算的等值式和重言蕴含式．并进行谓词公式的等价演算．3．了解前束范式的概念，会求公式的前束范式的方法.若一个谓词公式F等价地转化成，那么就是F的前束范式，其中Q1，Q2，…，Qk只能是"或$，而x1,x2,…,xk是个体变元，B是不含量词的谓词公式．前束范式仍然是谓词公式．重点：谓词与量词，公

5、式与解释，谓词演算．第3章集合及其运算复习要点1．理解集合、元素、集合的包含、子集、相等，以及全集、空集和幂集等概念，熟练掌握集合的表示方法．具有确定的，可以区分的若干事物的全体称为集合，其中的事物叫元素.．集合的表示方法：列举法和描述法.注意：集合的表示中元素不能重复出现，集合中的元素无顺序之分．掌握集合包含(子集)、真子集、集合相等等概念．注意：元素与集合，集合与子集，子集与幂集，Î与Ì(Í),空集Æ与所有集合等的关系.空集Æ，是惟一的，它是任何集合的子集．集合A的幂集P(A)＝，A的所有子集构成的集合．若½A½＝n，则½P(A)½=2n．2．熟练掌握集合A和B的并AÈB，交

6、AÇB，补集~A(~A补集总相对于一个全集).差集A－B，对称差Å，AÅB＝(A－B)È(B－A)，或AÅB＝(AÈB)－（AÇB）等运算，并会用文氏图表示．掌握集合运算律.3．掌握用集合运算基本规律证明集合恒等式的方法．集合的运算问题：其一是进行集合运算；其二是运算式的化简；其三是恒等式证明．证明方法有二：(1)要证明A＝B，只需证明AÍB，又AÊB；(2)通过运算律进行等式推导．重点：集合概念，集合的运算，集合恒等式的证明．第4章关系与函数复习要点1．了解有序对和笛卡儿积的概念，掌握笛卡儿积的运算．有序对就是有顺序二元组，如，x,y的位置是确定的，不能随意放置．注意

7、：有序对¹，以a,b为元素的集合{a,b}={b,a}；有序对有意义，而集合{a,a}是单元素集合，应记作{a}．集合A，B的笛卡儿积A×B是一个集合，规定A×B＝{½xÎA,yÎB}，是有序对的集合.笛卡儿积也可以多个集合合成，A1×A2×…×An．2．理解关系的概念：二元关系、空关系、全关系、恒等关系.掌握关系的集合表示、关系矩阵和关系图，掌握关系的集合运算和求复合关系、逆关系的方法．二元关系是一个有序对集合，，记作xRy．空关系Æ是唯