Confusion in the logic of propositional logic

Question

I can not understand the following algorithm regarding the logic of propositions and drives, taken from the book "Artificial Intelligence" Modern approach.

The truth table enumeration algorithm for determining propositional attraction. TT stands for truth table. PL-TRUE? returns true if the sentence is contained within the model. A variable model represents a partial assignment of a model to only some of the variables. The call to EXTEND (P, true, model) returns a new partial model in which P is 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) 

Answer 1

Of course, the only thing TT-ENTAILS is to call TT-CHECK-ALL with the appropriate parameters, so there is not much to say. Interesting bits begin with the else part of TT-CHECK-ALL , which recursively builds a huge conjunction for all possible assignments for characters found in the knowledge base and query ("models").

For example, TT-CHECK-ALL(KB, a, [P, Q], []) will evaluate the value

 ( 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]) ) 

The first part of TT-CHECK-ALL , which is executed when all characters are assigned a value in the model, checks whether the given model, for example. [P = true, Q = false], consistent with the knowledge base ( PL-TRUE?(KB, model) ). These models correspond to rows in the truth table that have true in the KB column. For them, the algorithm then checks if the query matches the true ( PL-TRUE?(query, model) ). All other models that are incompatible with KB in the first place are not considered, returning true , which is a neutral interface element.

In other words, this is the same as PL-TRUE?(KB, model) -> PL-TRUE?(query, model) .

So, TT-CHECK-ALL checks that for each model (each possible assignment is "true" or "false" for different characters), compatible with KB, the request is evaluated as true:

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

Which is logically equivalent

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

That is, there is no model, so KB and the negation of the request can be true, i.e. KB and request denial are logically incompatible.

And this is just the definition of KB entails query .

Edit: About symbols . These are atomic propositional characters in a dictionary. In the example in the book, these will be different P_i,j and B_i,j , indicating whether (i, j) there is a pit and / or a breeze. Note that R1 through R5 are not part of symbols , as they are simply abbreviated for convenience, representing more complex terms. Therefore, when transferring KB to the algorithm, we would not have passed R1 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) .

Answer 2

TT-CHECK-ALL (KB, α, characters, model) At the first iteration, the 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 toby occurs.

finally, the connection from this TT-CHECK-ALL () is returned from the 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? (characters), then if PL-TRUE? (KB, model), then return PL-TRUE? (α, model)

In i) the characters were not empty, there was q, so he went to the second part of TT-CHECK-ALL, but to ii) as the characters where it is empty, he went to the first part (KB, model), if the model is incorrect, it doesn't check if alpha is true. The thing is that if the alpha query is true in every (true) knowledge base model. if all alpha are true in every true knowledge base (model). then the alpha value is possible again if alpha does not correspond to the truth in each real knowledge base (model). then we cannot be sure of this request.

exmp: In the example with wumpus-world, the corresponding sentence is the characters B1,1, B1,2, P1,2, P2,1, P2,3 and P3,1. With seven characters, there are 27 = 128 possible patterns; in three of them, KB (combining different meanings of these characters) is true. In these three models, -p1,2 is true, so there is no pit in [1,2]. On the other hand, P2,1 is true in two of the three models and false in one, so we can’t say yet if there is a hole in [2,2].

The whole TT-point entails an algorithm that sees with the knowledge base that I have if the request will respond or not. the knowledge base (models) is true, and the query (one sentence) is true in all of them, and then BINGO! :)

I found that the tobias explanation is extremely useful. just thought about adding some materials to the elite to make them better.