离散数学知识点.docx

离散数学知识点.docx

《离散数学知识点.docx》由会员分享，可在线阅读，更多相关《离散数学知识点.docx（43页珍藏版）》请在冰点文库上搜索。

离散数学知识点

说明：

定义：

红色表示。

定理性质：

橙色表示。

公式：

蓝色表示。

算法:

绿色表示

页码：

灰色表示

数理逻辑：

1.命题公式：

命题，联结词（，，，，），合式公式，子公式

2.公式的真值：

赋值，求值函数，真值表，等值式，重言式，矛盾式

3.范式：

析取范式，极小项，主析取范式，合取范式，极大项，主合取范式

4.联结词的完备集：

真值函数，异或，条件否定，与非，或非，联结词完备集

5.推理理论：

重言蕴含式，有效结论，P规则，T规则，CP规则，推理

6.谓词与量词:

谓词，个体词，论域，全称量词，存在量词

7.项与公式:

项，原子公式，合式公式，自由变元，约束变元，辖域，换名，代入

8.公式语义:

解释，赋值，有效的，可满足的，不可满足的

9.前束范式:

前束范式

10.推理理论:

逻辑蕴含式，有效结论，-规则（US），+规则（UG），-规则（ES），+规则（EG）,推理

集合论：

1.集合:

集合,外延性原理,,,,空集,全集,幂集,文氏图,交,并,差,补,对称差

2.关系:

序偶,笛卡尔积,关系,domR,ranR,关系图,空关系,全域关系,恒等关系

3.关系性质与闭包:

自反的,反自反的,对称的,反对称的,传递的,自反闭包r（R）,对称闭包s（R）,传递闭包t（R）

4.等价关系:

等价关系,等价类,商集,划分

5.偏序关系:

偏序,哈斯图,全序（线序）,极大元/极小元,最大元/最小元,上界/下界

6.函数:

函数,常函数,恒等函数,满射,入射,双射，反函数,复合函数

7.集合基数:

基数,等势,有限集/无限集,可数集,不可数集

代数结构：

1.运算及其性质：

运算，封闭的,可交换的,可结合的,可分配的,吸收律,幂等的，幺元,零元,逆元

2.代数系统：

代数系统，子代数，积代数，同态，同构。

3.群与子群：

半群,子半群,元素的幂，独异点，群，群的阶数，子群,平凡子群，陪集，拉格朗日（Lagrange）定理

4.阿贝尔群和循环群：

阿贝尔群（交换群），循环群,生成元

5.环与域：

环，交换环，含幺环，整环，域

6.格与布尔代数：

格，对偶原理，子格，分配格，有界格，有补格，布尔代数，有限布尔代数的表示定理

图论：

1.图的基本概念：

无向图、有向图、关联与相邻、简单图、完全图、正则图、子图、补图，握手定理，图的同构

2.图的连通性:

通路，回路，简单通路，简单回路（迹）初级通路（路径），初级回路（圈），点连通，连通图，点割集，割点，边割集，割边，点连通度，边连通度，弱连通图，单向连通图，强连通图，二部图（二分图）

3.图的矩阵表示：

关联矩阵，邻接矩阵，可达矩阵

4.欧拉图与哈密顿图：

欧拉通路、欧拉回路、欧拉图、半欧拉图，哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图

5.无向树与根树：

无向树，生成树，最小生成树，Kruskal，根树，m叉树，最优二叉树，Huffman算法

6.平面图:

平面图，面，欧拉公式，Kuratoski定理

数理逻辑：

命题：

具有确定真值的陈述句。

否定词符号：

设p是一个命题，p称为p的否定式。

p是真的当且仅当p是假的。

p是真的当且仅当p是假的。

【定义1.1】

合取词符号：

设p，q是两个命题，命题“p并且q”称为p，q的合取，记以pq，读作p且q。

pq是真的当且仅当p和q都是真的。

【定义1.2】

析取词符号：

设p，q是两个命题，命题“p或者q”称为p，q的析取，记以pq，读作p或q。

pq是真的当且仅当p，q中至少有一个是真的。

【定义1.3】

