离散_图片无法上传思维导图模板_ProcessOn思维导图、流程图

2一阶逻辑

概念

个体词

5，x,小王，小李

谓词

....是无理数

..与...同岁

符号化为H（a,b)

...与...有关系

符号化为G（a,b)

0元谓词

不带个体变项的谓词

f(a)或G(a,b)

个体常项

a,b,c...

个体变项

子主题 1

特性谓词

M(X)

在没有确定的个人域时，都是M(X)∧F（x)

量词

∀

∀A（x）→B

　如果,对任意x,A（x）为真；那么B为真；

如果该班的所有同学,都成绩优秀时；那么该班一定会被评为优秀班级.

∀x（A（x）→B）

对任意x：如果A（x）为真,那么B为真；

对于本班中的任何一个同学，如果他成绩优秀，那么该班就会被评为优秀班级。

存在

∀x（¬A（x）∨B）=∀x（¬A（x））∨B=¬∃x（A（x））∨B=∃x A（x）→B

全称量词对析取没有分配律

有张三、李四2人,张三会百唱歌但不会跳舞,李四不会唱歌但会跳舞。度“所有人或者会唱歌或者会跳舞”是对的，“所有人会问唱歌或者所有人会跳舞”是错的。所以：全称量词对析取没有分配律。

是错的

∃

有坑

公式

子主题 1

命题符号化

在一阶逻辑符号化时，存在量词后用合取式，而全称量词后用蕴含式

∃用∧，∀用→

在需要使用特性谓词限定个体域中的个体时，全称量词对应的特性谓词后面应该使用蕴含连接词。同理，在需要使用特性谓词限定个体域中的个体时，存在量词对应的特性谓词后面应该使用合取连接词。

杂记

f的解释

规则

置换规则

换名规则

出现

约束出现

自由出现

指导变元

闭式

没有自由出现的个体变项

闭式在任何解释下都变成命题

等值式

量词辖域收缩与扩张等值式

容易理解的

子主题 2

∀x（A（x）→B）=∃x A（x）→B

∃x （A（x）→B）=∀xA（x）→B

量词否定等值式

¬∃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））已经扩到了

逻辑有效式一定是可满足式

1命题逻辑

命题与联结词

真假命题

悖论不是命题

以符号形式写出命题

联结词

∧

V

排斥或

相容或

→蕴含

q→p的情况

只有...才

除非... 否则非p

假如没有...就没有

仅当

p→q

等价联结词

P

Q的情况

当且...仅当

与非联结词

true

当且仅当不同时为真

￢（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

吸收律

Av(A∧B)=A

A∧(AvB)=A

等价否定等值式

范式

只能有┐∨∧

不能有→，┐只能出现在（）内

析取范式

∨

但它由每个合取简单式构成

主析取范式

m1Vm2Vm5=Σ（1,2,5）

合取范式

主合取范式

M1∧M2∧M5=Π（1,2,5）

∧

由每个简单析取范式构成

推理

推理定律

分配律

(AvB)∧(C∧D)

假言三段论

（A→B)∧（B→C)→（A→C)

析取三段论

已知条件1 或条件2那么利用条件2的否定可以得到条件1成立比如：我今天去游泳或者去爬山如果我说,我今天不去爬山那么肯定知道我今天要去游泳

假言推理

（A→B)∧A→B

如果我刷牙，那我肯定用了牙刷，如果我刷了牙。所以用了牙刷

拒取式

（A→B)∧￢B→A

如果我刷牙，那我肯定用了牙刷，如果我没用牙刷。所以我肯定没刷牙

构造性二难

如果我刷了牙，那我用了牙刷，如果我是男人，那我有胡子。如果我刷了牙或者是男人，那么，我用了牙刷或者有胡子

（A→B)∧（C→D）∧（AvC)→(BvD)

假言推理的升级版

破坏性二难

如果我刷了牙，那我用了牙刷，如果我是男人，那我有胡子。如果我没有用了牙刷或者有胡子。，那么，我没有刷牙或者是男人

（A→B)∧（C→D）∧￢(BvD)→￢（AvC)

合取引入

结论中可以引入前提条件，毕竟前提条件都为真,如（PvQ)是前提

如r合取引入

r∧（PvQ)

化简律

r∧s

r

附加律

推理形式是否正确

有效推理和能推出正确结论的推理并不度相同。有效推理仅指形式正确，并不保证结版论一定正确。在演绎推理中，要保证结论正确，必须同时满足两个条件：1、有效的推理形权式，2、前提内容真实。而有效的推理形式并不涉及前提内容的真实性

辑学中有效的推理是指推理的形式符合规则，即前提与结论的联系方式合乎推理的规则

