还剩2页未读，继续阅读
文本内容:
命题称能判断真假的陈述句为命题命题公式若在复合命题中，p、q、r等不仅可以代表命题常项，还可以代表命题变项，这样的复合命题形式称为命题公式命题的赋值设A为一命题公式，pp…p为出现在A中的所有命题变项给pp…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约束变元和自由变元在合式公式xA和$xA中，称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={xy|x∈A∧y∈A}=A×A
（3）恒等关系IA={xx|x∈A}
（4）小于等于关系LA={xy|xy∈A∧x≤y∈A}AÍR
（5）整除关系RÍ={xy|x，y∈ψ∧xÍy}ψ是__族二元关系的运算设R是二元关系，
（1）R中所有有序对的第一元素构成的__称为R的定义域domR={x|$y（xy∈R）}
（2）R中所有有序对的第二元素构成的__称为R的值域ranR={y|$x（xy∈R）}
（3）R的定义域和值域的并集称为R的域fldR=domR∪ranR二元关系的性质自反性，反自反性，对称性，__称性，传递性等价关系如果__A上的二元关系R是自反的，对称的和传递的，那么称R是等价关系设R是A上的等价关系，xy是A的任意元素，记作x～y等价类设R是A上的等价关系，对任意的x∈A，令[x]R={y|y∈A∧xRy}，称[x]R为x关于R的等价类偏序关系设R是__A上的二元关系，如果R是自反的，__称的和传递的，那么称R为A上的偏序，记作≤；称序偶AR为偏序__函数的性质设f:A®B，
（1）若ranf=B，则称f是满射（到上）的
（2）若yÎranf都存在唯一的xÎA使得fx=y则称f是单射（——）的
（3）若f既是满射又是单射的，则称f是双射（——到上）的无向图是一个有序的二元组VE，记作G，其中1V¹Ф称为顶点集，其元素称为顶点或结点2E为边集，它是无序积VV的多重子集，其元素称为无向边，简称边有向图是一个有序的二元组VE记作D其中1V同无向图2E为边集，它是笛卡尔积V´V的多重子集，其元素称为有向边设G=VE是一个无向图或有向图有限图若VE是有限集，则称G为有限图n阶图若|V|=n，称G为n阶图零图若|E|=0，称G为零图当|V|=1时，称G为平凡图基图将有向图变为无向图得到的新图，称为有向图的基图图的同构在用图形表示图时，由于顶点的位置不同，边的形状不同，同一个事物之间的关系可以用不同的图表示，这样的图称为图同构带权图在处理有关图的实际问题时，往往有值的存在，一般这个值成为权值，带权值的图称为带权图或赋权图连通图若无向图是平凡图，或图中任意两个顶点都是连通的，则称G是连通图否则称为非连通图设D是一个有向图，如果D的基图是连通图，则称D是弱连通图，若D中任意两个顶点至少一个可达另一个，则称D是单向连通图若D中任意两个顶点是相互可达的，则称D是强连通图欧拉图通过图中所有边一次且仅一次并且通过所有定点的通路（回路），称为欧拉通路（回路）存在欧拉回路的图称为欧拉图哈密顿图经过图中每个顶点一次且仅一次的通路（回路），称为哈密顿通路（回路），存在哈密顿回路的图称为哈密顿图平面图一个图G如果能以这样的方式画在平面上出定点处外没有变交叉出现，则称G为平面图画出的没有边交叉出现的图称为G的一个平面嵌入二部图若无向图G=〈VE〉的顶点__V可以划分成两个子集V1和V2（V1∩V2=f），使G中的任何一条边的两个端点分别属于V1和V2，则称G为二部图（偶图）二部图可记为G=V1V2EV1和V2称为互补顶点子集树的定义连通无回路的无向图称为无向树，简称树，常用T表示树平凡图称为平凡树若无向图G至少有两个连通分支，每个连通都是树，则称G为森林在无向图中，悬挂顶点称为树叶，度数大于或等于2的顶点称为分支点树的性质性质
1、设G=VE是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可知，2n-1=∑dvi≥x+2n-x由上式解出x≥
2.最小生成树设T是无向图G的子图并且为树，则称T为G的树若T是G的树且为生成子图，则称T是G的生成树设T是G的生成树e∈EG，若e∈ET，则称e为T的树枝，否则称e为T的弦并称导出子图G[EG-ET]为T的余树，记作T最优二元树设2叉树T有t片树叶v1v2…vt，权分别为w1w2…wt，称Wt=wilvi为T的权，其中lvi是vi的层数在所有有t片树叶，带权w1w2…wt的2叉树中，权最小的2叉树称为最优2叉树最佳前缀码利用Huff__n算法求最优2叉树，由最优2叉树产生的前缀码称为最佳前缀码，用最佳前缀码传输对应的各符号能使传输的二进制数位最省蕴含式推理E1┐┐p=PE12R∨P∧┐P=RE2P∧Q=Q∧PE13R∧P∨┐P=RE3P∨Q=Q∨PE14R∨P∨┐P=TE4P∧Q∧R=P∧Q∧RE15R∧P∧┐P=FE5P∨Q∨R=P∨Q∨RE16P→Q=┐P∨QE6P∧Q∨R=P∧Q∨P∧RE17┐P→Q=P∧┐QE7P∨Q∧R=P∨Q∧P∨RE18P→Q=┐Q→┐PE8┐P∧Q=┐P∨┐QE19P→Q→R=P∧Q→RE9┐P∨Q=┐P∧┐QE20PQ=P→Q∧Q→PE10P∨P=PE21PQ=P∧Q∨┐P∧┐QE11P∧P=PE22┐PQ=P┐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条件三段式PQ∧QR=PR双条件三段式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前后附加式E23xAx∨Bx=xAx∨xBxE30xAx→B=xAx→BE24xAx∧Bx=xAx∧xBxE31xAx→B=xAx→BE25┐xAx=x┐AxE32A→xBx=xA→BxE26┐xAx=x┐AxE33A→xBx=xA→BxE27xA∨Bx=A∨xBxI17xAx∨xBx=xAx∨BxE28xA∧Bx=A∧xBxI18xAx∧Bx=xAx∧xBxE29xAx→Bx=xAx→xBxI19xAx→xBx=xAx→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=f吸收律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二元关系的运算设FGH是任意的关系，
（1）（F-¹-¹=F
（2）domF-¹=ranF；ranF-¹=domF
（3）（F◦G◦H= F◦G◦H
（4）（F◦G-¹=G-¹◦F-¹设R是A上的关系（幂运算）
（1）Rº={x，x|x∈A}
（2）R^n=R^n-1◦R，n≥1
（3）R◦Rº=Rº◦R=R图的矩阵表示
（1）无向图的关联矩阵设无向图G=VEV={v1v2…vn}E={e1e2…em}，令mij为顶点vi与边的关联次数，则称（mij）n´m为G的关联矩阵记为MG
（2）有向图的关联矩阵设无向图D=VEV={v1v2…vn}E={e1e2…em}，1vi是ej的始点mij=0vi与ej不关联-1，vi是ej的终点则称（mij）n´m为D的关联矩阵记为MD。
个人认证
优秀文档
获得点赞 0
