命题：能够判断真假的命题称为命题。
命题公式：如果在复合命题中p、q、r等既可以表示命题常数，又可以表示命题变量，这样的复合命题形式称为命题公式。
命题替换：设A 为命题表达式，p,p,p 为A 中出现的所有命题变量。将一组真值分配给p,p,…,p称为A的赋值或解释。如果指定的一组值使得A的值为真，则称为真赋值。
真值表：包含n（n1）个命题变量的命题表达式。总共包含2^n 组作业。列出一个表中所有赋值下命题表达式A的值。这称为A 的真值表。
命题公式的类型： (1) 如果A 在各种赋值下取值为true，则A 称为同义反复或永远为真公式。
(2) 如果A 基于其赋值的所有值都为false，则称A 是不一致的或持续为false。
(3) 如果A 至少有一个赋值集是真赋值，则A 是可满足表达式。
主析取范式：假设命题表达式A 包含n 个命题变量。如果A 的析取范式中的所有简单连词都是最小项，则该析取范式称为A 的主析取范式。
主合取范式：假设命题表达式A 包含n 个命题变量。如果A 的合取范式中的所有简单连词都是极大项，则该合取范式称为A 的主合取范式。
命题等价：假设A和B是两个命题表达式。如果AB 是同义反复，则A 和B 被认为是等价的，记为A=B。
约束变量和自由变量：在格式良好的表达式'x A 和$x A 中，x 称为引导变量，A 称为相应量词的域，x 称为约束变量，x 的出现称为。约束出现，A 中的其他出现称为自由出现（自由变量）。
一阶逻辑等价：设A 和B 为一阶逻辑的任意两个表达式。如果AB是逻辑上有效的表达式，则A和B被认为是等价的，记为A=B和A=B。是等价的表达式。
前端范式：设A为谓词表达式。如果A 具有以下形式，我们称A 为前端范式：
集合的基本运算：并、交、差、相对补运算、对称差运算。
笛卡尔积：由有序对组成的集合，其中A 和B 为第一个元素，B 的第二个元素称为A 和B 的笛卡尔积，表示为AB。
二元关系：如果集合R 为空或者其所有元素都是有序对，则称集合R 为二元关系。
特殊关系：(1)、空关系： (2)全局关系：EA={x, y xA yA }=AA
(3) 恒等关系：IA={x, x | xA}
(4) 有如下关系：LA={x, y| x, yAxyA},A R
(5) 整除关系：R={x, y| x, y x y}， 是集合族
二元关系的运算：令R为二元关系。
(1) R中所有有序对的第一个元素的集合称为R的域。 domR={ x , yR)}
(2) R 中所有有序对的第二个元素的集合称为范围R ranR={y $x (x, yR)}。
(3) R的定义域与取值范围的并集称为R的定义域。 fldR=domR ranR
二元关系的性质：自反性、反自反性、对称性、反对称性、传递性。
等价关系：集合A 上的二元关系R 如果是递归、对称和传递的，则称为等价关系。假设R是A上的等价关系。 x和y是A中的任意元素，表示为x~y。
等价类：设R是关于A的等价关系。对于任何'xA，令[x]R={ yA x R y } 并将[x]R 称为x 相对于的关系。 R 等价类。
偏序关系：假设R是集合A上的二元关系。如果R 是递归的、反对称的和传递的，则R 称为A 上的偏序，有序对A 称为R。
函数性质：设f: AB。
(1) 如果ranf=B，则f 被称为满射（向上）。
(2) 如果'y' ranf 中存在唯一的x A 使得f(x)=y，则f 被称为单内射(--)。
(3) 如果f 既是双射又是内射，则称f 是双射的（—至顶部）。
无向图：这是一个有序二元群V，E，用G表示。这里，
(1) V^称为顶点集，其元素称为顶点或节点。
(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称为零图。
基图：将有向图变为无向图得到的新图称为有向图的基图。
图同构：用图来表示图时，由于顶点的位置和边的形状不同，同一关系可能用不同的图来表示。这种图称为图同构。
加权图：在处理与图相关的实际问题时，通常对该值进行加权。这称为加权图或授权图。
连通图：如果无向图是平凡的或者图中任意两个顶点相连，则称G 是连通图。否则，它被称为截断图。假设D是有向图。如果D 的基本图是连通图，则如果D 的两个顶点中至少有一个可以到达另一个，则称D 是弱连通的。单向连接图。如果D 的任意两个顶点相互可达，则称D 是强连通图。
欧拉图：经过图中每条边恰好一次并经过所有不动点的路径（环）称为欧拉路径（环）。使用欧拉回路的图称为欧拉图。
哈密顿图：仅经过图中每个顶点一次的路径（环）称为哈密顿路径（环）。 具有哈密顿环的图称为哈密顿图。
平面图：如果可以在平面上绘制图G，并且在固定点之外不发生交点，则称G 为平面图。没有边相交绘制的图称为G 的平面嵌入。
二部图：若无向图G=的顶点集合V可以分为两个子集V1和V2（V1V2=f），则G的任意边的两个端点分别属于V1和V2。对于V2，G称为二部图（偶图）。二部图可记为G=V1, V 2 , E , V1 和V 2 ，称为互补顶点子集。
树的定义：无环连接的无向图称为无向树，简称树，常用来表示树。平凡图称为平凡树。如果无向图G至少有两个连通的分支，并且每个连接都是一棵树，则G称为森林。在无向图中，悬挂的顶点称为叶子，度数为2 或更高的顶点称为分叉。
树的性质： 性质1. 假设G=V且E是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)。
最小生成树：如果T是无向图G的子图并且是一棵树，则T称为G的树。如果T 是G 的树和生成子图，则称T 是G 的生成树。设T 为G 的生成树。如果eE(G)，eE(T)，则e称为T的分支，否则称为T的串。导出的子图G[E(G)-E(T)]也称为T的协树，记为T。
最优二叉树：假设二叉树T 有t 个叶子v1, v2, vt，权重分别为w1, w2, wt。这称为W(t)=wil(vi)。 T 的重量。 l(vi) 是vi 的层数。在所有有t 个叶子、权重为w1、w2、wt 的二叉树中，权重最小的二叉树称为最优二叉树。
最优前缀码：使用霍夫曼算法找到最优二叉树。使用最佳前缀码传输相应的符号可以最大限度地减少传输的二进制数字的数量。
隐含推理
E1
p=P
E12
R(PP)=R
E2
PQ=QP
E13
R(PP)=R
E3
PQ=QP
E14
R(PP)=T
E4
(PQ)R=P(QR)
E15
R(PP)=F
E5
(PQ)R=P(QR)
E16
PQ=PQ
E6
P(QR)=(PQ)(PR)
E17
(PQ)=PQ
E7
P(QR)=(PQ)(PR)
E18
PQ=QP
E8
(PQ)=PQ
E19
P(QR)=(PQ)R
E9
(PQ)=PQ
E20
PDQ=(PQ)(QP)
E10
PP=P
E21
PDQ=(PQ)(PQ)
E11
PP=P
E22
(PDQ)=PDQ
等价公式表
PQ=P
简化形式
PQ=Q
简化形式
P=PQ
添加在
P=PQ
变形插件
Q=PQ
变形插件
(PQ)=P
变换简化形式
(PQ)=Q
变换简化形式
p(PQ)=Q
假设推理
Q(PQ)=P
拒绝类型
p(PQ)=Q
析取三部分表达式
(PQ)(QR)=PR
条件三部分表达式
(PDQ) (QDR)=PDR
二条件三级式
(PQ)(RS)(PR)=QS
建立联系的困境
(PQ)(RS)(PR)=QS
析取结构的困境
PQ=(PR)(QR)
前部和后部附加组件
PQ=(PR)(QR)
前后附加组件
E23
（
x)((Ax)(Bx))=(
x)(Ax)(
x)(Bx)
E30
（
x)(轴)B=(
x) ((Ax)B)
E24
（
x)((Ax)(Bx))=(
x)(轴)(
x)(Bx)
E31
（
x)(轴)B=(
x) ((Ax)B)
E25
(
x)(斧)=(
x)(斧头)
E32
A(
x)(Bx)=(
x) (A(Bx))
E26
(
x)(斧)=(
x)(斧头)
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)(轴)(
x)(Bx)
E29
（
x)((Ax)(Bx))=(
x)(轴)(
x)(Bx)
I19
（
x)(轴)(
x)(Bx)=(
x)((Ax)(Bx))
套装身份：P61
幂等定律：AA=A；AA=A；
结合律： (AB)C=A(BC)； (AB)C=A(BC)；
交换律：AB=BA；AB=BA；
分配律：A(BC)=(AB)(AC) A(BC)=(AB)(AC)
恒等法：Af=AAE=A；
零定律：AE=Af=f；
排中律：A~A=E
矛盾律：A~A=ff
吸收定律：A(AB)=A；A(AB)=A；
德摩根定律：A-(BC)=(A-B)(A-C)；A-(BC)=(A-B)(A-C)；
（BC）=BC；（BC）=BC；
双重否定定律：~(~A)=A
操纵二元关系：
假设F、G和H具有任意关系。
(1) (F -1) -1=F (2) dom(F -1)=ranF ; ran (F -1)=domF
(3) (F G ) H=F (G H ) (4) (F G ) - 1=G - 1 F - 1
令R 为A 上的关系（幂运算）
(1) R={x, x| xA} (2) R ^n=R ^(n-1) R, n1 (3) R R=R R=R
图的矩阵表示：
(1)无向图的相关矩阵：设无向图G=V,E，V={v1,v2,…,vn}，E={e1,e2,…,em}，顶点vi为mij。边的相关程度称为(mij) n´ m，作为G的相关矩阵。写作M(G)。
(2) 有向图的相关矩阵：无向图D=V,E, V={v1,v2,…,vn}, E={e1,e2,…,em}，
1、vi是ej的起点
mij=0，vi 和ej 不相关
-1，vi是ej的端点
在这种情况下，(mij)n´ m 称为D 的相关矩阵。写作M(D)。
版权声明：本文转载于网络，版权归作者所有。如有侵权，请联系本站编辑删除。