蕴含词符号：

设p，q是两个命题，命题“如果p，则q”称为p蕴含q，记以pq。

pq是假的当且仅当p是真的而q是假的。

【定义1.4】

等价词符号：

设p，q是两个命题，命题“p当且仅当q”称为p等价q，记以pq。

pq是真的当且仅当p，q或者都是真的，或者都是假的。

【定义1.5】

合式公式:

（1）命题常元和变元符号是合式公式；

（2）若A是合式公式，则（A）是合式公式，称为A的否定式；

（3）若A，B是合式公式，则（AB），（AB），（AB），（AB）是合式公式；

（4）所有合式公式都是有限次使用

（1），

（2），（3）、（4）得到的符号串。

子公式:

如果Ｘ是合式公式A的一部分，且Ｘ本身也是一个合式公式，则称Ｘ为公式A的子公式。

【定义1.6】

赋值（指派，解释）：

设是命题变元集合，则称函数v：

{1，0}是一个真值赋值。

【定义1.8】

真值表：

公式A在其所有可能的赋值下所取真值的表，称为A的真值表。

【定义1.9】

重言式（永真式）:

任意赋值v，v

A

矛盾式（永假式）:

任意赋值v，有v

A【定义1.10】

等值式：

若等价式AB是重言式，则称A与B等值，记作AB。

【定义2.1】

基本等值式

双重否定律AA

幂等律AAA,AAA

交换律ABBA,ABBA

结合律（AB）CA（BC）,（AB）CA（BC）

分配律A（BC）（AB）（AC）,A（BC）（AB）（AC）

德摩根律（AB）AB,（AB）AB

吸收律A（AB）A,A（AB）A

零律A,A

同一律AA,AA

排中律AA

矛盾律AA

蕴涵等值式ABAB

等价等值式AB（AB）（BA）

假言易位ABBA

等价否定等值式ABAB

归谬论（AB）（AB）A

置换规则：

设Ｘ是公式A的子公式,ＸY。

将A中的Ｘ（可以是全部或部分X）用Y来置换，所得到的公式B，则AB。

文字:

设A（命题变元集）,则A和A都称为命题符号A的文字，其中前者称为正文字，后者称为负文字。

【定义2.2】

析取范式：

形如A1A2…An（n1）的公式称为析取范式，其中Ai（i=1,…,n）是由文字组成的合取范式。

合取范式：

形为A1A2…An（n1）的公式称为合取范式，其中A1,…,An都是由文字组成的析取式。

【定义2.3】

极小项：

文字的合取式称为极小项，其中公式中每个命题符号的文字都在该合取式中出现一次。

极大项：

文字的析取式称为极大项，其中公式中每个命题符号的文字都在该合取式中出现一次。

【定义2.4】

主析取范式：

给定的命题公式的主析取范式是一个与之等价的公式，后者由极小项的析取组成。

主合取范式：

给定的命题公式的主合取范式是一个与之等价的公式，后者由极大项的合取组成。

【定义2.5】

公式的真值表中真值为F的指派所对应的极大项的合取，即为此公式的主合取范式。

真值函数：

称F:

{0,1}n{0,1}为n元真值函数.【定义2.6】

联结词的完备集：

设C是联结词的集合，若对于任意一个合式公式均存在一个与之等价的公式，而后者只含有C中的联结词，则称C是联结词的完备集。

【定义2.7】

{，，，，}，{，，},{，}，{，}，{，}是联结词的完备集。

【定理2.6】

异或PQ：

（PQ）

条件否定PQ：

（PQ）

与非PQ：

（PQ）

或非PQ：

（PQ）【定义2.8】

{},{↓}都是联结词的完备集【定理2.7】

重言蕴含式：

当且仅当PQ是一个重言式时，称P重言蕴含Q，记为PQ。

有效结论：

设A、C是两个命题公式，若AC，称C是A的有效结论。

【定义3.1】

推理定律——重言蕴涵式

1.A（AB）附加律

2.（AB）A化简律

3.（AB）AB假言推理

4.（AB）BA拒取式

5.（AB）BA析取三段论

