离散数学笔记Discrete Mathematics
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
------------------------------------------------------------------- Design By 2100301629王家寧
第一章 集合
1.集合的运算
①补运算
②对称差运算
2.集合运算的性质
①集合运算的基本恒等式
可用文氏图进行相关推导
重点记忆德摩根律和补交转换律 ⑩和⑪
德摩根律补集分配进括号里面就把括号里面的交并符号反过来
补交转换律交补连着写可以换成差
在证明题中可以使用假设X来进行代入来证明也可以通过举反例来列出具体的实例来推翻命题
②容斥原理
容斥原理由来将相容重的集合部分在计算并集集合的基数的时候进行排斥出去故称容斥原理
基数集合中元素的个数
第二章 关系
1.序偶与笛卡尔积
序偶中有几个元素就叫做几元序偶
笛卡尔积的定义
笛卡尔积的性质
笛卡尔积不满足交换律和结合律但是对交和并都满足分配律
2.关系的定义
几种特殊的关系空关系、全域关系、恒等关系
关系的定义域和值域
3.关系的表示
关系图通过有向弧的方式表示
关系矩阵表示法
4.关系的性质
①自反性与反自反性
②对称性与反对称性
对称性和反对称性并非对立关系
③传递性
关系性质的判别
5.关系的基本运算
关系是一种特殊的集合因此集合的基本运算对关系也同样适用
6.关系的复合运算
复合关系的关系矩阵
矩阵相乘是将前矩阵的第一行分别和后矩阵的各列进行相乘并相加得到新矩阵的第一行元素
这里改为布尔与和布尔或运算是因为有时运算结果是2或者更多但是实际上是一个序偶所以结果为一
复合运算满足并运算的分配律但是不满足交运算的分配律
7.关系的逆运算
将元素对调矩阵转置即为关系的逆运算
逆运算的性质
8.关系的幂运算
R的零次幂就是A上的恒等关系
关系的幂运算的关系矩阵示例
幂运算的性质简言之有限集A上的关系R的幂序列R的0~n次幂是一个周期变化的序列n无穷大
也就是鸽巢原理 如果有n+1个鸽子飞进了n个鸽巢中那么必定有鸽巢中至少飞进了2只鸽子。
9.关系的闭包运算
三种闭包运算也即添加最少序偶元素来让序偶集合符合自反、对称、传递关系的运算
自反闭包 r(R)
对称闭包 s(R)
传递闭包 t(R)
闭包运算的性质
10.等价关系
①等价关系的定义
满足自反、对称、传递的关系即为等价关系
②等价类的定义
等价类后面的括号里包括自身
11.商集
①商集的定义
特别的可以记一下A关于恒等关系还有全域关系的商集
不要记错商集是共有的后边的元素而不是等价类
也就是满足特定关系的各个划分的集合共同组成一个新的集合
②划分的定义
特别的一一对应的商集和划分对应某等价关系的商集所形成的划分叫做由该等价关系导出的等价划分
由某划分确定的等价关系称为由该划分所导出的等价关系
通过划分求对应的等价关系
通过划分的各个集合求笛卡尔积之后再求并集所得结果即为所求等价关系
通过等价关系求对应划分
通过等价类导出对应的商集所得商集即为所求等价划分
12.偏序关系
①偏序关系的定义
自反的、反对称的、传递的。
可比与盖住的定义
X、Y符合关系则为可比的
不存在中间元素则为盖住
13.哈斯图和特殊关系
①哈斯图的定义以及绘制步骤
②特殊元素
最大元和最小元
极大元与极小元
总结与分辨
上界与下界
上确界与下确界
总结与分辨
第三章 函数
1.函数的定义
①函数的定义
②函数与关系的区别
③函数的特点
④函数的数量问题
2.特殊函数
①特殊函数的分类
单射函数、满射函数、双射函数
②特殊函数的必要条件
③特殊函数的数量
3.函数的运算
①函数的基本运算
函数是一种特殊的关系因此关系的所有运算都适用于函数如集合的基本运算、关系的复合运算和逆运算等。但运算的结果并不一定都是函数 如下基本运算就不是函数
②函数的复合运算
函数是一种特殊的关系能进行关系的复合运算。函数经复合运算之后仍然是函数。
③函数复合的性质
④逆运算的定义
⑤复合函数的实例洗牌
⑥复合函数与逆函数的实例凯撒密码
第四章 命题逻辑
1.命题
①命题的定义
②简单命题/原子命题
③复合命题
2.命题联结词
否定联结词 ¬
合取联结词 ∧
析取联结词 ∨
蕴含联结词 → 前真后假方为假
等价联结词 ↔ 同真同假方为真
3.命题符号化及其应用
命题符号化一般分为三个步骤
①简单命题的符号化
②联结词的符号化
③“联结”简单命题
4.命题公式和真值表
①命题常量和命题变元定义
②成真赋值和成假赋值
③真值表
5.命题公式的分类
①重言式/永真命题公式
任何情况下均为真
②可满足公式
至少存在一种为真的情况
重言式是特殊的可满足公式
③矛盾式/永假命题公式
在任何情况下均为假
6.命题公式的逻辑等值及应用
①命题公式的等值式
②基本等值式
可以和集合的交并补等操作进行互换
重点 ⑪~⑯ 德摩根律、蕴含等值式、等价等值式、假言易位逆否、等价否定等价式逆否、归谬论
③等值演算
在等值演算的时候要注意符号的优先级确定好式子的前界和后界
同时也要合理使用结合律来简化操作去除括号
优先级越高越放在最后看先看优先级低的将其转化为优先级高的
证明两个公式等值
简化公式
也可以再写一步蕴含等值式得出¬p∨r
等值演算也可以用来判断公式的类型重言式、矛盾式等
示例
7.范式
①简单析取式和简单合取式
简单析取式和简单合取式的定义
并不一定要把所有命题变元否定给用上给了三个用两个也可以
②合取范式
合取范式的定义
同样不要求把所有的命题单元否定都给用上
③命题公式的范式求解
任何命题公式都存在与之等值的析取范式和合取范式但是不一定唯一
重点 蕴涵等值式、等价等值式、双重否定律
示例
④命题公式的范式应用
示例例题
首先把各种能达到齐全功能的选择方案进行合取这里是根据题意进行操作来得到原始式子
之后通过命题公式的规律求解得到 命题范式这里是 简单析取式
其中简单合取式子里面的 每一个命题单元就是 一个方案
8.主范式
①极小项和极大项
极小项简单合取式中每个命题变元和其否定不同时出现但是一定要出现一个
极大项简单析取式中每个命题变元和其否定不同时出现但是一定要出现一个
n个命题变项可以生成个极小项和
其中从 0,0,0开始赋值此时的符号表示为此后依次赋值递增
极小项为 成真赋值 极大项为 成假赋值
极小项是合取 极大项是析取
极大项和极小项的成真赋值和成假赋值彼此之间进行取非一一对应如上图
②极小项和极大项的性质以及对应关系
③主析取范式
每个 简单合取式都是该 n个命题变元的 极小项也就是 简单合取式一定要有所有 命题变元的 本身或者 其否定然后再进行合取但不是同时有只要有一个其本身和其否定不能同时出现
任何命题公式都存在与之等值的唯一主析取范式
主析取的意思就是括号最外边是析取同理合取
主析取范式的求解步骤
主要使用排中律进行求解添项
主析取范式的求解示例
可以看到这里 第三步使用了 同一律是关键进行了 单一命题变元的补项之后再进行分配化简 消去相同元素即可
④主合取范式
每个 简单析取式都是该 n个命题变元的极大项也就是 简单析取式一定要有所有 命题变元的 本身或者 其否定然后再进行合取但不是同时有只要有一个其本身和其否定不能同时出现
任何命题公式都存在与之等值的唯一主合取范式
主合取的意思就是括号最外边是合取同理析取
主合取范式的求解步骤
主要使用同一律和矛盾律进行求解添项
主合取范式的求解示例
第四步应该是 同一律而非 分配律
可以看到这里 第四步使用了 同一律是关键进行了 命题变元的补项之后再进行分配化简 消去相同元素即可
其中符号下标的表示可以参考极小项和极大项的对应表格
⑤主范式相关关系
如题可以发现主合取范式的符号表示正好和主析取范式的符号表示在0~7之间互补因此可以复习一下之前的知识点
主范式的根据命题单元的个数n决定数量其个数为2 n
主析取范式使用小写表示
主析取范式的下标和 主合取范式的下标在 0~2 n -1范围内互补 正如上题所示
互补的原因是
极大项和极小项的成真赋值和成假赋值彼此之间进行取非
因为 极小项是 合取所以只有 一个成真赋值而 极大项是 析取只有 一个成假赋值
它们两个彼此 一一对应
所以当 主合取范式的 极小项确定之后 主析取范式只要避开对应的 成假赋值的极大项就行
可以参考 四.8.①表格
详细证明如下
⑥主范式的作用
通过求解主析取范式和主合取范式 可以统一表示某个问题的表达
因为其 具有唯一的主范式通过此唯一的主范式 可以求出其对应的成真赋值和成假赋值
因此 可以判断命题公式的类型重言式、矛盾式、非永真式的可满足式
判断命题公式是否等值当且仅当其具有相同的主析取范式/主合取范式
因此也便于计算机求解相关问题
简记
小m全有为重言式/永真式
大M全有为矛盾式
只有一部分则非永真式的可满足式
⑦主范式的实际应用
派人问题
9.简单证明推理
①推理的基本形式定义
②永真/重言蕴含式的定理及定义
③简单证明推理例题
如上例题将所有前提以及结论使用命题公式表示出来再进行交集操作因为要保证这些要同时成立
之后解法有三
①利用等值演算
②利用主析取范式和主合取范式
③利用真值表
p: A地发生了交通事故q: 小李的通行发生困难r: 小李按指定时间到达
其中第二行的 q∨r的消去是先转化为 q Λr
因为小李通行发生困难时一定不能按时到达所以 q Λr 为假所以 q Λr 为真原式为真
倒数第二行 p Λ q也是同理
10.构造证明推理
引言
①构造证明推理定义
基于 永真蕴含式或 推理规则进行的命题公式的推理称为 构造证明推理
②构造证明推理规则
重点记忆
③置换规则
①前提引入规则:在证明的任何步骤上都可以引入前提②结论引入规则:在推理中若一个或一组前提已证出结论B则B可引入到以后的推理中作为前提使用。③置换规则:在推理过程的任何步骤上命题公式中的任何命题公式都可以用与之等值的命题公式置换。
④直接构造证明推理
⑤间接构造证明推理
也就是将所求结论的前界加入到前提之中形成析取命题公式之后继续推导结论的后界为真即可
除上述两种方法之外还可以使用归谬法来证明原命题的正确性也即把结论取反然后和前提进行等值演算得出其结果为0假
第五章 谓词逻辑
1.谓词逻辑的基本概念
①个体词的定义
个体词→个体常量、个体变量
个体域→全总域
②谓词定义
谓词常量
谓词变量
n元谓词特殊的有0元谓词
谓词的使用示例
由此可得谓词的值域为 {1,0}如上述第二个例子假如把 南宁改为 河南则值为0
③函词
函词的定义
函词对应一般意义下的 函数 n元函词就是对应 n元函数只不过 函词的元素从 数变成了 个体词
定义域为 个体域的笛卡尔积 函词的 值域为个体域
值得注意的是n元谓词也是一个n元函数其区别在于前者的值域为 {1,0}而后者的值域为 个体域
函词和谓词的区别
函词使用小写谓词使用大写
函词是映射谓词表示特定的性质或者关系
函词通常是是什么谓词通常是的什么或者在......北方之类的
④量词
一、全称量词
第二个 交运算表达方式不对的原因
使用蕴含符号时意思为 x是人所以x是要死的
使用交运算符号 ∧时意思为 x是人并且x是要死的
交运算体现不出来前提条件
二、存在量词
这里使用蕴含而非逻辑交的道理同上
2.谓词符号化
①谓词符号化的常用规则
②谓词符号化应用机器人移盒子问题
3.谓词公式
①项
项的定义
②原子谓词公式
可以类比 简单公式/原子公式
③谓词逻辑公式
④约束变元和自由变元
辖域/作用域/约束域、作用变元/指导变元、约束出现/约束变元、自由出现/自由变元
- 约束变元和自由变元示例
在不造成公式冲突的情况下可以更改一个或者多个变元的符号
这样可以使原得公式更为清晰明了
4.谓词公式的解释和分类
①谓词公式的解释定义
示例
由此可见根据不同的解释谓词公式在其解释下的取值有所不同这里可以类比第四章的命题公式的成真、成假赋值
②谓词公式的分类
永真谓词公式、可满足谓词公式、永假谓词公式
在谓词逻辑中谓词公式的解释依赖于个体域导致了真值表法在判断一个谓词公式的类型时很难实施。
5.谓词公式的逻辑等值
①谓词公式的等值式
②谓词公式的代换实例
通过使用 谓词公式代换 命题变元所得到的 谓词公式称为其对应的一个 代换实例
注 可满足公式的代换实例不一定是可满足式
③命题逻辑等值式的推广
注意这里的全称量词和存在量词要保持一致
注意这里的A(x)里面的x为自由变元因为要保证其确定性所以取任何值不能影响其结果不能只在一部分情况下适用
⑤量词消去律
全称量词也就是对任意的个体变元都适用在这里我们使用交集
存在量词也就是存在一个个体变元使用在这里我们使用并集
注意在这里量词的顺序很重要顺序不同结果不同因此并不能随意的调换
A(x)是谓词公式并不要简单的理解为原子谓词公式
- 示例
⑥量词与否定的交换律
也就是量词和否定转换之后量词的全称和存在属性要改变
⑦量词辖域收缩与扩张律
就是贴一块儿而已简单感觉没必要记但是还是写一下
⑧量词分配律和双量词交换律
注意第三、四条的X和Y的变化
- 例题示例
6.前束范式
①前束范式的定义
前束范式、母式
前束范式可以类比前面的主范式但是是两个完全不同的东西互通的方面也不是很多
任何谓词公式都存在与之等值的前束范式但是并不唯一因为前面的量词位置可以不同约束变元的表达形式也可以不同
②前束范式的求法原理
- 示例
7.谓词逻辑推理
在谓词逻辑中谓词公式的推理依赖于个体域求解谓词公式在各种解释下的真值往往非常繁琐甚至异常困难
这就导致了命题逻辑中的简单证明推理在谓词逻辑中不容易实施
在谓词逻辑中的推理通常是基于永真蕴含式或构造逻辑推理
①谓词逻辑推理的基本形式
可以类比命题逻辑推理的基本形式
②简单证明推理
可以转换为 重言式的证明或者 矛盾式的证明
矛盾式也就是将重言式的蕴含式使用蕴涵等值式之后将左侧的非再进行代入如下图
也可以代入实例
命题逻辑中的推理规则也可用在谓词逻辑的构造证明推理中。
③构造证明推理规则
构造证明推理可以有效解决苏格拉底假言三段论的问题
以下为多出来的有关量词的消去规则
注意约束变元的限制条件
选择一个常数a进行代入就可以
US规则
UG规则
同样选择一个常数a代入就可以
ES规则
EG规则
- 示例
不能交换的原因③是由②所得来的是存在量词③具有特殊性而④是由①推导来的是全称量词④具有一般性
特殊可以满足一般但是一般不一定满足特殊而 c又已经确定为同一个因此该顺序不能交换
④附加前提证明法
在谓词逻辑的推理中如果结论是以蕴含式形式给出则蕴含式的前件可作为推理的前提使用。
- 例题示例
⑤反证法/归谬法
结论的否定引入
- 示例例题
- 上下册分分界线
第六章 代数系统
1.代数系统的基本概念
①代数运算的定义及其性质
唯一性、全域性、封闭性
- 代数运算的判断示例
模K加法
模K乘法
②运算表
③代数系统的定义
④子代数系统的定义
- 示例及其证明
2.代数运算的基本性质
交换律、结合律、分配律
①交换律
是否满足交换律也可以通过看运算表是否对称的方式来判断
②结合律
③分配律
注意区分左可分配、右可分配
④幂运算的定义
注意其中示例的运算方法要根据具体的代数系统来进行操作
- 实例
3.代数运算的吸收律性质
问题引入如何像交并、析取合取一样抽象表述代数运算的吸收律
吸收律简记括号内外的运算不同而括号外有和括号内相同的部分则不同的部分B被吸收只留下相同的部分A
在运算系统中还要注意其左右位置
这里的*和Δ仅仅表示二元运算
这里说*对Δ是左可吸收的也就是指*是在括号的外面而Δ在括号的里面同理可得右可吸收的
- 实例
4.代数运算的幂等律和消去律
①幂等律定义
也就是二元运算作用于个体域中的每一个对象之后结果还是它本身那就符合幂等律
②消去律定义
也就是等式相同可以推到得出等式同项相消除留下来的部分相等
- 示例
5.代数运算的特殊元素
①等幂元
在某个代数系统中某个元素通过代数运算之后结果还等于它自身则该元素就是关于该运算的等幂元
- 示例
②零元
任何元素和一个特定元素进行二元运算之后的结果始终等于该特殊元素则该特殊元素称为零元
零元也有左右之分
零元必为等幂元
零元具有唯一性因为不能有两个特殊元素保证运算后和自身相等
运算表中某元素是等幂元的充要条件是该元素在对角线上的取值为其本身
运算表中某元素是零元的充要条件是该元素对应的行、列元素均与该元素相同
③单位元
任何元素和一个特殊元素进行二元运算所得结果都为选取的任何元素则该特殊元素称为代数系统的单位元
幺元也必为等幂元
单位元也有左右之分
单位元又称为幺元
幺元也具有唯一性同理零元
- 幺元的求法
假设代入求解法此方法也适用于其他代数运算的特殊元素
④逆元
某元素和另一个元素进行二元运算所得结果为单位元e则该元素称为某元素的逆元
逆元也有左右之分
每个元素的逆元都是唯一的
元素逆元的逆元是其本身
- 实例
⑤可消去元
定义
如果a存在逆元则a就是可消去元证明如下
⑥特殊元素求解
等幂元求解、零元求解
单位元求解、幺元求解
逆元求解
可消去元求解
6.同构代数系统
引入使用双射函数来表示两个结构相同的代数系统之间的关系
①同构代数系统定义
证明代数系统同构要构造出其符合的双射函数
②同构代数系统的证明
③自同构代数系统
④自同构映射示例
⑤代数系统同构关系性质
代数系统的同构关系是等价关系
这里函数是有具体含义的不能直接换给另一个用
- 同构代数系统的概念可以推广到含有多个代数运算的代数系统
7.同态代数系统
引入两个代数系统没有完全相同的结构但存在一些相似的性质
①同态代数系统的定义
设函数f是代数系统<S,﹡>到<T,◦>的同态映射则同态像f(S)是集合T的非空子集。
- 示例
②自同态代数系统
- 示例
N 6中的元素为012345
自同态映射的证明最关键的一步
③同态核
设函数f是代数系统<S,﹡>到<T,◦>的同态映射则同态核Ker(f)是集合S的非空子集。
同态核可以用来求解子代数系统
注意 f(x)的结果要是 幺元才行
8.同态映射的性质
引子
①可交换性和可结合性对应
②单位元和零元一一对应
③逆元和等幂元一一对应
- 示例
④代数系统同态的意义
⑤同态概念推广
9.代数系统的应用
引入问题分析
①同余关系
②国际标准书号校验码
第七章 典型代数系统
1.半群和子半群
①半群的定义
查看是否有结合性判断半群
- 示例
②半群的性质
③子半群的定义
根据封闭性判断是否是子半群
2.独异点和子独异点
①独异点的定义
根据幺元判定独异点
②子独异点的定义
根据子群、相同幺元、封闭性判断子独异点
3.群
①群的定义
根据结合律、幺元、逆元判定群
③群的阶数定义、无限群
④元素的阶数
④群的应用 Klein四元群
4.群的性质
①性质一
幺元是唯一的等幂元
②性质二
G中至少有两个元素时不存在零元
③性质三
V a,b∈G 如果a*b =b或者b*a=b 则a是关于运算“*”的幺元。
④性质四
任一元素都是可消去元
⑤性质五
待转换公式
⑥性质六
待转换公式
⑦性质七
待转换公式
⑧⑨性质八九
待转换公式
群性质的应用
5.子群
①子群的定义
②子群的求解
6.子群的性质
性质一
性质二
性质三
- 示例
性质四
有限子群的判定方法
性质五
拉格朗日定理
子群性质的应用 Klein
Klein
7.交换群和循环群
①交换群的定义
②循环群的定义
③循环群的判定
- 示例
8.循环群的性质
- 示例
9.群的应用
引入
奇偶校验码
汉明距离定义
汉明距离性质
- 实例
第八章 图论基础
1.图的基本概念
①无序对、无序序偶、无序积
②图的阶数、有向边、无向边、自环、关联边
- 示例
③重复边、重数
④图的分类定义
2.子图
①子图的定义
②生成子图的定义
④导出子图的定义
示例
3.握手定理
①节点度数定义
②握手定理
- 推论
- 示例
③握手定理的应用
4.图的同构
①图的同构定义
②图同构的必要条件
③同构实例
5.通路和回路
①通路和回路的定义
②通路和回路的性质
示例
6.图的连通性
①无向图的连通性
②连通分支
③有向图的连通性
弱连通图、单向连通图、强连通图
弱连通分支、单向连通分支、强连通分支
④示例
7.图的操作
①删除边
②删除结点
③收缩边
示例
8.图的表示
①关联矩阵表示
②邻接矩阵表示
③可达矩阵表示
9.赋权图和最短通路问题
①赋权图定义
②边权矩阵定义
③最短通路问题
- 示例
④最短通路问题的应用-设备更新问题
10.欧拉图及其应用
①哥尼斯堡七桥问题
②欧拉图定义
③欧拉图的判定
无向欧拉图的判定定理
有向欧拉图的判定定理
④欧拉图的应用
蚂蚁赛跑问题
道路清扫车问题
11.哈密顿图及其应用
引入
①哈密顿图定义
②哈密顿图的判定
③哈密顿图的判定定理
④哈密顿图的应用
欧拉图和哈密顿图的对比
第九章 树
1.无向树
①无向树定义
②树的性质定理
- 推导证明
④树的应用
2.生成树
问题引入
①生成树的定义
②生成树的性质
③生成树算法
3.最小生成树及其应用
问题引入
①最小生成树定义-边赋权树
②最小生成树算法-Kruskal避圈法
③最小生成树算法-破圈法
④最小生成树的应用
4.有向树和根树
引入
①有向树定义
②有向树的性质
③根树定义
儿子、兄弟、祖先、后代
④根子树定义
⑤根树的应用
5.根树的遍历
引入
①有序树定义
②根树的遍历
③根树遍历的应用
6.二叉树
引入
①二叉树的定义
②二叉树的性质
③前缀码
④二叉树的应用
7.最优树及其应用
引入
①叶赋权树
②最优二叉树
③最优树的构造-Huffman算法
最优二叉树不一定唯一
④最优树的应用
完 | 结 | 撒 | 花 |