离散数学期末复习完全手册

离散数学·期末复习完全手册涵盖数理逻辑/集合论/关系/函数/代数系统/图论｜50道选择题·可直接打印一、考试题型与分值分布（通用）题型题量分值主要考查范围策略选择题15-20题20-30分命题公式类型、集合运算、关系性质、代数系统性质、图的基本概念熟记定义，注意反例填空题10-15题10-15分主析取/主合取范式、哈斯图关键元素、欧拉/哈密顿图条件、树的边数公式牢记经典结论和公式判断题10题10分性质判断（等价关系、函数类型、格的性质等）精确理解定义简答题/证明题4-5题20-30分等值演算、关系闭包构造、函数性质证明、群/格的性质、图的矩阵表示、平面图欧拉公式分步推演，逻辑严密计算/应用题2-3题15-25分真值表与范式、集合计数（容斥原理）、关系图与闭包、最短路径与最小生成树、图着色、哈夫曼树按步骤解答二、数理逻辑速查2.1命题逻辑基本概念概念说明命题具有确定真值的陈述句命题常项真值确定的命题（T/1或F/0）命题变项真值可变的命题变量联结词优先级¬最高，∧∨其次，→↔最低2.2常见逻辑联结词真值表pq¬pp∧qp∨qp→qp↔q0010011011011010001001101111特别注意：p→q仅在p真q假时为假。2.3命题公式类型类型定义重言式（永真式）对所有指派均为真矛盾式（永假式）对所有指派均为假可满足式至少存在一组真值指派使其为真2.4等值演算与范式基本等值式：双重否定律、德摩根律、分配律、吸收律等。

主析取范式：极小项（简单合取式，每个变元必出现一次）之析取。

主合取范式：极大项（简单析取式，每个变元必出现一次）之合取。2.5推理规则常用的推理规则：假言推理、拒取式、析取三段论、附加律、化简律等。

推理证明方法：真值表法、等值演算法、自然推理系统（CP规则/附加前提法等）。三、集合论速查3.1集合基本概念概念定义/符号属于a∈A子集A⊆B⇔∀x(x∈A→x∈B)真子集A⊂B⇔A⊆B∧A≠B幂集P(A)={X|X⊆A}，元素个数2|A|3.2集合运算运算符号定义并集A∪B{x|x∈A∨x∈B}交集A∩B{x|x∈A∧x∈B}差集A−B{x|x∈A∧x∉B}补集~A相对于全集E：E−A对称差A⊕B(A−B)∪(B−A)3.3容斥原理（包含排斥原理）|A∪B|=|A|+|B|−|A∩B|推广到三个集合：

|A∪B∪C|=|A|+|B|+|C|−|A∩B|−|A∩C|−|B∩C|+|A∩B∩C|四、二元关系与函数速查4.1关系的定义从A到B的二元关系R是A×B的子集。若A=B，称R是A上的关系。4.2关系的表示集合表达式（列举序偶）、关系矩阵、关系图。4.3关系的性质（重要）性质定义关系图特征自反性∀x∈A,(x,x)∈R每个结点有自环反自反性∀x∈A,(x,x)∉R每个结点无自环对称性(x,y)∈R⇒(y,x)∈R边成对出现反对称性(x,y)∈R∧(y,x)∈R⇒x=y两不同结点间至多一条边传递性(x,y)∈R∧(y,z)∈R⇒(x,z)∈R若x到y有边，y到z有边，则x到z有边4.4关系的运算运算定义/符号逆关系R−1={(y,x)|(x,y)∈R}复合R∘S={(x,z)|∃y((x,y)∈R∧(y,z)∈S)}幂Rn=Rn−1∘R4.5关系的闭包自反闭包r(R)=R∪IA；对称闭包s(R)=R∪R−1；传递闭包t(R)=R∪R2∪R3∪...（可用Warshall算法）。4.6等价关系与序关系等价关系：自反+对称+传递。产生等价类和划分。

偏序关系：自反+反对称+传递。(A,≼)称为偏序集。

哈斯图：去除自环和传递边，箭头上指。

特殊元素：最大元、最小元、极大元、极小元、上/下界、上/下确界。

全序关系：偏序+任意两元素可比。4.7函数函数（映射）：特殊的关系，每个x对应唯一的y。

单射：x₁≠x₂⇒f(x₁)≠f(x₂)；满射：ran(f)=B；双射：既单射又满射（一一对应）。五、代数系统速查5.1基本概念概念定义二元运算封闭任意a,b∈A，运算结果仍在A中结合律(a*b)*c=a*(b*c)交换律a*b=b*a单位元ee*a=a*e=a零元θθ*a=a*θ=θ逆元对a，存在b使a*b=b*a=e5.2半群与群半群：运算满足结合律。独异点（幺群）：含单位元的半群。群：每个元素都有逆元的独异点。

交换群（阿贝尔群）：满足交换律的群。

子群判定：非空子集H满足∀a,b∈H有a*b−1∈H。5.3格与布尔代数格：偏序集<L,≼>中任意两元素都有最小上界（∨）和最大下界（∧）。

