计算机数学基础离散数学部分.DOC

离散数学复习提纲 一、基本内容 数理逻辑部分 1．理解命题概念，会判别语句是不是命题．理解五个联结词：否定、析取、合取、条件、和双条件及其真值表，会将简单命题符号化． 具有确定真假意义的陈述句称为命题． 命题必须具备：其一，语句是陈述句；其二，语句有唯一确定的真假意义. 2．了解公式的概念(公式、赋值、成真指派和成假指派)和公式真值表的构造方法．能熟练地作公式真值表．理解永真式和永假式概念，掌握其判别方法． 判定命题公式类型的方法：其一是真值表法，其二是等价演算法. 3．了解公式等价概念，掌握公式的重要等价式和判断两个公式是否等价的有效方法：等价演算法、列真值表法和主范式方法． 4．理解析取范式和合取范式、极大项和极小项、主析取范式和主合取范式的概念，熟练掌握它们的求法． 命题公式的范式不惟一，但主范式是惟一的． 命题公式A有n个命题变元，A的主析取范式有k个极小项，有m个极大项，则 求命题公式A的析取(合取)范式的步骤． 求命题公式A的主析取(合取)范式的步骤． 5．要理解并掌握推理理论的规则、重言蕴含式和等价式，掌握命题公式的证明方法：真值表法、直接证法、间接证法． 重点：命题与联结词，公式与解释，真值表，公式的类型及判定，主析取(合取)范式，命题演算的推理理论. 6．理解谓词、量词、个体词、个体域，会将简单命题符号化． 原子命题分成个体词和谓词，个体词可以是具体事物或抽象的概念，分个体常项和个体变项．谓词用来刻划个体词的性质或之间的关系． 量词分全称量词，存在量词. 命题符号化注意：使用全称量词，特性谓词后用；使用存在量词，特性谓词后用． 7．了解原子公式、谓词公式、变元(约束变元和自由变元)与辖域等概念．掌握在有限个体域下消去公式的量词和求公式在给定解释下真值的方法． 由原子公式、联结词和量词构成谓词公式．谓词公式具有真值时，才是命题． 在谓词公式中，会区分约束变元和自由变元． 在非空集合D(个体域)上谓词公式A的一个解释或赋值有3个条件． 在任何解释下，谓词公式A取真值1，A为逻辑有效式(永真式)；公式A取真值0，A为永假式；至少有一个解释使公式A取真值1，A称为可满足式． 在有限个体域下，消除量词的规则为：设D＝{}，则 会求谓词公式的真值，量词的辖域，自由变元、约束变元，以及换名规则、代入规则等． 掌握谓词演算的等价式和重言蕴含式．并进行谓词公式的等价演算． 8．了解前束范式的概念，会求公式的前束范式的方法. 若一个谓词公式F等价地转化成 ，那么就是F的前束范式．前束范式仍然是谓词公式． 9．了解谓词逻辑推理的四个规则．会给出推理证明． 谓词演算的推理是命题演算推理的推广和扩充，命题演算中基本等价式，重言蕴含式以及P，T，CP规则在谓词演算中仍然使用．谓词逻辑的推理演算引入了US规则(全称量词指定规则)，UG规则(全称量词推广规则)，ES规则(存在量词指定规则)，EG规则(存在量词推广规则)等. 集合论部分 1．理解集合、元素、集合的包含、子集、相等，以及全集、空集和幂集等概念，熟练掌握集合的表示方法． 具有确定的，可以区分的若干事物的全体称为集合，其中的事物叫元素． 集合的表示方法：列举法和描述法. 注意：集合的表示中元素不能重复出现，集合中的元素无顺序之分． 掌握集合包含(子集)、真子集、集合相等等概念． 注意：元素与集合，集合与子集，子集与幂集，空集与所有集合的关系：空集是惟一的，它是任何集合的子集． 集合A的幂集P(A)＝， A的所有子集构成的集合．若|A|＝n，则|P(A)|=2n． 2．熟练掌握集合A和B的并、交，补集(A补集总相对于一个全集).差集A－B，对称差等运算，并会用文氏图表示． 掌握集合运算律(运算的性质). 3．掌握用集合运算基本规律证明集合恒等式的方法． 集合的运算问题：其一是进行集合运算；其二是运算式的化简；其三是恒等式证明． 证明方法有二：(1)要证明A＝B，只需证明A是B的子集，又B是A的子集； (2)通过运算律进行等式推导． 4．了解有序对和笛卡儿积的概念，掌握笛卡儿积的运算． 有序对就是有顺序二元组，如x, y，x, y 的位置是确定的，不能随意放置． 注意：有序对a，b(b, a，以a, b为元素的集合{a, b}={b, a}；有序对(a, a)有意义，而集合{a, a}是单元素集合，应记作{a}． 集合A，B的笛卡儿积A×B是一个集合，规定A×B＝{x,y(x(A,y(B}，是有序对的集合.笛卡儿积也可以多个集合合成，A1×A2×…×An． 5．理解关系的概念：二元关系、空关系、全关系、恒等关系