资源描述：
《离散数学部分概念和公式总结》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、离散数学部分概念和公式总结命题:称能判断真假的陈述句为命题。命题公式:若在复合命题中，p、q、r等不仅可以代表命题常项，还可以代表命题变项，这样的复合命题形式称为命题公式。命题的赋值:设A为一命题公式，p,p,・・・,p为11!现在A中的所有命题变项。给p,p,・・・,p指定一组真值，称为对A的一个赋值或解释。若指定的一组值使A的值为真，则称成真赋值。真值表:含n（n^l）个命题变项的命题公式，共有2%组赋值。将命题公式A在所有赋值下的取值情况列成表，称为A的真值表。命题公式的类型:（1）若A在它的各种赋值下均取值为真，则称A
2、为重言式或永真式。（2）若A在它的赋值下取值均为假，则称A为矛盾式或永假式。（3）若A至少存在一组赋值是成真赋值，则A是可满足式。主析取范式:设命题公式A中含n个命题变项，如果A得析取范式中的简单合取式全是极小项，则称该析収范式为A的主析収范式。主合取范式:设命题公式A屮含n个命题变项，如果A得析取范式屮的简单合析式全是极大项，则称该析取范式为A的主析取范式。命题的等值式:设A、B为两命题公式，若等价式A-B是重言式，则称A与B是等值的,记作A<=>Bo约束变元和自由变元:在合式公式VxA和％A中，称x为指导变项，称A为相应量
3、词的辖域，x称为约束变元，x的出现称为约束出现，A中其他出现称为自由出现（自由变元）。一阶逻辑等值式:设A,B是一阶逻辑中任意的两公式，若A-B为逻辑有效式，则称A与B是等值的，记作A<=>B,称A<=>B为等值式。前束范式:设A为一谓词公式，若A具有如下形式Qlx1Q2x2Qk・rkB,称A为前束范式。集合的基本运算:并、交、差、相对补和对称差运算。笛卡尔积:设A和B为集合，用A小元素为第一元素，用B小元素为第二元素构成有序对组成的集合称为A和B的笛卡尔积，记为AXBo二元关系:如果一个集合R为空集或者它的元素都是有序对，则
4、称集合R是一个二元关系。特殊关系:（1）、空关系：①（2）全域关系：EA={
5、x丘AAA}=AXA（3）恒等关系：IA={
6、xWA}(4)小于等于关系：LA={
7、x,yeAAx^yeA},AcR(5)整除关系：Rc={
8、x,yW巾Axcy},ip是集合族二元关系的运算:设R是二元关系，（1）7?中所有有序对的第一元素构成的集合称为R的定义域domR={x
9、3y（e/?）}（2）R屮所有有序对的第二元素构成的集合称为的值域ranR={y
10、3.x（WR）}（3）R的定义
11、域和值域的并集称为R的域fld&domRUran/?二元关系的性质:自反性，反自反性，对称性，反对称性，传递性。等价关系:如果集合A上的二元关系R是自反的，对称的和传递的，那么称7?是等价关系。设R是A上的等价关系，■歹是A的任意元素，记作x〜y。等价类:设/?是A上的等价关系，对任意的VxEA,令［x］R={y
12、yWAAxRy},称［兀］R为x关于R的等价类。偏序关系:设R是集合A上的二元关系，如果R是自反的，反对称的和传递的，那么称R为A上的偏序，记作W；称序偶为偏序集合。函数的性质:设/:A->B,（1）#ran/=B,
13、则称.f是满射（到上）的。（2）若Vyerar/都存在唯一的xeA使得f（x）=y,则称/是单射（）的。（3）若/既是满射又是单射的，则称/是双射（——到上）的。无向图:是一个有序的二元组,记作G,其中：（1）*0称为顶点集，其元素称为顶点或结点。（2）E为边集，它是无序积V&V的多重子集，其元素称为无向边，简称边。有向图：是一个有序的二元组记作D其中（1）V同无向图。（2）E为边集，它是笛卡尔积VxV的多重子集，其元素称为有向边。设G=是一个无向图或有向图。有限图:若是有限集，则称G为有限图。n阶图:若
14、
15、V
16、=n,称G为n阶图。零图:若
17、£
18、=0,称G为零图，当
19、V
20、=l时，称G为平凡图。基图:将有向图变为无向图得到的新图，称为有向图的基图。图的同构:在用图形表示图时，由于顶点的位置不同，边的形状不同，同一个事物Z间的关系可以用不同的图表示，这样的图称为图同构。带权图:在处理有关图的实际问题时，往往有值的存在，一般这个值成为权值，带权值的图称为带权图或赋权图。连通图:若无向图是平凡图，或图中任意两个顶点都是连通的，则称G是连通图。否则称为非连通图。设D是一个有向图，如果Q的基图是连通图，则称D是弱连通图，若Q中任意两个顶点至少
21、一个可达另一个，则称D是单向连通图。若D中任意两个顶点是相互可达的，则称D是强连通图。欧拉图:通过图中所有边一次且仅一次并且通过所有定点的通路(回路)，称为欧拉通路(回路)。存在欧拉冋路的图称为欧拉图。哈密顿图:经过图中每个顶点一次且仅一次的通路(回路)，称为哈密顿通路(回路
