全套课件：离散数学.ppt

1、离 散 数 学绪 言 1 计算机科学与离散数学 介绍离散数学在计算机科学发展中的作用与关系，明确离散数学是掌握与研究计算机科学的基础理论与工具。2离散数学的特征 离散性 能行性 3离散数学的内容 离散数学的主要内容为：数理逻辑 集合论 代数系统 图论 第一篇 数理逻辑 数理逻辑是用数学方法研究形式逻辑演绎推理规则的科学，它是一门数学，是一门研究演绎推理规则的数学，在学习此部分时，主要要掌握如下几个要点：思维的形式化 指派法 公式推理 公理系统 范式 自动定理证明 本篇由命题逻辑、谓词逻辑、公理化理论及非经典逻辑等四部分组成，其中命题逻辑以命题为研究对象而谓词逻辑则以谓词为研究对象，而公理化理论

2、则是数理逻辑中演绎推理的形式化思想的介绍，最后非经典逻辑则介绍若干种计算机科学中常用的一些特殊形式逻辑，以上四部分有机结合构成完整的整体。1.4 1.4 命题逻辑基本等式命题逻辑基本等式（6）命题逻辑42个基本等式。交换律 PQQP；PQQP；PQQP 结合律 （PQ）RP（QR）；（PQ）RP（QR）；（PQ）RP（QR）分配律 P（QR）（PQ）（PR）；P（QR）（PQ）（PR）；否定深入PP；（PQ）PQ；（PQ）PQ；（PQ）PQ；(14)（PQ）PQPQ；变元等同PPP；PPP；PPF；PPT；PPT；PPP；PPP；PPT；PPPPF；常值与变元的联结TPP；FPF；TPT；FP

3、F；TPP；FPT；PTT；PFP；TPP；FPP；联结词化归PQ（PQ）；PQ（PQ）；PQPQ；PQ（PQ）（QP）其它PQQP(PQ)（PR）PQRP（PQ）PP（QR）PQRP（PQ）P1.5 1.5 对偶定理对偶定理（7）对偶公式定义（8）对偶公式性质：一个等式成立其对偶等式也成立1.6 1.6 命题逻辑基本蕴含式及推理规则命题逻辑基本蕴含式及推理规则（9）19个基本蕴含重言式 PQP；PQQ；P PQ；QPQ；PPQ；QPQ；（PQ）P；（PQ）Q；P（PQ）Q；Q（PQ）P；P（PQ）Q；Q（PQ）P；(PQ)(QR)PR；(PQ)(RS)PRQS；(PQ)(PR)(QR)R；P

