离散第三、四章复习内容

离散数学内容总结大纲第一篇 数理逻辑第1章 命题逻辑求命题公式的主析取范式及主合取范式例 求()()p r q p ∨⌝∧∨的主析取范式及主合取范式。

例 求(P →Q)∧R 的主析取范式及主合取范式。

例 求命题公式R Q P ∨∧)(的主析取范式和主合取范式。

例 求公式A =(p →⌝q )→r 的主析取范式与主合取范式。

例 求()r q p →→的主析取范式。

判断公式类型例 用等值演算法判断公式q ∧⌝ (p →q )的类型例 判断下列命题公式的类型（永真式、永假式、可满足式），方法不限。

(1)(2)证明例 证明：()()()r q r p r q p →∧→⇔→∨ 例 证明：r q p r q p →∧⇔→→)()( 例 推证：⌝Q ∧(P →Q)⇒⌝P例 前提：q p s q r p ∨→→,,，结论：s r ∨。

该结论是否有效？请说明原因。

在命题逻辑中构造下面推理的证明：例 如果小张守第一垒并且小李向B 队投球，则A 队获胜。

或者A 队未获胜，或者A 队成为联赛的第一名。

小张守第一垒。

A 队没有成为联赛的第一名。

因此小李没有向B 队投球。

解：先将简单命题符号化。

P：小张守第一垒；Q：小李向B队投球；R：A队取胜；S：A 队成为联赛第一名。

前提：(P∧Q)→R，R∨S，P，S结论：Q证明：(1) R∨S 前提引入(2) S 前提引入(3) R (1)(2)析取三段论(4) (P∧Q)→R 前提引入(5) (P∧Q) (3)(4)拒取式(6) P∨Q (5)置换(7) P 前提引入(8) Q (6)(7)析取三段论例一个公安人员审查一件盗窃案，已知下列事实：（1）甲或乙盗窃了录像机；（2）若甲盗窃了录像机，则作案时间不能发生在午夜前；（3）若乙的证词正确，则午夜时屋里灯光未灭；（4）若乙的证词不正确，则作案时间发生在午夜前；（5）午夜时屋里灯光灭了。

根据以上事实，推断谁是盗窃犯。

（在命题逻辑中构造推理证明。

第1章集合及其运算考核知识点1．集合，元素，集合的表示，全集，空集2．集合的包含、相等，子集，幂集3．集合的并、交、补、差、对称差等运算及其运算律4．容斥原理考核要求1．理解集合的概念，容斥原理．2．理解集合的包含、子集、相等和幂集等概念，熟练掌握集合的表示方法和集合的并、交、补、差和对称差等运算，会用文氏图表示集合的各种运算．3．掌握用集合运算基本规律证明集合恒等式的方法．4．掌握利用容斥原理进行计数的方法．第2章关系与函数考核知识点1．有序对和笛卡儿积2．关系及其运算性质3．二元关系的矩阵与图4．复合关系与逆关系5．二元关系的性质6．等价关系与等价类7．偏序关系、复盖集与哈斯图，极大(小)元，最大(小)元，上(下)界，最小上界，最大下界8．函数反函数复合函数单射满射和双射考核要求1．了解有序对和笛卡儿积的概念，掌握笛卡儿积的运算．2．理解关系的概念：包括二元关系、空关系、全关系、恒等关系．掌握关系的集合表示、关系矩阵和关系图，掌握关系的运算．3．掌握求复合关系和逆关系的方法．4．理解关系的性质(自反性和反自反性、对称性和反对称性、传递性)，掌握其判别方法．5．理解等价关系和偏序关系概念，掌握等价关系、偏序关系的判定，掌握等价类、复盖集的求法和作偏序关系哈斯图的方法．知道极大(小)元，最大(小)元的概念，会求极大(小)元、最大(小)元、最小上界和最大下界．6．理解函数概念：函数(映射)，函数相等，复合函数和反函数．7．理解单射、满射和双射等概念，掌握其判别方法．第3章图的基本概念与性质考核知识点1．图的概念与表示，有向图，无向图，简单图，完全图，结点的度数，图的同构，子图、补图2．通路，通路的长度，初级通路，简单通路，回路，初级回路，简单回路3．图的连通性与连通度概念、判定，点割集与割点，边割集与割边4．图的矩阵表示、邻接矩阵、可达性矩阵及其计算5．最短路径考核要求1．理解图的基本概念：结点、边、有向图，无向图、简单图、完全图、结点的度数、图的同构子图等，理解握手定理．2．了解通路与回路的概念：简单通路、初级通路和复杂通路，简单回路、初级回路和复杂回路，会求通路和回路的长度．3．了解无向图的连通性，会求无向图的连通分支．了解点割集、割点、边割集、割边、点连通度、边连通度等概念．4．了解有向图的强连通性、单向连通性、弱连通性；会判别有向图连通性的类型．5．理解图的矩阵表示法、邻接矩阵、可达性矩阵的概念，掌握邻接矩阵、可达性矩阵的有关计算．6．知道最短路径的概念，会最短路径的算法．第4章几种特殊图考核知识点1．欧拉通路(回路)，欧拉图2．哈密顿通路(回路)，哈密顿图3．平面图，欧拉公式4．对偶图及着色考核要求1．了解欧拉回路、欧拉图的概念及性质，掌握欧拉图的判别方法．2．了解汉密尔顿回路、汉密尔顿图的概念及性质，掌握汉密尔顿图的判别方法．3．了解平面图的概念：平面图、面、边界、面的次数和非平面图，掌握平面图的判别方法，掌握欧拉公式的应用．4．理解平面图与对偶图的关系、对偶图在图着色中的作用，掌握着色算法；5．掌握图论中常用的证明方法．第5章树及其应用考核知识点1．树的定义及性质2．生成树与最小生成树的概念，最小生成树的Kruskal算法3．根树的概念及性质4．最优树的概念，最优树的Huffman算法，前缀码的求法考核要求1．了解无向树、树叶、分支点、平凡树、生成树和最小生成树等概念及性质，掌握最小生成树的Kruskal算法．2．了解有向树、根树、有序树、最优二元（叉）树等概念及性质，掌握最优树的Huffman 算法．3．掌握利用最优树产生前缀码的方法．第6章命题逻辑考核知识点1．命题与联结词(否定、析取、合取、蕴含、等价)，真值与真值表2．命题公式的解释3．命题公式的等值式与蕴涵式，等值演算4．析取范式、合取范式、极小(大)项，主析取范式、主合取范式的概念与求法5．命题逻辑的推理理论考核要求1．理解命题联结词概念，掌握命题公式的翻译（命题符号化）及判断语句是不是命题的方法．2．熟练掌握求给定公式真值表的方法．3．掌握基本等值式以及用真值表法和等值演算法判别公式类型和公式等值的方法．4．了解析取(合取)范式概念，理解极小(大)项的概念和主析取(合取)范式概念，熟练掌握用基本等值式或真值表将公式化为主析取(合取)范式的方法．5．掌握命题公式的的直接证明方法与间接证明方法．第7章谓词逻辑考核知识点1．谓词，量词，个体词，个体域，变元2．谓词公式的解释3．前束范式的概念与求法4．谓词公式的等值式与蕴涵式5．谓词逻辑的推理理论考核要求1．理解谓词、量词、个体词、个体域、全域、原子公式、谓词公式和变元等概念．掌握谓词公式的翻译．2．掌握在有限个体域下消去公式的量词和求公式在给定解释下真值的方法．3．掌握谓词演算的等值式和重言蕴含式．4．了解前束范式的概念，会求谓词公式的前束范式的方法．5．了解谓词逻辑推理的规则，掌握谓词公式的证明与推导方法．。

离散数学复习要点第一章命题逻辑一、典型考查点1、命题的判断方法：陈述句真值唯一，特殊：反问句也是命题。

其它疑问句、祈使句、感叹句、悖论等皆不是。

详见教材P12、联结词运算定律┐∧∨→记住特殊的：1∧1⇔1，0∨0⇔0，1→0⇔0，11⇔1，00⇔1详见P53、命题符号化步骤：A划分原子命题，找准联结词。

特殊自然语言：不但而且，虽然但是用∧，只有P才Q，应为Q →P；除非P否则Q，应为┐P→Q。

B设出原子命题写出符号化公式。

详见P54、公式的分类判定（重言式、矛盾式、可满足式）方法：其一根据所有真值赋值情况，其二根据等价演算来判断。

详见P95、真值表的构造步骤：①命题变元按字典序排列，共有2n个真值赋值。

②对每个指派，以二进制数从小到大或从大到小顺序列出。

③若公式较复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所求公式的真值。

详见P8。

6、基本概念：置换规则，P规则，T规则，详见P24；合取范式，析取范式，详见P15；小项详见P16；大项详见P18，最小联结词组详见P15,7、等价式详见P22表1.6.2 证明方法：①真值表完全相同②用等价演算③利用A B的充要条件是A B且B A。

主要等价式：(1)双否定：A A。

(2)交换律：A∧B B∧A，A∨B B∨A，A B B A。

3)结合律：(A∧B)∧C A ∧(B∧C)，(A∨B)∨C A∨(B∨C)，(A B)C A(B C)。

