Substitution A function:∑*→∑* is a substitution iff 1.f∈∑.,then(x)≠6 2.fx,y∈∑*,then(xy)=(x)(y) If B1 and B2 are substitutions such that B1(a)=B2() for every primitive symbol then Logic in Computer Science - p 7/39Substitution A function θ : Σ∗ → Σ∗is a substitution iff 1. If x ∈ Σ, then θ(x) 6=  2. If x, y ∈ Σ∗, then θ(xy) = θ(x)θ(y) If θ1 and θ2 are substitutions such that θ1(x) = θ2(x) for every primitive symbol x, then θ1 = θ2 Logic in Computer Science – p.7/39