离散数学部分概念和公式总结(考试专用).doc

命题：称能判断真假的陈述句为命题。
命题公式：若在复合命题中，p、q、r等不仅可以代表命题常项，还可以代表命题变项，这样的复合命题形式称为命题公式。
命题的赋值：设A为一命题公式，p ,p ,…,p 为出现在A中的所有命题变项。给p ,p ,…,p 指定一组真值，称为对A的一个赋值或解释。若指定的一组值使A的值为真，则称成真赋值。
真值表：含n（n≥1）个命题变项的命题公式，共有2^n组赋值。将命题公式A在所有赋值下的取值情况列成表，称为A的真值表。
命题公式的类型：（1）若A在它的各种赋值下均取值为真，则称A为重言式或永真式。
（2）若A在它的赋值下取值均为假，则称A为矛盾式或永假式。
（3）若A至少存在一组赋值是成真赋值，则A是可满足式。
主析取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合取式全是极小项，则称该析取范式为A的主析取范式。
主合取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合析式全是极大项，则称该析取范式为A的主析取范式。
命题的等值式：设A、B为两命题公式，若等价式A↔B是重言式，则称A与B是等值的，记作A<=>B。
约束变元和自由变元：在合式公式"x A和 $x A中，称x为指导变项，称A为相应量词的辖域，x称为约束变元，x的出现称为约束出现，A中其他出现称为自由出现（自由变元）。
一阶逻辑等值式：设A，B是一阶逻辑中任意的两公式，若A↔B为逻辑有效式，则称A与B是等值的，记作A<=>B，称A<=>B为等值式。
前束范式：设A为一谓词公式，若A具有如下形式Q1x1Q2x2Qk…xkB，称A为前束范式。
集合的基本运算：并、 交、差、相对补和对称差运算。
笛卡尔积：设A和B为集合，用A中元素为第一元素，用B中元素为第二元素构成有序对组成的集合称为A和B的笛卡尔积，记为A×B。
二元关系：如果一个集合R为空集或者它的元素都是有序对，则称集合R是一个二元关系。
特殊关系：（1）、空关系：Φ （2）全域关系：EA={ | x∈A ∧ y∈A }= A×A
（3）恒等关系：IA={ | x∈A}
（4）小于等于关系：LA={| x, y∈A∧x≤y∈A },A Í R
（5）整除关系： RÍ ={| x，y∈ψ ∧ x Í y} ,ψ是集合族
二元关系的运算：设R是二元关系，
（1）R中所有有序对的第一元素构成的集合称为R的定义域domR = { x | $y（∈R）}
（2）R中所有有序对的第二元素构成的集合称为R的值域ranR = {y | $x（∈R）}
（3）R的定义域和值域的并集称为R的域fldR= domR ∪ranR
二元关系的性质：自反性，反自反性，对称性，反对称性，传递性
等价关系：如果集合A上的二元关系R是自反的，对称的和传递的，那么称R是等价关系。设R是A上的等价关系，x , y是A的任意元素，记作x～y。
等价类：设R是A上的等价关系，对任意的"x∈A，令[x]R={ y | y∈A ∧ x R y }，称[x]R为x关于R的等价类。
偏序关系：设R是集合A上的二元关系，如果R是自反的，反对称的和传递的，那么称R为A上的偏序，记作≤；称序偶< A ,R >为偏序集合。
函数的性质：设f: A®B，
（1）若ranf = B，则称f 是满射（到上）的。
（2）若 "yÎ ranf 都存在唯一的x ÎA 使得f(x)=y,则称f 是单射（— —的。
（3）若f 既是满射又是单射的，则称f 是双射（— —到上）的。
无向图：是一个有序的二元组，记作G，其中：
(1) V¹Ф称为顶点集，其元素称为顶点或结点。
(2) E为边集，它是无序积V&V的多重子集，其元素称为无向边，简称边。
有向图：是一个有序的二元组,记作D,其中
(1) V同无向图。 (2) E为边集，它是笛卡尔积V´V的多重子集，其元素称为有向边。
设G=是一个无向图或有向图。
有限图：若V, E是有限集，则称G为有限图。
n阶图：若| V |=n，称G为n阶图。
零图：若| E |=0，称G为零图,当| V |=1时，称G为平凡图。
基图：将有向图变为无向图得到的新图，称为有向图的基图。
图的同构：在用图形表示图时，由于顶点的位置不同，边的形状不同，同一个事物之间的关系可以用不同的图表示，这样的图称为图同构。
带权图：在处理有关图的实际问题时，往往有值的存在，一般这个值成为权值，带权值的图称为带权图或赋权图。
连通图：若无向图是平凡图，或图中任意两个顶点都是连通的，则称G是连通图。否则称为非连通图。设D是一个有向图，如果D的基图是连通图，则称D是弱连通图，若D中任意两个顶点至少一个可达另一个，则称D是单向连通图。若D中任意两个顶点是相互可达的，则称D是强连通图。
欧拉图：通过图中所有边一次且仅一次并且通过所有定点的通路（回路），称为欧拉通路（回路）。存在欧拉回路的图称为欧拉图。
哈密顿图：经过图中每个顶点一次且仅一次的通路（回路），称为哈密顿通路（回路），存在哈密顿回路的图称为哈密顿图。
平面图：一个图G如果能以这样的方式画在平面上：出定点处外没有变交叉出现，则称G为平面图。画出的没有边交叉出现的图称为G的一个平面嵌入。
二部图：若无向图G=〈V, E〉的顶点集合V可以划分成两个子集V1和V 2（V1∩V2 =f ），使G中的任何一条边的两个端点分别属于V1和V2，则称G为二部图（偶图）。二部图可记为G = < V1, V 2 , E >, V1和V 2称为互补顶点子集。
树的定义：连通无回路的无向图称为无向树，简称树，常用T表示树。平凡图称为平凡树。若无向图G至少有两个连通分支，每个连通都是树，则称G为森林。在无向图中，悬挂顶点称为树叶，度数大于或等于2的顶点称为分支点。
树的性质：性质1、设G=是n阶m条边的无向图，则下面各命题是等价的：
（1）G是树 （2）G中任意两个顶点之间存在唯一的路径 （3）G中无回路且m=n-1.
（4）G是连通的且m=n-1. （5）G是连通的且G中任何边均为桥。 （6）G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈。
性质2、设T是n阶非平凡的无向树，则T中至少有两片树叶。
证：设T有x片树叶，由握手定理及性质1可知，2(n-1)=∑d(vi)≥x+2(n-x)由上式解出x≥2.
最小生成树：设T是无向图G的子图并且为树，则称T为G的树。若T是G的树且为生成子图，则称T是G的生成树。设T是G的生成树。e∈E(G)，若e∈E(T)，则称e为T的树枝，否则称e为T的弦。并称导出子图G[E(G)-E(T)]为T的余树，记作T。
最优二元树：设2叉树T有t片树叶v1,v2,…,vt，权分别为w1,w2,…,wt，称W(t)=wil(vi)为T的权，其中l(vi)是vi的层数。在所有有t片树叶，带权w1,w2,…,wt的2叉树中，权最小的2叉树称为最优2叉树。
最佳前缀码：利用Huffman算法求最优2叉树，由最优2叉树产生的前缀码称为最佳前缀码，用最佳前缀码传输对应的各符号能使传输的二进制数位最省。
蕴含式推理
E1
┐┐p<=>P
E12
R∨(P∧┐P)<=>R
E2
P∧Q<=>Q∧P
E13
R ∧(P∨┐P)<=>R
E3
P∨Q<=>Q∨P
E14
R∨(P∨┐P)<=>T
E4
(P∧Q)∧R<=>P∧(Q∧R)
E15
R∧(P∧┐P)<=>F
E5
(P∨Q)∨R<=>P∨(Q∨R)
E16
P→Q<=>┐P∨Q
E6
P∧(Q∨R)<=>(P∧Q)∨(P∧R)
E17