4、(QPQ)；(PQ)(QR)(PR)；(P(QR)(Q(PR)；(PQ)(RQ)(PRQ)（10）11个推理规则 P，QP；P，QQ；PPQ；QPQ；P，QPQ；P，PQQ；P，PQQ；Q，PQP；PQ，QRP R；PQ，RSPR QS；PQ，PR，QRR；1.7 1.7 范式范式 （11）范式命题公式的一种标准形式 （12）特异析取范式：该范式是一个析取式，每个析取项是所有命题变元式其否定的合取式。（13）特异合取范式：该范式是一个合取式，每个析取项是所有命题变元式其否定的析取式。1.8 1.8 命题联结词的扩充与归约命题联结词的扩充与归约 （13）命题联结词的扩充异或：、与非：、或非：、蕴

5、含否定：C （14）命题联结词的归约命题联结词可归约为如下形式之一：,第二章 谓词逻辑 2.1 2.1 谓词与个体谓词与个体（1）个体 个体常量与个体变量 个体域与全总个体域（2）谓词 一元谓词刻划个体性质 二元谓词刻划两个个体间关系 n元谓词刻划n个个体间关系量词量词（3）存在量词：x P(x)“有一些”之语义（4）全称量词：x P(x)“所有”之语义（5）量词的辖域量词所作用的范围 函数函数（6）函数个体间的特定关系称函数，它是个体间的映射。f(x)中X是个体而f为函数符号，f(x)为函数。2.2 2.2 谓词逻辑公式谓词逻辑公式 （7）谓词逻辑公式 项：个体是项，函数是项 原子公式：P（

6、t1,t2,tn）是原子公式（其中ti为项）公式：原子公式是公式；A，B是公式，则（A）,（AB）,（AB）,（AB），（AB）是公式；A是公式，x为个体变量，则（x）A，（x）A为公式；公式由且仅由有限次使用前面三步而得。2.3 2.3 自由变元与约束变元自由变元与约束变元 （8）谓词公式中的自由变元与约束变元 谓词公式中的自由变元与约束变元 约束变元的改名规则改名在量词变元及其辖域中该变元的约束出现处进行且该变元不在量词辖域内出现过。自由变元的代入规则代入在公式的自由变元出现的每一处进行且该代入变元不允许在式中以任何约束形式出现。2.4 2.4 谓词逻辑永真公式谓词逻辑永真公式 （9）谓词

7、逻辑永真公式定义 谓词公式的解释与赋值 （10）谓词逻辑永真公式定义公式在所有解释下对所有赋值均为真 （11）谓词逻辑永真公式等式：（xP（x）x（P（x）（x P（x）x（P（x）xP（x）Qx（P（x）Q）xP（x）Qx（P（x）Q）xP（x）Qx（P（x）Q）xP（x）Qx（P（x）Q）xyP（x,y）yx（P（x,y）xyP（x,y）yx（P（x,y）x P（x）Qx（P（x）Q）x P（x）Qx（P（x）Q）Qx P（x）x（Q P（x）Qx P（x）x（Q P（x）x（P（x）Q（x）x（P（x）x Q（x）x（P（x）Q（x）x（P（x）x Q（x）（12）谓词逻辑的蕴含永真公式

8、xyP（x,y）yx（P（x,y）xP（x）P（x）P（x）x P（x）xP（x）x Q（x）x（P（x）Q（x）xP（x）x Q（x）x（P（x）Q（x）x（P（x）x（P（x）x（P（x）Q（x）x（P（x）x Q（x）x（P（x）Q（x）xP（x）x Q（x）2.5 2.5 范式范式 （13）前束范式公式的所有量词均非否定的出现在公式最前面，它的辖域一直延伸至公式末尾，且公式中不出现与。（14）斯科林范式前束范式的首标处仅出现全称量词且公式中不出现自由变元x1x2xnM（x1,x2,x n）命题逻辑与谓词逻辑的公理化理论命题逻辑与谓词逻辑的公理化理论（16）公理系统的组成 命题：P1，P

9、2，Pn；命题联结词：，；个体常量：a，b，c，x，y，z；个体变量：P，Q，R；函 数：f，g，h；谓 词：，；括 号：（，）项：个体常量是项；个体变量是项；f是n元函数，t1，t2，,tn是项，则f(t1，t2，,tn)是项；项由且仅由有限次使用、而得。原子公式：P是n元谓词，t1，t2，tn是项，则P（t1，t2，tn)是原子公式。命题逻辑公式：命题是公式；P是公式则（P）是公式；P，Q是公式则（PQ），（PQ），（PQ），（PQ）是公式；公式由且仅由有限次使用，而得。谓词逻辑公式：原子公式是公式；A，B是公式则：（A），（AB），（AB），（AB）,（AB）是公式；A是公式则（x）A，

10、（x）B是公式；公式由且仅由有限次使用、而得。（17）公理系统的推理 1）公理 如P，Q，R为公式，则有下述的公理：PP；（P（QR）（Q（PR）；（PQ）（QR）（PR）；（P（PQ）（PQ）；（PQ）（PQ）；（PQ）（QP）；（PQ）（QP）（PQ）；PQQ；PQP；P（QPQ）；PPQ；QPQ；（QP）（RP）（QRP）；（PQ）（QP）；PP；2）推理规则 分离规则：PQ，PQ。3）证明（过程）与定理 证明（过程）给出了公理系统中定理生成的过程，它是一个公式序列：P1，P2，Pn，其中每个Pi（i1，2，n）必须满足下条件之一。Pi是公理；Pi是由Pk，Pr，（k，ri）施行分离规则

11、而得。最后，PnQ 即为定理。（18）导出规则如有AB为定理则必有AB。（19）推理定理设有设有A1，A2，AnB，则必有：A 1,A2,An-1 An B。（20）谓词逻辑公理系统 1系统组成部分 可见（16）2推理部分 1）公理 设P，Q，R为公式，则有公理如下：pp（P（QR）（Q（PR）（PQ）（QR）（PR）（P（PQ）（PQ）（PQ）（PQ）（PQ）（QP）（PQ）（QP）（PQ）PQQ PQP P（QPQ）PPQ QPQ （QP）（RP）（QRP）（PQ）（QP）PP xP（x）P（x）P（x）xP（x）。11121314151617 2）推理规则 分离规则：PQ，PQ.全称规规

12、：QP（x）QxP（x）存在规则：P（x）Qx P（x）Q 上面17个公理与3个规则中有15个公理与1个规则是命题逻辑公理系统的，真正属谓词逻辑的仅有2个公理与2个规则。3）证明（过程）与定理。证明（过程）是一个公式序列：P1，P2，Pn，其中每个Pi（i1，2，n）必须满足下条件之一：Pi是公理；Pi是由Pk，Pr，（k，ri）施行分离规则而得；Pi是由Pk（ki）施行全称规则而得；Pi是由Pk（ki）施行存在规则而得。最后，PnQ 即为定理。（21）谓词逻辑中四个重要的推理规则 全称指定规则：US x P（x）P（x）全称推广规则：UG P（x）x P（x）存在指定规则：ES x P（x）

13、P（x）存在推广规则：EG P（x）x P（x）2.6 2.6 数理逻辑公理化应用系统数理逻辑公理化应用系统 （22）数理逻辑公理化应用系统的定义：数理逻辑公理系统学科式领域的公理与规则。公理化理论与计算机科学公理化理论与计算机科学 （23）公理化理论在计算机科学中的应用谓词逻辑的自动定理证明谓词逻辑的自动定理证明（24）子句与Horn子句（25）消解原理 将一公式化为Horn子句集 采用消解原理，即由S为公理证明E为定理的过程可改写：作SSUE为公理；从E开始在S中不断使用反驳法；最后出现空子句口则结束；如空子句出现则表示公式为真。PROLOGPROLOG语言简介语言简介（26）PROLOG

14、语言第三章 非经典逻辑介绍 3.1 3.1 多值逻辑多值逻辑 （27）多值逻辑逻辑变量超过两个值的逻辑，如三值逻辑。3.2 3.2 模态逻辑模态逻辑 （28）模态逻辑在逻辑中增加虚拟语句的逻辑如增加：可能、必然、相信、希望等模态词。3.3 3.3 非单调逻辑非单调逻辑 （29）非单调逻辑在逻辑中增加“例外”的逻辑。3.4 3.4 时态逻辑时态逻辑 （30）时态逻辑在逻辑中增加“时间”概念的逻辑。3.5 3.5 模糊逻辑模糊逻辑 （31）模糊逻辑在逻辑中增加“模糊”概念的逻辑。第二篇 集合论 本篇由集合论初步、关系、函数、有限集与无限集等与集合论相关等四部分内容组成，它们间是一个内容关联的整体。

15、第四章 集合论初步 集合论是数学的基础，也是离散数学的基础。故学好集合论十分重要，在本章学习中要掌握：集合中的一个基本概念 集合中的两种关系 集合中的三种特殊集合 集合中的四种表示方法 集合中的五种运算 集合中的21个常用公式4.1 集合论基本概念集合论基本概念（1）一个主要的概念一个主要的概念集合的基本概念集合的基本概念：一些不同确定的对象全体称集合，而这些对象称集合的元素。（2）集合中的两个关系集合中的两个关系 集合间的比较关系：AB，AB，AB，AB。集合与元素间的隶属关系：aA，aA。（3）三种特殊的集合三种特殊的集合 空集 全集E 幂集（A）。（4）集合的四种表示法：集合的四种表示法

16、：枚举法枚举法。即将集合元素一一列举。例：1,2,3,特性刻划法特性刻划法。即用元素的性质刻划集合。例：x|p(x)图示法图示法。即用文氏图表示集合及集合间的关系。例：运算法运算法。即用已知集合的运算构造新的集合。例：SA（BC）AAB（5）集合的五种运算：）集合的五种运算：交运算：AB 倂运算：AB 差运算：AB 补运算：A 对称差运算：AB（6）集合的）集合的21个公式：个公式：交换律：交换律：ABBAABBA结合律：结合律：A（BC）（AB）CA（BC）（AB）C分配律：分配律：A（BC）（AB）（AC）A（BC）（AB）（AC）同一律：同一律：AAAEA零一律：零一律：AEEA互补律：

17、互补律：AAEAA双补律：双补律：（A）AE与与 的互补：的互补：EE等幂律：等幂律：AAA AAA吸收律：吸收律：A（AB）A A（AB）A狄狄莫根定律：莫根定律：（AB）AB（AB）AB 4.5 有限集与无限集 （1）有限集与无限集的基本概念 有限集的两个定义 集合S与Nn 一 一对应 非无限集即为有限集 无限集的两个定义 S与一 一对应函数f：SS使得：f(S)S S存在与其等势的真子集 （2）有限集 有限集的基数有限集元素个数 有限集的计数计算有限集中元素个数 有限集计数的四种方法：|AB|A|+|B|AB|A|+|B|AB|ABC|A|+|B|+|C|AB|AC|BC|+|ABC|S

18、1S2Sn|Si|SiSj|SiSjSk|（1）|S1S2S n|ni=11ijn1ijkn 无限集无限集 （3）四个常用的无限集：）四个常用的无限集：自然数集N 整数集I 有理数集Q 实数集R （4）无限集的势无限集的势 （5）无限集分类（按势分类）无限集分类（按势分类）自然数集自然数集 可列集可列集基数为基数为0 整整 数数 集集 无限集无限集 实数集实数集基数为基数为 有理数集有理数集 更大基数的集更大基数的集（A）幂集、幂集、n元有序组与笛卡尔乘积元有序组与笛卡尔乘积 （7）幂集 幂集定义：集合A的所有子集所组成的集合，可记为（A）。幂集性质：|A|n 则|(A)|2 n （8）n元有

19、序组与笛卡尔乘积元有序组与笛卡尔乘积 n元有序组是一种特殊的集合结构形式，它有两个基本概念与一种基本运算（笛卡尔乘积）。基本概念之一：有序偶。例：（a,b）基本概念之二：n元有序组。例：（a1,a2,an）基本运算：笛卡尔乘积。例：AB第五章 关系 关系研究集合内元素间的关联及集合间元素关联，主要有：一个基本概念 两种表示方法 三种运算 九个公式 五种性质 六种常用关系 5.1 5.1 关系基本概念关系基本概念 （1）一个主要的概念二元关系的基本概念：关系定义：关系定义：从集合A到B的关系R是A B的一个子集。（2）两种表示方法：集合表示法：集合表示法：有序偶的集合 图表示法：图表示法：有向图

20、5.2 5.2 关系运算关系运算（3）两种运算：关系的复合运算复合运算 关系的逆运算逆运算（4）有关运算的五个公式：复合运算的公式：复合运算的公式：(R S)TR (S T)Rm RnRm+n(Rm)nRmn 逆运算的公式：逆运算的公式：RR(R S)R S 5.3 5.3 关系重要性质关系重要性质（5）关系的五种性质 关系的自反性 关系的反自反性 关系的对称性 关系的反对称性 关系的传递性（6）六种常用关系 次序关系之一：偏序关系 次序关系之二：拟序关系 次序关系之三：线性次序关系 次序关系之四：字典次序关系 相容关系 等价关系5.4 5.4 闭包运算闭包运算（1）关系的闭包运算闭包运算 自

21、反闭包 r(R)对称闭包 s(R）传递闭包 t(R）（2）闭包的公式：闭包的公式：r（R）R s（R）RR t（R）Ri i=1 5.5 5.5 次序关系次序关系 （7）次序关系 四个定义：偏序关系：X上自反、反对称与传递的关系称偏序关系并用 表示。拟序关系：反自反、传递的关系称拟序关系并用 表示。线性次序关系：X上偏序关系R如有x,yx必有x y或y x则称R是X上线性次序关系。字典次序关系：有限字母表 上的偏序关系。如建立上的次序关系：设x=x1,x2,xn,y=y1,y2,ym；x,y*；x1,x2,xn,y1,y2,ym.（1）x1y1且如x1y1则我们说xLy；如y1x1，则我们说y

22、Lx；（2）如存在一个最大的K且Kmin(n，m)，使得x1y1，x2y2，xkyk而xk1yk+1，如果xk1yk1，则我们说xLy；如yk1xk1，则我们说yLx；（3）如存在一个最大的Kmin(n，m)，使得x1y1，x2y2，xnyn，此时如nm，则我们说xLy；如mn，则我们说yLx。四个次序关系间的关系：R是拟序则r(R)=R R是偏序则RQ是拟序 字典次序关系必为线性次序关系 R是拟序则必反对称 八个概念：最大元素（最小元素）极大元素（极小元素）上界（下界）上确界（下确界）5.6 5.6 相容关系相容关系 （8）相容关系 相容关系定义X上自反、对称关系称相容关系并用“”表示。相容

23、关系的极大相容块设有集合X上的相容关系，设A是X的子集，如A中任何元素都互为相容，且XA中的任何元素没有一个与A中的所有元素相容，则称A是X中的极大相容性分块。相容关系完全覆盖X上相容关系，它的极大相容性分块的集合称X的完全覆盖。5.7 5.7 等价关系等价关系 （9）等价关系 等价关系定义X上自反、对称、传递的关系称等价关系。等价类R是X上等价关系，对xX可构造一个X的子集xR 称为x 对R的等价类。划分S的子集A1，A2，An满足：Ai均分离(i=1，2，n)A1A2AnS则AA1，A2，An为S的划分，而Ai称为划分的块（i=1,2,n）。商集X上等价关系R所构成的类产生X的划分叫X关于

24、R的商集记以XR。第六章 函数 函数是一种特殊的关系，它在数学中具有普遍重要价值，函数主要内容有：一个基本概念 两种基本运算 三种性质函数 四种常用函数 6.1 6.1 函数的基本概念函数的基本概念 （1）一个基本概念函数的基本概念。函数建立了从一个集合到另一个集合的特殊对应关系。设有集合X与Y，如果我们有一种对应关系f，使X的任一元素x能与y中的一个唯一的元素y相对应，则这个对应关系f叫从X到Y的函数或叫从X到Y的映射。x所对应的y内的元素y叫x的像，而x则叫y的像源。上述函数我们可以表示成f：XY；或写成XY；以及yf（x）。（2）三种不同性质函数：满射与内射 一对一与多对一 一一对应（双

25、射）y1 y2 y3 y4 x1 x2 x3 x4 y1 y2 y3 y4 x1 x2 x3 x4 x5 y1 y2 y3 y4 x1 x2 x3 x4 X Yg X Yf X Yh 从图中可以看出函数f使得Y中的每个元素均有X中的元素与之对应，这种函数叫做从X到Y上的函数，否则叫做从X到Y内的函数。从图中可以看出，函数g使得不但X中的每一个元素xi唯一对应一个Y中的一个元素yj，而且也只有一个xi对应yj，也就是说一个像只有一个像源与之对应，这种函数叫做一对一的函数，否则叫做多对一的函数。从图中可以看出，函数h使得X与Y间建立了一对应的关系，这种函数叫X与了间一对应的函数。6.2 6.2 复

26、合函数、反函数、多元函数复合函数、反函数、多元函数 （3）两种运算：复合运算（复合函数）设函数f：XY，g：YZ则复合函数hgf：XZ是一个新的函数。定义：设函数f：XY，g：YZ，它们所组成的复合函数或叫复合映射gf，也是一个函数h：XZ，即：hg f：(x,z)|xX,zZ且至少存在一个yY，有y=f（x），zg（y）y1 y2 x1 x2 x3 z1 z2YXZhfg 逆运算（反函数）定义：定义：设f：XY是一对应的函数，则f所构成的逆关系叫f的逆映射或叫f的反函数，记以f1：Y X （4）函数分类：一元函数：f(x)二元函数：f(x,y)多元函数：f(x1,x2,xn)6.3 常用函数

27、常用函数（5）四种常用函数 常值函数：f(x)b 恒等函数：f(a)a 单调递增函数与严格单调递增函数：单调递减函数与严格单调递减函数：1 aA 特征函数：f(a)0 aA 第三篇 近世代数 代数系统是建立在集合论基础上以代数运算为研究对象的学科。本篇共三章，第五章代数系统基础介绍代数系统的一般原理与性质，第六章群论，主要介绍具有代表性的代数系统群，最后第七章其它代数系统，介绍除群外常见的一些代数系统，如环、域、格与布尔代数等，这三章相互配合构成了代数系统的完整的整体。第八章 代数系统 8.1 代数系统一般概念代数系统一般概念 1代数系统中的基本概念 （1）代数系统：集合上具有封闭性的运算组成

28、代数系统（S,）。（2）子代数：代数系统（S,），（S，）满足：SS 如 a,bS，ab=a b 则称（S，）为（S,）的子代数。8.2 代数系统常见的一些性质代数系统常见的一些性质（3）代数系统常见性质 1）结合律：（a b）ca （b c）2）交换律：a bb a 3）分配律：a （bc）（a b）（a c）4）单位元：a 1a 5）逆元：a a11 6）零元：a 00 7）生成元 8.3 同构与同态同构与同态 （4）同构：（X，）与（Y，）存在一一对应函数g:XY使得如x1,x2X，则有：g（x1 x2）g（x1）g（x2）此时则称（X,）与（Y，）同构。（5）同态：（X,）与（Y，）存

29、在函数g:XY使得如x1,x2X，则有：g（x1 x2）g（x1）g（x2）此时则称（X，）与（Y，）同态。8.4 常用代数系统常用代数系统 （6）代数系统的构成（一个二元运算 ）两个运算有逆元两个运算有单位元代数系统代数系统结合律 半群半群 单位元、逆元 群群循环群循环群可换群可换群变换群变换群子群子群循环半群循环半群单元半群单元半群可换半群可换半群整环整环域域商环商环理想理想有补格有补格有界格有界格布尔代数布尔代数正规子群、商群正规子群、商群特殊环特殊子环两个运算的单位元、逆元 （两个二元运算：,)两个运算的结合律、交换律、吸收律 格格 两个运算的分配律 分配格分配格单位元，无零因子（两个

30、二元运算：,)可换群,半群,对分配群 环环 交换律 可换环可换环 单位元,逆元交换律单位元生成元交换律生成元子集上的群特殊群特殊群第九章 群论 9.1 一些群的定义一些群的定义 （7）半群代数系统满足交换律 （8）单元半群半群存在单位元 （9）群半群存在单位元与逆元 （10）可换群群满足交换律 （11）变换群集合A上所有的变换构成的集合E（A），对于复合变换所构成的代数系统（E（A）,）是一个群，称变换群。（12）循环群群有生成元。（13）有限群：群（S,）中S为有限集。（14）子群：群（G，）上G的子集所构成的群。（15）正规子群：（H，）是群（G，）的子群，如对aG都有：aH=Ha则称（H

31、，）是（G，）的正规子群。（16）陪集：H是G的子群，Haha|hH,aH=ah|hH 分别称H在G中的一个右陪集或左陪集。（17）商群：H是G的正规子群，对Ha，HbG/H，二元运算（Ha)(Hb)Hab构成群，则称H是G的商群。（18）单元半群性质：单元半群的子系统若包含单位元也是单元半群。可列个元素的单元半群的运算组合表每行（列）均不相同。循环单元半群是可换单元半群。可换单元半群的所有等幂元素是一个子单元半群。9.2 一些群的理论与半群性质：一些群的理论与半群性质：半群的子代数也是半群。循环半群是可换半群。（19）关于群的基本理论 群方程可解性：a x=b（或x a=b）对x存在唯一解；