6.（AB）（BC）（AC）假言三段论

7.（AB）（BC）（AC）等价三段论

8.（AB）（CD）（AC）（BD）构造性二难

（AB）（AB）B构造性二难（特殊形式）

9.（AB）（CD）（BD）（AC）破坏性二难

形式系统:

一个形式系统I由下面四个部分组成：

（1）非空的字母表，记作A（I）.

（2）A（I）中符号构造的合式公式集，记作E（I）.

（3）E（I）中一些特殊的公式组成的公理集，记作AX（I）.

（4）推理规则集，记作R（I）.

记I=,其中是I的形式语言系统,是I的形式演算系统.

自然推理系统:

无公理,即AX（I）=

公理推理系统:

推出的结论是系统中的重言式,称作定理【定义3.2】

P规则：

在推导过程中,可以随时添加前提。

T规则：

在推导过程中,可以引入公式S，它是由其前题的一个或多个公式借助重言、蕴含而得到的。

推理（证明）：

从前提A1,A2,,Ak到结论B的推理是一个公式序列C1,C2,,Cl.其中Ci（1il）是某个Aj,或者可由序列中前面的公式应用推理规则得到,并且Cl=B。

【定义3.3】

CP规则（演绎定理）：

若{R}|-S，则|-RS,其中为命题公式的集合。

个体词：

用于表示命题中主语部分的符号或符号串。

个体常元表示确指个体。

个体变元表示不确指个体。

个体域:

个体变元的取值范围，常用D表示。

量词：

限定个体数量特性的词。

全称量词：

对所有的

存在量词：

有些

谓词语言：

用符号串表示个体、谓词、量词和命题

个体变元符号：

x，y，z，…

个体常元符号：

a，b，c，…

函数符号：

f，g，…

谓词符号：

P，Q，R，…

命题常元符号：

，

量词符号：

，

连接词符号：

,,,

辅助符号：

）,（【定义4.1】

项:

（1）个体常元和变元是项；

（2）若f是n元函数符号，t1,…,tn是项，则f（t1,…,tn）是项；

（3）仅仅有限次使用

（1），

（2）产生的符号串是项。

【定义4.2】

原子公式:

若P是一个元谓词符号，t1,…,tn是项,则P（t1,…,tn）是原子公式。

【定义4.3】

合式公式：

（1）原子公式是公式；

（2）若A是合式公式，则（A）是合式公式；

（3）若A，B是公式，则（AB），（AB），AB），（AB）是公式；

（4）若A是公式，x是变元，则xA，xA是公式；

（5）仅仅有限次使用１～４得到的符号串才是合式公式。

【定义4.4】

设公式的一个子公式为xA或xA。

则称：

指导变元：

x是或的指导变元。

辖域：

A是相应量词的辖域。

约束出现：

辖域中x的一切出现，以及（x）中的x称为x在中的约束出现。

自由出现：

变元的非约束出现。

约束变元：

约束出现的变元。

自由变元：

自由出现的变元。

【定义4.5】

封闭的：

一个公式A是封闭的，若其中不含自由变元。

【定义4.6】

变元换名：

（1）换名的范围是量词的指导变元,及其相应辖域中的变元，其余部分不变。

（2）换名时最好选用辖域中未出现的变元名。

变元代入：

代入对自由变元进行。

不能改变约束关系。

解释：

谓词语言的一个解释I=（D,）包括：

（1）非空集合D，称之为论域；

（2）对应于每一个个体常元a，（a）D；

（3）对应于每一个n元函数符号f都有一个函数（f）:

DnD；

（4）对应于每一个n元谓词符号A都有一个n元关系（A）Dn。

【定义4.7】

赋值：

解释I中的赋值v为每一个个体变元x指定一个值v（x）D，即设V为所个体变元的集合，则赋值v是函数v:

VD.

可满足的：

给定公式A，若在某一解释中至少有一种赋值使A取值为1，则称A为可满足的。

否则称A是不可满足的。

等值式AB：

若AB是有效的【定义5.1】

几类等值式

（1）命题公式的推广

e.g.P（x）Q（x）P（x）Q（x）

