Chapitre 1

Logique
et raisonnements
Le mathématicien italien Giuseppe Peano était très soucieux
d’exposer les mathématiques dans un cadre précis et rigoureux.
Dans son Formulaire mathématique publié en 1895, il introduisit de
nombreux symboles nouveaux. On lui doit en particulier et
désignant respectivement l’intersection et la réunion. Il utilise la
lettre grecque epsilon, abréviation du grec esti, il est, pour noter
l’appartenance et introduit le quantificateur existentiel qu’il
note , renversant un E pour signifier l’initiale du mot italien
esiste. Il propose aussi de supprimer les déclinaisons du latin
pour obtenir une langue internationale, simple et comprise
par tous, qu’il nomme Latino sine flexione. Le logicien anglais
Bertrand Russell propose un paradoxe qui remet en cause la
Bertrand Russell
théorie des ensembles et nécessite de la fonder
1872-1970
sur un système d’axiomes.

LOGIQUE ET RAISONNEMENTS 3 !!
 Objectifs
Les incontournables
! les incontournables
! manipuler les quantificateurs
Manipuler les quantificateurs.
! raisonner par implication ou par équivalence
Raisonner par implication ou par équivalence.
! utiliser un raisonnement par l’absurde ou par contraposition
!
Utiliser
effectuer unun raisonnement
raisonnement parpar l absurdesimple
récurrence ou par
oucontraposition.
double
Effectuer un raisonnement par récurrence simple ou double.
! et plus si affinités
! Et plus
appliquer une si affinités...
récurrence forte
! raisonner par analyse-synthèse
Appliquer une récurrence forte.

Raisonner par analyse synthèse.

 Résumé de cours
! Notions de logique
Définition : Proposition —. Une proposition (ou assertion) est un énoncé mathématique qui
peut prendre deux valeurs : vrai (V) ou faux (F).
Définition : Négation d’une proposition —. Soit P une proposition. On appelle négation de P
et on note non P la proposition définie par :
! non P est vraie lorsque P est fausse ;
! non P est fausse lorsque P est vraie.
Définition : Conjonction de deux propositions —. Soit P et Q deux propositions. On appelle
conjonction de P et Q la proposition notée P et Q, et définie de la manière suivante :
! P et Q est vraie lorsque P et Q sont vraies ;
! P et Q est fausse lorsque l’une au moins des deux propositions est fausse.
Définition : Disjonction de deux propositions —. Soit P et Q deux propositions. On appelle
disjonction de P et Q la proposition notée P ou Q, et définie de la manière suivante :
! P ou Q est vraie lorsque l’une au moins des deux propositions est vraie ;
! P ou Q est fausse lorsque P et Q sont fausses.
Définition : Implication —. Soit P et Q deux propositions. On appelle implication de Q par P la
proposition non P ou Q. Cette proposition se note P ⇒ Q.
Vocabulaire : la proposition P ⇒ Q se lit ! P implique Q " ou encore ! si P alors Q "
Remarque : lorsque P ⇒ Q est vraie, on dit que P est une condition suffisante pour avoir Q,
ou que Q est une condition nécessaire pour avoir P .
Définition : Réciproque —. Soit P et Q deux propositions. On appelle réciproque de P ⇒ Q
l’implication Q ⇒ P .
Définition : Équivalence —. Soit P et Q deux propositions. On appelle équivalence de P et Q la
proposition P ⇒ Q et Q ⇒ P . Cette proposition se note P ⇔ Q.
Vocabulaire : la proposition P ⇔ Q se lit ! P si et seulement si Q ".
Remarque : lorsque P ⇔ Q est vraie, P est une condition nécessaire et suffisante pour avoir
Q. Ainsi, les équivalences sont les conditions nécessaires et suffisantes.
Table de vérité des connecteurs logiques :

P Q non P P et Q P ou Q P ⇒ Q P ⇔Q

V V F V V V V

V F F F V F F

F V V F V V F

F F V F F V V

LOGIQUE ET RAISONNEMENTS 5 !!
Remarque : d’après cette table de vérité, si P et P ⇒ Q sont vraies alors Q est vraie. C’est le
principe de déduction.
Définition : Contraposée —. Soit P et Q deux propositions. On appelle contraposée de l’implica-
tion P ⇒ Q l’implication non Q ⇒ non P

