离散数学复习提纲

《离散数学复习提纲》由会员分享，可在线阅读，更多相关《离散数学复习提纲（7页珍藏版）》请在金锄头文库上搜索。

1、12010-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 是

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

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

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

6、总个体域2. 谓词 谓词常项，谓词变项，1 元谓词（表示事物性质） ，n（n2）元谓词（表示事物之间的关系） ，0元谓词，特性谓词3. 量词及其分类 量词，全称量词，存在量词34. 命题符号化 设 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

7、 而言，若 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. 一阶语言的

8、解释 公式在解释 I 下的解释对于给定的解释 I，会在解释 I 下解释公式，判断公式是否是命题，是真命题、还是假命题。4. 公式的类型 永真式，永假式，可满足式第五章 一阶逻辑等值演算与推理5.1 一阶逻辑等值式与置换规则1. 等值式 设 A、B 为一阶逻辑公式，若 AB 为永真式，则称 A 与 B 等值。2. 基本的等值式第一组 命题逻辑中基本等值式的代换实例。第二组 一阶逻辑中的重要等值式（1）在有限个体域中消去量词等值式（2）量词否定等值式（3）量词辖域收缩与扩张等值式（4）量词分配等值式三个主要规则 置换规则、换名规则、代替规则熟练使用置换规则、换名规则、代替规则5.2 一阶逻辑前束范

9、式1. 前束范式 公式 A 的前束范式2. 求给定的前束范式 利用重要的等值式、置换规则、换名规则、代替规则等，对给定公式进行等值演算即可求出给定公式的前束范式。熟练地求出给定公式的前束范式。5.3 一阶逻辑的推理理论41. 推理的形式结构 形式结构 1若 A1A 2A kB（其中 A1，A 2，A k，B 均为一阶逻辑公式）为永真式，称推理正确，否则称推理不正确。形式结构 2前提：A 1，A 2，A k结论：B2. 一阶逻辑中重要的推理定律第一组 命题逻辑推理定律的代换实例第二组 一阶逻辑中每个基本等值式均生成两条推理定律第三组 一些常用的重要推理定律3. 自然推理系统 由字母表、合式公式、

10、推理规则构成。4. 在自然推理系统中构造证明前提：A 1，A 2，A k结论：B构造证明的方法：直接证明法：由前提 A1，A 2，A k 出发，应用推理规则，推出 B。附加前提证明法：当结论为 CB 形式时，可以将 C 列入前提中，然后用直接证明法推出 B，这里称C 为附加前提。归谬证明法：将结论 B 的否定式 B 列入前提中，然后用直接证明法推出矛盾式。牢记各条推理规则，能正确给出有效推理的证明。第二部分 集合论第六章 集合代数6.1 集合的基本概念1. 元素与集合 集合，元素，属于或者不属于 2. 特殊集合 自然数集 N，有理数集 Q，实数集 R，空集 ，全集 E，集合 A 的幂集 P（A

11、）=x|x A3. 集合的表示法 列元素法，谓词表示法，文氏图熟练掌握集合的前两种表示法4. 集合之间的关系 、=及它们的否定、能够判断两个集合之间是否存在包含、相等、真包含等关系。5. 重要结果 空集是任何集合的子集如果|A| = n，则| P（A）| = 2 n6.2 集合的运算1. 集合初级运算 并，交，相对补，绝对补，对称差 2. 集合广义运算 广义并，广义交3. 运算的优先权规定 称广义并，广义交，幂集，绝对补运算为一类运算；并，交，相对补，对称差运算为二类运算。一类运算优先于二类运算，一类运算之间有右向左顺序进行，5二类运算之间由括号决定先后顺序。熟练掌握集合的基本运算（幂集运算，

12、普通运算和广义运算）并能化简集合表达式。6.4 集合恒等式掌握证明集合等式或者包含关系的基本方法。第七章 二元关系7.1 有序对与笛卡尔积1. 有序对 2. 笛卡尔积 设 A，B 为集合，A 与 B 的笛卡尔积记作 AB，AB=|xAyB3. 笛卡尔积运算的性质 不适合交换律、结合律，但对于并和交运算满足分配律。4. 笛卡尔积中元素的个数 |A|=m，|B |= n，则|AB|=mn7.2 二元关系1. 二元关系2. 从 A 到 B 的二元关系与 A 上的关系3. A 上的某些特殊关系 空关系 、全域关系 EA、恒等关系 IA4. 关系的表示 集合表达式、关系矩阵、关系图熟练掌握关系矩阵、关系

13、图的表示法。7.3 关系的运算1. 关系运算的定义 定义域、值域、域、逆、右复合、限制、像、幂2. 关系运算的性质熟练掌握关系的定义域、值域、域、逆、右复合、限制、像、幂运算。7.4 关系的性质1. 关系的性质 自反、反自反、对称、反对称、传递2. 判别关系性质的三种方法 书 P117 表 7.1熟练掌握判断关系五种性质的方法，并能对关系的性质给出证明。3. 关系运算与关系性质之间的联系 书 P118 表 7.27.5 关系的闭包1. 关系的闭包 自反闭包 r(R)、对称闭包 s(R)、传递闭包 t(R)2. 构造闭包的三种方法集合表达式：r(R) = RR 0= RI A、 s(R) = R

14、R 1、t(R) = RR 2R 3关系矩阵：Mr = M + E Ms = M + M Mt = M + M2 + M3 + 关系图3. 闭包的性质熟练计算集合 A 上关系 R 的自反闭包 r(R)、对称闭包 s(R)、传递闭包 t(R)67.6 等价关系与划分1. 等价关系 A 上的自反、对称和传递的关系。2. 等价类设 R 为非空集合 A 上的等价关系，xA，令x R = y | yAxRy ，称 xR 为 x 关于 R 的等价类，简称为 x 的等价类，简记为x。3. 等价类的性质(1) xA ，x 是 A 的非空子集。 (2) x, yA，如果 x R y，则 x=y。(3) x, y

15、A，如果 x y，则 x与y不交。(4) x | xA=A，即所有等价类的并集就是 A。 4. 商集 设 R 为非空集合 A 上的等价关系，以 R 的所有等价类作为元素的集合称为 A 关于 R 的商集，记做 A/R， A/R = xR | xA 。5. 集合 A 的划分设 A 为非空集合，若 A 的子集族 ( P(A) 满足下面条件：(1) (2) xy (x,y x yxy=)(3) =A 则称 是 A 的一个划分，称 中的元素为 A 的划分块。6. 集合 A 上的等价关系与 A 的划分之间的一一对应熟练掌握等价关系、等价类、商集、划分的概念，以及等价关系与划分的对应性质。7.7 偏序关系1. 偏序关系 A 上的自反、反对称和传递的关系。2. 哈斯图3. 偏序集中的特殊元素 最大元、最小元、极大元、极小元、上界、下界、最小上界、最大下界熟练掌握偏序关系、哈斯图、特殊元素等概念。第五部分 图论第十四章 图的基本概念14.1 图1. 图的定义 无向图，有向图，n 阶图，零图，平凡图，标定图，非标定图，基图。2. 顶点与边的关系 顶点与边的关联关系，关联次数，环，孤立点；顶点与顶点的相邻关系，边与边的相邻关系；无向图的邻域与关联集；有向图的后继元集、先驱元集与邻域。73