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

Formulaires, étapes clés de la méthode pour chaque thème et 8 exercices, avec les corrigés complets à la fin.

Nouveaux exercices Retour au cours

Dans la fenêtre d’impression, choisissez « Enregistrer au format PDF » pour garder une copie sur votre appareil.

1Formules et méthodes

Logique propositionnelle et preuves

Lignes d’une table de vérité: 2ⁿ
Implication: p → q ≡ ¬p ∨ q ≡ ¬q → ¬p
Implication niée: ¬(p → q) ≡ p ∧ ¬q
Équivalence: p ↔ q ≡ (p → q) ∧ (q → p)
De Morgan: ¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬q
Lois de distributivité: p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r), p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
Quantificateurs niés: ¬∀x P(x) ≡ ∃x ¬P(x), ¬∃x P(x) ≡ ∀x ¬P(x)
Modus ponens, modus tollens: p → q, p ⊢ q; p → q, ¬q ⊢ ¬p

Méthode

Comptez les variables distinctes : la table de vérité a 2ⁿ lignes, la première avec toutes les variables à 1.
Donnez à chaque sous-formule sa propre colonne et remplissez les colonnes de l’intérieur vers l’extérieur.
Appliquez la règle de chaque connecteur : → n’est 0 que pour 1 → 0, ↔ vaut 1 quand les deux côtés sont égaux.
Pour des équivalences, comparez les colonnes finales ligne par ligne ; pour un raisonnement, regardez seulement les lignes où toutes les prémisses valent 1.
Pour nier un énoncé quantifié, faites passer ¬ vers l’intérieur, échangez ∀ et ∃, et niez la formule intérieure.

Ensembles, relations et fonctions

Deux ensembles: |A ∪ B| = |A| + |B| − |A ∩ B|
Trois ensembles: |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|
Différence et complémentaire: A − B = A ∩ B′, |A′| = |U| − |A|
Ensemble des parties et produit: |𝒫(A)| = 2^|A|, |A × B| = |A|·|B|
Sous-ensembles de taille k: C(n, k) = n!/(k!(n − k)!)
Fonctions A → B: nᵐ; injective n!/(n − m)!; surjective Σ (−1)ᵏ C(n, k)(n − k)ᵐ
Relations sur n éléments: 2^n²; reflexive 2^{n² − n}; symmetric 2^n(n+1)/2
Composition: (g ∘ f)(x) = g(f(x))

Méthode

Dessinez un diagramme de Venn et décidez région par région ce qui appartient à l’expression ensembliste.
Pour les problèmes de dénombrement, remplissez les régions du centre vers l’extérieur : tous les ensembles, puis les paires, puis les ensembles seuls, puis l’extérieur.
Utilisez le principe d’inclusion-exclusion comme vérification : |A ∪ B| = |A| + |B| − |A ∩ B|.
Pour une relation, testez chaque propriété sur chaque paire et donnez un contre-exemple quand elle échoue.
Pour une fonction, comptez les flèches qui arrivent à chaque élément de B : au plus une signifie injective, au moins une surjective.

Théorie des graphes

Lemme des poignées de main: Σ deg(v) = 2|E|
Graphes complets: |E(K_n)| = n(n − 1)/2, |E(K_m,n)| = m·n
Graphe régulier: |E| = n·k/2
Arbre et forêt: |E| = n − 1, |E| = n − c
Feuilles d’un arbre: L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Euler: circuit : tous les degrés pairs ; chemin : exactement 2 degrés impairs
Circuits hamiltoniens dans K_n: (n − 1)!/2
Mise à jour de Dijkstra: d(v) = min(d(v), d(u) + w(u, v))
Marches de longueur L: (Mᴸ)_ij

Méthode

Notez le degré de chaque sommet ; la somme des degrés vaut deux fois le nombre d’arêtes.
Pour les questions d’Euler, vérifiez que le graphe est connexe et comptez les sommets de degré impair.
Pour les arbres, utilisez n − 1 arêtes et le lemme des poignées de main.
Pour Dijkstra, tenez un tableau des distances provisoires et fixez à chaque tour le sommet non fixé de plus petite distance.
Pour un arbre couvrant minimal, triez les arêtes par poids et sautez toute arête qui ferme un cycle (Kruskal), ou faites croître un arbre à partir d’un sommet de départ (Prim).

Théorie des nombres et arithmétique modulaire

