Induction

 

 

1.      Montrez par récurrence que pour tout entier n, la somme des n premiers entiers non nuls est égale à n(n+1)/2

P(n) est ici la propriété (en notant S_n, la somme des n premiers entiers non nuls) :  S_n =  n(n+1)/2

Base :

On commence par vérifier que le résultat est vrai pour n = 0 : en effet la somme d’aucun entier1 vaut 0.

Hypothèse de récurrence (appelée aussi Hypothèse d'induction) :

On suppose que le résultat est vrai à l’ordre n, c'est-à-dire S_n = n(n+1)/2.

Montrons qu'alors le résultat est vrai à l’ordre n+1, c'est-à-dire que la somme des S_n+1=  (n+1)(n+2)/2.

S_n+1=  S_n + (n+1), donc par hypothèse d’induction : S_n+1=  n(n+1)/2 + (n+1).

Puis en factorisant (n+1), on obtient ce que l'on cherche S_n+1=  (n+1)(n+2)/2.

 

2.      Montrez par récurrence que la somme des cubes des n premiers entiers non nuls est égal au carré de la somme de ces entiers

P(n) est ici la propriété (en notant S_n, la somme des n premiers entiers non nuls et SommeDesCubes_n, la somme des cubes des n premiers entiers non nuls) :
SommeDesCubes_n =  (S_n)²

Base : On commence par vérifier que le résultat est vrai pour n=0, en effet la somme d’aucun cube vaut 0.

Hypothèse de récurrence

On suppose que le résultat est vrai à l’ordre n, c'est-à-dire SommeDesCubes_n =  (S_n)².

Montrons que le résultat est vrai à l’ordre n+1

La somme des cubes des n+1 1 premiers entiers non nuls, est égale à (n+1)³ plus la somme des cubes des n premiers entiers non nuls qui par hypothèse d’induction est égale à (n(n+1)/2)². Donc la somme des cubes des n+1 premiers entiers non nuls est bien (n+1(n+2)/2)².

 

3.      Modifiez la forme du raisonnement par récurrence pour prouver inductivement qu’une propriété est vraie pour les entiers pairs, puis pour les entiers relatifs

Pour les entiers pairs, il suffit de montrer P(0) et que pour tout n pair, P(n) entraîne P(n+2)

Pour les entiers relatifs, il suffit de montrer P(0) et que pour tout n positif, P(n) entraîne P(n+1) et P(n-1)

D'autres formulations sont possibles.

 

4.      Validité de la  récurrence

 

Supposons qu’il existe une propriété P qui soit vraie pour 0, qui si elle est vraie pour n soit vraie pour n+1 et qui cependant n’est pas vraie pour tous les entiers. Soit F l’ensemble des entiers pour lesquels cette propriété est fausse. F est non vide par hypothèse, donc F étant un sous ensemble non vide de N possède un plus petit élément, soit n₀ celui ci. Comme n₀ ne peut pas être nul, n₀  -1 est un entier, qui par définition du plus petit élément n’est pas dans F. Donc la propriété P est vraie pour n₀  -1  , et par donc elle est vraie pour n₀  -1+1 = n₀    , une contradiction.

 

 

5.      Trouver l’erreur dans la démonstration suivante de la propriété suivante : pour tout n entiers, si un paquet de n pièces contient une pièce de un euro, alors ce paquet ne contient que des pièces de un euros

  Base : Cette propriété est bien sûr vraie pour  n=1.

 

Induction : Supposons donc que la propriété est vraie pour tout paquet de n pièces.

On va montrer qu'alors elle est vraie pour tout paquet de  n+1 pièces.

Soit donc un paquet de  n+1 pièces contenant une pièce de 1€. Retirons l'une des pièces qui ne soit pas cette pièce, on a un paquet de n pièces. Ce paquet contient une pièce de 1€. Par hypothèse de récurrence, ce paquet ne contient donc que des pièces de 1€. Rajoutons la pièce qu'on avait enlevée : si c'est 1€, on a terminé. Sinon, enlevons du paquet une des n autres pièces. On obtient alors un nouveau paquet de n pièces contenant au moins 1€, et par hypothèse de récurrence il ne contient que des pièces de 1€.

 

On a donc prouvé qu'il n'y a que des pièces de 1€ ???

 

L'affirmation erronée a été mise en gras dans le texte.

L’étape inductive n’est pas vraie pour n=1, c'est-à-dire que que p(1) n'implique pas P(2), car le nouveau paquet de 1 pièce ne contient pas nécessairement 1€ !

 

 

6.      Nous allons démontrer que lorsque n pièces de monnaies, avec n supérieur à 2, d'apparence identique sont données, avec une plus légère que les autres, alors il suffit d’une pesée sur une balance à 2 plateaux pour identifier la plus légère.

 

 

Lorsque n=2, c'est facile ! On place une pièce sur chaque plateau de la balance, l'équilibre ne se fait pas car par hypothèse une des pièces est plus légère, et cette pesée permet de la déterminer.

 

On suppose maintenant que l'on connaît une procédure utilisant une pesée pour n pièces, et montrons comment en obtenir une pour n+1 pièces. Donnons-nous (n+1) pièces dont l'une est plus légère que les autres (qui, elles, ont toutes un poids identique). Nous mettons à part l'une des pièces, et appliquons la procédure donnée par l'hypothèse de récurrence pour les n pièces restantes. Si cette procédure fonctionne, on connaît la pièce la plus légère, sinon, c'est celle qu'on a mis à part qui est la plus légère.

 

L'affirmation erronée a été mise en gras dans le texte. On ne peut pas appliquer la procédure donnée par l'hypothèse de récurrence, car parmi ces n pièces restantes, il n'y a pas nécessairement la pièce plus légère (elle n'y est pas si par malchance, on a mis à part cette pièce plus légère) et rien n'est dit ce que fait la procédure pour un paquet de n pièces toutes de même poids.

 

7.      Justification de la récurrence forte

Première démonstration

Supposons qu’il existe une propriété P qui soit vraie pour 0, qui si elle est vraie pour tout entier m <n est aussi  vraie pour n et qui cependant n’est pas vraie pour tous les entiers. Soit F l’ensemble des entiers pour lesquels cette propriété est fausse. F est non vide par hypothèse, donc F étant un sous ensemble non vide de N possède un plus petit élément, soit n₀ celui ci. La propriété P est vraie pour tous les entiers strictement plus petits que n₀,  par définition du plus petit élément de F. Elle est donc vraie pour n₀  , une contradiction.

 

Seconde démonstration

Soit Q(n) la propriété : Pour tout m<n P(n) est vrai.

Alors une récurrence forte sur P est équivalente à une récurrence simple sur Q

 

8.      Montrer que tout nombre entier positif est le produit de (un ou plusieurs) nombres premiers.

Preuve par récurrence forte

Base : c’est vrai pour n=2, puisque 2 est lui-même premier.

Induction : Supposons que tout entier strictement inférieur à n soit le produit de un ou plusieurs nombres premiers.

Montrons que n est le produit de un ou plusieurs entiers premiers.

Si n est premier, n lui même est le produit de un nombre premier.

Sinon, n admet deux diviseurs d et p, différent de 1 et de n. On a donc n=dp, où d et p sont deux entiers strictement inférieur à n. Chacun d’eux est donc le produit d’un ou plusieurs nombres premiers, et n est donc lui-même le produit d’un ou plusieurs nombres premiers.

 

 

9.      Donnez un exemple d’ordre total et un exemple d’ordre partiel.

Il y en a plusieurs dans le cours, la relation « inférieur ou égal » sur les entiers ou les réels est un ordre total (lorsque l’on compare deux entiers, il y en a toujours un qui est inférieur ou égal  à l’autre), en revanche la relation d’inclusion pour les parties d’un ensemble est un ordre partiel ( si l’on regarde les deux ensembles í1ý et í2ý, aucun n’est inclus dans l’autre).

 

