I’m not able to understand the following algorithm concerning propositional logic and entailment, taken from the book Artificial Intelligence A modern approach.
A truth-table enumeration algorithm for deciding propositional entailment. TT stands for truth table. PL-TRUE? returns true if a sentence holds within a model. The variable model represents a partial model- assignment to only some of the variables. The function call EXTEND(P, true, model) returns a new partial model in which P has the value 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)
2
Answers
Of course, the only thing
TT-ENTAILS
does is to callTT-CHECK-ALL
with the proper parameters, so there is not much to tell here. The interesting bits start in theelse
part ofTT-CHECK-ALL
which recursively constructs a huge conjunction for all the possible assignments for the symbols occurring in the knowledge base and the query (the ‘models’).For example,
TT-CHECK-ALL(KB, a, [P, Q], [])
will evaluate toThe first part of
TT-CHECK-ALL
, which is executed when all the symbols have been given a value in the model, checks whether the given model, e.g. [P=true, Q=false], is consistent with the knowledge base (PL-TRUE?(KB, model)
). These models correspond to the lines in the truth table, which have atrue
in the KB column. For those, the algorithm then checks whether the query evaluates to true (PL-TRUE?(query, model)
). All other models, that are inconsistent with the KB in the first place, are not considered, by returningtrue
, which is the neutral element of conjugation.In other words, this is the same as
PL-TRUE?(KB, model) -> PL-TRUE?(query, model)
.So in short, TT-CHECK-ALL checks that for each model (each possible assignment of ‘true’ or ‘false’ to the different symbols) that is consistent with the KB, the query evaluates to true:
foreach model: PL-TRUE?(KB, model) -> PL-TRUE?(query, model)
Which is logically equivalent to
not exist model: PL-TRUE?(KB, model) and not PL-TRUE?(query, model)
That is, there is no model, such that KB and the negation of the query can both be true, i.e. the KB and the negation of the query are logically inconsistent.
And this is exactly the definition of
KB entails query
.Edit:
About the
symbols
. Those are the atomic propositional symbols in the vocabulary. In the example in the book those would be the variousP_i,j
andB_i,j
, denoting whether room (i,j) has a pit and/or a breeze. Note thatR1
throughR5
are not part ofsymbols
, as those are just shorthands for convenience, representing more complex terms. Consequently, when passing theKB
into the algorithm we would not passR1 and R2 and ... R5
, but(not P_1,1) and (B_1,1 <=> (P_1,2 or P_2,1)) and ... and (B_2,1)
.TT-CHECK-ALL(KB,α,symbols,model )
On first iteration ,second part of TT-CHECK-ALL
i) TT-CHECK-ALL(KB,a,Q,Extend(P,true,[]))
at first
TT-CHECK-ALL(KB,a,Q,Extend(P,false,[]))
then happens what tobias said.
at last there’s a conjunction of all this TT-CHECK-ALL() is returned from TT-entails function .
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)
On i) the symbols wasn’t empty , there was q so it would go to the 2nd part of TT-CHECK-ALL , but on ii) as the symbols where empty it would go to the first part (KB,model) , if model isn’t true , it doesn’t check if alpha is true . The whole point is that if alpha the query is true in the every (true ) models of the knowledge base. if all the alpha are true in every true knowledge base(models). then the value of alpha is possible again if the alpha is not true in every true knowledge base(models). then we cannot be certain of that query .
exmp: In the wumpus-world example, the relevant proposition
symbols are B1,1, B1,2, P1,2, P2,1, P2,3, and P3,1. With seven symbols, there are
27 = 128 possible models; in three of these, KB (conjuction of different values of those symbols) is true . In those three models,
-p1,2 true, hence there is no pit in [1,2]. On the other hand, P2,1 true in two of the three
models and false in one, so we cannot yet tell whether there is a pit in [2,2].
Whole point of TT-entails algorithm to see , with the knowledge base i have , if the query would have answer or not . knowledge base (models )are true and query(one propositional sentence) is true in all of them then BINGO ! 🙂
i found tobias’s explanation extremely helpful. just thought about add some elimentry stuffs ,to make it better.