Logical conclusion

Recall that the purpose of the inference is to determine whether the expression KB \ = a is true for some statement a. For example, does the P _2.2 statement follow from the knowledge base? The first inference algorithm, considered in this section, is a direct practical implementation of the logical consequence definition: go through (list) all the models and check whether the statement a is true in each model in which the KB knowledge base is true. For propositional logic, the models are options for assigning true or false values ​​to each propositional symbol. Returning to the example of the world of vampus, we determine that the corresponding propositional symbols are B _1,1 , B _2,1 , P _1,1 , P _1,2 , P _2,1 , P _2,2 and P _3,1 .

With seven symbols, there may be 2 ⁷ = 128 possible models; in three of them, the KB knowledge base is true. In these three models, the statement ¬P _1,2 is also true, therefore there is no well in the square [1,2]. On the other hand, the statement P _{2,2 is} true in two of the three models and false in one of them, therefore we cannot yet determine whether there is a well in the square [2,2].

The truth table that is generated for the knowledge base defined in the chapter text. The KB knowledge base is true if the statements R ₁ -R ₅ are true, and this happens only in 3 of 128 lines. In all 3 lines, the statement P _{1,2 is} false, so there is no hole in the square [1,2]. On the other hand, a pit in the square [2.2] may be (or not)

The table reproduces in a more accurate form the process of forming the reasoning, which is illustrated in the figure. The general algorithm for determining the logical consequence of propositional logic is given in the listing. As in the Backtracking-Search algorithm given on p. 131, TT-Entails feature? performs a recursive enumeration of the final space of options for assigning values ​​to variables. This algorithm is consistent because it directly implements the definition of a logical consequence, and is complete because it can be applied to any KB knowledge base and any statement a and always finishes its work, provided that the number of models to be tested is finite.

The algorithm for iterating the truth table to obtain propositional logical consequences, TT denotes the truth table, the function PL-True? returns true value if some statement is true within a certain model. The model variable represents a partially specified model — assigning only some variables. A call to the Extend function (P, true, model) returns a new partially defined model, in which the P statement has the value true

function TT-Entails? (KB, a) returns true or false

   inputs : KB, knowledge base - statement in propositional logic

a request is a statement in propositional logic

symbols <- list of propositional symbols in KB and a

return TT-Check-All (KB, a, symbols, [])

function TT-Check-All (KB, a, symbols, model) returns value

true or false

if Empty? (symbols) then

if PL-True? (KB, model) then return PL-True? (a, model)

else return true

else do

P <- First (symbols); rest <- Rest (symbols)

return TT-Check-All (KB, a, rest, Extend (P, true, model) and

TT-Check-All (KB, a, rest, Extend (P, false, model)

Of course, the expression "is finite" does not always mean the same as the expression "is small." If KB and a contain a total of n characters, then the number of models is 2 ⁿ . Thus, the time complexity of this algorithm is O (2 ⁿ ). (The spatial complexity is only O (n), since the enumeration of assignment options is based on the depth search principle.) Algorithms that are much more efficient in practice will be shown below. Unfortunately, each known logic inference algorithm for propositional logic has, in the worst case, a complexity that depends exponentially on the size of the input. We cannot rely on the fact that our algorithms will function better, since the task of obtaining a propositional logical consequence is co-NP-complete.