Division avec reste: a = q·n + r, 0 ≤ r < n
Euclide: gcd(a, b) = gcd(b, a mod b)
Plus petit commun multiple: lcm(a, b) = a·b/gcd(a, b)
Inverse: a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
Congruence linéaire: a·x ≡ b → x ≡ a⁻¹·b (mod n)
Indicatrice d’Euler: φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
Fermat: aᵖ⁻¹ ≡ 1 (mod p)
RSA: n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n

Méthode

Réduisez d’abord chaque nombre modulo n ; les restes sont compris entre 0 et n − 1.
Pour un pgcd, divisez plusieurs fois avec l’algorithme d’Euclide ; le dernier reste non nul est le pgcd.
Pour un inverse, appliquez l’algorithme étendu et gardez le coefficient de a ; ajoutez n s’il est négatif.
Résolvez a·x ≡ b en multipliant par a⁻¹ ; combinez deux congruences en écrivant x = r₁ + m₁k.
Pour les puissances, écrivez l’exposant en binaire et élevez au carré à répétition ; en RSA, d = e⁻¹ mod φ(n) avec φ(n) = (p − 1)(q − 1).

2Exercices

1.Logique propositionnelle et preuvesMoyen

Dans combien des 8 lignes de sa table de vérité (a → ¬(c ∨ b)) ∧ ¬(¬(b ∧ c) → ¬a) est-elle vraie ? Appelez ce nombre N.

(a → ¬(c ∨ b)) ∧ ¬(¬(b ∧ c) → ¬a)

N =

2.Logique propositionnelle et preuvesDifficile

Quel énoncé est équivalent à ¬∀x F(x), la négation étant passée complètement à l’intérieur ? Cliquez dessus.

¬∀x F(x)

1∀x F(x)
2∀x ¬F(x)
3∃x F(x)
4∃x ¬F(x)

3.Ensembles, relations et fonctionsMoyen

La relation R sur {1, 2, 3} est dessinée comme un graphe orienté (une boucle signifie (x, x) ∈ R). Exactement une des quatre propriétés est vérifiée. Cliquez dessus.

R = {(1, 1), (2, 1), (2, 2), (3, 2)}

1réflexive
2symétrique
3antisymétrique
4transitive

4.Ensembles, relations et fonctionsDifficile

Sur X = {1, 2, …, 10}, la relation R est vérifiée quand x ≡ y (mod 4). Combien de couples ordonnés R contient-elle ? Appelez ce nombre |R|.

X = {1, …, 10}x R y ⟺ 4 | (x − y)

|R| =

5.Théorie des graphesMoyen

Un graphe connexe a 15 sommets et 20 arêtes. Combien d’arêtes k faut-il retirer pour obtenir un arbre couvrant ?

|V| = 15|E| = 20

k =

6.Théorie des graphesDifficile

Trouvez le poids total W d’un arbre couvrant minimal du graphe pondéré.

|V| = 5|E| = 7

W =

7.Théorie des nombres et arithmétique modulaireMoyen

Trouvez l’inverse de 66 modulo 71 : le nombre x avec 0 < x < 71 et 66·x ≡ 1 (mod 71).

a = 66n = 71

66⁻¹ mod 71 =

8.Théorie des nombres et arithmétique modulaireDifficile

Combien de solutions N a 15x ≡ 63 (mod 66) dans {0, 1, …, 65} ?

15x ≡ 63 (mod 66)

N =

3Solutions

1.Logique propositionnelle et preuves

Réponse: N = 1

Tables de vérité : une formule à n variables distinctes a 2ⁿ lignes, une pour chaque combinaison de valeurs de vérité (1 = vrai, 0 = faux). Travaillez de l’intérieur vers l’extérieur et donnez à chaque sous-formule sa propre colonne. ¬a inverse la valeur ; a ∧ b vaut 1 seulement quand les deux valent 1 ; a ∨ b vaut 0 seulement quand les deux valent 0 ; a → b vaut 0 seulement quand a = 1 et b = 0 ; a ↔ b vaut 1 quand les deux côtés sont égaux.

Table de vérité ligne par ligne

a = 1, b = 1, c = 1: c ∨ b = 1, ¬(c ∨ b) = 0, a → ¬(c ∨ b) = 0, b ∧ c = 1, ¬(b ∧ c) = 0, ¬a = 0, ¬(b ∧ c) → ¬a = 1, ¬(¬(b ∧ c) → ¬a) = 0, (a → ¬(c ∨ b)) ∧ ¬(¬(b ∧ c) → ¬a) = 0