（2）否定深入

xP（x）x（P（x））

xP（x）x（P（x））

（3）量词作用域的扩张与收缩

设B中不含x的自由出现，则

x（A（x）B）xA（x）B

x（A（x）B）xA（x）B

x（A（x）B）xA（x）B

x（BA（x））BxA（x）

x（A（x）B）xA（x）B

x（A（x）B）xA（x）B

x（A（x）B）xA（x）B

x（BA（x））BxA（x）

（4）量词分配等值式

x（A（x）B（x））xA（x）xB（x）

x（A（x）B（x））xA（x）xB（x）

（5）多个量词的使用

xyA（x,y）yxA（x,y）

xyA（x,y）yxA（x,y）

置换规则：

设（A）是含A的公式,那么,若AB,则（A）（B）.

换名规则：

设A为一公式，将A中某量词辖域中个体变项的所有约束出现及相应的指导变元换成该量词辖域中未曾出现过的个体变项符号，其余部分不变，设所得公式为A，则AA.

前束范式：

如果谓词公式A有如下形状：

Q1x1…QnxnM，其中Qixi或者是xi，或者是xi，i=1，…，n，M是不含量词的公式，Q1x1…Qnxn称为首标，M称为母式。

【定义5.2】

前束范式存在定理：

对于任意谓词公式，都存在与它逻辑等价的前束范式。

【定理5.1】

前束范式的算法：

步1.对约束出现的变元进行必要的换名，使得约束出现的变元互不相同且不与任何自由变元同名。

步2.将所有的否定号深入到量词后面。

步3.将量词符号移至公式最外层。

逻辑蕴含式AC：

当且仅当AC是有效的。

几类逻辑蕴涵式

第一组命题逻辑推理定理的代换实例

如,xF（x）yG（y）xF（x）

第二组基本等值式生成的推理定理

如,xF（x）xF（x）,xF（x）xF（x）

xF（x）xF（x）,xF（x）xF（x）

第三组其它常用推理定律

（1）xA（x）xB（x）x（A（x）B（x））

（2）x（A（x）B（x））xA（x）xB（x）

（3）x（A（x）B（x））xA（x）xB（x）

（4）x（A（x）B（x））xA（x）xB（x）

推理规则

-规则（US）：

或

x,y个体变项，c个体常项

+规则（UG）：

x个体变项

-规则（ES）：

x个体变项,c个体常项

+规则（EG）：

或

x,y个体变项，c个体常项

或

先用ES，再用US

自然推理系统NL：

1.字母表.同一阶语言L的字母表

2.合式公式.同L的合式公式

3.推理规则:

（1）前提引入规则

（2）结论引入规则

（3）置换规则

（4）假言推理规则

（5）附加规则

（6）化简规则

（7）拒取式

（8）假言三段论规则

（9）析取三段论规则

（10）构造性二难推理规则

（11）合取引入规则

（12）-规则

（13）+规则

（14）-规则

（15）+规则【定义5.3】

集合论：

ABx（xAxB）【定义6.1】

A=BABBA【定义6.2】

ABABAB【定义6.3】

A⊈Bx（xAxB）

空集：

不含有任何元素的集合【定义6.4】

空集是任何集合的子集。

【定理6.1】

幂集P（A）={x|xA}【定义6.5】

如果|A|=n，则|P（A）|=2n

全集E：

包含了所有元素的集合【定义6.6】

并AB={x|xAxB}

交AB={x|xAxB}

差（相对补）AB={x|xAxB}【定义6.7】

对称差AB=（AB）（BA）【定义6.8】

补（绝对补）A=EA={x|xA}【定义6.9】

广义并A={x|z（zAxz）}【定义6.10】

广义交A={x|z（zAxz）}【定义6.11】

集合恒等式

1.只涉及一个运算的算律：

交换

AB=BA

AB=BA

AB=BA

结合

（AB）C=A（BC）

（AB）C=A（BC）

（AB）C=A（BC）

幂等

AA=A

AA=A

2．涉及两个不同运算的算律：

与

与

分配

A（BC）=（AB）（AC）

