■ Fiche de Logique – MPSI
1. Propositions logiques
Une proposition est un énoncé qui peut être vrai (V) ou faux (F).
1 « 2 est pair » (Vrai)
2 « 7 est divisible par 2 » (Faux)
2. Connecteurs logiques
1 ¬ P : non P
2 P ∧ Q : P et Q (vrai si les deux sont vrais)
3 P ∨ Q : P ou Q (vrai si au moins un est vrai)
4 P ⇒ Q : si P alors Q (faux uniquement si P est vrai et Q est faux)
5 P ⇔ Q : P si et seulement si Q (vrai si P et Q ont la même valeur)
3. Quantificateurs
1 ∀ x ∈ E, P(x) : pour tout x de E, P(x) est vrai
2 ∃ x ∈ E, P(x) : il existe au moins un x de E tel que P(x) est vrai
3 Négation : ¬(∀ x, P(x)) ⇔ ∃ x, ¬P(x)
4 Négation : ¬(∃ x, P(x)) ⇔ ∀ x, ¬P(x)
4. Preuves et raisonnements
1 Preuve directe : on part des hypothèses pour arriver à la conclusion
2 Contraposition : montrer P ⇒ Q équivaut à prouver ¬Q ⇒ ¬P
3 Par l’absurde : on suppose l’énoncé faux et on arrive à une contradiction
4 Par récurrence :
5 1. Initialisation : P(n■) est vrai
6 2. Hérédité : P(k) ⇒ P(k+1)
7 3. Conclusion : P(n) est vrai pour tout n ≥ n■
5. Exemples classiques
1 Si n² est pair, alors n est pair (preuve par contraposée)
2 La somme de deux entiers pairs est paire (preuve directe)
3 Il existe une infinité de nombres premiers (preuve par l’absurde, Euclide)
■ À retenir : La logique est la grammaire des mathématiques. Bien la maîtriser facilite toutes les
démonstrations du programme.
■ Exercices de Logique – Niveau MPSI
Exercice 1 : Contraposée
Montrer que si n² est pair, alors n est pair.
Correction : Par contraposée : si n est impair, alors n² est impair. Si n=2k+1, alors
n²=(2k+1)²=4k²+4k+1 impair. Donc si n² est pair, n est pair.
Exercice 2 : Raisonnement par l’absurde
Prouver qu’il existe une infinité de nombres premiers.
Correction : Supposons un nombre fini de nombres premiers : p■,…,p■. Considérons
N=p■p■…p■+1. N n’est divisible par aucun p■, donc est premier ou possède un nouveau
facteur premier. Contradiction. Donc infinité de nombres premiers.
Exercice 3 : Quantificateurs
Traduire et nier correctement : ∀n ∈ ■, n² ≥ n ; ∃x ∈ ■, x² < 0.
Correction : 1) Proposition : Pour tout n ∈ ■, n² ≥ n. Négation : Il existe n tel que n² < n. 2)
Proposition : Il existe x ∈ ■ tel que x² < 0. Négation : Pour tout x, x² ≥ 0.
Exercice 4 : Récurrence
Prouver que 1+2+…+n = n(n+1)/2.
Correction : Initialisation pour n=1, vrai. Hérédité : supposons vrai pour n=k. Pour n=k+1 :
somme = k(k+1)/2+(k+1) = (k+1)(k+2)/2. Donc vrai pour tout n.
Exercice 5 : Implications et équivalences
Montrer : « Si n est divisible par 6 alors n est divisible par 2 et par 3 ».
Correction : Si n=6k, alors divisible par 2 (n=2(3k)) et par 3 (n=3(2k)). Donc vrai.
■ Exercices plus difficiles (niveau concours)
Exercice 6 : Contre-exemple
Montrer que la proposition : « ∀x ∈ ■, (x² ≥ x) » est fausse.
Correction : Pour x=1/2, on a (1/2)²=1/4 < 1/2. Donc la proposition est fausse.
Exercice 7 : Double implication
Prouver que pour tout n, n est divisible par 4 ⇔ n² est divisible par 16.
Correction : Si n divisible par 4, n=4k donc n²=16k² divisible par 16. Réciproquement, si n²
divisible par 16, alors n est pair, écrivons n=2m. Donc n²=4m² divisible par 16 ⇒ m pair ⇒
n=4k. Équivalence démontrée.
Exercice 8 : Irrationalité de √2
Montrer par l’absurde que √2 n’est pas rationnel.
Correction : Supposons √2=p/q irréductible. Alors 2q²=p². Donc p² pair ⇒ p pair. p=2k ⇒
2q²=4k² ⇒ q²=2k² ⇒ q pair. Contradiction (p et q ont un facteur 2). Donc √2 est irrationnel.
