Regeln und Substitutionen: Vom syntaktischen Standpunkt betrachtet ist eine Regel eine Objektliste der Art
x=>y oder
x:=>y. Wir bezeichnen
x als Variable oder als Muster, wenn sie keine Variable ist. Außerdem bezeichnen wir
y als Bild und
x=>y oder
x:=>y als Paar. Eine Substitution ist eine ausschließlich über Variablen definierte Regel. Wenn wir
=> wählen, verwenden wir den Wert von
y zur Definition der Regel. Wählen wir aber
:=>, so betrachten wir
y bei der Definition der Regel als Variable.
Wir können die Symbole => und :=> mit den Symbolbildern
und
erzeugen (in dieser Reihenfolge).
Wenn man eine Regel auf einen Ausdruck anwendet, werden alle Muster (oder Variablen), die im Ausdruck auftauchen, durch das Bild des Musters (oder der Variablen) ersetzt. Alle Terme, die nicht mit dem Muster (oder der Variablen) übereinstimmen, bleiben unverändert.