# Catalogue of Artificial Intelligence Techniques

## Least General Generalisation

**Keywords:**
least general generalisation

### Categories: Theorem Proving , Inference and Reasoning , Logic Programming

Author(s): **Steve Muggleton**

Plotkin showed that there exists a dual of the most general unifier of two literals. Suppose that the most general unifying substitution (see Unification) for two first-order literals, ${l}_{1}^{}$ and ${l}_{2}^{}$ is $\theta $ . Then${l}_{1}^{}\theta ={l}_{2}^{}\theta $

is called the most general instance (mgi) of${l}_{1}^{}$

and ${l}_{2}^{}$ . Like the most general instance, the least general generalisation (lgg) of ${l}_{1}^{}$ and ${l}_{2}^{}$ does not always exist. However, whenever ${l}_{1}^{}$ and ${l}_{2}^{}$ have the same predicate symbol and sign their lgg is unique up to renaming of variables. Generalisation over literals is defined by subsumption. ${l}_{1}^{}$ subsumes${l}_{2}^{}$

whenever there exists a substitution $\theta $ such that${l}_{1}^{}\theta ={l}_{2}^{}$

. Plotkin showed that due to the uniqueness of the least general generalisation and most general instance, subsumption forms a infinite semi-lattice over first-order literals. Plotkin extends this result to show that the same holds for subsumption over clauses. Subsumption can be defined relative to given first-order clausal background theory, $B$ (see Clausal Form). In this case, clause $C$ relatively subsumes clause $D$ whenever $B\wedge C\u22a2D$ . Plotkin studies the case in which $\u22a2$ is taken to be Resolution-based derivation in which each clause in$B\wedge C$

is used at most once. In this case there exists a unique relative least general generalisation (rlgg), $C$ of two clauses ${D}_{1}^{}$

and ${D}_{2}^{}$ . In Muggleton (1991) it is shown that the relative subsumption lattice is the same as the lattice searched by Inverse Resolution. More specifically the most specific inverse resolvent to depth $n$ is unique up to renaming of variables. The least general generalisation of the most-specific inverse resolvents of ${D}_{1}^{}$ and ${D}_{2}^{}$ is equivalent to the relative least general generalisation of ${D}_{1}^{}$ and ${D}_{2}^{}$ .

### References:

- Muggleton, S.,
*Inductive Logic Programming*New Generation Computing**8**(1991) no.4, 295--318.

### Comments:

No comments.