a = 1, b = 1, c = 0: c ∨ b = 1, ¬(c ∨ b) = 0, a → ¬(c ∨ b) = 0, b ∧ c = 0, ¬(b ∧ c) = 1, ¬a = 0, ¬(b ∧ c) → ¬a = 0, ¬(¬(b ∧ c) → ¬a) = 1, (a → ¬(c ∨ b)) ∧ ¬(¬(b ∧ c) → ¬a) = 0

a = 1, b = 0, c = 1: c ∨ b = 1, ¬(c ∨ b) = 0, a → ¬(c ∨ b) = 0, b ∧ c = 0, ¬(b ∧ c) = 1, ¬a = 0, ¬(b ∧ c) → ¬a = 0, ¬(¬(b ∧ c) → ¬a) = 1, (a → ¬(c ∨ b)) ∧ ¬(¬(b ∧ c) → ¬a) = 0

a = 1, b = 0, c = 0: c ∨ b = 0, ¬(c ∨ b) = 1, a → ¬(c ∨ b) = 1, b ∧ c = 0, ¬(b ∧ c) = 1, ¬a = 0, ¬(b ∧ c) → ¬a = 0, ¬(¬(b ∧ c) → ¬a) = 1, (a → ¬(c ∨ b)) ∧ ¬(¬(b ∧ c) → ¬a) = 1

a = 0, b = 1, c = 1: c ∨ b = 1, ¬(c ∨ b) = 0, a → ¬(c ∨ b) = 1, b ∧ c = 1, ¬(b ∧ c) = 0, ¬a = 1, ¬(b ∧ c) → ¬a = 1, ¬(¬(b ∧ c) → ¬a) = 0, (a → ¬(c ∨ b)) ∧ ¬(¬(b ∧ c) → ¬a) = 0

a = 0, b = 1, c = 0: c ∨ b = 1, ¬(c ∨ b) = 0, a → ¬(c ∨ b) = 1, b ∧ c = 0, ¬(b ∧ c) = 1, ¬a = 1, ¬(b ∧ c) → ¬a = 1, ¬(¬(b ∧ c) → ¬a) = 0, (a → ¬(c ∨ b)) ∧ ¬(¬(b ∧ c) → ¬a) = 0

a = 0, b = 0, c = 1: c ∨ b = 1, ¬(c ∨ b) = 0, a → ¬(c ∨ b) = 1, b ∧ c = 0, ¬(b ∧ c) = 1, ¬a = 1, ¬(b ∧ c) → ¬a = 1, ¬(¬(b ∧ c) → ¬a) = 0, (a → ¬(c ∨ b)) ∧ ¬(¬(b ∧ c) → ¬a) = 0

a = 0, b = 0, c = 0: c ∨ b = 0, ¬(c ∨ b) = 1, a → ¬(c ∨ b) = 1, b ∧ c = 0, ¬(b ∧ c) = 1, ¬a = 1, ¬(b ∧ c) → ¬a = 1, ¬(¬(b ∧ c) → ¬a) = 0, (a → ¬(c ∨ b)) ∧ ¬(¬(b ∧ c) → ¬a) = 0

Compter les lignes de valeur 1

(a → ¬(c ∨ b)) ∧ ¬(¬(b ∧ c) → ¬a): 0, 0, 0, 1, 0, 0, 0, 0

N = 1

Réponse

N = 1

2.Logique propositionnelle et preuves

Réponse: ∃x ¬F(x)

Quantificateurs et raisonnements : ¬∀x P(x) ≡ ∃x ¬P(x) et ¬∃x P(x) ≡ ∀x ¬P(x). Faites passer une négation vers l’intérieur, échangez chaque quantificateur qu’elle traverse, et niez la formule intérieure avec les lois propositionnelles, comme ¬(a → b) ≡ a ∧ ¬b. Un raisonnement est valide quand la conclusion vaut 1 dans toutes les lignes où toutes les prémisses valent 1. Une seule ligne avec des prémisses vraies et une conclusion fausse est un contre-exemple et montre que le raisonnement est invalide.

Faire passer la négation vers l’intérieur

¬∀x F(x) ≡ ∃x ¬F(x)

Réponse

∃x ¬F(x)

Les autres options laissent un quantificateur inchangé, changent l’ordre des quantificateurs, ou nient mal la formule intérieure.

3.Ensembles, relations et fonctions

Réponse: antisymétrique

