Logic for Computer Scientists/Predicate Logic/Resolution

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:

\begin{matrix}
C_1: & p(x) \lor q(x) \\

C_2: & \lnot p(f(x))
\end{matrix}

In these two clauses there are no complementary literals, however, after substituting the term f(a) for the variable x in C_1 and a for x in C_2 we arrive at:

\begin{matrix}
C_1': & p(f(a)) \lor q(f(a)) \\ 

C_2': & \lnot p(f(a))
\end{matrix}

Now we can apply the inference rule from propositional logic and arrive at the resolvent q(f(a)).

Another possibility is to substitute f(x') for x in C_1 to get


C_1'':  p(f(x')) \lor q(f(x'))

and then we can have the resolvent q(f(x')) from C_1'' and C_2, which is in a certain sense more general then the resolvent derived previously.

Definition 18Edit

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

\sigma =\{x_1 / t_1, \cdots , x_n / t_n\}

If t_1, \cdots , t_n are groundterms, we call \sigma a ground substitution. The empty substitution is notated by \epsilon .

Definition 19Edit

Let \theta = \{ x_1 / t_1, \cdots , x_n / t_n\} be a substitution and E an expression (i.e. a literal or a term), then E\theta is the expression, obtained from E by replacing simultaneously each occurrence of X_i, 1 \leq i \leq n in E by the term t_i.

Example:
With \theta = \{ x/a, y/f(b), z/e\} and E = p(x, y, z), we get E\theta = p(a,f(b),c)

Definition 20Edit

Let \sigma = \{ x_1 / t_1, \cdots , x_n / t_n\} and  \lambda = \{ y_1/s_1,\cdots , y_m/s_m\} be substitutions. Then the composition of substitutions, denoted by  \sigma \circ \lambda , is the substitution, which is obtained from  \{ x_1 / t_1 \lambda,
\cdots,x_n / t_n \lambda, y_1/s_1,\cdots , y_m/s_m \} by deleting any element x_j/t_j \lambda for which  t_j \lambda = x_j and any element y_i/s_i such that y_i \in\{ x_1, \cdots, x_n\} .
Example:

Definition 21Edit

Let  \{E_1, \cdots, E_n\} be a set of expressions and \theta a substitution, \theta is unifier for  \{E_1, \cdots, E_n\} iff

E_1\theta = E_2\theta = \cdots E_n\theta

.

A unifier \theta is called most general unifier iff for every unifier \sigma there is a substitution \lambda such that  \sigma =  \theta \circ \lambda.

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

N = \{ y = t_1, \cdots , y = t_n\}

We will now transform this set such that its unifiers stay invariant, where a \sigma is a unifier of a set of  \{s_1 = t_1, \cdots , s_n =
t_n\} if  \{s_1 \sigma = t_1 \sigma , \cdots , s_n\sigma  =
t_n\sigma \} holds.


Unification


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

  1. \frac {R \uplus \{t=x\}}{R \uplus \{x=t\}} Orient

    where x is a variable and t a non-variable term

  2. \frac{R \uplus \{s=s\}}{R} Delete

  3. \frac{R \uplus \{f(s_1,\dots, s_n) = f(t_1, \dots, t_n)\}}{R \uplus \{s_1=t_1, \dots, s_n=t_n\}} Decompose (Termreduction)

  4. \frac{R \uplus \{x=t\}}{R[x/t] \uplus \{x=t\}} Eliminate (Elimination of variable I)

    if x not in t, but in R

  5.  \frac{R \uplus \{x=y\}}{R[x/y] \uplus \{x=y\}}Coalesce (Elimination of variable II)

    if x \neq y in R

  6.  \frac{R \uplus \{f(s_1, \dots, s_m) = g(t_1,\dots, t_n)\}}{\mbox{FAIL}} Conflict

    if f \neq g or m \neq n

  7. \frac{R \uplus \{x=t\}}{\mbox{FAIL}} Occur Check

    if x in t

Theorem 7Edit

Let N be a set of expressions. The above unification algorithm terminates. If it returns FAIL, there is no unifier for N, otherwise N is transformed into a set of equation \{y_1 = u_1, \cdots , y_m 
= u_m\}, which represents the most general unifier for N.

Definition 22Edit

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

Example:
With  C= \{p(x), p(f(y)), \lnot q(x)\} and \sigma = \{ x/f(y)\} we get the factor C\sigma = \{p(f(y)), \lnot q(f(y))\}

Definition 23Edit

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

 (C_1\sigma - L_1\sigma) \cup (C_2 \sigma - L_2\sigma)


Example: Given C_1 = \{ p(x), q(x)\} and C_2 = \{\lnot p(a),r(x)\}. After renaming C_2 into C_2 = \{\lnot p(a), r(y)\} we get the resolvent \{q(a), r(y)\} by using the most general unifier \{x/a\} .


We often depict resolvent graphically, e.g.

Resolvent.png

Definition 24Edit

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

  • a binary resolvent of C_1 and C_2
  • a binary resolvent of C_1 and a factor of C_2
  • a binary resolvent of a factor of C_1 and C_2
  • a binary resolvent of a factor of C_1 and a factor of C_2


Example:

Given C_1 = \{ p(x), p(f(y)), r(g(y))\} and C_2 = \{\lnot
p(f(g(a))),q(b)\}.

A factor of C_1 is C_1\prime = \{p(f(y)), r(g(y))\}. A binary resolvent of C_1\prime and C_2 and hence also of C_1 and C_2 is C_3 = \{ r(g(g(a))), q(b)\} .

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

Lemma 5 (Lifting lemma)Edit

If C_1\prime and C_2\prime are instances of C_1 and C_2, respectively, and C\prime is a resolvent of C_1\prime and C_2\prime, then there is a resolvent C of C_1 and C_2 such that C\prime is an instance of C.

Liftinglemma.png


Figure 1

Theorem 8Edit

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

  • If T' 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 S.
  • Assume T' consists of more than one node. Then there must be an inference node N in T', hence both its descendants N_1 and N_2 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 T', which would violate, that fact that it is a finite closed semantic tree. Let N, N_1, N_2 given as described above; and let
    \begin{matrix}
  I(N) & =& \{m_1, m_2, \ldots, m_n\} 
   I(N_1) & =& \{m_1, m_2, \ldots, m_n, m_n, m_{n+1}\} 
  I(N_2) &  =&  \{m_1, m_2, \ldots, m_n, m_n, \lnot m_{n+1}\} \end{matrix}

Now, let C_1' and C_2' be ground instances of clauses C_1 and C_2, such that C_1' is falsified by I(N_1) and C_2' by I(N_2), such that both are not falsified by I(N).

Hence we have \lnot m_{n+1} \in C_1' and  m_{n+1} \in C_2' and we can construct the resolvent


C' = (C_1' - \{ \lnot m_{n+1}\} ) \cup (C_2' - \{  m_{n+1}\} )

C' must be false in I(N), because both (C_1' - \lnot m_{n+1}) and (C_2' -  m_{n+1}) are false in I(N). According to the Lifting Lemma 5 there exists a resolvent C of C_1 and C_2, such that C' is a ground instance of C. Let T \; '' be the closed semantic tree for  S \cup \{ C\} , obtained from T' by deleting all nodes below the first node which falsifies C'. Note, that S is unsatisfiable if and only if S \cup \{ C\} is unsatisfiable. Clearly, T \; '' has less nodes than T' 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 \square is derivable. For the opposite direction, assume that \square is derivable by resolution from S and let R_1, \ldots, R_k the resolvents constructed during this process. Assume S is satisfiable and M to be a model for S. From the correctness lemma according to the propositional case we known, that if a model satisfies two clauses it also satisfies its resolvent. Therefore M has to satisfy R1, \ldots, R_k; this, however, is impossible, because one of this resolvents is \square.


Resolutiontree1.png


Figure 2

ProblemsEdit

Problem 14 (Predicate)Edit

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

  1. \{ \{p(x,0,x)\}, \{p(x,s(y),s(z)),\lnot p(x,y,z)\}, \{\lnot p(s(s(s(0))),s(s(0)),u)\}\}
  2. \{\{q(x),q(s(x))\},\{\lnot q(x),\lnot q(s(s(x)))\}\}
    (\star)
  3. \{ \{\lnot r(x,f(x),y),\lnot r(x,g(y),z)\},\{r(c,u,i(v)),r(h(u),v,j(v))\} \}


\Box

Problem 15 (Predicate)Edit

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

F and F[x/t]. Then

 \mathcal{I}(F[x/t]) = \mathcal{I}_{[x/\mathcal{I}(t)]}(F),


is valid, if t does not contain any variable that [x/t] is laced

by the substitution in F.
\Box

Problem 16 (Predicate)Edit

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

  1. \{p(x,a),p(f(c),y)\}
  2. \{p(f(x),a,x),p(y,z,z)\}
  3. \{q(x,x),q(g(y),y)\}
  4. \{r(x,x),r(a,h(y))\}


\Box

Problem 17 (Predicate)Edit

Determine all direct resolvents of the following pairs of clauses:

  1. \{\lnot p(x), q(x,b)\} and \{p(a), q(a,b)\}
  2. \{p(x), p(f(x))\} and \{\lnot p(x), \lnot p(f(f(x)))\}
  3. \{\lnot q(c,g(c))\} and \{\lnot p(x), q(x,x)\}
  4. \{\lnot p(x,y,z), \lnot p(y,u,v), \lnot p(x,v,w), p(z,u,w)\} and \{p(g(x,y),x,y)\}


\Box

Problem 18 (Predicate)Edit

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

  1. \{o(x,x),o(a,f(y))\}
  2. \{p(x,a),p(f(c),y)\}
  3. \{q(g(x),a,x),q(y,z,z)\}
  4. \{r(x,x),r(h(y),y)\}


\Box

Problem 19 (Predicate)Edit

Determine all direct resolvents of the following pairs of clauses:

  1. \{\lnot p(x),\lnot p(b), q(x,b)\} and \{p(a), q(a,b)\}
  2. \{r(x), r(f(x))\} and \{\lnot r(x),\lnot r(f(f(x)))\}
  3. \{\lnot s(c,g(c))\} and \{s(x,x), \lnot t(x)\}


\Box

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!

 \{ \{\lnot e(x),o(s(x))\},\{\lnot e(x),\lnot o(s(x)),e(s(s(x)))\},\{e(a)\},\{\lnot o(s(s(s(s(s(a))))))\}\}


\Box

Problem 21 (Predicate)Edit

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

  1. \{ \{p(x,0,x)\}, \{p(x,s(y),s(z)),\lnot p(x,y,z)\},\{\lnot p(s(s(s(0))),s(s(0)),u)\}\}
  2. \{\{q(x),q(s(x))\},\{\lnot q(x),\lnot q(s(s(x)))\}\}
    (\star)
  3. \{ \{\lnot r(x,f(x),y),\lnot r(x,g(y),z)\},\{r(c,u,i(v)),r(h(u),v,j(v))\} \}


\Box

Last modified on 12 October 2010, at 20:33