10.  Montrer que la relation être préfixe est une relation d’ordre.

La relation est réflexive, un mot est préfixe de lui-même. Elle est antisymétrique, c’est-à-dire que si u est préfixe de v et que v est préfixe de u, alors nécessairement les deux mots sont de même longueur, et ont toutes leurs lettres identiques, ils sont donc égaux.

La relation est aussi transitive, si u est préfixe de v, et v préfixe de w, alors u est préfixe de w.

Ce n’est pas un ordre total, par exemple deux mots chacun composé d’une seule lettre  ne sont pas préfixe l’un de l’autre si ces deux lettres sont différentes.

 

 

11.  Définir formellement l’ordre lexicographique. Montrez qu’il s’agit bien d’un ordre et dites s’il est partiel ou total

 

On suppose que l’alphabet est muni d’une relation d’ordre total ≤.

Soient u=u₁u₂…u_n et v=v₁v₂…v_m deux mots sur A, on définit la relation infLex par u infLex v si et seulement si

ou u est un préfixe de v

ou il existe k, 0 ≤k<inf(n,m) tel que pour tout i ≤k u_i=v_i et u_k+1 ≤ v_k+1 et u_k+1 ≠ v_k+1.

 

Il s’agit bien d’un ordre, en effet

-         infLex est reflexive, car u infLex u puisque u est prefixe de u.

-         infLex est antisymétrique, en effet supposons u infLex v et v infLex u

Cas 1 u est prefixe de v, on a alors deux sous cas :

            Cas 1.1 v est prefixe de u, on a alors u=v

            Cas 1.2 il existe k, 0 ≤k<inf(longueur(u),longueur(v)) tel que pour tout i ≤k u_i=v_i et v_k+1 ≤ v_k+1 et u_k+1 ≠ v_k+1., mais ceci est imcompatible de v prefixe de u

 

Cas 2 il existe k, 0 ≤k<inf(n,m) tel que pour tout i ≤k u_i=v_i et u_k+1 ≤ v_k+1 et u_k+1 ≠ v_k+1.

                Cas 2.1  v est prefixe de u : mais ceci est incompatible

            Cas 2.2 il existe k, 0 ≤k<inf(longueur(u),longueur(v)) tel que pour tout i ≤k u_i=v_i et u_k+1 ≤ v_k+1 et u_k+1 ≠ v_k+1. mais ceci est incompatible

Donc necessairement on a u=v et la relation est bien antisymètrique

-         infLex est transitive

Supposons u infLex v et v infLex w

Cas 1 u est prefixe de v

            Cas 1.1 v est prefixe de w, dans ce cas, u est prefixe de w et donc infLex w

            Cas 1.2 il existe k, 0 ≤k<inf(longueur(v),longueu(w)) tel que pour tout i ≤k w_i=v_i et v_k+1 ≤ w_k+1 et w_k+1 ≠ v_k+1.,

                        Cas 1.2.1 longueur(u) ≤k dans ce cas u est prefixe de w et donc u infLex v

                        Cas 1.2.2 longeur(u)>k, fans ce cas, 0 ≤k<inf(longueur(u),longueu(w)) tel que pour tout i ≤k w_i=u_i et u_k+1 ≤ w_k+1 et w_k+1 ≠ u_k+1.,donc u infLex w

 

 

Cas 2 il existe k, 0 ≤k<inf(longueur(u),longueur(w)) tel que pour tout i ≤k u_i=v_i et v_k+1 ≤ v_k+1 et u_k+1 ≠ v_k+1.,

Cas 2.1 v est prefixe de w, donc 0 ≤k<inf(longueur(u),longueur(v)) tel que pour tout i ≤k u_i=w_i et u_k+1 ≤ w_k+1 et w_k+1 ≠ u_k+1., donc u infLex w

Cas 2.2 il existe k’, 0 ≤k’<inf(longeur(v),longueur(w)) tel que pour tout i ≤k’ w_i=v_i et v_k’+1 ≤ w_k’+1 et w_k’+1 ≠ v_k’+1.,

            Cas 2.2.1 k’>=k, dans ce cas  0 ≤k<inf(longueur(u),longueur(w)) tel que pour tout i ≤k u_i=w_i et u_k+1 ≤ w_k+1 et w_k+1 ≠ u_k+1., donc u infLex w

 

            Cas 2.2.2k’<k Dans ce cas 0 ≤k’<inf(longueur(u),longueur(w)) tel que pour tout i ≤k’ u_i=w_i et u_k’+1 ≤ w_k’+1 et w_k’+1 ≠ u_k’+1., donc u infLex w

 

 

 

 

 

On vérifie « aisément » qu’il s’agit d’un ordre total .

 

12.  Dans (IN, ≤) quels sont les minorants et les majorants de E’=í6,8,23ý ?

 

Les minorants sont tous les entiers inférieurs ou égaux à 6. Les majorants sont tous les entiers supérieurs ou égaux à 23.

13.  Dans(P(IN),Ì), quels sont les minorants et les majorants de E’=í í6,8,23,42ý , í8,23,37ý , í6,8,23ýý ?

Les minorants sont í8,23ý,í23ý,í8ý et l’ensemble vide. En fait tout ensemble inclus dans l’intersection des trois élémentq de E’ est un minorant.

Les majorants sont tous les sous-ensembles de N qui contiennent í6,8,23,37,42ý. En fait tout ensemble contenant l’union des trois éléments de E’ est un majorant.

 

14.  Donnez, si possible, un exemple d’un sous-ensemble E’ d’un ensemble ordonné  (E,≤) n’ayant aucun majorant

Il suffit de choisir E=E’=N et la relation d’ordre usuelle.

 

15.  Donnez, si possible, un exemple d’un sous-ensemble E’ d’un ensemble ordonné (E,≤) n’ayant aucun minorant

Il suffit de prendre E=E’=Z, et la relation d’ordre usuelle

 

16.  Mêmes questions si la relation d’ordre est un ordre total

Les ordres donnés en exemple sont des ordres totaux.

 

17.  Si A= ía,b,c,dý est un alphabet muni d’un ordre strict a<b<c<d et si (A⁺,£ ) est l’ensemble des mots sur A muni de l’ordre lexicographique, quels sont les minorants et les majorants de íaab, ab,cdý ?

Les minorants sont le mot vide, a, aa, aab, et tous les mots commençant  par aaa.

Les majorants sont tous les mots qui commencent par cd, et tous les mots commençant par d.

 

18.  Un élément de E’ peut-il être un majorant de E’?

Oui par exemple dans (N, £), 23 est un minorant de E’=í2,8,23ý

 

19.  E’ peut-il avoir plusieurs majorants?

Oui, voir plus haut

 

20.  Deux éléments distincts de E’ peuvent-il être majorants de E’?

Non car si x et y sont deux majorants de E’ alors x est inférieur ou égal à y et y est inférieur ou égal à x, donc x=y.

 

21.  Est ce que cela change quelque chose si la relation d’ordre est totale?

non

22.  ou si l’ensemble E est fini?

Non

 

23.  Donnez un exemple d’ensemble ordonné (E,≤)  et de sous-ensemble E’ admettant minimum, (resp.un maximum)

On peut choisir (E,≤)= (N,≤) et E’ égal à n’importe quel sous-ensemble de N.

24.  Donnez un exemple d’ensemble ordonné (E,≤)  et de sous-ensemble E’ n’admettant pas de minimum, (resp. de maximum)

On peut choisir  E=(P(N),Ì), et E’=íí2,8,23ý, í12,8,23ý

 

25.  Dans (N, ≤) E’=í6,8,23ý a t-il un minimum, un maximum?

Oui, le minimum est 6, le maximum est 23.

