《2022年2022年离散数学知识汇总 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年离散数学知识汇总 .pdf（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、i 离散数学笔记第一章命题逻辑合取析取定义1. 1.3 否定：当某个命题为真时，其否定为假，当某个命题为假时，其否定为真定义1. 1.4 条件联结词，表示“如果那么”形式的语句定义1. 1.5 双条件联结词，表示“当且仅当”形式的语句定义1.2.1 合式公式(1)单个命题变元、命题常元为合式公式，称为原子公式。(2)若某个字符串A 是合式公式，则A、(A) 也是合式公式。(3)若 A、B 是合式公式，则A B、AB、AB、AB 是合式公式。(4)有限次使用 (2)(3)形成的字符串均为合式公式。1.3 等值式1.4 析取范式与合取范式名师资料总结 - - -精品资料欢迎下载 - - - - -
2、 - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 14 页 - - - - - - - - - ii 将一个普通公式转换为范式的基本步骤名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 14 页 - - - - - - - - - iii 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 14
3、 页 - - - - - - - - - iv 1.6 推理定义1.6.1 设 A 与 C 是两个命题公式，若 A C 为永真式、重言式 ，则称C 是 A 的有效结论，或称A 可以逻辑推出C，记为A = C。 （用 等值演 算或 真值表 ）第二章谓词逻辑2.1、基本概念?：全称量词?：存在量词一般情况下，如果个体变元的取值范围不做任何限制即为全总个体域时，带 “全称量词”的谓词公式形如?x(H(x) B(x) ，即量词的后面为条件式，带“存在量词”的谓词公式形如?x(H(x) WL(x) ，即量词的后面为合取式例题R(x)表示对象x 是兔子， T(x) 表示对象x 是乌龟，H(x,y) 表示x
4、 比 y 跑得快， L(x,y) 表示 x 与 y 一样快，则兔子比乌龟跑得快表示为：?x?y(R(x) T(y) H(x,y) 有的兔子比所有的乌龟跑得快表示为： ?x?y(R(x) T(y) H(x,y) 2.2、谓词公式及其解释定义2.2.1、 非逻辑符号：个体常元 (如 a,b,c)、 函数常元 (如表示22yx的 f(x,y) 、 谓词常元 (如表示人类的H(x) 。定义2.2.2、逻辑符号 ：个体变元、量词(?)、联结词 (?)、逗号、括号。定义2.2.3、项的定义：个体常元、变元及其函数式的表达式称为项(item)。定义2.2.4、原子公式 ：设 R(nxx.1)是 n 元谓词，
5、ntt.1是项，则R(t)是原子公式。原子公式中的个体变元，可以换成个体变元的表达式(项)，但不能出现任何联结词与量词，只能为单个的谓词公式。定义2.2.5 合式公式 ：(1)原子公式是合式公式；(2)若 A 是合式公式， 则(A)也是合式公式； (3)若 A,B 合式，则 AB, AB, AB , A?B 合式 (4)若 A 合式，则?xA、?xA 合式 (5)有限次使用 (2)(4)得到的式子是合式。定义2.2.6 量词辖域 ：?xA 和?xA 中的量词?x/?x 的作用范围， A 就是作用范围。定义2.2.7 约束变元 ：在?x 和?x 的辖域A 中出现的个体变元x，称为约束变元，这是与
6、量词相关的变元，约束变元的所有出现都称为约束出现。定义2.2.8 自由变元 ：谓词公式中与任何量词都无关的量词，称为自由变元，它的每次出现称为自由出现。一个公式的个体变元不是约束变元，就是自由变元。注意： 为了避免约束变元和自由变元同名出现，一般要对“约束变元”改名，而不对自由变元改名。定义2.2.9 闭公式是指不含自由变元的谓词公式名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 14 页 - - - - - - - - - v 从本例 (已省 )可知，不同的公式在同一个
7、解释下，其真值可能存在，也可能不存在，但是对于没有自由变元的公式 (闭公式 )，不论做何种解释，其真值肯定存在谓词公式 的类型：重言式(永真式 )、矛盾式 (永假式 )、可满足公式三种类型定义2.2.10 在任何解释下，公式的真值总存在并为真，则为重言式或永真式。定义2.2.11 在任何解释下，公式的真值总存在并为假，则为矛盾式或永假式。定义2.2.12 存在个体域并存在一个解释使得公式的真值存在并为真，则为可满足式。定义2.2.13 代换实例设nppp,.,21是命题公式0A中的命题变元，nAAA,.,10是 n 个谓词公式，用iA代替公式0A中的ip后得到公式A，则称A 为0A的代换实例。
8、如 A(x) A(x) ，?xA(x)? xA(x) 可看成p p 的代换实例， A(x)A(x) ，?xA(x) ?x A(x)可看成p p 的代换实例。定理2.2.1 命题逻辑的永真公式之代换实例是谓词逻辑的永真公式，命题逻辑的永假公式之代换实例是谓词逻辑的永假式。 （代换前后是同类型的公式）2.3、谓词公式的等值演算定义2.3.1 设 A、B 是两个合法的谓词公式，如果在任何解释下，这两个公式的真值都相等，则称A 与 B 等值，记为A B。当 AB 时，根据定义可知，在任何解释下，公式A 与公式B 的真值都相同，故A?B 为永真式，故得到如下的定义。定义2.3.2 设 A、B 是两个合法
9、谓词公式，如果在任何解释下，A? B 为永真式，则 A 与 B 等值，记为A B。一、利用代换实例可证明的等值式(p?p 永真，代换实例? xF(x)? xF(x) 永真 ) 二、个体域有限时，带全称量词、存在量词公式的等值式如：若 D=naaa,.,21，则? xA(x) A(1a)A(2a)A(na) 三、量词的德摩律1、?xA(x) ?xA(x) 2、?xA(x) ?xA(x) 四、量词分配律1、?x(A(x) B(x) ?xA(x) ?xB(x) 2、?x(A(x) B(x) ?xA(x) ?xB(x) 记忆方法 ：?与，一个尖角朝下、一个尖角朝上，相反可才分配。2 式可看成1 式的对
10、偶式五、量词作用域的收缩与扩张律A(x) 含自由出现的个体变元x，B 不含有自由出现的x，则有：1、?/?(A(x) B) ?/?A(x) B 2、?/?(A(x) B) ?/?A(x) B 对于条件式A(x)?B， 利用“基本等值一”将其转换为析取式，再使用德摩律进行演算六、置换规则若 B 是公式A 的子公式，且B C，将 B 在 A 中的每次出现，都换成C 得到的公式记为D，则A D 七、约束变元改名规则将公式A 中某量词的指导变元及辖域中约束变元每次约束出现，全部换成公式中未出现的字母，所得到的公名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - -
11、 - - - - - 名师精心整理 - - - - - - - 第 5 页，共 14 页 - - - - - - - - - vi 式记为B，则A B 例证明步骤：2.4、谓词公式的范式从定理证明过程，可得到获取前束范式的步骤：(1)剔除不起作用的量词；(2)如果约束变元与自由变元同名，则约束变元改名；(3)如果后面的约束变元与前面的约束变元同名，则后的约束变元改名；(4)利用代换实例，将、?转换表示；(5)利用德摩律，将否定深入到原子公式或命题的前面；(6)利用量词辖域的扩张与收缩规律或利用量词的分配律，将量词移到最左边2.5、谓词推理定义2.5.1 若在各种解释下BAAAn.21只能为真即
12、为永真， 则称为前提nAAA.21可推出结论B。定义2.5.2 在所有使nAAA.21为真的解释下， B 为真，则称为前提nAAA.21可推出结论B。谓词逻辑的推理方法分为以下几类：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 14 页 - - - - - - - - - vii 一、谓词逻辑的等值演算原则、规律：代换实例、量词的德摩律、量词的分配律、量词辖域的扩张与收缩、约束变元改名。二、命题逻辑的推理规则的代换实例，如假言推理规则、传递律、合取与析取的性质律、CP
13、规则、反证法等。三、谓词逻辑的推理公理第三章集合与关系3.1、基本概念在离散数学称“不产生歧义的对象的汇集一块”便构成集合。常用大写字母表示集合，如 R 表示实数，N 表示自然数，Z 表示整数，Q 表示有理数， C 表示复数。 描述一个集合一般有“枚举法”与 “描述法”，“枚举法”。元素与集合之间有“属于”或“不属于”二种关系。定义3.1.1 设 A，B 是两个集合，如果A 中的任何元素都是B 中的元素，则称A 是 B 的子集，也称B 包含于A，记为BA，也称A 包含 B，记为AB。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - -
14、 名师精心整理 - - - - - - - 第 7 页，共 14 页 - - - - - - - - - viii 3.2 集合运算性质定义3.2.1 设 A、B 为集合， A 与 B 的并集AB、A 与 B 的的交集AB、A-B 的定义：AB=x|xAxB ，AB=x|xAxB ，A-B=x|xAxB 定 义 3.2.2 设 A、 B 为 集 合 ， A 与 B 的 对 称 差 ， 记 为 AB=x|(xAxB)( x AxB)= AB - AB。定义3.2.3 设 A、B 是两个集合，若AB、BA 则 A=B ，即两个集合相等。幂等律AA=A 、AA=A 结合律ABC= A(BC)= (A
15、B)C ABC= A(BC)= (AB)C 交换律AB=BA、AB=BA 分配律A(BC)=(AB)(AC) A(BC)=(AB)(AC) 同一 /零律A? = A 、A?= ? 排中 /矛盾律AA=E 、AA= ? 吸收律 (大吃小 ) A(BA)=A 、 A(BA)=A 德摩律(AB)= A B 、(AB)= AB 双重否定A=A 3.3、有穷集的计数定理3.3.1 二个集合的包含排斥原理|21AA| = |1A| + |2A| - |21AA| 3.4、序偶定义3.4.2 令 与是二个序偶，如果x=u、y=v ，那么 = 即二个序偶相等。定义3.4.3 如果 是序偶，且 ,z 也是一个序
16、偶，则称 为三元组。3.5、直积或笛卡尔积定义3.5.1 令 A、B 是两个集合，称序偶的集合|xA, yB 为 A 与 B 的直积或笛卡尔积， 记为 AB。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 14 页 - - - - - - - - - ix 如：A=1,2,3 ，B=a,b,c 则 AB=1,2,3a,b,c=, 直积的性质1、A(BC)= A B A C 2、A (BC)= A B A C 3、(BC) A = B AC A 4、(B C) A = B
17、A C A 5、ABA C B C C A C B 6、AB,CDA C B D 定义3.5.2 令nAAA,.,21是 n 个集合，称n 元组的集合 | nnAxAxAx,.,2211 ，为nAAA,.,21的直积或笛卡尔积，记为nAAA.21。3.6、关系定义3.6.1 称直积中部分感兴趣的序偶所组成的集合为“关系”，记为R。如在直积 1,2,3,4,5,6,7,81,2,3,4,5,6,7,8 中，只对第1 个元素是第2 个元素的因数的序偶感兴趣，即只对R=, , , , , , , ，RAA（A=1,2,3,4,5,6,7,8 ）定义3.6.2 如果序偶或元组属于某个关系R，则称序偶或
18、元组具有关系R。关系图，关系矩阵3.7、关系的复合定义3.7.1 若关系FAA，关系GAA，称集合 |t 使得 F，G 为 F 与 G 的复合，记为FG。例题3.7.1 令 A=1,2,3 ，F=, G=,则解：FG= , ，GF=, ， 因此关系的复合不满足交换律。采用复合的定义去计算，只适合于人工计算，为了编程实现，故采用矩阵表示关系。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 14 页 - - - - - - - - - x 说明：FM的第i 行与GM的第j 列
19、相乘时，乘法是合取，加法是析取，如MF 的 1 行与MG 的第3 列相乘是： (11)(10)(00)，结果为1。定义3.7.2 若关系FAA，称集合 |F 为 F 的逆，记为1F例题3.7.2 令 A=1,2,3 ，F=,，则1F= ,。3.8、关系的分类定义3.8.1 若Ax都有 R，则 R 是自反关系 。(自己到自己的关系全属于R) 定义3.8.2 若Ax都有 R,则 R 是反自反 的。(自己到自己的关系全不属于R) 定义3.8.4 如果所有形如 的序偶都在关系R 中， R 也只有这种形式的序偶，则称R 为恒等关系，记为AI。对于恒等关系而言，其关系矩阵是单位矩阵，即其主对角线全是1，其
20、他位置全是0，对关系图是每个点都有自旋，仅只有自旋，没有其他边。定义3.8.5 令关系 RAA，如果当 R 时R，则称R 为对称关系 。定义3.8.6 令关系 RAA，如果当 R 且 xy 时R， 则称R 为反对称关系 。定义3.8.8 令关系 RAA，若当 R,R 时有R，则称 R 为可传递关系 。从 RR 的关系矩阵可知，其非0 元素在 R 的关系矩阵都出现，即RRRMM，凡满足这个不等式的关系，肯定为可传递关系。所以不可传递。从 RR 的关系矩阵可知，其非0 元素出现在 (1,1)，(1,3)，(2,2)，(2,4)，在R 的关系矩阵都没出现，不满足RRRMM，不可传递关系。名师资料总结
21、 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 14 页 - - - - - - - - - xi 3.9、关系的闭包将关系矩阵的主角线上全部变成1， 即得到其 自反闭包 的关系矩阵，从而可得到其自反闭包。3.10、等价关系与集合的划分定义3.10.1 设 RAA，如果R 是自反、对称、可传递的关系则称为等价关系 。定义3.10.2 设 RAA，如果R 是等价关系，BA， B 中任意二个元素之间都有关系R，则 B 是一个等价类 。定义3.10.3 设 RAA， R 是等价关系，kA
22、AA,.,10是基于R 得到的等价类， 则称集合 kAAA,.,10为 A 关于R 的商集 ，记为A/R。定义3.10.3 若110,.,kAAA是 A 的子集， 若ji时jiAA，并且110.kAAAA，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 14 页 - - - - - - - - - xii 则称kAAA,.,10是 A 的一个划分 。定理3.10.1 设 RAA ，R 是等价关系，110,.,kAAA是利用R 得到的k 个不同的等价类，则110,.,kA
23、AA为集合A 的划分。定理3.10.2 设110,.,kAAA是 A 的划分，R=111100.kkAAAAAA， 则 R 是等价关系。3.11、偏序关系定义3.1 1.1 设 RAA ，如果R 是自反、反对称、可传递的关系则称为 偏序关系 。如： R 是实数中小于等于关系，则R 是偏序关系。定义3.1 1.2 设 RAA ，R 偏序关系， x 与 y 是 A 中的元素，若序偶 与 至少有一个在R 中，则称x 与 y 可比 。定义3.1 1.3 设 RAA，R 偏序关系，若A 中任意二个元素都可比，则称A 为全序关系 或线序关系。定义3.1 1.4 设 RAA ，R 偏序关系，将关系图绘制成所
24、有箭头都朝上，然后去掉所有箭头、去掉自旋边、去掉复合边 ，得到关系图的简化形式，称为哈斯图 。定义3.1 1.5 在哈斯图中，如果某个元素y 在元素x 的直接上方，则称y 盖住了 x。记 COVA= 定义3.1 1.6 设 RAA，R 偏序关系，将偏序关系与集合A 一块称为偏序集，记为 ，表示是A 上的偏序关系。以后说偏序关系时，可简单地说偏序集 。定义3.1 1.7 在偏序集 中，BA，yB，若Bx都有 R，则称y 是最大元 。即最大元与B 中每个元素都可比，并且都比其大。定义3.1 1.8 在偏序集 中，BA，yB，若Bx都有 R，则称y 是最小元 。即最小元与B 中每个元素都可比，并且都
25、比其小。一个子集中没有最大元或最小元时，可能存在极大元或极小元。定义3.1 1.9 在偏序集 中，BA，yB，若不存在xB 使得 R，则称y 是极大元 ， 即 B 中不存在比 y“大”的元素。即极大元与B 中有些元素是否可比不做要求。定义3.1 1.10 在偏序集 中，BA，yB，若不存在xB 都有 R，则称y 是极小元 ，不存在比y 小的元素。即极小元与B 中元素是否可比不做要求。定义3.1 1.1 1 在偏序集 中， BA，yB，若任意 xB 都有 R，则称 y 是 B 的上界 。与 B 中每个元素都可比，并且都B 中的元素大。3.12、其它关系定义 3.6.1 给定集合A 上的关系 ，若
26、 是自反的 、对称的 ，则称 是 A 上的相容关系。定义3.6.3 给定非空集合A ，设有集合S=nSSS,.,21 ，其中ASi且iS， i=1,2, ,m, 且)(jiSSji，则称集合S 称作 A 的覆盖。定理 3.6.1 给定集合A 的覆盖，nSSS,.,21，由它确定的关系：nnSSSS.11是相容关系。定义 3.7.1 设 R 为定义在集合A 上的一个关系，若R 是自反的，对称的，传递的，则R 称为等价关系 。(显然名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页
27、，共 14 页 - - - - - - - - - xiii 等价关系一定是相容关系)。定义3.7.2 设给定非空集合A，若有集合S=nSSS,.,21 ，其中ASi且iS(i=1,2,m) ，且有)(jiSSji，同时有ASimi1，则称 S为 A 的一个划分。 (所有子集的并为A，且子集的交为空，则这些子集组成的集合为A 的一个划分，覆盖中，子集的交集可不为空) 等价类商集偏序关系 (自反性，反对称性，传递性),A，哈斯图，可比的，元素y 盖住元素x，全序关系，极大元，极小元，最大元，最小元拟序关系 (反自反的，传递的),A第四章代数系统定义4.3.1 设是集合S 上的二元运算，若Syx,
28、都有 xy=yx，则称在S 上是可交换的，或者说运算在S 上满足 交换律 。定义4.3.2 设是集合S 上的二元运算， 若Syx,都有 (xy)z=x(yz)， 则称在S 上是可结合的,或者说运算在S 上满足 结合律 。定义4.3.3 设是集合S 上的二元运算， 若Sx都有xx=x ，则称在S 上是幂等的 ,或说运算在S 上满足幂等律。定义4.3.4 设与 * 是集合S 上的二种运算，若Syx,都有x*(y z)=(x*y) (x*z) 与(yz)*x=(y*x) (z*x) ，则称 * 对 是可分配的 。定义4.3.5 设与 *是集合S 上的二种可交换的二元运算，若Syx,都有x*(x y)=x 与 x(x*y)=x 则称*与是满足 吸收律 ，内外二种运算不一样，运算符内外各出现一次，以多吃少。广群：半群：群：子群：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 14 页 - - - - - - - - - xiv 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 14 页 - - - - - - - - -