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.
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(Kn)| = n(n − 1)/2, |E(Km,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 Kn
(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
Vous voulez prouver q → (p ∧ r) par contraposée. Quelle implication prouvez-vous à la place ? Cliquez dessus.
q → (p ∧ r)
1¬q → ¬(p ∧ r)
2¬(p ∧ r) → ¬q
3(p ∧ r) → q
4q ∧ ¬(p ∧ r)
2.Logique propositionnelle et preuvesDifficile
Combien des 16 lignes de la table de vérité rendent (a → (¬b ∧ c)) ∨ ((¬d → b) ∧ (d ∧ c)) vraie ? Appelez ce nombre N.
(a → (¬b ∧ c)) ∨ ((¬d → b) ∧ (d ∧ c))
N =
3.Ensembles, relations et fonctionsMoyen
Sur 41 étudiants de première année, 29 ont réussi les mathématiques (M), 17 ont réussi la physique (P) et 12 ont réussi les deux. Combien sont dans exactement un des deux ensembles ?
|U| = 41|M| = 29|P| = 17|M ∩ P| = 12
|(M − P) ∪ (P − M)| =
4.Ensembles, relations et fonctionsDifficile
Combien de relations sur un ensemble de 4 éléments sont à la fois réflexives et symétriques ? Appelez ce nombre N.
|X| = 4
N =
5.Théorie des graphesMoyen
Un arbre a 3 sommets de degré 4, 4 sommets de degré 5, et tous ses autres sommets sont des feuilles (degré 1). Combien de feuilles L a-t-il ?
3 × deg 44 × deg 5
L =
6.Théorie des graphesDifficile
Combien de marches fermées de longueur 3 partent de E et y reviennent ? Une marche peut répéter des sommets et des arêtes. Appelez ce nombre N.
M = matrice d’adjacenceL = 3
N =
7.Théorie des nombres et arithmétique modulaireMoyen
Trouvez le plus petit entier positif x tel que x ≡ 3 (mod 9) et x ≡ 9 (mod 10).
x ≡ 3 (mod 9)x ≡ 9 (mod 10)
x =
8.Théorie des nombres et arithmétique modulaireDifficile
Combien de solutions N a 21x ≡ 27 (mod 87) dans {0, 1, …, 86} ?
21x ≡ 27 (mod 87)
N =
3Solutions
1.Logique propositionnelle et preuves
Réponse: ¬(p ∧ r) → ¬q
Équivalence logique : deux formules sont équivalentes (≡) quand elles ont la même valeur dans chaque ligne de la table de vérité. Une tautologie vaut 1 dans toutes les lignes, une contradiction 0 dans toutes les lignes, et une contingence n’est ni l’une ni l’autre. Lois utiles : De Morgan, ¬(a ∧ b) ≡ ¬a ∨ ¬b et ¬(a ∨ b) ≡ ¬a ∧ ¬b ; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (contraposée) ; ¬(a → b) ≡ a ∧ ¬b ; et les lois de distributivité, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).
Parties de l’implication
a = q, b = p ∧ r
Contraposée
¬b → ¬a = ¬(p ∧ r) → ¬q
Réponse
¬(p ∧ r) → ¬q
La contraposée est équivalente à l’énoncé initial, donc la prouver prouve l’énoncé.
2.Logique propositionnelle et preuves
Réponse: N = 11
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.
Colonnes
¬b; ¬b ∧ c; a → (¬b ∧ c); ¬d; ¬d → b; d ∧ c; (¬d → b) ∧ (d ∧ c); (a → (¬b ∧ c)) ∨ ((¬d → b) ∧ (d ∧ c))
Scinder selon a
a = 1: 3
a = 0: 8
N = 3 + 8 = 11
Réponse
N = 11
3.Ensembles, relations et fonctions
Réponse: |(M − P) ∪ (P − M)| = 22
Ensembles et diagrammes de Venn : A ∪ B contient les éléments de A ou de B (ou des deux), A ∩ B les éléments des deux, A − B les éléments de A qui ne sont pas dans B, et le complémentaire A′ tout ce qui est dans U sans être dans A. Dans un diagramme de Venn, toute expression ensembliste est une réunion de régions, donc dénombre-la région par région. Inclusion-exclusion : |A ∪ B| = |A| + |B| − |A ∩ B|, et |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.
Régions
M ∩ P: 12
M − P: 29 − 12 = 17
P − M: 17 − 12 = 5
(M ∪ P)′: 41 − (17 + 5 + 12) = 7
Réponse
|(M − P) ∪ (P − M)| = 22
Réponse
|(M − P) ∪ (P − M)| = 22
4.Ensembles, relations et fonctions
Réponse: N = 64
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.
Compter les choix libres
N = 26 = 64
Réponse
N = 64
5.Théorie des graphes
Réponse: L = 20
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 ; Kn 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.
Lemme des poignées de main pour un arbre
L + 32 = 2(L + 7) − 2
L = 20
Réponse
L = 20
Raccourci : L = 2 + Σ (d − 2) sur les sommets de degré d ≥ 3.
6.Théorie des graphes
Réponse: N = 2
Degrés : le degré d’un sommet est le nombre d’arêtes qui y aboutissent. Chaque arête a deux extrémités, donc les degrés totalisent deux fois le nombre d’arêtes : Σ deg(v) = 2|E| (le lemme des poignées de main). Le nombre de sommets de degré impair est donc pair. Kn a n(n − 1)/2 arêtes, un graphe k-régulier à n sommets en a nk/2, et un arbre à n sommets a n − 1 arêtes.
Matrice d’adjacence
A: 0 1 1 0 0
B: 1 0 0 1 1
C: 1 0 0 0 1
D: 0 1 0 0 1
E: 0 1 1 1 0
Un pas de plus
(M³)EE = 2·0 + 1·1 + 0·1 + 1·1 + 3·0 = 2
Réponse
N = 2
7.Théorie des nombres et arithmétique modulaire
Réponse: x = 39
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).
Première congruence
x = 3 + 9k
Deuxième congruence
3 + 9k ≡ 9 (mod 10) → 9k ≡ 6 (mod 10)
k ≡ 9·6 ≡ 4 (mod 10)
Résultat
x = 3 + 9·4 = 39
x = 39
vérification: 39 mod 9 = 3, 39 mod 10 = 9
Réponse
x = 39
8.Théorie des nombres et arithmétique modulaire
Réponse: N = 3
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).