Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

MATHÉMATIQUES DISCRÈTES Mathieu SABLIK Table des matières I Introduction à la t

MATHÉMATIQUES DISCRÈTES Mathieu SABLIK Table des matières I Introduction à la théorie des ensembles 5 I.1 Notions sur les ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 I.1.1 Construction par extension et compréhension . . . . . . . . . . . . . . . . . . 5 I.1.2 Principales règles de fonctionnement . . . . . . . . . . . . . . . . . . . . . . . 5 I.1.3 Représentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 I.2 Sous-ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 I.2.1 Inclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 I.2.2 Ensemble des parties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 I.3 Opérations sur les ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 I.3.1 Union et Intersection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 I.3.2 Différence et complémentaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 I.3.3 Produit cartésien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 II Notions sur les langages 9 II.1 Exemples de problèmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 II.2 Mots sur un alphabet ﬁni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 II.2.1 Un peu de vocabulaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 II.2.2 Propriété d’équidivisibilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 II.3 Langage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 II.3.1 Déﬁnition et exemples de langages . . . . . . . . . . . . . . . . . . . . . . . . . 11 II.3.2 Opérations sur les langages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 II.3.3 Equations sur les langages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 III Fonctions et applications 13 III.1 Premières notions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 III.1.1 Déﬁnition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 III.1.2 Modes de représentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 III.1.3 Composition de fonction et d’applications . . . . . . . . . . . . . . . . . . . . 16 III.1.4 Applications singulières . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 III.2 Propriétés sur les fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 III.2.1 Injection et surjection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 III.2.2 Bijection et application réciproque . . . . . . . . . . . . . . . . . . . . . . . . . 17 III.3 Quelques classes importantes de fonctions . . . . . . . . . . . . . . . . . . . . . . . . 18 III.3.1 Fonction caractéristique d’un ensemble . . . . . . . . . . . . . . . . . . . . . . 18 III.3.2 Suites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 IV Cardinalité 21 IV.1 Cardinalité des ensembles ﬁnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 IV.1.1 Ensembles de même cardinalité . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 IV.1.2 Cardinal d’un ensemble ﬁni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 TABLE DES MATIÈRES 2 IV.1.3 Principe des tiroirs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 IV.2 Dénombrement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 IV.2.1 Dénombrement et opération sur les ensembles . . . . . . . . . . . . . . . . . . 23 IV.2.2 Arrangements et combinaisons . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 IV.3 Cas des ensembles inﬁnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 IV.3.1 Déﬁnition et premiers exemples d’ensembles dénombrables . . . . . . . . . . 29 IV.3.2 Critères de dénombrabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 IV.3.3 Ensembles non dénombrables . . . . . . . . . . . . . . . . . . . . . . . uploads/Ingenierie_Lourd/ mathematiques-discretes 1 .pdf