Logic for Computer Scientists/Predicate Logic/Resolution

< Logic for Computer Scientists‎ | Predicate Logic

Contents

ResolutionEdit

In the propositional case we defined the resolution inference rule by "cutting away" a pair of complementary literals in two clauses which are resolved upon. In the first order case however this is not always sufficient:

In these two clauses there are no complementary literals, however, after substituting the term for the variable in and for in we arrive at:

Now we can apply the inference rule from propositional logic and arrive at the resolvent .

Another possibility is to substitute for in to get

and then we can have the resolvent from and , which is in a certain sense more general then the resolvent derived previously.

Definition 18Edit

A substitution is a function, which maps variables to terms and which is the identical mapping almost everywhere. Hence it can be represented as

If are groundterms, we call a ground substitution. The empty substitution is notated by .

Definition 19Edit

Let be a substitution and an expression (i.e. a literal or a term), then is the expression, obtained from by replacing simultaneously each occurrence of in by the term .

Example:
With and , we get

Definition 20Edit

Let and be substitutions. Then the composition of substitutions, denoted by , is the substitution, which is obtained from by deleting any element for which and any element such that .
Example:

Definition 21Edit

Let be a set of expressions and a substitution, is unifier for iff

.

A unifier is called most general unifier iff for every unifier there is a substitution such that .

In the following we discuss an algorithm for computing most general unifiers. For this we assume a set of terms to be unified. First we transform this into a set of equations by introducing a new variable not yet occurring in this set, say and by defining the set of equations

We will now transform this set such that its unifiers stay invariant, where a is a unifier of a set of if holds.


Unification


Given a set of expression. Transform it into a set of equations as defined above. Apply the following transformation rules as long as possible:

  1. Orient

    where is a variable and a non-variable term

  2. Delete

  3. Decompose (Termreduction)

  4. Eliminate (Elimination of variable I)

    if not in , but in

  5. Coalesce (Elimination of variable II)

    if in

  6. Conflict

    if or

  7. Occur Check

    if in

Theorem 7Edit

Let be a set of expressions. The above unification algorithm terminates. If it returns , there is no unifier for , otherwise is transformed into a set of equation , which represents the most general unifier for .

Definition 22Edit

Let two or more literals of a clause have a unifier , then is called a factor of .

Example:
With and we get the factor

Definition 23Edit

Let and be two clauses with no variables in common, such that and and and have a most general unifier . A binary resolvent of and is


Example: Given and . After renaming into we get the resolvent by using the most general unifier .


We often depict resolvent graphically, e.g.

Definition 24Edit

A resolvent of two clauses and is one of the following binary resolvents:

  • a binary resolvent of and
  • a binary resolvent of and a factor of
  • a binary resolvent of a factor of and
  • a binary resolvent of a factor of and a factor of


Example:

Given and .

A factor of is . A binary resolvent of and and hence also of and is .

The following lemma is used in the completeness proof of resolution.

Lemma 5 (Lifting lemma)Edit

If and are instances of and , respectively, and is a resolvent of and , then there is a resolvent of and such that is an instance of .


Figure 1

Theorem 8Edit

A set of clauses is unsatisfiable iff the empty clause can be derived from by resolution.
Proof:
Assume that is unsatisfiable. Let be the ground atom set of , hence the Herbrand basis. Let be a complete binary tree, as given in Figure 2. According to Herbrand's theorem (version1) there exists a closed finite semantic tree . There are two cases:

  • If consists only of one node (hence the root), The interpretation to be collected from the empty branch in this tree falsifies only the empty clause. Hence the empty clause must be in .
  • Assume consists of more than one node. Then there must be an inference node in , hence both its descendants and are failure nodes. If such a node would not exist, every node would have at least one non-failure node, which would mean that there is at least an infinite path in , which would violate, that fact that it is a finite closed semantic tree. Let given as described above; and let

Now, let and be ground instances of clauses and , such that is falsified by and by , such that both are not falsified by .

Hence we have and and we can construct the resolvent

must be false in , because both and are false in . According to the Lifting Lemma 5 there exists a resolvent of and , such that is a ground instance of . Let be the closed semantic tree for , obtained from by deleting all nodes below the first node which falsifies . Note, that is unsatisfiable if and only if is unsatisfiable. Clearly, has less nodes than and we now can iterate this process until only the root of the semantic tree is remaining. This, however is only possible if the empty clause is derivable. For the opposite direction, assume that is derivable by resolution from and let the resolvents constructed during this process. Assume is satisfiable and to be a model for . From the correctness lemma according to the propositional case we known, that if a model satisfies two clauses it also satisfies its resolvent. Therefore has to satisfy ; this, however, is impossible, because one of this resolvents is .



Figure 2

ProblemsEdit

Problem 14 (Predicate)Edit

Indicate in each case a derivation of the empty clause with predicate-logical resolution!

  1. ()


Problem 15 (Predicate)Edit

Show the following Lifting lemma by means of induction over the term- and formula construction: Is a predicate-logical formula, and a fitting interpretation for

and . Then


is valid, if does not contain any variable that is laced

by the substitution in .

Problem 16 (Predicate)Edit

Compute - if possible - the most general unifier of following sets of clauses:


Problem 17 (Predicate)Edit

Determine all direct resolvents of the following pairs of clauses:

  1. and
  2. and
  3. and
  4. and


Problem 18 (Predicate)Edit

Compute - if possible - the most general unifier of following sets of clauses:


Problem 19 (Predicate)Edit

Determine all direct resolvents of the following pairs of clauses:

  1. and
  2. and
  3. and


Problem 20 (Predicate)Edit

Give for the following set of clauses (a) a linear derivation, (b) a derivation with unit resolution, (c) a further (maximally short) derivation of the empty clause by means of predicate-logical resolution!


Problem 21 (Predicate)Edit

Indicate in each case a derivation of the empty clause with predicate-logical resolution!

  1. ()