How do I simplify these lambda calculus equations?

86 Views Asked by At

How do I solve these lambda calculus equations?

  1. $\lambda x y z . x y (z x)$

  2. $\lambda x y z . x y (z x y)$

For 1, is this correct?

$xy[xyz := zx] = x$?

1

There are 1 best solutions below

2
On BEST ANSWER

I'm assuming the parentheses make these expressions in the form $(\lambda x y z . x y)(z x)$. In both cases you are applying one $\beta$-reduction which replaces the variable $x$ with the term in the parentheses.

1) $\lambda x y z . x y (z x)$ $\beta$-reduces to $\lambda y z . zxy$

2) $\lambda x y z . x y (zxy)$ $\beta$-reduces to $\lambda y' z . zxy y'$

Note we had to rename the bound variable $y$ to $y'$ to prevent it from being duplicated. Only $x$ is being replaced in the term inside the $\lambda$-abstraction, so we have $xy[x := zx]$ instead of $xy[xyz := zx]$.