Ch3 确定性推理
是指按照某种策略从已知事实出发去推出结论的过程。
- 推理策略
主要解决推理方向、冲突消解等问题，如推理方向控制策略、求解策略、限制策略、冲突消解策略等 - 搜索策略
主要解决推理线路、推理效果、推理效率等问题。
推理的逻辑基础
-
解释：对于谓词公式\(P\)，如果对其中的常元指派一个元素，变元指派一个集合，每一个 n 元函数指派一个映射，一个 n 元谓词指派一个映射，则称为谓词公式的解释。
可以看出，一个谓词公式有很多种解释，而每种解释都对应一个真值。
-
永真：如果一个谓词公式对非空个体域\(D\)所有解释下都为真，则称为永真。
-
可满足：如果一个谓词公式对某个非空个体域\(D\)的某个解释下为真，则称为可满足。谓词公式的可满足性也称为相容性
-
等价：如果两个谓词公式在某个个体域\(D\)的所有解释下都有相同的真值，则称为等价。
-
前束范式：如果一个谓词公式的量词部分均非否定地只出现在公式的最前面，则称为前束范式。
例： \(\forall x \exists y P(x,y) \land Q(x)\) 是前束范式
-
Skolem 范式：如果一个谓词公式的量词部分均非否定地只出现在公式的最前面，且所有的存在量词都在全称量词之前，则称为 Skolem 范式。
例： \(\exist y \forall x P(x,y) \land Q(x)\)
-
置换： 可以简单理解为在一个谓词公式中使用置换项替换变元。是形如${ t_1/x_1, \dots, t_n/x_n } $的有限集合，其中 \(t_i\) 是项，\(x_i\) 是互不相同的变元。要求 \(t_i\) 中不包含 \(x_i\)， \(x_i\) 也不在 \(t_j\) 中出现。
例如：\(P(x,y) \land Q(x) \{ a/x, b/y \} = P(a,b) \land Q(a)\)
置换的得到的新的公式可以被称作例示，是原公式的逻辑结论 -
置换的合成：假设我们有两个置换 (\sigma) 和 (\tau)，它们分别将某些变量映射到某些项。置换 (\sigma) 和 (\tau) 的合成记作 (\sigma \circ \tau)，表示先应用置换 (\tau)，然后再应用置换 (\sigma)。
如果 (\sigma = {x_1 \mapsto t_1, x_2 \mapsto t_2, \ldots, x_n \mapsto t_n}) 和 (\tau = {y_1 \mapsto s_1, y_2 \mapsto s_2, \ldots, y_m \mapsto s_m})，那么合成置换 (\sigma \circ \tau) 是一个新的置换，它将每个变量 (x) 映射到 (\sigma(\tau(x)))。
示例：
假设有两个置换：
- (\sigma = {x \mapsto a, z \mapsto b})
- (\tau = {y \mapsto x, z \mapsto f(x)})
将这两个置换合成得到 (\sigma \circ \tau)：
- 先应用 (\tau)：对于任意变量 (v)，将其替换为 (\tau(v))
- (y) 被替换为 (x)
- (z) 被替换为 (f(x))
- 再应用 (\sigma)：将 (\tau(v)) 中的变量继续替换为 (\sigma) 中对应的值
- (x) 被替换为 (a)
- (f(x)) 中的 (x) 被替换为 (a)，得到 (f(a))
因此，合成置换 (\sigma \circ \tau = {y \mapsto a, z \mapsto f(a)})。
-
合一： 是指两个项之间的一种特殊的置换，使得这两个项在这个置换下相等。合一是一种特殊的置换，它将两个项映射到相同的值。
例如，假设有两个项 (f(x, y)) 和 (f(a, b))。这两个项可以通过合一 ({x \mapsto a, y \mapsto b}) 相等。
示例：
假设有两个项 (f(x, y)) 和 (f(a, b))。这两个项可以通过合一 ({x \mapsto a, y \mapsto b}) 相等。
合一的另一个示例是 (f(x, g(y))) 和 (f(a, g(b)))。这两个项可以通过合一 ({x \mapsto a, y \mapsto b}) 相等。
自然演绎推理
从一组已知为真的事实出发，直接运用经典逻辑中的推理规 则推出结论的过程称为自然演绎推理
归结演绎推理
在人工智能中，几乎所有的问题都可以转化为一个定理证明问题。定理证明的实质，就是要对前提 P 和结论 Q，证明 P→Q 永真。
证明永真非常困难，因此我们通常采用反证法，即证明 \(P \land \lnot Q\)不可满足。这样，我们就可以通过归结演绎推理来证明 \(P \to Q\)。
子句和子句集
-
子句：是一个或多个文字的析取，其中每个文字都是一个谓词符号或其否定。
例如，\(P(x) \lor Q(y)\) 是一个子句，\(P(x) \lor Q(y) \lor R(z)\) 也是一个子句。
-
空子句：不包含任何文字的子句，通常用符号 \(\square\) 表示。
-
子句集：子句的集合
子句集的化简
对每一个子句，我们要将其化为所有全是全称量词的前束范式，随后消去全称量词。
如果有存在量词被全称量词约束，我们可以使用 Skolem 函数将其消去。
同时要消去全称量词，由于母式中的全部变元均受全称量词的约束，并且全称量词的次序已无关紧要，因此可以省掉全称量词。但剩下的母式，仍假设其变元是被全称量词量化的
随后将合取范式中的每一个子句拆分，得到一个子句集。
鲁滨逊归结原理
由于在消去存在量词时所用的 Skolem 函数可以不同，因此化简后的标准子句集是不唯一的
但当原谓词公式为永假（或不可满足）时，其标准子句集则一定是永假的，即 Skolem 化并不影响原谓词公式的永假性。
定理 3.1 设有谓词公式 F，其标准子句集为 S，则 F 为不可满足的充要条件是 S 为不可满足的
两个关键：
- 第一，子句集中的子句之间是合取关系。因此，子句集中只要有一个子句为不可满足，则整个子句集就是不可满足的；
- 第二，规定空子句是不可满足的。因此，一个子句集中如果包含有空子句，则此子句集就一定是不可满足的。
归结式：设 C1 和 C2 是子句集中的任意两个子句，如果 C1 中的文字 L1 与 C2 中的文字 L2 互补，那么可从 C1 和 C2 中分别消去 L1 和 L2，并将 C1 和 C2 中余下的部分按析取关系构成一个新的子句 C12
定理 3.2 归结式 C12 是其亲本子句 C1 和 C2 的逻辑结论， 即如果 C1， C2 关于解释 I 为真，则 C12 也为真
推论 1：设 C1 和 C2 是子句集 S 中的两个子句，C12 是 C1 和 C2 的归结式，若用 C12 代替 C1 和 C2 后得到新的子句集 S1，则由 S1 的不可满足性可以推出原子句集 S 的不可满足性。即：S1 的不可满足性 ⇒ S 的不可满足性
推论 2：设 C1 和 C2 是子句集 S 中的两个子句，C12 是 C1 和 C2 的归结式，若把 C12 加入 S 中得到新的子句集 S2，则 S 与 S2 的不可满足性是等价的。即：S2 的不可满足性 ⇔S 的不可满足性
定理 3.3 子句集 S 是不可满足的，当且仅当存在一个从 S 到空子句的归结过程
有了上述定理，我们可以将结论的否定加入子句集，然后通过归结过程来证明蕴含式的正确性。
在谓词逻辑中，由于子句集中的谓词一般都含有变元，因此不能象命题逻辑那样直接消去互补文字。而需要先用一个最一般合一对变元进行代换，然后才能进行归结。
人话：就是将全称量词置换到同一个符号，然后再进行归结。
检测题：
已知
• F: (∀x)((∃y)(A(x, y)∧B(y))→(∃y)(C(y)∧D(x, y)))
• G: ﹁(∃x)C(x)→(∀x)(∀y)(A(x, y)→﹁B(y))
求证 G 是 F 的逻辑结论。
解决复杂问题
某记者到一孤岛采访，遇到了一个难题，即岛上有许多人说假话，因而难以保证新闻报道的正确性，不过有一点他是清楚的，这个岛上的人有一特点：说假话的人从来不说真话，说真话的人也从来不说假话。一次记者遇到了孤岛上的三个人，为了弄清楚谁说真话，谁说假话，他向这三个人中的每一个都提了一个同样的问题，即 “谁是说谎者？”
结果 A 答“B 和 C 都是说谎者”，
B 答“A 和 C 都是说谎者”，
C 答“A 和 B 中至少有一个 是说谎者”
归结策略
归结策略是指在归结过程中，如何选择两个子句进行归结。归结策略的选择直接影响到归结的效率。
- 广度优先策略
(1)从 S0 出发，对 S0 中的全部子句作所有可能的归结，得到第一层归结式，把这些归结式的集合记为 S1;
(2) 用 S0 中的子句与 S1 中的子句进行所有可能的归结，得到第二层归结式，把这些归结式的集合记为 S2;
(3) 用 S0 和 S1 中的子句与 S2 中的子句进行所有可能的归
结，得到第三层归结式，把这些归结式的集合记为 S3;
如此继续，直到得出空子句或不能再继续归结为止
当问题有解时，能够保证找到最短的归结路径与解，但是会产生组合爆炸的问题。
- 支持集策略