Théorème 1.1.— Soit P et Q deux propositions. L’implication P ⇒ Q et sa contraposée sont

équivalentes. Autrement dit :

(P ⇒ Q) ⇐⇒ (non Q ⇒ non P )

Proposition 1.2.— Soit P et Q deux propositions. Alors :

! non (non P ) ⇐⇒ P ! non (P ou Q) ⇐⇒ (non P ) et (non Q)

! non (P et Q) ⇐⇒ (non P ) ou (non Q) ! non (P ⇒ Q) ⇐⇒ P et (non Q)

! Quantificateurs
Définition : Soit P (x) une propriété dépendant d’un paramètre x, où x est un élément d’un en-
semble E.
• Quantificateur universel : Pour signifier que la propriété P (x) est vraie pour tous les éléments
x de E, on écrit :
∀x ∈ E, P (x)

Le symbole ∀ est appelé quantificateur universel et se lit ! quel que soit ".
• Quantificateur existentiel —. Pour signifier que la propriété P (x) est vraie pour au moins
un élément x de E, on écrit :
∃x ∈ E, P (x)

Le symbole ∃ est appelé quantificateur existentiel et se lit ! il existe ".

Proposition 1.3.— Négation des propositions avec quantificateurs —.

! La négation de la proposition ∀x ∈ E, P (x) est : ∃x ∈ E, non P (x).
! La négation de la proposition ∃x ∈ E, P (x) est : ∀x ∈ E, non P (x).

Remarque : attention, l’ordre des quantificateurs est très important. Lorsque plusieurs quantifi-
cateurs apparaissent dans une proposition, on ne peut pas intervertir leur ordre sans changer (en
général) le sens de la proposition. Pour s’en convaincre, on pourra consulter le Vrai/Faux.

!! 6 CHAPITRE 1
! Raisonnement par récurrence

Théorème 1.4.— Propriété fondamentale de N —. Toute partie non vide de N admet un plus
petit élément.

Théorème 1.5.— Principe de récurrence —. Soit P(n) une proposition dépendant de n ∈ N, et

n0 ∈ N. Si
• Initialisation : la proposition P(n0 ) est vraie,
• Hérédité : pour tout entier n " n0 , P(n) implique P(n + 1) ;
alors la proposition P(n) est vraie pour tout entier n " n0 .

Théorème 1.6.— Récurrence double —. Soit P(n) une proposition dépendant de n ∈ N, et

n0 ∈ N. Si
• Initialisation : les propriétés P(n0 ) et P(n0 + 1) sont vraies,
• Hérédité : pour tout entier n " n0 , (P(n) et P(n + 1)) implique P(n + 2) ;
alors la proposition P(n) est vraie pour tout entier n " n0 .

Théorème 1.7.— Principe de récurrence forte (ou récurrence avec prédécesseurs) —. Soit
P(n) une proposition dépendant de n ∈ N, et n0 ∈ N. Si
• Initialisation : la proposition P(n0 ) est vraie,
! "
• Hérédité : pour tout entier n " n0 , P(n0 ) et P(n0 + 1) et · · · et P(n) implique P(n + 1) ;

alors la proposition P(n) est vraie pour tout entier n " n0 .

LOGIQUE ET RAISONNEMENTS 7 !!
 Méthodes
! Démontrer une proposition

Méthode 1.1.— Comment démontrer une proposition par déduction

Si P et P ⇒ Q sont vraies, alors Q est vraie. C’est le principe de déduction. C’est un
principe très simple que l’on utilise en permanence : si l’on sait qu’une proposition P est
vraie (propriété du cours, résultat d’une question antérieure...) et que l’on sait démontrer
P ⇒ Q, alors on a démontré que la proposition Q est vraie.

Exemple : montrer que, pour tout x ∈ R, x2 − 4x + 5 > 0.

On a x2 − 4x + 5 = x2 − 4x + 4 + 1 = (x − 2)2 + 1. Or, (x − 2)2 " 0 (le carré d’un réel est positif)
et 1 > 0. Par conséquent, (x − 2)2 + 1 > 0, c’est-à-dire x2 − 4x + 5 > 0.
Mise en œuvre : tous les exercices !

