教学ppt课件：《离散数学导论(第5版)》

1离散数学导论（第5版）1离散数学导论（第5版）2第一篇概论本篇是对离散数学的宏观介绍。1 计算机学科与离散数学 介绍离散数学在计算机学科发展中的作用与关系，明确离散数学是掌握与研究计算机学科的基础理论与工具。2离散数学的特征 离散性 可构造性 抽象性 3离散数学的内容 离散数学的主要内容为：集合论 代数结构 图论 数理逻辑2第一篇概论本篇是对离散数学3离散数学导论（第5版）3离散数学导论（第5版）4第二篇 集合论本篇由集合论初步、关系、函数、有限集与无限集等与集合论相关等四部分内容组成，它们间是一个内容关联的整体。4第二篇集合论本篇5第1章 集合论初步集合论是数学的基础，也是离散数学的基础。故学好集合论十分重要，在本章学习中要掌握：集合中的一个基本概念 集合中的两种关系 集合中的三种特殊集合 集合中的三种表示方法 集合中的五种运算 集合中的21个常用公式5第1章集合论初步集合论是数学61.1集合论基本概念 （1）一一个个主主要要的的概概念念集集合合的的基基本本概概念念：一些不同确定的对象全体称集合，而这些对象称集合的元素。（2）集集合合中中的的两两个个关系关系 集合间的比较 关 系：A B，AB，AB，AB。集合与元素间的隶属关系：aA，aA。（3）三三种种特特殊殊的的集合集合 空集 全集E幂集（A）。61.1集合论基本概念（1）7（4）集合的三种表示法：集合的三种表示法：枚枚举举法法。即将集合元素一一列举。例：1,2,3,特特性性刻刻划划法法。即用元素的性质刻划集合。例：x|p(x)图图示示法法。即用文氏图表示集合及集合间的关系。例：AAB7（4）集合的三种表示法：AAB81.2集合运算（5）集合的五种运算：）集合的五种运算：交运算：AB倂运算：AB差运算：AB补运算：A对称差运算：AB81.2集合运算（5）集合的五种运算：9（6）集合的）集合的21个公式：个公式：交换律：交换律：ABBAABBA结合律：结合律：A（BC）（AB）CA（BC）（AB）C分配律：分配律：A（BC）（AB）（AC）A（BC）（AB）（AC）9（6）集合的21个公式：10同一律：同一律：AAAEA零一律：零一律：AEEA互补律：互补律：AAEAA双补律：双补律：（A）A10同一律：11E与与 的互补：的互补：EE等幂律：等幂律：AAAAAA吸收律：吸收律：A（AB）AA（AB）A狄狄莫根定律：莫根定律：（AB）AB（AB）AB11E与的互补：121.3幂集 幂集定义：集合A的所有子集所组成的集合，可记为（A）。幂集性质：|A|n则|(A)|2n121.3幂集幂集定义：集合A的所有子集所组成的集13第2章 关系关系研究集合内元素间的关联及集合间元素关联，主要有：一种预备知识 一个基本概念 两种表示方法 三种运算 九个公式 五种性质 六种常用关系13第2章关系关系研究集合内元素间的关联及集合间元素关联142.1关系的预备知识 n元有序组与笛卡尔乘积 n元有序组是一种特殊的集合结构形式，它有两个基本概念与一种基本运算（笛卡尔乘积）。基本概念之一：有序偶。例：（a,b）基本概念之二：n元有序组。例：（a1,a2,an）基本运算：笛卡尔乘积。例：AB142.1关系的预备知识n元有序组与笛卡尔乘积152.2 关系基本概念 （1）一个主要的概念二元关系的基本概念：关关系系定定义义：从集合A到B的关系R是A B的一个子集。（2）两种表示方法：集集合合表表示示法法：有序偶的集合 图表示法：图表示法：有向图152.2关系基本概念（1）一个主要的概念16 2.3关 系 运 算（3）两种运算：关系的复复合合运运算算 关系的逆运算逆运算（4）有关运算的五个公式：复合运算的公式：复合运算的公式：(RS)TR(ST)RmRnRm+n(Rm)nRmn 逆运算的公式：逆运算的公式：RR(RS)RS 162.3关系运算（3）两种运算：172.4 关系重要性质（5）关系的五种性质 关系的自反性 关系的反自反性 关系的对称性 关系的反对称性 关系的传递性172.4关系重要性质（5）关系的五种性质18（6）六种常用关系 次序关系之一：偏序关系 次序关系之二：拟序关系 次序关系之三：线性次序关系 次序关系之四：字典次序关系 相容关系 等价关系18（6）六种常用关系192.5 闭包运算（1）关系的闭包运闭包运算算 自反闭包 r(R)对称闭包 s(R）传递闭包 t(R）（2）闭包的公式：闭包的公式：r（R）RQs（R）RQt（R）Rii=1192.5闭包运算（1）关系的闭包运算i=1202.6 次序关系 （7）次序关系 四个定义：偏序关系：X上自反、反对称与传递的关系称偏序关系并用 表示。拟序关系：反自反、传递的关系称拟序关系并用表示。线性次序关系：X上偏序关系R如有x,yx必有xy或yx则称R是X上线性次序关系。字典次序关系：有限字母表 上的偏序关系。如建立上的次序关系：设x=x1,x2,xn,y=y1,y2,ym；x,y*；x1,x2,xn,y1,y2,ym.202.6次序关系（7）次序关系21（1）x1y1且如x1y1则我们说xLy；如y1x1，则我们说yLx；（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。21（1）x1y1且如x1y1则我们说xLy；如y1x22四个次序关系间的关系：R是拟序则r(R)=RR是偏序则RQ是拟序 字典次序关系必为线性次序关系 R是拟序则必反对称 八个概念：最大元素（最小元素）极大元素（极小元素）上界（下界）上确界（下确界）22四个次序关系间的关系：232.7 相容关系（8）相容关系 相容关系定义X上自反、对称关系称相容关系并用“”表示。相容关系的极大相容块设有集合X上的相容关系，设A是X的子集，如A中任何元素都互为相容，且XA中的任何元素没有一个与A中的所有元素相容，则称A是X中的极大相容性分块。相容关系完全覆盖X上相容关系，它的极大相容性分块的集合称X的完全覆盖。232.7相容关系（8）相容关系242.8 等价关系 （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关于R的商集记以XR。242.8等价关系（9）等价关系25第3章 函数函数是一种特殊的关系，它在数学中具有普遍重要价值，函数主要内容有：一个基本概念 两种基本运算 三种性质函数 四种常用函数25第3章函数函数是一种特殊26 3.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）三种不同性质函数：满射与内射 一对一与多对一 一一对应（双射）263.1函数的基本概念（1）一个基本概念函数的基27 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 XYgXYfXYh27y1x1y1x128从图中可以看出函数f使得Y中的每个元素均有X中的元素与之对应，这种函数叫做从X到Y上的函数，否则叫做从X到Y内的函数。从图中可以看出，函数g使得不但X中的每一个元素xi唯一对应一个Y中的一个元素yj，而且也只有一个xi对应yj，也就是说一个像只有一个像源与之对应，这种函数叫做一对一的函数，否则叫做多对一的函数。从图中可以看出，函数h使得X与Y间建立了一对应的关系，这种函数叫X与了间一对应的函数。28从图中可以看出函数f使得Y中的293.2 复合函数、反函数、多元函数 （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）293.2复合函数、反函数、多元函数30 y1 y2 x1 x2 x3 z1 z2YXZhfg30YXZhfg31 逆运算（反函数）定定义义：设f：XY是一对应的函数，则f所构成的逆关系叫f的逆映射或叫f的反函数，记以f1：Y X（4）函数分类：一元函数：f(x)二元函数：f(x,y)多元函数：f(x1,x2,xn)31逆运算（反函数）323.3常用函数（5）四种常用函数 常值函数：f(x)b恒等函数：f(a)a单调递增函数与严格单调递增函数：ab，必有f(a)f(b)：ab，必有f(a)f(b)单调递减函数与严格单调递减函数：ab，必有f(a)f(b)：ab，必有f(a)f(b)1aA特征函数：f(a)0aA323.3常用函数（5）四种常用函数33第4章 有限集与无限集 4.1 有限集与无限集基本概念有限集与无限集基本概念 （1）有限集与无限集的基本概念 有限集的两个定义 集合S与Nn一 一对应 非无限集即为有限集 无限集的两个定义 S与一 一对应函数f：SS使得：f(S)SS存在与其等势的真子集33第4章有限集与无限集344.2 有限集 （2）有限集 有限集的基数有限集元素个数 有限集的计数计算有限集中元素个数 有限集计数的四种方法：|AB|A|+|B|AB|A|+|B|AB|ABC|A|+|B|+|C|AB|AC|BC|+|ABC|S1S2Sn|Si|SiSj|SiSjSk|（1）|S1S2Sn|ni=11ijn1ijknn1344.2有限集ni=11ijn1ij354.3无限集 （3）四个常用的无限集：）四个常用的无限集：自然数集N 整数集I 有理数集Q 实数集R （4）无限集的势无限集的势 （5）无限集分类（按势分类）无限集分类（按势分类）自然数集自然数集 可可列列集集基基数数为为0 整整 数数 集集 无无限限集集 实实数数集集基基数数为为 有有理数集理数集 更大基数的集更大基数的集（A）354.3无限集36离散数学导论（第5版）36离散数学导论（第5版）37第三篇 代数系统代数系统是建立在集合论基础上以代代数数运运算算为为研研究究对对象象的学科。本篇共三章，第5章代数系统基础介绍代数系统的一般原理与性质，第6章群论，主要介绍具有代表性的代数系统群，最后第7章其它代数系统，介绍除群外常见的一些代数系统，如环、域、格与布尔代数等，这三章相互配合构成了代数系统的完整的整体。37第三篇代数系统代数系统是建38第5章 代数系统基础 5.1 代数系统一般概念代数系统一般概念 1代数系统中的基本概念 （1）代数系统：集合上具有封闭性的运算组成代数系统（S,）。（2）子代数：代数系统（S,），（S，）满足：SS 如 a,bS，ab=ab则称（S，）为（S,）的子代数。38第5章代数系统基础5.1395.2代数系统常见的一些性质（3）代数系统常见性质 1）结合律：（ab）ca（bc）2）交换律：abba3）分配律：a（bc）（ab）（ac）4）单位元：aea5）逆元：aa1e6）零元：a7）吸收律：a（ab）a；a（ab）a8）上界与下界：a1a；a00；a11；a0a；9）补元素：ab1；ab0395.2代数系405.3同构与同态（4）同构：（X，）与（Y，）存在一一对应函数g:XY使得如x1,x2X，则有：g（x1x2）g（x1）g（x2）此时则称（X,）与（Y，）同构。（5）同态：（X,）与（Y，）存在函数g:XY使得如x1,x2X，则有：g（x1x2）g（x1）g（x2）此时则称（X，）与（Y，）同态。5.4 常用代数系统常用代数系统 （6）代数系统的构成405.3同构与41（一个二元运算）上界、下界两亇补元素代数系统代数系统结合律半群半群单位元、逆元群群循环群循环群可换群可换群子群子群循环半群循环半群单元半群单元半群可换半群可换半群单元环单元环域域有补格有补格有界格有界格布尔代数布尔代数（两个二元运算：,)两个运算的结合律、交换律、吸收律格格两个运算的分配律分配格分配格单位元，（两个二元运算：,)可换群,半群,对分配群环环 交换律 可换环可换环,逆元交换律单位元生成元交换律生成元子集上的群41（一个二元运算）上界、下界42第6章 群论 6.1 一些群的定义一些群的定义 （7）半群代数系统满足交换律 （8）单元半群半群存在单位元 （9）群半群存在单位元与逆元 （10）可换群群满足交换律 （11）变换群集合A上所有的变换构成的集合E（A），对于复合变换所构成的代数系统（E（A）,）是一个群，称变换群。（12）循环群群有生成元。（13）有限群：群（S,）中S为有限集。（14）子群：群（G，）上G的子集所构成的群。42第6章群论6.1一些群的定43（15）正规子群：（H，）是群（G，）的子群，如对aG都有：aH=Ha则称（H，）是（G，）的正规子群。（16）陪集：H是G的子群，Haha|hH,aH=ah|hH分别称H在G中的一个右陪集或左陪集。（17）商群：H是G的正规子群，对Ha，HbG/H，二元运算（Ha)(Hb)Hab构成群，则称H是G的商群。（18）单元半群性质：单元半群的子系统若包含单位元也是单元半群。可列个元素的单元半群的运算组合表每行（列）均不相同。循环单元半群是可换单元半群。可换单元半群的所有等幂元素是一个子单元半群。43（15）正规子群：（H，）是群446.2群的性质：（19）半群性质 半群的子代数也是半群。循环半群是可换半群。（20）关于群的基本理论 群方程可解性：a x=b（或x a=b）对x存在唯一解；群的消去律：a b=a c（或b a=c a）必有b=c；任一群必与变换群同构；与一个群同构或满同态的代数系统必为群；一个代数系统有限群满足结合律及消去律则必为群；446.2群的性质：（19）半群性质45有限群必与置换群同构；循环群要么与（I,）同构，要么与（Zm，m）同构；一个群子集H构成群（H,o）的充分必要条件：a,bH 则a bH,aH 则a1 H；一个群子集H构成子群（H,o）的充分必要条件：a,b H 则a b1H；一个有限群的阶一定被它的子群的阶所等分（拉格朗日定理）；f是群（G,）与（G，）的满同态，K是f的核，则必有：（G/k,）与（G，）同构；45有限群必与置换群同构；46第7章 环、格与布尔代数 7.1 环论环论 （21）环：（R，,），对的可换群，对的半群，对的分配律；（22）可換环：满足交换律的环；（23）域：环（P，,）中，运算交换律，有单位元，逆元；46第7章环、格与布尔代数7.147（24）环的基本理论 环的基本运算性质：a0=0a=0；a（b）=（a）b=（ab）(a)(b)ab 环中无零因子 环满足消去律；环中子系统S是子环的充要条件是as则必有a1S。（25）域的基本理论 1）域是整环；2）有限整环必是域。3)域满足消去律47（24）环的基本理论487.2格与布尔代数（26）格：（P，,）中，两个运算的结合律、吸收律、交换律；（27）偏序格：P上的偏序关系所组成的偏序集(P，)对P的任意子集均有上确界与下确界，则称(P，)为偏序格。（28）布尔代数：格（B，,）中，两个运算的分配律、单位元、逆元。487.2格与布尔代数（26）格：（P，,）中49（28）格的基本理论 1)格满足幂等律；2)格的子代数必为格；3)格满足对偶律；4）一个偏序格必是一个代数格，反之亦然；49（28）格的基本理论50（29）布尔代数的基本理论 布尔代数（B，）满足：（对与）交换律 结合律 等幂律 吸收律 分配律 零一律 同一律 互补律 双补律 德摩根律50（29）布尔代数的基本理论51(30)布尔函数1)B=0,1上的函数：f：BnB称为布尔函数。2)布尔表达式：由0,1，布尔变元经补、和、积可构成布尔表达式。3)布尔积之和展开式。4)布尔函数可以用一个布尔积之和展开式表示。51(30)布尔函数52离散数学导论（第5版）52离散数学导论（第5版）53第四篇 图 论 图论用结点表示事物，而用边表示事物间联系，并用结点与边所构成的图用以研究客观世界。为便于计算，建立了图的矩阵表示，这样可以将图论研究与计算相结合，从而使图论研究具有很大的实用性。由于图的形式很多，在实用中我们一般对若干种常用的图作研究，它们是树。在图论学习中主要要掌握如下几个方面：53第四篇图论图论用54图论中的基本概念。图论中的基础理论。图的矩阵计算。几种常用的图。在本篇中共有两部分组成，它们是图论原理与常用图，其中图论原理部分介绍图的基本概念、理论与计算而常用图部分则介绍树与欧拉图。这两部分的有机结合构成了图论的完整的整体。54图论中的基本概念。55第8章 图论原理 8.1 8.1 图的基本概念图的基本概念 8.1.1 图图 8.1.2 图的基本概念图的基本概念 （1）图的概念 图由结点集Vv1，v2，vn与边集El1，l2，lm所组成，可记为：G（2）有向图与无向图 边为有向的图称为有向图 边为无向的图称为无向图55第8章图论原理8.1图56（3）几种特殊的图 零图：无边的图。平凡图：仅有一个结点所组成的图。完全图：各结点间均有边相联的图。补图：G，G如有为完全图且EE，则称G为G的补图。简单图与多重图：包括多重边的图称为多重图，否则称为简单图。有权图：边带权的图。56（3）几种特殊的图57 8.1.3 图的同构图的同构 同构图：G，G，V与V以及相应边的结点对中有一一对应关系。8.1.4 图中结点的次数图中结点的次数 （4）图中结点的次数 引 入 次 数deg（v）、引出次数deg（v）、次数deg（v）。定理：deg（vi）=2m578.1.3图的同构588.2 通路、回路与连通性 （5）通路与回路 通路：图中vi至vj的通路是在边的序列：（vi，vi1），（vi1，vi2），（vik1，vik），其中vikvj基本通路与简单通路：图各边全不同的通路叫简单通路，各点全不同的通路叫基本通路。环与回路：边的始点与终点相同称环，通路的起始点与终止点相同称回路。简单回路与基本回路：简单（基本）通路的起始点与终止点相同称简单（基本）回路。有向图（n,m）的基本通路长度 n1，基本回路长度n。588.2通路、回路与连通性59（6）图的连通性 图的可达性：图的结点vi到vj间存在通路则称从vi到vj是可达的。连通图：图的任何两结点间均可达。三种连通图：强连通：有向图中任何两结点间相互可达则称强连通。弱连通：有向图忽略其边的方向所构成的无向图为连通则称弱连通。单向连通：有向图两结点间至少有一向是可达的则称单向连通。59（6）图的连通性60 9.2 9.2 欧拉图欧拉图 （15）欧拉图 欧拉回路与欧拉通路：通过G中每边一次的回（通）路称欧拉回（通）路，具此回路的图称欧拉图。欧拉图与欧拉通路：欧拉图每个结点次数为偶数。由vi到vj欧拉通路vi，vj结点次数为奇数，其它结点次数为偶数。609.2欧拉图61 8.3 图的矩阵表示法 （7）图的邻接矩阵：G为（n，m）图，其邻接矩阵：A（aij）nn.1（vi，vj）Eaij 0（vi，vj）E （8）通路计算：BA，B（bij）nn，Bij表示从vi到vj长度为 的通路数，Bij表示vi的回路数。（9）可达性计算：PA（）A（2）（）（）A（n），P（Pij）nn，Pij表示从vi到vj是否可达（0不可达，1可达）。（12）连通性计算：可达性矩阵除对角线元素外均为1618.3图的矩阵表示法62第9章 常用图 9.1 9.1 树树 9.1.1 9.1.1 树的基本性质树的基本性质 （10）树的基本概念与属性 树：不含回路的连通图。（n,m）树中必有mn1 树的性质 T为树两结点间只有一条通路。9.1.2 9.1.2 有向树有向树 （11）有向树 62第9章常用图9.1树63 （12）外向树与内向树：有向树中，仅有一个结点引入次数为0（根），其它结点引入次数为1，有些结点引出次数为0（叶）称外向树。有向树中，仅有一个结点引出次数为0（根），其它结点引入次数为1，有些结点引入次数为0（叶）称内向树。9.1.3 9.1.3 二元树二元树 （13）二元树与多元树：一个n个结点的外向树：（vi）m（i=1,2,n），称m元树。如（vi）m（i=1,2,n）（除叶外），称m元完全树，当m2时称二元树或二元完全树。9.1.4 9.1.4 生成树生成树 （14）生成树：连通图G的生成树TGG的子图，且是树并满足VV，EE。生成树寻找算法：在G中寻找基本回路，寻到后删除边，并继续寻找，直到无基本回路出现为止。63（12）外向树与内向树：有向树中，仅有一个结64 9.2 9.2 欧拉图欧拉图 （15）欧拉图 欧拉回路与欧拉通路：通过G中每边一次的回（通）路称欧拉回（通）路，具此回路的图称欧拉图。欧拉图与欧拉通路：欧拉图每个结点次数为偶数。由vi到vj欧拉通路vi，vj结点次数为奇数，其它结点次数为偶数。649.2欧拉图65离散数学导论（第5版）65离散数学导论（第5版）66第五篇 数理逻辑 数理逻辑是用数学方法研究形式逻辑演绎推理规则的科学，它是一门数学，是一门研究演绎推理规则的数学，在学习此部分时，主要要掌握如下几个要点：思维的形式化 指派法 公式推理 公理系统 范式 自动定理证明 66第五篇数理逻辑数理逻辑是用数学方法研67 本篇由命题逻辑、谓词逻辑、公理化理论部分组成，其中命题逻辑以命题为研究对象而谓词逻辑则以谓词为研究对象，而公理化理论则是数理逻辑中演绎推理的形式化思想的介绍，它们的有机结合构成完整的整体。67本篇由命题逻辑、谓词逻辑、公理化理论部分组68第10章 命题逻辑 命题逻辑以命题为对象，研究命题的符号体系及推理规则。10.1 10.1 命题与命题联结词命题与命题联结词（1）命题能判别真假的语句。（2）基本命题联结词否定、并且、或者、蕴含、等价。10.2 10.2 命题公式命题公式（3）命题公式由命题及命题联结词构成命题公式。10.3 10.3 重言式重言式（4）指派命题公式中变元的一组确定的值。（5）重言式所有指派均取值为真的公式。68第10章命题逻辑命题逻辑以命题为对象，研究命题的符6910.4 命题逻辑基本等式及等式推理（6）等式推理：由三部分组成：它们是基本等式、推理规则及推理过程。（7）命题逻辑42个基本等式。交换律 PQQP；PQQP；PQQP 结合律 （PQ）RP（QR）；（PQ）RP（QR）；（PQ）RP（QR）分配律 P（QR）（PQ）（PR）；P（QR）（PQ）（PR）；6910.4命题逻辑基本等式及等式推理（6）等式推理：由70否定深入PP；（PQ）PQ；（PQ）PQ；（PQ）PQ；(14)（PQ）PQPQ；变元等同PPP；PPP；PPF；PPT；PPT；PPP；PPP；PPT；PPPPF；70否定深入71常值与变元的联结TPP；FPF；TPT；FPF；TPP；FPT；PTT；PFP；TPP；FPP；71常值与变元的联结72联结词化归PQ（PQ）；PQ（PQ）；PQPQ；PQ（PQ）（QP）其它PQQP(PQ)（PR）PQRP（PQ）PP（QR）PQRP（PQ）P72联结词化归73（8）推理规则：代入规则 替换规则(9)推理过程 由P到Q的推理过程是一个等式序列：P=P1 P1=P2 Pn-1=Pn Pn=P73（8）推理规则：7410.5 命题逻辑基本蕴含式及蕴含推理（10）蕴含推理是单向推理，它有三部分组成：前提已知条件证明是一种过程定理结论(11)蕴含推理组成：基本蕴含式推理规则证明过程7410.5命题逻辑基本蕴含式及蕴含推理（10）蕴含推75（9）19个基本蕴含重言式 PQP；PQQ；P PQ；QPQ；PPQ；QPQ；（PQ）P；（PQ）Q；75（9）19个基本蕴含重言式76 P（PQ）Q；Q（PQ）P；P（PQ）Q；Q（PQ）P；(PQ)(QR)PR；(PQ)(RS)PRQS；(PQ)(PR)(QR)R；P(QPQ)；(PQ)(QR)(PR)；(P(QR)(Q(PR)；(PQ)(RQ)(PRQ)76P（PQ）Q；77 （13）11个推理规则 PQP；PQQ；PPQ；QPQ；P，QPQ；P，PQQ；P，PQQ；Q，PQP；PQ，QRP R；PQ，RSPR QS；PQ，PR，QRR；77（13）11个推理规则78(14)(14)证明过程证明过程 是一个公式序列并运用三个规则：P规则 T规则 CP规则10.6 10.6 范式范式 （15）范式命题公式的一种标准形式 （16）主析取范式：该范式是一个析取式，每个析取项是所有命题变元式其否定的合取式。（17）主异合取范式：该范式是一个合取式，每个析取项是所有命题变元式其否定的析取式。78(14)证明过程7910.8 命题联结词的扩充与归约 （18）命题联结词的扩充异或：、谢佛：、魏泊：、蕴含否定：（19）命题联结词的归约命题联结词可归约为如下形式之一：,7910.8命题联结词的扩充与归约80第11章 谓词逻辑 谓词逻辑基本概念11.1 11.1 谓词与个体谓词与个体（1）个体 个体常量与个体变量 个体域与全总个体域（2）谓词 一元谓词刻划个体性质 二元谓词刻划两个个体间关系 n元谓词刻划n个个体间关系80第11章谓词逻辑谓词逻辑基本概念81 11.2量词（3）存在量词：x P(x)“有一些”之语义（4）全称量词：x P(x)“所有”之语义（5）量词的辖域量词所作用的范围11.3 11.3 函数函数（6）函数个体间的特定关系称函数，它是个体间的映射。f(x)中X是个体而f为函数符号，f(x)为函数。8111.2量词（3）存在量词：xP(x)“8211.4 谓词逻辑公式 （7）谓词逻辑公式 项：个体是项，函数是项 原子公式：P（t1,t2,tn）是原子公式（其中ti为项）公式：原子公式是公式；A，B是 公 式，则（A）,（AB）,（AB）,（AB），（AB）是公式；A是公式，x为个体变量，则（xA），（xA）为公式；公式由且仅由有限次使用前面三步而得。8211.4谓词逻辑公式8311.5 自由变元与约束变元 （8）谓词公式中的自由变元与约束变元 谓词公式中的自由变元与约束变元 约束变元的改名规则改名在量词变元及其辖域中该变元的约束出现处进行且该变元不在量词辖域内出现过。自由变元的代入规则代入在公式的自由变元出现的每一处进行且该代入变元不允许在式中以任何约束形式出现。8311.5自由变元与约束变元8411.6 谓词逻辑永真公式 （9）谓词逻辑永真公式定义 谓词公式的解释与赋值 （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）8411.6谓词逻辑永真公式85xP（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）85xP（x）Qx（P（x）Q）86（12）谓词逻辑的蕴含永真公式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）86（12）谓词逻辑的蕴含永真公式8711.7 谓词逻辑等式推理(13)有三部分组成：基本等式 推理规则代入规则与替换规则 推理过程等式序列11.11.谓词逻辑蕴含推理谓词逻辑蕴含推理(1)谓词逻辑蕴含推理是单向推理，有三部分组成：前提 证明推理规则与证明过程 定理8711.7谓词逻辑等式推理(13)有三部分组成88（）谓词逻辑蕴含推理组成：推理规则：规则规则规则规则 证明规则：规则规则规则88（）谓词逻辑蕴含推理组成：89 11.11.谓词逻辑范式谓词逻辑范式 （1）前束范式公式的所有量词均非否定的出现在公式最前面，它的辖域一直延伸至公式末尾，且公式中不出现与。（1）斯科林范式前束范式的首标处仅出现全称量词且 公 式 中 不 出 现 自 由 变 元x1x2xnM（x1,x2,x n）8911.谓词逻辑范式90第12章 数理逻辑公理化理论12.1 12.1 公理化理论的基本思想公理化理论的基本思想（1）公理系统的两个部分 公理系统的组成与推理 公理系统的讨论：不矛盾性 完整性 独立性90第12章数理逻辑公理化理论12.1公理化理论的基9112.2 命题逻辑与谓词逻辑的公理化理论（1）命题逻辑永真公理系统的组成、组成部分 命题：P1，P2，Pn；命题联结词：，；个体常量：a，b，c，x，y，z；个体变量：P，Q，R；函 数：f，g，h；谓 词：，；括 号：（，）9112.2命题逻辑与谓词逻辑的公理化理论（1）命题92 项：个体常量是项；个体变量是项；f是n元函数，t1，t2，,tn是项，则f(t1，t2，,tn)是项；项由且仅由有限次使用、而得。92项：93 原子公式：P是n元谓词，t1，t2，tn是项，则P（t1，t2，tn)是原子公式。命题逻辑公式：命题是公式；P是公式则（P）是公式；P，Q是公式则（PQ），（PQ），（PQ），（PQ）是公式；公式由且仅由有限次使用，而得。93原子公式：P是n元谓词，t1，t2，tn是项94 谓词逻辑公式：原子公式是公式；A，B是公式则：（A），（AB），（AB），（AB）,（AB）是公式；A是 公 式 则（xA），（xB）是公式；公式由且仅由有限次使用、而得。94谓词逻辑公式：95 推理部分 1）公理 如P，Q，R为公式，则有下述的公理：PP；（P（QR）（Q（PR）；（PQ）（QR）（PR）；（P（PQ）（PQ）；（PQ）（PQ）；（PQ）（QP）；95推理部分96（PQ）（QP）（PQ）；PQQ；PQP；P（QPQ）；PPQ；QPQ；（QP）（RP）（QRP）；（PQ）（QP）；PP；111213141596（PQ）（QP）（PQ）；1112131497 2）推理规则 分离规则：PQ，PQ。3）证明（过程）与定理 证明（过程）给出了公理系统中定理生成的过程，它是一个公式序列：P1，P2，Pn，其中每个Pi（i1，2，n）必须满足下条件之一。972）推理规则98 Pi是公理；Pi是 由 Pk，Pr，（k，ri）施行分离规则而得。最后，PnQ 即为定理。（）导出规则如有AB为定理则必有AB。（）假设推理 具有特定环境下的假设作前提 推理定理设有A1，A2，AnB，则必有：A 1,A2,An-1An B。98Pi是公理；99 假设推理的证明过程必须满足：i是假设前提；i是公理；i是由k，Pr用分离规则而得 最 后。Pn=B，而 （n B）为定理。99假设推理的证明过程必须满足：100（）额外假设推理反证法 以结论为假设作前提 反证推理定理：设有A1，A2，An，BPP，则必有：A1(A2(AnB）3 反证推理证明过程必须满足 1)Pi是公理；2)Pi是假设；3)Pi是待证定理B的否定，即为P；4)Pi是由Pk，Pr用分离规则而得。最后Pn=PP，而此时：A1(A2(AnB）为定理。100（）额外假设推理反证法101 （23）谓词逻辑永真公理系统 1系统组成部分 2推理部分 1）公理 设P，Q，R为公式，则有公理如下：101（23）谓词逻辑永真公理系统102 pp（P（QR）（Q（PR）（PQ）（QR）（PR）（P（PQ）（PQ）（PQ）（PQ）（PQ）（QP）（PQ）（QP）（PQ）PQQ102pp103 PQP P（QPQ）PPQ QPQ （QP）（RP）（QRP）（PQ）（QP）PP xP（x）P（x）P（x）xP（x）。11121314151617103PQP11121314151617104 2）推理规则 分离规则：PQ，PQ.全 称 规 规：QP（x）QxP（x）存 在 规 则：P（x）Qx P（x）Q 上面17个公理与3个规则中有15个公理与1个规则是命题逻辑公理系统的，真正属谓词逻辑的仅有2个公理与2个规则。1042）推理规则105 3）证明（过程）与定理。证明（过程）是一个公式序列：P1，P2，Pn，其中每个Pi（i1，2，n）必须满足下条件之一：Pi是公理；Pi是由Pk，Pr，（k，ri）施行分离规则而得；Pi是由Pk（ki）施行全称规则而得；Pi是由Pk（ki）施行存在规则而得。最后，PnQ 即为定理。1053）证明（过程）与定理。106(24)谓词逻辑的假设推理与反证推理。谓词逻辑的推理定理与命题逻辑一致。谓词逻辑的假设推理与命题逻辑一致。谓词逻辑的反证推理与命题逻辑一致。106(24)谓词逻辑的假设推理与反证推理。107 12.3 12.3 数数理理逻逻辑辑应应用用公公理理系统系统(25）数理逻辑公理化应用系统的定义：1 公理 永真公理 学科领域的公理 2 推理规则 永真公理系统推理规则 3 证明过程 1)Pi是永真公理；2)Pi是学科领域公理；3)Pi用分离规则而得；4)Pi用全称或存在规则而得。最后Pn=Q即为定理。10712.3数理逻辑应用公理系统10812.4 谓词逻辑的自动定理证明（26）子句与Horn子句（27）消解原理 将一公式化为Horn子句集 采用消解原理，即由S为公理证明E为定理的过程可改写：作SSUE为公理；从E开始在S中不断使用反驳法；最后出现空子句口则结束；如空子句出现则表示公式为真。（28）PROLOG语言及其他逻辑语言10812.4谓词逻辑的自动定理证明（26）子句与Ho109离散数学导论（第5版）109离散数学导论（第5版）110第六篇 离散建模离散建模是利用离散数学为工具建立计算机学科的数学模型以利于问题的求解。本篇共两章：第十三章：离散建模的概念与方法 第十四章：离散建模应用实例介绍110第六篇离散建模离散建111第1 3章 离散建模概念13.1 13.1 离散建模概念离散建模概念 客观世界问题抽象成形式化数学表示数学模型。数学模型的建立过程数学建模。可数集上的数学模型离散模型。离散模型的建立过程离散建模。客观世界问题域的求解离散模型计算。111第13章离散建模概念13.1离散建模概念11213.2 离散建模方法(1)问题形成。(2)离散建模离散模型的形成。(3)离散模型计算离散模型解的形成。(4)解的语义化问题域解的形成。11213.2离散建模方法(1)问题形成。11313.3 离散建模方法五个步骤(1)问题域形成 客观世界中离散建模的注视点。(2)离散建模及模型的形成。离散语言选择，形式化表示等。(3)离散模型的检验与修改。(4)离散模型计算 通过计算对离散模型求解，解的表示为数学形式。(5)解的语义化 解的数学形式转换成问题域中的语义形式，从而获得问题域的解。11313.3离散建模方法五个步骤(1)问题域形114第1 4章 离散建模应用实例14.1 14.1 数字逻辑电路的离散建模数字逻辑电路的离散建模(1)问题域形成 研究对象两种信号。研究方法三种电路。需求电路设计、电路简化及简化门电路类型。(2)模型建立 离散语言布尔代数。逻辑电路布尔代数表达式。(3)模型计算 电路设计积之和展开式。电路简化布尔代数优化。简化门电路运算符转换。114第14章离散建模应用实例14.1数字逻辑电路11514.2 电话线路故障影响分析的离散建模(1)问题域形成 研究对象城市。研究内容电话线路。需求线路故障对通话的影响。(2)模型建立 离散语言图论。离散模型图结构。(3)模型计算 用图的矩阵计算。线路故障对通话的影响图的可达性矩阵计算。11514.2电话线路故障影响分析的离散建模(1)问题11614.3 关系数据模型离散建模关系代数(1)问题域形成 研究对象数据表。研究内容数据表上的操作。需求数据表示，操作表示，简化及标准化。(2)离散模型1关系代数 离散语言关系代数。离散模型关系代数表达式。(3)模型计算 数据及操作表示关系代数表达式。操作简化表达式优化。操作标准化表达式规范化。11614.3关系数据模型离散建模关系代数(1)11714.3 关系数据模型离散建模关系演算(1)问题域补充 需求数据操作的表示，简化及查询。(2)离散模型2 关系演算 离散语言谓词逻辑。离散模型谓词公式。(3)模型计算 数据操作表示谓词公式。操作简化等式推理。查询蕴含推理。11714.3关系数据模型离散建模关系演算(1)11814.4操作系统死锁检测离散建模(1)问题域形成 研究对象资源与进程。研究内容进程与资源间的占有关系 需求无限时的占有等待。(2)模型建立 离散语言图论。离散模型图模型中的可达性(3)模型计算可达性矩阵计算。D 1死锁；D 0未死锁间间11814.4操作系统死锁检测离散建模(1)问题域形成间间