(4) 分配律：A∧(B∨C)(A∧B)∨(A∧C)，A∨(B∧C)(A∨B)∧(A∨C)。

(5) 德·摩根律：(A∧B)A∨B，(A∨B)A∧B。

(6) 等幂律：A∧A A，A∨A A。

(7) 同一律：A∧T A，A∨F A。

(8) 零律：A∧F F，A∨T T。

(9) 吸收律：A∧(A∨B)A，A∨(A∧B)A。

(10) 互补律：A ∧A F，(矛盾律)，A∨A T。

(排中律)(11) 条件式转化律：A→B A∨B，A→B B→A。

《离散数学》期中复习内容：第一章~第三章题型：一、选择题（20%，每题2分）二．填空题（16%，每题2分）三、计算题（15%，每题5分）四、证明题（15%，每题5分）五、判断题（20%，每题2分）六、程序题（14%，每题7分）第1章数学语言与证明方法1.1 常用的数学符号1.计算常用的数学符号式子1.2 集合及其表示法1.用列举法和描述法表示集合2.判断元素与集合的关系(属于和不属于)3.判断集合之间的包含与相等关系，空集(E)，全集(∅)4.计算集合的幂集5.求集合的运算：并、交、相对补、对称差、绝对补6.用文氏图表示集合的运算7.证明集合包含或相等方法一：根据定义, 通过逻辑等值演算证明方法二：利用已知集合等式或包含式, 通过集合演算证明1.3 证明方法概述1、用如下各式方法对命题进行证明。