┐(P→Q)<=> P∧┐Q
E7
P∨(Q∧R)<=>(P∨Q)∧(P∨R)
E18
P→Q<=>┐Q→┐P
E8
┐(P∧Q)<=> ┐P∨┐Q
E19
P→(Q→R)<=>(P∧Q)→R
E9
┐(P∨Q)<=> ┐P∧┐Q
E20
PDQ<=>(P→Q)∧(Q→P)
E10
P∨P<=>P
E21
PDQ<=>(P∧Q)∨(┐P∧┐Q)
E11
P∧P<=>P
E22
┐(PDQ) <=> PD┐Q
等值公式表
P∧Q=>P
化简式
P∧Q=>Q
化简式
P=>P∨Q
附加式
┐P=>P→Q
变形附加式
Q=>P→Q
变形附加式
┐(P→Q)=>P
变形简化式
┐(P→Q)=>┐Q
变形简化式
p∧(P→Q)=>Q
假言推论
┐Q∧(P→Q)=>┐P
拒取式
┐p∧(P∨Q)=>Q
析取三段式
(P→Q) ∧(Q→R)=>P→R
条件三段式
(PDQ) ∧(QDR)=>PDR
双条件三段式
(P→Q)∧(R→S)∧(P∧R)=>Q→S
合取构造二难
(P→Q)∧(R→S)∧(P∨R)=>Q∨S
析取构造二难
P→Q=>(P∨R) →(Q∨R)
前后附加式
P→Q=>(P∧R) →(Q∧R)
前后附加式
E23
(x)((Ax)∨(Bx))<=>( x)(Ax)∨(x)(Bx)
E30
(x)(Ax) →B<=>(x) ((Ax)→B)
E24
(x)((Ax)∧(Bx))<=>(x)(Ax)∧(x)(Bx)
E31
(x)(Ax) →B<=>(x) ((Ax)→B)
E25
┐(x)(Ax)<=>(x)┐(Ax)
E32
A→(x)(Bx) <=>(x) (A→(Bx))
E26
┐(x)(Ax)<=>(x)┐(Ax)
E33
A→(x)(Bx) <=>(x) (A→(Bx))
E27
(x)(A∨(Bx))<=>A∨(x)(Bx)
I17
(x)(Ax)∨(x)(Bx) =>(x)((Ax)∨(Bx))
E28