推理无效就要去证明前提真结论假这种情况存在

推理正确，当且仅当为重言式

等值演算法

真值表法

主析取范式法

观察法

CP规则附加前提证明法Conclusion Premise

结论里的蕴含式移到前提，结论只留一个

归谬法

结论的否定

引入条件，结论为0

归结法

结论的否定

前提全改为简单析取式

前提条件可以用好几次

如P多次引入，前提都是真的，当然可以多次引入

ES(存在指定规则 Exstential Specify)UG(全称推广规则 Universal Generalize)

推理形式

子主题 6

x+2=7不是命题，是真值不确定的陈述句

长江和黄河是中国最长的两条河是简单命题

主语：长江和黄河谓语:是中国最长的两条河：

如果改为长江和黄河都是是中国最长的两条河是复合命题

与“连结的是主语

李梅和李雪是姐妹：

符号化为：p

基础知识

集合

空集是一切集合的子集

幂集

P(A)=｛Φ,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}｝

德摩根律

对称差

A=Ø无元素，B={Ø}有一个元素Ø

⊂

包含关系指的是集合之间的关系,例如集合A={1,2,3}集合B={1,2},那么A就包含B

C

复数集

0是偶数

|A|=集合A上的元素数目

子主题 11

T规则

偏序的逆也是偏序

属于关系指的是元素和集合之间的关系

文氏图

7代数系统

定义

零元

乘法的0元是0

1是乘法群幺元，0是加法群幺元，幺元乘以任何x都等于x

二元运算

加法，乘法

代数系统

半群

子半群，他的子集

一个群是另一个群的子群，要证明任意两个元素a.b属于子群，且两元素乘积和a逆属于子群

子主题 1

独异点

含有幺元的半群

群

对任意x都含有逆元的独异点

x^-1是逆元，x。x^-1=e 如加法群中，3的逆元是-2

各种群

平凡群

只有单位元的群如<{0},+>

循环群

U(9)U(9) units组成的一个群。{1,2,4,5,7,8},{}里面的数全部与9互质。相应的4的units，U(4)U(4) 是{1，3} ，4 以内只有1，3与4互质。 2是9的生成元(generator),因为 211 mod 9 = 2 222 mod 9 = 4 233 mod 9 = 8 244 mod 9 = 7 255 mod 9 = 5 266 mod 9 = 1

定义为若—个群G的每—个元都是G的某—个固定元a的乘方，则称G为循环群，记作G=(a)，a称为G的—个生成元

3

交换群

阿贝尔群（Abelian Group），又称交换群或加群.设<G,☆>是群，如果运算☆知满足交换律，a ☆ b = b ☆ a则称<G,☆>是交换群例.<Z,+> , <Q,+> , <R,+> , <Zn,+n> (”+”都是普通的加法道；“+n”是模的加法)都是交换群

阿贝尔群（Abelian Group），又称交换群或加群，是这样一类群：它除了满足一般的群公理，即运算的结合律、G 有单位元、所有 G 的元素都有逆元之外，还满足交换律公理。

置换群

n元对称群的子群

四元群

环与域

环

要有逆元

对乘法的要求只有适合结合律一条

整环

交换，含幺，无零因子的环

域

格和布尔代数

分配格

x∨(y∧z)=(x∨y)∧(x∨z)

x∧(y∨z)=(x∧y)∨(x∧z)

∧最大下界，∨最小上界

有补格

a和a'是互补，L中所有元素都有补元

1和2都有两个上界，因此这两个点没有最小上界(最小上界有且只能有一个)

<s,。>满足交换律，结合律，分配律则也是格

同态

单射映射

单同态

满射映射

满同态

双射映射

同构

到自身

自同态

6树

无向树定义

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和1

若只有一个儿子（子结点），命为0

遍历

首先遍历根结点，然后遍历左子树，再遍历右子树-前序

首先遍历左子树，再遍历根结点，再遍历右子树-中序

首先遍历左子树，然后遍历右子树，最后访问根结点-后序

子主题 7

5图

基本概念

无向图和有向图

简单无向图 △《n-1

各种图

含平行边的图称为多重图

不含平行边和环的图称为简单图

有向图可以！！！<c,d>和<d,c>不是平行边

最大度数=最小度数是k-正则图

是特殊的n-1正则图-完全图

在无向圈里放置一个顶点使它与每个顶点均相邻, 这是n阶-轮图

所有顶点加起来等于n，n阶轮图

2^n个顶点，一个正方形套一个正方形，为N方体图

顶点标了名字叫标定图

图中任意两点都是连通，称为连通图

圈图

一个圈

对偶图

