Substitutionen: Produkt

Produkt von Substitutionen: t(σ₁oσ₂) = (tσ₁)σ₂

Beispiel 1:

σ₁ = {X $\mapsto$ Y}, σ₂ = {Y $\mapsto$ a}, σ₁oσ₂ = {X $\mapsto$ a, Y $\mapsto$ a}.

Beispiel 2 (nachrechnen!):

σ₁ = {X $\mapsto$ Y}, σ₂ = {Y $\mapsto$ X}, σ₁oσ₂ = σ₂

Eigenschaften:

• σ pur ⇒ σ idempotent: σoσ = σ
• σ₁ pur ∧ σ₂ pur impliziert nicht σ₁oσ₂ pur

Implementierung:

import Data.Map 
type Substitution = Map Identifier Term
times :: Substitution -> Substitution -> Substition