26.  Dans (R, ≤), E’=[3,7[ a-t-il un minimum, un maximum ?

Le minimum est 3, mais il n’y a pas de maximum

27.  Dans(P(N),Ì)í í6,8,23,42ý , í8,23,37ý , í6,8,23ýý a -t-il un minimum, un maximum ?

Non

28.  Dans(P(N),Ì), í í6,8,23,42ý , í8,23,37ý , í6,8,23ýý a -t-il un élément maximal, minimal?

í6,8,23,42ý et í8,23,37 sont deux éléments maximaux. , í8,23,37ý et  í6,8,23ý sont deux éléments minimaux.

 

29.  Montrer la Proposition : Si E’ a un maximum (resp. minimum), alors c’est son unique élément maximal (resp. minimal).

Supposons que E’ admette un maximum M, c'est-à-dire un élément M qui appartient à E’ et qui est supérieur ou égal à tout élément de E’.

Montrons d’abord que M est un élément maximal.

Supposons qu’il existe un y dans E’ tel que y≥ M, comme M est maximum, on a aussi y≤M, et donc y=M. Donc M est bien un élément maximal.

Considérons  M’ un élément maximal quelconque de E’, alors puisque M est un maximum on a M≥M’. Mais puisque M’ est maximal, cela entraîne M=M’. M est donc bien l’unique élément maximal.

 

 

30.  La reciproque de la Proposition : Si E’ a un maximum (resp. minimum), alors c’est son unique élément maximal (resp. minimal) est elle vraie ?

Non , elle est fausse. Considérons l’ensemble ordonné constitué de l’ensemble E des  intervalles de R muni de l’inclusion. Soit E’ le sous ensemble de E formé de l’intervalle [1,2], et de tous les intervalles [3,n], avec n entier , n>3.  E’ ne contient qu’un élément maximal, l’intervalle [1,2], mais cependant E’ n’a pas de maximum.

 

En revanche , si l’ensemble ordonné (E, ≤) est muni d’ordre total, alors si un sous ensemble E’ ne contient un élément maximal, alors cet élément est unique. En

effet si M et M’ sont deux éléments maximaux on a soit M≤M’ soit M’≤M,  et M et M’ étant maximaux on en déduit M=M’.

De plus cet élément maximal est aussi maximum. En effet supposons que M soit maximal et que M ne soit pas maximum. Alors il existe m dans E, tel que m≤M n’est pas vrai. Comme la relation d’ordre est totale, cela signifie que l’on a M<m, et donc puisque M est maximal, on a m=M, une contradiction.

 

31.  Démontrer par l’absurde la Proposition : Un ensemble ordonné (E,£) est bien fondé si et seulement si toute partie non vide de E admet au moins un élément minimal.

Si l’ensemble n’est pas bien fondé, c’est qu’il existe une suite infinie strictement décroissante. Soit E’ le sous ensemble composé des éléments de cette suite, E’ est une partie de E non vide sans élément minimal, donc si toute partie non vide admet au moins un élément minimal , l’ensemble ordonné est bien fondé

Reciproquement, supposons qu’un ensemble soit bien fondé et qu’il existe une partie non vide F  n’admettant pas d’élément minimal. On peut alors construire une suite infinei décroissante u_nde la manière suivante. Pour u1, on choisit un élément quelconque de F, F n’admettant pas d’élémént minimal, il y a dans F des éléments strictement plus petits que u₁, on en choisit un que l’on nomme u₂. Supposons que la suite soit construite jusqu’à un, F n’admettant pas d’élémént minimal, il y a dans F des éléments strictement plus petits que u_n, on en choisit un que l’on nomme u_n+1. On peut donc construire ainsi une suite infinie strictement décroissante.

 

 

.

 

32.  (IN,£) est-il bien fondé (relation d’ordre usuelle) ?

oui

33.  (Z,£) est-il bien fondé (relation d’ordre usuelle) ?

non, car la suite un=-n est une suite infinie décroissante

 

34.  L’ordre préfixe est-il bien fondé ?

Oui , car si u est préfixe de v et u est différent de v, alors la longueur de u est inférieur à v, il ne peut donc pas y avoir de suite infinie strictement décroissante.

35.  L’ordre lexicographique est-il bien fondé ?

Il l’est si l’alphabet ne comporte qu’une seule lettre, sinon il ne l’est pas, car  la suite aⁿb est une suite infinie strictement décroissante

 

36.  Donner un bon ordre sur l’ensemble des mots sur un alphabet fini A.

Par exemple u ≤ v si lg(u) < lg(v) ou (lg(u)=lg(v) et u infLex v).

Il s’agit bien d’un ordre, en effet :

• u ≤ u, donc la relation est reflexive.
• Elle est transitive :

Supposons u ≤ v et v ≤ w

            Cas 1 : lg(u) < lg(v)

                        Cas 1.1 lg(v) < lg(w). Dans ce cas lg(u)<lg(w) et donc u ≤w

                        Cas 1.2 (lg(w)=lg(v) et v infLex w)., dans ce cas lg(u)<lg(w) et donc u ≤w

 

Cas 2 (lg(u)=lg(v) et u infLex v).

                        Cas 2.1 lg(v)< lg(w), dans ce cas lg(u) < lg(w) et donc u ≤w

 

                        Cas 2.2 (lg(w)=lg(v) et v infLex w). dans ce cas lg(u)=lg(w) et u infLex w, donc u ≤w.

• Elle est antisymétrique

Supposons  u ≤ v et  v ≤u

            Cas 1 : lg(u) < lg(v)

Cas 1.1 lg(v) < lg(u). impossible

Cas 2.2 (lg(u)=lg(v) et v infLex u), impossible

 

 

Cas 2 (lg(u)=lg(v) et u infLex v).

                        Cas 2.1 lg(v)< lg(u), impossible                      

Cas 2.2 (lg(u)=lg(v) et v infLex u). dans ce cas u=v.

 

Il s’agit donc bien d’une relation d’ordre.

C’est un ordre total, puisque inflex est un ordre total.

L’ordre est bien fondé, en effet considerons un mot m sur l’alphabet A. Il n’existe qu’un nombre fini de mots strictement inférieur à m. En effet, il y a un nombre fini de mots de longueur strictement plus petite à celle de m, et un nombre fini de mots de longueur égale à m.

 

37.  Montrer que le programme suivant termine sur les entiers naturels strictement positifs

while (m!=n) {

            if (m > n) {

                        m = m-n;

            } else {

                        n = n-m;

            }

}

Considérons l’ordre défini par

(m,n) ≤(m’,n’) si et seulement si (m<m’) ou (m=m’ et n≤n’)

Il s’agit bien d’une relation d’ordre total sur N², et (N², ≤) est bien fondé.

Le seul élément minimal de N*² est (1,1).

Le programme ci-dessus termine pour le couple (1,1)

Supposons que le programme termine pour tous les couples (m’,n’)<(m,n).

Alors il termine aussi pour le couple (m,n), en effet après le premier tour de boucle on se trouve dans les mêmes conditions que si l’on avait pris pour valeurs initiales (m-n,n) ou (n,m-n) et dans les deux cas il s’agit d’un couple de N*² strictement plus petit que (m,n).

 

 

 

38.  Donnez une définition inductive de l’ensemble des entiers pairs. Donnez une définition inductive des entiers relatifs

 

On peut définir les entiers pairs comme le plus petit ensemble qui contient 0 et qui est stable pour l’opération « ajouter 2 ».

On peut définir les entiers relatifs, comme le plus petit ensemble qui contient 0 et qui est stable pour les opérations « ajouter 1 » et « retirer un ».

 

39.  Analyse constructive :Soit B_i la suite d’ensembles définie par

B₀=B

B_i+1=W(B_i) U B_i

Soit F=U B_i

Soit E défini inductivement par le schéma (B,W)

 

Montrez que E=F

 

On va montrer la double inclusion

EÌF

F contient la base B.

F est stable par W, en effet considérons une règle w de W, d’arité p, soient x₁,x₂,….x_p, p éléments de F, chaque xi appartient à un certain B_ji. Soit j le plus grand de tous les indices ji, les p x_i appartiennent à B_j, donc w(x₁,x₂,…x_p) appartient à B_j+1 et donc à F.

 

Puisque E est le plus petit ensemble au sens de l’inclusion, contenant B et stable par W, et puis que F lui aussi contient B et est stable par W, alors F contient nécessairement E

FÌE

On va montrer par récurrence sur i que B_i est inclus dans E

Base :SI i=0, c’est vrai puisque E contient B

Hypothèse de récurrence, E contient B_i

Soit x dans B_i+1 .Soit x est dans B_i et donc dans E, soit il est dans =W(B_i ) . Mais les éléments de B_i ,sont par hypothèse de récurrence des éléments de E, et E est stable par W , donc x est bien dans E

 

40.  Un ensemble défini par induction structurelle, peut être muni d’un ordre bien fondé, lequel? Quels sont les éléments minimaux pour cet ordre?

Considérons la relation xRy si et seulement si il existe w de W, x=w(x₁,x₂,…x_p) et il existe i tel y=x_i et x différent de y.

Soit R’ la fermeture transitive de R, c'est-à-dire la relation définie par

xR’y si et seulement si(( xRy) ou (il existe z tel que xRz et zR’y )).

Notons x≤y si et seulement si x=y ou xR’y.

≤ est un ordre (mais ce n’est pas forcement un ordre total).

Les éléments minimqux pour cet ordre sont les éléments de la base de l’ensemble.

 

 

41.  Analyse descendante :Montrez que x appartient à E si et seulement si

–x est dans B

ou

–il existe w dans W , et un p-uplet (x₁,x₂,...,x_p) d’éléments de E tel que x= w (x₁,x₂,...,x_p)

 

 

Clairement si l’une des deux conditions est vérifiée, alors x appartient à E.

Réciproquement, supposons qu’il existe un élément de E ne vérifiant aucune de ces deux conditions. Soit y cet élément. Considérons F =E-íyý.

Puisque y n’appartient pas à B, et que B est inclus dans E, B est aussi inclus dans F.

Si l’on applique une règle à des éléments de F,on obtient un résultat dans E, qui ne peut pas être y, et donc qui est dans F.

F est donc stable pour W. Ceci contredit la définition de E, plus petit ensemble contenant B et stable pour W.

 

42.  Les schémas donnés plus tôt pour définir les entiers, les entiers pairs, les entiers relatifs sont ils libres ?

 

Oui pour celui des entiers pairs, en effet 0 qui est dans la base ne peut pas être obtenu par la règle n donne n+2. Un élément qui n’est pas dans la base est obtenu par l’unique règle à partir de l’unique entier pari k-2

 

Non pour les entiers relatifs, 0 est dans la base, peut être obtenu en ajoutant un à moins un ou en retirant un à un.

 

43.  Donner une définition par induction structurelle de l’ensemble A+ des mots finissnon vides.

 

Base toute lettre un mot

Règle : Si m est un mot et a une lettre, am est un mot.

 

44.  Donner une définition par induction structurelle de l’ensemble A* des mots finis

 

Base le mot vide est  un mot

Règle : Si m est un mot et a une lettre, am est un mot.

 

45.  Le premier schéma définissant les mots finis non vidse est il libre ?

 

Oui, parce que  la règle  produit des mots ayant au moins deux lettres, et qu’un mot produit par la règle à un antécédent unique

 

46.  Le second schéma définissant les mots finis non vide est il libre ?

 

Non, le mot aaaa peut être produit par la règle à partir de (aa,aa) ou à partir de (a,aaa)

 

47.  Donner deux exemples de schéma inductif ne comportant qu’une seule règle et cependant non libre?

 

C’est le cas pour le deuxième schéma définissant les mots.

C’est aussi le cas pour le schéma suivant

Base a,b,c, et d sont dans E

Règle si x et y sont dans E, x+y est dans E

 

Ce schéma n’est pas libe car a+b+c peut être formé à partir de a+b et de c ou de a et de b+c.

 

 

48.  Le schéma définissant les mots finis est-il libre ?

 

Oui, car e ne peut être produit par une règle (tout mon produit contient au moins une lettre), et un mot produit par la règle ne peut avoir qu’un antécédent.

 

49.  Les mots suivants sont-ils dans LP?

–(((()))

–(((((())))))

–(())()

–()(())

–()()()

–(()())(())

 

Montrons que tous les mots de la forme (ⁱ)ⁱ  sont dans LP (cette notation représente un mot formé de i parenthèses ouvrantes suivies de i parenthèses fermantes).

Par récurrence sur i.

Si =0 c’est vrai , car l mot vide est dans LP

On suppose que c’est vrai pour un certain i. Le mot (ⁱ⁺¹)^{i +1} est aussi dans LP car il peut être produit par la règle en prenant u=(ⁱ)ⁱ  et v=e.

Le premier mot n’est pas dans LP, car il ne contient pas aurant de ( que de ). On justifiera plus tard cette intuition

Le second est dans LP

Le troisième est dans LP  car il peut être produit par la règle en choisissant u=v=()

Le quatrième est dans LP car il peut etre produit parla règle en choisissant u=e et v=(())

Le cinquième est dans LP car il peut etre produit par la règle en choisissant u=e et v=()(), lequel v est dans LP car il peut etre produit par la règle en choisissant u’=e et v’=().

Le sixième est dans LP car il peut etre produit par la règle en choisissant u=()()e et v=(())

 

 

50.  Exercice 13

Démontrez la validité de  l’induction structurelle

 

Si ce n’etait pas le cas, il existerait une propriété P et un ensemble E défini par un schéma inductif, tel que P soit vrai pour tout élément de la base, P soit propagée par chacune des règles du schéma et cependant il existe au moins un élément e de E pour le quel la propriété est non vide.

Soit F le sous ensemble de E constitué des éléments de E pour lesquels la propriété P est vraie.

B est inclus dans F puisque P est  vrai pour tout élément de la base

F est stable par les règles du schéma définissant E puisque  P est propagée par chacune des règles du schéma

F est strictement inclus dans E.

Ce qui contredit le fait que E est le plus petit ensemble contenant B et stable parles règles.

 

51.  Montrer que ces définitions sont bien correctes pour N2

(0,0) Î E

(n,m) Î E Þ (n,m+1) Î E

(n,m) Î E Þ (n+1,m) Î E

 

 

(0,0) Î F

(n,m) Î F Þ (n,m+1) Î F

(n,0) Î F Þ (n+1,0) Î F

 

En déduire deux schémas de preuve par induction sur N²

 

Premier ensemble

E est inclus dans N².

Par induction structurelle

Base (0,0 ) est dans N²

Supposons (n,m) dans N², alors (n+1,m) et (n+1,m) sont dans N²

 

 N²est inclus dans E

On va montrer par récurrence sur k que n£k, m£k impliquent que (n,m) est dans E.

 

Pour k=0, c’est vrai car (0,0) est dans E

On suppose que pour un certain k, n£k, m£k impliquent que (n,m) est dans E.

Soit (n,m) tels que  n£k+1 et  m£k+1.

Sin£k et  m£k , (n,m) est dans E.

Si n£k, et m=k+1, alors par hypothèse de récurrence, (n,m-1) est dans E et donc (n,m) est dans E .

Si m£k, et n=k+1, alors par hypothèse de récurrence, (n-1,m) est dans E et donc (n,m) est dans E .

(k,k) étant dans E, (k+1,k) est dans E et (k+1,k+1) aussi.

On en déduit qu’une propriété P(n,m) est vraie pour tout les couples d’entiers (n,m) si et seulement si P(0,0) est vraie, et P(n,m)ÞP(n+1,m) et P(n,m)ÞP(n+1,m)

 

Second  ensemble

F est inclus dans N².

Par induction structurelle

Base (0,0 ) est dans N²

Supposons (n,m) dans N², alors (n+1,m) est dans N²

Supposons (n,0) dans N², alors (n+1,0) est dans N²

 

 N²est inclus dans F

On va montrer par récurrence sur k que n+m£k impliquent que (n,m) est dans F.

 

Pour k=0, c’est vrai car (0,0) est dans F

On suppose que pour un certain k, n+m£k impliquent que (n,m) est dans E.

Soit (n,m) tels que  n+m£k+1.

Si m=0, alors par hypothèse de récurrence, (n-1,0) est dans F et donc (n,m) est dans F .

Si m est non nul,

 si n est nul, alors (n,m) est dans F,

 sinon (n-1,m) est dans N²et donc par hypothèse de récurrence dans F. Par définition de F, (n,m) est donc dans F.

On en déduit qu’une propriété P(n,m) est vraie pour tout les couples d’entiers (n,m) si et seulement si P(0,0) est vraie, et P(n,m)ÞP(n+1,m) et P(n,0)ÞP(n+1,0)

 

52.  Soit M  le sous ensemble de (0,1)* constitué des mots ayant autant de 0 que  de 1. Soit E l’ensemble défini de manière inductive par

Base  eÎE

Règles:   m ÎE  Þ0m1 ÎE

                m ÎE  Þ1m0 ÎE

 

a) Le  schéma définissant E est –il libre?

b) A-t-on  M  Ì E?

c) A-t-on  E Ì M?

 

