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