32、群的消去律：a b=a c（或b a=c a）必有b=c；任一群必与变换群同构；与一个群同构或满同态的代数系统必为群；一个代数系统有限群满足结合律及消去律则必为群；有限群必与置换群同构；循环群要么与（I,）同构，要么与（Zm，m）同构；一个群子集H构成群（H,o）的充分必要条件：a,bH 则a bH,aH 则a1 H；一个群子集H构成子群（H,o）的充分必要条件：a,b H 则a b1 H；一个有限群的阶一定被它的子群的阶所等分（拉格朗日定理）；f是群（G,）与（G，）的满同态，K是f的核，则必有：（G/k,）与（G，）同构；第十章 环论 10.1 环和域环和域 （20）环：（R，,），对的可

33、换群，对 的半群，对的分配律；（21）理想：（D，,），环（R，,）的子环，满足：aR,bD，必有：a bD,b aD；（22）整环：环（R，,）中，运算 有单位元，无零因子；（23）域：环（P，,）中，运算 交换律，有单位元，逆元；（24）环的基本理论 环的基本运算性质：a 0=0 a=0；a （b）=（a）b=（a b）(a)(b)a b 环中无零因子 环满足消去律；环中子系统S是子环的充要条件是as 则必有a1S。（25）域的基本理论 1）域是整环；2）有限整环必是域。第十一章 格与布尔代数 11.1 格与布尔代数格与布尔代数 （26）格：（P，,）中，两个运算的结合律、吸收律、交换律；