a)      le schéma définissant E est libre, en effet

-                                 aucun mot ne peut être dans la base (donc de longueur de nulle) et produit par une règle (donc de longueur au moins deux)

-                                 un mot se terminant soit par un un soit par un zéro, il ne peut être produit que par l'une des deux règles.

-                                 Un seul antécédent est possible pour une règle donnée, car 0m1=0m'1 entraîne m=m' et de même 1m0=1m'0 entraîne m=m'.

 

 

b)      Non , par exemple, le mot 0110 appartient à M (il comporte autant de zéro que de un), mais pas à E ( il n'est pas dans la base et aucune règle ne peut le produire)

c)      Oui. La preuve se fait facilement par induction structurelle

Base : le mot vide contient autant de zéro que de un(zéro de chaque)

Propagation : Supposons que m contienne autant de zéro que de un, alors clairement il en est de même de 0m1 et de 1m0.

 

53.  Donnez et prouvez une définition inductive pour l’ensemble des mots binaires palindromes

 

Une définition possible est

Base    {e,0} est inclus dans E

Règles  Si m est dans E, alors m1 est dans E

                         Si m est dans E, alors m10 est dans E

Soit MBS20C l'ensemble des mots binaires ne comportant pas deux zéros consécutifs

 

Montrons l'égalité des deux ensembles

