《离散数学》复习提纲(2018)

《离散数学》期末复习一、期末考试题型试题类型及分数分别为单项选择题和填空题各有15题，分数占60％；化简解答题与计算题及证明题，共占40％。

各章分数的比例大致与其所用课时比例相同。

单项选择题和填空题主要涉及基本概念、基本理论、重要性质和结论、公式及其简单计算。

单项选择题给出四个备选答案，其一正确。

填空题只需填写正确结论，不写计算、推论过程或理由。

化简解答题与计算题主要考核同学们的基本运算技能和速度，要求写出计算过程。

证明题主要考查应用概念、性质、定理及重要结论进行逻辑推理的能力，要求写出推理过程。

二、各章复习要求和重点第1章命题逻辑复习要求1. 命题及其联结词。

命题表述为具有确定真假意义的陈述句。

命题必须具备二个条件：其一，语句是陈述句；其二，语句有唯一确定的真假意义，六个联结词。

2. 命题公式及分类。

在各种赋值下均为真的命题公式A，称为重言式(永真式)；在各种赋值下均为假的命题公式A，称为矛盾式(永假式)；命题A不是矛盾式，称为可满足式；真值表3. 命题的判定及命题演算的推理理论。

推理方法有：真值表法；等值演算法；主析取范式法，构造证明法(直接证明法、附加前提证明法和间接证明法)本章重点：命题与联结词，公式与解释，真值表，公式的类型及判定, (主)析取(合取)范式，命题逻辑的推理理论.。

第2章一阶逻辑复习要求1.谓词与量词谓词，在谓词逻辑中，原子命题分解成个体词和谓词. 个体词是可以独立存在的客体，它可以是具体事物或抽象的概念。

谓词是用来刻划个体词的性质或事物之间关系的词 量词，是在命题中表示数量的词，量词有两类：全称量词∀，表示“所有的”或“每一个”；存在量词∃，表示“存在某个”或“至少有一个”2. 2.公式与解释谓词公式，由原子公式、联结词和量词可构成谓词公式(严格定义见教材).命题的符号化结果都是谓词公式.例如∀x(F(x)→G(x))，∃x(F(x)∧G(x))，∀x∀y(F(x)∧F(y)∧L(x,y)→H(x,y))等都是谓词公式3. 解释(赋值)，谓词公式A的个体域D是非空集合，则(1) 每一个常项指定D中一个元素；(2) 每一个n元函数指定D n到D的一个函数；(3) 每一个n元谓词指定D n到{0,1}的一个谓词；按这个规则做的一组指派，称为A的一个解释或赋值。

离散数学复习提纲离散数学是一门关于离散对象的数学分支，它主要研究离散结构及其性质，广泛应用于计算机科学、信息技术、密码学等领域。

下面是一个离散数学的复习提纲，包括离散数学的基本概念、离散结构、图论、关系、逻辑以及集合论等内容。

一、离散数学的基本概念1.数学基础：集合、函数、关系、证明方法（数学归纳法、反证法、递归法等）；2.命题逻辑：命题、命题连接词、真值表、逻辑运算、逻辑等价、推理规则等；3.谓词逻辑：谓词、量词、公式、合取范式和析取范式、蕴含、等价、量词的否定规则等；4.证明方法：直接证明、间接证明、归谬证明、证明策略等。

二、离散结构1.图论：图的基本概念、图的表示方法、连通性、路径和回路、图的着色、最小生成树等；2.代数结构：群、环、域的定义、性质及基本例子；3.组合数学：组合基本原理、二项式系数、排列组合、生成函数、递归关系、容斥原理等；4.有限状态自动机：确定性有限状态自动机、非确定性有限状态自动机、正则表达式等。

1.图的基本概念：顶点、边、路径、回路、度等；2.图的表示：邻接矩阵、邻接表、关联矩阵等；3.图的遍历：深度优先、广度优先；4. 最短路径问题：Dijkstra算法、Floyd-Warshall算法；5. 最小生成树问题：Prim算法、Kruskal算法；6.匹配问题：最大匹配、二分图匹配等。

四、关系1.关系的基本概念：关系矩阵、关系的性质（反自反性、对称性、传递性等）；2.等价关系：等价关系的性质、等价类等；3.偏序关系：偏序关系的性质、偏序集合、哈斯图等；4.传递闭包：传递闭包的定义、传递闭包的计算方法等。

五、逻辑1.命题逻辑：命题的定义、逻辑运算、真值表、逻辑等价、推理规则等；2.谓词逻辑：量词的定义、公式的定义、量词的否定规则、等价变换等；3.命题逻辑与谓词逻辑的转换；4.形式化推理：前向链式推理、后向链式推理、消解法等。

1.集合的基本概念：子集、并集、交集、差集、补集等；2.集合运算：集合的并、交、差、补等运算的性质；3.集合的关系：包含关系、相等关系、等价关系等；4.集合的表示方法：列举法、描述法、元祖法等；5.集合的基数：有限集合的基数、无穷集合的基数、基数的性质。