Méthode 1.2.— Comment démontrer une proposition par disjonction de cas

On est parfois amené à distinguer plusieurs cas pour démontrer qu’une proposition est
vraie. C’est le principe d’une démonstration par disjonction de cas. En particulier, si
l’on souhaite démontrer qu’une proposition P (x) est vraie pour tous les éléments x d’un
ensemble E, on peut prouver la proposition pour tous les éléments d’une partie A de E,
puis pour les éléments de E n’appartenant pas à A.

Exemple : montrer que, pour tout n ∈ N, n(n+1)

2 est un entier naturel.
n(n+1)
Soit n ∈ N. On va démontrer que 2 ∈ N en distinguant les cas n pair ou impair.
n(n+1)
! Si n est pair, on peut écrire n = 2k, où k ∈ N. Alors 2 = 2k(2k+1)
2 = k(2k + 1) ∈ N.
n(n+1) (2p+1)(2p+2)
! Si n est impair, on a n = 2p + 1, où p ∈ N. Alors 2 = 2 = (2p + 1)(p + 1) ∈ N.
n(n+1)
Finalement, pour tout entier naturel n, 2 ∈ N.
Mise en œuvre : exercice 1.5, exercice 1.6.

Méthode 1.3.— Comment démontrer une proposition par l’absurde

Pour démontrer qu’une proposition P est vraie, on peut utiliser un raisonnement par
l’absurde. Pour cela, on suppose que P est fausse et on démontre que l’on aboutit alors
à une contradiction.

Exemple : montrer qu’il n’existe pas d’entier naturel supérieur à tous les autres.
Nous allons démontrer cette proposition en raisonnant par l’absurde. Pour cela, on suppose qu’il
existe un entier naturel N0 supérieur à tous les autres. On a alors, pour tout n ∈ N, n # N0 . La
relation est donc vraie pour l’entier n = N0 + 1, donc N0 + 1 # N0 ; d’où 1 # 0, ce qui est faux !
Par conséquent, il n’existe pas d’entier naturel supérieur à tous les autres.
Mise en œuvre : exercice 1.9, exercice 1.12.

!! 8 CHAPITRE 1
! Démontrer une implication

Méthode 1.4.— Comment démontrer une implication par raisonnement direct

Pour montrer directement l’implication P ⇒ Q, on suppose que P est vraie et on
démontre que Q est vraie. La démonstration commence par ! supposons que P est
vraie " et se termine par ! Q est vraie ".

Exemple : démontrer que, pour x et y réels, x2 = y 2 =⇒ |x| = |y|.

Soit x et y deux réels tels que x2 = y 2 . On a donc x2 − y 2 = 0, soit (x − y)(x + y) = 0.
Par conséquent, x − y = 0 ou x + y = 0. Ainsi, x = y ou x = −y, ce qui signifie que |x| = |y| (x et
y sont égaux ou opposés). On a donc démontré l’implication attendue.

Méthode 1.5.— Comment démontrer une implication par contraposition

Le raisonnement par contraposition est basé sur le théorème 1.1 :
l’implication P ⇒ Q est équivalente à sa contraposée non Q ⇒ non P .

Ainsi, pour montrer que l’implication P ⇒ Q est vraie, on peut prouver que l’implication
non Q ⇒ non P est vraie. En pratique, on suppose donc que non Q est vraie et on montre
que non P est vraie.

Exemple : soit n un entier naturel. Montrer que, si n2 est pair, alors n est pair.
La proposition à démontrer s’écrit : ! n2 est pair ⇒ n est pair ". Nous allons raisonner par
contraposition en démontrant la proposition (équivalente) : ! n n’est pas pair ⇒ n2 n’est pas
pair ", c’est-à-dire ! n est impair ⇒ n2 est impair ". Considérons un entier impair n : il existe
donc k ∈ N tel que n = 2k + 1. On a alors n2 = (2k + 1)2 = 4k 2 + 4k + 1, ce qui s’écrit aussi
n2 = 2p+1, où p = 2k 2 +2k. Par conséquent, n2 est un entier impair, ce qui démontre l’implication :
si n est impair, alors n2 est impair. Par contraposition, nous avons donc montré l’implication : si
n2 est pair, alors n est pair.