E est inclus dans MBS20C

            La preuve se fait très simplement par induction structurelle

            Base: e et 0  sont bien des mots binaires et ne comportent pas deux zéros consécutifs

            Propagation: Supposons que m ne comporte pas deux zéros consécutifs, alors il en est de même de m1 et de m10.

MBS20C est inclus dans E

            La preuve se fait sur la longueur des mots de MBS20C

           

                        Si cette longueur est 0 alors le mot est dans la base de E, donc dans E

                        Supposons que tout mot de MBS20C de longueur <k est aussi dans E

                                   Soit alors m un mot de MBS20C de longueur k.

            Si sa longueur est un il est dans la base, ou produit par la règle à partir de e, on peut donc supposer k au moins égal à deux.

            Si la dernière lettre de m est un 1, alors m=m'1 et m' est lui aussi un mot de MBS20C. Comme la longueur de m' est <k, m' est dans E (par hypothèse de récurrence) et donc m=m'1 est aussi dans E (par définition de E)

            Sinon, la dernière lettre de m est un 0, mais alors son avant dernière lettre est forcément un 1 et m=m'10, et m' est lui aussi un mot de MBS20C. Comme la longueur de m' est <k, m' est dans E (par hypothèse de récurrence) et donc m=m'10 est aussi dans E (par définition de E)

Le schéma est libre, en effet :

-                                 aucun mot ne peut être dans la base (donc de longueur de un) et produit par une règle (donc de longueur au moins deux)

-                                 un mot se terminant soit par un un soit par un zéro, il ne peut être produit que par l'une des deux règles.

-                                 Un seul antécédent est possible pour une règle donnée, car m1=m'1 entraîne m=m' et de même m10=m'10 entraîne m=m'.

 

54.  Donner et prouver une définition inductive pour l’ensemble des mots binaires ne comportant pas deux zéros consécutifs

 

Soit E l’ensemble défini par le schéma inductif

Base e , 0 sont dans E

Règle m,m’ dans E Þm1m’ dans E

Montrons que E est égal à MB , l’ensemble des mots binaires ne comportant pas deux zéros consécutifs ;

E ÌMB

Démonstration par induction structurelle

Base e et 0 sont dans MB

Propagation :Supposons que m,m’ soient dans MB, alors m1m’ ne comporte que les lettres 0 et 1, et ne comportent pas deux zéros consécutifs dans E

MBÌE

Montrons par récurrence sur k que tout mot de MB de longueur inférieure ou égale à k appartient à E.

Base k=0 : le seul mot de MB de longueur inférieure ou égale à 0 est e qui appartient à E

Hypothèse de récurrence : Pour un certain k, tout mot de MB de longueur inférieure ou égale à k appartient à E.

Soit m un mot de MB de longueur k+1.

Si m comporte un 1, m est de la forme m₁1m₂, où m₁ et m₂ sont deux mots de MB de longueur inférieure ou égale à k, et donc par hypothèse de récurrence ils sont dans E. Par définition de E m est aussi dans E.

Si m ne comporte aucun 1, m=0. et m est dans E

 

 

 

55.  Donnez et prouvez une définition inductive pour l’ensemble des mots binaires représentant des entiers pairs sans zéro inutile en tête.

 

Soit E l’ensemble défini de manière inductive par

Base : 0 est dans E

Règles Si m est dans E alors 1m est dans E

  Si m¹0 et m ‘ sont dans E, mm’ est dans E

 

Soit MBP l’ensemble des mots binaires représentant les entiers pairs sans zéro inutile en tête.

 

Montrons par induction structurelle que EÌMBP

Base

0 représente bien un mot binaire pair sans 0 inutile en tête

Propagation

Supposons que m soit dans MB, alors 1m est aussi dans MB puis qu’il se termine par 0 et commence par un un.

Supposons que m et m’ sont dans MB, et que m soit différent de 0, alors mm’ commence par un un et termine par un zéro, et donc mm’ est bien dans MBP

 

Montrons par récurrence sur k que tout mot de MBP de longueur au plus k est dans E.

Base k=1, le seul mot concerné est le mot 0 qui est dans E

Hypothèse de récurrence : pour un certain entier k>0, tout mot de MBP de longueur au plus k est dans E.

Soit m un mot de MBP de longueur k+1. m est de longueur au moins deux, donc m commence par un 1 et termine par un 0

Si m est de longueur deux, m=10 et donc m appartient à MBP

 

Sinon, m=1m’0. Si m’ termine par un 0, m=1n00, le mot 1n0 est dans MBP, il est de longueur k et donc il appartient à E et m aussi est dans E.

Sinon si m’ ne comporte que des un, m=11n0, le mot 1n0 est dans MBP, il est de longueur k et donc il appartient à E et m aussi est dans E.

Sinon le mot m’ comporte des 0 et des 1, de plus m’ termine par un 1, m’ est donc de la forme m’=n01ⁱ, donc m=1n01ⁱ0. Or 1n0 et 1ⁱ0 sont deux mots de MBP de longueur inférieure à k, donc des mots de E, donc m est dans E.

 

 

 

