离散数学部分概念及公式总结(考试专用).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, y | x∈A ∧ y∈A }= A×A （3）恒等关系：IA={x, x | x∈A} （4）小于等于关系：LA={x, y| x, y∈A∧x≤y∈A },A í R （5）整除关系： Rí ={x, y| x，y∈ψ ∧ x í y} ,ψ是集合族 二元关系的运算：设R是二元关系， （1）R中所有有序对的第一元素构成的集合称为R的定义域domR = { x | $y（x , y∈R）} （2）R中所有有序对的第二元素构成的集合称为R的值域ranR = {y | $x（x , y∈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 是双射（— —到上）的。 无向图：是一个有序的二元组V, E，记作G，其中： (1) V1Ф称为顶点集，其元素称为顶点或结点。 (2) E为边集，它是无序积VV的多重子集，其元素称为无向边，简称边。 有向图：是一个有序的二元组V,E,记作D,其中 (1) V同无向图。 (2) E为边集，它是笛卡尔积V′V的多重子集，其元素称为有向边。 设G=V,E是一个无向图或有向图。 有限图：若V, E是有限集，则称G为有限图。 n阶图：若| V |=n，称G为n阶图。 零图：若| E |=0，称G为零图,当| V |=1时，称G为平凡图。 基图：将有向图变为无向图得到的新图，称为有向图的基图。 图的同构：在用图形表示图时，由于顶点的位置不同，边的形状不同，同一个事物之间的关系可以用不同的图表示，这样的图称为图同构。 带权图：在处理有关图的实际问题时，往往有值的存在，一般这个值成为权值，带权值的图称为带权图或赋权图。 连通图：若无向图是平凡图，或图中任意两个顶点都是连通的，则称G是连通图。否则称为非连通图。设D是一个有向图，如果D的基图是连通图，则称D是弱连通图，若D中任意两个顶点至少一个可达另一个，则称D是单向连通图。若D中任意两个顶点是相互可达的，则