A（BC）=（AB）（AC）

A（BC）=（AB）（AC）

吸收

A（AB）=A

A（AB）=A

3．涉及补运算的算律：

D.M律

A（BC）=（AB）（AC）

A（BC）=（AB）（AC）

（BC）=BC

（BC）=BC

双重否定

A=A

4．涉及全集和空集的算律：

E

补元律

AA=

AA=E

零律

A=

AE=E

同一律

A=A

AE=A

否定

=E

E=

序偶（有序对）：

由两个元素x和y，按照一定的顺序组成的二元组，记作.【定义7.1】

笛卡儿积:

设A,B为集合，A与B的笛卡儿积记作AB定义为AB={|xAyB}.【定义7.2】

笛卡尔积性质：

A=或B=时,AB=

“”不满足结合律

A（BC）=（AB）（AC）

关系：

（两个定义）

（1）序偶的一个集合,确定了一个二元关系R。

R中任一序偶,可记作R或xRy【定义7.3】

（2）笛卡尔积的子集：

RAB【定义7.4】

空关系:

全域关系：

A×B

恒等关系IA={|x∈A}【定义7.5】

关系矩阵：

若A={x1,x2,…,xm}，B={y1,y2,…,yn}，R是从A到B的关系，R的关系矩阵是布尔矩阵MR=[rij]mn,其中rij=1R.

关系图：

若A={x1,x2,…,xm}，R是从A上的关系，R的关系图是GR=,其中A为结点集，R为边集.如果属于关系R，在图中就有一条从xi到xj的有向边.

前域（定义域）dom（R）={x|y.R}

值域ran（R）={y|x.R}

域fld（R）=domRranR【定义7.6】

逆关系R1={|R}【定义7.7】

互逆（R1）1=R

（RS）1=R1S1

（RS）1=R1S1

（AB）1=BA

（R-S）1=R1-S1

复合关系RS={|y（RS）}【定义7.8】

（RS）P=R（SP）

Rm=RR…R

设RXY,SYZ,则（RS）1=S1R1【定理7.2】

R在A上的限制R↾A={|xRy∧x∈A}

A在R下的像R[A]=ran（R↾A）【定义7.9】

自反的：

若x∈A，都有R,则称R是自反的

反自反的：

若x∈A，都有R,则称R是反自反的.【定义7.11】

对称的：

对任意x,yA,满足,若R,则R

反对称的：

对任意x,yA,满足，若R且R,则x=y【定义7.12】

传递的：

对任意的x,y,zA,满足:

若R且R,则R,则称R是传递的【定义7.13】

自反闭包（对称、传递）：

设R是A上的二元关系,如果有另一个关系R'满足:

1R'是自反（对称、传递）的;

2R'R;

3对于任何自反的关系R”,若R"R,则有R"R'.

则称关系R'为R的自反闭包.记为r（R）（ 对称闭包s（R）和传递闭包t（R））。

【定义7.14】

设R为A上的关系,则有

（1）r（R）=R∪IA

（2）s（R）=R∪R1

（3）t（R）=R∪R2∪R3∪…（若|A|=n，则t（R）=R∪R2∪…∪Rn）

等价关系：

设R为集合A上的一个二元关系。

若R是自反的,对称的,传递的,则称R为A上的等价关系【定义7.15】

等价类：

设R为集合A上的等价关系,对aA,定义:

[a]R={x|xA且R}称之为元素a关于R的等价类。

【定义7.16】

给定A上的等价关系R,对于a,bA有当且仅当[a]R=[b]R【定理17.4】

商集：

设R是A上的等价关系，定义A/R={[a]R|aA}称之为A关于R的商集.【定义7.17】

划分：

设A为非空集合,若A的子集族π（πP（A））满足:

（1）π

（2）xy（x,yπ∧x≠yx∩y=）

（3）∪π=A

则称π是A的一个划分,称π中的元素为A的划分块.【定义7.18】

给定集合A上的等价关系R,则商集A/R是A的一个划分.

集合A的一个划分π诱导出A上的一个等价关系R.R定义为R={|x,yA且x,y在π的同一分块中}