合一推断
一般化肯定前件：对于原子语句$p_i$、$p_{i}^{‘}$和$q$，存在置换$\theta $使得对所有$i$有$Subst\left( \theta ,p_{i}^{‘} \right) =Subst\left( \theta ,p_i \right) $，则有：
$$
\frac{p_{1}^{‘},p_{2}^{‘},…p_{n}^{‘},\left( p_1\land p_2\land …p_n\Rightarrow q \right)}{Subst\left( \theta ,q \right)}
$$
很容易证明一般化肯定前件是可靠的推断规则。首先，观察到，对于任意语句$p$（假设其变量是全称量化的）和任意置换$\theta $，都有$p\models Subst\left( \theta ,p \right) $。根据全称量词实例化为真。特别地，它对于满足一般化肯定前件规则条件的为真。因此，可以由$p_{1}^{‘},p_{2}^{‘},…p_{n}^{‘}$推得：
$$
Subst\left( \theta ,p_{1}^{‘} \right) \land Subst\left( \theta ,p_{2}^{‘} \right) \land …Subst\left( \theta ,p_{n}^{‘} \right)
$$
进而从蕴涵式$p_1\land p_2\land …p_n\Rightarrow q$和$Subst\left( \theta ,p_{i}^{‘} \right) =Subst\left( \theta ,p_i \right) $可以推得：
$$
Subst\left( \theta ,p_1 \right) \land Subst\left( \theta ,p_2 \right) \land …Subst\left( \theta ,p_n \right) \Rightarrow Subst\left( \theta ,q \right)
$$
一般化肯定前件是肯定前件的提升版——它将肯定前件从基本（无变量的）命题逻辑提升到一阶逻辑。提升版推断规则相比于命题化的重要优势在于，提升版推断规则只需必要的置换就可以进行特定的推断。
提升版推断规则需要找出使不同的逻辑表达式看起来相同的置换。这一过程被称作合并，是所有一阶逻辑推断算法的重要组成部分。合一算法$Unify$接收两条语句作为输入，如果存在置换，则为它们返回一个合一子：
$$
Unify\left( p,q \right) =\theta \ \text{其中\ }Subst\left( \theta ,p \right) =Subst\left( \theta ,q \right)
$$
对要合一的两条语句中的一条进行标准化分离，也就是对其变量进行重命名可以避免名称冲突导致的推断失败。返回的合一子可能不止一种，但是每一对可合一的表达式都有一个最一般合一子，在不考虑变量的重命名和置换的情况下，它是唯一的。
用于告知和询问知识库的$Tell$、$Ask$和$AskVar$函数的底层是更基本的$Store$和$Fetch$函数。$Store(s)$将语句$s$存入知识库，而$Fetch(q)$返回所有使查询$q$与知识库中某个语句合一的合一子。实现$Store$和$Fetch$最简单的方式就是在一个长列表中列出所有事实，并将每个查询与列表中的每个元素合一。这种过程很低效，却可以正常工作。
可以通过确保仅对有一定合一可能的语句进行合一来使$Fetch$更高效。例如，合一$Knows(John, x)$和$Brother(Richard, John)$就没什么意义。可以通过索引知识库中的事实来避免这种合一。一种叫作谓词索引的简单方法将所有$Knows$开头的事实放入一个存储桶内，而将所有$Brother$开头的事实放入另一个存储桶内。而这些存储桶可以用哈希表存储，以提高效率。
谓词索引对于谓词符号很多而每个符号只有少量子句的情形非常有用。但有时，一个谓词有许多子句，这就会形成一个非常大的存储桶。对于这类特殊的查询，如果除谓词外再使用附带参数一起索引事实的话，就可能改善效率。这种方法也许要用到组合的哈希表键值。这样只要用查询构造键值，就能精确地检索到能与查询合一的事实。因此，事实可以存储在多个索引键值之下，以便各种可能与之合一的查询迅速地找到它们。给定要存储的语句，可以对所有可能与之合一的查询构建索引。
包容格：格中任意节点的子节点都是对父节点进行一次置换而来，而任意两个节点的 “最高” 共同后代则是
应用最一般合一子的结果。对于只有少量参数的谓词符号，为包容格中每一个点创建一个索引是一种很好的权衡。这增加了一点点存储时间，但节省了检索时间。然而，对于有$n$个参数的谓词，其包容格含有$O(2^n)$个节点。如果允许函数符号的话，节点的数量同样是要存储的语句中项的数量的指数级。这就会导致大量的索引。
因此不得不采用一些方法将索引的范围限制为可能被查询频繁使用的节点，否则花在创建索引上的时间可能比使用索引而节省的时间还多。可以采取固定的策略，譬如只维护键值由一个谓词和单个参数构成的索引。可以习得一种自适应的策略，它能够创建索引来满足各类查询的要求。
前向链接
一阶确定子句是文字的析取式，其中必须有且仅有一个正文字。这意味着确定子句要么是原子的，要么是前件为正文字的合取、后件为单个正文字的蕴涵式。存在量词在此处不能使用，而全称量词则被隐式地表示：如果你在确定子句中看到$x$，就意味着有隐含的$∀x$量词，一阶文字可以含有变量。
数据日志知识库：数据日志是由不含函数符号的一阶确定子句组成的语言。它能够表示由关系数据库生成的陈述类型，故得名。没有了函数符号使推断更容易。
简单的前向链接推断算法从已知事实开始，触发所有前提被满足的规则，将结论添加到已知事实中。这一过程不断重复，直到查询得到回答（假设只需要一个回答）或没有新的事实被添加。注意，如果一个事实只是某个已知事实的重命名，也就是只有变量名字不同的语句，那它就不是一个“新”事实。
上图展示了简单前向链接所生成的证明树。注意，此时已不可能再产生新的推断，因为每个可以用前向链接得出的语句已经显式地被纳入知识库。这种知识库被称为推断过程的不动点。对一阶确定子句使用前向链接得到的不动点与命题前向链接中的类似，主要的区别在于一阶逻辑不动点可以含有全称量化的原子语句。
首先，简单前向链接推断是可靠的，因为每个推断都是对一般化肯定前件的应用，而一般化肯定前件是可靠的。其次，它对于确定子句知识库是完备的，也就是说，它能够对所有答案蕴涵在确定子句知识库中的查询做出回答。
对于不含有函数符号的数据日志知识库，完备性的证明相当简单。先对可能被添加的事实进行计数，这决定着迭代的次数。令$k$为最大元数（参数的数量），$p$为谓词数量，$n$为常量符号的数量。显然，基本事实的数量不可能超过$pn^k$个，因此在这么多次迭代后，算法必然已经到达了不动点。然后就可以得出论据，它非常类似于命题前向链接完备性的证明。
对于含有函数符号的一般确定子句，简单前向链接会生成无穷多的新事实，一般来说，这个问题是无法避免的，确定子句的蕴含是半可判定的。
简单前向链接推断算法为了便于理解而牺牲了效率。低效的原因有 3 个。首先，算法的内层循环试图对知识库中的每一条规则和每一条事实进行匹配。其次，算法每次迭代都检查所有规则，尽管知识库只有少量更新。最后，算法会生成许多与目标无关的事实。
（一）将规则与已知事实进行匹配
将规则的前提与知识库中的事实进行匹配的问题似乎很简单，找出与前提中的子句相匹配的事实，在被恰当索引的知识库中可以在常量时间内完成。但是在不同情况下使用不同的顺序进行匹配所需要的代价有所不同，故要使代价最小相当于求解规则前提的合取子句的排序，使总代价最小。实际上找出最优排序是$NP$困难问题，不过可以使用很好的启发式算法求解。例如，$CSP$的最小剩余值（$MRV$）启发式算法会建议优先选择对象数量最少的子句。
实际上，模式匹配与约束满足的联系十分紧密。可以将每个合取子句看作一条对它所包含的变量的约束，拓展这种想法，就能将所有有限域$CSP$表示为单个确定子句和相关的基本事实。可以断定，将确定子句与事实集进行匹配的问题是$NP$困难问题。尽管前向链接的内层循环含有$NP$困难的匹配问题，但是有三个事实可以说明前向链接往往可以高效完成：
1、真实世界知识库的大部分规则是简洁的而不是繁复的，在数据库世界中，很常用的假设是规则的长短和谓词的元数都限于一个常数，只需关心数据复杂性的问题，也就是，形式为知识库中基本事实数量的函数的推断复杂性。很容易证明前向链接的数据复杂性是多项式级别的，而非指数量级的。
2、可以考虑使匹配变得高效的规则的子类别。本质上，所有数据日志子句都可以视作定义一个$CSP$，因此，如果对应的$CSP$容易求解，则匹配也容易求解。如：使用割集调整策略和树分解策略可以大大加快算法速度。
3、可以试着消除前向链接算法中冗余的规则匹配尝试。
（二）增量前向链接
所有在第$t$次迭代中推断出的新事实必然是从至少一个在第$t−1$次迭代中推断出的新事实推得的。基于这一点可以说明可以避免这种多余的规则匹配，因为所有不需要来自第$t−1$次迭代的新事实的推断，肯定在第$t−1$次迭代时就已经得出了。据此提出引出增量前向链接算法：
在第$t$次迭代时，仅检查前提含有合取子句$p_i$的规则，$p_i$能够与在第$t−1$次迭代新产生的事实$p_{i}^{‘}$合一。规则匹配步骤随后固定$p_i$来与$p_{i}^{‘}$合一，但允许规则的其他合取子句与任意先前迭代产生的事实匹配。如果有合适的索引，就很容易找到所有能够由任意已知事实触发的规则。很多真实系统在“更新”模式下运作，也就是每次收到$Tell$时都以前向链接作为回应。推断在规则集上逐级运行，直到达到不动点。这一过程对下一个新事实重复执行。
一般来说，知识库中只有少部分规则是由新添加的已知事实而触发的。这就意味着在反复构建某些前提不满足的部分匹配时产生了大量冗余的工作。比较好的做法是，保留部分匹配，并在新事实到来时逐步补全部分匹配而非直接丢弃它们。
$Rete$算法首先求解了这一问题。算法对知识库中的规则集进行预处理来构建一个数据流网络，其中每个节点是规则前提中的一个文字。变量绑定在网络中流动，并在无法匹配某个文字时被过滤掉。如果一条规则中的两个文字共用一个变量，则每个文字的绑定会被一个相等节点过滤。当变量绑定到达一个$n$元文字的节点时，可能需要在过程继续运行前等待其他变量绑定的建立。在任意给定时刻，$Rete$网络的状态都会捕获所有规则的部分匹配，避免了大量的重新计算。
$Rete$网络和以它为基础的各种改进已经成为了所谓的产生式系统的关键组成部分。产生式系统是最早被大量使用的前向链接系统之一。产生式系统在认知架构中也很流行，认知架构也就是人类推理的模型。在这些系统中，系统的“工作记忆”对人类的短期记忆进行建模，而产生式则是长期记忆的一部分。在每个操作周期中，产生式被匹配到事实的工作记忆。条件得到满足的产生式可以在工作记忆中添加或删除事实。相比于数据库中的典型情形，产生式系统往往有很多规则，却只有很少的事实。运用适当的优化匹配技术，系统可以在有几百万条规则的情况下实时运行。
（三）不相关事实
另一个低效的原因是前向链接允许所有基于已知事实的推断，即使它们与目标并不相关。一种避免得到不相关结论的方法是使用反向链接。另一种方法是将前向链接限制到特意挑选的规则子集上。第三种方法已经出现在演绎数据库中，这是一种大规模数据库，类似于关系数据库，但使用前向链接而非$SQL$查询作为标准推断工具。它的基本原理是使用目标信息重写规则集，以便在前向推理中只考虑相关的变量绑定。演绎数据库的完整过程过于复杂，在此不详细描述，但其基本概念是从目标进行某种“通用”的反向推断，以此来找出哪些变量绑定需要被约束。因此，魔法集方法可以被认为是一种前向推断和反向预处理的混合。
