［新西兰］新西兰地理

离散数学部分概念和公式总结(考试专用)[管理资料] 命题:称能判断真假的陈述句为命题。 命题公式:若在复合命题中，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 , x> | x?A}(3)恒等关系:IA={| 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 =, )，使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叉树产生的前缀码称为最佳前缀码，用最佳前缀码传输对应的各符号能使传输的二进制数位最省。 蕴含式推理 E ??p<=>P E R?(P??P)<=>R 112E P?Q<=>Q?P E R ?(P??P)<=>R 213E P?Q<=>Q?P E R?(P??P)<=>T 314E (P?Q)?R<=>P?(Q?R) E R?(P??P)<=>F 415E (P?Q)?R<=>P?(Q?R) E P?Q<=>?P?Q 516E P?(Q?R)<=>(P?Q)?(P?R) E ?(P?Q)<=> P??Q 617E P?(Q?R)<=>(P?Q)?(P?R) E P?Q<=>?Q??P 718E ?(P?Q)<=> ?P??Q E P?(Q?R)<=>(P?Q)?R 819E ?(P?Q)<=> ?P??Q E P Q<=>(P?Q)?(Q?P) 920E P?P<=>P E P Q<=>(P?Q)?(?P??Q) 1021E P?P<=>P E ?(P Q) <=> P ?Q 1122等值公式表 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 条件三段式 (P Q) ?(Q R)=>P R 双条件三段式 (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) 前后附加式 ,E (x)((Ax)?(Bx))<=>( x)(Ax)?(x)(Bx) E (x)(Ax) ?B<=>(x) ((Ax)?B) 23，，，30， ,,,,E (x)((Ax)?(Bx))<=>(x)(Ax)?(x)(Bx) E (x)(Ax) ?B<=>(x) ((Ax)?B) ，2431 ,,,E ?(x)(Ax)<=>(x)?(Ax) E A?(x)(Bx) <=>(x) (A?(Bx)) ，2532 ,E ?(x)(Ax)<=>(x)?(Ax) E A?(x)(Bx) <=>(x) (A?(Bx)) ，，，2633 ,,,,,E (x)(A?(Bx))<=>A?(x)(Bx) I (x)(Ax)?(x)(Bx) =>(x)((Ax)?(Bx)) 2717 ,,E (x)(A?(Bx))<=>A?(x)(Bx) I (x)((Ax)?(Bx)) =>(x)(Ax)?(x)(Bx) ，，，2818 ,,,,E (x)((Ax)?(Bx))<=>(x)(Ax)?(x)(Bx) I (x)(Ax)?(x)(Bx) =>(x)((Ax)?(Bx)) ，，2919 集合恒等式: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?, =A ;A?E=A 零 律:A?E =A ;A?, = , 排中律:A?~A=E 矛盾律:A?~A =, 吸收律: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;~,=E;~E=, 双重否定律:~(~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) 。