Abderrazak Chakor 21 septembre 2023 Logique et ensembles Notes
Èléments de Logique
et
vocabulaire de la théories des ensembles
Les notions comprises dans ce chapitre introductif restent à jour tant que vous faîtes les
mathématiques plutôt tant que vous raisonnez.
On aura toujours au long de l’année des occasions pour leur mise en oeuvre
I - Èléments de Logique
1. 1. Construction de propositions et valeurs de vérité
Définition 1.1
Une proposition est une phrase (ou assertion) qui a un sens mathématique et qui est soit
vrai soit faux .
On dira qu’une proposition n’a que deux valeurs de vérité : vraie (notée V ) et fausse (notée
F ).
Si P désigne une assertion, on notera :P sa négation (lire « non P »)
Exemples 1.1
— « 2 est un entier pair » est une proposition vraie.
— « 3 est un entier pair » est une proposition fausse.
— « n est un entier pair » n’est pas une proposition car sa valeur de vérité dépend de la
valeur de n, un telle phrase est appelée prédicat portant sur la variable n à valeurs
dans Z , on pourrait noter ce prédicat P (n) par exemple.
Par convention :
Dans les raisonnements mathématiques on n’écrit que des propositions vraies.
Si P est une proposition, au lieu d’écrire «P est vraie », on écrit simplement « P », et au
lieu d’écrire « P est fausse », on écrit simplement « P » c’est à dire la négation
1. 2. Conjonction ,disjonctuon inclusive,implication et équivalence
Définition 1.2
1. Négation de P : P ou non(P ) ou ⌝P
2. Conjonction de P, Q : (P et Q) notée aussi P ∧ Q
3. Disjonction inclusive de P, Q : (P ou Q) notée aussi P ∨ Q
4. Implication de P, Q : (P ou Q) notée aussi P =⇒ Q
5. Equivalence de P, Q :P ⇐⇒ Q
et on a les tableaux de verité suivants :...
1. 3. Quelques Synonymes :Equivalences loqiques
Étant données trois propositions A, B et C
les propositions suivantes sont vraies indépendamment des valeurs de vérités de
A, B et C
1. [(A =⇒ B) ∧ (B =⇒ C) =⇒ (A =⇒ C)]
2. [(A =⇒ B) ⇐⇒ (B =⇒ A)]
3. [(A ⇐⇒ A)]
4. [(A ∧ B) ⇐⇒ (A ∨ B)](Premiére lois de Morgan)
5. [(A ∨ B) ⇐⇒ (A ∧ B)](Deusième lois de Morgan)
6. [(A =⇒ B) ⇐⇒ (A ∧ B)]
1
Abderrazak Chakor 21 septembre 2023 Logique et ensembles Notes
Exercice 1.1
Faites la preuve moyennant les tableaux de vérités
Définition 1.3
Vocabulaire :
— Certaines propositions sont déclarées vraies à priori : ce sont les axiomes.
Sinon la véracité d’une proposition doit résulter d’une démonstration
— Un théorème est une proposition vraie particulièrement importante.
— Un lemme est une proposition vraie, utile à la démonstration d’une proposition
plus importante.
— Un corollaire est une proposition vraie, conséquence immédiate d’une autre
proposition vraie.
— Une conjecture est une proposition qu’on pense généralement vraie, sans en
avoir de preuve.
1. 4. Quantificateurs
l’énoncé P (x) peut être vraie ou fausse pour un élément x de E .
On forme de nouvelles propositions en s’intéréssant aux éléments de E qui vérifient cet
énoncé
Définition 1.4
1. Quantificateur existentiel
[∃x ∈ E, P (x)] exprime qu’il éxiste au moins un élément de E qui vérifie la
propostion A
2. Quantificateur universel
[∀x ∈ E, P (x)] exprime que tous les éléments de E vérifient la propostion A
Propriété 1.1
Étant donné une propostion P (x, y) qui dépend de deux éléments x et y de E.
— [∃x ∈ E, ∃y ∈ E, P (x, y)] ⇐⇒ [∃y ∈ E, ∃x ∈ E, P (x, y)]
— [∀x ∈ E, ∀y ∈ E, P (x, y)] ⇐⇒ [∀y ∈ E, ∀x ∈ E, P (x, y)
— [∃x ∈ E, ∀y ∈ E, P (x, y)] et [∀y ∈ E, ∃x ∈ E, P (x, y)] ne veulent pas dire
la même chose
Exemples 1.2
Proposés par les étudiants.
Quatres règles à retenir
— Règle1 : Les quantificateurs sont écrits avant la proposion à quantifier.
— Règle 2 : ∀x ∈ E; P (x) est un condencé de ∀x, (x ∈ E =⇒ P (x))
— Règle 3 : Un objet affecté du quatifcateur ∃ dépend de tous les objets affectés de
∀ qui sont plassés avant lui dans le même énoncé.
— Règle 4 :Quantificateurs et négation
non(∀x ∈ E; P (x)) ⇐⇒ ∃x ∈ E; P (x)
non(∃x ∈ E; P (x)) ⇐⇒ ∀x ∈ E; P (x)
Exercice 1.2
Exprimer à l’aide des quantificateurs
— L’application f de R vers R n’ést pas nulle
— L’ application f de R vers R n’ést pas continue en un point 1
— La suite (un ) n’admet pas −2 pour limite
— L’application f de R vers R n’ést pas continue sur R
— La suite réelle (un ) est majorée
— La suite complexe (un ) est bornée
II - Méthodes pour faire une démonstrations et exemples :
2. 1. Pour démontrer une implication P =⇒ Q
1 Méthode directe :
on suppose que la proposition P est vraie (c’est l’hypothèse),
2 on cherche alors à
établir que nécessairement la proposition Q est vraie
Abderrazak Chakor 21 septembre 2023 Logique et ensembles Notes
2 Par l’absurde :
on suppose que P =⇒ Q, c’est à dire on suppose (P et Q)( c’est à dire P est
vraie et Q est fausse)
On montre alors que ceci conduit à une contradiction, ce qui entraîne que l’hy-
pothèse faite est fausse et par conséquent P =⇒ Q.
3 Par Contraposition
Pour démontre que (Q =⇒ P )
2. 2. Pour démontrer P ∨ Q
Comme la proposition P ∨ Q est équivalente à (P =⇒ Q) .
Par conséquent, démontrer P ∨ Q revient à démontrer (P =⇒ Q).
« If it’s not black it’s white»
2. 3. Pour démontrer une équivalence P ⇐⇒ Q
1. Par double implication :
on établit dans un premier temps que P =⇒ Q , puis dans un deuxième temps
on établit la réciproque, c’est à dire que Q =⇒ P
2. Méthode directe :
on suppose que la proposition P est vraie (hypothèse) puis on cherche à établir
que Q est vraie en s’assurant à chaque étape du raisonnement que l’équivalence est
conservée
2. 4. Raisonnement par absurde
Si le but est de démontrer qu’une proposition P est vraie
Raisonner par l’absurde c’est :
1. Supposer P
2. Cherche à obtenir une contradiction, c’est à dire : montrer que P =⇒ Q où Q
est une proposition dont sait qu’elle est fausse .
D’autre part P =⇒ Q impose que Q est vraie
Ainsi on aura Q et Q ce qui est impossible car une telle proposition est toujours
fausse : c’est le principe contradiction.
3. Conclure que P est vraie
Exercice 2.1
√
Montrons que 2 est un irrationnel par l’absurde
√ √ p
Solution : On suppose que 2 ∈ Q, on peut écrire 2 = avec p et q entiers
q
strictement positifs et premiers entre . En élevant au carré on a 2q = p2 , ce qui entraîne
2
que pest pair et donc p = 2a avec a entier, d’où 2a2 = q 2 , donc q est pair lui aussi et par
conséquent p et q ne sont pas premiers entre eux : contradiction
2. 5. Raisonnement par analyse-synthèse
Cette methode est utilisée lorsquon’on cherche la ou les solutions à un problème donné
Elle se fait en deux étapes qui sont :
1. Analyse : on suppose que l’on a une solution du problème et on cherche à
en déduire toutes les propriétés possibles de cette solution pour l’identifier au
mieux.(CN)
2. Synthèse : elle consiste à déterminer parmi tous les objets mathématiques ayant
les propriétés requises (obtenues lors de l’analyse), ceux qui sont effectivement
solutions du problème(CS)
Exercice 2.2
Montrons que toute fonction f : [0; 1] −→ R est la somme d’une fonction affine et
d’une fonction qui s’annule en 0 et en 1
Analyse : supposons qu’il existe une fonction g qui s’annule en 0 et en 1, ainsi que deux
réels a et b tels que ∀x ∈ R, f (x) = g(x) + ax + b.
En évaluant en 0 on a f (0) = b, en évaluant en 1 on a f (1) = a + b, d’où a = f (1) − b =
f (1) − f (0).
Maintenant que a et b sont connus, on en déduit que ∀x ∈ R, g(x) 3 = f (x) − ax − b
Abderrazak Chakor 21 septembre 2023 Logique et ensembles Notes
Synthèse : posons b = f (0), a = f (1) − f (0) et g : x 7−→ f (x) − ax − b. Il est clair
que f (x) = g(x) + ax + b, d’autre part g(0) = f (0) − b = 0 et g(1) = f (1) − a − b =
f (1) − f (1) + f (0) − f (0) = 0.
Donc a, b et g sont bien solution du problème et celle-ci est unique
Remarque 2.1
Un exemple de "démonstration" montrant que l’étape synthèse est indispensable.
√ √
Résoudre :x ∈ R / x−2= 2x − 1
Analyse :
Si x existe alors x − 2 = 2x − 1 donc x = −1
Synthèse : -1 n’est pas solution
Conclusion :Pas de solution
Exercice 2.3
Montrer que toute application de f de R vers R s’écrit d’une façon unique comme
somme d’une application paire g et d’une application impaire h
III - Notions ensemblistes
3. 1. Ensembles
Définition 3.1
— Un ensemble E est une collection d’objets , ceux-ci sont appelés éléments de E.
— Si x est un élément de E on écrira x ∈ E(se lit « x appartient à E »), dans le cas
contraire on écrira x ∈/ E.
— Si E n’a pas d’éléments on dira que c’est l’ensemble vide et on le notera ∅.
— un ensemle F est dit une partie de E si ses appartiennet à E et on note F ⊂ E
on lit «F est inclus dans E»
— Deux ensembles E et F sont dits égaux si et seulement si ils ont les mêmes
éléments, on écrira alors E = F
c’est à dire aussi F ⊂ E et E ⊂ F
3. 2. Intrsection -Réunion -Complémentaire
Définition 3.2
Soit E et F deux ensembles
1. L’ ensemble des éléments x qui appartiennent à la fois à E et à F s’ap-
pelle l’intersection de E et F on le note E ∩ F et on écrit E ∩ F =
{ x/(x ∈ E) ∧ (x ∈ F ) } = F ∩ E
si de plus E ∩ F = ∅ alors E et F sont dit disjoints
2. L’ ensemble des éléments x qui appartiennent à E ou à F s’appelle la réunion de
E et F on le note E ∪ F et on écrit E ∪ F = { x/(x ∈ E) ∨ (x ∈ F ) } =
F ∪E
A
3. Si A est une partie de E l’ensemble CE = { x ∈ E/x ∈ / A } = A est le
complémentaire de A dans E s’il n’ya pas d’ambiguité
Exemple 3.1
Déterminer E ∩ F et E ∪ F si E = { 1, 2, 3, 4, 5, 6 } et F = { 5, 6, 7, 8 }
Propriétés 3.1
A, B, C trois parties d’un ensemle E
1. A ∩ B = B ∩ A; (A ∩ B) ∩ C = A ∩ (B ∩ C)
2. A ∪ B = B ∪ A; (A ∪ B) ∪ C = A ∪ (B ∪ C)
3. A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) et A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
4. A ∩ A = ∅ et A ∪ A = E
5. A ∩ B = A ∪ B et A ∪ B = A ∩ B
6. A ⊂ B ⇔ A ∩ B = ∅
3. 3. Différence et différence symétrique de deux ensembles 4
Abderrazak Chakor 21 septembre 2023 Logique et ensembles Notes
Exercice 3.2
1. Déterminer P (E) l’ensemle de toutes les parties de E = { a, b, c }
2. Quel lien entre le nombre n des éléments de E et celui deP (E) ?
3. 5. Partition d’un ensemble
Définition 3.5
Soit E un ensemble non videT ⊂ P (E)
∀A ∈ T, A ̸= ∅
∀A, B ∈ T, (A ̸= B =⇒ A ∩ B = ∅)
T est une partition de E ⇔ S
A, = E
A∈T
Exemples 3.1
{ 2N, 2N + 1 } est une partion de N
{ { n } /n ∈ N } est une partion de N
{ Q, R\Q } est une partion de R
3. 6. Produit cartésien de deux ensembles E et F
Définition 3.6
E et F deux ensembles donnés.
On appelle produit cartesien de E et F l’ensemble E × F =
{ (x, y)/x ∈ E et y ∈ F }
Remarques 3.1
— E×F =F ×E ⇔E =F
— On définit de même le produit d’un nombre fini d’ensemles E1 , E2 , ..., Ep
E1 × E2 × ... × Ep = { (x1 , x2 , ..., xp )/∀i ∈ [[p, ]] , xi ∈ Ei }
Ainsi par exemple R × R × R se note R3 = { (x, y, z)/x, y, z ∈ R }
IV - L’ensemble des entiers naturels et raisonnement par récurrence
L’ensemble N des entiers naturels muni de l’ordre habituel étant supposé connu
4. 1. Propriétés fondamentales de N :Récurrence
Axiomes :
1. Toute partie non vide de N admet un plus petit élément
2. Toute partie non vide et majorée de N admet un plus grand élément
3. N n’ést pas de plus grand élément.
Théorème 4.1 Principe de récurrence
Soit A une partie de N .
0∈A
Si Alors A = N
∀n ∈ N , (n ∈ A => n + 1 ∈ A)
Corollaire 4.1 Récurrence simple
Soient n0 ∈ N et P (n) une propriété dépendant de l’entiern pour n ≥ n0
P (n0 )
Si Alors ∀n ≥ n0 ; P (n)
∀n ∈ N; [P (n) =⇒ P (n + 1)]
Exercices 4.1
Montrer par récurrence que :
n n(n + 1)
1. ∀n ∈ N∗ ,
P
k=
k=1 2
n n(n + 1)(2n + 1)
2. ∀n ∈ N∗ , k2 =
P
k=1 6
n
2
n(n + 1)
3. ∀n ∈ N∗ , k3 =
P
k=1 2
5
Abderrazak Chakor 21 septembre 2023 Logique et ensembles Notes
Corollaire 4.2 Récurrence forte
Soient n0 ∈ N et P (n) une propriété dépendant de l’entiern pour n ≥ n0
P (n0 )
Si alors ∀n ≥ n0 ; P (n)
∀n ≥ n0 ; [(∀k ∈ [[n0 , n]] , P (k)) =⇒ P (n + 1)]
Exercice 4.1
Montrer que tout entier supérieur ou égal à 2 admet un diviseur premier
Exercice 4.2
1. Montrer que ∀n ∈ N∗ ; ∃!(p, q) ∈ N2 tel que n = 2p (2q + 1)
2. Déduire que N2 et N sont en bijection
Exercice 4.3
1. Rappeler la définition d’un entier naturel premier
2. Montrer que tout entier naturel n ≥ 2 admet un diviseur premier
Exercice 4.4
Pn 1
Pour n entier n ≥ 2 on pose Sn =
k=1 k
1. Montrer que : ∀n > 1 , Sn est le quotient d’un entier impair et d’un entier pair
a 1 1
Indication : S2m = + Sm ; S2m+1 = S2m +
2b + 1 2 2m + 1
2. Déduire que ∀n > 1; Sn ∈ Q \ N
