# Logic for Computer Scientists/Predicate Logic/Strategies for Resolution/SLD-Resolution

## Selective Linear Definite (SLD) Resolution

In this section we will introduce a special form of linear resolution for Horn clauses. We will interpret a clause a program by notationing it in the following form:

${\displaystyle {\begin{matrix}A&\gets &&&{\text{program clause (fact)}}\\A&\gets &B_{1},\ldots ,B_{n}&&{\text{ program clause }}\\&\gets &B_{1},\ldots ,B_{n}&&{\text{ goal }}\\\end{matrix}}}$

## Definition 27

Let ${\displaystyle P}$ be a set of program clauses. Assume a selection function, which gives for a given goal ${\displaystyle \gets A_{1},\ldots ,A_{n}}$ one of its subgoals ${\displaystyle A_{i}}$. Further assume a goal ${\displaystyle G_{i}=\gets A_{1},\ldots ,A_{m},\ldots ,A_{n}}$ and a selection function which selects ${\displaystyle A_{m}}$. Let ${\displaystyle C_{i}=A\gets B_{1},\ldots ,B_{q}}$ be a variant of a clause in ${\displaystyle P}$, such that ${\displaystyle C_{i}}$ and ${\displaystyle G_{i}}$ have no variable in common. If ${\displaystyle \theta _{i+1}}$ is most general unifier of ${\displaystyle A_{m}}$ and ${\displaystyle A}$, the goal

${\displaystyle G_{i+1}=\gets (A_{1},\ldots ,A_{m-1},B_{1},\ldots ,B_{q},A_{m+1},\ldots ,A_{n})\theta _{i+1}}$

is called SLD-resolvent

## Definition 28

An SLD-deduction (-refutation)of ${\displaystyle P\cup \{G\}}$ for a set of program clauses ${\displaystyle P}$ and a goal clause ${\displaystyle G}$ is a linear deduction (refutation) in which only SLD-resolution steps occur and ${\displaystyle G}$ is the start clause.

• An ${\displaystyle R}$-computed answer substitution ${\displaystyle \theta }$ for ${\displaystyle P\cup \{G\}}$ is ${\displaystyle \theta _{1}\circ \ldots \circ \theta _{n}|_{Var(G)}}$, where ${\displaystyle \theta _{1},\ldots ,\theta _{n}}$ are the mgUs from a SLD-refutation of ${\displaystyle P\cup \{G\}}$ with selection function ${\displaystyle R}$.
• A substitution ${\displaystyle \theta }$ for ${\displaystyle Var(G)}$ is an answer substitution for ${\displaystyle P\cup \{G\}}$.
• It is a correct answer substitution for ${\displaystyle P\cup \{G\}}$, if ${\displaystyle P\models \forall G\theta }$

## Theorem 11

Let ${\displaystyle P}$ be a set of program clauses, ${\displaystyle G}$ a goal clause and ${\displaystyle R}$ a selection function. For every correct answer substitution ${\displaystyle \theta }$ for ${\displaystyle P\cup \{G\}}$, there is an ${\displaystyle R}$-computed answer substitution ${\displaystyle \sigma }$ for ${\displaystyle P\cup \{G\}}$ and a substitution ${\displaystyle \gamma }$, such that ${\displaystyle \theta =\sigma \circ \gamma \;|_{Var(G)}}$

In the Section on Propositional Logic we already explained propositional tableaux and its variants, like the connection calculus and model elimination. In this section we will give model elimination in the first order case. Note that we need one more inference rule, the reduction rule, in this case

## Definition 29

A clause (normalform) tableau for a set of clauses ${\displaystyle S}$ is a tableau for ${\displaystyle S}$, whose nodes are literals from ${\displaystyle S}$ and which is constructed by a (possibly infinite) sequence of applications of the following rules:

• The tree consisting of root ${\displaystyle true}$ and immediate successors ${\displaystyle L_{1},\cdots ,L_{n}}$, where ${\displaystyle C=L_{1},\cdots ,L_{n}}$ is a new variant of a clause from ${\displaystyle S}$ is a tableau for ${\displaystyle S}$ (initialisation rule).
• Let ${\displaystyle T}$ be a tableau for ${\displaystyle S}$, ${\displaystyle B}$ a branch of ${\displaystyle T}$, and ${\displaystyle C=L_{1},\cdots ,L_{n}}$ an new variant of a clause from ${\displaystyle S}$, such that the link-condition with mgu ${\displaystyle \sigma }$ is satisfied. If the tree ${\displaystyle T'}$ is constructed by extending ${\displaystyle B}$ by the ${\displaystyle n}$ subtrees ${\displaystyle L_{i}}$, then ${\displaystyle T'\sigma }$ is a tableau for ${\displaystyle S}$ (expansion rule).
• Let ${\displaystyle T}$ be a tableau for ${\displaystyle S}$, ${\displaystyle B}$ a branch of ${\displaystyle T}$, ${\displaystyle L}$ a leaf of ${\displaystyle B}$, and ${\displaystyle L'\in C}$, such that ${\displaystyle {\overline {L'}}}$ and ${\displaystyle L}$ have a mgu ${\displaystyle \sigma }$, than ${\displaystyle T\sigma }$ is a tableau for ${\displaystyle S}$ (reduction rule).

The following are three possible link conditions:

1. No condition.
2. Weak link condition: There is a literal ${\displaystyle L\in B}$ and ${\displaystyle L'\in C}$, such that ${\displaystyle {\overline {L'}}}$ and ${\displaystyle L}$ have a mgu ${\displaystyle \sigma }$
3. Strong link condition: There is a leaf ${\displaystyle L}$ of ${\displaystyle B}$, and ${\displaystyle L'\in C}$, such that ${\displaystyle {\overline {L'}}}$ and ${\displaystyle L}$ have a mgu ${\displaystyle \sigma }$ .

Analog to the propositional case the different link conditions result in different calculi:

• The empty condition results in a clause normal form tableau calculus.
• The weak condition results in a connection calculus.
• The strong link condition results in a model elimination calculus.