Substitution

  • x[x:=N] == N
  • y[x:=N] == y if x != y
  • (%l y.M)[x:=N] == %l y.(M[x:=N])
  • (M_1 M_2 ) [x:=N] == (M_1 [x:=N]) (M_2[x:=N])

slide: The lambda calculus -- substitution