分配格：满足分配律的格。有补格：有全界且每元素至少有一补元。

布尔代数：有补分配格。六、图论速查6.1图的基本概念术语定义无向图G=<V,E>V为非空顶点集，E为边集（无序偶）有向图D=<V,E>E为弧集（有序偶）阶图的顶点数度d(v)无向图：关联的边数，握手定理：∑d(v)=2|E|出度/入度有向图：出边数/入边数通路/回路顶点边交替序列连通性任意两点有路径则连通6.2图的矩阵表示邻接矩阵A：aij=1若vi与vj相邻。

可达矩阵P：pij=1若vi可达vj。6.3特殊图图类型定义/条件完全图Kn每对顶点间都有边，边数n(n−1)/2二部图顶点集可划分V₁,V₂，所有边连接V₁与V₂欧拉图存在欧拉回路（经过每条边恰一次）。充要：连通且所有顶点度为偶数哈密顿图存在哈密顿回路（经过每个顶点恰一次）。充分条件：Ore定理d(u)+d(v)≥n树连通无回路。|V|=n,|E|=n−1平面图能画在平面上边不交叉。欧拉公式：n−m+r=26.4图的应用算法最小生成树：Prim或Kruskal。最短路径：Dijkstra（权非负）。拓扑排序：DAG的线性序。着色：图的点着色。七、高频选择题题库（50题完整版）模块一：数理逻辑（1-8题）#题目ABCD答案1命题公式(p→q)∧p的类型是重言式矛盾式可满足式等值式C2p→q的等价式是¬q→¬p¬p∨q¬p∧qp∧¬qB3下列联结词中优先级最高的是∧∨→¬D4"如果下雨则带伞"符号化为（p:下雨,q:带伞）p∧qp∨qp→qq→pC5(¬p∧q)∨(p∧¬q)等价于p↔qp⊕qp→qq→pB6命题公式p∨(q∧r)的对偶式为p∧(q∨r)p∨(q∧r)¬p∧(¬q∨¬r)¬p∨(¬q∧¬r)A7含n个命题变元的极小项个数为nn²2nn!C8(p→q)∧(q→r)→(p→r)是永真式永假式可满足式非命题A模块二：集合（9-15题）#题目ABCD答案9设A={1,2}，幂集P(A)的元素个数是2341C10设A={1,2},B={2,3}，则A−B={1}{2}{3}{1,3}A11容斥原理|A∪B|=|A|+|B||A|+|B|−|A∩B||A∩B||A|−|B|B12A⊕B表示A∪BA∩B(A−B)∪(B−A)(A∪B)−(A∩B)C13空集是任何集合的子集对错仅对有限集仅对无限集A14设|A|=m,|B|=n，从A到B的二元关系个数为mnm+n2mnnmC15集合A={∅}的幂集P(A)为{∅}{∅,{∅}}{{∅}}∅B模块三：关系与函数（16-25题）#题目ABCD答案16设R是A上的小于等于关系，则R具有自反、对称、传递自反、反对称、传递反自反、反对称对称、传递B17等价关系必满足自反、对称、反对称反自反、对称、传递自反、对称、传递反对称、传递C18哈斯图表示的是等价关系偏序关系函数逆关系B19f(x)=x²（R→R）是单射非满射满射非单射双射既非单射也非满射D20传递闭包可通过什么算法求解DijkstraWarshallPrimKruskalB21R={<1,1>,<2,2>,<3,3>,<1,2>}不具有自反性对称性反对称性传递性B22恒等关系IA具有的性质是自反、对称、传递反自反、对称自反、反对称对称、传递A23自然数集N上的小于关系是自反反自反对称等价B24若f(a)=f(b)⇒a=b，则f是满射单射双射恒等映射B25等价关系产生的等价类构成集合的覆盖划分子集幂集B模块四：代数系统（26-33题）#题目ABCD答案26群中元素的逆元一定存在且唯一不一定存在存在多个只对单位元存在A27在格中，a∨b表示a和b的最大下界a和b的最小上界补元零元B28布尔代数要求有补分配格有补格分配格半群A29整数加法群属于半群独异点交换群环C30子群判定：∀a,b∈H，必须有a*b∈Ha*b−1∈Ha−1∈Hb*a∈HB31群中单位元不一定存在可能不唯一存在且唯一与零元相同C32格中∨和∧满足仅结合律仅交换律结合律、交换律、吸收律分配律C33模6加法群Z6中元素4的逆元是4210B模块五：图论（34-45题）#题目ABCD答案34握手定理指出度数和等于顶点数边数2倍边数2倍顶点数C35n个顶点的树边数为nn−1n+12nB36欧拉图的充要条件是所有顶点度数为偶数所有顶点度数为奇数连通且所有顶点度数为偶数有哈密顿回路C37平面图欧拉公式n−m+r=1230B38Dijkstra算法求解的是最小生成树最短路径拓扑排序最大流B39连通图的最小生成树唯一可能不唯一不存在一定有回路B40Kn中每个顶点的度是nn−12nn(n−1)/2B41完全二部图K3,3的边数为69123B42哈密顿图的一个充分条件是连通欧拉图d(u)+d(v)≥n（不相邻）度均为偶数C43二部图的充要条件是含奇度点不含奇圈不含偶圈无回路B44Kruskal算法选择边的原则是每次选权值最小且不构成回路每次选与当前树相连的最小权边随机选边从最长边开始A45无向树中任意两顶点间存在多条通路唯一通路无通路两条通路B模块六：综合（46-50题）#题目ABCD答案46命题公式的主析取范式与主合取范式之间互相对偶互为否定等价无关系B47格的哈斯图中，某元素上方无其他元素，则为最大元极大元最小元上界B48K5是否为平面图是不是取决于画法不确定B49一棵完全二叉树有n个叶子，内部结点数为nn−12nn+1B50偏序集中，若存在上界且所有上界有最小元，则称此元为最小元上确界最大元极大元B八、填空题高频考点（直接背诵）1.命题公式p∨¬p是________式。重言（永真）2.集合A有3个元素，其幂集元素个数为________。8（2³）3.设|A|=m,|B|=n，从A到B的二元关系有________个。2mn4.等价关系产生的等价类构成集合的________。划分5.偏序关系的哈斯图中箭头指向________。上方6.群必须满足：结合律、存在单位元、________。每个元素有逆元7.格中保联运算∨满足________律和结合律。交换8.n个顶点的无向完全图边数为________。n(n−1)/29.握手定理：无向图中所有顶点度数之和等于________。2×边数10.树的顶点数n与边数m的关系为________。m=n−111.欧拉图的充要条件是：连通且所有顶点度数为________。偶数12.平面图满足欧拉公式n−m+r=________。213.传递闭包的Warshall算法时间复杂度为________。O(n³)14.复合关系R∘S中，(x,z)∈R∘S当存在y使得(x,y)∈R且________。(y,z)∈S15.f是单射当且仅当f(a)=f(b)⇒________。a=b16.容斥原理|A∪B∪C|=Σ|A|−Σ|A∩B|+________。|A∩B∩C|17.极小项是每个变元必须出现________次的简单合取式。一18.子群判定定理：H⊆G，H非空，∀a,b∈H有ab−1∈________。H19.二部图的边数等于________之和。两端顶点度数20.任何图中奇度顶点个数为________。偶数九、判断题速记（20题）#题目答案1命题公式(p→q)∧(q→r)→(p→r)是永真式。对2集合{1,2,3}与{3,1,2}不相等。错3空集是任何集合的子集。对4关系R是自反的当且仅当IA⊆R。对5对称关系的关系矩阵是对称矩阵。对6等价关系一定有传递性。对7偏序关系中任意两个元素都可比。错8函数必须是一对一的。错9群中单位元是唯一的。对10半群中每个元素必有逆元。错11格中∨和∧运算相互满足分配律。错12树至少有两个叶子（n≥2时）。对13无向连通图若所有顶点度均为偶数，则是欧拉图。对14哈密顿图一定存在欧拉回路。错15平面图至少有一个顶点度数不超过5。对16最短路径问题可以用Prim算法求解。错17任何图都有生成树。错（必须连通）18完全图K5是平面图。错19布尔代数是特殊的格。对20命题公式主析取与主合取是等值的。错十、名词解释高频考点名词定义命题具有确定真值的陈述句。重言式在所有真值指派下均为真的命题公式。主析取范式由极小项构成的析取式，每个变元在极小项中恰好出现一次。幂集给定集合A的所有子集构成的集合，记为P(A)。等价关系同时满足自反、对称、传递的关系。偏序关系同时满足自反、反对称、传递的关系。群代数系统<G,*>，运算满足结合律，有单位元，每个元素有逆元。格偏序集中任意两个元素都有最小上界和最大下界。欧拉图存在欧拉回路（经过每条边恰一次）的图。树连通且无简单回路的无向图。十一、简答题高频考点速记1.简述五种常用逻辑联结词的真值表及优先级。¬（非）最高，∧（与）、∨（或）次之，→（蕴含）然后，↔（等价）最低。真值表见2.2节。2.什么是关系的闭包？如何构造自反闭包和对称闭包？闭包是包含原关系且具有指定性质的最小关系。自反闭包r(R)=R∪IA；对称闭包s(R)=R∪R−1。3.比较欧拉图与哈密顿图的定义与判定。欧拉图：存在欧拉回路，充要条件是连通且所有顶点度为偶数。哈密顿图：存在哈密顿回路，无充要条件，有充分条件（Ore定理）。4.叙述握手定理及其推论。握手定理：无向图中所有顶点度数之和等于边数的两倍。推论：奇度顶点个数为偶数。5.什么是格？列举格的典型例子。格是一个偏序集，其中任意两个元素都有最小上界（∨）和最大下界（∧）。例：正整数集上的整除关系格，集合代数<P(X),⊆>。十二、计算题示例与公式例1：真值表与范式求(p→q)∧p的主析取范式。答：仅当p=1,q=1时公式为真，主析取范式为p