Relations : une relation R sur un ensemble X est un ensemble de couples ordonnés (x, y). R est réflexive quand (x, x) ∈ R pour tout x de X ; symétrique quand (x, y) ∈ R vient toujours avec (y, x) ∈ R ; antisymétrique quand (x, y) et (y, x) sont tous deux dans R seulement si x = y ; et transitive quand (x, y) et (y, z) dans R imposent (x, z) ∈ R. Une relation d’équivalence est réflexive, symétrique et transitive, et découpe X en classes disjointes.

réflexive

échoue : (3, 3) ∉ R

symétrique

échoue : (2, 1) ∈ R, (1, 2) ∉ R

antisymétrique

est vérifiée

transitive

échoue : (3, 2), (2, 1) ∈ R, (3, 1) ∉ R

Réponse

antisymétrique

4.Ensembles, relations et fonctions

Réponse: |R| = 26

Classes

reste 0: 2

reste 1: 3

reste 2: 3

reste 3: 2

Couples

|R| = 2² + 3² + 3² + 2² = 26

Réponse

|R| = 26

5.Théorie des graphes

Réponse: k = 6

Euler, Hamilton et arbres : un graphe connexe a un circuit eulérien (chaque arête une fois, retour au départ) quand tous les sommets ont un degré pair, et un chemin eulérien qui n’est pas un circuit quand exactement deux sommets ont un degré impair ; le chemin va alors d’un sommet impair à l’autre. Un circuit hamiltonien visite chaque sommet une fois ; K_n en a (n − 1)!/2. Un arbre à n sommets a n − 1 arêtes, et un graphe connexe à m arêtes conserve un arbre couvrant après suppression de m − n + 1 arêtes.

Arêtes d’un arbre couvrant

15 − 1 = 14

Arêtes à retirer

k = 20 − 14 = 6

Réponse

k = 6

6.Théorie des graphes

Réponse: W = 32

Plus courts chemins et arbres couvrants : l’algorithme de Dijkstra fixe un sommet par tour : le sommet non fixé de plus petite distance provisoire. Sa distance est alors définitive, et chaque voisin v reçoit d(v) = min(d(v), d(u) + w(u, v)). L’algorithme de Kruskal construit un arbre couvrant minimal en prenant les arêtes de la plus légère à la plus lourde et en sautant toute arête qui fermerait un cycle ; l’algorithme de Prim fait croître un arbre à partir d’un sommet de départ en ajoutant toujours l’arête la plus légère qui en sort. Un arbre couvrant à n sommets a n − 1 arêtes.

Algorithme de Kruskal

AB (3): prise

CE (6): prise

AC (9): prise

BE (10): sautée, ferme un cycle

BC (11): sautée, ferme un cycle

BD (14): prise

Poids total

W = 3 + 6 + 9 + 14 = 32

Réponse

W = 32

7.Théorie des nombres et arithmétique modulaire

Réponse: 66⁻¹ mod 71 = 14

Inverses et congruences : a a un inverse modulo n exactement quand pgcd(a, n) = 1. L’algorithme d’Euclide étendu écrit 1 = s·n + t·a, et alors a⁻¹ ≡ t (mod n). Une congruence a·x ≡ b (mod n) avec pgcd(a, n) = 1 a pour solution x ≡ a⁻¹·b. Deux congruences x ≡ r₁ (mod m₁) et x ≡ r₂ (mod m₂) à modules premiers entre eux ont une solution modulo m₁·m₂ (théorème des restes chinois). L’indicatrice d’Euler φ(n) compte les nombres de 1 à n premiers avec n : φ(n) = n·∏(1 − 1/p).

Algorithme d’Euclide étendu

Chaque reste r s’écrit r ≡ t·66 (mod 71).

r = 71, t = 0

r = 66, q = 1, t = 1

r = 5, q = 13, t = −1

r = 1, q = 5, t = 14

Inverse

1 ≡ 14·66 (mod 71)

x = 14

vérification: 66·14 = 924 = 13·71 + 1

Réponse

66⁻¹ mod 71 = 14

8.Théorie des nombres et arithmétique modulaire

Réponse: N = 3

Diviser par le pgcd

gcd(15, 66) = 3

5x ≡ 21 (mod 22)

Résoudre la congruence réduite

5⁻¹ ≡ 9 (mod 22) → x ≡ 13 (mod 22)

Solutions modulo 66

x ∈ {13, 35, 57}

N = 3

Réponse

N = 3

ExamProblems · examproblems.com/courses/discrete-mathematics