度数为1的为悬挂顶点，与它关联的边是悬挂边

最大度△

△+最大出度

△-最大入度

最小度ξ

ξ+最小出度

ξ-最小入度

一个顶点的度数=deg(v2)

子主题 1

子图和补图

子图

从原图中删去一些百点或删去一些线或既删去一些点又删去一些线，剩下的部分（当然必须仍然度是图）。允许两种极端情况：什么都不删；删去所有点和所有线

真子图

专同“子图”，但不允许什么都不删

生成子图

同“子图”，但只允许删去线，不允许删去点

补图

以所有能使G成为完全图Kn的添加边组成的集合

一个图有着跟G相同的点，这些点之间有边相连当且仅当在G里面他们没有边相连，如Kn的补图为n阶零图

自补图

当一个图和它的补图同构时，为自补图。

同构

每个点出入度不变，图的整个拓扑结构不变(连通性)，顶点个数不变

图的连通性

通路的条数

所有的边各异-简单回路

所有的边和点各异-初级回路（圈）

长度为奇数称为奇圈

初级回路的边可以重复-复杂回路（高级）

无向图的连通性和连通度

点割集

少了这些点，图失去连通性。而且它的子集不会

若只有一个，称为割点

边割集

少了这些边，图失去连通性。而且它的子集不会

若只有一个，称为割边

桥

连通度

点连通度

K（G）=最少的顶点个数使图失去连通性

边连通度

λ（G）=最少的边个数使图失去连通性

最小度》边连通度》点连通度，ξ》λ》K

有向图的连通性和连通度

短程线

Vi到Vj最短通路

距离d=长度

单向连通图

任意两个顶点至少有一个可达另一个顶点

强连通图

任意两个顶点相互可达

每个度数至少为2，则包含一条回路

弱连通

无向图的

图的矩阵

无向图的关联矩阵

边与顶点的联系

0

1

环2

有向图

有向图的关联矩阵

边e与顶点v的联系

1顶点是边的起始点

0没有关系

-1顶点是边的终点

有向图的邻接矩阵

顶点到顶点的通路条数联系

V1到v3的长度为2的通路有多少条

有向图的可达矩阵又称连通矩阵

顶点i是否能到达J

0

1

主对角元素全为1

图是强连通的当且仅当矩阵全为1

将矩阵的1~n-1次方对应点相加求和，存入另一n*n矩阵中，将此矩阵非0元素全部置为1，将对角线元素置为1，便得到此图的可达矩阵。

边数

边数=n(n-1)

特殊的图

二部图

定义

顶点分成两个不相交的子集，G中任何一条边一条属于V1一条属于V2

当且仅当无奇数度长度的回路

一个点回到原点只能是偶数边数

n阶零图是二部图

完全二部图

V1每个节点都与V2每个节点相邻

证明

每条回路经过的边数都是偶数

匹配

E中边不相邻

极大匹配

多一条边就是相邻了

最大匹配

极大匹配边数最多的

匹配的边数与最小顶点子集数关系

匹配的边数等于最小顶点子集数关系，完备匹配

特殊的完备匹配。与两个子集数都相等，完美匹配

证明二部图的完备匹配

相异性条件

V1任意k个顶点和V2的k个顶点相邻

边数等于V1定点数，当然是这样

t条件

V1至少关联t条边

V2至多关联t条边

欧拉图

欧拉回路（一笔画），也称为欧拉图

不重复遍历所有的边回到原点（顶点可以经过多次，必须经过图中所有的边）

简单回路不需要经过图中所有的边，所以简单回路不一定是欧拉回路

定义无向图

G是连通图且无奇度顶点

所有顶点的度数为偶数

定义有向图

当且仅当D是连通的且所有顶点的入度等于出度

欧拉通路

经过边一次且仅一次

哈密顿图

经过每个顶点一次且仅一次，哈密顿通路

经过每个顶点一次且仅一次的回路，哈密顿回路（初级回路），也称为哈密顿图

一定要经过每个顶点，边可以不管

哈密顿回路属于初级回路，但初级回路不一定是哈密顿回路，因为不包括每一个点

定义

哈密顿回路一定没有割点

平面图

null

定义

除顶点外没有边交叉出现

画出没有边交叉的图称为平面嵌入或平面表示

否则称为非平面图

平面图的边把区域画成若干区域

面积无限-外部面

有限-内部面

包围这个面的回路称为-边界

极大平面图

任意不相邻的两个顶点之间加一个边，所得图就是非平面图，则为极大平面图

他的每个面的长度（次数）=3

是连通的

