离散数学复习提纲

1、2010-2011-1离散数学复习提纲第一部分 数理逻辑第一章 命题逻辑基本概念§1.1 命题与联结词1. 命题与真值 命题，命题的真值，真命题，假命题，简单命题（原子命题），复合命题2. 命题与真值的符号化 用p，q，r等小写英文字母表示命题，用数字1代表真，0代表假。3. 常用联结词及其符号化 否定，合取，析取，蕴涵，等价4. 基本复合命题 设p，q为命题否定式p合取式pq析取式pq蕴涵式pq 分清逻辑关系、真值以及在自然语言中对“pq”的不同的描述方法。等价式pq5. 复合命题 基本复合命题以及多次使用常用联结词复合而成的命题统称为复合命题。深刻理解5种常用联结词的涵义，并能准

2、确地应用它们将复合命题符号化。§1.2 命题公式及其赋值1. 命题常项与命题变项 命题常项（简单命题），命题变项（取值为1或0的变量p，q，r）2. 命题公式与赋值 合式公式（也称命题公式或公式），公式的层次，公式的赋值，成真赋值，成假赋值，真值表3. 命题公式的类型 重言式（永真式），矛盾式（永假式），可满足式4. 判断公式类型的方法 在本章内主要用真值表判断命题公式的类型，进而求公式的成真赋值和成假赋值。理解命题的赋值、成真赋值，成假赋值，重言式、矛盾式、可满足式第二章 命题逻辑等值演算§2.1 等值式1. 等值式 若AB为重言式，则称A与B是等值的。记为A B2. 基

3、本等值式3. 等值演算 由已知等值式推演除新的等值式的过程。4. 重言式与矛盾式的判别法 A为重言式当且仅当A1，A为矛盾式当且仅当A0。§2.2 析取范式与合取范式1. 基本概念 文字，简单析取式，简单合取式，极小项，极大项，析取范式，合取范式，主析取范式，主合取范式深刻理解极小项、极大项的定义、名称、下脚标与成真赋值的关系。2. 主要定理 在命题逻辑中，任何公式都存在与之等值的主析取范式和主合取范式，并且是唯一的。3. 求公式A的主析取范式的方法和步骤等值演算法（1）消去A联结词，（若存在）（2）否定联结词的内移（3）使用分配律以上三步将A等值地化成析取范式（4）将析取范式中不是

4、极小项的简单合取式利用排中律、同一律、分配律化成若干个极小项（5）将极小项用名称mi表示，使用幂等律，最后排序4. 求公式A的主合取范式的方法和步骤等值演算法同上熟练掌握求主析取范式与主合取范式的方法。第三章 命题逻辑的推理理论§3.1 推理的形式结构1. 推理 推理的形式结构的符号化形式： 若A1A2AkB为重言式，称推理是有效的。或： 前提：A1，A2，Ak 结论：B2. 判断推理是否正确的方法用第二章的只是判断推理是否正确的方法有以下三种：真值表法、等值演算法、主析取范式法3. 推理规则9条牢记各条推理规则的内容及名称。§3.2 自然推理系统1. 自然推理系统 由字母

5、表、合式公式、推理规则构成。2. 在自然推理系统中构造证明前提：A1，A2，Ak结论：B构造证明的方法：直接证明法：由前提A1，A2，Ak出发，应用推理规则，推出B。附加前提证明法：当结论为CB形式时，可以将C列入前提中，然后用直接证明法推出B，这里称C为附加前提。归谬证明法：将结论B的否定式B列入前提中，然后用直接证明法推出矛盾式。熟练掌握在系统中构造证明的直接证明法、附加前提证明法、归谬证明法。第四章 一阶逻辑基本概念§4.1 一阶逻辑命题符号化1. 个体词 个体，个体常项，个体变项，个体域，有限个体域，无限个体域，全总个体域2. 谓词 谓词常项，谓词变项，1元谓词（表示事物性质

