Fiche de révision : Mathématiques discrètes

📋 Plan du Cours

1. Implication et logique propositionnelle
2. Notion et représentation des ensembles
3. Opérations ensemblistes
4. Produits et cardinalités finies
5. Relations et classes d’équivalence
6. Ordres et fonctions
7. Algèbre de Boole
8. Numération et codages binaires
9. Arithmétique entière
10. Congruences et chiffrement RSA

📖 1. Implication et logique propositionnelle

🔑 Notions clés & Définitions

• Implication : Logique reliant deux propositions selon la forme « si A alors B », notée $A\Rightarrow B$, où A est la condition suffisante et B la condition nécessaire.
• Équivalence : Une équivalence affirme simultanément $A\Rightarrow B$ et $B\Rightarrow A$, et se note $A\Leftrightarrow B$.

📝 Points essentiels

📌 La réciproque de $A\Rightarrow B$ est $B\Rightarrow A$, tandis que sa contraposée est $\neg B\Rightarrow\neg A$.

💡 Astuce mémo

Implication A ⇒ B, réciproque B ⇒ A, contraposée ¬B ⇒ ¬A

📖 2. Notion et représentation des ensembles

🔑 Notions clés & Définitions

• Ensemble : Collection d’éléments déterminée par ses éléments, et deux ensembles sont égaux s’ils possèdent exactement les mêmes éléments.
• Sous-ensemble : Ensemble B dont tout élément appartient aussi à A.

★ À maîtriser

📌 Un ensemble défini en extension liste exhaustivement ses éléments, tandis qu’un ensemble défini en compréhension sélectionne les éléments vérifiant une propriété dans un ensemble de référence.

Compléments

• Les inclusions usuelles sont $\mathbb N\subset\mathbb Z\subset\mathbb Q\subset\mathbb R\subset\mathbb C$.

💡 Astuce mémo

Appartenance → inclusion → extension ou compréhension

📖 3. Opérations ensemblistes

🔑 Notions clés & Définitions

• Réunion : La réunion de A et B, notée A ∪ B, contient les éléments appartenant à A ou à B.
• Intersection : L’intersection de A et B, notée A ∩ B, contient les éléments appartenant simultanément à A et à B.
• Différence symétrique : La différence symétrique A∆B contient les éléments appartenant à A ou à B mais pas aux deux, et vérifie $A\Delta{}B=(A\cup B)\setminus(A\cap B)$.

📝 Points essentiels

• Les lois de Morgan donnent $\overline{A\cup B}=\overline A\cap\overline B$ et $\overline{A\cap B}=\overline A\cup\overline B$.

💡 Astuce mémo

Union = ou, intersection = et, complémentaire = non

📖 4. Produits et cardinalités finies

🔑 Notions clés & Définitions

• Produit cartésien : Ensemble des couples ordonnés $(a,b)$ tels que a appartient à A et b appartient à B.
• Cardinalité : Nombre d’éléments d’un ensemble fini A.
• Partition : Des sous-ensembles forment une partition de E s’ils recouvrent E et sont deux à deux disjoints.

📝 Points essentiels

📐 Formule — Pour tout ensemble fini E, le nombre de ses sous-ensembles vérifie $|\mathcal P(E)|=2^{|E|}$.

📐 Formule — Pour deux ensembles finis A et B, $|A\cup B|=|A|+|B|-|A\cap B|$.

💡 Astuce mémo

Chaque sous-ensemble reçoit un code binaire → 2^{|E|} sous-ensembles

📖 5. Relations et classes d’équivalence

🔑 Notions clés & Définitions

• Relation binaire : Relation définie par un sous-ensemble G de E × F, avec xRy si et seulement si (x,y) appartient à G.
• Relation d’équivalence : Relation réflexive, symétrique et transitive.
• Relation d’ordre : Relation réflexive, antisymétrique et transitive.

📝 Points essentiels

• Les classes d’équivalence d’une relation d’équivalence forment une partition de l’ensemble considéré.

💡 Astuce mémo

Réflexivité → symétrie → transitivité

📖 6. Ordres et fonctions

🔑 Notions clés & Définitions

• Fonction : Une fonction de E vers F associe à chaque élément de E au plus une image dans F.
• Application : Fonction dont l’ensemble de définition est égal à son ensemble de départ E.

★ À maîtriser