56.  Montrez que  LBP=LP

Montrons d’abord que LPÌ LBP par induction structurelle

Base P(e ) est vrai, puisque le mot vide est dans LBP

Propagation :

Montrons que P(u) et P(v) entraînent P((u)v).

Un préfixe de (u)v est soit

• Le mot vide
• Le mot (
• (p_u ou p_u est un préfixe de u
• (u) p_v où p_v est un préfixe de v

Dans tous les cas, ce préfixe comporte au moins autant d’ouvrante que de fermante.

De plus (u)v contient exactement autant d’ouvrantes que de fermantes.

Donc (u)v est bien dans LBP.

 

Réciproquement montrons par récurrence sur n la propriété

H(n): tout mot m de longueur n vérifiant P(m) est dans LP

 

H(0) est vrai car e est le seul mot de longueur 0 et il appartient à LP

Supposons H(p) vrai pour tout p<n

Soit m un mot vérifiant P(m) et de longueur n

m=m₁m₂…m_n

Soit f(i)= le nombre de ( - le nombre de ) dans les i premières lettres de m

P(m)Û "i f(i)≥0 et f(lg(m))=0

Soit k le plus petit entier tel que f(k)=0 (il existe car f(n)=0)

f(k-1)=1 donc m_k=)

Posons u=m₁m₂..m_k-1, et v=m_k+1..m_n

On a m=(u)v, et u et v vérifient tous les deux la propriété P. Ils sont de longueur  strictement  inférieure à n, donc par hypothèse ils sont dans LP. Par définition de LP, m est donc aussi dans LP

 

 

 

57.  Montrez que le schéma définissant LP est libre

Clairement un mot ne peu pas être à la fois dans la base et construit par les règles. Supposons qu’il existe m=(u)v=(u’)v’, avec u,v,u’,v’ dans LP.

Avec la même fonction f que pour l’exercice précédent, on a f((u))=0=f((u’)).

Supposons que u et u’ soient différents, alors ils sont forcement de longueur différente.

On peut donc supposer que lg(u)<lg(u’). Alors u) est un préfixe de u’ puisque (u)v=(u’)v’, mais u) contient plus de ) que de (, en contradiction avec u’ dans LP.

Donc u=u’, et donc v=v’.

 

58.  Montrez que LP = LP2. Le schéma définissant LP2 est il libre ?

 

 

1)      LP et LP2 sont identiques

 

Montrons tout d'abord que LP est inclus dans LP2, par induction structurelle sur LP

 

            Tout mot de la base de LP est dans LP2, car les deux ensembles ont la même base.

 

Supposons que les mots u et v de LP soient aussi dans LP2, alors par définition de LP2, le mot (u) est dans LP2 (Règle 2) et puisque (u) et v sont dans LP2, (u)v est dams LP2 (Règle 1), donc si u et v sont dans LP2, (u)v est dans LP2.

 

On vient de prouver que tous les mots de LP ont la propriété d’« appartenir à LP2 » par induction structurelle sur LP2

 

 

Montrons maintenant que LP2 est inclus dans LP

 

A nouveau, faisons une induction structurelle sur LP2 cette fois.

 

            Tout mot de la base de LP2 est dans LP

 

            Si un mot u de LP2 est dans LP il en est de même de (u), car on peut appliquer la règle de LP avec v égal au mot vide.

 

 

            Soient maintenant  u et v mots de LP2 , supposons qu’ils sont dans LP, et montrons que uv est lui aussi dans LP

                   Il suffit donc  de montrer que si u et v sont dans LP alors uv est dans LP

 

Or, on sait que les mots de LP sont les mots composés d'exactement autant d'ouvrantes que de fermantes, et tels que tout préfixe comporte au moins autant d'ouvrantes que de fermantes. Donc nécessairement si u et v sont dans LP, alors uv contient exactement autant d’ouvrantes que de fermantes, tout préfixe de uv contient au moins autant d’ouvrante que de fermante, puisqu’un préfixe de uv est soit un préfixe de u, soit u suivi d’un préfixe de v, et que u et v sont dans LP. Donc uv est bien dans LP.

 

 

 

2)      Ce schéma n'est pas libre : par exemple le mot ()()() peut être produit à partir de la première règle avec u=() et v=()() ou bien avec u=()() et v=()

 

 

 

59.  Soit A l'alphabet {(,)}, soit L le sous ensemble de A* formé des mots dont  tous les préfixes contiennent au moins autant de ( que de )

a) Donnez une définition inductive de L et la prouver

b) Montrez que L n’est pas égal à l’ensemble des mots bien parenthésés.  Comment peut-on associer à un mot de L, un mot bien parenthésé

c) Prouvez soit que le schéma donné en a) est libre soit qu'il est ambigu

 

Première solution

Une définition possible est

            Base :    est dans  M

            Règles :Si m et m'  sont dans M alors om et (m)m' sont dans M

 

