离散数学知识点

1．内容及范围主要来自ppt，标签对应书本2．可能有错，仅供参考离散数学知识点说明：定义：红色表示。定理性质：橙色表示。公式：蓝色表示。算法:绿色表示页码：灰色表示数理逻辑：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的合取，记以pq，读作p且q。pq是真的当且仅当p和q都是真的。【定义1.2】析取词符号：设p，q是两个命题，命题“p或者q”称为p，q的析取，记以pq，读作p或q。pq是真的当且仅当p，q中至少有一个是真的。【定义1.3】蕴含词符号：设p，q是两个命题，命题“如果p，则q”称为p蕴含q，记以pq。pq是假的当且仅当p是真的而q是假的。【定义1.4】等价词符号：设p，q是两个命题，命题“p当且仅当q”称为p等价q，记以pq。pq是真的当且仅当p，q或者都是真的，或者都是假的。【定义1.5】合式公式:(1)命题常元和变元符号是合式公式；(2)若A是合式公式，则(A)是合式公式，称为A的否定式；(3)若A，B是合式公式，则(AB)，(AB)，(AB)，(AB)是合式公式；(4)所有合式公式都是有限次使用(1)，(2)，(3)、(4)得到的符号串。子公式:如果Ｘ是合式公式A的一部分，且Ｘ本身也是一个合式公式，则称Ｘ为公式A的子公式。【定义1.6】赋值（指派，解释）：设是命题变元集合，则称函数v：{1，0}是一个真值赋值。【定义1.8】真值表：公式A在其所有可能的赋值下所取真值的表，称为A的真值表。【定义1.9】重言式（永真式）:任意赋值v，vA矛盾式（永假式）:任意赋值v，有vA【定义1.10】等值式：若等价式AB是重言式，则称A与B等值，记作AB。【定义2.1】基本等值式双重否定律AA幂等律AAA,AAA交换律ABBA,ABBA结合律(AB)CA(BC),(AB)CA(BC)分配律A(BC)(AB)(AC),A(BC)(AB)(AC)德摩根律(AB)AB,(AB)AB吸收律A(AB)A,A(AB)A零律A,A同一律AA,AA排中律AA矛盾律AA蕴涵等值式ABAB等价等值式AB(AB)(BA)假言易位ABBA等价否定等值式ABAB归谬论(AB)(AB)A置换规则：设Ｘ是公式A的子公式,ＸY。将A中的Ｘ（可以是全部或部分X）用Y来置换，所得到的公式B，则AB。文字:设A（命题变元集）,则A和A都称为命题符号A的文字，其中前者称为正文字，后者称为负文字。【定义2.2】析取范式：形如A1A2…An(n1)的公式称为析取范式，其中Ai(i=1,…,n)是由文字组成的合取范式。合取范式：形为A1A2…An(n1)的公式称为合取范式，其中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】异或PQ：(PQ)条件否定PQ：(PQ)与非PQ：(PQ)或非PQ：(PQ)【定义2.8】{},{↓}都是联结词的完备集【定理2.7】重言蕴含式：当且仅当PQ是一个重言式时，称P重言蕴含Q，记为PQ。有效结论：设A、C是两个命题公式，若AC，称C是A的有效结论。【定义3.1】推理定律——重言蕴涵式1.A(AB)附加律2.(AB)A化简律3.(AB)AB假言推理c4.(AB)BA拒取式5.(AB)BA析取三段论6.(AB)(BC)(AC)假言三段论7.(AB)(BC)(AC)等价三段论8.(AB)(CD)(AC)(BD)构造性二难(AB)(AB)B构造性二难(特殊形式)9.(AB)(CD)(BD)(AC)破坏性二难形式系统:一个形式系统I由下面四个部分组成：(1)非空的字母表，记作A(I).(2)A(I)中符号构造的合式公式集，记作E(I).(3)E(I)中一些特殊的公式组成的公理集，记作AX(I).(4)推理规则集，记作R(I).记I=A(I),E(I),AX(I),R(I),其中A(I),E(I)是I的形式语言系统,AX(I),R(I)是I的形式演算系统.自然推理系统:无公理,即AX(I)=公理推理系统:推出的结论是系统中的重言式,称作定理【定义3.2】P规则：在推导过程中,可以随时添加前提。T规则：在推导过程中,可以引入公式S，它是由其前题的一个或多个公式借助重言、蕴含而得到的。推理（证明）：从前提A1,A2,,Ak到结论B的推理是一个公式序列C1,C2,,Cl.其中Ci(1il)是某个Aj,或者可由序列中前面的公式应用推理规则得到,并且Cl=B。【定义3.3】CP规则(演绎定理)：若{R}|-S，则|-RS,其中为命题公式的集合。个体词：用于表示命题中主语部分的符号或符号串。个体常元表示确指个体。个体变元表示不确指个体。个体域:个体变元的取值范围，常用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是公式，则(AB)，(AB)，AB)，(AB)是公式；(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):DnD；(4)对应于每一个n元谓词符号A都有一个n元关系(A)Dn。【定义4.7】赋值：解释I中的赋值v为每一个个体变元x指定一个值v(x）D，即设V为所个体变元的集合，则赋值v是函数v:VD.可满足的：给定公式A，若在某一解释中至少有一种赋值使A取值为1，则称A为可满足的。否则称A是不可满足的。等值式AB：若AB是有效的【定义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(BA(x))BxA(x)x(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(BA(x))BxA(x)（4）量词分配等值式x(A(x)B(x))xA(x)xB(x)x(A(x)B(x))xA(x)xB(x)（5）多个量词的使用