逻辑程序更新与动态逻辑编程深入解析

### 逻辑程序更新与动态逻辑编程深入解析 #### 1. 逻辑程序更新基础 逻辑程序更新是一个重要的概念，它涉及到对已有程序进行修改和扩展。在逻辑程序更新中，我们需要考虑多个方面，包括剩余规则、默认规则等。 假设有两个程序 \(P\) 和 \(U\)，剩余规则 \(Residue (M) = P \cup U - Rejected (M)\)，其中 \(Rejected (M)\) 是被拒绝的规则集合。同时，默认规则 \(Defaults (M)\) 包含了所有不被支持的原子的默认否定。 例如，对于程序 \(P\) 和 \(U\)： ```plaintext P : sleep <- not tv-on tv-on <- watch-tv <- tv-on U : not tv-on <- power-failure power-failure <- ``` 根据定义，\(P \oplus U\) 可以表示为： ```plaintext P|+|U = (RP) u (RU) U (UR) U (IR) U (DR) ``` 其中： ```plaintext RP : sleepp <- tv-on~ tv-onp <- watch-tvp <- tv-on RU : tv-on~ <- power-failure power-failure~ <- ``` 可以验证 \(M = \{power - failure, sleep\}\) 是 \(P \oplus U\) 的唯一稳定模型（限制在相关原子上）。其推理过程如下： 1. 从 \((RU)\) 的第二个子句和更新规则可以推出 \(power - failure\)。 2. 由 \(power - failure\)，根据 \((RU)\) 的第一个规则和更新规则可以推出 \(tv - on~\)，进而推出 \(not tv - on\)。 3. 从 \((RP)\) 的第一个规则可以推出 \(sleepp\)，再根据继承规则推出 \(sleep\)。 4. 最后，根据默认规则推出 \(watch - tv~\) 和 \(not watch - tv\)。 #### 2. 逻辑程序更新的性质 逻辑程序更新具有一些重要的性质，这些性质有助于我们更好地理解和应用逻辑程序更新。 ##### 2.1 稳定模型与剩余规则 如果 \(M\) 是 \(P \oplus U\) 的稳定模型，那么 \(M\) 也是 \(Residue (M) = P \cup U - Rejected (M)\) 的稳定模型。但反之不一定成立，因为 \(M\) 是由 \(Defaults (M)\) 而不是 \(M^-\) 决定的。 例如，设 \(P\) 仅包含事实 \(A <-\)，\(U\) 仅包含子句 \(not A <- not A\)，\(M = \{not A\}\)。此时 \(Residue (M) = U\)，\(M\) 是 \(Residue (M)\) 的稳定模型，但由于 \(Defaults (M) = 0\)，\(M\) 不是 \(P \oplus U\) 的稳定模型，实际上 \(M = \{A\}\) 是 \(P \oplus U\) 的唯一稳定模型。 ##### 2.2 语义比较 \(P \oplus U\) 的语义总是弱于或等于 \(P \cup U\) 的语义。如果 \(M\) 是 \(P \cup U\) 的稳定模型，那么 \(M\) 是 \(P \oplus U\) 的稳定模型，但反之不成立。 例如，对于前面的程序 \(P\) 和 \(U\)，\(P \cup U\) 是矛盾的，没有稳定模型。 ##### 2.3 特殊情况 - 当 \(U\) 为空程序时，\(M\) 是 \(P \oplus 0\) 的稳定模型当且仅当 \(M\) 是 \(P\) 的稳定模型。 - 当 \(P = U\) 时，\(M\) 是 \(P \oplus P\) 的稳定模型当且仅当 \(M\) 是 \(P\) 的稳定模型。 - 如果 \(P\) 和 \(U\) 不包含冲突规则，那么 \(M\) 是 \(P \cup U\) 的稳定模型当且仅当 \(M\) 是 \(P \oplus U\) 的稳定模型。 ##### 2.4 稳定模型的简化表征 稳定模型 \(M\) 满足条件： ```plaintext M = least(Residue (M) U Defaults (M)) ``` 其中： ```plaintext Rejected(M) = {r | r ∈ P, ∃r' ∈ U, r ≺ r', M |= B(r')} Defaults (M) = {notA|∄r∈P U U: H(r) = A ∧ M |= B(r)} Residue (M) = P U U - Rejected (M) ``` #### 3. 程序更新与解释更新 解释更新最初被称为“修订程序”，它是程序更新的一个特殊情况。 ##### 3.1 修订程序的定义 修订程序由 \(in - rule\) 和 \(out - rule\) 组成，例如： ```plaintext in(A0) <- in(A1), ..., in(Am), out(Am + 1), ..., out(An) out(A0) <- in(A1), ..., in(Am), out(Am + 1), ..., out(An) ``` 其中 \(A_i\) 是命题。 ##### 3.2 必要变化 设 \(U\) 是修订程序，其最小模型为 \(M\)，必要变化为 \((I_U, O_U)\)，其中： ```plaintext I_U = {a : in(a) ∈ M} O_U = {a : out(a) ∈ M} ``` 如果 \(I_U \cap O_U = \{\}\)，则 \(U\) 是连贯的。 ##### 3.3 U - 正当修订 对于修订程序 \(U\) 和两个解释 \(I_i\) 和 \(I_u\)，可以通过以下操作得到 \(U_{I_u|I_i}\)： 1. 从 \(U\) 中移除所有体中包含 \(in(a)\) 且 \(a \notin I_u\) 的规则。 2. 从 \(U\) 中移除所有体中包含 \(out(a)