资源描述：
《离散数学复习提纲》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、第一章TRUTHTABLES,LOGIC,ANDPROOFS 命题的概念、命题的真值：T，F 命题联结词：否定联结词～，合取联结词，析取联结词，蕴含联结词→，等值(双条件)联结词 真值表 命题符号化 合式公式(命题公式)、子公式和指派 公式分类与永真式，永假式，可满足式 等价命题 基本逻辑恒等式和永真蕴含式 证明方法 对偶原理 基本和、合取范式、极大项、主合取范式、求主合取范式的方法 基本积、析取范式、极小项、主析取范式、求主析取范式的方法 命题逻辑的推理理论：真值表法、直接证明方法（P规则、T规则、CP规则）、间接证明方法（反证法）主要知识点、重点和难点：（1）数理逻
2、辑是用数学方法研究思维规律和推理过程的科学，推理的基本要素是命题。命题符号化一般的处理过程是先分析自然语言描述的语义，然后用正确的命题联结词加以表示。应特别注意用于表示“合取”含义的一些联结词：如“不但（仅）…而且…”、“既…又…以”；用于表示条件联结词的“若…则…”，“PQ”表示Q是P的必要条件，P是Q的充分条件。在自然语言表达中，要根据前提和结论的语义来判断条件语句的前件和后件，否则会出现将必要条件当成充分条件，以至于将真命题变成假命题，或将假命题变成真命题。在构造命题公式时，应概念清楚，按命题公式的定义准确书写公式；8（2）判断哪些语句是命题？判断给定的公式是否是
3、永真式？关于是否是命题的判定主要根据命题的概念：即能惟一判断其真假的陈述句。简单命题是不能再进一步分解的命题，不含联结词；而复合命题是可以进一步分解的命题，其中至少包含一个联结词。（3）判断一个公式是否是一个永真式，可以利用真值表法、等价取代和写出其相应的主范式等方法；（4）析（合）取范式的求解方法，一般可采用公式推导（等价取代）的形式，先将公式中的条件和双条件联结词转化掉，化为只含，，～的式子，然后利用德摩根律将“～”放到每个变元的前面，利用结合律、分配律将公式化成析（合）取范式的形式；而主析（合）取范式的求解则可用：真值表法、公式推导法；或者可从主析（合）取范式直接
4、转换成主合（析）取范式；（5）证明结论有效性（蕴涵式）的方法：真值表法、利用蕴涵式的定义（前件真推出后件也真法、后件假推出前件也假法）、直接证明法、间接证明法（反证法）。第二章 SETTHEORY 集合和元素，集合和元素之间的关系（属于和不属于），集合和元素的表示 子集的概念、集合之间的包含、真包含关系 集合的基数，有限集和无限集，空集，全集 集合的运算：交、并、补、差、对称差、幂集 基本集合恒等式 布尔代数及其基本性质 有序对、集合的笛卡尔积 关系定义与表示：集合表示法、关系图表示法 关系的性质：自反性、反自反性、对称性、反对称性和传递性 关系的运算：并、交、差、对称
5、差、逆关系和合成运算8 等价关系、等价类与划分 序关系：偏序关系、全序关系和良序关系 偏序关系的覆盖，哈斯图主要知识点、重点和难点：（1）根据集合、元素、集合间的关系的概念及性质，集合运算的定义，确定元素与集合间的关系，集合与集合间的关系、集合的幂集等。元素和集合的关系只有属于和不属于两种。而集合间的关系可以是相等、不相等、包含、真包含等。（2）求给定集合的幂集时，只需求出给定集合的所有子集。集合间的交、并、补、差、对称差运算，可根据定义进行。（3）集合恒等式的证明：一是利用集合相等的定义AB，BA；二是已知的集合恒等式，即等价取代的方法，对A利用有关的集合恒等式，得到
6、B；或证明A＝C且B＝C，从而A＝B。（4）A和B的笛卡尔积就是由所有第一个元素属于集合A，第二个元素属于集合B的序偶构成的集合。（5）二元关系是笛卡尔积的任意一个子集。二元关系有三种表示方法：集合表示法、关系矩阵表示法和关系图表示方法。（6）二元关系性质（自反性、反自反性、对称性、反对称性、传递性）的判断，取决于关系的表示方式。关系的这五个性质是非常重要且常用的内容，也是解决证明题的关键。对于各种不同性质的证明，一般地，总是这样开始证明的：自反性：xX,……,（x,x）R，即R是自反的；反自反性：xX,……,（x,x）R，即R是反自反的；对称性：x,yX,若（x,y）
7、R……,（y,x）R，即R是对称的；反对称性：x,yX,若（x,y）R且（y,x）R……,y＝x，即R是反对称的；传递性：x,y,zX,若（x,y）R且（y,z）R……,（x,z）R，即R是传递的；8（7）等价关系和划分、偏序关系、全序关系和良序关系所具有的性质，无非就是上述某些性质的组合；（8）偏序关系与哈斯图的对应。第三章LOGIC,INTEGERS,ANDPROOFS LP的基本概念：个体、个体域、谓词和命题的谓词形式 量词：全称量词、存在量词、量词的辖域 自由变元、约束变元 合式公式 全称量词指定规则，全称量词推广规则，存在量词指
