1、1/29/2023 1:04 PM Discrete Math.,DeRen Chen1 Discrete Math.离散数学离散数学 研究离散对象及其相互间关系的一门数学学科。研究离散对象及其相互间关系的一门数学学科。研究离散结构的数学分支。（辞海）研究离散结构的数学分支。（辞海）离散数学的内容离散数学的内容：基础：基础概念概念 原理原理方法方法 应用应用实践实践1/29/2023 1:04 PM Discrete Math.,DeRen Chen2基础部分基础部分:逻辑逻辑(Logic)集合集合(Sets)算法算法(Algorithms)数论数论(Number Theory)原理部分原理部
2、分:数学推理数学推理(Reasoning)计数原理计数原理(Counting)关系关系(Relations)应用部分应用部分:图图(Graphs)树树(Trees)代数系统：布尔代数代数系统：布尔代数(Boolean Algebra)，群（群（Group）1/29/2023 1:04 PM Discrete Math.,DeRen Chen3逻辑（逻辑（LOGIC）：命题逻辑命题逻辑 Proposition Logic命题演算命题演算 Propositional Equivalences谓词和量词谓词和量词 Predicates and Quantifiers1/29/2023 1:04 PM
3、 Discrete Math.,DeRen Chen4 （1）命题的概念：）命题的概念：定义、逻辑值、定义、逻辑值、符号化表示符号化表示（2）从简单命题到复合命题：）从简单命题到复合命题：逻辑联接词：运算方法、运算优先级逻辑联接词：运算方法、运算优先级（3）从命题常量到命题变量，）从命题常量到命题变量，从复合命题到命题公式：从复合命题到命题公式：命题公式的真值描述：命题公式的真值描述：真值表真值表（4）命题公式的分类：）命题公式的分类：永真公式、永假公式、可满足公式永真公式、永假公式、可满足公式 （5）命题公式的等价演算：）命题公式的等价演算：基本等价定理；两种方法基本等价定理；两种方法（6）
4、命题公式的标准化描述：）命题公式的标准化描述：表达、判定、分类与应用表达、判定、分类与应用（7）从命题到命题函数：）从命题到命题函数：N元谓词、个体、个体变量、个体域元谓词、个体、个体变量、个体域（8）从命题公式到谓词公式：）从命题公式到谓词公式：存在量词、全称量词；变量的分类存在量词、全称量词；变量的分类（9）谓词公式的演算：）谓词公式的演算：基本等价定理基本等价定理1/29/2023 1:04 PM Discrete Math.,DeRen Chen51/29/2023 1:04 PM Discrete Math.,DeRen Chen6p q Tp q Fp (p q)p Absorpt
5、ion Laws/吸收律p (p q)pp q p qp q (p q)(q p)1/29/2023 1:04 PM Discrete Math.,DeRen Chen7判断命题公式逻辑等价的方法：判断命题公式逻辑等价的方法：1、真值表、真值表 2、命题公式的演算、命题公式的演算 基本等值定理（基本等价定理）；基本等值定理（基本等价定理）；公式的代入不变性；公式的代入不变性；等值关系的传递性。等值关系的传递性。1/29/2023 1:04 PM Discrete Math.,DeRen Chen8命题公式逻辑等价关系的应用：命题公式逻辑等价关系的应用：1、判定是否逻辑等价；、判定是否逻辑等价；
6、2、判断是否为永真公式或永假公式；、判断是否为永真公式或永假公式；3、命题公式的化简、命题公式的化简 1/29/2023 1:04 PM Discrete Math.,DeRen Chen9定理定理2 （基本量词等值定律）（基本量词等值定律）量词分配律量词分配律 Vx（A(x)B(x)）VxA(x)VxB(x)x(A(x)B(x)）xA(x)xB(x)另两种情况的思考：另两种情况的思考：V与与，与与量词否定律量词否定律1/29/2023 1:04 PM Discrete Math.,DeRen Chen10量词扩张量词扩张/收缩律收缩律Vx(PB(x)PVxB(x)Vx(PB(x)PVxB(x
7、)x(PB(x)P xB(x)x(PB(x)P x B(x)这里这里A、B是任意包括个体变量是任意包括个体变量x的谓词公式，的谓词公式，P是不包括是不包括个体变量个体变量x的任意谓词公式。的任意谓词公式。1/29/2023 1:04 PM Discrete Math.,DeRen Chen11 集合集合1.集合的表示集合的表示2.集合间的关系：相等、包含集合间的关系：相等、包含3.集合间的运算集合间的运算4.一些特殊的集合：空集、全集、幂集、一些特殊的集合：空集、全集、幂集、X集集5.集合的分类：集合的基集合的分类：集合的基6.函数的概念函数的概念7.函数的分类函数的分类8.函数的运算函数的运
8、算9.一些特殊的应用函数：语言一些特殊的应用函数：语言1/29/2023 1:04 PM Discrete Math.,DeRen Chen121/29/2023 1:04 PM Discrete Math.,DeRen Chen131/29/2023 1:04 PM Discrete Math.,DeRen Chen14证明两个集合相等的方法：证明两个集合相等的方法：1、定义方法：谓词公式、定义方法：谓词公式2、相等定理：互相包含、相等定理：互相包含3、集合相等运算：基本相等定理、集合相等运算：基本相等定理4、Venn 图（文氏图）：图解图（文氏图）：图解5、位运算、位运算1/29/2023
9、 1:04 PM Discrete Math.,DeRen Chen15一对一，单函数，单射一对一，单函数，单射映上的，满函数，满射映上的，满函数，满射一一对应，双射一一对应，双射逆函数逆函数函数的复合运算，积运算函数的复合运算，积运算1/29/2023 1:04 PM Discrete Math.,DeRen Chen16几个常用的函数：几个常用的函数：Eigenfunctionfloor functionceiling function关于集合的进一步讨论（基于函数）：关于集合的进一步讨论（基于函数）：Sequences string Language Countable of eleme
10、nts in sets1/29/2023 1:04 PM Discrete Math.,DeRen Chen17 算法（算法（Algorithm）是通过一个有限的指是通过一个有限的指令序列集合对特定问题进行求解的一种计算执令序列集合对特定问题进行求解的一种计算执行描述。行描述。An algorithm is a finite set of precise instructions for performing a computation or for solving a problem.1/29/2023 1:04 PM Discrete Math.,DeRen Chen18一个算法通常应具有
11、下列特征：一个算法通常应具有下列特征：（1）输入：一个算法具有零个或多个取自指定集合的输入）输入：一个算法具有零个或多个取自指定集合的输入值；值；（2）输出：对算法的每一次输入，算法具有一个或多个与）输出：对算法的每一次输入，算法具有一个或多个与输入值接联系的输出值；输入值接联系的输出值；（3）确定性：算法的每一个指令步骤都是明确的；）确定性：算法的每一个指令步骤都是明确的；（4）有限性：对算法的每一次输入，算法都必须在有限步）有限性：对算法的每一次输入，算法都必须在有限步骤（即有限时间）内结束；骤（即有限时间）内结束；（5）正确性：对每一次输入，算法应产生出正确的输出值；）正确性：对每一次输
12、入，算法应产生出正确的输出值；（6）通用性：算法的执行过程可应用于所有同类求解问题，）通用性：算法的执行过程可应用于所有同类求解问题，而不是仅适用于特殊的输入。而不是仅适用于特殊的输入。1/29/2023 1:04 PM Discrete Math.,DeRen Chen19Let f and g be functions from the set of R or I to the set of R.Call that f(x)is O(g(x)if there are constants C and k such that|f(x)|k.Read as“f(x)is big-oh of g(
13、x)”O:Landau symbol关于关于C和和k 的说明：的说明：1、不唯一不唯一 2、是有序对作为元素的一个无限集、是有序对作为元素的一个无限集 3、尽可能小、尽可能小1/29/2023 1:04 PM Discrete Math.,DeRen Chen20Theorem 1 If f(x)=an xn+an-1 xn-1+a 1 x1+a0 where ai R,i=0,1,nThen f(x)is O(xn)Theorem 2 If f1(x)is O(g1(x),f2(x)is O(g2(x),Then (f1+f2)(x)is O(max(g1(x),g2(x)1/29/2023
14、 1:04 PM Discrete Math.,DeRen Chen21Corollary 1 If f1(x)is O(g(x),f2(x)is O(g(x),Then (f1+f2)(x)is O(g(x)Theorem 3 If f1(x)is O(g1(x),f2(x)is O(g2(x),Then (f1 f2)(x)is O(g1(x)g2(x)1/29/2023 1:04 PM Discrete Math.,DeRen Chen22常用的算法复杂性分类：常用的算法复杂性分类：O(1):constant complexity O(log n):logarithmic complex
15、ity O(n):linear complexity O(n log n):n log n complexity linear O(nb):polynomial complexity polynomial O(bn):exponential complexity(b1)exponential O(n!):factorial complexity1/29/2023 1:04 PM Discrete Math.,DeRen Chen23Let f and g be functions from the set of R or I to the set of R.Call that f(x)is (
16、g(x)if there are constants C and k such that|f(x)|=C|g(x)|Wherever x k.Read as“f(x)is big-omega of g(x)”1/29/2023 1:04 PM Discrete Math.,DeRen Chen24Let f and g be functions from the set of R or I to the set of R.Call that f(x)is (g(x)if f(x)is O(g(x)and f(x)is (g(x)Read as“f(x)is big-theta of g(x)”
17、“f(x)is of order g(x)”1/29/2023 1:04 PM Discrete Math.,DeRen Chen25数论数论（Number Theory）1、算术基本定理、算术基本定理2、同余关系、同余关系3、密码学基础、密码学基础定义定义 设设m是一个正整数，对任意两个整数是一个正整数，对任意两个整数a、b，若，若a-b能被能被m整除，则称整除，则称a与与b是是（模（模m）同余的）同余的，或，或（模（模m）合）合同的同的/congruent by modulo m，记为，记为 a b(mod m)在在m确定的情况下，简记为确定的情况下，简记为 a b。1/29/2023 1
18、:05 PM Discrete Math.,DeRen Chen261、整数的因子、公因子、整数的因子、公因子、GCD -EUCLID算法、算法、GCD的线性组合的线性组合2、质数、质因子、两两互质、质数、质因子、两两互质 -整数分解整数分解3、同余关系、线性同余、中国同余定理、同余关系、线性同余、中国同余定理4、费尔玛小定理、费尔玛小定理、RSA算法算法1/29/2023 1:05 PM Discrete Math.,DeRen Chen27原理部分原理部分:数学推理数学推理(Reasoning)3.1 推理与证明方法推理与证明方法 3.2 数学归纳方法数学归纳方法 3.3 递推方法递推方法
19、 计数原理计数原理(Counting)关系关系(Relations)1/29/2023 1:05 PM Discrete Math.,DeRen Chen28蕴涵演算蕴涵演算/logical implying operation 对于任意的公式对于任意的公式P和和Q，如果，如果P Q 为为T，则称，则称P蕴涵蕴涵Q，记为记为P Q 或或P/Q蕴涵演算的推广表示：蕴涵演算的推广表示：P1、P2、Pn Q 前提组前提组/hypotheses 结论结论/conclusion1/29/2023 1:05 PM Discrete Math.,DeRen Chen29Rule of Inference N
20、ameP P QAddition/析取附加式析取附加式P Q P Simplification/合取化简式合取化简式P、Q P Q Conjunction/并发式并发式P、P Q QModus ponens/分离式分离式 Q、P Q PModus tollens/拒取式拒取式 p、P Q QDisjunctive syllogism/析取三段式析取三段式P Q、Q R P R Hypothetical syllogism/假言假言三段式三段式1/29/2023 1:05 PM Discrete Math.,DeRen Chen30定理证明方法：定理证明方法：1、直接证明、直接证明/direct
21、 proof:p Q 2、间接证明、间接证明/indirect proof:p Q Q P3、空证明、空证明/vacuous proof:p Q 其中其中 P为为 F4、平凡证明、平凡证明/trivial proof：p Q 其中其中 Q 为为T1/29/2023 1:05 PM Discrete Math.,DeRen Chen31定理证明方法：定理证明方法：5、反证明、反证明/proof of contradiction：P P S S6、分例证明、分例证明/proof of cases：P1 P2 Pn Q （P1 Q）（P2 Q）（Pn Q）7、存在证明、存在证明/existence
22、proof：x P(x)constructive,nonconstructive8、归纳证明、归纳证明/induction proof：x P(x)1/29/2023 1:05 PM Discrete Math.,DeRen Chen32（1）0N；（2）对每一个）对每一个nN，唯一定义了一个自然数，唯一定义了一个自然数n，n 称为称为n的后邻；的后邻；（3）不同的自然数，其后邻也不同；）不同的自然数，其后邻也不同；（4）没有一个自然数的后邻是）没有一个自然数的后邻是0；（5）如果有一个子集）如果有一个子集M N满足：满足：0M；nM时必时必n M,则则M=N自然数全体自然数全体N通过皮亚诺公
23、理的五条公理组成。通过皮亚诺公理的五条公理组成。这些公理缺一不可，其中性质（这些公理缺一不可，其中性质（5）称为归纳公理，并指）称为归纳公理，并指出了自然数是满足公理（出了自然数是满足公理（1）（4）的最小集合。）的最小集合。1/29/2023 1:05 PM Discrete Math.,DeRen Chen33数学归纳法的一般公式表示：数学归纳法的一般公式表示：P(k)m(m k P(m)P(m+1)n P(n)1、归纳基础：、归纳基础：P(k)2、归纳步骤：、归纳步骤：m(m k P(m)P(m+1)第二数学归纳法：第二数学归纳法：P(n0)k(k n0 P(n0)P(n0+1)P(k)
24、P(k+1)n P(n)1、归纳基础：、归纳基础：P(n0)2、归纳步骤：、归纳步骤：k(k n0 P(n0)P(n0+1)P(k)P(k+1)1/29/2023 1:05 PM Discrete Math.,DeRen Chen34有限数学归纳法：对于有限数学归纳法：对于 n0 n nk 的的 P(n)有限数学归纳法的前推公式表示：有限数学归纳法的前推公式表示：P(n0)n(n0 n nk-1 P(n)P(n+1)n(n0 n nk P(n)1、归纳基础：、归纳基础：P(n0)2、归纳步骤：、归纳步骤：n(n0 n nk-1 P(n)P(n+1)有限数学归纳法：对于有限数学归纳法：对于 n0
25、 n nk 的的 P(n)有限数学归纳法的后推公式表示：有限数学归纳法的后推公式表示：P(nk)n(n0+1 n nk P(n)P(n-1)n(n0 n nk P(n)1、归纳基础：、归纳基础：P(nk)2、归纳步骤：、归纳步骤：n(n0+1 n nk P(n)P(n-1)1/29/2023 1:05 PM Discrete Math.,DeRen Chen35定义定义1如果一个对象部分地由自己所组成，如果一个对象部分地由自己所组成，或 者 按 它 自 己 定 义，则 称 为 是或 者 按 它 自 己 定 义，则 称 为 是 递 归递 归 的的（Recursion）。）。f的定义域：非负整数集
26、的定义域：非负整数集 1、递归基础：、递归基础：f(0)2、递归步骤：、递归步骤：f(n)=g(f(k),k=0菲波那契数菲波那契数/FibonacciF(0)=0，F(1)=1F(n)=F(n1)+F(n2)n11/29/2023 1:05 PM Discrete Math.,DeRen Chen364、计数原理、计数原理/Counting 4.1 基本计数原理基本计数原理:加法原理和乘法原理加法原理和乘法原理 The Basic of Counting 4.2 包含与排斥原理包含与排斥原理:有限集的基的运算有限集的基的运算 The Inclusion-Exclusion Principle
27、 4.3 鸽洞原理鸽洞原理:有限集的基的比较有限集的基的比较 The Pigeonhole Principle4.4 排列与组合排列与组合:排列、组合、二项式排列、组合、二项式 Permutations and Combinations4.5 排列与组合的生成：排列与组合的生成：排列生成、组合生成排列生成、组合生成 Generating Permutations and Combinations1/29/2023 1:05 PM Discrete Math.,DeRen Chen37求和规则求和规则/The Sum RuleIf a first task can be done in n wa
28、ys and a second task in m ways,and if there these tasks cannot be done at the same time,then there are n+m ways to be either task.|A1 A2|=|A1|+|A2|其中其中A1 A2=求和规则的推广求和规则的推广|A1 A2 An|=|A1|+|A2|+|An|其中其中A i A j=i j,i,j=1,2,n1/29/2023 1:05 PM Discrete Math.,DeRen Chen38求积规则求积规则/The Product RuleSuppose t
29、hat a procedure can be broken down into two tasks.If there are n ways to do the first task and m ways to do the second task after the first task has been done,then there are nm ways to do the procedure.|A1 A2|=|A1|A2|求积规则的推广求积规则的推广|A1 A2 An|=|A1|A2|An|1/29/2023 1:05 PM Discrete Math.,DeRen Chen39对任意
30、有限集对任意有限集A1、A2，成立成立|A1 A2|=|A1|+|A2|-|A1 A2|推广：推广：|A1 A2 An|=1/29/2023 1:05 PM Discrete Math.,DeRen Chen40The Pigeonhole PrincipleIf k+1 or more objects are placed into k boxes,then there is at least one box containing two or more of the objects.The Generalized Pigeonhole PrincipleIf N objects are p
31、laced into k boxes,then there is at least one box containing at least N/k objects.1/29/2023 1:05 PM Discrete Math.,DeRen Chen414.4 排列与组合排列与组合/Permutations and Combinations(1)排列：排列：r-排列、全排列、排列、全排列、r-可重排列、可重排列、r-限重排列、限重排列、r-循环排列循环排列(2)组合：组合：r-组合、组合、r-可重组合可重组合(3)二项式定理与二项式系数：二项式定理与二项式系数：4.5 排列与组合的生成排列与组
32、合的生成 Generating Permutations and Combinations1/29/2023 1:05 PM Discrete Math.,DeRen Chen42定义定义1：n个元素的集合个元素的集合A中任意选择中任意选择r个（个（r n）进行排列称为进行排列称为A的一个的一个r-排列排列/r-Permutation定理定理1：n个元素的集合个元素的集合A的的r-排列数为排列数为 n(n-1)(n-2)(n-r+1)=P(n,r)特别地，当特别地，当r=n 时，记时，记P(n,r)=n!称为称为A的一个的一个全排列全排列1/29/2023 1:05 PM Discrete M
33、ath.,DeRen Chen43排列的函数表示：排列的函数表示：|A|=n，B=1,2,r，F:BA（1）F是一个单射是一个单射 A的一个的一个r-排列排列（2）B到到A的所有的所有单射总数单射总数 P(n,r)排列的球盒模型表示：排列的球盒模型表示：|A|=n n个盒子个盒子 B=1,2,r r个不同的球个不同的球F:BA且是单射且是单射 每个盒子最多放一个球每个盒子最多放一个球 A的一个的一个r-排列排列B到到A的所有的所有单射总数单射总数 球放入盒子的放法总数球放入盒子的放法总数 P(n,r)1/29/2023 1:05 PM Discrete Math.,DeRen Chen44定义
34、定义2：n个元素的集合个元素的集合A中任意选择中任意选择r个（个（r n）称为）称为A的一个的一个r-组合组合/r-Combination定理定理2：n个元素的集合个元素的集合A的的r-组合数为组合数为 n(n-1)(n-2)(n-r+1)/r!记为记为C(n,r)组合的球盒模型表示：组合的球盒模型表示：B=0，1 两个盒子两个盒子 A n个不同的球个不同的球F:BA且使得且使得A中的中的r个元素的象为个元素的象为1 指定一个盒子恰好放指定一个盒子恰好放r个球个球 A的一个的一个r-组合组合满足条件的满足条件的F总数总数=C(n,r)=满足条件的球的放法总数满足条件的球的放法总数1/29/20
35、23 1:05 PM Discrete Math.,DeRen Chen45定理定理6（Binomial Theorem/二项式定理）：二项式定理）：对任意正整数对任意正整数n和变量和变量x、y （x+y）n=nj=0 C（n，j）xn-j yj1/29/2023 1:05 PM Discrete Math.,DeRen Chen46定义定义3 n个不同元素的集合个不同元素的集合A，每个元素可重复，每个元素可重复选取，则选取，则A中任意选择中任意选择r个（个（r n）进行排列称为）进行排列称为A的一个的一个r-可重排列可重排列/r-Permutation with repetition。定理定
36、理7 n个不同元素的集合个不同元素的集合A，每个元素可重复，每个元素可重复选取，则选取，则A的的r-可重排列总数为可重排列总数为nr。1/29/2023 1:05 PM Discrete Math.,DeRen Chen47定义定义6 n个不同元素的集合个不同元素的集合A，每个元素可重复，每个元素可重复选取，则选取，则A中任意选择中任意选择r个（个（r n）的方式称为）的方式称为A的的一个一个r-可重组合可重组合/r-Combination with repetition。定理定理10 n个不同元素的集合个不同元素的集合A，每个元素可重，每个元素可重复选取，则复选取，则A的的r-可重组合总数为
37、可重组合总数为 C（n-1+r，r）1/29/2023 1:05 PM Discrete Math.,DeRen Chen48Relations 关系关系（1）二元关系的概念：集合、关系、函数）二元关系的概念：集合、关系、函数 多元关系多元关系（2）二元关系的表示）二元关系的表示:集合、图形、矩阵集合、图形、矩阵（3）二元关系的性质：分类）二元关系的性质：分类（4）二元关系的运算：集合运算、函数运算、闭包运算）二元关系的运算：集合运算、函数运算、闭包运算1/29/2023 1:05 PM Discrete Math.,DeRen Chen49（5）等价关系的概念、等价关系与划分等价关系的概念、
38、等价关系与划分（6）半序关系与半序集、全序关系与全序集半序关系与半序集、全序关系与全序集 半序集中的极小半序集中的极小/大元素、最小大元素、最小/大元素、大元素、上上/下界、上下界、上/下确界下确界 良序关系与良序集、拓扑排序良序关系与良序集、拓扑排序1/29/2023 1:05 PM Discrete Math.,DeRen Chen50 7、图、图/Graph7.1 图的概念图的概念/Introduction of Graph7.2 图的术语图的术语/Graph Terminology7.3 图的表示与同构图的表示与同构/Representing Graph and Graph Isomo
39、rphism 表示表示:集合、表、矩阵集合、表、矩阵 图的转换、图的包含、图的转换、图的包含、图的运算、图的同构图的运算、图的同构7.4 连通性连通性/Connectivity1/29/2023 1:05 PM Discrete Math.,DeRen Chen51一些特殊的简单无向图：一些特殊的简单无向图：（1）Complete Graphs/完全图完全图Kn （2）Cycles/环图环图Cn （3）Wheels/轮图轮图Wn （4）n-Cubes/n-立方图立方图Qn （5）Bipartite Graphs/二分图二分图Kn,m1/29/2023 1:05 PM Discrete Math
40、.,DeRen Chen52一些特殊的其他图：一些特殊的其他图：（1）有向完全图）有向完全图 （2）零图）零图 （3）平凡图）平凡图 （4）正则图：若图（，）中每正则图：若图（，）中每个顶点的次均为个顶点的次均为n n，称此图是，称此图是n-n-正则的正则的/n-/n-regularregular。1/29/2023 1:05 PM Discrete Math.,DeRen Chen537.5 欧拉道路与哈密尔顿道路欧拉道路与哈密尔顿道路/Euler and Hamilton Paths7.6 最短道路问题最短道路问题/Shortest Path Problem7.7 平面图平面图/Plana
41、r Graphs 平面图的概念：无向、简单、有限、非交叉边平面图的概念：无向、简单、有限、非交叉边/区域区域 平面图的欧拉公式：必要条件平面图的欧拉公式：必要条件 平面图判定的库氏定理：关键点：极大非平面图平面图判定的库氏定理：关键点：极大非平面图7.8 图的着色图的着色/Graph Coloring1/29/2023 1:05 PM Discrete Math.,DeRen Chen54树树/Trees8.1 树的概念树的概念/Introduction of Trees8.2 树的应用树的应用/Applications of Trees8.3 树的遍历树的遍历/Tree Traversal8
42、.4 树和分类树和分类/Trees and Sorting8.5 生成树和最小生成树生成树和最小生成树/Spanning Trees and minimum Spanning Trees1/29/2023 1:05 PM Discrete Math.,DeRen Chen551、树的概念：无向、树的概念：无向/有向有向 树的层、树中顶点的道路长度树的层、树中顶点的道路长度2、树的分类：、树的分类：M元树、正规元树、正规M元树、完全元树、完全M元树元树3、树的应用：、树的应用：前缀码、前缀码、二元树的遍历问题二元树的遍历问题4、生成树：存在的充分必要条件、生成树：存在的充分必要条件 最小生成树的
43、求法最小生成树的求法算法算法1/29/2023 1:05 PM Discrete Math.,DeRen Chen56 布尔代数的抽象定义：布尔代数的抽象定义：半序集（半序集（A，）格格/Lattics:半序集（半序集（A，）对任意）对任意a,b A,a,b 的上的上确界确界c和下确界和下确界d存在，记存在，记a b=c,a b=d有界格有界格：格中存在最大元素：格中存在最大元素1和最小元素和最小元素0。有界格中元素的余元有界格中元素的余元：a A，若存在，若存在b A使得使得a b=1,a b=0，称称b是是 a的一个余元。的一个余元。1/29/2023 1:05 PM Discrete M
44、ath.,DeRen Chen57有余格有余格：有界格中每一个元素都存在余元。：有界格中每一个元素都存在余元。分配格分配格：有界格中：有界格中上确界和下确界运算满足分配律。上确界和下确界运算满足分配律。定理：分配格中任意元素若有余元，则必唯一。定理：分配格中任意元素若有余元，则必唯一。布尔格布尔格：至少有两个元素的有余分配格。：至少有两个元素的有余分配格。布尔代数布尔代数：布尔格对应的代数系统：布尔格对应的代数系统 （A，）1/29/2023 1:05 PM Discrete Math.,DeRen Chen58布尔表达式与布尔函数布尔表达式与布尔函数Boolean Expressions a
45、nd Boolean FunctionsB=0,1,xi:布尔变量布尔变量,i=1,2,nF:BnB,布尔函数，布尔函数，n:布尔函数的维数布尔函数的维数布尔表达式的表示布尔表达式的表示 布尔表达式的图示方法：卡诺图布尔表达式的图示方法：卡诺图/Karnaugh Maps 布尔表达式的标准化描述布尔表达式的标准化描述 表达、分类、判定、应用表达、分类、判定、应用1/29/2023 1:05 PMDiscrete Math.,DeRen Chen59精品课件精品课件！1/29/2023 1:05 PMDiscrete Math.,DeRen Chen60精品课件精品课件！1/29/2023 1:05 PM Discrete Math.,DeRen Chen61
