离散数学概念回顾：课件展示

离散数学概念回顾离散数学是研究离散量的数学分支，是计算机科学的理论基础它研究的对象通常是可数的、非连续的数学结构，如整数、图形和逻辑命题本课件将系统回顾离散数学的核心概念，包括集合论、数理逻辑、关系与函数、图论、树、组合数学、代数结构以及算法与复杂性等八大主题通过这些内容，我们将建立对离散数学体系的完整认识目录集合论1集合的基本概念、表示方法、集合运算、幂集与笛卡尔积数理逻辑2命题逻辑、逻辑连接词、命题公式、等值演算、范式、谓词逻辑关系与函数3关系的基本概念、表示方法、运算与性质、等价关系、偏序关系、函数概念图论与树4图的基本概念与表示、特殊图、欧拉图与哈密顿图、图的着色与匹配、树的概念与性质组合数学与代数结构5计数原理、排列组合、代数系统、群、环、格、布尔代数算法与复杂性6集合论基础概念集合论是数学的基础理论，研究集合及其运算集合是具有某种特定性质的对象的全体，是离散数学的根本概念，为其他数学分支提供了基础工具和语言研究内容集合论研究集合的表示方法、基本运算（如并、交、差、补）、幂集、笛卡尔积等内容，建立了描述集合关系的形式化语言重要性集合论为数学提供了统一的符号系统和语言，是理解其他离散数学概念的基础在计算机科学中，数据结构、数据库理论和人工智能等领域都广泛应用集合论集合的基本概念集合的定义元素集合是具有某种特定性质的对象的全体，记为大写字母（如A、B、构成集合的对象称为该集合的元素，记为小写字母（如a、b、c）C）集合是一个整体概念，其内部结构和元素顺序不重要，只关注若a是集合A的元素，记作a∈A；若a不是集合A的元素，记作元素是否属于该集合a∉A子集空集若集合A的所有元素都属于集合B，则称A是B的子集，记作A⊆B不含任何元素的集合称为空集，记作∅空集是任何集合的子集若A⊆B且A≠B，则称A是B的真子集，记作A⊂B集合中元素的个数称为集合的基数，空集的基数为0集合的表示方法列举法描述法文氏图将集合中的所有元素一一列举出来，用用谓词公式描述集合中元素的共同特用平面上的封闭曲线表示集合，曲线内大括号{}括起来例如A={1,2,3,4,性格式为A={x|Px}，读作A是的点表示集合的元素文氏图直观地展5}表示由数字1到5组成的集合；B={a,使命题Px为真的所有x的集合示了集合间的关系，特别是多个集合的e,i,o,u}表示由英文元音字母组成的集交、并、补等关系例如偶数集E={x|x=2n,n∈N}；合素数集P={x|x1且x只能被1和自身文氏图是理解集合运算的有力工具，在列举法适用于元素个数有限且可以明确整除}描述法适用于难以列举但有明确解决包含多个集合的问题时特别有效列出的集合对于无限集合，可以使用特征的集合它通过图形化方式使抽象的集合概念变省略号表示规律，如自然数集N={0,1,得直观2,3,...}集合运算并集交集差集集合A与B的并集，记为A∪B，集合A与B的交集，记为A∩B，集合A与B的差集，记为A-B或表示属于A或属于B的所有元素表示同时属于A和B的所有元素A\B，表示属于A但不属于B的构成的集合形式化定义构成的集合形式化定义所有元素构成的集合形式化A∪B={x|x∈A或x∈B}并A∩B={x|x∈A且x∈B}若定义A-B={x|x∈A且集操作满足交换律和结合律，A∩B=∅，则称A与B互斥或不x∉B}差集不满足交换律可以推广到多个集合的并集相交补集在给定全集U下，集合A的补集记为A或Ā或U-A，表示属于全集U但不属于A的所有元素构成的集合形式化定义A={x|x∈U且x∉A}补集满足双重否定律A=A幂集与笛卡尔积幂集的定义1集合A的幂集，记为PA或2^A，是由A的所有子集构成的集合形式化定义PA={X|X⊆A}幂集始终包含空集∅和集合A本身幂集的性质2若集合A含有n个元素，则A的幂集PA含有2^n个元素这源于对A中每个元素都有选或不选两种可能，共有2^n种选择方式幂集构成了布尔代数的重要实例笛卡尔积的概念3集合A与B的笛卡尔积，记为A×B，是由所有可能的有序对a,b构成的集合，其中a∈A，b∈B形式化定义A×B={a,b|a∈A且b∈B}笛卡尔积的应用4若集合A含有m个元素，集合B含有n个元素，则A×B含有mn个元素笛卡尔积是定义关系和函数的基础，广泛应用于数据库理论、坐标系统和关系代数等领域数理逻辑研究对象主要分支数理逻辑研究用形式化方法表示和分析包括命题逻辑、谓词逻辑、模态逻辑和1逻辑推理的规则和原理，是数学推理的证明论等，提供了分析数学陈述真假的2基础工具历史发展应用领域4从亚里士多德的三段论发展到现代的符广泛应用于计算机科学、人工智能、电号逻辑，极大地推动了数学的公理化进3子工程和哲学等领域，是形式化思维的程基础命题逻辑命题的定义命题是一个陈述句，具有明确的真值（真或假）命题是命题逻辑的基本研究对象，通常用小写字母p、q、r等表示例如3是素数（真命题）、5是偶数（假命题）简单命题与复合命题简单命题不能被分解为更简单的命题复合命题由简单命题通过逻辑连接词组合而成，如3是素数且5是奇数复合命题的真值取决于其组成部分的真值和逻辑连接词的语义真值表真值表是表示命题公式在所有可能的真值赋值下的真值情况的表格对于含有n个命题变元的公式，真值表有2^n行，对应变元的所有可能取值组合真值表是分析复合命题性质的重要工具逻辑连接词否定合取析取蕴含否定是一元运算，表示非p，记作合取是二元运算，表示p且q，记作析取是二元运算，表示p或q，记作蕴含是二元运算，表示如果p，则¬p或~p当p为真时，¬p为假；当p p∧q仅当p和q都为真时，p∧q才p∨q当p和q至少有一个为真时，q，记作p→q仅当p为真且q为假为假时，¬p为真否定运算可以理解为真；其他情况均为假合取运算对p∨q为真；仅当p和q都为假时，时，p→q为假；其他情况均为真为对命题真值的反转，满足双重否定应自然语言中的并且，需要同时满p∨q才为假析取运算对应自然语言p→q等价于¬p∨q，表示一个条件关律¬¬p≡p足两个条件中的或者，是非排它性的系等价等价是二元运算，表示p当且仅当q，记作p↔q当p和q真值相同时（都为真或都为假），p↔q为真；否则为假等价关系可以理解为双向蕴含p→q∧q→p命题公式合式公式永真式永假式可满足式合式公式是根据语法规则正永真式（重言式）是在任何永假式（矛盾式）是在任何可满足式是至少在某种情况确构成的表达式命题变情况下（任何真值赋值下）情况下都为假的命题公式下（某个真值赋值下）为真项、命题常项是合式公式；都为真的命题公式在真值在真值表中，永假式的最后的命题公式在真值表中，若A是合式公式，则¬A也是表中，永真式的最后一列全一列全部为假可满足式的最后一列至少有合式公式；若A和B是合式公部为真一个真值例如p∧¬p（矛盾律）、式，则A∧B、A∨B、例如p∨¬p（排中律）、p∧q∧¬p都是永假式永假所有非永假式的公式都是可A→B、A↔B也是合式公式p→p（自蕴含）、式表示了逻辑上不可能的情满足式判断公式是否可满p→q↔¬p∨q都是永真况足是计算机科学中的核心问例如p∧q∨r、式永真式表示了命题逻辑题（SAT问题）¬p→q↔r都是合式公式中的普遍规律合式公式是命题逻辑研究的核心对象等值演算等值关系基本等值式若命题公式A与B具有相同的真值表，则称A与B等值，记作A≡B等值关系是命题基本等值式包括双重否定律¬¬p≡p；交换律p∧q≡q∧p，p∨q≡q∨p；结合律逻辑中的等价关系，具有自反性、对称性和传递性等值公式可以在推理过程中相p∧q∧r≡p∧q∧r，p∨q∨r≡p∨q∨r；分配律互替换而不改变整体真值p∧q∨r≡p∧q∨p∧r，p∨q∧r≡p∨q∧p∨r；德摩根律¬p∧q≡¬p∨¬q，¬p∨q≡¬p∧¬q；蕴含等值式p→q≡¬p∨q；等价等值式p↔q≡p→q∧q→p等值演算的应用等值演算的步骤等值演算是推导、化简和证明命题公式性质的重要方法通过基本等值式，可以将等值演算通常采用链式推导，每一步根据某个基本等值式进行变换，并注明使用的复杂公式转化为更简单的等值形式，验证公式的永真性、永假性或可满足性，构造规则例如，证明¬p→q≡p∧¬q¬p→q≡¬¬p∨q≡¬¬p∧¬q≡p∧¬q等值特定形式的等值公式（如范式）演算是命题逻辑的核心推理技术范式范式的概念范式是具有特定结构的命题公式将任意命题公式转换为范式可以简化问题分析，便于系统处理范式是研究命题逻辑的标准化工具，在逻辑电路设计和计算机科学中有重要应用合取范式合取范式CNF是若干个子句的合取，其中每个子句是若干个文字的析取文字是命题变元或其否定形式上，合取范式为L11∨L12∨...∧L21∨L22∨...∧...例如p∨q∧¬p∨r∧¬q∨¬r是合取范式析取范式析取范式DNF是若干个子句的析取，其中每个子句是若干个文字的合取形式上，析取范式为L11∧L12∧...∨L21∧L22∧...∨...例如p∧q∨¬p∧r∨¬q∧¬r是析取范式主合取范式与主析取范式主合取范式PCNF是合取范式的特殊形式，其中每个子句包含所有变元（原形或否定形式）主析取范式PDNF是析取范式的特殊形式，其中每个子句包含所有变元主合取范式与主析取范式可以直接从真值表构造，提供了公式的标准表示谓词逻辑谓词的概念1谓词是关于对象的陈述，表示对象具有的性质或对象之间的关系谓词可以看作是含有变量的命题函数，当变量被赋予确定值时，谓词转变为具有确定真值的命题谓词的表示2n元谓词P表示为Px1,x2,...,xn，其中x1,x2,...,xn是变量例如一元谓词Px可表示x是素数；二元谓词Qx,y可表示x大于y谓词的真值取决于变量取值和定义的关系量词3量词用于表示变量的取值范围全称量词∀（对所有）表示对全部对象均成立；存在量词∃（存在）表示至少存在一个对象使陈述成立量词将谓词转变为命题量词的否定4全称量词和存在量词的否定遵循德摩根律¬∀x Px≡∃x¬Px（并非对所有x都成立P，等价于存在x使P不成立）；¬∃x Px≡∀x¬Px（不存在使P成立的x，等价于对所有x都不成立P）谓词公式谓词公式的构成1原子谓词公式由谓词符号和相应的变元组成复合谓词公式由原子公式通过逻辑连接词（¬、∧、∨、→、↔）和量词（∀、∃）构成，遵循特定的形成规则自由变元与约束变元2在谓词公式中，被量词限制的变元称为约束变元，未被量词限制的变元称为自由变元例如，在公式∀xPx,y中，x是约束变元，y是自由变元谓词公式的解释谓词公式的解释需要指定论域（变量的取值范围）、常元解释和谓词解释不含自由变元的3谓词公式称为谓词句，具有确定的真值闭式与开式不含自由变元的谓词公式称为闭式，具有确定的真值；含有自由变元的4谓词公式称为开式，真值取决于自由变元的取值关系与函数基本概念数学表示关系是对象间联系的数学描述，函数是关系可通过有序对集合、矩阵或图形表1一种特殊的关系，表示输入到输出的映示；函数表示为y=fx，强调一个输入2射规则对应唯一输出应用价值分类与性质4关系和函数是描述现实世界连接的基础关系有自反、对称、传递等性质；函数工具，广泛应用于数学建模和计算机科3分为单射、满射、双射等类型，各有特学点关系的基本概念二元关系关系的定义域关系的值域二元关系R是两个集合A和B的笛卡尔积关系R⊆A×B的定义域是关系R⊆A×B的值域是ranR={b∈B|A×B的子集，表示为R⊆A×B若domR={a∈A|存在b∈B使得存在a∈A使得a,b∈R}，即所有能与Aa,b∈R，则称a与b之间有关系R，记作a,b∈R}，即所有能与B中元素构成关中元素构成关系的B中元素构成的集合aRb当A=B时，R称为集合A上的二元系的A中元素构成的集合关系关系的定义域描述了关系的起点集合关系的值域描述了关系的终点集合，例如，在整数集上，大于关系，表示参与关系的第一分量的全体定表示关系映射的输出结果的全体值={a,b|a,b∈Z且ab}是一种二元关义域可能是A的真子集，表示A中并非所域可能是B的真子集，表示B中并非所有系在学生集合S上，是同班同学也是有元素都参与了关系元素都是某些关系的结果一种二元关系关系的表示方法关系矩阵关系图关系表设A={a₁,a₂,...,aₘ}，关系R⊆A×B可以用二部图表关系可以通过表格形式列出所有B={b₁,b₂,...,bₙ}，关系R⊆A×B示，其中A和B中的元素分别作为有序对a,b∈R这是关系最直可以用m×n的矩阵M_R表示，其两组顶点，若a,b∈R，则在对接的表示方法，适合关系规模较中矩阵元素M_R[i,j]=1当且仅当应顶点间连一条有向边当A=B小时使用在数据库理论中，关a_i,b_j∈R，否则M_R[i,j]=0时，R可表示为有向图，顶点对系表是关系数据库的基础，其中关系矩阵是二维表格，行对应A应集合元素，若aRb则从a到b有每一行代表一个关系实例中元素，列对应B中元素，适合一条有向边计算机处理映射图对于特殊的关系（如函数），可以通过映射图直观表示，用箭头连接对应的元素映射图特别适合表示函数关系，清晰展示输入和输出之间的对应关系，帮助理解函数的性质关系的运算复合运算设R₁⊆A×B，R₂⊆B×C，R₁与R₂的复合关系R₁∘R₂⊆A×C定义为R₁∘R₂={a,c|存在b∈B使得a,b∈R₁且b,c∈R₂}复合运算表示关系的顺序连接，类似于函数的复合逆运算关系R⊆A×B的逆关系R⁻¹⊆B×A定义为R⁻¹={b,a|a,b∈R}逆运算实现了关系的方向反转，满足R⁻¹⁻¹=R和R₁∘R₂⁻¹=R₂⁻¹∘R₁⁻¹的性质幂运算设R是集合A上的关系，定义R的幂R⁰=I_A（恒等关系），R¹=R，R^n+1=R^n∘R（n≥1）关系的幂表示同一关系的多次复合，对应关系图中的n步可达路径闭包运算关系R的自反闭包、对称闭包、传递闭包分别是包含R的最小的具有自反性、对称性、传递性的关系传递闭包R⁺=R¹∪R²∪R³∪...，表示从R出发可达的所有关系关系的性质自反性对称性若对任意a∈A，都有a,a∈R，则称关系若对任意a,b∈A，当a,b∈R时，都有R在A上是自反的自反关系的特点是每b,a∈R，则称关系R在A上是对称的对个元素都与自身有关系，如相等关系称关系的特点是如果a与b有关系，则b与=、小于等于关系≤a也有关系，如是同学、相等在关系矩阵中，自反关系的主对角线元素在关系矩阵中，对称关系的矩阵是对称矩全为1；在关系图中，自反关系的每个顶阵；在关系图中，对称关系的每条边都是点都有环反自反关系是指对任意a∈A，双向的反对称关系是指对任意都有a,a∉R，如严格小于关系a,b∈Aa≠b，若a,b∈R，则b,a∉R，如小于关系传递性若对任意a,b,c∈A，当a,b∈R且b,c∈R时，都有a,c∈R，则称关系R在A上是传递的传递关系的特点是如果a与b有关系，b与c有关系，则a与c也有关系，如大于、先祖在关系矩阵中，传递关系的矩阵满足布尔运算M²⊆M；在关系图中，传递关系中若有从a到b和从b到c的路径，则必有从a到c的直接边等价关系划分商集集合A的一个划分是A的一些非空子等价类设R是集合A上的等价关系，A中所有集的集合{A₁,A₂,...,Aₙ}，满足

