数学逻辑的规则规定了推理数学语句的方法。希腊哲学家亚里士多德是逻辑推理的先驱。逻辑推理为许多数学领域以及计算机科学提供了理论基础。它在计算机科学中有很多实际应用，例如计算机器的设计、人工智能、编程语言的数据结构定义等。主要类别数学逻辑可以大致分为三类。命题逻辑 - 命题逻辑关注可以赋予“真”和“假”真值语句。目的是分析这些语句，无论是单独的还是组合的。谓词… 阅读更多

设'G'是一个具有'n'个顶点和'm'条边的连通图。G的一个生成树'T'包含(n-1)条边。因此，为了得到一个生成树，你需要从'G'中删除的边的数量 = m-(n-1)，这称为G的电路秩。这个公式是正确的，因为在一个生成树中，你需要有'n-1'条边。在'm'条边中，你需要在图中保留'n-1'条边。因此，从'm'中删除'n-1'条边得到为了得到一个生成树而需要从图中删除的边，这些边不应该形成… 阅读更多

树的中心是具有最小离心率的顶点。树G中顶点X的离心率是顶点X与树的任何其他顶点之间的最大距离。最大离心率是树的直径。如果一棵树只有一个中心，则称为中心树；如果一棵树有多个中心，则称为双中心树。每棵树要么是中心树，要么是双中心树。查找树的中心和双中心的算法步骤1 - 从给定的树中删除所有度数为1的顶点，以及… 阅读更多

二分图 - 如果图G的顶点集可以分成两个不相交的集合V1和V2，以这样的方式，图中的每条边都连接V1中的一个顶点和V2中的一个顶点，并且G中没有边连接V1中的两个顶点或V2中的两个顶点，则图G称为二分图。完全二分图 - 完全二分图是一个二分图，其中第一组中的每个顶点都连接到第二组中的每一个顶点。… 阅读更多

图是一组点，称为节点或顶点，它们通过一组称为边的线相互连接。图的研究，或图论，是数学、工程和计算机科学领域许多学科的重要组成部分。图论定义 - 图（表示为G = (V, E)）由一组非空顶点或节点V和一组边E组成。顶点a代表边的端点。一条边连接两个顶点a、b，并由它连接的顶点集表示。示例 - 让我们… 阅读更多

单射/一对一函数函数$f: A \rightarrow B$是单射或一对一函数，如果对于每个$b \in B$，最多存在一个$a \in A$使得$f(s) = t$。这意味着如果$a_1 e a_2$蕴含$f(a1) e f(a2)$，则函数f是单射的。示例$f: N \rightarrow N, f(x) = 5x$是单射的。$f: N \rightarrow N, f(x) = x^2$是单射的。$f: R\rightarrow R, f(x) = x^2$不是单射的，因为$(-x)^2 = x^2$满射/到函数函数$f: A \rightarrow B$是满射（到），如果f的像等于其值域。等价地，对于每个$b \in B$，… 阅读更多

为了对量化语句得出结论，有四个推理规则，它们统称为谓词演算的推理理论。推理规则表推理规则名称 $$\begin{matrix} \forall x P(x) \ \hline \therefore P(y) \end{matrix}$$ 规则US：普遍特例 $$\begin{matrix} P(c) \text { 对于任何c} \ \hline \therefore \forall x P(x) \end{matrix}$$ 规则UG：普遍泛化 $$\begin{matrix} \exists x P(x) \ \hline \therefore P(c) \text { 对于任何c} \ \end{matrix}$$ 规则ES：存在特例 $$\begin{matrix} P(c) \text { 对于任何c} \ \therefore \exists x P(x) \end{matrix}$$ 规则EG：存在泛化规则US：普遍特例 - 从$(x)P(x)$，可以得出$P(y)$。规则US：… 阅读更多

独立集用集合表示，其中不应该有任何相互邻接的边。任何两条边之间不应该有任何公共顶点。不应该有任何相互邻接的顶点。任何两个顶点之间不应该有任何公共边。独立线集设'G' = (V, E)为一个图。E的一个子集L被称为'G'的独立线集，如果L中没有两条边是邻接的。这样的集合称为独立线集。示例让我们考虑以下子集 -L1 = {a, b} L2 = {a, b} … 阅读更多

独立集用集合表示，其中不应该有任何相互邻接的边。任何两条边之间不应该有任何公共顶点。不应该有任何相互邻接的顶点。任何两个顶点之间不应该有任何公共边。独立顶点集设'G' = (V, E)为一个图。'V'的一个子集被称为'G'的独立集，如果'S'中没有两个顶点是邻接的。示例考虑来自上述图的以下子集 -S1 = {e} S2 = {e, f} S3 = {a, g, c} S4 = {e, d}显然，S1 … 阅读更多

邻接矩阵邻接矩阵用于表示图。我们可以使用邻接矩阵表示有向图和无向图。以下是邻接矩阵的关键属性。属性邻接矩阵A[V][V]是一个大小为V × V的二维数组，其中V是无向图中顶点的数量。如果Vx和Vy之间存在一条边，则A[Vx][Vy] = 1且A[Vy][Vx]=1，否则值为零。对于有向图，如果Vx和Vy之间存在一条边，则A[Vx][Vy]=1，否则值为零。邻接矩阵… 阅读更多