Resolution algorithm

Inference procedures based on the resolution rule operate using the principle of proof by establishing a contradiction, which was described at the end of the section. Thus, to show that KB ≠ α, we show that the statement (KB ^ ¬α) is impossible. This can be done by proving that there is a contradiction.

Algorithm resolution is shown in the listing. First, the statement (KB ^ ¬α) is transformed into the form of CNF .

Then the resolution rule is applied to the resulting expressions. In each pair of expressions containing mutually opposite literals, these opposite literals are removed to obtain a new expression, which is added to the set of existing expressions, if this set does not yet have such an expression. The specified process continues until one of the following two events occurs:

• any new expressions that could be added to the existing ones cease to be developed, and in this case, the statement α does not follow from the KB;
• two opposite expressions are eliminated, resulting in a blank expression; in this case, the statement α follows from the KB knowledge base.

Simple resolution algorithm for propositional logic. The PL function - Resolve returns the set of all possible expressions obtained by removing the opposite literals from the two statements that arrive at its input.

function PL-Resolution (KB, ce) returns true or false

   inputs : KB, knowledge base - statement in propositional logic

a request is a statement in propositional logic

clauses <- set of expressions obtained after conversion

statements KB l —i (X in the form of CNF

new <- {}

loop do

for each d, cj in clauses do

resolvents <- PL-Resolve (Cl, Cj)

   if the resolvents set contains an empty expression

then return true

new <- new u resolvents

if new with clauses then return false

clauses <- clauses u new

An empty expression (disjunction without disjunct) is equivalent to saying False, since a disjunction is true only if at least one of its disjunct is true. Another way to make sure that an empty expression is evidence of a contradiction is that, returning to the logical inference process described above, you can see that an empty expression occurs only after eliminating two mutually opposite individual expressions, such as P and ¬Р .

This resolution procedure can be applied to form a very simple inference in the vampus world . When the agent is in the square [1,1], he does not feel the breeze, so there can be no holes in the adjacent squares. The relevant knowledge base is as follows:

KB = R ₂ ^ R ₄ = (B _1,1 <=> (P _1,2 v P _2,1 )) ^ ¬ B _1,1

and it is required to prove the statement α, which, say, has the form ¬P _1,2 . After transforming the statement (KB ^ ¬α) into the form of CNF, we obtain the expressions. The bottom row in this figure shows all the expressions obtained by removing opposing literals from all the pairs of expressions given in the top row. Then, after eliminating the literal P _1,2 , opposite to the literal ¬P _1,2 , a blank expression will be obtained, shown as a small square.

An analysis of the results reveals that many of the stages of the resolution were meaningless. For example, the expression B1,1 v ¬B1,1 v P1,2 is equivalent to the expression True v P _1,2 , which is equivalent to True. The logical conclusion that True is true is not very useful. Therefore, any expression in which there are two mutually additional literals can be dropped.