(x)(A∧(Bx))<=>A∧(x)(Bx)
I18
(x)((Ax)∧(Bx)) =>(x)(Ax)∧(x)(Bx)
E29
(x)((Ax)→(Bx))<=>(x)(Ax)→(x)(Bx)
I19
(x)(Ax)→(x)(Bx) =>(x)((Ax)→(Bx))

集合恒等式：P61
幂等律：A∪A=A ；A∩A=A
结合律：(A∪B)∪C=A∪(B∪C) ；(A∩B)∩C=A∩(B∩C)
交换律：A∪B=B∪A ；A∩B=B∩A
分配律：A∪(B∩C)=(A∪B)∩(A∪C) ；A∩B∪C)=(A∩B)∪(A∩C)
同一律：A∪f =A ；A∩E=A
零 律：A∪E =A ；A∩f = f
排中律：A∪~A=E
矛盾律：A∩~A =ff
吸收律：A∩(A∪B)=A；A∪ (A∩B)=A
德摩根定律：A-(B∪C)=(A-B)∩(A-C)；A-(B∩C)=(A-B)∪(A-C)
~(B∪C)= ~B∩~C；~(B∩C)= ~B∪~C；~f=E；~E=f
双重否定律：~（~A)=A
二元关系的运算：
设F,G,H是任意的关系，
（1）（F -¹) -¹= F （2）dom(F -¹)=ranF ；ran F -¹)=domF
（3）（ F ◦ G ) ◦ H =　F ◦(G ◦ H ) （4）（ F ◦ G ) - ¹ =G -¹ ◦ F -¹
设R是A上的关系（幂运算）
（1）Rº = {| x∈A} （2）R ^n = R ^(n-1) ◦ R，n≥1 （3）R ◦ Rº = Rº ◦ R = R
图的矩阵表示：
（1）无向图的关联矩阵：设无向图G=, V={v1,v2,…,vn}, E={e1,e2,…,em}，令mij为顶点vi与边的关联次数，则称（ mij ）n´ m为G的关联矩阵。记为M(G)。
（2）有向图的关联矩阵：设无向图D=, V={v1,v2,…,vn}, E={e1,e2,…,em}，
1, vi是ej的始点
mij = 0, vi与ej不关联
-1，vi是ej的终点
则称（ mij ）n´ m为D的关联矩阵。记为M(D) 。