Logic for Computer Scientists/Predicate Logic/Resolution

Resolution

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{array}{cc}{C}_1:& p(x)\vee q(x)\\ C_2:& \mathrm{\neg }p(f(x))\end{array}$

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{array}{cc}{C_1}^{\prime }:& p(f(a))\vee q(f(a))\\ {C_2}^{\prime }:& \mathrm{\neg }p(f(a))\end{array}$

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^{\prime })$ for $x$ in $C_1$ to get

${C_1}^{″}:p(f(x^{\prime }))\vee q(f(x^{\prime }))$

and then we can have the resolvent $q(f(x^{\prime }))$ from ${C_1}^{″}$ and $C_2$, which is in a certain sense more general then the resolvent derived previously.

Definition 18

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 $ϵ$ .

Definition 19

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\le i\le 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 20

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 21

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.

Theorem 7

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 22

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)),\mathrm{\neg }q(x)\}$ and $\sigma =\{x/f(y)\}$ we get the factor $C\sigma =\{p(f(y)),\mathrm{\neg }q(f(y))\}$

Definition 23

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=\{\mathrm{\neg }p(a),r(x)\}$. After renaming $C_2$ into $C_2=\{\mathrm{\neg }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.

Definition 24

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=\{\mathrm{\neg }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)

If $C{\text{'}}_1$ and $C{\text{'}}_2$ are instances of $C_1$ and $C_2$, respectively, and $C^{\prime }$ is a resolvent of $C{\text{'}}_1$ and $C{\text{'}}_2$, then there is a resolvent $C$ of $C_1$ and $C_2$ such that $C^{\prime }$ is an instance of $C$.

Figure 1

Theorem 8

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,\dots \}$ 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^{\prime }$. There are two cases:

• If $T^{\prime }$ 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^{\prime }$ consists of more than one node. Then there must be an inference node $N$ in $T^{\prime }$, 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^{\prime }$, 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{array}{ccccccc}I(N)& =& \{m_1,m_2,\dots ,m_n\}I(N_1)& =& \{m_1,m_2,\dots ,m_n,m_n,m_{n+1}\}I(N_2)& =& \{m_1,m_2,\dots ,m_n,m_n,\mathrm{\neg }{m}_{n+1}\}\end{array}$

Now, let ${C_1}^{\prime }$ and ${C_2}^{\prime }$ be ground instances of clauses $C_1$ and $C_2$, such that ${C_1}^{\prime }$ is falsified by $I(N_1)$ and ${C_2}^{\prime }$ by $I(N_2)$, such that both are not falsified by $I(N)$.

Hence we have

$\mathrm{\neg }{m}_{n+1}\in {C_1}^{\prime }$

and

$m_{n+1}\in {C_2}^{\prime }$

and we can construct the resolvent

$C^{\prime }=({C_1}^{\prime }-\{\mathrm{\neg }{m}_{n+1}\})\cup ({C_2}^{\prime }-\{m_{n+1}\})$

$C^{\prime }$ must be false in $I(N)$, because both $({C_1}^{\prime }-\mathrm{\neg }{m}_{n+1})$ and $({C_2}^{\prime }-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^{\prime }$ is a ground instance of $C$. Let $T{}^{″}$ be the closed semantic tree for $S\cup \{C\}$ , obtained from $T^{\prime }$ by deleting all nodes below the first node which falsifies $C^{\prime }$. Note, that $S$ is unsatisfiable if and only if $S\cup \{C\}$ is unsatisfiable. Clearly, $T{}^{″}$ has less nodes than $T^{\prime }$ 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 $S$ and let $R_1,\dots ,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,\dots ,R_k$; this, however, is impossible, because one of this resolvents is $◻$.

Figure 2

Problems

Problem 14 (Predicate)

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)),\mathrm{\neg }p(x,y,z)\},\{\mathrm{\neg }p(s(s(s(0))),s(s(0)),u)\}\}$
2. $\{\{q(x),q(s(x))\},\{\mathrm{\neg }q(x),\mathrm{\neg }q(s(s(x)))\}\}$
   ($\star$)
3. $\{\{\mathrm{\neg }r(x,f(x),y),\mathrm{\neg }r(x,g(y),z)\},\{r(c,u,i(v)),r(h(u),v,j(v))\}\}$

$◻$

Problem 15 (Predicate)

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

$F$

and

$F[x/t]$

. Then

$ℐ(F[x/t])={ℐ}_{[x/ℐ(t)]}(F),$

is valid, if

$t$

does not contain any variable that

$[x/t]$

is laced

by the substitution in $F$.
$◻$

Problem 16 (Predicate)

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))\}$

$◻$

Problem 17 (Predicate)

Determine all direct resolvents of the following pairs of clauses:

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

$◻$

Problem 18 (Predicate)

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)\}$

$◻$

Problem 19 (Predicate)

Determine all direct resolvents of the following pairs of clauses:

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

$◻$

Problem 20 (Predicate)

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!

$\{\{\mathrm{\neg }e(x),o(s(x))\},\{\mathrm{\neg }e(x),\mathrm{\neg }o(s(x)),e(s(s(x)))\},\{e(a)\},\{\mathrm{\neg }o(s(s(s(s(s(a))))))\}\}$

$◻$

Problem 21 (Predicate)

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)),\mathrm{\neg }p(x,y,z)\},\{\mathrm{\neg }p(s(s(s(0))),s(s(0)),u)\}\}$
2. $\{\{q(x),q(s(x))\},\{\mathrm{\neg }q(x),\mathrm{\neg }q(s(s(x)))\}\}$
   ($\star$)
3. $\{\{\mathrm{\neg }r(x,f(x),y),\mathrm{\neg }r(x,g(y),z)\},\{r(c,u,i(v)),r(h(u),v,j(v))\}\}$

$◻$