M1201 - Mathématiques discrètesTD 3 - Relation binaire de E vers F

2020/2021 - A. RIDARD

Exercice 1.On considère l’emploi du temps suivant :

Lundi Mardi Mercredi Jeudi Vendredi

Algorithmique BDD Communication Algorithmique Systèmes et RéseauxProgrammation Programmation Algorithmique Programmation Anglais

BDD Systèmes et Réseaux MathématiquesMathématiques Anglais Économie

1. Modéliser cet emploi du temps à l’aide d’une relation binaire et la représenter graphiquement.

2. Proposer un nouvel emploi du temps, en évitant les créneaux grisés, modélisable cette fois à l’aide d’une fonction.

Exercice 2.Soit I un intervalle de R et f : I →R une application.Montrer que si f est strictement croissante [1], alors elle est injective.

Exercice 3.On considère E ,F deux ensembles et f : E → F une application.

1. Étant données A, A′ deux parties de E , montrer : A ⊂ A′ =⇒ f (A) ⊂ f (A′).

2. Étant données B ,B ′ deux parties de F , montrer : B ⊂ B ′ =⇒ f −1(B) ⊂ f −1(B ′).

Exercice 4.On considère E ,F deux ensembles et f : E → F une application.

1. Soit A, A′ deux parties de E . Montrer :

(a) f (A∪ A′) = f (A)∪ f (A′)(b) f (A∩ A′) ⊂ f (A)∩ f (A′)

2. Montrer :(∀A, A′ ⊂ E , f (A∩ A′) = f (A)∩ f (A′)

)⇐⇒ f injective

3. Soit B ,B ′ deux parties de F . Montrer :

(a) f −1(B ∪B ′) = f −1(B)∪ f −1(B ′)(b) f −1(B ∩B ′) = f −1(B)∩ f −1(B ′)

Exercice 5.On considère E ,F deux ensembles et f : E → F une application. Montrer :

1. ∀A ⊂ E , A ⊂ f −1(

f (A))

2. ∀B ⊂ F, f(

f −1(B))⊂ B

3.(∀A ⊂ E , A = f −1

(f (A)

))⇐⇒ f injective

4.(∀B ⊂ F, f

(f −1(B)

)= B)⇐⇒ f surjective

[1]. ∀x, y ∈ I , x < y =⇒ f (x) < f (y)

1

Exercice 6.Montrer que Z est dénombrable en considérant l’application f : N −→ Z

n 7−→{ n

2 si n est pair−n+1

2 sinon

Exercice 7.On considère l’alphabet Σ= {A,B , . . . , Z } et le langage L =Σ4 constitué des mots de longueur 4.Calculer le cardinal de la partie formée des mots :

1. contenant les lettres I , N , F et O

2. du langage régulier dénoté par IU T (A|B | . . . |Z ) que l’on notera plus simplement IU TΣ

3. du langage régulier dénoté par ΣARΣ

4. du langage régulier dénoté par Σ3Z

5. du langage régulier dénoté par IU TΣ|ΣARΣ

6. du langage régulier dénoté par Σ3Z |ΣARΣ

7. contenant 4 lettres distinctes

8. contenant 4 lettres distinctes dont Z

9. contenant 4 lettres distinctes dont A et R

10. contenant 4 lettres distinctes dont I , U et T

11. contenant exactement 3 lettres distinctes

12. contenant la lettre Z

13. contenant les lettres I , U et T

Exercice 8.Démontrer les propriétés de la partie III. Isomorphisme du cours d’algèbre linéaire.

1. Image d’une famille génératrice par une application linéaire surjective

2. CNS d’injectivité

3. Image d’une famille libre par une application linéaire injective

4. Linéarité de la bijection réciproque

5. Caractérisation « efficace » d’un isomorphisme

2