In designing an actual realization of the unification algorithm the first question which arises is how best to represent the expressions in the computer store. We have a collection of tables: symbol, args, vble, arity, subst, term, equals, and part, each of which has the same number N of rows. All the tables have one column, with the exception of args; and args has as many columns as the arity of that symbol, in the expressions being represented, whose arity is largest. We always arrange matters so that in a normal representation, distinct rows represent distinct expressions, i.e., so that We are now ready to explain the computation.
It seems most unlikely that one could in general write purely applicative Schonfmkel descriptions', like (5), of functions already known to one in some other form. One makes assertions in the system by writing clauses, i.e., finite collections of literals considered as disjunctions of their members, universally quantified with respect to all variables. In other words, this is a first-order language in which there is only one relation symbol, namely equality; only one function symbol, namely application; and a collection of individual constants. In particular the resolution principle may be used as sole principle; or the resolution principle together with paramodulation (Robinson and Wos 1969); or Sibert's system (Sibert 1969); or the E-resolution system of Morris (1969).
The generalized resolution principle is a single inference principle which provides, by itself, a complete formulation of the quantifier-free first-order predicate calculus with equality. The completeness theory of the generalized resolution principle exploits the very intuitive and natural idea of attempting to construct counterexamples to the theorems for which proofs are wanted, and makes this the central concept. The expressions are all built up from primitive We shall usually employ lower case letters for individual symbols and upper case letters for function and relation symbols. Similarly, a counterexample to a general proposition is an interpretation which strongly satisfies its premisses but falsifies its conclusion.
These programs have generated proofs of some interesting propositions of number theory, in addition to theorems of first-order functional logic and group theory. Quantifiers do not occur in these formulae, since existentially quantified variables have been replaced by functions of universally quantified ones, and the remaining variables may therefore be taken as universally quantified. Starting with a finite number of individual constants, all possible substitutions were made in the input clauses, and the resulting conjunction of substitution instances was tested for truth-functional consistency. Davis in fact proved that any substitution instance Lo/L2 v vL„ that contains at least one unmated literal may be erased without affecting consistency, and that the test for consistency may be confined to'linked conjuncts', i.e., conjuncts (or clauses) wherein each literal Li is negated by a mate This'theorem on linked conjuncts' provides a necessary, though not a sufficient, condition of relevance: any substitution instance containing an unmated literal is demonstrably irrelevant to consistency and may be deleted forthwith, but the remaining substitution instances are not necessarily all relevant.