📌 Une application est injective si chaque élément d’arrivée a au plus un antécédent, surjective s’il en a au moins un, et bijective s’il en a exactement un.

Compléments

• Une application bijective possède une application réciproque f⁻¹ vérifiant $f\circ f^{-1}=\operatorname{id}$ et $f^{-1}\circ f=\operatorname{id}$.

💡 Astuce mémo

Injective : au plus un antécédent ; surjective : au moins un ; bijective : exactement un

📖 7. Algèbre de Boole

🔑 Notions clés & Définitions

• Algèbre de Boole : Structure définie sur B={0,1} avec le produit, la somme et la négation, correspondant respectivement à et, ou et non.

★ À maîtriser

• Les éléments neutres sont a+0=a et a·1=a, tandis que les éléments absorbants sont a·0=0 et a+1=1.

• Les lois de Morgan booléennes donnent $\overline{a+b}=\overline a\cdot\overline b$ et $\overline{a\cdot b}=\overline a+\overline b$.

Compléments

📐 Formule — L’implication booléenne se réécrit $a\Rightarrow b=\overline a+b=\overline{a\cdot\overline b}$.

💡 Astuce mémo

0 = faux, 1 = vrai ; · = et, + = ou, barre = non

📖 8. Numération et codages binaires

🔑 Notions clés & Définitions

• Écriture positionnelle : Pour une base b supérieure ou égale à 2, tout entier naturel non nul s’écrit de manière unique comme $a=a_nb^n+\cdots+a_1b+a_0$ avec des chiffres entre 0 et b−1 et a_n non nul.

★ À maîtriser

• Sur 32 bits non signés, on peut coder 2³² nombres, de 0 à 2³²−1, soit de 0 à 4294967295.

• Pour coder un entier négatif a en complément à deux sur n bits, on utilise l’écriture binaire de 2ⁿ+a.

Compléments

• Le nombre décimal 63 possède les écritures (111111)₂, (2100)₃, (223)₅ et (3F)₁₆.

• En décimal codé binaire, chaque chiffre décimal utilise quatre bits, de sorte que 2016 est codé 0010 0000 0001 0110.

💡 Astuce mémo

Base → écriture positionnelle → codage des positifs → compléments

📖 9. Arithmétique entière

🔑 Notions clés & Définitions

• Divisibilité : Un entier a divise un entier b s’il existe un entier m tel que b=am, ce qui se note a|b.
• Nombre premier : Entier strictement positif possédant exactement deux diviseurs positifs : 1 et lui-même.

📝 Points essentiels

• L’algorithme d’Euclide calcule le PGCD en effectuant successivement les divisions euclidiennes jusqu’au dernier reste non nul, qui est le PGCD.

📐 Formule — Le théorème de Bézout affirme qu’il existe des entiers p et q tels que $pa+qb=\operatorname{PGCD}(a,b)$.

• Tout entier strictement supérieur à 1 possède une décomposition unique en produit de facteurs premiers.

💡 Astuce mémo

Divisibilité → PGCD → Bézout → facteurs premiers

📖 10. Congruences et chiffrement RSA

🔑 Notions clés & Définitions

• Congruence : Pour n≥1, deux entiers a et b sont congrus modulo n si n divise a−b, ce qui se note $a\equiv b\ [n]$.

📝 Points essentiels

• Chaque entier est congru modulo n au reste de sa division euclidienne par n, et il existe exactement n classes de congruence modulo n.

📌 La congruence modulo n est compatible avec l’addition, la soustraction, la multiplication et les puissances entières.

📌 Dans Z/nZ, une classe non nulle est inversible si et seulement si son représentant est premier avec n ; sinon elle est un diviseur de zéro ou la classe nulle.

• Pour un nombre premier p et un entier a non multiple de p, le petit théorème de Fermat donne $a^{p-1}\equiv1\ [p]$.

• RSA choisit deux nombres premiers distincts p et q, calcule n=pq et φ(n)=(p−1)(q−1), choisit e premier avec φ(n), puis calcule d inverse de e modulo φ(n).

📐 Formule — Dans RSA, le chiffrement d’un message M donne $C=M^e$ modulo n, puis le déchiffrement calcule $C^d$ modulo n pour retrouver M.

💡 Astuce mémo

Congruence → inversibilité → Fermat/Euler → clés RSA

📊 Tableaux de synthèse

Types de relations

Propriétés des applications