Exemple : montrer l’implication ! / Q⇒1+x∈

x∈ / Q ".
Nous allons de nouveau utiliser la contraposée en démontrant l’implication ! 1 + x ∈ Q ⇒ x ∈ Q ".
Soit x un réel tel que 1 + x ∈ Q. On peut écrire x = (1 + x) − 1. Or 1 + x est un nombre rationnel
(hypothèse), et 1 aussi. Par conséquent, (1 + x) − 1 est un nombre rationnel, ce qui montre que
x ∈ Q. Par contraposition, on a démontré l’implication ! x ∈ / Q⇒1+x∈ / Q ".
Mise en œuvre : exercice 1.8

Méthode 1.6.— Comment démontrer une implication par l’absurde

L’implication P ⇒ Q est la proposition non P ou Q, sa négation est donc P et non Q.
Pour démontrer par l’absurde l’implication P ⇒ Q :
• on suppose que P est vraie et que Q est fausse ;
• on montre que cela aboutit à une contradiction.

LOGIQUE ET RAISONNEMENTS 9 !!
 x y
Exemple : soit x, y ∈ R+ . En raisonnant par l’absurde, montrer que, si 1+y = 1+x , alors x = y.
x y
On raisonne par l’absurde en supposant que 1+y = 1+x et x "= y (P est vraie, Q est fausse). Il en
résulte que x(1 + x) = y(1 + y), d’où l’on tire x2 − y 2 = y − x, soit (x − y)(x + y) = y − x, d’où
(x − y)(x + y + 1) = 0. Comme x "= y, on en déduit que x + y + 1 = 0, donc x + y = −1. Absurde
vu que x et y sont positifs ! leur somme ne saurait être négative. D’où le résultat.

! Démontrer une équivalence

Méthode 1.7.— Comment démontrer une équivalence par double implication

Par définition, l’équivalence ! P ⇔ Q " est la proposition ! P ⇒ Q et Q ⇒ P ".
Démontrer par double implication l’équivalence P ⇔ Q, c’est démontrer que les implica-
tions P ⇒ Q et Q ⇒ P . En pratique, pour démontrer P ⇔ Q par double implication :
• on démontre P ⇒ Q ;
• puis on démontre Q ⇒ P .
Dans ce cas, il y a donc deux démonstrations à faire pour obtenir l’équivalence.

Exemple : on pose f (x) = mx + 1. Montrer que f garde un signe constant sur R si et seulement
si m = 0. Nous allons prouver cette équivalence en raisonnant par double implication.
⇒ Si m = 0, f est constante et égale à 1, elle garde donc un signe constant (positif) sur R.
⇐ Réciproquement, montrons que, si f garde un signe constant sur R, alors m = 0. Pour cela,
on raisonne par contraposée en supposant que m "= 0. On a alors :
! 1"
f (x) = m x + ,
m
1 1 1
et f change de signe en − m (du signe de m pour x > − m , du signe de −m pour x < − m ). Ainsi,
si m "= 0, f change de signe sur R.
Nous avons montré les deux implications. Ainsi, f garde un signe constant sur R si et seulement
si m = 0.
√
Exemple : résoudre dans R l’équation 2x = x2 + 1.
On va raisonner par double implication.
• Si x est solution de l’équation, alors (2x)2 = x2 + 1, soit 4x2 = x2 + 1, d’où 3x2 = 1. On obtient
donc x = √13 ou x = − √13 .
• Réciproquement, √13 et − √13 sont-ils solutions de l’équation ? Si x est égal à √13 ou − √13 , alors
√ #
x2 + 1 = 4/3 = √23 . Par conséquent, √13 est solution mais − √13 ne l’est pas.
Finalement, l’unique solution de l’équation est √13 .

Méthode 1.8.— Comment démontrer une équivalence par raisonnement direct

Pour démontrer l’équivalence P ⇔ Q, on peut également enchaı̂ner les équivalences.
On passe de P à Q par une succession d’équivalences en s’assurant, à chaque étape du
raisonnement, que l’équivalence est bien conservée.

! ! 10 CHAPITRE 1