DEA 01/02
DEA 9/10/01
Résumé: cours du 9/10/01
cours précédent ........ cours suivant..........tous les cours
Contenu du cours: Arbres, syntaxe du lambda-calcul, variables libres et
liées; substitution; beta-réduction.
Exercices.
Soient $A,B,C$ trois termes et $x,y$ deux variables distinctes.
A quelle condition
a-t-on $A[x:=B][y:=C]=A[y:=C][x:=B]$?
Soient $A,B,C$ trois termes. A quelle condition
a-t-on $A[x:=B][x:=C]=A[x:=C][x:=B]$?
Calculer $x :x$ [x:= lam x.x]$.
Définir l'ensemble $BV(M)$ des variables liées dans $M$.
L'intersection de $BV(M)$ et $FV(M)$ est-elle vide. Alors?
On pose $D:= lam x. x:x$. Calculer $D: lam x. x:y$.
Problème.
On considère l'ensemble $L$ des suites finies d'entiers positifs (on dit
aussi que c'est l'ensemble des chemins).
Donner une définition plus précise de cet ensemble. Mettre cet ensemble en
bijection avec un ensemble de parties de $N2$; avec
une partie de $R$; avec une partie de $N$.
Choisir des définitions méritant les noms "étêter" et "équeuter".
Formuler et démontrer quelques principes d'induction pour $L$.
Formuler et démontrer deux principes de récursion pour $L$.
On munit $L$ de l'ordre "préfixe": $u =< v$ ssi $v$ commence par $u$.
Préciser cette définition, et montrer que c'est un ordre. Les bijections que
vous avez trouvées sont-elles croissantes, bicroissantes?
On note $L2$ le sous-ensemble de $L$ des suites de $1$ et de $2$ et
on appelle arbre binaire toute partie finie "commençante" de $L2$.
On note $A2$ l'ensemble des arbres binaires.
Choisir des définitions méritant les noms "sous-arbre droit" et
"sous-arbre gauche" et "feuilles" d'un arbre binaire.
Formuler et démontrer quelques principes d'induction et un principe de
récursion pour $A2$.
Mettre l'ensemble des types simples en bijection avec l'ensemble des
arbres binaires.
Mettre l'ensemble des lambda-termes en bijection avec un ensemble
d'arbres binaires "munis" d'une application vers $V+{lam, app}$. Préciser
cette définition et caractériser les arbres atteints.
Même question avec $V+{app}$.
On munit $L$ d'un ordre plus fin que l'ordre préfixe, dans lequel
on
a aussi, pour toute suite $u$ et tout entier $n$: $u;n < u;n+1$.
Préciser
cet ordre.
On appelle arbre toute partie finie "commençante" de $L$.
On note $A$ l'ensemble des arbres. Donner un exemple d'arbre binaire qui n'est
pas un arbre.
Mettre l'ensemble des lambda-termes normaux en bijection avec un ensemble
d'arbres "munis" d'une application vers $Vx{lam, app}$.
Mettre l'ensemble des lambda-termes normaux en bijection avec l'ensemble
des arbres "munis" d'une application vers $list(V)xV$.
cours précédent ........ cours suivant..........tous les cours
Andre.HIRSCHOWITZ
Last modified: Oct 2