2018年春季学期离散数学期末复习题第一章集合论一、判断题（1）空集是任何集合的真子集． （ 错 ）（2）{}φ是空集． （ 错 ） （3）{}{}a a a },{∈ （ 对 ） （4）设集合{}{}{}{}AA 22,1,2,1,2,1⊆=则. ( 对 ） （5）如果B A a ⋃∉，则A a ∉或B a ∉． （ 错 ） 解 B A a ⋃∉则B A B A a ⋂=⋃∈，即A a ∈且B a ∈，所以A a ∉且B a ∉（6）如果A ∪.,B A B B ⊆=则 （ 对 ）（7）设集合},,{321a a a A =，},,{321b b b B =，则},,,,,{332211><><><=⨯b a b a b a B A （ 错 ）（8）设集合}1,0{=A ，则}1},0{,0},0{,1,,0,{><><><><=φφρ是A 2到A 的关系． （ 对 ） 解 A 2}},1{},0{,{A φ=，=⨯A A 2}1,,0,,1},1{,0},1{,1},0{,0},0{,1,,0,{><><><><><><><><A A φφ（9）关系的复合运算满足交换律． （ 错 ）（10）.条件具有传递性的充分必要上的关系是集合ρρρρA =ο （ 错 ）（11）设.~,上的传递关系也是则上的传递关系是集合A A ρρ ( 对 ) （12）集合A 上的对称关系必不是反对称的. （ 错 ）（13）设21,ρρ为集合A 上的等价关系, 则21ρρ⋂也是集合A 上的等价关系( 对 ) （14）设ρ是集合A 上的等价关系, 则当ρ>∈<b a ,时， ρρ][][b a = ( 对 )（15）设21,ρρ为集合A 上的等价关系, 则 ( 错 )二、单项选择题 （1）设R 为实数集合，下列集合中哪一个不是空集 （ A ）A. {}R x x x ∈=-且,01|2 B ．{}R x x x ∈=+且,09|2C. {}R x x x x ∈+=且,1|D. {}R x x x ∈-=且,1|2（2）设B A ,为集合，若φ=B A \，则一定有 （ C ）A. φ=B B ．φ≠B C. B A ⊆ D. B A ⊇（3）下列各式中不正确的是 （ C ）A. φφ⊆ B ．{}φφ∈ C. φφ⊂ D. {}}{,φφφ∈（4）设{}}{,a a A =，则下列各式中错误的是 （ B ）A. {}A a 2∈ B ．{}A a 2⊆ C. {}A a 2}{∈ D. {}Aa 2}{⊆ （5）设{}2,1=A ，{}c b a B ,,=，{}d c C ,=，则)(C B A I ⨯为 （ B ） A. {}><><c c ,2,1, B ．{}><><c c ,2,,1C. {}><><2,,,1c cD. {}><><2,,1,c c（6）设{}b A ,0=，{}3,,1b B =，则B A Y 的恒等关系为 （ A ） A. {}><><><><3,3,,,1,1,0,0b b B ．{}><><><3,3,1,1,0,0C. {}><><><3,3,,,0,0b bD. {}><><><><0,3,3,,,1,1,0b b（7）设{}c b a A ,,=上的二元关系如下，则具有传递性的为 （ D ）A.{}><><><><=a b b a a c c a ,,,,,,,1ρ B ．{}><><=a c c a ,,,2ρ C.{}><><><><=c b a b c c b a ,,,,,,,3ρ D. {}><=a a ,4ρ（8）设ρ为集合A 上的等价关系，对任意A a ∈，其等价类[]ρa 为 （B ） A. 空集； B ．非空集； C. 是否为空集不能确定； D. }|{A x x ∈.（9）映射的复合运算满足 （ B ）A. 交换律 B ．结合律 C. 幂等律 D. 分配律（10）设A ，B 是集合，则下列说法中（ C ）是正确的.A ．A 到B 的关系都是A 到B 的映射B ．A 到B 的映射都是可逆的C ．A 到B 的双射都是可逆的D ．B A ⊂时必不存在A 到B 的双射（11）设A 是集合，则（ B ）成立.A ．A A #22#=B ．A X X A ⊆↔∈2C ．{}A2∈φ D ．{}AA 2∈ （12）设A 是有限集（n A =#），则A 上既是≤又是～的关系共有（B ）.A ．0个B ．1个C ．2个D ．n 个三、填空题1. 设}}2,1{,2,1{=A ，则=A 2____________. 填}}},2,1{,2{}},2,1{,1{},2,1{}},2,1{{},2{},1{,{2A A φ=2.设}}{,{φφ=A ，则A 2= . 填}}},{{},{,{2A A φφφ=3.设集合B A ,中元素的个数分别为5#=A ，7#=B ，且9)(#=⋃B A ，则集合B A ⋂中元素的个数=⋂)(#B A .34.设集合}4,1001|{Z x x x x A ∈≤≤=的倍数，是，}5,1001|{Z x x x x B ∈≤≤=的倍数，是，则B A Y 中元素的个数为 .405.设 },{b a A =, ρ 是 A 2 上的包含于关系，,则有ρ= .},,},{,}{},{,},{,}{},{,,,}{,,}{,,,{><><><><><><><><><A A A b b b A a a a A b a φφφφφ6.设21,ρρ为集合A 上的二元关系, 则=21ρρο .~1~2ρρο 7.集合A 上的二元关系ρ为传递的充分必要条件是 ．ρρρ⊆ο8. 设集合{}{}><><==0,2,2,02,1,01ρ上的关系A 及集合A 到集合{}4,2,0=B 的关系=2ρ｛><b a ,|><b a ,A b a B A ∈⨯∈,且∩}=21,ρρο则B ___________________. 填 }2,2,0,2,2,0,0,0{><><><><四、解答题1. 设集合{}{}{},2,1,,2,1,==B A φφ 求（1）A ∪B 2 ；（2）B A 22I 解 （1）A ∪{}{}φφ,2,1,2=B ∪{}{}{}B ,2,1,φ {}{}{}{}.,2,1,,2,1,B φφ= （2）}{2φ=B A I ，所以 }}{,{22}{2φφφ==BA I2. 设 A d c b a A },,,,{=上的关系 },,,,,,,,,,,,,,,{><><><><><><><><=c d d c a b b a d d c c b b a a ρ（1）写出ρ的关系矩阵；（2）验证ρ是A 上的等价关系；（3）求出A 的各元素的等价类。

离散数学期末复习总要离散数学期末复习各个章节要点纲要（及定理）离散数学定义定理1.3.1命题演算的合式公式规定为：（1）单个命题变元本身是一个合式公式。

（2）如果A是合式公式，那么┐A是合式公式。

（3）如果A和B是合式公式，那么（A∨B）、（A∧B）、（A→B）、（A?B）、都是合式公式。

（4）当且仅当有限次地应用（1）（2）（3）所得到的包含命题变元，连接词和圆括号的符号串是合式公式。

1.3.2 设Ai是公式A的一部分，且Ai是一个合式公式，称Ai是A的子公式。

1.3.3 设P为一命题公式，P1,P2,……，Pn为出现在P中的所有命题变元，对P1,P2,……，Pn指定一组真值称为对P的一种指派。

若指定的一种指派，使P的值为真，则称这组指派为成真指派。

若指定的一种指派，使P的值为假，则称这种指派为成假指派。

含n个命题变元的命题公式，共有2n个指派。

1.3.4 给定两个命题公式A和B，设P1,P2,……，Pn为所有出现于A和B中的原子变元，若给P1,P2,……，Pn任一组真值指派，A和B的真值都相同，称A和B是等价的，记做A <=>B。

1.3.5 设A为一命题公式，若A在它的各种指派情况下，其取值均为真，则称A为重言式或永真式。

1.3.6 设A为一命题公式，若A在它的各种指派情况下，其取值均为假，则称A为矛盾式或永假式。

1.3.7设A为一命题公式，若A在它的各种指派情况下至少存在一组成真指派，则称A为可满足式。

1.4.1 设X式合式公式A的子公式，若有Y也是一个合式公式，且X<=>Y，如果将Ａ中的Ｘ用Ｙ置换，得到公式Ｂ，则A<=>B。

1.4.2 设A，B为两个命题公式，A<=>B，当且仅当A ←→B为一个重言式。

P=>Q称做P蕴含Q或蕴含式，又称永真条件式。

蕴含式有下列性质：（1）对任意公式A，又A=>A；（2）对任意公式A，B和C，若A=>B，B=>C，则A=>C；（3）对任意公式A，B和C，若A=>B，A=>C，则A=>(B∧C); （4）对任意公式A，B和C，若A=>C，B=>C，则A∨B=>C.1.4.3设P，Q为任意两个命题公式，P<=>Q的充分必要条件式P=>Q,，Q=>P。

《离散数学》期末复习大纲（完整版）（含例题和考试说明）一、命题逻辑[复习知识点]1、命题与联结词（否定￢、析取∨、合取∧、蕴涵→、等价↔），复合命题2、命题公式与赋值（成真、成假），真值表，公式类型（重言、矛盾、可满足），公式的基本等值式3、范式：析取范式、合取范式，极大（小）项，主析取范式、主合取范式4、公式类型的判别方法（真值表法、等值演算法、主析取/合取范式法）5、命题逻辑的推理理论本章重点内容：命题与联结词、公式与解释、（主）析取范式与（主）合取范式、公式类型的判定、命题逻辑的推理[复习要求]1、理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方法。

2、理解公式与赋值的概念；掌握求给定公式真值表的方法，用基本等值式化简其它公式，公式在解释下的真值。

3、了解析取（合取）范式的概念；理解极大（小）项的概念和主析取（合取）范式的概念；掌握用基本等值式或真值表将公式化为主析取（合取）范式的方法。

4、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判别公式类型和公式等价方法。

5、掌握命题逻辑的推理理论。

[疑难解析]1、公式类型的判定判定公式的类型，包括判定公式是重言的、矛盾的或是可满足的。

具体方法有两种，一是真值表法，二是等值演算法。

2、范式求范式，包括求析取范式、合取范式、主析取范式和主合取范式。

关键有两点：一是准确理解掌握定义；另一是巧妙使用基本等值式中的分配律、同一律和互补律（排中律、矛盾律），结果的前一步适当使用幂等律，使相同的短语（或子句）只保留一个。

3、逻辑推理掌握逻辑推理时，要理解并掌握12个（除第10，11）推理规则和3种证明法（直接证明法、附加前提证明法和归谬法）。

例1.试求下列公式的主析取范式：（1）))()((P Q Q P P ⌝∨⌝⌝∧→→；（2）)))((R Q Q P P →⌝∨→⌝∨（))()(())()((:)1P Q Q P Q P P P Q Q P P ∧∧∨∧∧⌝∨⌝=∧∧∨⌝∨⌝=原式解 Q P P P Q P P Q P ∨⌝=∨⌝∧∨⌝=∧∨⌝=)()()())(())((Q P P Q Q P ∧∨⌝∨∨⌝∧⌝=)()()(Q P Q P Q P ∧∨∧⌝∨⌝∧⌝=)))((()))(((:)2R Q Q P P R Q Q P P ∨∨∨∨=→⌝∨→⌝∨解)()()()(R Q P R Q P R Q P R Q P R Q P ∧⌝∧∨∧∧⌝∨⌝∧∧⌝∨∧⌝∧⌝=∨∨=)()()(R Q P R Q P R Q P ∧∧∨⌝∧∧∨⌝∧⌝∧∨）2．用真值表判断下列公式是恒真？恒假？可满足？（1）（P ∧⌝P ）↔Q（2）⌝（P →Q ）∧Q（3）（（P →Q ）∧（Q →R ））→（P →R ）解：（1） 真值表因此公式（1）为可满足。

2018离散数学复习要点1.命题演算公式的范式、主范式是什么？2.命题演算的假设推理证明方法是什么？3.命题演算的归结推理证明方法是什么？4.在命题演算归结推理证明过程中容易犯的错误有哪些？5.在知识翻译时，紧跟在量词之后的主联结词是怎么规定的？6.谓词演算公式的前束范式是什么？7.谓词演算公式的SKOLEM(斯柯伦)标准形是什么？8.谓词演算的假设推理证明方法是什么？9.谓词演算的归结推理证明方法是什么？10.谓词演算的HORN子句逻辑程序证明方法是什么？11.子句与SKOLEM(斯柯伦)标准形有什么关系？12.把函数化为(m,n)标准迭置的方法是什么？13.什么是集合的包含关系？14.集合的基本运算有哪些？15.A×B是什么？16.2A是什么？17.集合等式的证明方法有哪些？18.什么是二元关系的自反性、反自反性、对称性、反对称性和传递性？19.什么是等价关系？两个等价关系的并/交还是不是等价关系？20.什么是一个集合的划分？它与等价关系有什么关联？21.什么是函数的单射性、满射性、双射性？22.函数的复合=关系的复合,但记号顺序相反。

23.简单无向图的定义是什么？24.握手定理是什么？25.什么是连通性？什么是连通分支？26.欧拉图的充分必要条件是什么？27.哈密尔顿图的充分条件是什么？必要条件是什么？28.什么是二部图？二部图的边与顶点的关系是什么？29.关于连通平面图的欧拉公式是什么？30.简单连通平面图的必要条件是什么？简单连通平面图的边与区域有什么关系？31.在什么条件下两个图同构？32.什么是树？树的等价定义有哪些？33.对于一棵树，顶点的度数与边数有什么关系？34.什么是生成树、最小生成树？35.什么是基本圈系统、基本割集？36.什么是半群、含幺半群？37.什么是群？38.什么是群的同态、群的同构？39.什么是子群？子群的判定条件是什么？40.什么是正规子群？。

离散数学复习提纲第一章 命题逻辑1．（P ∨Q ）→（⌝Q ∧R ）的主合取范式和主析取范式。

2．试求下列公式的主析取范式：（1）))()((P Q Q P P ⌝∨⌝⌝∧→→；（2）)))((R Q Q P P →⌝∨→⌝∨（an: ))()(())()((:)1P Q Q P Q P P P Q Q P P ∧∧∨∧∧⌝∨⌝=∧∧∨⌝∨⌝=原式解 Q P P P Q P P Q P ∨⌝=∨⌝∧∨⌝=∧∨⌝=)()()())(())((Q P P Q Q P ∧∨⌝∨∨⌝∧⌝=)()()(Q P Q P Q P ∧∨∧⌝∨⌝∧⌝=)))((()))(((:)2R Q Q P P R Q Q P P ∨∨∨∨=→⌝∨→⌝∨解)()()()(R Q P R Q P R Q P R Q P R Q P ∧⌝∧∨∧∧⌝∨⌝∧∧⌝∨∧⌝∧⌝=∨∨=)()()(R Q P R Q P R Q P ∧∧∨⌝∧∧∨⌝∧⌝∧∨）3．用真值表判断下列公式是恒真？恒假？可满足？（1）（P ∧⌝P ）↔Q（2）⌝（P →Q ）∧Q（3）（（P →Q ）∧（Q →R ））→（P →R ）(an: 解：（1）真值表)（2因此公式（2）为恒假。

（3因此公式（3）为恒真。

4．┐Q ∧（P →Q ）蕴涵 ┐P法1：真值表法2：若┐Q ∧（P →Q ）为真，则 ┐Q ，P →Q 为真，所以Q 为假，P 为假，所以┐P 为真。

法3：若┐P 为假，则P 为真，再分二种情况：①若Q 为真，则┐QÙ（P →Q ）为假②若Q 为假，则P →Q 为假，则┐Q ∧（P →Q ）为假根据① ②，所以 ┐Q ∧（P →Q ）蕴涵 ┐P 。

）5．利用基本等价式证明下列命题公式为恒真公式。

（（P →Q ）∧（Q →R ））→（P →R ）（（P ∨Q ）∧⌝（⌝P ∧（⌝Q ∨⌝R ）））∨（⌝P ∧⌝Q ）∨（⌝P ∧⌝R ）（an: 1、证明：（（P →Q ）∧（Q →R ））→（P →R ）=（（⌝P ∨Q ）∧（⌝Q ∨R ））→（⌝P ∨R ）=⌝（（⌝P ∨Q ）∧（⌝Q ∨R ））∨（⌝P ∨R ）=（P ∧⌝Q ）∨（Q ∧⌝R ）∨⌝P ∨R=（（P ∧⌝Q ）∨⌝P ）∨（（Q ∧⌝R ）∨R ）=（1∧（⌝Q ∨⌝P ））∨（（Q ∨R ）∧1）= ⌝Q ∨⌝P ∨Q ∨R=（⌝Q ∨Q ） ∨⌝P ∨R= 1 ∨⌝P ∨R= 1（（P ∨Q ）∧⌝（⌝P ∧（⌝Q ∨⌝R ）））∨（⌝P ∧⌝Q ）∨（⌝P ∧⌝R ）=（（P ∨Q ）∧（P ∨（Q ∧R ）））∨（⌝P ∧（⌝Q ∨⌝R ））=（P ∨（Q ∧ Q ∧R ））∨（⌝P ∧（⌝Q ∨⌝R ））=（P ∨（Q ∧R ））∨⌝（P ∨（Q ∧R ））=1）6．用形式演绎法证明：{S R R Q Q P →∨⌝∨⌝,,}蕴涵S P →(an: 证明：2006年12月离散数学复习提纲 3（1）Q P ∨⌝ 规则P（2）Q P → 规则Q （1）（3）R Q ∨⌝ 规则P（4）R Q → 规则Q （3）（5）R P → 规则Q （2）（4）（6）R →S 规则P（7）P →S 规则Q （5）（6） )7．用形式演绎法证明：（E F D D C B A →∨∧→∨)(),()蕴涵A E →（an: 、证明：(改()()(),()F D F D B A B A ∨∧∨∧为为)（1）A 规则D（2）A ∨B 规则Q （1）（3）)()(D C B A ∧→∨ 规则P（4）D C ∧ 规则Q （2）（3）（5）D 规则Q （4）（6）F D ∨ 规则Q （5）（7）E F D →∨)( 规则P（8）E 规则Q （6）（7）（9）E A → 规则Q （1）（8））8．┐（P ∧┐Q ），┐Q ∨R ，┐R 蕴涵 ┐P（an: （1）┐Q ∨R（2）┐R（3）┐Q（4）┐（P ∧┐Q ）（5）┐P ∨Q（6）┐P ）9．某案涉及甲、乙、丙、丁四个，根据已有线索，已知：（1） 若甲、乙均未作案，则丙、丁也均未作案；（2） 若丙、丁均未作案，则甲、乙也均未作案；（3） 若甲与乙同时作案，则丙与丁有一人且只有一人作案；（4） 若乙与丙同时作案，则甲与丁同时作案或同未作案。

试卷类型一、选择题（10题，每题2分，共计20分）二、填空题（10空，每空2分，共计20分）三、选择题（8题，每空1分，共计8分）四、名词解释（3个，每个4分，共计12分）五、构造推理证明题（1题，计10分）六、计算题（共计30分）求解主析取范式或合取范式、等价关系或偏序关系哈斯图、最小生成树、求解前束范式离散数学的定义第1章数学语言与证明方法主要内容：●集合定义，集合的两种描述方法，空集合的定义与定理及推论，子集、真子集、全集，相等集合，包括0的自然数、有理数、整数、实数集合，集合的元素个数●集合的交、并、补、差、对称差、幂运算（集合的个数）定义，经过括号形成的更为复杂的集合运算，简单的可以通过文氏图来表示。

第2章命题逻辑主要内容：●命题及其真值。

感叹句、祈使句、疑问句都不是命题，陈述句中的悖论以及判断结果不惟一确定的也不是命题。

●简单命题与复合命题概念，5种联结词的具体涵义、真值表与符号表示，汉语的复合句的那些联结词与它们对应，特别是相容或和排斥或的符号化表示。

●联结词优先级：( ),⌝, ∧, ∨, →, ↔；同级按从左到右的顺序进行●命题常项、命题变项、合式公式定义，公式的赋值、真值表●命题公式的分类有重言式（永真式）、矛盾式（永假式）、可满足式●等值式的定义，真值表法和等值演算两种判断方法，置换规则●文字、简单析取式、简单合取式、析取范式、合取范式的定义●定理：(1) 一个简单析取式是重言式当且仅当它同时含某个命题变项和它的否定；(2) 一个简单合取式是矛盾式当且仅当它同时含某个命题变项和它的否定●定理：(1) 一个析取范式是矛盾式当且仅当它的每一个简单合取式都是矛盾式；(2)一个合取范式是重言式当且仅当它的每一个简单析取式都是重言式●定理：任何命题公式都存在着与之等值的析取范式与合取范式●求公式的范式的3个步骤●极小项、极大项的定义，对于每一个最小项只有一种指派使其取1，对于每一个最大项只有一种指派使其取0●定理：设m i与M i是由同一组命题变项形成的极小项和极大项, 则⌝m i ⇔ M i , ⌝M i⇔ m i●主析取范式、主合取范式的定义，求解公式的析取范式、合取范式、主析取范式、主合取范式●定理：任何命题公式都存在着与之等值的主析取范式和主合取范式, 并且是惟一的●求主析取范式的步骤，求主合取范式的步骤，快速求法、主析取范式的用途●命题逻辑推理的推理证明第3章一阶逻辑主要内容：●个体词（个体常项、个体变项）、个体域、全总个体域的定义●谓词（全称量词和存在量词）、n元谓词P(x1, x2,…, xn)的定义，命题的符号化●量词（全称量词和存在量词）、谓词公式、量词的辖域、谓词公式的真值判断、量词的消去等值变换●等值式的定义，5类基本等值式（量词的消去，量词辖域范围的收缩和扩展）●置换规则、换名规则的定义●前束范式的定义，利用量词的辖域的扩张，完成前束范式的求解●定理3.3(前束范式存在定理) 一阶逻辑中的任何公式都存在与之等值的前束范式第4章关系主要内容：●有序对、笛卡儿积、二元关系、从A到B的关系、A上的关系的定义●A上重要关系●A到B上关系的计数，A上关系的计数●关系的三种表示：关系的集合表达式、关系矩阵、关系图，后两种的使用限制●定义域、值域、域的定义●关系的运算：逆、合成的定义和表示方法以及简单计算●定理 4.1 设F是任意的关系, 则 (1) (F-1)-1=F (2) dom F-1=ran F,ran F-1=dom F●定理4.2 设F, G, H是任意的关系, 则(1) (F∘G)∘H=F∘(G∘H) (2) (F∘G)-1=G-1∘F-1●定理4.3 设R 为A上的关系, 则R∘I A= I A∘R = R●定义4.13 设R为A上的关系, n为自然数, 则 R 的 n次幂是 (1) R0 = {<x,x>| x∈A } = I A (2) R n+1 = R n∘R●定理4.4 设 A 为 n 元集, R是A上的关系, 则存在自然数 s 和 t, 使得 R s=R t.●定理4.5 设 R 是 A 上的关系, m, n∈N, 则 (1) R m∘R n = R m+n (2) (R m)n= R mn●自反性与反自反性, 对称性与反对称性，传递性的定义以及矩阵表示的特征。

离散数学复习提纲一、基本内容数理逻辑部分1．理解命题概念，会判别语句是不是命题．理解五个联结词：否定、析取、合取、条件、和双条件及其真值表，会将简单命题符号化．具有确定真假意义的陈述句称为命题．命题必须具备：其一，语句是陈述句；其二，语句有唯一确定的真假意义.2．了解公式的概念(公式、赋值、成真指派和成假指派)和公式真值表的构造方法．能熟练地作公式真值表．理解永真式和永假式概念，掌握其判别方法．判定命题公式类型的方法：其一是真值表法，其二是等价演算法.3．了解公式等价概念，掌握公式的重要等价式和判断两个公式是否等价的有效方法：等价演算法、列真值表法和主范式方法．4．理解析取范式和合取范式、极大项和极小项、主析取范式和主合取范式的概念，熟练掌握它们的求法．命题公式的范式不惟一，但主范式是惟一的．命题公式A 有n 个命题变元，A 的主析取范式有k 个极小项，有m 个极大项，则 n m k 2=+ 求命题公式A 的析取(合取)范式的步骤．求命题公式A 的主析取(合取)范式的步骤．5．要理解并掌握推理理论的规则、重言蕴含式和等价式，掌握命题公式的证明方法：真值表法、直接证法、间接证法．重点：命题与联结词，公式与解释，真值表，公式的类型及判定，主析取(合取)范式，命题演算的推理理论.6．理解谓词、量词、个体词、个体域，会将简单命题符号化．原子命题分成个体词和谓词，个体词可以是具体事物或抽象的概念，分个体常项和个体变项．谓词用来刻划个体词的性质或之间的关系．量词分全称量词，存在量词.命题符号化注意：使用全称量词，特性谓词后用；使用存在量词，特性谓词后用．7．了解原子公式、谓词公式、变元(约束变元和自由变元)与辖域等概念．掌握在有限个体域下消去公式的量词和求公式在给定解释下真值的方法．由原子公式、联结词和量词构成谓词公式．谓词公式具有真值时，才是命题． 在谓词公式中，会区分约束变元和自由变元．在非空集合D(个体域)上谓词公式A 的一个解释或赋值有3个条件．在任何解释下，谓词公式A 取真值1，A 为逻辑有效式(永真式)；公式A 取真值0，A 为永假式；至少有一个解释使公式A 取真值1，A 称为可满足式．在有限个体域下，消除量词的规则为：设D ＝{n a a a ,...,21}，则)(...)()()(21n a A a A a A x xA ∧∧∧⇔∀)(...)()()(21n a A a A a A x xA ∨∨∨⇔∃ 会求谓词公式的真值，量词的辖域，自由变元、约束变元，以及换名规则、代入规则等．掌握谓词演算的等价式和重言蕴含式．并进行谓词公式的等价演算．8．了解前束范式的概念，会求公式的前束范式的方法.若一个谓词公式F 等价地转化成B x Q x Q x Q k k ...2211，那么B x Q x Q x Q k k ...2211就是F 的前束范式．前束范式仍然是谓词公式．9．了解谓词逻辑推理的四个规则．会给出推理证明．谓词演算的推理是命题演算推理的推广和扩充，命题演算中基本等价式，重言蕴含式以及P ，T ，CP 规则在谓词演算中仍然使用．谓词逻辑的推理演算引入了US 规则(全称量词指定规则)，UG 规则(全称量词推广规则)，ES 规则(存在量词指定规则)，EG 规则(存在量词推广规则)等.集合论部分1．理解集合、元素、集合的包含、子集、相等，以及全集、空集和幂集等概念，熟练掌握集合的表示方法．具有确定的，可以区分的若干事物的全体称为集合，其中的事物叫元素．集合的表示方法：列举法和描述法.注意：集合的表示中元素不能重复出现，集合中的元素无顺序之分．掌握集合包含(子集)、真子集、集合相等等概念．注意：元素与集合，集合与子集，子集与幂集，空集与所有集合的关系：空集是惟一的，它是任何集合的子集．集合A 的幂集P(A)＝}{A x x ⊆， 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>xA,yB}，是有序对的集合.笛卡儿积也可以多个集合合成，A1×A2×…×An ．5．理解关系的概念：二元关系、空关系、全关系、恒等关系.掌握关系的集合表示、关系矩阵和关系图，掌握关系的集合运算和求复合关系、逆关系的方法． 二元关系是一个有序对集合，},{B y A x y x R ∈∧∈><=，记作xRy ．关系的表示方法有三种：集合表示法，关系矩阵：RA ×B ，R 的矩阵⎪⎪⎭⎫ ⎝⎛==⎪⎩⎪⎨⎧/==⨯n j m i b R a Rb a r r M j i j i ij n m ij R ,...,2,1,...,2,101,)(. 关系图：R 是集合上的二元关系，若<ai, bj>R ，由结点ai 画有向弧到bj 构成的图形．空关系是唯一、是任何关系的子集的关系； 全关系},,{A b a b a E A ∈><=A A ⨯≡； 恒等关系},{A a a a I A ∈><=，恒等关系的矩阵MI 是单位矩阵．关系的集合运算有并、交、补、差和对称差． 复合关系}),,(,{2121R c b R b a b c a R R R >∈<∧>∈<∃><=•=；复合关系矩阵：21R R R M M M ⨯=(按布尔运算)；有结合律：(RS)T ＝R(ST)，一般不可交换． 逆关系},,{1R y x x y R >∈<><=-；逆关系矩阵满足：T R R M M =-1；6．理解关系的性质(自反性和反自反性、对称性和反对称性、传递性的定义以及矩阵表示或关系图表示)，掌握其判别方法(利用定义、矩阵或图，充分条件)，知道关系闭包的定义和求法．注：(1)关系性质的充分必要条件：① R 是自反的；②R 是反自反的；③R 是对称的 ；④R 是反对称的；⑤R 是传递的.(2)IA 具有自反性，对称性、反对称性和传递性．EA 具有自反性，对称性和传递性．故IA ，EA 是等价关系．具有反自反性、对称性、反对称性和传递性．IA 也是偏序关系．7．理解等价关系和偏序关系概念，掌握等价类的求法和作偏序集哈斯图的方法．知道极大(小)元，最大(小)元的概念，会求极大(小)元、最大(小)元、最小上界和最大下界． 等价关系和偏序关系是具有不同性质的两个关系.⎩⎨⎧==+⎭⎬⎫⎩⎨⎧+偏序关系等价关系传递性反对称性对称性自反性 知道等价关系图的特点和等价类定义，会求等价类．一个子集的极大(小)元可以有多个，而最大(小)元若有，则惟一.且极元、最元只在该子集内；而上界与下界可以在子集之外．由哈斯图便于确定任一子集的最大(小)元，极大(小)元．8．理解函数概念：函数(映射)，函数相等，复合函数和反函数．理解单射、满射和双射等概念，掌握其判别方法．函数是一种特殊的关系．集合A ×B 的任何子集都是关系，但不一定是函数．函数要求对于定义域A 中每一个元素a ，B 中有且仅有一个元素与a 对应，而关系没有这个限制．二函数相等是指：定义域相同，对应关系相同，而且定义域内的每个元素的对应值都相同． 函数有：单射——若)()(2121a f a f a a ≠⇒≠；满射——f(A)=B 或,,A x B y ∈∃∈∀使得y=f(x)；双射——单射且满射．复合函数,:,:,:C A f g C B g B A f →→→ 则 即))(()(x f g x f g = ．复合成立的条件是：)(Dom )(Ran g f ⊆．一般g f f g ≠，但f g h f g h )()(=. 反函数——若f ：AB 是双射，则有反函数f －1：BA ，},)(,,{1A a b a f B b a b f ∈=∈><=-，f f g f f g ==-----11111)(,)(重点：关系概念与其性质，等价关系和偏序关系，函数.图论部分1．理解图的概念：结点、边、有向图，无向图、简单图、完全图、结点的度数、边的重数和平行边等.理解握手定理．图是一个有序对<V ，E>，V 是结点集，E 是联结结点的边的集合．掌握无向边与无向图，有向边与有向图，混合图，零图，平凡图、自回路(环)，无向平行边，有向平行边等概念．简单图，不含平行边和环(自回路)的图、在无向图中，与结点v(V)关联的边数为结点度数deg (v)；在有向图中，以v(V)为终点的边的条数为入度deg －(v)，以v(V)为起点的边的条数为出度deg ＋(v)，deg(v)=deg+(v) +deg －(v)．无向完全图Kn 以其边数)1(21-=n n E ；有向完全图以其边数)1(-=n n E ． 了解子图、真子图、补图和生成子图的概念． 生成子图——设图G ＝<V, E>，若EE ，则图<V, E>是<V, E>的生成子图．知道图的同构概念，更应知道图同构的必要条件，用其判断图不同构.重要定理：(1) 握手定理 设G=<V ，E>，有∑∈=V v E v 2)deg(； (2) 在有向图D ＝<V, E>中，∑∑∈+∈-=V v V v v v )(deg )(deg ；(3) 奇数度结点的个数为偶数个．2．了解通路与回路概念：通路(简单通路、基本通路和复杂通路)，回路(简单回路、基本回路和复杂回路)．会求通路和回路的长度．基本通路(回路)必是简单通路(回路)．了解无向图的连通性，会求无向图的连通分支．了解点割集、边割集、割点、割边等概念．了解有向图的强连通强性；会判别其类型．设图G ＝<V ，E>，结点与边的交替序列为通路．通路中边的数目就是通路的长度．起点和终点重合的通路为回路．边不重复的通路(回路)是简单通路(回路)；结点不重复的通路(回路)是基本通路(回路).无向图G 中，结点u, v 存在通路，u, v 是连通的，G 中任意结点u, v 连通，G 是连通图．P(G)表示图G 连通分支的个数．在无向图中，结点集VV ，使得P(G －V)>P(G)，而任意VV,有P （G －V ）＝P(G)，V 为点割集. 若V 是单元集，该结点v 叫割点；边集EE ，使得P(G －V)>P(G)，而任意EE ，有P （G －E ）＝P(G)，E 为边割集．若E 是单元集，该边e 叫割边(桥)．要知道：强连通−−→−必是单侧连通−−→−必是弱连通，反之不成立． 3．了解邻接矩阵和可达矩阵的概念，掌握其构造方法及其应用．重点：图的概念，握手定理，通路、回路以及图的矩阵表示．4．理解欧拉通路(回路)、欧拉图的概念，掌握欧拉图的判别方法．通过连通图G 的每条边一次且仅一次的通路(回路)是欧拉通路(回路)．存在欧拉回路的图是欧拉图.欧拉回路要求边不能重复，结点可以重复．笔不离开纸，不重复地走完所有的边，走过所有结点，就是所谓的一笔画．欧拉图或通路的判定定理(1) 无向连通图G 是欧拉图G 不含奇数度结点(即G 的所有结点为偶数度)；(2) 非平凡连通图G 含有欧拉通路G 最多有两个奇数度的结点；(3) 连通有向图D 含有有向欧拉回路D 中每个结点的入度＝出度．连通有向图D 含有有向欧拉通路D 中除两个结点外，其余每个结点的入度＝出度，且此两点满足deg －(u)－deg ＋(v)＝1．5．理解汉密尔顿通路(回路)、汉密尔顿图的概念，会做简单判断．通过连通图G 的每个结点一次，且仅一次的通路(回路)，是汉密尔顿通路(回路)．存在汉密尔顿回路的图是汉密尔顿图.汉密尔顿图的充分条件和必要条件(1) 在无向简单图G=<V ，E>中，V3，任意不同结点V v u G v u ≥+∈)deg()deg(,,，则G 是汉密尔顿图．(充分条件)(2) 有向完全图D ＝<V ，E>, 若3≥V ，则图D 是汉密尔顿图. (充分条件)(3) 设无向图G=<V ，E>，任意V1V ，则W(G －V1)V1(必要条件)若此条件不满足，即存在V1V ，使得P(G －V!)>V1,则G 一定不是汉密尔顿图(非汉密尔顿图的充分条件)．6．了解平面图概念，平面图、面、边界、面的次数和非平面图．掌握欧拉公式的应用． 平面图是指一个图能画在平面上，除结点之外，再没有边与边相交．面、边界和面的次数)deg(r 等概念．重要结论：(1)平面图e r e E v V E V G r i i2)deg(,,,,1===>=<∑=则． (2)欧拉公式：平面图,,,,e E v V E V G ==>=< 面数为r ，则2=+-r e v (结点数与面数之和＝边数＋2)(3)平面图633,,,,-≤≥==>=<v e v e E v V E V G ，则若．会用定义判定一个图是不是平面图．7．理解平面图与对偶图的关系、对偶图在图着色中的作用，掌握求对偶图的方法． 给定平面图G ＝〈V ，E 〉，它有面F1，F2，…，Fn ，若有图G*＝〈V*，E*〉满足下述条件：⑴对于图G 的任一个面Fi ，内部有且仅有一个结点vi*∈V*；⑵对于图G的面Fi，Fj的公共边ek，存在且仅存在一条边ek*∈E*，使ek*＝(vi*，vj*)，且ek*和ek相交；⑶当且仅当ek只是一个面Fi的边界时，vi*存在一个环ek*和ek相交；则图G*是图G的对偶图．若G*是G的对偶图，则G也是G*的对偶图．一个连通平面图的对偶图也必是平面图．8．掌握图论中常用的证明方法．重点：欧拉图和哈密顿图、平面图的基本概念及判别．9．了解树、树叶、分支点、平凡树、生成树和最小生成树等概念，掌握求最小生成树的方法．连通无回路的无向图是树．树的判别可以用图T是树的充要条件(等价定义)．注意：(1) 树T是连通图；(2)树T满足m＝n－1（即边数=顶点数-1）．图G的生成子图是树，该树就是生成树．每边指定一正数，称为权，每边带权的图称为带权图．G的生成树T的所有边的权之和是生成树T的权，记作W(T)．最小生成树是带权最小的生成树．10．了解有向树、根树、有序树、二叉树、二叉完全树、正则二叉树和最优二叉树等概念．了解带权二叉树、最优二叉树的概念，掌握用哈夫曼算法求最优二叉树的方法．有向图删去边的方向为树，该图为有向树．对非平凡有向树，恰有一个结点的入度为0(该结点为树根)，其余结点的入度为1，该树为根树．每个结点的出度小于或等于2的根树为二叉树；每个结点的出度等于0或2的根树为二叉完全树；每个结点的出度等于2的根树称为正则二叉树．有关树的求法：(1)生成树的破圈法和避圈法求法；(2)最小生成树的克鲁斯克尔求法；(3) 最优二叉树的哈夫曼求法重点：树与根树的基本概念，最小生成树与最优二叉树的求法.代数结构部分1. 二元运算（定义，封闭性）、运算表2.各种定律（交换、结合、幂等、分配、吸收、消去、幺元、零元、逆元）3·代数系统、子代数、积代数（定义、特殊元素、代数常数）4·同态与同构（同态等式、证明）5·半群、独异点6·群、子群、阿贝尔群、生成子群、元素的阶（周期）、循环群（定义与证明）·环、含幺环、零因子、无零因子环、整环、除环与域7·格（两种定义）、分配格、有界格、布尔格（判断）练习题数理逻辑部分（一）1．填空题(1) 公式(p∧⌝q)∨(⌝p∧q)的成真赋值为__________________；(2) 设p, r为真命题，q, s为假命题，则复合命题(p→q)↔(⌝r→s)的真值为________；(3) 设p, q均为命题，在_________________________条件下，p与q的排斥或也可以写成p与q的相容或；(4) 公式⌝(p↔q)与(p∧⌝q)∨(⌝p∧q)共同的成真赋值为____________；(5) 设A为任意的公式，B为重言式，则A∨B的类型为______________.2．将下列命题或语句符号化(1) 7不是无理数是不对的；(2) 小刘既不怕吃苦，又很钻研；(3) 只有不怕困难，才能战胜困难；(4) 只要别人有困难，老王就帮助别人，除非困难解决了；(5) 整数n是偶数当且仅当n能被2整除.3．求复合命题的真值p：2能整除5，q：旧金山是美国的首都，r：一年分四季.(1) ((p∨q)→r)∧(r→(p∧q))；(2) ((⌝q↔p)→(r∨p))∨((⌝p∧⌝q)∧r).4．判断推理是否正确设y=2|x|，x为实数. 推理如下：若y在x=0可导，则y在x=0连续. y在x=0连续. 所以，y在x=0可导.5．判断公式的类型(1) (⌝(p↔q)→((p∧⌝q)∨(⌝p∧q)))∨r;(2) (p∧⌝(q→p))∧(r∧q);(3) (p↔⌝r)→(q↔r).（二）1．填空题．(1)设A为含命题变项p、q、r的重言式，则公式A∨ ((p∧q)→r)的类型为___________；(2)设B为含命题变项p、q、r的矛盾式，则公式B∧((p↔q)→r)的类型为___________；(3)设p、q为命题变项，则(⌝p↔q)的成真赋值为________________；(4)设p、q为真命题，r、s为假命题，则复合命题(p↔r)↔(⌝q→s)的真值为___________；(5)矛盾式的主析取范式为_________________；(6)设公式A含命题变项p、q、r，又已知A的主合取范式为M0∧M2∧M3 ∧M5，则A的主析取范式为_______________________________．2．用等值演算法求公式的主析取范式或主合取范式(1)求公式p→((q∧r)∧(p∨(⌝q∧⌝r)))的主析取范式；(2)求公式⌝(⌝(p→q))∨(⌝q→⌝p)的主合取范式；(3)求公式((p∨q)∧(p→q))↔(q→p)的主析取范式，再由主析取范式求出主合取范式．3．用真值表求公式(p→q)↔r的主析取范式4．将公式p→(q→r)化成与之等值且仅含{⌝, ∧}中联结词的公式．5．用主析取范式判断⌝ (p↔q) 与((p∨q)∧(⌝(p∧q))是否等值．6. 用消解原理证明p∧(⌝p∨q)∧(⌝r) ∧(⌝p∨⌝q∨r)是矛盾式.（三）1．填空题(1)(A→B)∧⌝B⇒_____________为拒取式推理定律；(2) (A∨⌝B)∧B⇒______________为析取三段论推理定律；(3) (⌝A→B)∧(B→⌝C)⇒_________________为假言三段论推理定律；(4) (⌝A→⌝B)∧⌝A⇒________________为假言推理定律．2．判断推理是否正确，并证明之（方法不限）(1)如果王红学过英语和法语，则她也学过日语．可她没有过日语，但学过法语. 所以，她也没学过英语；(2)若小李是文科学生，则他爱看电影．小李不是文科学生. 所以, 他不爱看电影．（3）设y=2|x|，x为实数. 推理如下：若y在x=0可导，则y在x=0连续. y在x=0连续. 所以，y在x=0可导.3．在自然推理系统P中，用直接证明法构造下面推理的证明(1)前提：⌝(p∧⌝q), q→⌝r, r结论：⌝p(2)前提：p→r, q→s, p,q结论：r∧s4．在自然推理系统P中，用附加前提证明法证明下面推理．(1)前提：⌝p∨ (q→r), s→p, q结论：⌝r→⌝s(2)前提：⌝p→q, ⌝p∨r, q→s结论：⌝s→r5．在自然推理系统P中，用归谬法证明下面推理．前提：p→(q→r), p∧q结论：r∨s6．在自然推理系统P中，构造下面用自然语言给出的推理．若小张喜欢数学，则小李或小赵也喜欢数学．若小李喜欢数学，则他也喜欢物理．小张确实喜欢数学，可小李不喜欢物理. 所以, 小赵喜欢数学．（四）1.填空题2.(1) 设F(x)：x具有性质F，G(x)：x具有性质G. 命题“对所有的x而言，若x有性质F，则x就有性质G”的符号化形式为__________________________；(2) 设F(x)：x具有性质F，G(x)：x具有性质G. 命题“有的x既有性质F、又有性质G”的符号化形式为__________________________；(3) 设F(x)：x具有性质F，G(y)：y具有性质G. 命题“若所有的x都有性质F，则所有的y都有性质G”的符号化形式为__________________________；(4) 设F(x)：x具有性质F，G(y)：y具有性质G. 命题“若存在x具有性质F，则所有的y都没有性质G”的符号化性质为__________________________；(5) 设A为任意的一阶逻辑公式，若A中_________________，则称A为封闭的公式；(6) 在一阶逻辑中将命题符号化时，若没指明个体域，则使用________________个体域.2. 用0元谓词将下列命题符号化(1) 只要4不是素数，3就是素数；(2) 只有2是偶数，4才是偶数；(3) 5是奇数当且仅当5不能被2整除.3. 在一阶逻辑中将下列命题符号化(1) 所有的整数，不是负整数，就是正整数，或者是0；(2) 有的实数是有理数，有的实数是无理数；(3) 发明家都是聪明的并且是勤劳的．王前进是发明家. 所以, 王前进是聪明的并且是勤劳的．4．在一阶逻辑中，将下列命题符号化(1) 实数不都是有理数；(2) 不存在能表示成分数的无理数．5．在一阶逻辑中，将下列命题符号化(1) 若x与y都是实数且x>y，则x+2>y+2；(2) 不存在最大的自然数．6．证明题(1) 证明∀x(F(x)→G(x))∧∃y(H(y)∧⌝R(y))为可满足式、但不是永真式；(2) 证明(∀xF(x)∨∃yG(y))∧⌝∃yG(y) →∀xF(x)为永真式．（五）1．填空题．(1) ⌝∃x∀yF(x,y)的前束范式为_______________________；(2)由量词量词分配等值式，∃x(A(x)∨B(x))⇔________________；(3) 缩小量词的辖域, ∀x(F(x)→B)⇔ ________________；(4)公式((∀y⌝G(x)∧∀xF(x))∧∃yG(y))→∀xF(x)的类型为_____________________；(5)取解释I为：个体域为D={a}，F(x)：x具有性质F，在I下∀xF(x)↔∃xF(x)的真值为_________；(6)前提：∀x∃yF(x,y)结论：∃yF(y,y)以上推理是错误的，某学生却给出了如下证明：①∀x∃yF(x,y) 前提引入②∃yF(y,y) ①∀-此证明错在_____________________．2．在有限个体域内消去量词．(1)个体域D={1,2,3}，公式为∀x∀y(F(x)→G(y))(2)个体域D={a,b}，公式为∀x∃y(F(x,y)→G(y,x))3．求前束范式．(1)∀x(F(x,y)→∀y(G(x,y)→∃zH(x,y,z)))；(2) (∃xF(x,y)→∀yG(x,y,z))→∃zH(z).4．在自然推理系统N L中，构造下面推理的证明．(1)前提：∀x∀y(F(x)→G(y)), F(a)结论：∃xG(x)(2)前提：∀x(F(x)→∀y(G(y)∧H(x))), ∃xF(x)结论：∃x(F(x)∧G(x)∧H(x))5．在自然推理系统F中，构造下面用自然语言描述的推理．火车都比汽车快，汽车都比轮船快，a是火车，b是汽车，c是轮船．所以，a比b快，b比c快．（六）1. 填空题(1) 设A={2,a,{3},4}, B={∅, 4,{a},3}，则A⊕B=______________________________；(2) 设A={{{1,2}},{1}}，则P(A)=__________________________________________；(3) 设X,Y,Z为任意集合，且X⊕Y={1,2,3}, X⊕Z={2,3,4}，若2∈Y, 则一定有_______；A. 1∈ZB. 2∈ZC. 3∈ZD. 4∈Z(4) 下列命题中为真的是________________________________________________；A. {a,{b}}∈{{a,{b}}}B. ∅∈P(⋃{∅,{∅}})C.{a}⊆X⇔a∈XD. X⋃Y=Y⇔X=∅E. X-Y=X⇔X⊆~Y(5) 设[0,1]和(0,1)分别表示实数集上的闭区间和开区间，则下列命题中为真的是_____________________________________；A. {0,1}⊆ (0,1)B. {0,1}⊆ [0,1]C. (0,1)⊆[0,1]D. [0,1]⊆QE. {0,1}⊆Z(6) 设[a,b], (c,d)代表实数区间，那么([0,4]⋂[2,6])-(1,3)=_________________________.2. 简答题(1) 设E={1,2,...,12}，A={1,3,5,7,9,11}, B={2,3,5,7,11}，C={2,3,6,12}, D={2,4,8}，计算：A⋃B, A⋂C, C-(A⋃B), A-B, C-D, B⊕D.(2) 设A={{a},{a,b}}, 求⋃A, ⋂A, ⋃⋃A-⋂⋃A.(3) 设A, B, C为集合，判断下列集合等式是否为恒等式，并说明理由.(A⋃B⋃C)-(A⋃B) = C, A-(B-C) = (A-B) - (A-C)(4) 找出下列集合等式成立的充分必要条件, 并简单说明理由.(A-B)⊕(A-C)=∅3. 证明题(1) A⊆B⇒C-B⊆C-A；(2) A⋃B=E⇔~A⊆B⇔~B⊆A.4. 应用题（1）一个学校有507, 292, 312和344个学生分别选了微积分、离散数学、数据结构或程序设计语言课，且有14人选了微积分和数据结构课，213人选了微积分和程序设计语言课，211人选了离散数学和数据结构课，43人选了离散数学和程序设计语言课，没有学生同时选微积分和离散数学课，也没有学生同时选数据结构和程序设计语言课。

离散数学复习提纲（代数系统）1．（1）相等关系显然是所有代数结构上的同余关系. 同余关系是相等关系的推广。

（2）同余关系也是模k相等关系（数论中也称模k同余关系）的推广。

可证模k相等关系是如上定义的关于整数加、乘运算的同余关系。

设整数x,y,u,v满足x＝y（mod k）, u＝v（mod k）,那么x –y = nk,u –v = mk(n,m 为整数),于是(x+u) – (y+v) = (n+m)k故x+u = y+v（mod k）。

为证 xu＝yv（mod k），将 x = y+nk与u = v+mk两边分别相乘,于是有xu – yv = ymk+vnk+nmk2xu – yv = (ym+vn+nmk)k由于ym+vn+nmk 为整数，xu＝yv（mod k）得证。

模k相等关系关于减运算和一元减运算（添负号运算）也是同余关系，请读者自行验证。

2．设<G，*>为群,G中元素a的阶为k,那么,a n = e当且仅当k整除n .证先证充分性．设 a k ＝ e，k整除n，那么n = kr（r为整数），因为a k ＝ e，所以a n = a kr = (a k )r = e r = e 。

再证必要性．设 a n ＝ e，n = mk＋ r，其中m为n除以 k的商，r为余数，因此0≤ r＜k 。

于是e＝a n＝a mk+r＝a mk*a r＝a r因此,由k的最小性得r = 0，k整除n ．3．有限群G的每个元素都有有限阶,且其阶数不超过群G的阶数| G | .证设a为G的任一元素,考虑 e = a0 ,a1 ,a2 , … ,a│G│这| G |+1个G中元素.由于G中只有| G |个元素,因此它们中至少有两个是同一元素,不妨设a r = a s(0 ≤ r < s ≤ | G | )于是a s-r = e,因此a有有限阶,且其阶数至多是s-r,不超过群G的阶数| G | .4．设<G，*>为群，a为G中任一元素，那么a与a-1具有相同的阶．证只要证 a具有阶n当且仅当a-1具有阶n 。

离散数学期末复习提纲一、基本概念:1.数理逻辑中使用哪8条推理规则?其中哪几条规则的使用是有条件限制的?2.把实际问题符号化时,全称量词对应哪个逻辑连接词?存在量词对应哪个逻辑连接词?3.一个谓词公式一经量化就是一个确定的命题,假设个体域为S={1，2，3，⋯}如何确定(∀x)A(x)和（∃x）A(x)的真值？4.何为极小项(极大项)?极小项(极大项)一定是基本积(基本和)吗?5.何为判定问题?解决判定问题的途径是什麽?6.对偶式和对偶原理相同吗?7.一个谓词公式的前束范式具有什麽样的结构?8.⎨⌝,∧,∨⎬是最小功能完备集吗？为什麽？9.设A和B为任意两个集合，A⨯B一定是二元关系吗？10.一个关系可能具有哪些性质？每种性质的形式化描述如何？11.如何从一个关系的关系矩阵来判断其性质？在关系上可以进行哪些运算？12.R*和R+的意义各是什麽？13.我们都介绍了哪些特种关系？它们的形式化定义是什麽？14.划分和什麽关系相对应？覆盖和什麽关系相对应？15.盖复和覆盖是同一个概念吗？什麽关系使用哈斯图？画哈斯图时用到什麽概念？16.极大员、极小员、最大员、最小员和上界、下界、上确界、下确界定义的根本区别在哪里？17.是关系一定是函数，是函数一定是关系这两句话哪一句是正确的？18.一个关系若存在，则其逆关系一定存在；一个函数若存在，则其反函数一定存在这两句话哪一句是正确？19.我们介绍了哪些特种函数？20.当一个函数满足什麽条件时，就是运算？一个零元运算又叫集合X中的特异元素，我们介绍了哪些特异元素？21.两个无限集通过什麽方法比较大小？22.何为两个代数系统的同态，同构？23.何为同余关系？一个同余关系会造成一个集合的商集，一个商集一定是原集合的覆盖吗？24.何为群？寻找子群的Laglangre定理？25.何为格？何为布尔代数？一个元素的补元唯一吗？如果存在一个元素没有补元，还能构成格吗？26.何为图（指图的抽象数学定义）？图的度？d度正则图指的是有向图还是无向图?何为路径?从V i到Vj可达，从Vj到V i一定可达吗？强连通，单向连通，弱连通是指有向图还是指无向图而言？何为一个结点的可达集？设图的邻接矩阵为A，A中行上1的个数，列上1的个数各代表什麽含义？A²和A'²'中的元素含义各是什麽？何为欧拉图？何为哈密顿图？是哈密顿路一定是欧拉路，是欧拉路一定是哈密顿路，这两句话哪一句正确？二元树和二叉树的概念相同吗？什麽是叶加权最优二叉树？公式∑W(V)∙L(v)中各参数的含义是什麽？v∈V27.遍历二叉树有几种方法？二．能够熟练解决以下问题：1．命题逻辑中通过求主范式进行判定的问题。

离散数学复习提纲集合论一、基本概念集合(set)：做为整体识别的、确定的、互相区别的一些对象的总体。

规定集合的三种方式：列举法、描述法、归纳法集合论的三大基本原理外延公理：两个集合A和B相等当且仅当它们具有相同的元素（无序性）概括公理：对于任意个体域U，任一谓词公式P都确定一个以该域中的对象为元素的集合S（确定性）正规公理：不存在集合A1,A2,A3,…使得…∈A3∈A2∈A1（有限可分，集合不能是自己的元素）注意：隶属、包含的判断（有时两者兼有）定理1：对于任意集合A和B，A=B当且仅当A ? B且B ? A传递性，对全集、空集的?关系等定理5：空集是唯一的子集、真子集、子集个数等运算：并、交、补、差、幂集，及一些运算性质、公式幂集：对任意集合A，ρ(A)称作A的幂集，定义为：ρ(A)={x|x?A}，所有子集的集合设A,B为任意集合，A A B当且仅当ρ(A) ?ρ(B)集合族：如果集合C中的每个元素都是集合，称C为集合族集合族的标志集：如果集合族C可以表示为某种下标的形，C={Sd|d∈D}，那么这些下标组成的集合称作集合族C的标志集广义并、广义交，及相关运算性质、公式归纳定义：基础条款：规定某些元素为待定义集合成员，集合其它元素可以从基本元素出发逐步确定归纳条款：规定由已确定的集合元素去进一步确定其它元素的规则终极条款：规定待定义集合只含有基础条款和归纳条款所确定的成员基础条款和归纳条款称作“完备性条款”，必须保证毫无遗漏产生集合中所有成员终极条款又称“纯粹性条款”，保证集合中仅包含满足完备性条款的那些对象例：自然数的归纳定义、数学归纳法等……（建议看一下课件例子了解一下思路）二、关系有序组（二元）：设a,b为任意对象，称集合族{{a},{a,b}}为二元有序组，简记为称a为的第一分量，b为第二分量递归定义：n=2时，={{a1},{a1,a2}}n>2时，=<< a1,…,an-1>, an>集合的笛卡儿积：对任意集合A,A2,…,A，A1×A2称作集合A1，A2的笛卡儿积，定义如下：A1×A2 = { | u∈A1,v∈A2}A1×A2×…×An =(A1×A2×…×An-1) ×An定理：对于任意有限集合A1,…,An，有|A1×…×An|=|A1|*…*|An|一些运算性质关系是各个对象之间的联系和对应R称为集合A1,A2,…,An-1到An的n元关系，如果R是A1×A2×…×An的一个子集。

一、数理逻辑（第1章、第2章）·命题定义、联结词（与、或、非、单条件、双条件）·命题公式、真值、真值表、符号化·谓词、量词（全称、存在）、谓词公式·一阶逻辑符号化（所有的。

是。

，、和有些。

是。

特性谓词）·谓词公式求真值（在某种解释下）·命题公式的等值（等价）演算（十大定律）·命题公式的主范式·谓词公式的前束范式·命题逻辑应用·命题逻辑推理（推理定律、推理规则：P，T，CP）·谓词逻辑推理（推理定律、推理规则：P，T，CP，UI，EI,UG,EG）····························二、集合论（第3章）·集合的定义与表示方法（解析法、枚举法、文氏图法）·集合间的相互关系（定义，符号：⊆⊂ =）·集合的运算定义与图示（⋂⋃ - ~⊕⨯ P / ）——入集条件·集合定律（十大定律）·集合恒等式的证明法一：直接利用定律及已证等式法二：利用集合相等的定义（①左⊆右∧右⊆左②x∈左⇔ x∈右）·集合的元素计数与应用（包容排斥原理）·································三、关系论（第4章）·二元关系的定义及其表示（解析法、集合法、图示法、矩阵法）·关系的运算（集合的所有运算+左复合、求逆、求闭包）·关系的性质（定义、关系图特点、矩阵的特点、证明）·等价关系（定义、等价类、上集、划分）·偏序关系与偏序集（定义、哈斯图）·全序集（线序集、定义、最元、极元、界元、确界）·································四、函数论（第4章）·定义（唯一性）·A到B的函数（唯一性、良定性）·特殊函数（常、恒等、单增、单减、特征、自然映射）·BA的计数·函数的性质（单、满、双，判断）·函数的复合（左复合）·反函数（只有双设才有）·······························五、代数系统（第5章、第6章）·二元运算（定义，封闭性）、运算表·各种定律（交换、结合、幂等、分配、吸收、消去、幺元、零元、逆元）·代数系统、子代数、积代数（定义、特殊元素、代数常数）·同态与同构（同态等式、证明）·半群、独异点·群、子群、阿贝尔群、生成子群、元素的阶（周期）、循环群（定义与证明）·环、含幺环、零因子、无零因子环、整环、除环与域·格（两种定义）、分配格、有界格、布尔格（判断）·······························六、图论（第7张、第8张、第9张）·无向图、有向图、零图、平凡图、完全图、子图、生成子图、补图·第一握手定理、度数序列·通路、回路、简单。

第一部分数理逻辑第一章命题逻辑重点：●熟练掌握联结词的定义；●掌握数理逻辑中命题的翻译及命题公式的定义；●熟记基本的等价公式和蕴涵公式；●利用真值表技术和公式法求公式的主析取范式和主合取范式；●熟练掌握应用基本推理方法完成命题逻辑推理：1.直接证法2.反证法3.CP规则难点：●如何正确地掌握对语言的翻译；●如何利用推理方法正确的完成命题推理。

第二章谓词逻辑重点：●谓词、量词、个体域的概念；●谓词逻辑中带量词命题的符号化；●熟记基本的谓词等价公式；●求公式的前束范式；●掌握谓词逻辑的推理规则以及能够熟练地完成一阶逻辑推理；难点：●谓词逻辑中带量词命题的符号化；●如何利用推理方法正确地完成一阶逻辑推理。

第二部分集合论第三章集合与关系重点：●掌握集合的五种基本运算和集合相等的证明方法；●幂集的概念以及和子集的关系；●序偶和笛卡尔积的概念；●关系定义及其和笛卡尔积之间的联系；●关系的复合；●关系的五种性质及其判断和证明；●关系的闭包；●等价关系定义、证明及其与等价类、集合的划分间的关系；●偏序关系的定义和证明，哈斯图；●偏序关系中的特殊元素；难点：●如何正确证明集合之间包含和相等关系；●如何正确地理解和判断关系的性质；●非常重要的关系性质的证明方法——按定义证明法；●如何正确地掌握等价关系及相应的等价类与集合划分之间的关系；●如何正确地理解和判断偏序关系中的八种特殊元素。

第四章函数重点：●能够判定某个二元关系是否是函数；●几种特殊的函数：满射，单射，双射；难点：●如何正确地判断三种特殊函数。

第三部分代数结构重点：●理解代数结构的构成和研究方法；●代数结构中运算的性质以及特殊元素；●广群⇒半群⇒独异点⇒群；●群的定义与性质；●环与域的判断和证明；●格的两种定义；●特殊格：分配格、有界格、有补格、有补分配格；●有补分配格与布尔代数之间的联系；难点：●循环群的判断和证明；●如何正确理解由偏序关系定义的格与由代数系统定义格之间的关系和区别；●如何正确理解布尔代数的概念。

《离散数学》复习大纲本说明包括以下部分：考核说明及实施要求考核内容和要求第一部分集合论第二部分数理逻辑第三部分图论第四部分代数结构第一部分集合论（集合和二元关系）一、集合[考核知识点]集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集集合的交、并、差、补等运算及其运算律（交换律、结合律、分配律、吸收律、 De Morgan律等），文氏（Venn）图序偶与迪卡尔积[考核要求]理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。

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

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

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

二、二元关系[考核知识点]关系、关系矩阵与关系图复合关系与逆关系关系的性质（自反性、对称性、反对称性、传递性）关系的闭包（自反闭包、对称闭包、传递闭包）等价关系与等价类[考核要求]理解关系的概念：二元关系、空关系、全关系、恒等关系；掌握关系的集合表示、关系矩阵和关系图、关系的运算。

掌握求复合关系与逆关系的方法。

理解关系的性质（自反性、对称性、反对称性、传递性），掌握其判别方法（定义、矩阵、图） 掌握求关系的闭包 （自反闭包、对称闭包、传递闭包）的方法。

理解等价关系的概念，掌握等价类的求法。

理解单射、满射、双射等概念，掌握其判别方法。

三、 典型题第一章 集合1. 设A=∅, B={∅,a,{a}},求P(A)和P(B).2. 设A={1,2,3,4} , B={a,b,c}, 求A ⨯B 和B ⨯A.3. P21: 84. P22: 125.证明：B A B A =-6.思考题 P29： 15， 16第二章 关系1. 设A=｛1，2，3，4｝，A 上的关系R={(1,1), (1,2), (1,3), (1,4), (2,2), (2,4),(3,4)}, S=={(2,1), (1,2), (2,3), (1,4), (2,2), (2,4),(4,4)}, 求（1） R 和S 的关系图和关系矩阵（2） R-S（3） S R 1-（4） S R ⊕（5） A 上的恒等关系I A2. 设A=｛a ，b ，c ｝，R 是A 上的关系R=｛(a,a),(a,c),(c,b)｝, 求 ∞=1n n R3. 设R 是A 上的关系，请叙述R 具有自反性，反自反性，对称性，反对称性和传递性的含义4. 设A=｛1，2，3，4，5｝，A 上的关系R=｛(a,b)|a-b 是偶数｝，求R ，判断R 具有的性质。