☐直接证明法：A→B为真☐间接证明法：“A→B为真” ⇔“ ¬B→ ¬A为真”☐归谬法(反证法)：A∧¬B→0为真☐穷举法：A1→B, A2→B,…, A k→B 均为真☐构造证明法：在A为真的条件下, 构造出具有这种性质的客体B ☐空证明法：“A恒为假” ⇒“A→B为真”☐平凡证明法：“B恒为真”⇒“A→B为真”☐数学归纳法：第2章命题逻辑2.1 命题逻辑基本概念1、判断句子是否为命题、将命题符号化、求命题的真值（0或1）。

命题的定义和联结词(¬, ∧, ∨, →, ↔)2、判断命题公式的类型赋值或解释.成真赋值,成假赋值；重言式(永真式)、矛盾式(永假式)、可满足式:。

2.2 命题逻辑等值演算1、用真值表判断两个命题公式是否等值2、用等值演算证明两个命题公式是否等值3、证明联结词集合是否为联结词完备集2.3 范式1、求命题公式的析取范式与合取范式2、求命题公式的主析取范式与主合取范式（两种主范式的转换）3、应用主析取范式分析和解决实际问题2.4 命题逻辑推理理论1、用直接法、附加前提、归谬法、归结证明法等推理规则证明推理有效第3章一阶逻辑3.1 一阶逻辑基本概念1、用谓词公式符号命题（正确使用量词）2、求谓词公式的真值、判断谓词公式的类型3.2 一阶逻辑等值演算1、证明谓词公式的等值式2、求谓词公式的前束范式3、一阶逻辑的演绎推理（补充）程序题：1.编写程序用位串方法，求出它们的交集、相对补集、对称差集、绝对补集。