M est inclus dans L par induction structurelle , en effet e appartient à L et si tout préfixe de m et de m' comprennent au moins autant de ( que de ), alors il en est de même de om et de (m)m', les préfixes de (m)m’ étant de la forme (p_m ou (m)p_m’, p_m étant un préfixe de m et p_m’ un préfixe de m’.

 

Réciproquement, soit m un mot  de longueur n, soit p_i le préfixe de m composé des i premières lettres, et soit c(m,i)= le nombre de ( dans p_i moins le nombre de ).

Notons que m appartient à L si et seulement si c(m,i) ³0, pour tout i, 1£i£n. En particulier tout mot de L commence par la lettre (.

 

Montrons par récurrence sur n que tout mot de L appartient à M.

 

Base Si n=0, m= et donc m appartient à M

 

Etape inductive

Supposons que tout mot de L de longueur strictement inférieure à n appartient à M

 

Soit l un mot de L, de longueur n

Premier cas :  c(l,i)>0 pour tout i 1£i£n

            Si l n’est pas le mot vide, alors l=(l’, et comme c(l,i)=c(l’,i-1)+1,  c(l’,j)³0, pour tout j 1£j£n-1, et donc l’ appartient à L. Comme l’ est de longueur n-1, par hypothèse de récurrence l’ appartient à M. Donc l appartient à M par définition de M.

 

Deuxième cas : il existe k tel que c(l,k)=0

            Soit j le plus petit entier tel que c(l,j)=0. On a donc c(l,i)>0, pour tout i 1£i£j-1.  La j-ième lettre de l est nécessairement un f. Soit m tel que p_j=(m). Comme c(l,k)=1+c(m,k-1), m appartient à L, et par hypothèse de récurrence à M. Soit m’ le mot éventuellement vide tel que m=p_jm’, on a c(m,k)=c(m’,k-i), et donc m’ aussi appartient à L et par récurrence à M. On a donc l=(m)m’, avec m et m’ dans M, donc l appartient à M.

 

deuxième solution

Une autre définition possible est

            Base :    et ( sont dans  M

            Règles :Si m et m' sont dans M alors (mf et mm' sont dans M

 

M est inclus dans L par induction structurelle , en effet eet ( sont dans L et si tout préfixe de m et de m' comprennent au moins autant de ( que de ), alors il en est de même de (m)  (dont les préfixes non vides sont de la forme (p_m ) et de mm' (dont les préfixes sont de la forme p_m ou mp_m’ )

 

En utilisant les mêmes notations que pour la première définition, montrons par récurrence sur la longueur des mots que tout mot de L est dans M.

 

Base : le mot vide est bien dans M

Hypothèse de récurrence : Tout mot de L de longueur inférieure à n est dans M

 

Soit l un mot de L de longueur n.

Premier cas c(l,i)>0, pour tout i 1£i£n

Alors l=(m’, où m’ est un mot de L . Si m’ est le mot vide alors l=( appartient à M. Sinon

Ou bien la dernière lettre de m’ est un (. Dans ce cas l=(l’(, et (l’ est dans L et par hypothèse d’induction il est aussi dans M. Par définition de M, l=(l’( est donc dans M.

Ou bien la dernière lettre de m’ est un ). Dans ce cas l=(l’) et l’ est dans L et par hypothèse d’induction il est aussi dans M. Par définition de M  l=(l’)est donc aussi dans M

 Deuxième cas il existe k tel que c(l,k)=0, choisissons pour k , le plus petit entier tel que c(l,k)=0,

Soit m=p_k et m’ tel que l=mm’. m et m’ sont dans L.

Si m’ n’est pas le mot vide alors la longueur de m et de m’ est inférieur à n et donc par hypothèse d’induction ils sont tous les deux dans M et donc l aussi appartient à M

Si m’ est le mot vide (k=n), alors l=(m), avec m dans L et donc dans M. En conséquence, l est dans M.

 

Question b)

le mot ( est dans M mais n’est pas bien parenthésé. En fait il suffit d’ajouter en fin d’un mot de M le nombre de ) nécessaires pour équilibrer le nombre de ) et de ( pour rendre ce mot bien parenthésé.

 

Question c)

Le premier schéma donné en a) n'est pas libre, en effet le mot (() peut être dérivé soit avec la règle (m et m=(), soit avec la règle (m)m’ avec m=( et m’ vide.

Le second schéma n’est pas libre non plus, le mot ((( peut être dérivé par la règle mm’ avec m=( m'=((, soit avec m'=( , m=((.

 

 

 

 

 

60.  Soient Var et Op deux alphabets disjoints.

On pose A= Var U Op.

On appelle langage des expressions polonaises préfixées le langage L sur  A défini par le schéma :           

Base     Var  Ì L          

Règle    Si w Î Op,  u,v ÎL, alors wuv Î L  

En supposant que  Var={0,1,2,3,4,5,6,7,8,9}

et Op={+,-,/,*}, le  mot

+ + * 2 4 - 5 7 - 4 + 3 2  est-il dans L?

 

Montrez qu'un mot w de A* appartient à L si et seulement si il  vérifie les deux conditions suivantes :           

 i)w contient une variable de plus que d’opérateurs

 ii ) tout préfixe propre p de w contient au moins autant d’opérateurs que de variables

Montrez que le schéma définissant L est libre.

 

 _{Le mot est dans L, on peut l’obtenir de la manière suivante}

3,2                                          Þ        + 3 2

4, +3    2                                 Þ        -4 + 3 2

2 4                                          Þ        * 2 4

5 7                                          Þ        - 5 7

* 2 4, - 5 7                              Þ        +* 2 4 - 5 7

+* 2 4 - 5 7, -4 + 3 2  Þ        ++* 2 4 - 5 7 -4 + 3 2

 

 Montrons par induction structurelle sur L que tout mot m de L vérifie les 2 propriétés

 

            Si m est dans la base, alors  et m n'a aucun préfixe propre, donc les deux propriétés sont vérifiées.

 

            Supposons que u et v vérifient les deux propriétés, alors  vérifie aussi les deux propriétés

En effet par hypothèse :

 et

 

 

Donc

Et donc wuv vérifie la première propriété

 

Pour montrer que wuv vérifie la seconde propriété, examinons p un prefixe propre quelconque de wuv.

Cas 1,  p= w, alors p vérifie bien

Cas 2 p=wp_u  où p_u est un prefixe propre de u. Par hypothèse d'induction , et donc

Cas 3 p=wup_v p_u  où p_v est un prefixe propre de u. Par hypothèse d'induction  et , et donc

 

 

Réciproquement, montrons par induction sur la longueur du mot que si un mot vérifie les deux propriétés, alors il appartient à L.

 

Pour tout mot m posons d(m) =

Soit  w un mot vérifiant les deux propriétés, c'est à dire tel que d (w)=1 et d (p)<1 pour tout préfixe propre p de w.

 

            Si w est de longueur 1, alors w est une variable  ( à cause de la propriété 1) et w appartient à L.

 

            Sinon supposons que tout mot de longueur inférieure où égale à n vérifiant les deux propriétés est  dans L.

 

            Soit w un mot de longueur n+1, vérifiant les deux conditions, alors nécessairement ce mot commence par un opérateur :   (remarque : je ne peux pas dire ici que p vérifie les propriétés i et ii parce que ce n'est pas vrai, je vais chercher deux mots u et v qui vérifient les propriétés ( et qui donc par hypothèse de récurrence seront dans L, tels que p =uv )

 

Appelons  le préfixe de p comportant i lettres. 

Puisque   est un préfixe de w, d ( ) £  0, d'autre part puisque , on a  d(wp_n)=1. Donc il existe i, 1£ i tel que pour tout j<i,  d(wp_j)<0 et d(wp_i) =0.  (i est le plus petit entier tel que  d(wp_i) =0. )

Puisque w est un opérateur, on a donc pour tout j<i,   d(p_j)<= 0 et  d(p_i) =1.

Donc p_i vérifie les  deux propriétés, comme il est de longueur strictement inférieure à n, il est donc dans L.

Soit r tel que  . Puisque  d(wp_i) =0, r lui aussi vérifie les deux conditions. Comme r est de longueur strictement inférieure à n, il appartient à L, il en est donc de même pour w.

 

 

Montrons que le schéma est non ambigu

 

Soit w un mot de L, ayant n lettres , et supposons qu'il existe deux opérateurs et  et quatre mots de L   tels que w=.

 

Nécessairement  =

 

                _{Si  et  sont de la même longueur, alors ils doivent être égaux.}

            Sinon, supposons . Alors   étant un  mot de L , d(  ) = 1, mais

            par ailleurs  est un préfixe propre de   donc d (  ) < 0, contradiction.  

Donc nécessairement  _{et  sont de la même longueur.}

_{On a donc u1=u2 et v1=v2.}

 

 

 

 

61.  Exercice 24 :Comme pour la fonction factorielle, donnez des définition inductives des fonctions:

                        Add_m

                        Multiply_by_m

 

Add_m(0)=m Add_m(n+1)=Add_m(n)+1

Ou

public int addM(int n){

            if (n==0) return 1

            else return 1+addM(n-1)

}

Multiply_by _m(0)=0 Multiply_by _m(n+1)= Multiply_by _m(n)+m

Ou

public int Multiply_by_M(int n){

            if (n==0) return 0

            else return m+ Multiply_by_M (n-1)

}

 

 

62.  On défini les ensemble E,F,G et H par

 

Base 0 et 1  sont dans E

Règle Si n est dans E, alors n+2 est dans E

 

Base 0 est dans F

Règle Si n est dans F, alors  2*n est dans F

 

Base 0 est dans G

Règle Si n est dans G, alors 2*n+1 est dans G

 

Base 0 est dans H

Règles

Si n est dans H, alors 2*n est dans H          

Si n est  dans H, alors 2*n+1 est dans H1)      

A  quoi sont égaux ces 4 ensembles ?

Les schémas sont ils libres?

En vous appuyant sur une définition inductive de N, donnez une définition inductive des fonctions n modulo 2, division entière  de n par 2 et écriture de n en base deux.

 

1)      L'ensemble E est égal à N

Tout élément de E est dans N, par induction structurelle sur E (ajouter 2 à un entier donne un entier)

Tout élément de N est dans E, par récurrence sur  N:

      0 et 1 sont dans E

      Supposons que tout entier < k soit dans E

      Soit l'entier k, on peut le supposer au moins égal à 2 ( les autres cas sont réglés dans la base) et donc k-2 est en entier qui par hypothèse de récurrence est dans E, donc par définition de E, k est lui aussi dans E.

 

Le schéma est libre : 0et 1 sont dans la base et ne peuvent être le résultat de la règle. Tout entier >=2 peut etre fabriqueé par LA règle appartir de n-2 uniquement

 

L'ensemble F est réduit au nombre 0, ce qui se voit aisément par induction structurelle sur F. Le schéma n'est pas libre 0 est dans la base et peut etre engendré par la règle

 

L'ensemble G, est égal au sous ensemble de N formé des entiers qui sont égaux à une puissance de 2 moins un. Notons G' ce sous-ensemble.

      Clairement G est inclus dans G' par induction structurelle ( il suffit de vérifier que 1 = 2-1 et que si n=2^k-1 alors 2n+1 =2(2^k-1)+1 =2^k+1-1).

      Réciproquement, on peut montrer que G' est inclus dans G , en montrant par récurrence sur k que 2^k-1 est dans G

      Si k=1, c'est vrai .

      Supposons le résultat vrai pour k,  soit l'entier 2^k+1-1, par hypothèse de récurrence l'entier 2^k-1 est dans G, donc définition de G, il est de même de 2(2^k-1)+1 =2^k+1-1

 

Le schéma est libre.

 

 

L'ensemble H est égal à N

      H est inclus dans N par induction structurelle

      N est inclus dans H

      Montrons par récurrence sur k que k appartient à H

      Si k=0, c'est vrai car 0 est dans la base de H

      Soit k un entier non nul, supposons que tous les entiers inférieur à k soit dans H.

      Si k est pair, k=2k', et k'<k, donc par hypothèse de récurrence k' est dans H, donc par définition de H, k=2k' est aussi dans H

Si k est impair, k=2k'+1, et par hypothèse de récurrence k' est dans H, donc par définition de H, k=2k'+1 est aussi dans H

Le schéma n'est pas libre tel que car n est dans la base et est aussi résultat de la règle un appliqué à n=0. On peut modifier le schéma pour le rendre libre :

Règles Si n non nul est dans H, alors 2*n est dans H

 

 

2)      Pour donner une définition inductive de la fonction n modulo 2, on peut utiliser le fait que N=E .

On définira alors la fonction modulo 2 par

  0 mod 2 = 0

                          1 mod 2 = 1

                        n+2 mod 2 = n mod 2

 

Ce qui pourrait se programmer sous la forme

Public int mod2 (int n) {

            (if n==0 | n==1)  {return n}

                                   else return (mod2(n-2))}

}

 

     Pour définir n / 2 , on peut aussi utiliser N=E,

            On définira alors la fonction division entière par deux par

    0/2 =0

                                      1/2  =0

                                     (n+2)/2 = n/2 +1

 

Ce qui pourrait se programmer sous la forme

Public int div2 (int n) {

            (if n==0 | n==1)  {return 0}

                                   else return (div(n-2)+1 )}

}

 

 

     Pour définir la fonction écriture en base deux de n, on peut utilise le fait que N=H,

            On définira alors a fonction écriture en base deux  par

                                   Ecriture (0)=0

                                   Si n>0 Ecriture (2n)=Ecriture(n).0

                                   Si n >0, Ecriture(2n+1)=Ecriture(n).1

                                               Ecriture(1)=1

 

 

           

 

     

 

 

 

 

63.  Définir inductivement les fonctions de N² dans N :

Addition de deux entiers

Multiplication de deux entiers

Calcul de mⁿ.

Add(0,0=0

Add(n+1,0)=n+1

Add(m,n+1)=Add(m,n)+1

public int add (int m, int n) {

            if (n==0) return m

                        else return add (m,n-1)+1

}

Mult(0,0)=0

Mult(n+1,0)=0

Mult(m,n+1)=Mult(m,n)+m

public int mult (int m, int n) {

            if (n==0) return 0

                        else return mult (m,n-1)+m

}

Puiss(0,0)=0

Puiss(n+1,0)=1

Puiss(m,n+1)=Puiss(m,n)*m

public int puiss (int m, int n) {

            if (n==0) {if (m==0) return 0 else return 1}

                        else return puiss (m,n-1)*m

}

64.  Définir inductivement la fonction  m de  A* ----> A* telle que

m(x1x2…xn)=xn …x2x1

 

Base   

            Règle   Si

Preuve : Montrons par induction structurelle sur  A* que

                                              

            Base :

            Supposons , alors m(am)= m(m)a=m~a=(am)~

 

 

65.  Exercice 28

Définir inductivement la fonction

w : A*x A---->N,  w(m,c)=  |m|_c

 

Base               

            Règles 

                                  

 

Preuve : Immédiate par induction structurelle sur A*

 

 

 

66.  Définir inductivement la fonction

val : {0,1}*---->N, 

 

val(m)=  entier représenté par m

val: {0,1}*---->N

 

            Base                val()=0

            Règles  val(m0)=2*val(m)

                                   val(m1)=2*val(m)+1

 

 

 

67.  Exercice 30

Définir inductivement la fonction

s: {0,1}*x{0,1}*---->N, s x,y)=val(x)+val(y)

 

s: {0,1}*x{0,1}*---->N,   s(x,y)=x+y

 

            Base                s(m,e)=val(m)

            Règles  s (m,m')= s (m',m)

                                   s (mi,m'j)=2* s (m,m')+i+j

 

 

68.  Définir inductivement la fonction

S: {0,1}*x{0,1}*---->{0,1}*, S(x,y) un  mot binaire qui correspond à l'entier  val(x)+val(y)

 

 

Dans cette question, on voit la somme comme ayant son résultat  dans les mots binaires  (on ne dispose donc pas de la multiplication et de l'addition).

 

            Base                S(e,e)=e,

                                   S(e,0)=0;

                                   S(e,1)=1;

 

            Règles  S(u0,v0)=S(u,v)0

                                   S(u0,v1)=S(u,v)1

                                   S(u,v)=S(v,u)

                                   S(u0,e)=S(u,e)0

                                   S(u1,e)=S(u,e)1

                                   S(u1,v1)=S(u,S(v,1))0

Preuve :

 

Si A est un alphabet,  alors A* x A* peut se définir par le schéma inductif libre suivant :

            Base               

            Règles

                                  

                                  

(la preuve de cette définition et de sa non-ambiguïté est laissée en exercice pour le lecteur).

La définition de S se prouve par induction structurelle sur A* x A.

 

 

 

 

69.  Définir inductivement les fonctions longueur d’une liste concaténation de  deux listes, ajout_en_fin d’un élément à une liste et miroir d’une  liste. Donner aussi un code récursif.

Définir une fonction inductive qui teste si un élément appartient à une liste

 

Corrigé

longueur(liste_vide)=0

longueur(cons(a,l))=longueur(l)+1

 

concat(liste_vide,l)=l

concat(cons(a,l’),l)=cons(a,concat(l’,l))

 

ajout_en_fin(liste_vide,e)= cons(e, liste_vide)

ajout_en_fin(cons(a,l),e)=cons(a,ajout_en_fin(l,e)

 

miroir(liste_vide)=liste_vide

miroir(cons(a,l))=ajout_en_fin(miroir(l),a))

 

 

 

 

70.  On suppose que les éléments de la liste sont des entiers. Ecrire une fonction inductive qui a une liste associe

la somme de ses éléments

la sous liste de ses éléments pairs

la liste où tous les éléments ont été augmentés de un

 

 

71.  Combien y a-t-il d’arbres binaires ayant 5 noeuds?Un arbre binaire est saturé si tout noeud à 0 ou 2 fils. Donnez une définition inductive des arbres binaires saturés.Combien y a-t-il d’arbres binaires saturés ayant 5 noeuds?

 

72.  On définit l'ordre d'un arbre comme étant son  nombre de sommets, la taille d'un  arbre comme étant son nombre d’arêtes.Donner une définition inductive de ces 2 fonctions.Prouver que si T est un arbre non vide, alors taille(T) = ordre(T)-1