# 7. Type-free λ-calculus homework # 1

## Как выполнять и сдавать домашнюю работу
* Скопируйте все задания в Google Doc.
* В документе выполните все задания.
* Прикрепите документ с выполненными заданиями в качестве решения.

## Задания
#### 1. Расставьте скобки
1. λv.vp λu.v u
2. (λv.vp) λu.w λw.wupv
3. λv.v u λv.uv

#### 2. Подчеркните все свободные переменные
1. λv.v p λu.v u
2. (λv. v p) λu. w λw. w u p v
3. λv. v u λv. u v

#### 3. Примените β-редукцию (и α-конверсию там, где это необходимо) до тех пор, пока это возможно. В ответе укажите все этапы преобразования выражения
1. (λp.p) (λu.u u) (λv.v s)
2. (λp.p) (λp.p p) (λp.p u)
3. (λv.λu.v u u) (λs.s) t
4. (λv.λu.v u u) (λu.u) u
5. (λv.v v) (λu.u v) p
6. (λv. (λu. (v u)) u) p
7. ((λv.v v) (λu.u)) (λu.u)
8. (((λv. λu.(v u))(λu.u)) w)

#### 4. Покажите, что заданные выражения имеют несколько различных последовательностей редукции
1. (λv.u) ((λu.u u u) (λv.v v v))
2. (λvu.v) (λu.u) ((λv.v v) (λv.v v))