6、），n（n2）元谓词（表示事物之间的关系），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而言，

7、如果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

8、、B为一阶逻辑公式，若AB为永真式，则称A与B等值。2. 基本的等值式第一组 命题逻辑中基本等值式的代换实例。第二组 一阶逻辑中的重要等值式（1）在有限个体域中消去量词等值式（2）量词否定等值式（3）量词辖域收缩与扩张等值式（4）量词分配等值式三个主要规则 置换规则、换名规则、代替规则熟练使用置换规则、换名规则、代替规则§5.2 一阶逻辑前束范式1. 前束范式 公式A的前束范式2. 求给定的前束范式 利用重要的等值式、置换规则、换名规则、代替规则等，对给定公式进行等值演算即可求出给定公式的前束范式。熟练地求出给定公式的前束范式。§5.3 一阶逻辑的推理理论1. 推理的形式结

9、构 形式结构1若A1A2AkB（其中A1，A2，Ak，B均为一阶逻辑公式）为永真式，称推理正确，否则称推理不正确。形式结构2前提：A1，A2，Ak结论：B2. 一阶逻辑中重要的推理定律第一组 命题逻辑推理定律的代换实例第二组 一阶逻辑中每个基本等值式均生成两条推理定律第三组 一些常用的重要推理定律3. 自然推理系统 由字母表、合式公式、推理规则构成。4. 在自然推理系统中构造证明前提：A1，A2，Ak结论：B构造证明的方法：直接证明法：由前提A1，A2，Ak出发，应用推理规则，推出B。附加前提证明法：当结论为CB形式时，可以将C列入前提中，然后用直接证明法推出B，这里称C为附加前提。归谬证明法

10、：将结论B的否定式B列入前提中，然后用直接证明法推出矛盾式。 牢记各条推理规则，能正确给出有效推理的证明。第二部分 集合论第六章 集合代数§6.1 集合的基本概念1. 元素与集合 集合，元素，属于或者不属于2. 特殊集合 自然数集N，有理数集Q，实数集R，空集，全集E，集合A的幂集P（A）=x|xA3. 集合的表示法 列元素法，谓词表示法，文氏图 熟练掌握集合的前两种表示法4. 集合之间的关系 、=及它们的否定能够判断两个集合之间是否存在包含、相等、真包含等关系。5. 重要结果 空集是任何集合的子集 如果|A| = n，则| P（A）| = 2n§6.2 集合的运算1. 集

11、合初级运算 并，交，相对补，绝对补，对称差2. 集合广义运算 广义并，广义交3. 运算的优先权规定 称广义并，广义交，幂集，绝对补运算为一类运算；并，交，相对补，对称差运算为二类运算。一类运算优先于二类运算，一类运算之间有右向左顺序进行，二类运算之间由括号决定先后顺序。熟练掌握集合的基本运算（幂集运算，普通运算和广义运算）并能化简集合表达式。§6.4 集合恒等式掌握证明集合等式或者包含关系的基本方法。第七章 二元关系§7.1 有序对与笛卡尔积1. 有序对 <x,y>2. 笛卡尔积 设A，B为集合，A与B的笛卡尔积记作A×B，A×B=<x

12、，y>|xAyB3. 笛卡尔积运算的性质 不适合交换律、结合律，但对于并和交运算满足分配律。4. 笛卡尔积中元素的个数 |A|=m，|B |= n，则|A×B|=mn§7.2 二元关系1. 二元关系2. 从A到B的二元关系与A上的关系3. A上的某些特殊关系 空关系、全域关系EA、恒等关系IA4. 关系的表示 集合表达式、关系矩阵、关系图熟练掌握关系矩阵、关系图的表示法。§7.3 关系的运算1. 关系运算的定义 定义域、值域、域、逆、右复合、限制、像、幂2. 关系运算的性质 熟练掌握关系的定义域、值域、域、逆、右复合、限制、像、幂运算。§7.4 关

