Artificial Intelligence Question posted in
ChatGBT is becoming a world-wide phenomena, try it out here.

Confusion in propositional logic algorithm – Artificial Intelligence

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)
Tags:

2

Answers


  1. 0

    Of course, the only thing TT-ENTAILS does is to call TT-CHECK-ALL with the proper parameters, so there is not much to tell here. The interesting bits start in the else 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 to 

    (
   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 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 a true 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 returning true, 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 various P_i,j and B_i,j, denoting whether room (i,j) has a pit and/or a breeze. Note that R1 through R5 are not part of symbols, as those are just shorthands for convenience, representing more complex terms. Consequently, when passing the KB into the algorithm we would not pass 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).

    Login or Signup to reply.
  2. 0

    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.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search