1
Chapitre 1 : Logique, ensembles et
raisonnements
Table des matières
1 Rudiments de logiques 2
1.1 Assertions mathématiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Connecteurs logiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Quantificateurs 5
2.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Ordre des quantificateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Quantificateurs et opérations logiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3 Ensembles 6
3.1 Définition d’un ensemble et appartenance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.2 Inclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.3 Sous-ensemble ou partie d’un ensemble . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.4 Opérations sur les parties d’un ensemble . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.5 Couples, p−uplets et produit cartésien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4 Différents modes de raisonnement 10
4.1 Démontrer une implication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.2 Démontrer une équivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.3 Raisonnement par récurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
S. Freyssinet BCPST 1.1 2021−2022
2
1 Rudiments de logiques
1.1 Assertions mathématiques
Définition 1.
On appelle assertion mathématique un énoncé portant sur les propriétés de certains objets mathé-
matiques.
Elle peut être vraie ou fausse.
Exemples :
• Le nombre 3 est pair.
• le nombre π est un irrationnel.
• il existe un nombre réel x tel que x2 = −1.
Définition 2.
On appelle conjecture une assertion mathématique dont on soupçonne la véracité mais qui n’a pas
été démontrée.
1.2 Connecteurs logiques
Définition 3.
Soit A une assertion mathématique.
La négation de A, notée eA, est l’assertion qui prend toujours la valeur contraire à celle de A.
La table de vérité est donnée par le tableau suivant.
A eA
Exemple 1:
1. La négation de tous les frères de Paul sont blonds est
............................................................................................................................
2. La négation de chaque élève a au moins lu un des livres au programme est
............................................................................................................................
Théorème 1.
Soit A une assertion mathématique.
e(eA) = A
S. Freyssinet BCPST 1.1 2021−2022
3
Définition 4.
Soient A et B deux assertions mathématiques.
L’assertion A et B, notée A ∧ B, est vraie seulement lorsque A et B sont vraies.
La table de vérité est donnée par le tableau suivant.
A B A∧B
V V
V F
F V
F F
Définition 5.
Soient A et B deux assertions.
L’assertion A ou B, notée A ∨ B, est vraie dès que A ou B est vraie.
La table de vérité est donnée par le tableau suivant.
A B A∨B
V V
V F
F V
F F
Exemple 2: Pour A= « 3 est pair » et B= « 6 est pair » , la proposition A ∨ B est vraie.
Théorème 2.
Soient A et B deux assertions mathématiques. On a les liens logiques suivants :
1. A ∧ A = A
2. A ∧ B = B ∧ A Commutativité de et
3. A ∨ A = A
4. A ∨ B = B ∨ A Commutativité de ou
5. A ∧ (eA) est toujours fausse.
6. A ∨ (eA) est toujours vraie.
7. e(A ∧ B) = (eA) ∨ (eB). Négation d’un et
8. e(A ∨ B) = (eA) ∧ (eB). Négation d’un ou
Exemple 3: La négation de la proposition Tous les élèves de la classe ont 3 frères et 2 sœurs est
.................................................................................................................................................
.................................................................................................................................................
Théorème 3.
Soient A,B et C trois assertions mathématiques. On a les liens logiques suivants :
1. A ∨ (B ∨ C) = (A ∨ B) ∨ C Associativité de ou
2. A ∧ (B ∧ C) = (A ∧ B) ∧ C Associativité de et
3. A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C) Distributivité de ou sur et
4. A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C) Distributivité de et sur ou
S. Freyssinet BCPST 1.1 2021−2022
4
Définition 6.
Soient A et B deux assertions mathématiques.
L’assertion A implique B, notée A ⇒ B, est vraie lorsque B ne peut pas être fausse avec A vraie.
La table de vérité est donnée par le tableau suivant.
A B A⇒B
V V
V F
F V
F F
Exemple 4: Avec A(x) : « x est un multiple de 6 » et B(x) : « x est un multiple de 2 »,
la proposition A(x) ⇒ B(x) est vraie tandis que la proposition B(x) ⇒ A(x) est fausse.
Définition 7.
Soient A et B deux propositions.
La réciproque de l’implication A ⇒ B est l’implication B ⇒ A.
Exemple 5: La réciproque de « Si n est un multiple de 6 alors n est un multiple de 2 » est
« Si n est un multiple de 2 alors n est un multiple de 6 ».
Définition 8.
Soient A et B deux assertions.
La contraposée de l’implication A ⇒ B est l’implication eB ⇒eA.
Exemple 6: La contraposée de « Si n est un multiple de 6 alors n est un multiple de 2 » est la proposition « Si
n n’est pas un multiple de 2 alors n n’est pas un multiple de 6 ».
Théorème 4.
Soient A et B deux assertions.
L’implication A ⇒ B et sa réciproque B ⇒ A ne sont pas égales.
L’implication A ⇒ B et sa contraposée eB ⇒eA sont toujours égales.
Définition 9.
Soient A et B deux assertions mathématiques.
La proposition A est équivalente à B, notée A ⇔ B, est la proposition définie par (A ⇒ B) ∧ (B ⇒
A). On lit « A si, et seulement si, B ».
La table de vérité est donnée par le tableau suivant
A B A⇒B B⇒A A⇔B
V V
V F
F V
F F
Exemple 7: Pour trois réels positifs a, b et c, un triangle de côtés de longueur a, b et c est rectangle si, et
seulement si, a2 + b2 = c2 .
S. Freyssinet BCPST 1.1 2021−2022
5
2 Quantificateurs
2.1 Définitions
Définition 10.
Le quantificateur ∈ traduit l’appartenance à un ensemble.
Le quantificateur ∈
/ traduit la non appartenance à un ensemble.
Définition 11.
Le quantificateur universel ∀ se lit quelque soit ou pour tout.
Exemple 8: Tous les carrés de nombres réels sont négatifs se traduit par
∀x ∈ R , x2 ≤ 0.
Remarque : Pour démontrer une propriété de la forme ∀x ∈ E, A(x), on doit montrer que pour toute valeur
de x, la propriété A(x) est vraie.
On commencera souvent par Soit x ∈ E.
Définition 12.
Le quantificateur existentiel ∃ se lit il existe.
Il signifie il existe au moins un élément tel que ...
√
Exemple 9: Il existe un réel dont le carré vaut 2 se traduit par
√
∃ x ∈ R , x2 = 2.
Remarque : Pour démontrer une propriété de la forme ∃x ∈ E, A(x), on doit justifier l’existence d’un tel
élément, en un proposant un par exemple.
Exemple 10: Comment traduire n est impair ?
..............................................................................................................................
Définition 13.
Le quantificateur ∃! se lit il existe un unique.
Il signifie il existe exactement un élément tel que ...
Exemple 11: Il existe un unique réel dont le double vaut la moitié se traduit par
x
∃! x ∈ R , 2x = .
2
Remarque : Pour démontrer une propriété de la forme ∃!x ∈ E, A(x), on doit justifier l’existence d’un tel
élément et son unicité.
Exemple 12: Que pensez-vous des propositions suivantes ?
• ∀ x ∈ R, cos(x) = 0
• ∃ x ∈ R, cos(x) = 0
• ∃! x ∈ R, cos(x) = 0
S. Freyssinet BCPST 1.1 2021−2022
6
2.2 Ordre des quantificateurs
Exemple : Comment traduire Tous les points de E ont un antécédent par f dans A ?
.............................................................................................................................
Remarque : L’ordre des quantificateurs est très important.
• ∀x ∈ R+ , ∃y ∈ R, x2 = y
• ∃y ∈ R, ∀x ∈ R+ , x2 = y
Théorème 5.
Lorsqu’on utilise plusieurs fois le même quantificateur, on peut inverser l’ordre.
Lorsqu’on utilise des quantificateurs différents, on ne peut pas inverser l’ordre.
Exemple 13: On peut écrire « ∀a ∈ A, ∀b ∈ B, ... » ou bien « ∀b ∈ B, ∀a ∈ A, ... » ou encore
« ∀(a, b) ∈ A × B, ... ».
2.3 Quantificateurs et opérations logiques
Théorème 6.
Soit A(x) une proposition portant sur un réel x.
1. La négation de « ∀x ∈ R, A(x) » est « ∃x ∈ R, eA(x) ».
2. La négation de « ∃x ∈ R, A(x) » est « ∀x ∈ R, eA(x) ».
Théorème 7.
Soient A(x, y) une proposition portant sur deux réels x et y.
La négation de « ∀x ∈ R, ∃y ∈ R, A(x, y) » est « ∃x ∈ R, ∀y ∈ R, eA(x, y) ».
3 Ensembles
3.1 Définition d’un ensemble et appartenance
Définition 14.
Lorsqu’un ensemble E est défini en faisant la liste des objets mathématiques qu’il contient, on dit
que l’on a défini cet ensemble par extension.
E = {x1 , . . . , xn }
Ces objets mathématiques sont appelés éléments de l’ensemble E.
Lorsqu’il n’y a qu’un seul élément, on parle de singleton : {x1 }.
Lorsqu’il n’y a aucun élément, on parle de l’ensemble vide. On le note ∅.
On dit que y appartient à E lorsque y est un des éléments de E.
y ∈ E ⇔ ∃ i ∈ [[1, n]], y = xi
S. Freyssinet BCPST 1.1 2021−2022
7
Exemple 14:
Définition 15.
Lorsqu’un ensemble E est défini par une propriété que vérifient les éléments d’un autre ensemble F ,
on dit que l’ensemble E est défini par compréhension.
E = {x ∈ F tel que P (x)}
On dit que y appartient à E lorsque P (y) est vraie.
y ∈ E ⇔ P (y)
Exemple 15: Prenons E = {x ∈ R / x(x + 2) = −12}. Il est défini par compréhension.
Sa définition par extension est E =
Exemples : Les ensembles R− ou N∗ sont définis par compréhension.
3.2 Inclusion
Définition 16.
Soient E et F deux ensembles. On dit que E est inclus dans F lorsque tous les éléments de E
appartiennent à F . On note E ⊂ F ou F ⊃ E.
E ⊂ F ⇔ ∀x ∈ E , x ∈ F
Remarque : Pour montrer qu’un ensemble E est inclus dans un ensemble F , on devra démontrer que tous les
éléments de E sont inclus dans F .
1. Soit x ∈ E.
2. . . .
3. donc x ∈ F .
S. Freyssinet BCPST 1.1 2021−2022
8
Exemple 16: Montrer que {n ∈ N tel que n impair} ⊂ n ∈ N tel que n2 impair .
Remarque : Il faut bien distinguer les symboles ∈ et ⊂.
• x ∈ E : l’élément x appartient à l’ensemble E.
• A ⊂ E : l’ensemble A est inclus dans l’ensemble E.
Remarque : L’ensemble vide est inclus dans tous les ensembles.
Définition 17.
Soient E et F deux ensembles. On dit que E est égal à F lorsque E est inclus dans F et que F est
inclus dans E.
E = F ⇔ (E ⊂ F ) et (F ⊂ E)
3.3 Sous-ensemble ou partie d’un ensemble
Définition 18.
Soit E un ensemble. On appelle sous-ensemble ou partie de E tout ensemble inclus dans E.
On note P(E) l’ensemble contenant toutes les parties de E.
Exemple 17: Faire la liste des parties de E = {0, 1} puis de F = {0, 1, 2}.
Remarque : Une partie de E est incluse dans E mais elle appartient à l’ensemble des parties de E.
A ⊂ E ⇔ A ∈ P(E)
3.4 Opérations sur les parties d’un ensemble
Définition 19.
Soient A et B deux parties d’un ensemble E. E
A
On appelle union de A et de B et on note A ∪ B
l’ensemble défini par
A ∪ B = {x ∈ E /x ∈ A ou x ∈ B} B
Théorème 8.
Soient A, B et C trois parties d’un ensemble E. Alors,
1. A ∪ ∅ = A et A ∪ E = E.
2. L’union est idempotente : A ∪ A = A.
3. L’union est commutative : A ∪ B = B ∪ A.
4. L’union est associative : A ∪ (B ∪ C) = (A ∪ B) ∪ C.
Remarque : L’union de deux ensembles est l’équivalent de l’opérateur logique ou.
S. Freyssinet BCPST 1.1 2021−2022
9
Définition 20.
Soient A et B deux parties d’un ensemble E. E
A
On appelle intersection de A et de B et on note A∩B l’ensemble
défini par
A ∩ B = {x ∈ E /x ∈ A et x ∈ B} B
Théorème 9.
Soient A, B et C trois parties d’un ensemble E. Alors,
1. A ∩ ∅ = ∅ et A ∩ E = A.
2. L’intersection est idempotente : A ∩ A = A.
3. L’intersection est commutative : A ∩ B = B ∩ A.
4. L’intersection est associative : A ∩ (B ∩ C) = (A ∩ B) ∩ C.
Remarque : L’intersection de deux ensembles est l’équivalent de l’opérateur logique et.
Théorème 10.
Soient A, B et C trois parties d’un ensemble E. Alors,
1. L’intersection est distributive sur l’union : A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
2. L’union est distributive sur l’intersection : A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
Définition 21.
Soient A et B deux parties d’un ensemble E. E
Lorsque A∩B = ∅, on dit que les ensembles A et B sont disjoints.
B
On dit alors que l’union A ∪ B est une union disjointe
A
et on la note A q B.
Remarque : Il ne faut pas confondre disjoint et distinct.
3.5 Couples, p−uplets et produit cartésien
Définition 22.
Soient E et F deux ensembles.
On appelle produit cartésien de E et F l’ensemble défini par
E × F = {(x, y), x ∈ E, y ∈ F }
Les éléments de E × F sont appelés des couples.
Lorsque E = F , on note E 2 plutôt que E × E.
S. Freyssinet BCPST 1.1 2021−2022
10
Exemple 18: Pour E = {a, 5} et F = {3, b}, E × F = {(a, 3), (a, b), (5, 3), (5, b)} et
F ×E ={
Exemple 19: Proposer un élément de N × P([0; 1]).
Définition 23.
Soit E un ensemble. Soit p ∈ N, n ≥ 2.
On appelle n−uplet de E (ou p−liste la donnée de p éléments de E dans un ordre précis.
On note E p l’ensemble des p−uplets de E.
E p = {(x1 , . . . , xp ), ∀i ∈ [[1, p]], xi ∈ E}
Exemple 20: (2,2,3,5) est un 4−uplet de l’ensemble E = {1, 2, 3, 4, 5}.
Remarque : On imagine un tirage avec remise dans l’ensemble E.
Remarque : L’ordre est très important. Si a 6= b alors (a, b) 6= (b, a) et {a, b} = {b, a}.
4 Différents modes de raisonnement
4.1 Démontrer une implication
Methode 1.
Pour démontrer une implication de la forme A ⇒ B,
• On suppose que l’assertion A est vraie
• On montrer qu’elle implique A1 , qui implique A2 , . . .
• on arrive à l’assertion B
Exemple 21: Démontrer que Si 6 divise n alors n est pair.
Théorème 11.
Soient A et B deux assertions.
L’implication A ⇒ B et sa contraposée eB ⇒eA sont équivalentes.
Exemple 22: Montrer que ∀n ∈ N, n2 pair ⇒ n pair .
4.2 Démontrer une équivalence
Methode 2.
Pour démontrer une équivalence A ⇔ B,
• on montre une double implication A ⇒ B et B ⇒ A.
• on montrer que A est équivalente à A1 , qui est équivalente à A2 , . . . , qui est équivalente à B.
Exemple 23: Démontrer qu’un produit de deux entiers est impair si, et seulement si, les deux entiers sont
impairs.
S. Freyssinet BCPST 1.1 2021−2022
11
4.3 Raisonnement par récurrence
Il s’agit d’un raisonnement qui convient pour démontrer que propositions de la forme suivante :
∀n ∈ N, P (n).
∀n ≥ n0 , P (n).
Théorème 12.
Soit P une assertion définie sur N. Si les deux conditions suivantes sont vérifiées
• ∃ n0 ∈ N, P (n0 )
• ∀ n ≥ n0 , P (n) ⇒ P (n + 1)
Alors, la propriété P est vraie sur N : ∀n ≥ n0 , P (n).
Exemple 24: Démontrer que ∀n ∈ N, 10n − 1 est un multiple de 9.
Remarque : Il se peut que P (n) ne suffise pas pour obtenir P (n + 1). On fait alors une récurrence forte.
Théorème 13.
Soient P une assertion définie sur N. Si les deux conditions suivantes sont vérifiées
• ∃ n0 ∈ N, P (n0 )
• ∀ n ≥ n0 , P (n0 ) ∧ · · · ∧ P (n) ⇒ P (n + 1)
Alors, la propriété P est vraie sur tout N : ∀n ∈ N, P (n).
S. Freyssinet BCPST 1.1 2021−2022