[PDF] LIFLC – Logique classique TD2 – Induction

View - Download LIFLC – Logique classique TD2 – Induction

Previous PDF

Next PDF

LIFLC - Logique classique

TD2 - Induction

Licence informatique UCBL - Automne 2017-2018

Les (parties d") exercices noté(e)s avec†sont plus difficiles.

Exercice 1 : Ensembles inductifs

SoitEetFdeux ensembles. Expliquer quels sont les ensembles inductifs définis à partir des 3 ensembles de règles suivants. Expliquer les différences entre ces trois ensembles. 1.

Ensemble N

-leafN?N si n1?N,n2?Net sie?EalorsnodeN(n1,e,n2)?N 2.

Ensemble L

si e?E, alorsleafL(e)?L si n1?Letn2?LalorsnodeL(n1,n2)?L 3.

Ensemble LH

si e?EalorsleafLH(e)?LH si n1?LH,n2?LHetf?F, alorsnodeLH(n1,f,n2)?LH Exercice 2 : Ensemble inductif des arbres binaires de recherche 1. Donner une définition pa rinduction de l"ensemble BinEdes arbres binaires contenant des éléments deE. On souhaite avoir une représentation d"arbre vide dansBinE. 2. Définir la fonction récu rsiveelementsqui renvoie l"ensemble des éléments deEcontenus dans un arbre binaire de recherche. On commencera par donner la signature (domaine et co-domaine) de cette fonction. 3. Donner une définition pa rinduction de l"en sembleBinRechEdes arbres binaires de recherche contenant des éléments deE. 4.

Définir la fonction récursive plusPetitElementqui renvoie le plus petit élément d"un arbre

binaire de recherche

1. Dans le cas où un tel élément n"existe pas, la fonction reverra la valeur

spéciale. On commencera par donner la signature de cette fonction. 5. Montrer que la fonction plusPetitElementest correcte. Pour cela, montrer par induction surBinEque : soitplusPetitElement(a) =min(elements(a)), soitelements(a) =∅et

plusPetitElement(a) =.1. on souhaite ici que la complexité de la fonction soit linéaire dans la hauteur de l"arbre

1 Exercice 3 : Plus petit ensemble stable par des règles de constructions† SoitEun ensemble. On considère les deux règles de construction de listes suivantes : [ ]est un eliste (on note cette règle R1) si l?est une liste et sie?E, alorscons(e,l?) est une liste (on note cette règleR2) SoitFun ensemble tel qu"il admet au moins un sous-ensembleGstable par ces règles de construction (i.e.[]?Get sie?Eetl??G, alorscons(e,l?)?G). Montrer qu"il existe un unique plus petit (au sens de l"inclusion) sous-ensemble deFstable par ces règles de construction.

Indice : considérer l"intersection de tous les sous-ensembles deFstables par ces règles de construc-

tion. Exercice 4 : Ordre bien fondé sur un ensemble inductif†

SoitEun ensemble. On considère l"ensemble inductif des listesListEconstruit à partir des règles

suivantes : [ ]est un eliste si l?est une liste et sie?E, alorscons(e,l?) est une liste Soit la relation binaireCdéfinie surListE×ListEparl?Clsi et seulement si on peut trouvere?E a.consest injective; b. qu"il n"existe pas de liste let d"élémentetels que [] =cons(e,l). Indice : On pourra montrer par induction que pour toute listel, il n"existe pas de suite infinie

Corrections

Solution de l"exercice 1

L"objectif de l"exercice est de faire travailler les étudiants afin qu"ils se construisent une intui-

tion de ces structures. On peut donner des exemples, dessiner les arbres au tableau, etc. Quelques exemples de remarques/différences : Les trois ensemble ssont des va riationsd"a rbresbinaires.

Seul Npermet d"avoir un arbre videleafN.

-Nstocke les valeurs dans des noeuds internes,Ldans les feuilles etLHdans les deux, mais les valeurs sont issues d"ensembles différents. En p renantLH avec Esingleton, on peut encoderNsur les éléments deF(i.e.on peut construire un isomorphisme entreLH(E,F) etN(F)). Comme exemple d"application d eLH(E,F), on peut prendreE=NetF={+,×}pour représenter des expressions arithmétiques.

Solution de l"exercice 2

1. c"est l"en sembleNde l"exercice 1. L"ensembleBinEest le plus petit ensemble tel que : -?BinE

Si e?E,a1?BinEeta2?BinEalorsnode(a1,e,a2)?BinE.

2.elements:BinE→ P(E)

elements(a) =?∅sia= {e} ?elements(a1)?elements(a2) sia=node(a1,e,a2) Plusieurs erreurs sur le type à anticiper, commeelements:BinE→(E). 3. L"ensemble BinRechEest le plus petit ensemble tel que : -?BinRechE Si les conditions suivantes sont toutes vérifiées -e?E, -a1?BinRechE, -a2?BinRechE, soit e≥Emax(elements(a1)), soita1=, alorsnode(a1,e,a2)?BinRechE. Remarque :BinRechE?BinEcarBinEest stable par ces règles. On utiliser cette remarque pour proposer une définition alternative équivalente deBinRechE:

BinRech

E={t?BinE|sit=node(a1,e,a2) alors

(e≥Emax(elements(a1) oua1=) 4. plusPetitElement:BinE→E? {} plusPetitElement(a) =? ?sia= esia=node(a1,e,a2) eta1= plusPetitElement(a1) sia=node(a1,e,a2) eta1?= 5. On m ontrepa rinduction et pa rcas sur aque soitplusPetitElement(a) =min(elements(a)), soitelements(a) =∅etplusPetitElement(a) =. Si a=, alors il suffit de remarquer que, par définition,elements() =∅ etplusPetitElement() =.

Supp osonsa=node(e,a1,a2).

Par induction, soitplusPetitElement(a1) =min(elements(a1)), soitelements(a1) =∅ etplusPetitElement(a1) =. et on a donce=min(elements(a2)? {e} ? ∅) =min(elements(a)). et définitione≥Emax(elements(a1)≥Emin(elements(a1)), doncmin(elements(a1)) = min(elements(a1)?elements(a2)? {e}) =min(elements(a)), et donc plusPetitElement(a) =plusPetitElement(a1) =min(elements(a1)) =min(elements(a)).

Solution de l"exercice 3

SoitFstablel"ensemble des sous-ensembles deFqui sont stables par les règles de construction de listes. SoitH=?Fstablel"intersection de tous les ensembles dansFstable. On peut remarquer que : [ ]?Hcar la première règle de constructionR1impose que tous les éléments deFstable contiennent [], et donc il en est de même pour leur intersection. Soit l??Hete?E. SoitG?? Fstablequelconque. On aH?G?, doncl??G?. ParR2, on en déduit quecons(e,l?)?G?. Donccons(e,l?)??Fstable. Hest donc stable par{R1,R2}, doncH? Fstable. Comme c"est l"intersection de tous les éléments deFstable, il est plus petit que tous les autres et il a été défini de manière unique.

Solution de l"exercice 4

Preuve de bonne fondation :

P ar(b.), il n"existe pas de liste lC[]. Donc il n"existe pas de suite infinie décroissante com- mençant par [].

Supp osonsque l=cons(e,l?).

Hypothèse d"induction surl?: il n"existe pas de suite infinie strictement décroissante commen-

devrait être une suite infinie strictement décroissante, ce qui est impossible par l"hypothèse

1. Il existe u nesuite l1,...,lk,...,lm, telle queliCli+1,l1=lm=ietlk=l?. 3. Comme consest injective, sil???? {l1,...,lm-1}, il existe un uniquel??et un uniqueetel quel??=cons(e,l??). On peut alors remarquer que dans ce casl???? {l1,...,lm-1}. 4. Considérons l"ensemble List?E=ListE\ {l1,...,lm-1}. (a) [ ]n"étant pa sdans {l1,...,lm-1}, []?List?E. (b) Soit l???List?E. CommeList?E?ListE, on al???ListEet donc pour toute?E, cons(e,l??)?ListE. Or par ce qui précède, sicons(e,l??)? {l1,...,lm-1}, alorsl??? {l1,...,lm-1}, ce qui contreditl???List?E. Donccons(e,l??)?ListE\{l1,...,lm-1}= List ?E. DoncList?Eest stable par les règles de construction de liste. 5. Or ListEest le plus petit ensemble stable par ces règles etList?E?ListE, ce qui est une contradiction. 6.

Donc le cas l?=l?est impossible.

quotesdbs_dbs41.pdfusesText_41

[PDF] propulsion fusée quantité de mouvement

[PDF] propulsion par réaction

[PDF] force de pression sur une paroi courbe

[PDF] force de pression sur une paroi plane tp

[PDF] force de pression sur une paroi inclinée

[PDF] force hydrostatique sur une surface courbe

[PDF] force de poussée hydrostatique

[PDF] force hydrostatique appliquée sur une paroi verticale plane

[PDF] quelle valeur ajoutée pensez vous pouvoir apporter

[PDF] décrivez votre personnalité exemple

[PDF] force de proposition synonyme

[PDF] force de proposition définition

[PDF] brochure kadjar pdf

[PDF] brochure kadjar france

[PDF] jantes alliage 19 extreme