13、系的性质1. 关系的性质 自反、反自反、对称、反对称、传递2. 判别关系性质的三种方法 书P117 表7.1 熟练掌握判断关系五种性质的方法，并能对关系的性质给出证明。3. 关系运算与关系性质之间的联系 书P118 表7.2§7.5 关系的闭包1. 关系的闭包 自反闭包r(R)、对称闭包s(R)、传递闭包t(R)2. 构造闭包的三种方法集合表达式：r(R) = RR0= RIA、 s(R) = RR-1、t(R) = RR2R3关系矩阵：Mr = M + E Ms = M + M Mt = M + M2 + M3 + 关系图3. 闭包的性质 熟练计算集合A上关系R的自反闭包r(R)、

14、对称闭包s(R)、传递闭包t(R)§7.6 等价关系与划分1. 等价关系 A上的自反、对称和传递的关系。2. 等价类设R为非空集合A上的等价关系，"xA，令xR = y | yAxRy ，称 xR 为 x 关于R 的等价类，简称为 x 的等价类，简记为x。3. 等价类的性质(1) "xA，x 是A的非空子集。 (2) "x, yA，如果 x R y，则 x=y。 (3) "x, yA，如果 x y，则 x与y不交。 (4) x | xA=A，即所有等价类的并集就是A。 4. 商集 设R为非空集合A上的等价关系，以R的所有等价类作为元素的集合称为

15、A关于R的商集，记做A/R，A/R = xR | xA 。5. 集合A的划分设A为非空集合，若A的子集族(ÍP(A) 满足下面条件： (1) ÏÆ (2) "x"y (x,yxyxy=Æ) (3) =A 则称是A的一个划分，称中的元素为A的划分块。6. 集合A上的等价关系与A的划分之间的一一对应 熟练掌握等价关系、等价类、商集、划分的概念，以及等价关系与划分的对应性质。§7.7 偏序关系1. 偏序关系 A上的自反、反对称和传递的关系。2. 哈斯图3. 偏序集中的特殊元素 最大元、最小元、极大元、极小元、上界、下界、最小上界、

16、最大下界 熟练掌握偏序关系、哈斯图、特殊元素等概念。第五部分 图论第十四章 图的基本概念§14.1 图1. 图的定义 无向图，有向图，n阶图，零图，平凡图，标定图，非标定图，基图。2. 顶点与边的关系 顶点与边的关联关系，关联次数，环，孤立点；顶点与顶点的相邻关系，边与边的相邻关系；无向图的邻域与关联集；有向图的后继元集、先驱元集与邻域。3. 简单图与多重图 平行边，多重图，简单图 理解与图的定义有关的诸多概念。4. 顶点的度数与握手定理及推论 深刻理解握手定理及推论的内容，并能熟练地应用它们。5. 图的同构 定义，图的同构关系是等价关系。6. 完全图与竞赛图 n阶有向完全图Kn，n

17、阶无向完全图，n阶竞赛图，以及简单性质。7. 正则图 n阶k正则图的定义及简单性质。8. 子图 子图的定义，真子图，生成子图，导出子图。9. 补图 补图的定义，自补图。理解上述概念及它们的性质和相互关系。10. 图的运算 删除运算、收缩边、加新边§14.2 图1. 通路与回路的定义 定义，通路与回路的长度2. 通路与回路的分类 简单通路与简单回路，初级通路（路径）与初级回路（圈），复杂通路与复杂回路3. 通路与回路的性质 定理14.5、定理14.6§14.3 图的连通性1. 无向图的连通性 顶点之间的连通关系，无向连通图，非连通图，连通分支，顶点之间的短程线与距离。2. 无向图的连通度 点割集与割点，边割集与割边（桥），G的点连通度(G)，k-连通图，G的边连通度(G)，r边-连通图，(G)与(G)的关系。