离散_图片无法上传
2021-11-13 10:58:07 11 举报AI智能生成
登录查看完整内容
图片无法上传，有需要的可以通过我的博客https://blog.csdn.net/lwj3326上浏览
作者其他创作
大纲/内容
个体词
....是无理数
..与...同岁
...与...有关系
不带个体变项的谓词
个体常项
子主题 1
个体变项
0元谓词
在没有确定的个人域时，都是M(X)∧F（x)
M(X)
特性谓词
谓词
∀A（x）→B
存在
对于本班中的任何一个同学，如果他成绩优秀，那么该班就会被评为优秀班级。
∀x（¬A（x）∨B）=∀x（¬A（x））∨B=¬∃x（A（x））∨B=∃x A（x）→B
∀x（A（x）→B）
是错的
全称量词对析取没有分配律
∀
有坑
∃
量词
公式
∃用∧，∀用→
在需要使用特性谓词限定个体域中的个体时，全称量词对应的特性谓词后面应该使用蕴含连接词。同理，在需要使用特性谓词限定个体域中的个体时，存在量词对应的特性谓词后面应该使用合取连接词。
在一阶逻辑符号化时，存在量词后用合取式，而全称量词后用蕴含式
命题符号化
概念
f的解释
置换规则
换名规则
规则
约束出现
自由出现
指导变元
出现
没有自由出现的个体变项
闭式在任何解释下都变成命题
闭式
杂记
容易理解的
∀x（A（x）→B）=∃x A（x）→B
∃x （A（x）→B）=∀xA（x）→B
子主题 2
量词辖域收缩与扩张等值式
¬∃x A（x）→∀x¬A（x）
¬∀xA（x）→∃x ¬A（x）
量词否定等值式
量词分配等值式
消去量词等值式
等值式
前束范式不唯一
∀xF（x）→∃x G（x）=∃y∃x F（y）→G（x）
但是∀x（A（x）→∃y G（y））=∀x∃y（A（x）→ G（y））已经扩到了
有→一定要收缩扩招
一阶逻辑前束范式
一阶逻辑等值演算
逻辑有效式一定是可满足式
2一阶逻辑
悖论不是命题
真假命题
以符号形式写出命题
∧
排斥或
相容或
V
只有...才
除非... 否则非p
假如没有...就没有
q→p的情况
p→q
仅当
→蕴含
当且...仅当
Q的情况
P
等价联结词
￢（p∧q)
当且仅当不同时为真
true
与非联结词
￢（pVq)
同时为假
或非联结词
联结词
自然语言转化成逻辑语言
重言式
可满足式
矛盾式
公式：命题变项和联结词形成
命题与联结词
A→B)∧(B→A)或
（r∧s)V( ￢r∧￢s)
（rV￢s)∧( ￢rVs)
等价等值式
（r∧￢s)∧( ￢r∧s)
有且只有一个人去
命题逻辑
德摩根律
分配
（A∧￢B）∧B=A∧（￢B∧B）=0
结合
幂等
A→B ⇔ ￢A∨B
蕴含等值
A→B=￢B→￢A
假言易位
A∧(AvB)=A
Av(A∧B)=A
吸收律
等价否定等值式
等值演算
命题逻辑等值演算
但它由每个合取简单式构成
∨
主析取范式
析取范式
主合取范式
由每个简单析取范式构成
合取范式
不能有→，┐只能出现在（）内
只能有┐∨∧
范式
(AvB)∧(C∧D)
分配律
（A→B)∧（B→C)→（A→C)
假言三段论
析取三段论
如果我刷牙，那我肯定用了牙刷，如果我刷了牙。所以用了牙刷
（A→B)∧A→B
假言推理
如果我刷牙，那我肯定用了牙刷，如果我没用牙刷。所以我肯定没刷牙
（A→B)∧￢B→A
拒取式
（A→B)∧（C→D）∧（AvC)→(BvD)
假言推理的升级版
如果我刷了牙，那我用了牙刷，如果我是男人，那我有胡子。如果我刷了牙或者是男人，那么，我用了牙刷或者有胡子
构造性二难
（A→B)∧（C→D）∧￢(BvD)→￢（AvC)
如果我刷了牙，那我用了牙刷，如果我是男人，那我有胡子。如果我没有用了牙刷或者有胡子。，那么，我没有刷牙或者是男人
破坏性二难
r∧（PvQ)
如r合取引入
合取引入
r
r∧s
化简律
附加律
推理定律
辑学中有效的推理是指推理的形式符合规则，即前提与结论的联系方式合乎推理的规则
推理无效就要去证明 前提真结论假这种情况存在
有效推理和能推出正确结论的推理并不度相同。有效推理仅指形式正确，并不保证结版论一定正确。在演绎推理中，要保证结论正确，必须同时满足两个条件：1、有效的推理形权式，2、前提内容真实。而有效的推理形式并不涉及前提内容的真实性
等值演算法
真值表法
主析取范式法
观察法
结论里的蕴含式移到前提，结论只留一个
CP规则附加前提证明法Conclusion Premise
引入条件，结论为0
结论的否定
归谬法
结论的否定
前提全改为简单析取式
归结法
如P多次引入，前提都是真的，当然可以多次引入
前提条件可以用好几次
ES(存在指定规则 Exstential Specify)UG(全称推广规则 Universal Generalize)
推理正确，当且仅当为重言式
推理形式
推理形式是否正确
推理
x+2=7不是命题，是真值不确定的陈述句
主语：长江和黄河 谓语:是中国最长的两条河：
如果改为长江和黄河都是是中国最长的两条河是复合命题
符号化为：p
李梅和李雪是姐妹：
与“连结的是主语
长江和黄河是中国最长的两条河是简单命题
子主题 6
1命题逻辑
空集是一切集合的子集
幂集
集合
对称差
A=Ø无元素，B={Ø}有一个元素Ø
⊂
复数集
C
0是偶数
|A|=集合A上的元素数目
子主题 11
T规则
偏序的逆也是偏序
属于关系指的是元素和集合之间的关系
文氏图
基础知识
乘法的0元是0
零元
1是乘法群幺元，0是加法群幺元，幺元乘以任何x都等于x
定义
加法，乘法
二元运算
一个群是另一个群的子群，要证明任意两个元素a.b属于子群，且两元素乘积和a逆属于子群
子半群，他的子集
半群
含有幺元的半群
独异点
x^-1是逆元，x。x^-1=e 如加法群中，3的逆元是-2
对任意x都含有逆元的独异点
群
平凡群
定义为若—个群G的每—个元都是G的某—个固定元a的乘方，则称G为循环群，记作G=(a)，a称为G的—个生成元
3
循环群
阿贝尔群（Abelian Group），又称交换群或加群，是这样一类群：它除了满足一般的群公理，即运算的结合律、G 有单位元、所有 G 的元素都有逆元之外，还满足交换律公理。
交换群
n元对称群的子群
置换群
四元群
各种群
要有逆元
对乘法的要求只有适合结合律一条
环
交换，含幺，无零因子的环
整环
域
环与域
x∨(y∧z)=(x∨y)∧(x∨z)
x∧(y∨z)=(x∧y)∨(x∧z)
∧最大下界，∨最小上界
分配格
a和a'是互补，L中所有元素都有补元
有补格
1和2都有两个上界，因此这两个点没有最小上界(最小上界有且只能有一个)
格和布尔代数
单同态
单射映射
满同态
满射映射
同构
双射映射
自同态
到自身
同态
代数系统
7代数系统
d(v)=1的都称为树叶，所以非平凡树至少有两个树叶
连通不含回路的无向图称为无向树
平凡树
只有一个根
树是连通的，删掉任何一条边都会变得不连通
边=顶点-1 m=n-1
度数=联结顶点的边数
deg=2m
无向树定义
无向连通图中存在生成树
在生成树中的称为树枝
不在树中的称为弦
它并不一定是树
所有弦的集合称为余树
边》顶点-1
把边按从小到大排序依次加入树中
克鲁斯卡尔kruskal算法
最小生成树
生成树
入度为0称为树根
层数，树高，儿子，父亲，有序树
r元树是有序的-r元有序树
每个分支点最多r个儿子-r元树
r元正则树是有序的-r元有序正则树
r元完全正则树是有序的-r元有序完全正则树
r元正则树的树叶的层数等于树高h-r元完全正则树
每个分支点恰有r个儿子-r元正则树
其它
入度为1，出度大于等于1
内点
树根
分支点
根数
权值最小的先合成树，最后总的权值最小（小的放左边）
哈夫曼算法
若只有一个儿子（子结点），命为0
0和1
最佳前缀码
首先遍历根结点，然后遍历左子树，再遍历右子树-前序
首先遍历左子树，再遍历根结点，再遍历右子树-中序
首先遍历左子树，然后遍历右子树，最后访问根结点-后序
遍历
子主题 7
6树
简单无向图 △《n-1
无向图和有向图
含平行边的图称为多重图
不含平行边和环的图称为简单图
最大度数=最小度数是k-正则图
是特殊的n-1正则图-完全图
所有顶点加起来等于n，n阶轮图
2^n个顶点，一个正方形套一个正方形，为N方体图
顶点标了名字叫标定图
图中任意两点都是连通，称为连通图
一个圈
圈图
对偶图
各种图
度数为1的为悬挂顶点，与它关联的边是悬挂边
△+最大出度
△-最大入度
最大度△
ξ+最小出度
ξ-最小入度
最小度ξ
一个顶点的度数=deg(v2)
基本概念
从原图中删去一些百点或删去一些线或既删去一些点又删去一些线，剩下的部分（当然必须仍然度是图）。允许两种极端情况：什么都不删；删去所有点和所有线
子图
专同“子图”，但不允许什么都不删
真子图
同“子图”，但只允许删去线，不允许删去点
生成子图
一个图有着跟G相同的点，这些点之间有边相连当且仅当在G里面他们没有边相连，如Kn的补图为n阶零图
当一个图和它的补图同构时，为自补图。
自补图
以所有能使G成为完全图Kn的添加边组成的集合
补图
子图和补图
每个点出入度不变，图的整个拓扑结构不变(连通性)，顶点个数不变
通路的条数
所有的边各异-简单回路
长度为奇数称为奇圈
所有的边和点各异-初级回路（圈）
初级回路的边可以重复-复杂回路（高级）
少了这些点，图失去连通性。而且它的子集不会
若只有一个，称为割点
点割集
少了这些边，图失去连通性。而且它的子集不会
桥
若只有一个，称为割边
边割集
K（G）=最少的顶点个数使图失去连通性
点连通度
λ（G）=最少的边个数使图失去连通性
边连通度
连通度
无向图的连通性和连通度
最小度》边连通度》点连通度，ξ》λ》K
Vi到Vj最短通路
距离d=长度
短程线
任意两个顶点至少有一个可达另一个顶点
单向连通图
任意两个顶点相互可达
强连通图
有向图的连通性和连通度
每个度数至少为2，则包含一条回路
无向图的
弱连通
图的连通性
0
1
环2
边与顶点的联系
无向图的关联矩阵
1顶点是边的起始点
0没有关系
-1顶点是边的终点
边e与顶点v的联系
有向图的关联矩阵
顶点到顶点的通路条数联系
V1到v3的长度为2的通路有多少条
有向图的邻接矩阵
顶点i是否能到达J
主对角元素全为1
将矩阵的1~n-1次方对应点相加求和，存入另一n*n矩阵中，将此矩阵非0元素全部置为1，将对角线元素置为1，便得到此图的可达矩阵。
图是强连通的当且仅当矩阵全为1
有向图的可达矩阵又称连通矩阵
边数=n(n-1)
边数
有向图
图的矩阵
当且仅当无奇数度长度的回路
一个点回到原点只能是偶数边数
顶点分成两个不相交的子集，G中任何一条边一条属于V1一条属于V2
n阶零图是二部图
V1每个节点都与V2每个节点相邻
完全二部图
每条回路经过的边数都是偶数
证明
多一条边就是相邻了
极大匹配
极大匹配边数最多的
最大匹配
E中边不相邻
匹配的边数等于最小顶点子集数关系，完备匹配
特殊的完备匹配。与两个子集数都相等，完美匹配
匹配的边数与最小顶点子集数关系
匹配
边数等于V1定点数，当然是这样
V1任意k个顶点和V2的k个顶点相邻
相异性条件
V1至少关联t条边
V2至多关联t条边
t条件
证明二部图的完备匹配
二部图
简单回路不需要经过图中所有的边，所以简单回路不一定是欧拉回路
不重复遍历所有的边回到原点（顶点可以经过多次，必须经过图中所有的边）
欧拉回路（一笔画），也称为欧拉图
所有顶点的度数为偶数
G是连通图且无奇度顶点
定义无向图
当且仅当D是连通的且所有顶点的入度等于出度
定义有向图
经过边一次且仅一次
欧拉通路
欧拉图
经过每个顶点一次且仅一次，哈密顿通路
哈密顿回路属于初级回路，但初级回路不一定是哈密顿回路，因为不包括每一个点
一定要经过每个顶点，边可以不管
经过每个顶点一次且仅一次的回路，哈密顿回路（初级回路），也称为哈密顿图
哈密顿回路一定没有割点
哈密顿图
null
除顶点外没有边交叉出现
否则称为非平面图
画出没有边交叉的图称为平面嵌入或平面表示
面积无限-外部面
包围这个面的回路称为-边界
有限-内部面
平面图的边把区域画成若干区域
任意不相邻的两个顶点之间加一个边，所得图就是非平面图，则为极大平面图
他的每个面的长度（次数）=3
是连通的
总的次数=2m
2m=3r (r是面数）
定理6.17
k=连通分支
n-m+r=k+1
平面图的欧拉公式n-m+r=2
m《3n-6
必要条件
不同胚于K33或K5
充要条件
证明是平面图
子主题 8
极大平面图
反复插入和消去2度顶点后同构
同胚
库拉图斯基定理
极大平面图每面的次数皆为3
平面图
特殊的图
偶阶圈图顶点着色2个
奇阶圈图顶点着色3
偶阶轮图顶点着色4个
奇阶轮图顶点着色3个
二部图顶点着色两个
任何图都是4-可着色的
5图
x只对应一个y，y=f(x)=x的平方-1。
函数
函数!!!A到B的函数的集合，就是X到Y的集合
性质
唯一的x，f(x)=y
对于∀x都有对应的y，y可以有多，ranf不一定等于集合B
单射
多个子弹打在一个点上，要全被打到
y中的元素都有对应
ranf=B
满射
一一对应，如y=x
既是满射又是单射
双射
从A到商集A/R的自然映射肯定是满射，可能是单射（当任意一个等价类中只有一个元素时）
自然映射一定是满射，但不一定是双射
两个函数是单射的，则复合函数也是单射。
两个函数是满射的，则复合函数也是满射
两个函数是双射的，则复合函数也是双射
复合函数的定义域和值域怎么理解
复合
f^-1
f可逆则f是双射，f是双射则f可逆
f*f^-1(x)=x
反函数
像就是y，原像就是x，f就是函数
函数的像和完全原像？
4函数
4.笛卡尔积运算对并和交运算满足分配律，即Ax(B∪C)=(AxB)∪(AxC)(B∪C)xA=(BxA)∪(CxA)Ax(B∩C)=(AxB)∩(AxC)(B∩C)xA=(BxA)∩(CxA)
(AxB)xC≠Ax(BxC)笛卡尔积运算不满足结合律，除非三者都为空
N阶笛卡尔积如空间直角坐标系
P(A)是幂集
有序对和笛卡尔积
包含R∈
整除Da
等于
恒等IA
子主题 4
二元关系是序偶的集合
二元关系R
关系的矩阵
fldR域
dom定义域
R是对称的，则R逆也对称，R补也对称
逆关系R^-1
R的幂R^2等等，就是线性代数的求法
n+1个鸽子放进n个笼子里
鸽巢定理
R^0=IA
关系的基本运算
自反
反自反
既不是自反也不算反自反
对称
反对称
既不是对称也不是反对称
非对称
R1=｛<1，1>，<2，2>｝是传递的
传递
像集
对称，传递不一定能推出自反
关系的性质
R^0是自环
自反 r(R)
symmetry 对称s(R)
纸上思想
链接
k=1时，第一行的元素逻辑加到第一列所有有1的那一行
k=2时，第二行的元素逻辑加到第二列所有有1的那一行。一直如此，直到K=n
代码思想
沃舍尔算法
传递闭包
t(R)
向R中加入少量有序对，使它有（自反，传递，对称）性质
先算自反再算对称，再算传递
次序
tsr(R)
关系的闭包
R是自反的对称的传递的，则称R为A上的等价关系--
比如从1出发，传递所能接触的所有元素化为一类！！！
根据传递性来划分等价！！！
等价类
就是等价类的划分
A/R
关于恒等关系划分
A/I
商集
115划分还没
就是一个蛋糕切划分，切块没有公共部分，切块合在一起是原来蛋糕，切块不能是空集
划分
等价关系
所以恒等关系属于偏序，集合包括IA
偏序关系都是带自反，反对称和传递的
偏序
反自反，传递
拟序
集合内任何一对元素在在这个关系下都是相互可比较的
全序
就是类似于最小公倍数
最小上界
最大公约数
最大下界
所有的公倍数
上界
所有的公约数
下界
哈斯图的箭头
偏序关系偏序集与哈斯图
子主题 10
3关系
所以总的次数=2*总边数
自由主题
离散_图片无法上传
0 条评论
回复 删除
下一页