①∪ᵢ等价关系的定义设R是集合A上的等价关系，对任意等价类构成的集合称为A关于R的商Aᵢ=A；

②当i≠j时，Aᵢ∩Aⱼ=∅划分具有自反性、对称性和传递性的关系a∈A，集合[a]_R={x∈A|a,x∈R}集，记作A/R={[a]_R|a∈A}商集表与等价关系一一对应任何等价关系称为等价关系等价关系是集合上的称为a关于R的等价类等价类表示与示等价关系R将A分解为若干不相交产生一个划分（等价类集合）；反一种基本关系类型，表示元素间的元素a等价的所有元素构成的集子集的结果商集中的元素是A的子之，任何划分也确定一个等价关系相似性或等同性典型的等价关合等价类具有以下性质对任意集（等价类），而非A中的元素商（同属一个子集的元素等价）系包括整数的模n同余关系≡ₙ；a,b∈A，要么[a]_R=[b]_R，要么集的基数（等价类的个数）反映了R集合的具有相同基数关系；平面上[a]_R∩[b]_R=∅；任意a∈A都属于唯的区分能力直线的平行关系等一的等价类[a]_R偏序关系全序关系任意两元素可比较的偏序关系1偏序关系2自反、反对称、传递的二元关系哈斯图3偏序关系的简化图形表示可比元素与不可比元素4偏序集中元素间的比较性极大元、极小元、最大元、最小元5偏序集中的特殊元素偏序关系是同时满足自反性、反对称性和传递性的二元关系，记作≤偏序集是指集合连同其上的偏序关系，记作A,≤典型的偏序关系包括自然数上的小于等于；集合上的包含关系；整除关系等在偏序集中，若a≤b且a≠b，记作a函数的基本概念函数的定义单射满射双射函数是从集合X到集合Y的一函数f:X→Y是单射（一对函数f:X→Y是满射（映函数f:X→Y是双射（一一对种特殊二元关系f，满足对一），当且仅当对任意上），当且仅当对任意应），当且仅当f既是单射又X中每个元素x，存在唯一的x₁,x₂∈X，若x₁≠x₂，则y∈Y，存在x∈X使得是满射双射建立了X和Y之Y中元素y使得x,y∈f函数fx₁≠fx₂等价地，若fx=y满射意味着函数的值间的完全对应关系，每个x对通常记作f:X→Y，其中X称为fx₁=fx₂，则x₁=x₂单射域等于陪域，Y中每个元素都应唯一的y，每个y也对应唯定义域，Y称为陪域，保持元素的不同性，不同是X中某元素的像一的x{fx|x∈X}称为值域的元素映射到不同的像满射函数的示例fx=x²从双射函数存在逆函数函数的本质是对应规则，单射函数的示例fx=2x从R到[0,+∞；函数fx=sinx f⁻¹:Y→X在有限集间，双强调定义域中每个元素都有Z到Z；在有限集间，若从R到[-1,1]在有限集间，射存在的条件是|X|=|Y|且仅有一个像函数可以通|X|≤|Y|，则存在从X到Y的满射存在的条件是双射在计数问题和集合基数过解析表达式、表格、图形单射|X|≥|Y|理论中有重要应用等方式表示特殊函数单调函数周期函数12单调增函数若对任意x₁fx₂单调函数的复合仍为单调函数若存在正数T，使得对任意x∈X，有x+T∈X且fx+T=fx，则称f为周期函数，T称为f的一个周期周期函数的典型例子包括三角函数sin、cos，它们的基本周期为2π周期函数在物理、信号处理中有广泛应用复合函数逆函数34设f:X→Y，g:Y→Z，则g∘f:X→Z定义为g∘fx=gfx，称为f与g的复合函数复若f:X→Y是双射，则存在唯一的函数g:Y→X，使得对任意x∈X，gfx=x；对任意合函数描述了函数的串联操作，先应用f再应用g复合运算不满足交换律，即一y∈Y，fgy=y函数g称为f的逆函数，记作f⁻¹严格单调函数必有逆函数逆般情况下g∘f≠f∘g函数的图形关于直线y=x对称图论研究对象基本问题图论研究由顶点和连接顶点的边组成的1图的表示、遍历、连通性分析、最短路图形结构，建模各类离散关系2径、着色问题和匹配问题等实际应用理论发展4在社交网络、交通规划、电路设计和计从欧拉七桥问题发展至今，形成完善的3算机网络等领域有广泛应用理论体系和丰富的算法工具图的基本概念图的定义顶点和边有向图无向图图G是一个二元组G=V,E，其中V顶点（节点）是图的基本元素，表有向图（Directed Graph或无向图中的边没有方向性，表示为是非空有限集合，称为顶点集；E示对象；边表示顶点之间的连接关Digraph）中的边有方向性，表示无序对{u,v}无向图适合描述对是V中元素的无序对或有序对的集系若图中的边是顶点的无序对为有序对u,v，u称为始点，v称称关系，如无线网络、社交网络中合，称为边集图是表示对象之间{u,v}，则称为无向边；若边是有为终点有向图适合描述单向关系，的朋友关系等无向图可以看作特关系的数学模型，可以描述各种网序对u,v，则称为有向边（弧）如交通流、信息流、社交网络中的殊的有向图，其中每条边对应两条络结构，如交通网、社交网、电路边可以有权重，表示连接的强度、关注关系等有向图可以通过邻接相反方向的有向边网等距离、成本等矩阵或邻接表表示图的表示方法邻接矩阵邻接表关联矩阵邻接矩阵是表示图的二维数组A，其中邻接表是一种链式存储结构，对每个顶关联矩阵是表示图的二维数组M，行对A[i,j]=1表示存在从顶点i到顶点j的边，点v，维护一个链表，存储与v相邻的所应顶点，列对应边对于无向图，若顶A[i,j]=0表示不存在该边若图是带权有顶点对于有向图，链表包含所有从v点v与边e关联，则M[v,e]=1，否则为图，则A[i,j]可表示边的权重，不存在的出发可达的顶点；对于无向图，链表包0；对于有向图，若边e从顶点v出发，则边可用特殊值（如∞）表示含与v相连的所有顶点M[v,e]=1；若边e指向顶点v，则M[v,e]=-1；否则为0对于n个顶点的图，邻接矩阵的大小为邻接表适合稀疏图，空间复杂度为n×n无向图的邻接矩阵是对称的邻接O|V|+|E|，便于查找顶点的所有邻关联矩阵适合边的操作频繁的场景，但矩阵适合稠密图，便于判断两点间是否居，但不便于判断两点间是否有边在对于大型图，关联矩阵非常稀疏，空间有边，但空间复杂度为On²实际应用中，邻接表比邻接矩阵更常利用率低关联矩阵的大小为用|V|×|E|图的基本术语度路径顶点v的度dv是与v关联的边的数量在有路径是顶点的序列v₀,v₁,...,vₖ，其中相邻顶向图中，区分入度d⁻v（指向v的边数）和点之间有边相连路径的长度是路径上边的出度d⁺v（从v出发的边数），总度数量若路径中不重复使用顶点，则称为简dv=d⁻v+d⁺v图中所有顶点的度之和单路径；若除起点和终点可能相同外，不重等于边数的两倍（每条边贡献两个度）复使用顶点，则称为简单回路最大度ΔG和最小度δG是图G中顶点的最从顶点u到顶点v的最短路径是所有从u到v的大度和最小度度数序列是图中所有顶点度路径中长度最小的路径两点间最短路径的数的非增序列Havel-Hakimi算法用于判计算是图论中的基本问题，常用算法包括断一个序列是否是某图的度数序列Dijkstra算法、Bellman-Ford算法和Floyd-Warshall算法连通性若图G中任意两点之间都存在路径，则称G是连通的图的连通分量是图中的极大连通子图无向图的连通性是指图保持连通所需删除的最少顶点数（点连通度）或边数（边连通度）在有向图中，强连通是指任意两点之间都存在有向路径；弱连通是指将所有有向边替换为无向边后图是连通的强连通分量是有向图中的极大强连通子图，Kosaraju算法和Tarjan算法用于计算强连通分量。