6

我无法理解以下有关命题逻辑和蕴涵的算法，取自《人工智能现代方法》一书。

一种用于确定命题蕴涵的真值表枚举算法。TT 代表真值表。PL-真？如果句子在模型中成立，则返回 true。变量模型表示仅对某些变量的部分模型分配。函数调用 EXTEND(P, true, model) 返回一个新的部分模型，其中 P 的值为 true。

function  TT-ENTAILS? (KB,α) returns  true  or  false
  inputs: KB, the knowledge base, a sentence in propositional logic
           α, the query, a sentence in propositional logic

symbols <--- a list of the propositional symbols in KB and α
return TT-CHECK-ALL(KB,α,symbols,[])

function TT-CHECK-ALL(KB,α,symbols,model ) returns true or false
   if EMPTY?(symbols) then
       if PL-TRUE?(KB, model) then return PL-TRUE?(α,model)
       else return true

   else do
       P <---FIRST(symbols); rest <--- REST(symbols)
       return TT-CHECK-ALL(KB,α,rest,EXTEND(P,true,model) and
              TT-CHECK-ALL(KB, α, rest, EXTEND(P,false,model)
4

2 回答 2

9

当然，唯一要做的TT-ENTAILS就是TT-CHECK-ALL用适当的参数调用，所以这里没有太多要说的。有趣的else部分开始于TT-CHECK-ALL递归地为知识库和查询（“模型”）中出现的符号的所有可能分配构造一个巨大的连接。

例如，TT-CHECK-ALL(KB, a, [P, Q], [])将评估为

(
   TT-CHECK-ALL(KB, a, [], [P=true, Q=true]) 
   and 
   TT-CHECK-ALL(KB, a, [], [P=true, Q=false])
) 
and 
(
    TT-CHECK-ALL(KB, a, [], [P=false, Q=true]) 
    and 
    TT-CHECK-ALL(KB, a, [], [P=false, Q=false])
)

的第一部分TT-CHECK-ALL，当模型中的所有符号都被赋值时执行，检查给定的模型，例如[P=true，Q=false]，是否与知识库（PL-TRUE?(KB, model)）一致。这些模型对应于真值表中的行，这些行在trueKB 列中有一个。对于那些，算法然后检查查询的计算结果是否为真（PL-TRUE?(query, model)）。所有其他模型，首先与 KB 不一致，通过返回 不考虑，true这是共轭的中性元素。

换句话说，这与 相同PL-TRUE?(KB, model) -> PL-TRUE?(query, model)。

所以简而言之，TT-CHECK-ALL 检查与 KB 一致的每个模型（每个可能的“真”或“假”分配给不同的符号），查询评估为真：

foreach model: PL-TRUE?(KB, model) -> PL-TRUE?(query, model)

这在逻辑上等同于

not exist model: PL-TRUE?(KB, model) and not PL-TRUE?(query, model)

即不存在模型，使得KB和查询的否定都可以为真，即KB和查询的否定在逻辑上不一致。

而这正是 的定义KB entails query。

编辑： 关于symbols. 这些是词汇表中的原子命题符号。在书中的示例中，这些将是各种P_i,jand B_i,j，表示房间 (i,j) 是否有坑和/或微风。请注意，R1throughR5不是 的一部分symbols，因为它们只是为了方便起见的简写，代表更复杂的术语。因此，当将 传递给KB算法时，我们不会传递R1 and R2 and ... R5，而是传递(not P_1,1) and (B_1,1 <=> (P_1,2 or P_2,1)) and ... and (B_2,1)。

于 2012-09-17T19:01:32.203 回答
-1

TT-CHECK-ALL(KB,α,symbols,model ) 在第一次迭代中，TT-CHECK-ALL 的第二部分 i) TT-CHECK-ALL(KB,a,Q,Extend(P,true,[])) at first TT-CHECK-ALL(KB,a,Q,Extend(P,false,[])) 发生了 tobias 所说的情况。

最后，所有这些 TT-CHECK-ALL() 都从 TT-entails 函数返回。

ii) (TT-CHECK-ALL(KB, a, [], [P=true, Q=true]) and TT-CHECK-ALL(KB, a, [], [P=true, Q=false])) and (TT-CHECK-ALL(KB, a, [], [P=false, Q=true]) and TT-CHECK-ALL(KB, a, [], [P=false, Q=false]))

PS。if EMPTY?(symbols) then if PL-TRUE?(KB, model) then return PL-TRUE?(α,model)

在 i) 符号不是空的，有 q 所以它会进入 TT-CHECK-ALL 的第二部分，但在 ii) 作为空的符号它会进入第一部分 (KB,model) ，如果 model 不是 true ，它不会检查 alpha 是否为 true 。关键是，如果 alpha 查询在知识库的每个 (true) 模型中为真。如果所有 alpha 在每个真实的知识库（模型）中都是真实的。如果每个真正的知识库（模型）中的 alpha 都不为真，那么 alpha 的值又是可能的。那么我们不能确定那个查询。

exmp：在 wumpus-world 示例中，相关命题符号为 B1,1、B1,2、P1,2、P2,1、P2,3 和 P3,1。有七个符号，有 27 = 128 种可能的模型；在其中三个中，KB（这些符号的不同值的结合）为真。在这三个模型中，-p1,2 为真，因此 [1,2] 中没有坑。另一方面，P2,1 三个模型中有两个为真，一个为假，所以我们还不能判断 [2,2] 中是否有坑。

TT-entails 算法的全部要点，根据我拥有的知识库，查询是否有答案。知识库（模型）是真实的，查询（一个命题句）在所有这些中都是真实的，然后 BINGO ！:)

我发现托比亚斯的解释非常有帮助。只是想添加一些基本的东西，以使其更好。

于 2014-03-28T19:34:07.380 回答