Equational Logic

The terms of equational logic are built up from variables and constants using function symbols (or operations). Identities (equalities) of the form

(1)

where  and  are terms, constitute the formal language of equational logic. The syllogisms of equational logic are summarized below.

1. Reflexivity:

(2)

2. Symmetry:

(3)

3. Transitivity:

(4)

4. For  a function symbol and ,

(5)

5. For  a substitution (cf. unification),

(6)

The above rules state that if the formula above the line is a theorem formally deducted from axioms by application of the syllogisms, then the formula below the line is also a formal theorem. Usually, some finite set  of identities is given as axiom schemata.

Equational logic can be combined with first-order logic. In this case, the fourth rule is extended onto predicate symbols as well, and the fifth rule is omitted. These syllogisms can be turned into axiom schemata having the form of implications to which Modus Ponens can be applied. Major results of first-order logic hold in this extended theory.

If every identity in  is viewed as two rewrite rules transforming the lذeft-hand side into the right-hand side and vice versa, then the respective term rewriting system is equivalent to the equational logic defined by : The identity  is deducible in the equational logic iff  in the term rewriting system. This property is called logicality of term rewriting systems.

Equational logic is complete, since if algebra  is a model for , i.e., all identities from  hold in algebra  (cf. universal algebra), then  holds in  iff it can be deduced in the equational logic defined by . This theorem is sometimes known as Birkhoff's theorem.

REFERENCES

Baader, F. and Nipkow, T. Term Rewriting and All That. Cambridge, England: Cambridge University Press, 1999.

Burris, S. and Sankappanavar, H. P. A Course in Universal Algebra. New York: Springer-Verlag, 1981.

 http://www.thoralf.uwaterloo.ca/htdocs/ualg.html.Kleene, S. C. Mathematical Logic. New York: Dover, 2002.

Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, pp. 1158 and 1172, 2002.