2m=3r (r是面数）

总的次数=2m

定理6.17

K5和k3,3都不是平面子图

证明是平面图

平面图的欧拉公式n-m+r=2

n-m+r=k+1

k=连通分支

子主题 2

必要条件

m《3n-6

充要条件

不同胚于K33或K5

子主题 8

同胚

反复插入和消去2度顶点后同构

库拉图斯基定理

子主题 1

子主题 2

极大平面图每面的次数皆为3

任何图都是4-可着色的

偶阶圈图顶点着色2个

奇阶圈图顶点着色3

偶阶轮图顶点着色4个

奇阶轮图顶点着色3个

二部图顶点着色两个

4函数

性质

函数

x只对应一个y，y=f(x)=x的平方-1。

<1,5><1,6>就不是函数，只是二元关系

函数!!!A到B的函数的集合，就是X到Y的集合

定义

单射

不存在两枪打在一个点上,可以有的靶子没有点。这依然是单射。7个猎人，10个靶子

唯一的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就是函数

设X,Y是两个非空来集合，如果存在一个法则f，使得对X中每个元素自x，按法则f，在Y中有唯一确定的元素y与之对应，则称f为从X到Y的映射。其中y称为元素x（在映射知f下）的像道，元素x称为元素y（在映射f下）的一个原像。

3关系

有序对和笛卡尔积

<x,y>

A×B = {(x,y)|x∈A∧y∈B}

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)笛卡尔积运算不满足结合律，除非三者都为空

左边的元素是 (（1,2）,3) ,右边的元素是 (1,（2,3）)

N阶笛卡尔积如空间直角坐标系

P(A)是幂集

二元关系R

包含R∈

整除Da

<x,y> x|y

等于

恒等IA

（a,a)

子主题 4

全域关系 Ea ={(x,y)|x∈A∧y∈A}

二元关系是序偶的集合

关系的矩阵

关系的基本运算

fldR域

dom定义域

逆关系R^-1

R是对称的，则R逆也对称，R补也对称

R的幂R^2等等，就是线性代数的求法

鸽巢定理

n+1个鸽子放进n个笼子里

R^0=IA

关系的性质

自反

<x,x>

反自反

<x,x>一个都不属于R

既不是自反也不算反自反

对称

<x,y>在则<y,x>也在

反对称

<x,y>则<y,x>是<x,x>

<y,x>不存在则也是反对称

非对称

既不是对称也不是反对称

传递

<x,y>和<y,z>在，则<x,z>也在

<y,z>不在，则也是传递的

{<1,3>}和{<1,2><3,2>}也是传递的，它们没有<y,z>

R1=｛<1，1>，<2，2>｝是传递的

像集

对称，传递不一定能推出自反

集合为{1, 2, 3}，R={(1, 2), (2, 1), (1, 1), (2, 2)}。显然R是对称的，传递的，但是，不是自反的。因为(3, 3)不在R中

关系的闭包

向R中加入少量有序对，使它有（自反，传递，对称）性质

自反 r(R)

R^0是自环

symmetry 对称s(R)

t(R)

传递闭包

沃舍尔算法

纸上思想

k=1,第一行所有有1的地方画竖线，第一列所有有1的地方画横线，交叉的地方0改为1。直到k=n

两个数逻辑加时，如两个数都是0则结果是0,否则为1

代码思想

链接

k=1时，第一行的元素逻辑加到第一列所有有1的那一行

k=2时，第二行的元素逻辑加到第二列所有有1的那一行。一直如此，直到K=n

tsr(R)

次序

先算自反再算对称，再算传递

等价关系

R是自反的对称的传递的，则称R为A上的等价关系--

等价类

根据传递性来划分等价！！！

比如从1出发，传递所能接触的所有元素化为一类！！！

商集

A/R

就是等价类的划分

{{1,4,7}{2,5}{3,6}}

A/I

关于恒等关系划分

{{1},{2},{3},{4},{5},{6},{7}}

划分

就是一个蛋糕切划分，切块没有公共部分，切块合在一起是原来蛋糕，切块不能是空集

115划分还没

偏序关系偏序集与哈斯图

偏序

偏序关系都是带自反，反对称和传递的

所以恒等关系属于偏序，集合包括IA

拟序

反自反，传递

全序

集合内任何一对元素在在这个关系下都是相互可比较的

全序关系指的是集合A,任意x和y,元素之间有偏序关系,x≤y,或者y≤x

最小上界

就是类似于最小公倍数

最大下界

最大公约数

上界

所有的公倍数

下界

所有的公约数

哈斯图的箭头

箭头→末端指向的是y <x,y>

设A={a,b}，,则A上共有 3 个不同的偏序关系

{1,2}上可以定义16种关系

子主题 10

所以总的次数=2*总边数

自由主题