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
Quelle formule est logiquement équivalente à a → c ? Cliquez dessus.
a → c
1¬a → ¬c
2¬c ∧ ¬a
3¬c → ¬a
4c → a
2.Logique propositionnelle et preuvesDifficile
Le raisonnement de prémisses b → c; ¬b et de conclusion ¬c est invalide. Cliquez sur la ligne de la table de vérité qui est un contre-exemple.
b → c¬b∴ ¬c
1b = 1, c = 1
2b = 1, c = 0
3b = 0, c = 1
4b = 0, c = 0
3.Ensembles, relations et fonctionsMoyen
La relation R sur {1, 2, 3, 4} 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.
Le graphe connexe a-t-il un circuit eulérien, un chemin eulérien qui n’est pas un circuit, ou ni l’un ni l’autre ? Cliquez sur votre réponse.
|V| = 6|E| = 6
1Circuit eulérien
2Chemin eulérien, pas de circuit
3ni l’une ni l’autre
6.Théorie des graphesDifficile
L’algorithme de Prim construit un arbre couvrant minimal en partant du sommet B. Cliquez sur l’arête qu’il ajoute en numéro 4.
départ : Bk = 4
1arête AB
2arête AC
3arête BC
4arête BD
5arête CE
6arête DE
7arête BE
7.Théorie des nombres et arithmétique modulaireMoyen
Trouvez l’inverse de 54 modulo 61 : le nombre x avec 0 < x < 61 et 54·x ≡ 1 (mod 61).
a = 54n = 61
54−1 mod 61 =
8.Théorie des nombres et arithmétique modulaireDifficile
Chiffre le message m = 162 avec la clé publique RSA (n, e) = (527, 7). Trouvez le chiffré c.
n = 527e = 7m = 162
c =
3Solutions
1.Logique propositionnelle et preuves
Réponse: ¬c → ¬a
É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).
La loi
Une implication est équivalente à sa contraposée ¬b → ¬a, pas à sa réciproque b → a ni à son inverse ¬a → ¬b.
a → c ≡ ¬c → ¬a
Vérifier avec la table de vérité
a = 1, c = 1: 1 | 1 0 1 1
a = 1, c = 0: 0 | 1 0 0 1
a = 0, c = 1: 1 | 0 0 1 0
a = 0, c = 0: 1 | 1 1 1 1
Réponse
¬c → ¬a
Les colonnes après la barre sont les options dans l’ordre affiché.
2.Logique propositionnelle et preuves
Réponse: b = 0, c = 1
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.
Prémisses et conclusion ligne par ligne
b = 1, c = 1: 1 0 | 0
b = 1, c = 0: 0 0 | 1
b = 0, c = 1: 1 1 | 0
b = 0, c = 0: 1 1 | 1
Contre-exemple
b = 0, c = 1
Réponse
b = 0, c = 1
Un raisonnement de cette forme ressemble à une règle valide, mais une seule ligne suffit à montrer qu’il ne l’est pas.
3.Ensembles, relations et fonctions
Réponse: transitive
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 : (1, 1) ∉ R
symétrique
échoue : (2, 1) ∈ R, (1, 2) ∉ R
antisymétrique
échoue : (3, 4), (4, 3) ∈ R
transitive
est vérifiée
Réponse
transitive
4.Ensembles, relations et fonctions
Réponse: (g ∘ f)(4) = 2
Fonctions et dénombrement : une fonction f: A → B donne à chaque élément de A exactement une image dans B. f est injective quand des éléments différents ont des images différentes, surjective quand tout élément de B est une image, et bijective quand les deux sont vraies. Avec |A| = m et |B| = n il y a nᵐ fonctions, n!/(n − m)! fonctions injectives (m ≤ n), et par inclusion-exclusion Σ (−1)ᵏ·C(n, k)·(n − k)ᵐ fonctions surjectives. |𝒫(A)| = 2ᵐ et |A × B| = m·n.
Fonction intérieure
f(4) = 4
Fonction extérieure
g(4) = 2
(g ∘ f)(4) = 2
Réponse
(g ∘ f)(4) = 2
5.Théorie des graphes
Réponse: Chemin eulérien, pas de circuit
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.
Le chemin eulérien commence à un sommet impair et finit à l’autre.
6.Théorie des graphes
Réponse: arête CE
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 Prim
1. AB (1)
2. BE (2)
3. DE (6)
4. CE (10)
numéro de l’arête 4
CE
Réponse
arête CE
7.Théorie des nombres et arithmétique modulaire
Réponse: 54−1 mod 61 = 26
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·54 (mod 61).
r = 61, t = 0
r = 54, q = 1, t = 1
r = 7, q = 7, t = −1
r = 5, q = 1, t = 8
r = 2, q = 2, t = −9
r = 1, q = 2, t = 26
Inverse
1 ≡ 26·54 (mod 61)
x = 26
vérification: 54·26 = 1404 = 23·61 + 1
Réponse
54−1 mod 61 = 26
8.Théorie des nombres et arithmétique modulaire
Réponse: c = 121
Puissances modulaires et RSA : calculez aᵏ mod n par carrés répétés : écrivez k en binaire, élevez au carré, réduisez après chaque étape et multipliez les puissances dont le bit vaut 1. Fermat : aᵖ⁻¹ ≡ 1 (mod p) pour un nombre premier p ne divisant pas a, donc l’exposant peut être réduit modulo p − 1. RSA : choisissez des nombres premiers p et q, n = p·q et φ(n) = (p − 1)(q − 1) ; l’exposant public e est premier avec φ(n), et l’exposant privé est d = e⁻¹ mod φ(n). Chiffre avec c = mᵉ mod n et déchiffrez avec m = cᵈ mod n.