离散数学知识点总结 一、各章复习要求与重点第一章 集 合[复习知识点]1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集2、集合的交、并、差、补等运算及其运算律（交换律、结合律、分配律、吸收律、 De Morgan 律等），文氏（V enn ）图3、序偶与迪卡尔积本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明 [复习要求]1、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。

2、掌握集合的表示法和集合的交、并、差、补等基本运算。

3、掌握集合运算基本规律，证明集合等式的方法。

4、了解序偶与迪卡尔积的概念，掌握迪卡尔积的运算。

[本章重点习题]P5~6，4、6； P14~15，3、6、7； P20，5、7。

[疑难解析] 1、集合的概念因为集合的概念学生在中学阶段已经学过，这里只多了一个幂集概念，重点对幂集加以掌握，一是掌握幂集的构成，一是掌握幂集元数为2n 。

2、集合恒等式的证明通过对集合恒等式证明的练习，既可以加深对集合性质的理解与掌握；又可以为第三章命题逻辑中公式的基本等价式的应用打下良好的基础。

实际上，本章做题是一种基本功训练，尤其要求学生重视吸收律和重要等价式在B A B A ~⋂=-证明中的特殊作用。

[例题分析]例1 设A ，B 是两个集合，A={1，2，3}，B={1，2}，则=-)()(B A ρρ 。

解}}3,2,1{},3,2{},3,1{},2,1{},3{},2{},1{,{)(φρ=A}}2,1{},2{},1{,{)(φρ=B于是}}3,2,1{},3,2{},3,1{},3{{)()(=-B A ρρ例2 设{}{}Φ=,,,,b a b a A ，试求：(1){}b a A ,-； (2)Φ-A ； (3){}Φ-A ； (4){}{}A b a -,； (5)A -Φ； (6){}A -Φ。

解 (1){}{}{}Φ=-,,,b a b a A (2)A A =Φ- (3){}{}{}b a b a A ,,,=Φ- (4){}{}Φ=-A b a , (5)Φ=-ΦA (6){}Φ=-ΦA 例3 试证明()()()()B A B A B A B A ~~~~⋂⋃⋂=⋃⋂⋃ 证明()()()()()()()()()()()()()()()()()()B A B A B A B A B B B A A B A A B B A A B A B A B A ~~~~~~~~~~~~~⋂⋃⋂=Φ⋃⋂⋃⋂⋃Φ=⋂⋃⋂⋃⋂⋃⋂=⋂⋃⋃⋂⋃=⋃⋂⋃第二章 二元关系[复习知识点]1、关系、关系矩阵与关系图2、复合关系与逆关系3、关系的性质（自反性、对称性、反对称性、传递性）4、关系的闭包（自反闭包、对称闭包、传递闭包）5、等价关系与等价类6、偏序关系与哈斯图（Hasse ）、极大/小元、最大/小元、上/下界、最小上界、最大下界7、函数及其性质（单射、满射、双射）8、复合函数与反函数本章重点内容：二元关系的概念、关系的性质、关系的闭包、等价关系、半序关系、映射的概念 [复习要求]1、理解关系的概念：二元关系、空关系、全关系、恒等关系；掌握关系的集合表示、关系矩阵和关系图、关系的运算。

离散数学结构第3章命题逻辑的推理理论复习第3章命题逻辑的推理理论主要内容1. 推理的形式结构：①推理的前提②推理的结论③推理正确④有效结论2. 判断推理是否正确的⽅法：①真值表法②等值演算法③主析取范式法3. 对于正确的推理，在⾃然推理系统P中构造证明4. ①⾃然推理系统P的定义②⾃然推理系统P的推理规则：前提引⼊规则、结论引⼊规则、置换规则、假⾔推理规则、附加规则、化简规则、拒取式规则、假⾔三段式规则、构造性⼆难规则、合取引⼊规则。

③附加前提证明法④归谬法学习要求1. 理解并记住推理的形式结构的三种等价形式，即①{A1,A2,…,A k}├B②A1∧A2∧…∧A k→B③前提与结论分开写：前提：A1,A2,…,A k结论：B在判断推理是否正确时，⽤②；在P系统中构造证明时⽤③。

2. 熟练掌握判断推理是否正确的三种⽅法（真值表法，等值演算法，主析取范式法）。

3. 牢记P系统中的各条推理规则。

4. 对于给定的正确推理，要求在P系统中给出严谨的证明序列。

5. 会⽤附加前提证明法和归谬法。

3.1 推理的形式结构定义3.1设A1,A2,…,A k和B都是命题公式，若对于A1,A2,…,A k和B中出现的命题变项的任意⼀组赋值，或者A1∧A2∧…∧A k为假，或者当A1∧A2∧…∧A k为真时，B也为真，则称由前提A1,A2,…,A k推出B的推理是有效的或正确的，并称B是有效结论。

⼆、有效推理的等价定理定理3.1命题公式A1,A2,…,A k推B的推理正确当且仅当(A1∧A2∧…∧A k )→B为重⾔式。

A k为假，或者A1∧A2∧…∧A k和B同时为真，这正符合定义3.1中推理正确的定义。

由此定理知，推理形式：前提：A1,A2,…,A k结论：B是有效的当且仅当(A1∧A2∧…∧A k)→B为重⾔式。

(A1∧A2∧…∧A k)→B称为上述推理的形式结构。

从⽽推理的有效性等价于它的形式结构为永真式。

于是，推理正确{A1,A2,…,A k} B可记为A1∧A2∧…∧A k B其中同⼀样是⼀种元语⾔符号，⽤来表⽰蕴涵式为重⾔式。

2014《离散》复习重点
第三章:属于,包含,相等，并集；环和；非空有限子集；
第四章:叉积;
等价关系，自反、对称、传递；等价类；
半序关系，自反、反对称, 传递；
半序集；
Hasse图（哈斯图）；
上确界、下确界，最大元素、最小元素。

良序集;
第五章:单射，满射、双射；
无限集合、可数集合、等势；
第六章:幺元，幂等元；
群，子群，定理14(非空性、包含性，封闭性、有逆元)；左陪集，右陪
集，定理17和定理19的证明；
同态、同态公式；
同构（单射，满射，同态公式）；
环，子环(非空性、包含性、(混合)封闭性x-y = x⊕(-y)、封闭性x⊗y)；
含零因子环，无零因子环；
环(N m , +m, ⨯m)；
域，素域，有限域；
（重点）
第七章:格(封闭性、结合律、交换律、幂等律、吸收律)；保序性；
半序格,定理4(a≼b ⇔a*b = a⇔a⊕b = b)；
分配格；
补元、唯一性；
叉积格；
（重点）
第八章:强连通图
迪杰克斯算法，迪杰克斯算法的特点；
欧拉图，定理1；有向欧拉图；
哈密顿图，定理1，标号法(着色法)；
二分图，定理1，标号法(着色法);
树；
（重点）。