离散数学复习提纲.doc
7页
2010-2011-1《离散数学》复习提纲第一部分 数理逻辑第一章 命题逻辑基本概念§1.1 命题与联结词1. 命题与真值 命题，命题的真值，真命题，假命题，简单命题（原子命题），复合命题2. 命题与真值的符号化 用p，q，r等小写英文字母表示命题，用数字1代表真，0代表假3. 常用联结词及其符号化 否定，合取，析取，蕴涵，等价4. 基本复合命题 设p，q为命题否定式┐p合取式p∧q析取式p∨q蕴涵式p→q 分清逻辑关系、真值以及在自然语言中对“p→q”的不同的描述方法等价式p↔q5. 复合命题 基本复合命题以及多次使用常用联结词复合而成的命题统称为复合命题深刻理解5种常用联结词的涵义，并能准确地应用它们将复合命题符号化§1.2 命题公式及其赋值1. 命题常项与命题变项 命题常项（简单命题），命题变项（取值为1或0的变量p，q，r……）2. 命题公式与赋值 合式公式（也称命题公式或公式），公式的层次，公式的赋值，成真赋值，成假赋值，真值表3. 命题公式的类型 重言式（永真式），矛盾式（永假式），可满足式4. 判断公式类型的方法 在本章内主要用真值表判断命题公式的类型，进而求公式的成真赋值和成假赋值。
理解命题的赋值、成真赋值，成假赋值，重言式、矛盾式、可满足式第二章 命题逻辑等值演算§2.1 等值式1. 等值式 若A↔B为重言式，则称A与B是等值的记为A B2. 基本等值式3. 等值演算 由已知等值式推演除新的等值式的过程4. 重言式与矛盾式的判别法 A为重言式当且仅当A1，A为矛盾式当且仅当A0§2.2 析取范式与合取范式1. 基本概念 文字，简单析取式，简单合取式，极小项，极大项，析取范式，合取范式，主析取范式，主合取范式深刻理解极小项、极大项的定义、名称、下脚标与成真赋值的关系2. 主要定理 在命题逻辑中，任何公式都存在与之等值的主析取范式和主合取范式，并且是唯一的3. 求公式A的主析取范式的方法和步骤等值演算法（1）消去A联结词→，↔（若存在）（2）否定联结词的内移（3）使用分配律以上三步将A等值地化成析取范式（4）将析取范式中不是极小项的简单合取式利用排中律、同一律、分配律化成若干个极小项（5）将极小项用名称mi表示，使用幂等律，最后排序4. 求公式A的主合取范式的方法和步骤等值演算法同上熟练掌握求主析取范式与主合取范式的方法第三章 命题逻辑的推理理论§3.1 推理的形式结构1. 推理 推理的形式结构的符号化形式： 若A1∧A2∧……∧Ak→B为重言式，称推理是有效的。
或： 前提：A1，A2，……，Ak 结论：B2. 判断推理是否正确的方法用第二章的只是判断推理是否正确的方法有以下三种：真值表法、等值演算法、主析取范式法3. 推理规则9条牢记各条推理规则的内容及名称§3.2 自然推理系统1. 自然推理系统 由字母表、合式公式、推理规则构成2. 在自然推理系统中构造证明前提：A1，A2，……，Ak结论：B构造证明的方法：直接证明法：由前提A1，A2，……，Ak出发，应用推理规则，推出B附加前提证明法：当结论为C→B形式时，可以将C列入前提中，然后用直接证明法推出B，这里称C为附加前提归谬证明法：将结论B的否定式┐B列入前提中，然后用直接证明法推出矛盾式熟练掌握在系统中构造证明的直接证明法、附加前提证明法、归谬证明法第四章 一阶逻辑基本概念§4.1 一阶逻辑命题符号化1. 个体词 个体，个体常项，个体变项，个体域，有限个体域，无限个体域，全总个体域2. 谓词 谓词常项，谓词变项，1元谓词（表示事物性质），n（n≥2）元谓词（表示事物之间的关系），0元谓词，特性谓词3. 量词及其分类 量词，全称量词，存在量词4. 命题符号化 设D为个体域（1）“D中所有x都有性质F”符号化为 xF（x）（2）“D中有的x有性质F”符号化为 xF（x）（3）“对D中所有x而言，如果x有性质F，x就有性质G”符号化为 x（F（x）→G（x））（基本公式1）（4）“对D中有的x既有性质F，又有性质G”符号化为 x（F（x）∧G（x））（基本公式2）（5）“对于D中所有x而言，若x有性质F，就存在y有性质G，则x与y就有关系H”符号化为 x（F（x）→y（G（y）∧H（x，y）））（6）“存在D中x有性质F，并且对D中所有的y而言，如果y有性质G，则x与y就有关系H”符号化为 x（F（x）∧y（G（y）→H（x，y）））准确地将给定命题符号化，分清各种符号化形式，特别要注意两个基本公式。
§4.2 一阶逻辑公式及其解释1. 一阶语言￡ 由非逻辑符集合L生成的一阶语言￡的字母表，项，原子公式，合式公式2. 量词的辖域 量词的辖域，指导变元，个体变项的自由出现与约束出现，闭式3. 一阶语言的解释 公式在解释I下的解释对于给定的解释I，会在解释I下解释公式，判断公式是否是命题，是真命题、还是假命题4. 公式的类型 永真式，永假式，可满足式第五章 一阶逻辑等值演算与推理§5.1 一阶逻辑等值式与置换规则1. 等值式 设A、B为一阶逻辑公式，若A↔B为永真式，则称A与B等值2. 基本的等值式第一组 命题逻辑中基本等值式的代换实例第二组 一阶逻辑中的重要等值式（1）在有限个体域中消去量词等值式（2）量词否定等值式（3）量词辖域收缩与扩张等值式（4）量词分配等值式三个主要规则 置换规则、换名规则、代替规则熟练使用置换规则、换名规则、代替规则§5.2 一阶逻辑前束范式1. 前束范式 公式A的前束范式2. 求给定的前束范式 利用重要的等值式、置换规则、换名规则、代替规则等，对给定公式进行等值演算即可求出给定公式的前束范式熟练地求出给定公式的前束范式§5.3 一阶逻辑的推理理论1. 推理的形式结构 形式结构1若A1∧A2∧……∧Ak→B（其中A1，A2，……，Ak，B均为一阶逻辑公式）为永真式，称推理正确，否则称推理不正确。
形式结构2前提：A1，A2，……，Ak结论：B2. 一阶逻辑中重要的推理定律第一组 命题逻辑推理定律的代换实例第二组 一阶逻辑中每个基本等值式均生成两条推理定律第三组 一些常用的重要推理定律3. 自然推理系统 由字母表、合式公式、推理规则构成4. 在自然推理系统中构造证明前提：A1，A2，……，Ak结论：B构造证明的方法：直接证明法：由前提A1，A2，……，Ak出发，应用推理规则，推出B附加前提证明法：当结论为C→B形式时，可以将C列入前提中，然后用直接证明法推出B，这里称C为附加前提归谬证明法：将结论B的否定式┐B列入前提中，然后用直接证明法推出矛盾式 牢记各条推理规则，能正确给出有效推理的证明第二部分 集合论第六章 集合代数§6.1 集合的基本概念1. 元素与集合 集合，元素，属于∈或者不属于2. 特殊集合 自然数集N，有理数集Q，实数集R，空集，全集E，集合A的幂集P（A）={x|xA}3. 集合的表示法 列元素法，谓词表示法，文氏图 熟练掌握集合的前两种表示法4. 集合之间的关系 、=及它们的否定能够判断两个集合之间是否存在包含、相等、真包含等关系5. 重要结果 空集是任何集合的子集 如果|A| = n，则| P（A）| = 2n§6.2 集合的运算1. 集合初级运算 并∪，交∩，相对补﹣，绝对补~，对称差2. 集合广义运算 广义并，广义交3. 运算的优先权规定 称广义并，广义交，幂集，绝对补运算为一类运算；并，交，相对补，对称差运算为二类运算。
一类运算优先于二类运算，一类运算之间有右向左顺序进行，二类运算之间由括号决定先后顺序熟练掌握集合的基本运算（幂集运算，普通运算和广义运算）并能化简集合表达式§6.4 集合恒等式掌握证明集合等式或者包含关系的基本方法第七章 二元关系§7.1 有序对与笛卡尔积1. 有序对
3. 关系运算与关系性质之间的联系 书P118 表7.2§7.5 关系的闭包1. 关系的闭包 自反闭包r(R)、对称闭包s(R)、传递闭包t(R)2. 构造闭包的三种方法集合表达式：r(R) = R∪R0= R∪IA、 s(R) = R∪R-1、t(R) = R∪R2∪R3∪…关系矩阵：Mr = M + E Ms = M + M’ Mt = M + M2 + M3 + …关系图3. 闭包的性质 熟练计算集合A上关系R的自反闭包r(R)、对称闭包s(R)、传递闭包t(R)§7.6 等价关系与划分1. 等价关系 A上的自反、对称和传递的关系2. 等价类设R为非空集合A上的等价关系，"x∈A，令[x]R = { y | y∈A∧xRy }，称 [x]R 为 x 关于R 的等价类，简称为 x 的等价类，简记为[x]3. 等价类的性质(1) "x∈A，[x] 是A的非空子集 (2) "x, y∈A，如果 x R y，则 [x]=[y] (3) "x, y∈A，如果 x y，则 [x]与[y]不交 (4) ∪{ [x] | x∈A}=A，即所有等价类的并集就是A 4. 商集 设R为非空集合A上的等价关系，以R的所有等价类作为元素的集合称为A关于R的商集，记做A/R，A/R = { [x]R | x∈A }。
5. 集合A的划分设A为非空集合，若A的子集族π(πÍP(A)) 满足下面条件： (1) ÏÆπ (2) "x"y (x,y∈π∧x≠y→x∩y=Æ) (3) ∪π=A 则称π是A的一个划分，称π中的元素为A的划分块6. 集合A上的等价关系与A的划分之间的一一对应 熟练掌握等价关系、等价类、商集、划分的概念，以及等价关系与划分的对应性质§7.7 偏序关系1. 偏序关系 A上的自反、反对称和传递的关系2. 哈斯图3. 偏序集中的特殊元素 最大元、最小元、极大元、极小元、上界、下界、最小上界、最。
