CSE 472/572, Spring 2002
COMPOSITION OF SUBSTITUTIONS
In lecture, we did the following example:
Let sigma = {f(y)/x, z/y}
tau = {a/x, b/y, y/z}.
Compute Compose(sigma, tau).
The result, as you should recall, was {f(b)/x, y/z}.
To show that composition of substitutions is not commutative, I
asked you to compute Compose(tau, sigma). Here is the solution:
Compose(tau, sigma) =

{Subst(sigma, a)/x, Subst(sigma, b)/y, Subst(sigma, y)/z, f(y)/x, z/y}
= {a/x, b/y, z/z, f(y)/x, z/y}

Remove {z/z, f(y)/x, z/y}
to yield {a/x, b/y}
which is not = Compose(sigma, tau)
Copyright © 2002 by
William J. Rapaport
(rapaport@cse.buffalo.edu)
file: 572/S02/compose.26mr01.html