34、（27）布尔代数：格（B，,）中，两个运算的分配律、单位元、逆元。（28）格的基本理论 1）一个偏序格必是一个代数格，反之亦然；2）格的运算性质。aab,bab （aba,abb）ac且bc abc （ac且bccab）aba,abb （aab,bab）ca且cb cab（ca且cbcabc）（29）布尔代数的基本理论 布尔代数（B，）满足：（对与 ）交换律 结合律 等幂律 吸收律 分配律 零一律 同一律 互补律 双补律 德摩根律第四篇 图 论 图论用结点表示事物，而用边表示事物间联系，并用结点与边所构成的图用以研究客观世界。为便于计算，建立了图的矩阵表示，这样可以将图论研究与计算相结合，从而

35、使图论研究具有很大的实用性。由于图的形式很多，在实用中我们一般对若干种常用的图作研究，它们是树、平面图与两分图。在图论学习中主要要掌握如下几个方面：图论中的基本概念。图论中的基础理论。图的矩阵计算。几种常用的图。在本篇中共有两部分组成，它们是图论原理与常用图，其中图论原理部分介绍图的基本概念、理论与计算而常用图部分则介绍树、平面图与两步图等三种常用图，这两部分的有机结合构成了图论的完整的整体。第十二章 图论原理 12.1 12.1 图的基本概念图的基本概念 12.1.1 图图 12.1.2 图的基本概念图的基本概念 （1）图的概念 图由结点集Vv1，v2，vn与边集El1，l2，lm所组成，可

