Question

In the following expressions say which, if any, variables are bound (and to which λ), and which are free.

λs.s z λq.s q

(λs. s z) λq. w λw. w q z s

(λs.s) (λq.qs)

λz. (((λs.sq) (λq.qz)) λz. (z z))

Answer 1

i) λs.s z λq.s q

s bound at {s} in λs.s z λq.s q

s free at {s} in λs.s z λq.s q

in λq.{s} q

in {s}

z free at {z} in λs.s {z} λq.s q

in λs.s {z}

in {z}

q bound at {q} in λs.s z λq.s q

in λq.s q

ii) (λs. s z) λq. w λw. w q z s

s bound at {s} in (λs. s z) λq. w λw. w q z s

s free at {s} in (λs. s z) λq. w λw. w q z s

in λq. w λw. w q z {s}

in λw. w q z {s}

in {s}

z free at {z} in (λs. s z) λq. w λw. w q z s

in (λs. s {z}) in {z}

in λw. w q {z} s

in {z}

q bound at {q} in (λs. s z) λq. w λw. w q z s

in λq. w λw. w q z s

q free at {q} in  (λs. s z) λq. w λw. w {q} z s

in  λw. w {q} z s

in {q}

w bound at {w} in (λs. s z) λq. w λw. w q z s

in λw. w q z s

w free at {w} in (λs. s z) λq. {w}λw. w q z s

in λq. {w} λw. w q z s

in λq. {w}

in {w}   

iii) (λs.s) (λq.qs)

s bound at {s} in (λs.s) (λq.qs)

in (λs.s)

s free at {s} in (λs.s) (λq.q{s})

in  λq.q{s}

in {s}

q bound at {q} in (λs.s) (λq.qs)

in λq. q s

iv) λz. (((λs.sq) (λq.qz)) λz. (z z))   

z bound at {z} in λz. (((λs.sq) (λq.q{z)}) λz. (z z))

z free at {z} in λz. (((λs.sq) (λq.q{z)}) λz. (z z))

in  (λs.sq) (λq.q{z})) λz. (z z)

in λq.q{z}

in {z}

s bound at {s} in λz. (((λs.sq) (λq.qz)) λz. (z z))

in (λs.sq)

q bound at {q} in λz. (((λs.sq) (λq.qz)) λz. (z z))

in (λq.qz)

q free at {q} in λz. (((λs.s{q}) (λq.qz)) λz. (z z))

in λs.s{q}

in {q}