6

人工知能の最新のアプローチという本から引用した、命題論理と含意に関する次のアルゴリズムを理解できません。

命題含意を決定するための真理値表列挙アルゴリズム。TT は真理値表の略です。PL-TRUE? 文がモデル内に保持されている場合、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)) と一致するかどうかをチェックします。trueこれらのモデルは、KB 列にがある真理値表の行に対応しています。これらの場合、アルゴリズムはクエリが true ( PL-TRUE?(query, model)) と評価されるかどうかをチェックします。そもそも KB と矛盾する他のすべてのモデルは、true活用の中立要素である を返すことによって考慮されません。

つまり、これは と同じPL-TRUE?(KB, model) -> PL-TRUE?(query, model)です。

つまり、TT-CHECK-ALL は、KB と一致する各モデル (さまざまなシンボルへの「true」または「false」の割り当て) ごとに、クエリが true と評価されることを確認します。

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

これは論理的に同等です

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

つまり、KB とクエリの否定が両方とも true になるようなモデルはありません。つまり、KB とクエリの否定は論理的に矛盾しています。

そして、これはまさに の定義ですKB entails query。

編集： についてsymbols。これらは、語彙の原子命題記号です。本の例では、部屋 (i,j) に穴やそよ風があるかどうかを示すさまざまなP_i,jとがあります。throughは の一部ではないB_i,jことに注意してください。これらは、便宜上の略記であり、より複雑な用語を表しています。したがって、 をアルゴリズムに渡すときは、 ではなく を渡します。R1R5symbolsKBR1 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 に答える