Cours – Logique, ensembles et applications
Chapitre 01
ECS (1re année) — Chapitre 01. Connecteurs, quantificateurs, raisonnements, injections, surjections, bijections.
Ce chapitre a été réalisé conformément au programme marocain de mathématiques de la filière ECS.
1 Éléments de logique
1.1 Propositions et connecteurs
Définition 1.1 — (Proposition)
Une proposition est un énoncé mathématique qui est soit vrai, soit faux. On les note P, Q, R, etc.
Définition 1.2 — (Connecteurs logiques)
Soient P et Q deux propositions.
| Connecteur | Notation | Lecture |
|---|---|---|
| Négation | \neg P | « non P » |
| Conjonction | P \wedge Q | « P et Q » |
| Disjonction | P \vee Q | « P ou Q » |
| Implication | P \Rightarrow Q | « si P alors Q » |
| Équivalence | P \Leftrightarrow Q | « P si et seulement si Q » |
Proposition 1.1 — (Propriétés fondamentales)
Pour toutes propositions P, Q :
- P \Rightarrow Q est équivalente à (\neg Q) \Rightarrow (\neg P) (contraposée).
- \neg(P \wedge Q) est équivalente à (\neg P) \vee (\neg Q) (De Morgan).
- \neg(P \vee Q) est équivalente à (\neg P) \wedge (\neg Q).
1.2 Quantificateurs
Définition 1.3 — (Quantificateurs)
Soit E un ensemble et P(x) une proposition dépendant de x \in E.
- \forall x \in E,\; P(x) : « pour tout x de E, P(x) ».
- \exists x \in E,\; P(x) : « il existe un x de E tel que P(x) ».
Proposition 1.2 — (Négation)
\neg(\forall x \in E,\; P(x)) \iff \exists x \in E,\; \neg P(x) \neg(\exists x \in E,\; P(x)) \iff \forall x \in E,\; \neg P(x)
1.3 Méthodes de raisonnement
Méthode 1.1 — (Récurrence)
Pour montrer P(n) pour tout n \geq n_0 :
- Initialisation : montrer P(n_0).
- Hérédité : supposer P(n) et montrer P(n+1).
- Conclusion : par récurrence, P(n) pour tout n \geq n_0.
Méthode 1.2 — (Contraposée)
Pour montrer P \Rightarrow Q, on montre \neg Q \Rightarrow \neg P.
Méthode 1.3 — (Absurde)
Pour montrer P, on suppose \neg P et on aboutit à une contradiction.
Méthode 1.4 — (Analyse-synthèse)
Pour résoudre un problème d’existence et d’unicité :
- Analyse : supposer la solution existante et en déduire sa forme nécessaire.
- Synthèse : vérifier que l’objet construit est bien solution.
2 Ensembles
2.1 Opérations
Définition 2.1 — (Opérations sur les ensembles)
Soient A, B deux ensembles.
- A \cup B = \{x \mid x \in A \text{ ou } x \in B\}
- A \cap B = \{x \mid x \in A \text{ et } x \in B\}
- A \setminus B = \{x \mid x \in A \text{ et } x \notin B\}
- \overline{A} = E \setminus A (complémentaire dans E)
- A \times B = \{(a,b) \mid a \in A,\; b \in B\}
Proposition 2.1 — (Lois de De Morgan)
\overline{A \cup B} = \overline{A} \cap \overline{B} \qquad \text{et} \qquad \overline{A \cap B} = \overline{A} \cup \overline{B}
Définition 2.2 — (Ensemble des parties)
\mathcal{P}(E) désigne l’ensemble de tous les sous-ensembles de E. Si \mathrm{card}(E) = n, alors \mathrm{card}(\mathcal{P}(E)) = 2^n.
3 Applications
3.1 Définitions
Définition 3.1 — (Application)
Une application f : E \to F associe à tout x \in E un unique élément f(x) \in F.
- E est l’ensemble de départ.
- F est l’ensemble d’arrivée.
- f(A) = \{f(x) \mid x \in A\} est l’image de A \subset E.
- f^{-1}(B) = \{x \in E \mid f(x) \in B\} est l’image réciproque de B \subset F.
3.2 Injection, surjection, bijection
Définition 3.2 — (Injection)
f : E \to F est injective si : \forall x, x' \in E,\quad f(x) = f(x') \implies x = x'
Autrement dit, tout élément de F admet au plus un antécédent.
Définition 3.3 — (Surjection)
f : E \to F est surjective si : \forall y \in F,\quad \exists x \in E,\quad f(x) = y
Autrement dit, tout élément de F admet au moins un antécédent.
Définition 3.4 — (Bijection)
f : E \to F est bijective si elle est injective et surjective. Tout élément de F admet un unique antécédent. On note f^{-1} : F \to E la bijection réciproque.
Proposition 3.1 — (Propriétés)
Soient f : E \to F et g : F \to G.
- f et g injectives \implies g \circ f injective.
- f et g surjectives \implies g \circ f surjective.
- f et g bijectives \implies g \circ f bijective, avec (g \circ f)^{-1} = f^{-1} \circ g^{-1}.
- f bijective \iff f admet une application réciproque.
Proposition 3.2 — (Caractérisation ensembliste)
Soit f : E \to F.
- f injective \iff \forall A \subset E,\; f^{-1}(f(A)) = A.
- f surjective \iff \forall B \subset F,\; f(f^{-1}(B)) = B.
Exemple 3.1
Soit f : \mathbb{R} \to \mathbb{R} définie par f(x) = 2x - 3.
- Injective : f(x) = f(x') \Rightarrow 2x = 2x' \Rightarrow x = x'. ✓
- Surjective : pour tout y, x = \frac{y+3}{2} vérifie f(x) = y. ✓
- Donc f est bijective et f^{-1}(y) = \frac{y+3}{2}.
Exemple 3.2
Soit g : \mathbb{R} \to \mathbb{R} définie par g(x) = x^2.
- g n’est pas injective : g(1) = g(-1) = 1.
- g n’est pas surjective : -1 n’a pas d’antécédent.
- Mais g : [0, +\infty[ \to [0, +\infty[ est bijective, de réciproque x \mapsto \sqrt{x}.
Exemple 3.3 — (Application exponentielle)
\exp : \mathbb{R} \to ]0, +\infty[ est une bijection, de réciproque \ln : ]0, +\infty[ \to \mathbb{R}.
4 Exercices
Exercice 4.1
Nier les propositions suivantes :
- \forall x \in \mathbb{R},\; x^2 \geq 0.
- \exists x \in \mathbb{R},\; x^2 = -1.
- \forall \varepsilon > 0,\; \exists N \in \mathbb{N},\; \forall n \geq N,\; |u_n - \ell| < \varepsilon.
Exercice 4.2
Montrer par récurrence que pour tout n \in \mathbb{N}^* : \sum_{k=1}^n k = \frac{n(n+1)}{2}.
Exercice 4.3
Montrer par l’absurde que \sqrt{2} \notin \mathbb{Q}.
Exercice 4.4
Montrer par contraposée que si n^2 est pair, alors n est pair.
Exercice 4.5
Soient A, B, C trois ensembles. Montrer que A \cap (B \cup C) = (A \cap B) \cup (A \cap C).
Exercice 4.6
Soit f : \mathbb{R} \to \mathbb{R} définie par f(x) = \dfrac{x}{1+|x|}.
- Montrer que f est injective.
- Montrer que f n’est pas surjective.
- Montrer que f : \mathbb{R} \to ]-1,1[ est bijective et déterminer f^{-1}.
Exercice 4.7
Soit f : E \to F une application. Montrer que f est injective si et seulement si f^{-1}(f(A)) = A pour tout A \subset E.
Exercice 4.8
Soit f : \mathbb{N} \to \mathbb{Z} définie par f(n) = (-1)^n \lfloor n/2 \rfloor. Montrer que f est bijective.