36、记为：G （2）有向图与无向图 边为有向的图称为有向图 边为无向的图称为无向图 （3）几种特殊的图 零图：无边的图。平凡图：仅有一个结点所组成的图。完全图：各结点间均有边相联的图。补图：G，G如有为完全图且EE，则称G为G的补图。简单图与多重图：包括多重边的图称为多重图，否则称为简单图。有权图：边带权的图。12.1.3 图的同构图的同构 同构图：G，G，V与V以及相应边的结点对中有一一对应关系。12.1.4 图中结点的次数图中结点的次数 （4）图中结点的次数 引入次数deg（v）、引出次数deg（v）、次数deg（v）。定理：deg（vi）=2mni 1 12.2 12.2 通路、回路与连通性

37、通路、回路与连通性 （5）通路与回路 通路：图中vi至vj的通路是在边的序列：（vi，vi1），（vi1，vi 2），（vi k1，vi k），其中vi kvj 基本通路与简单通路：图各边全不同的通路叫简单通路，各点全不同的通路叫基本通路。环与回路：边的始点与终点相同称环，通路的起始点与终止点相同称回路。简单回路与基本回路：简单（基本）通路的起始点与终止点相同称简单（基本）回路。有向图（n,m）的基本通路长度 n1，基本回路长度n。（6）图的连通性 图的可达性：图的结点vi到vj间存在通路则称从vi到vj是可达的。连通图：图的任何两结点间均可达。三种连通图：强连通：有向图中任何两结点间相互可达

