Rudiments de logique
Cours de É. Bouchet – PCSI
5 septembre 2025
Table des matières
1 Généralités et rappels 2
1.1 Propositions, négations et connecteurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Implication, équivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Quantificateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Les différents modes de raisonnement 4
2.1 Raisonnement par disjonction des cas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Raisonnement par récurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2.1 Récurrence simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2.2 Récurrence double . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2.3 Récurrence forte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Raisonnement par contraposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.4 Raisonnement par l’absurde . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.5 Raisonnement par analyse-synthèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1
1 Généralités et rappels
1.1 Propositions, négations et connecteurs
Définition 1.1 (Proposition)
Une proposition (ou assertion) est une phrase mathématique qui est soit vraie (V) soit fausse (F).
Exemple. « 3 » n’est ni vrai ni faux : ce n’est pas une proposition.
La proposition P1 : « 3 ⩾ 10 » est fausse.
La proposition P2 : « la fonction x 7→ x2 est positive sur R » est vraie.
Définition 1.2 (Négation d’une proposition)
Soit P une proposition. On appelle négation de P , notée non(P ), la proposition définie par :
— non(P ) est vraie si P est fausse,
— non(P ) est fausse si P est vraie.
P non(P )
Remarque. Cette définition se résume par la table de vérité suivante : V F
F V
Exemple. non(P1 ) est « 3 < 10 », ce qui est vrai.
non(P2 ) est « la fonction x 7→ x2 n’est pas positive sur R », ce qui est faux.
Définition 1.3 (P et Q, P ou Q)
Soit P et Q deux propositions.
— la proposition (P et Q) est vraie quand les phrases P et Q sont toutes les deux vraies ;
— la proposition (P ou Q) est vraie quand au moins l’une des phrases P ou Q est vraie.
P Q P et Q P ou Q
V V V V
Remarque. Ces définitions se résument par les tables de vérité suivantes : V F F V
F V F V
F F F F
Exemple. La proposition (P1 et P2 ) est fausse, alors que (P1 ou P2 ) est vraie.
Remarque. Attention : le « ou » mathématique diffère du « ou » utilisé habituellement en français. Si un
restaurant propose « fromage ou dessert », on a rarement le droit de choisir les deux. . .
Proposition 1.4 (Négation de et/ou)
Si P et Q sont des propositions, alors :
— la négation de (P et Q) est (non(P ) ou non(Q)),
— la négation de (P ou Q) est (non(P ) et non(Q)).
Démonstration. On vérifie que les tables de vérité sont les mêmes.
Exercice 1. Déterminer la négation de « on est lundi et c’est le matin ».
Solution : C’est « on n’est pas lundi ou ce n’est pas le matin ».
Exercice 2. Soit n un entier naturel. Déterminer la négation de « n est pair ou n > 9 ».
Solution : C’est « n est impair et n ⩽ 9 ». Autrement dit, « n vaut 1, 3, 5, 7 ou 9 ».
2
1.2 Implication, équivalence
Définition 1.5 (Implication, réciproque)
Soit P et Q des propositions, on définit la proposition P ⇒ Q par la table de vérité suivante :
P Q P ⇒Q
V V V
V F F
F V V
F F V
On appelle réciproque de l’implication P ⇒ Q l’implication Q ⇒ P .
Exercice 3. Soit x un réel, déterminer si les implications suivantes sont vraies ou fausses :
1. x ⩾ 0 ⇒ x + 1 ⩾ 0,
2. x + 1 ⩾ 0 ⇒ x ⩾ 0.
Solution :
1. On suppose que x ⩾ 0, alors x + 1 ⩾ 1 ⩾ 0. Donc x ⩾ 0 ⇒ x + 1 ⩾ 0 est vraie.
2. Soit x = − 21 , on a x + 1 ⩾ 0, mais pas x ⩾ 0. Donc x + 1 ⩾ 0 ⇒ x ⩾ 0 est fausse dans le cas général.
Exercice 4. Soit f une fonction croissante sur R et x, y deux réels. Déterminer si les implications suivantes sont
vraies ou fausses :
1. x ⩾ y ⇒ f (x) ⩾ f (y),
2. f (x) ⩾ f (y) ⇒ x ⩾ y.
Solution :
1. On suppose que x ⩾ y. Comme f est croissante sur R, f (x) ⩾ f (y). Donc x ⩾ y ⇒ f (x) ⩾ f (y) est vraie.
2. Soit f la fonction nulle (qui est croissante sur R), x = 0 et y = 1. Alors f (x) = 0 ⩾ 0 = f (y), mais x < y.
Donc f (x) ⩾ f (y) ⇒ x ⩾ y est fausse dans le cas général.
Remarque. La négation de (P ⇒ Q) est P et non(Q) .
Remarque. Attention à ne pas confondre (P ⇒ Q) et (P donc Q). Dans le premier cas, on dit que si P est vrai,
alors Q le sera aussi. Dans le second cas, on affirme que P est vrai et on en déduit que Q l’est aussi.
Définition 1.6 (Condition nécessaire ou suffisante)
Soit P et Q des propositions, si P ⇒ Q est vraie, on dit que :
— P est une condition suffisante pour avoir Q,
— Q est une condition nécessaire pour avoir P .
Définition 1.7 (Équivalence)
Soit P et Q des propositions. On note P ⇔ Q la proposition ((P ⇒ Q) et (Q ⇒ P )).
Elle se lit « P si et seulement si Q », souvent abrégé « P ssi Q ».
Remarque. Lorsque P ⇔ Q est vraie, P est une condition nécessaire et suffisante pour avoir Q (et inversement).
Remarque. Le raisonnement par équivalence est particulièrement utile quand on cherche à déterminer l’ensemble
des solutions d’un problème (alors qu’on raisonne par déductions quand on cherche juste à montrer quelque chose).
Exercice 5. Déterminer l’ensemble des solutions x réelles de l’équation x2 − x = 0.
Solution : Soit x ∈ R,
x2 − x = 0 ⇐⇒ x(x − 1) = 0 ⇐⇒ x = 0 ou x = 1.
L’ensemble des solutions de l’équation est donc {0, 1}.
3
1.3 Quantificateurs
Définition 1.8 (∀,∃)
Soit E un ensemble et P une propriété.
On écrit ∀x ∈ E, P (x) quand P est vraie pour tout élément x dans E.
On écrit ∃x ∈ E, P (x) quand il existe au moins un x dans E pour lequel P est vraie.
On écrit ∃!x ∈ E, P (x) quand il existe exactement un x dans E pour lequel P est vraie.
Remarque. Les symboles ∀ et ∃ ne sont en aucun cas des abréviations. Ils ne doivent jamais être utilisés dans
une phrase en français pour remplacer « pour tout » ou « il existe ».
Exemple. ∀x ∈ R, x2 ̸= −1 car le carré d’un réel est toujours positif.
Par contre, ∃z ∈ C tel que z 2 = −1 car par exemple i2 = −1.
1
Exercice 6. Montrer que : ∃x ∈ R tel que x2 ⩾ 3 et ⩽ 0, 1.
x
1
Solution : x = 10 convient, car 102 = 100 ⩾ 3 et 10 = 0, 1 ⩽ 0, 1.
Remarque. On peut permuter les quantificateurs ∀ entre eux et les quantificateurs ∃ entre eux. Dans le cas
général, il est cependant interdit de permuter un ∀ et un ∃.
√
Exemple. ∀y ∈ R+ , ∃x ∈ R tel que x2 = y est une assertion vraie : pour tout y ∈ R+ , x = y convient.
∃x ∈ R tel que ∀y ∈ R+ , x2 = y est une assertion fausse par contre : il faudrait que ce soit le même réel x qui, mis
au carré, vaille plusieurs valeurs de y différentes, c’est impossible.
Proposition 1.9 (Négation des quantificateurs)
Soit E un ensemble, on a :
non(∀x ∈ E, P (x)) ⇐⇒ ∃x ∈ E, non(P (x)),
et
non(∃x ∈ E, P (x)) ⇐⇒ ∀x ∈ E, non(P (x)).
Démonstration. On vérifie que les tables de vérité sont les mêmes.
Exercice 7. On considère la fonction f définie de R dans R par : ∀x ∈ R, f (x) = x2 − 9x + 20. Montrer que f
n’est pas une fonction positive.
Solution : « la fonction f est une fonction positive » s’écrit : ∀x ∈ R, f (x) ⩾ 0. En passant à la négation, « la
fonction f n’est pas une fonction positive » s’écrit donc : ∃x ∈ R tel que f (x) < 0. Or, on trouve par calcul :
9 81 81 81 − 81 × 2 + 80 1
f (4, 5) = f = − + 20 = = − < 0.
2 4 2 4 4
Donc la fonction f n’est pas positive.
2 Les différents modes de raisonnement
2.1 Raisonnement par disjonction des cas
Définition 2.1 (Principe du raisonnement par disjonction de cas)
Raisonner par disjonction de cas pour démontrer une propriété P consiste en la décomposer en un nombre
fini de cas vérifiés séparément.
Exercice 8. Montrer que ∀n ∈ N, n(n+1)2 est un entier.
Solution : Soit n ∈ N,
— Si n est pair, alors ∃k ∈ N tel que n = 2k. Donc n(n+1)
2 = k(2k + 1), qui est bien un entier.
4
n(n+1) (2k+1)(2k+2)
— Si n est impair, alors ∃k ∈ N tel que n = 2k + 1. Donc 2 = 2 = (2k + 1)(k + 1), qui est bien
un entier.
Donc ∀n ∈ N, n(n+1)
2 est un entier.
x + y + |x − y|
Exercice 9. Soit x et y deux réels fixés. Montrer que max(x, y) = .
2
Solution :
x + y + |x − y| x+y+x−y
— Si x ⩾ y, alors max(x, y) = x et |x − y| = x − y. Donc = = x = max(x, y).
2 2
x + y + |x − y| x+y+y−x
— Si x < y, alors max(x, y) = y et |x − y| = y − x. Donc = = y = max(x, y).
2 2
x + y + |x − y|
Comme x ⩾ y et x < y couvrent toutes les valeurs possibles de x et y, ∀(x, y) ∈ R2 , max(x, y) = .
2
2.2 Raisonnement par récurrence
2.2.1 Récurrence simple
Proposition 2.2 (Principe de récurrence)
Soit n un entier, et P (n) une propriété dépendant de n. Soit n0 un entier. Si P (n0 ) est vraie (initialisation)
et si ∀n ⩾ n0 , P (n) ⇒ P (n + 1) (hérédité) alors pour tout entier n ⩾ n0 , P (n) est vraie.
Démonstration. Admis.
n(n + 1)
Exercice 10. Montrer que pour tout entier n ∈ N, on a 0 + 1 + 2 + . . . + n = .
2
n(n + 1)
Solution : Soit n ∈ N. On pose P (n) : « 0 + 1 + 2 + . . . + n = ».
2
0×1
— 0= donc P (0) est vraie.
2
— Soit n ∈ N, on suppose que P (n) est vraie. Alors :
n(n + 1) n (n + 1)(n + 2)
0 + 1 + 2 + ... + n + n + 1 = + n + 1 = (n + 1) +1 = .
2 2 2
Donc P (n + 1) est vraie.
n(n + 1)
Donc ∀n ∈ N, 0 + 1 + 2 + . . . + n = .
2
2.2.2 Récurrence double
Proposition 2.3 (Récurrence double)
Soit n un entier, et P (n) une propriété dépendant de n. Soit n0 un entier. Si P (n0 ) et P (n0 + 1) sont vraies
(initialisation) et si ∀n ⩾ n0 , (P (n) et P (n + 1)) ⇒ P (n + 2) (hérédité) alors pour tout entier n ⩾ n0 , P (n)
est vraie.
Démonstration. On montre par récurrence simple sur n ⩾ n0 la propriété « P (n) et P (n + 1) ».
Exercice 11. Déterminer le terme général de la suite (un )n∈N définie par u0 = 1, u1 = 3 et pour tout n ∈ N,
un+2 = 2un+1 + 3un .
Solution : On remarque que u2 = 9, u3 = 27. On conjecture alors que pour tout n ∈ N, un = 3n .
Soit n ∈ N. On pose P (n) : « un = 3n ».
— On a u0 = 30 donc P (0) est vraie, et u1 = 31 donc P (1) est vraie.
— Soit n ∈ N, on suppose que P (n) et P (n + 1) sont vraies. Alors :
un+2 = 2un+1 + 3un = 2 · 3n+1 + 3 · 3n = 3n (6 + 3) = 3n+2 .
Donc P (n + 2) est vraie.
On conclut que : ∀n ∈ N, un = 3n .
5
2.2.3 Récurrence forte
Proposition 2.4 (Récurrence forte)
Soit n un entier, et P (n) une propriété dépendant de n. Soit n0 un entier. Si P (n0 ) est vraie (initialisation)
et si ∀n ⩾ n0 , (∀k ∈ [[n0 , n]], P (k)) ⇒ P (n + 1) (hérédité) alors pour tout entier n ⩾ n0 , P (n) est vraie.
Démonstration. On montre par récurrence simple sur n ⩾ n0 la propriété « ∀k ∈ [[n0 , n]], P (k) ».
Exercice 12. Déterminer le terme général de la suite (un )n∈N définie par : u0 = 1 et pour tout entier n ⩾ 0,
1
un+1 = (u0 + u1 + · · · + un ).
n+1
Solution : On remarque que u1 = 1, puis que u2 = 1. On conjecture alors que pour tout n ∈ N, un = 1.
Soit n ∈ N. On pose P (n) : « un = 1 ».
— On a u0 = 1 donc P (0) est vraie.
— Soit n ∈ N, on suppose que ∀k ∈ [[0, n]], P (k) est vraie. Alors :
1 1 n+1
un+1 = (u0 + u1 + · · · + un ) = (1 + 1 + · · · + 1) = = 1.
n+1 n+1 n+1
Donc P (n + 1) est vraie.
Donc ∀n ∈ N, un = 1.
2.3 Raisonnement par contraposition
Définition 2.5 (Contraposée)
Soit P et Q deux propositions. La contraposée de l’implication P ⇒ Q est l’implication non(Q) ⇒ non(P ).
Exemple. La contraposée de « si on est en hiver, le professeur porte des chaussettes » est « si le professeur ne
porte pas de chaussettes, on n’est pas en hiver ».
Proposition 2.6 (Principe du raisonnement par contraposition)
Soit P et Q deux propositions, on a alors :
(P ⇒ Q) ⇐⇒ (non(Q) ⇒ non(P )) .
Démonstration. Il suffit de vérifier que P ⇒ Q et non(Q) ⇒ non(P ) ont les mêmes tables de vérité.
Exercice 13. Montrer que pour tout entier n ∈ Z, (n2 est pair) ⇒ (n est pair).
Solution : Soit n ∈ Z. On suppose qu’il est impair. Alors il existe k ∈ Z tel que n = 2k + 1. Ce qui donne :
n2 = (2k + 1)2 = 4k 2 + 4k + 1 = 2(2k 2 + 2k) + 1.
Comme k est entier, 2k 2 + 2k ∈ Z, on en déduit que n2 est impair. D’où (n est impair) ⇒ (n2 est impair).
Par contraposition, on obtient (n2 est pair) ⇒ (n est pair).
2.4 Raisonnement par l’absurde
Proposition 2.7 (Principe du raisonnement par l’absurde)
Soit P une proposition. Si en supposant que P est fausse, on déduit une contradiction, alors P est vraie.
Démonstration. Montrer que P est vrai revient à montrer que Vrai implique P . Par contraposition, il suffit donc
de montrer que non(P ) implique Faux.
6
1
Exercice 14. On considère la suite (un )n∈N définie par u0 = 1 et pour tout n ⩾ 0, un+1 = un + , dont on
un
admet qu’elle est bien définie et à valeurs strictement positives. Montrer qu’elle diverge.
Solution : On suppose que la suite (un ) converge vers ℓ ∈ R. Alors la suite (un+1 ) converge aussi vers ℓ. Or ∀n ∈ N,
un+1 = un + u1n . En passant à la limite dans cette égalité, on trouve :
— Si ℓ ̸= 0, alors ℓ = ℓ + 1ℓ , donc 1ℓ = 0 : absurde.
— Si ℓ = 0, comme la suite (un ) est positive, alors ( u1n ) diverge vers +∞. Le passage à la limite donne donc
ℓ = +∞ : absurde.
Donc la suite (un ) diverge.
Variante : on pouvait aussi utiliser la positivité de u pour montrer que la suite est croissante. Or u0 = 1, donc
ℓ ⩾ 1, ce qui permet d’éviter la disjonction de cas.
2.5 Raisonnement par analyse-synthèse
Définition 2.8 (Principe du raisonnement par analyse-synthèse)
Le raisonnement par analyse-synthèse sert à déterminer l’ensemble des solutions d’un problème. Il se rédige
en deux étapes :
— L’analyse : correspond au sens direct d’un raisonnement par équivalences. On étudie une solution,
en supposant son existence. Le but est d’obtenir un maximum d’informations à son sujet, pour se
ramener à un nombre limité de candidats.
— La synthèse : correspond à la réciproque d’un raisonnement par équivalences. On étudie séparément
chacun des candidats de l’analyse pour vérifier s’ils sont solution ou non du problème.
Remarque. L’analyse permet de déterminer des conditions nécessaires à la résolution du problème, la synthèse
permet ensuite de vérifier si ces conditions sont suffisantes.
Remarque. Le plus souvent, on raisonne par analyse-synthèse quand on cherche toutes les solutions d’un problème
mais qu’un raisonnement par équivalences est impossible (ou compliqué).
√
Exercice 15. Déterminer les solutions réelles x de l’équation (E) : 6 + x = x.
Solution : Première méthode : par analyse-synthèse. √
— Analyse : on suppose que (E) admet une solution x ∈ R. Alors 6 + x = x. En passant au carré, on trouve
6 + x = x2 , et donc x2 − x − 6 = 0, dont le discriminant vaut ∆ = 1 + 24 = 25 > 0. Donc x = 1+5
2 = 3 ou
1−5
x = 2 = −2.
— Synthèse
√ : √
— √6 + 3 = √9 = 3, donc x = 3 est une solution de (E).
— 6 − 2 = 4 = 2 ̸= −2, donc x = −2 n’est pas une solution de (E).
Ainsi, l’équation (E) admet x = 3 pour unique solution.
Deuxième méthode : par équivalences. Soit x ∈ R,
√ √
6 + x = x ⇐⇒ 6 + x = x et x ⩾ 0 car une racine est toujours positive
⇐⇒ 6 + x = x2 et x ⩾ 0 car la fonction carré est strictement croissante sur R+
⇐⇒ (x = −2 ou x = 3) et x ⩾ 0 par calcul du discriminant
√
6 + x = x ⇐⇒ x = 3.
Donc x = 3 est l’unique solution de l’équation.
Exercice 16. Déterminer l’ensemble des fonctions de R dans R telles que :
∀x ∈ R, ∀y ∈ R, f (x + y) − f (x − y) = 4xy.
Solution :
7
— Analyse : On suppose que f est une fonction de R dans R qui vérifie la relation. Alors en particulier, pour
x ∈ R et y = x :
f (2x) − f (0) = 4x2 = (2x)2 .
Donc pour tout z ∈ R, (z = 2x, qui parcourt bien l’ensemble des réels), f (z) = f (0) + z 2 .
— Synthèse : Soit C ∈ R une constante fixée et f la fonction définie sur R par f (z) = C + z 2 .
∀x ∈ R, ∀y ∈ R, f (x + y) − f (x − y) = (x + y)2 + C − (x − y)2 − C = 4xy.
Donc f est bien solution du problème.
Les solutions du problème sont les fonctions f de R dans R pour lesquelles il existe C ∈ R tel que ∀z ∈ R,
f (z) = C + z 2 .
Variante : dans l’analyse, on pouvait aussi faire apparaître un taux d’accroissement pour montrer f ′ (x) = 2x et en
déduire f par calcul de primitive.