Remerciez-le!

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

INFO 1 – Semestre 1 Année 2012/2013 IUT de LAVAL Département Informatique - Pol

INFO 1 – Semestre 1 Année 2012/2013 IUT de LAVAL Département Informatique - Polycopié de cours - Mathématiques Discrètes Yann Walkowiak 1 http://www.univ-lemans.fr/~ywalko yann.walkowiak@univ-lemans.fr 1. Merci à Patricia Everaere et Serge Iovleﬀdont les documents m’ont aidé à rédiger ce cours. Table des matières 1 Théorie des ensembles 1 1.1 Ensembles et opérations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Propriétés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Application entre deux ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4 Cardinal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.5 Miscellannées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2 Logique 13 2.1 Logique propositionnelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 Prédicats et quantiﬁcateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.3 Théorèmes et démonstrations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3 Relations sur un ensemble 21 3.1 Déﬁnition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2 Opérations sur les relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.3 Propriétés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.4 Relation d’équivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.5 Relation d’ordre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4 Théorie des graphes : introduction 31 4.1 Graphes et modélisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.2 Graphe orienté . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.3 Graphe non orienté . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.4 Graphe partiel et sous-graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.5 Théorème des poignées de mains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.6 Chemin, chaîne, circuit et cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.7 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 5 Arithmétique 39 5.1 Divisibilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 5.2 Nombres premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.3 Équation diophantienne ax + by = c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 i ii Table des matières 5.4 Congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 5.5 Cryptographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 6 Mais qui sont ces gens ? 51 Bibliographie 57 Partie 1 Théorie des ensembles “Nul ne doit nous exclure du Paradis que Cantor a créé” (David Hilbert) 1.1 Ensembles et opérations 1.1.1 Déﬁnition - Exemples Il est très délicat de donner une déﬁnition rigoureuse de ce qu’est un ensemble. Nous nous contenterons d’une déﬁnition intuitive bien suﬃsante pour nos besoins. Déﬁnition 1.1.1. Un ensemble est une collection d’objets appelés éléments de l’ensemble. On note x ∈E (et on dit “x appartient à E”) si x est un élément de E. Exemple 1.1.1. 1. l’ensemble N des entiers naturels N = {0, 1, 2, 3, . . .} (7 ∈N, −2 / ∈N) 2. l’ensemble Z des entiers relatifs (−2 ∈Z, 1 3 / ∈Z) 3. l’ensemble Q des nombres rationnels ( 1 3 ∈Q, √ 2 / ∈Q) 4. l’ensemble R des nombres réels ( √ 2 ∈Q) Un ensemble peut être représenté par une patate, plus joliment appelée diagramme d’Euler 1 Exemple 1.1.2. l’ensemble E = {a, b, g, u, i, m} est représenté par le diagramme d’Euler de la ﬁgure 1.1. On a l’habitude de noter les ensembles avec des capitales majuscules et les éléments d’un ensemble avec des minuscules. Un ensemble peut être déﬁni en extension, c’est-à-dire en donnant la liste de ses éléments, ou en compréhension, c’est-à-dire en donnant une propriété vériﬁée par ses éléments (et uniquement par ses éléments). Exemple 1.1.3. 1. E = {2, 4, 6} est donné en extension 2. E = {x ∈N | x est pair et 1 ≤x ≤7} est le même ensemble donné en compréhension. Déﬁnition 1.1.2. Il existe un ensemble ne contenant aucun élément. On appelle cet ensemble “ensemble vide” et on le note ∅. 1. Leonhard Paul Euler, voir chapitre 6 page 51 1 2 Théorie des ensembles Figure 1.1 – Diagramme d’Euler de l’ensemble E Il y a une inﬁnité de façons de décrire un ensemble donné, la plus simple est souvent la meilleure ! {x ∈N | x + 1 = 0} uploads/Philosophie/ main-cours.pdf