38、则称强连通。弱连通：有向图忽略其边的方向所构成的无向图为连通则称弱连通。单向连通：有向图两结点间至少有一向是可达的则称单向连通。12.3 12.3 图的矩阵表示法图的矩阵表示法 （9）图的邻接矩阵：（10）通路计算：BA ，B（bij）nn，Bij表示从vi到vj长度为 l 的通路数，Bij表示vi的回路数。（11）可达性计算：PA（）A（2）（）（）A（n），P（Pij）n n，Pij表示从vi到vj是否可达（0不可达，1可达）。（12）连通性计算：可达性矩阵除对角线元素外均为1l第十三章 欧拉图与哈密尔顿图 13.1 13.1 欧拉图欧拉图 （7）欧拉图 欧拉回路与欧拉通路：通过G中每边一

39、次的回（通）路称欧拉回（通）路，具此回路的图称欧拉图。欧拉图与欧拉通路：欧拉图每个结点次数为偶数。由vi到vj欧拉通路vi，vj结点次数为奇数，其它结点次数为偶数。13.2 13.2 哈密尔顿图哈密尔顿图 （8）哈密尔顿图 哈密尔顿回路与哈密尔顿通路：通过G中每个结点一次的回（通）路称哈密尔回（通）路，具此回路的图称哈密尔顿图。哈密尔顿图与哈密尔顿通路中的定理 哈密尔顿图的必要条件G中V1V且P（GV1）|V1|，其中P（GV1）为从G中删除V1（包括V1中各结点及其关联边）后所得到的连通分支数。哈密尔顿图的充分条件：G无向简单图，|V|3，G中每结点对次数之和|V|。哈密尔顿通路：有向图D，

40、|V|2所有有向边均用无向边替代后得无向图含生成子图Kn。第十四章 特殊图 14.1 14.1 树树 14.1.1 14.1.1 树的基本性质树的基本性质 （13）树的基本概念与属性 树：不含回路的连通图。（n,m）树中必有mn1 树的性质 T为树两结点间只有一条通路。14.1.2 14.1.2 有向树有向树 （14）有向树 （15）外向树与内向树：有向树中，仅有一个结点引入次数为0（根），其它结点引入次数为1，有些结点引出次数为0（叶）称外向树。有向树中，仅有一个结点引出次数为0（根），其它结点引入次数为1，有些结点引入次数为0（叶）称内向树。14.1.3 14.1.3 二元树二元树 （16

41、）二元树与多元树：一个n个结点的外向树：（vi）m（i=1,2,n），称m元树。如（vi）m（i=1,2,n）（除叶外），称m元完全树，当m2时称二元树或二元完全树。14.1.4 14.1.4 生成树生成树 （17）生成树：连通图G的生成树TGG的子图，且是树并满足VV，EE。生成树寻找算法：在G中寻找基本回路，寻到后删除边，并继续寻找，直到无基本回路出现为止。14.2 14.2 两分图两分图 （21）两分图的概念：无向图G，有V1，V2V，V1V2，G中每一边e都有：e（vi，vj），viV1，vjV2，则称G为两分图。（22）两分图的判别法：图的所有回路长度为偶数。14.3 14.3 平面图平面图 14.3.1 14.3.1 平面图的基本概念平面图的基本概念 （18）平面图的概念：图的边间可不出现交叉称为平面图。14.3.2 14.3.2 平面图区域平面图区域 （n，m）连通平面图，区域数为r，必有：nmr2。（19）平面图区域性质 （n，m）连通平面图，且无环，边大于1，必有：m3n6。14.3.3 14.3.3 判别平面图的库拉托夫斯基定理判别平面图的库拉托夫斯基定理 （20）平面图的判别法（库拉托夫斯基定理）：图的任何子图都不可能减缩成下面两个图：