Ce chapitre de logique et ensembles ouvre la première année de licence. Il fixe le langage dans lequel s’écrivent toutes les mathématiques du supérieur. Vous y verrez d’abord les connecteurs logiques et leurs tables de vérité, puis l’implication, sa réciproque et sa contraposée. Ensuite viennent les quantificateurs et la façon de nier une phrase qui en contient plusieurs.
Le cours présente aussi les grands modes de raisonnement : direct, par contraposition, par l’absurde et par analyse-synthèse. Enfin, il décrit les opérations sur les ensembles, les lois de De Morgan, l’ensemble des parties, le produit cartésien et les fonctions indicatrices.
Ces outils servent partout ensuite. En effet, la définition d’une limite, la continuité ou l’algèbre linéaire reposent sur des quantificateurs bien placés. De plus, chaque démonstration de partiel se juge sur la clarté du raisonnement choisi.
Pour vous entraîner ensuite, travaillez les exercices de maths en L1 sur logique et ensembles.
I. Assertions et connecteurs logiques
Toute démonstration manipule des énoncés dont on peut dire s’ils sont vrais ou faux. Avant de raisonner, il faut donc fixer ce vocabulaire. Ce premier paragraphe définit les assertions, puis les connecteurs qui permettent de les combiner.
1. Assertions
Une assertion (ou proposition logique) est un énoncé mathématique qui est soit vrai, soit faux, sans autre possibilité. Sa valeur de vérité se note V (vrai) ou F (faux).
« \(7\) est un nombre premier » est une assertion vraie. De même, « \(2^{10} < 1000\) » est une assertion fausse, car \(2^{10} = 1024\). En revanche, « \(x > 3\) » n’est pas une assertion tant que \(x\) n’est pas fixé : c’est un prédicat, dont la vérité dépend de \(x\).
2. Les connecteurs
À partir de deux assertions \(P\) et \(Q\), on fabrique de nouvelles assertions. Leur valeur de vérité ne dépend que de celles de \(P\) et de \(Q\). C’est pourquoi on les définit par une table de vérité, qui liste les quatre cas possibles.
La négation « non \(P\) », notée \(\neg P\), est vraie exactement quand \(P\) est fausse. La conjonction « \(P\) et \(Q\) », notée \(P \wedge Q\), est vraie quand les deux sont vraies. La disjonction « \(P\) ou \(Q\) », notée \(P \vee Q\), est vraie quand au moins l’une des deux est vraie.
\[\begin{array}{|c|c|c|c|c|c|}
\hline P Q \neg P P \wedge Q P \vee Q P \Rightarrow Q \\
\hline \text{V} \text{V} \text{F} \text{V} \text{V} \text{V} \\
\text{V} \text{F} \text{F} \text{F} \text{V} \text{F} \\
\text{F} \text{V} \text{V} \text{F} \text{V} \text{V} \\
\text{F} \text{F} \text{V} \text{F} \text{F} \text{V} \\
\hline \end{array}\]
La dernière colonne, celle de l’implication, est étudiée au paragraphe II.
Le « ou » mathématique est inclusif. Ainsi, « \(P\) ou \(Q\) » reste vrai lorsque \(P\) et \(Q\) sont vraies toutes les deux. Le « ou exclusif » du langage courant (fromage ou dessert) n’est pas le « ou » des mathématiques.
3. Tautologies et règles de calcul
Deux assertions composées sont dites logiquement équivalentes quand elles ont la même table de vérité. Une tautologie est une assertion composée qui est vraie dans tous les cas, quelles que soient les valeurs de ses composantes.
Pour toutes assertions \(P\), \(Q\), \(R\), on a les équivalences suivantes :
- double négation : \(\neg(\neg P) \equiv P\) ;
- lois de De Morgan : \(\neg(P \wedge Q) \equiv (\neg P) \vee (\neg Q)\) et \(\neg(P \vee Q) \equiv (\neg P) \wedge (\neg Q)\) ;
- distributivité : \(P \wedge (Q \vee R) \equiv (P \wedge Q) \vee (P \wedge R)\) et \(P \vee (Q \wedge R) \equiv (P \vee Q) \wedge (P \vee R)\) ;
- tiers exclu : \(P \vee \neg P\) est une tautologie.
Chaque équivalence se vérifie sur une table de vérité. Par exemple, \(\neg(P \wedge Q)\) est fausse seulement quand \(P\) et \(Q\) sont vraies. De même, \((\neg P) \vee (\neg Q)\) est fausse seulement quand \(\neg P\) et \(\neg Q\) sont fausses, c’est-à-dire quand \(P\) et \(Q\) sont vraies. Les deux tables coïncident donc. Les autres lignes se traitent de la même façon ; pour trois assertions, la table compte \(2^3 = 8\) lignes.
II. Implication, contraposée et équivalence
L’implication est le connecteur central des démonstrations. Elle est aussi la source de la plupart des erreurs de rédaction. C’est pourquoi on la définit avec soin.
1. L’implication
L’implication « \(P \Rightarrow Q\) » est l’assertion \((\neg P) \vee Q\). Elle est fausse dans un seul cas : \(P\) vraie et \(Q\) fausse. On lit « \(P\) implique \(Q\) » ou « si \(P\), alors \(Q\) ». On dit aussi que \(P\) est une condition suffisante pour \(Q\), et que \(Q\) est une condition nécessaire pour \(P\).
Quand \(P\) est fausse, l’implication \(P \Rightarrow Q\) est vraie, quelle que soit \(Q\). Par exemple, « si \(1 = 2\), alors la Lune est un fromage » est une implication vraie. Autrement dit, une implication ne dit rien de \(Q\) lorsque l’hypothèse n’est pas satisfaite.
2. Réciproque et contraposée
La réciproque de \(P \Rightarrow Q\) est \(Q \Rightarrow P\). Sa contraposée est \((\neg Q) \Rightarrow (\neg P)\). L’équivalence \(P \Leftrightarrow Q\) est l’assertion \((P \Rightarrow Q) \wedge (Q \Rightarrow P)\) ; elle est vraie quand \(P\) et \(Q\) ont la même valeur de vérité.
Une implication et sa contraposée sont logiquement équivalentes : \[(P \Rightarrow Q) \equiv (\neg Q \Rightarrow \neg P).\] En revanche, une implication et sa réciproque ne le sont pas en général.
Par définition, \(\neg Q \Rightarrow \neg P\) s’écrit \(\neg(\neg Q) \vee \neg P\), soit \(Q \vee \neg P\) grâce à la double négation. Or la disjonction est commutative, donc on retrouve \(\neg P \vee Q\), c’est-à-dire \(P \Rightarrow Q\). Pour la réciproque, il suffit d’un cas : avec \(P\) fausse et \(Q\) vraie, \(P \Rightarrow Q\) est vraie mais \(Q \Rightarrow P\) est fausse.
On peut visualiser une implication entre prédicats comme une inclusion. En effet, dire que « \(x > 2 \Rightarrow x^2 > 4\) » pour tout réel \(x\), c’est dire que l’ensemble des \(x\) vérifiant \(x > 2\) est contenu dans l’ensemble des \(x\) vérifiant \(x^2 > 4\). Comme le montre la figure ci-dessous, la réciproque est fausse : le réel \(-3\) vérifie \(x^2 > 4\) sans vérifier \(x > 2\).
Pour un entier \(n\), l’implication « \(n\) multiple de \(4\) \(\Rightarrow\) \(n\) pair » est vraie. Sa contraposée, « \(n\) impair \(\Rightarrow\) \(n\) non multiple de \(4\) », est vraie aussi. Cependant, sa réciproque « \(n\) pair \(\Rightarrow\) \(n\) multiple de \(4\) » est fausse, comme le montre \(n = 6\).
III. Quantificateurs et langage formel
Les énoncés d’analyse et d’algèbre portent presque toujours sur une infinité d’objets. Les quantificateurs permettent de les écrire sans ambiguïté.
1. Les deux quantificateurs
Soit \(P(x)\) un prédicat portant sur les éléments \(x\) d’un ensemble \(E\).
- « \(\forall x \in E,\ P(x)\) » signifie que \(P(x)\) est vraie pour tous les éléments \(x\) de \(E\) (quantificateur universel).
- « \(\exists x \in E,\ P(x)\) » signifie que \(P(x)\) est vraie pour au moins un élément \(x\) de \(E\) (quantificateur existentiel).
- « \(\exists ! x \in E,\ P(x)\) » signifie qu’il existe un et un seul tel élément.
La variable quantifiée est muette : \(\forall x \in \mathbb{R},\ x^2 \geq\, 0\) et \(\forall t \in \mathbb{R},\ t^2 \geq\, 0\) disent la même chose. De plus, elle n’a plus de sens hors de la phrase. On n’écrit donc jamais « \(x\) » après la phrase sans l’avoir de nouveau introduit.
2. L’ordre des quantificateurs
Deux quantificateurs de même nature commutent. En revanche, on ne peut pas échanger un \(\forall\) et un \(\exists\) sans changer le sens. Dans « \(\forall x,\ \exists y\) », le \(y\) peut dépendre de \(x\). Au contraire, dans « \(\exists y,\ \forall x\) », le même \(y\) convient pour tous les \(x\).
L’assertion \(\forall n \in \mathbb{N},\ \exists m \in \mathbb{N},\ m > n\) est vraie : il suffit de prendre \(m = n + 1\). En revanche, \(\exists m \in \mathbb{N},\ \forall n \in \mathbb{N},\ m > n\) est fausse. En effet, un tel \(m\) vérifierait \(m > m\) en prenant \(n = m\). Ainsi, la première phrase dit que \(\mathbb{N}\) n’a pas de plus grand élément, alors que la seconde affirme l’existence d’un majorant strict de \(\mathbb{N}\) dans \(\mathbb{N}\).
On a toujours \((\exists y,\ \forall x,\ P(x, y)) \Rightarrow (\forall x,\ \exists y,\ P(x, y))\). La réciproque est fausse en général.
3. Négation d’une phrase quantifiée
\[\neg(\forall x \in E,\ P(x)) \equiv \exists x \in E,\ \neg P(x) \qquad \neg(\exists x \in E,\ P(x)) \equiv \forall x \in E,\ \neg P(x).\]
Autrement dit, pour montrer qu’une propriété universelle est fausse, il suffit d’exhiber un contre-exemple. Pour une phrase à plusieurs quantificateurs, on applique la règle de proche en proche.
Pour nier une phrase quantifiée :
- on remplace chaque \(\forall\) par \(\exists\) et chaque \(\exists\) par \(\forall\), sans changer l’ordre ni les ensembles ;
- on nie la propriété finale : \(\leq\,\) devient \(>\), « et » devient « ou », et une implication \(A \Rightarrow B\) devient \(A \wedge \neg B\).
Une fonction \(f : \mathbb{R} \to \mathbb{R}\) est majorée si \(\exists M \in \mathbb{R},\ \forall x \in \mathbb{R},\ f(x) \leq\, M\). Par conséquent, \(f\) n’est pas majorée si et seulement si \[\forall M \in \mathbb{R},\ \exists x \in \mathbb{R},\ f(x) > M.\] De même, la suite \((u_n)\) converge vers \(\ell\) si \(\forall \varepsilon > 0,\ \exists N \in \mathbb{N},\ \forall n \geq\, N,\ |u_n – \ell| \leq\, \varepsilon\). Sa négation s’écrit donc \(\exists \varepsilon > 0,\ \forall N \in \mathbb{N},\ \exists n \geq\, N,\ |u_n – \ell| > \varepsilon\).
4. Traduire un énoncé en langage formel
Traduire, c’est repérer les objets, leur ensemble et le type de quantification. Ensuite, on écrit la phrase de gauche à droite, dans l’ordre où les objets sont choisis. Par exemple, « tout réel positif est un carré » se traduit par \(\forall x \in \mathbb{R}_+,\ \exists y \in \mathbb{R},\ x = y^2\). De même, « la fonction \(f\) s’annule » devient \(\exists x \in \mathbb{R},\ f(x) = 0\).
Les symboles \(\forall\), \(\exists\), \(\Rightarrow\) ne sont pas des abréviations à glisser dans une phrase française. Dans une copie, on écrit soit une phrase formelle complète, soit une phrase en français. Ainsi, « \(\forall\) les réels, ils sont positifs » n’est ni l’un ni l’autre.
IV. Les modes de raisonnement
Démontrer une assertion, c’est l’établir à partir des axiomes et des résultats déjà démontrés, par des règles logiques admises. Plusieurs schémas reviennent sans cesse. Il faut savoir les reconnaître et les rédiger proprement.
1. Raisonnement direct et disjonction de cas
Pour prouver \(P \Rightarrow Q\) directement, on suppose \(P\) vraie et on en déduit \(Q\). Pour prouver « \(\forall x \in E,\ P(x)\) », on commence par « Soit \(x \in E\) » : l’élément est quelconque, donc la conclusion vaut pour tous. Enfin, la disjonction de cas sépare l’étude en plusieurs cas qui recouvrent toutes les situations.
Montrons que, pour tout entier \(n\), le produit \(n(n+1)\) est pair. Soit \(n \in \mathbb{Z}\). Si \(n\) est pair, alors \(n(n+1)\) est pair car \(n\) l’est. Sinon, \(n\) est impair, donc \(n + 1\) est pair et le produit aussi. Dans les deux cas, \(n(n+1)\) est pair.
2. Raisonnement par contraposition
D’après le théorème du paragraphe II, prouver \(P \Rightarrow Q\) revient à prouver \(\neg Q \Rightarrow \neg P\). On procède ainsi lorsque la négation de \(Q\) fournit une information plus facile à exploiter.
Montrons que si \(n^2\) est pair, alors \(n\) est pair. Raisonnons par contraposition : supposons \(n\) impair et écrivons \(n = 2k + 1\) avec \(k \in \mathbb{Z}\). Alors \(n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1\), donc \(n^2\) est impair. La contraposée est établie, donc l’implication aussi.
3. Raisonnement par l’absurde
Pour prouver \(P\), on suppose \(\neg P\) et on aboutit à une contradiction, c’est-à-dire à une assertion de la forme \(R \wedge \neg R\). Comme \(\neg P\) conduit au faux, \(P\) est vraie.
Le réel \(\sqrt{2}\) est irrationnel.
Supposons par l’absurde que \(\sqrt{2} = \dfrac{p}{q}\) avec \(p, q\) entiers naturels non nuls et la fraction irréductible. Alors \(p^2 = 2q^2\), donc \(p^2\) est pair. D’après l’exemple précédent, \(p\) est pair : \(p = 2k\). Ensuite, \(4k^2 = 2q^2\) donne \(q^2 = 2k^2\), donc \(q\) est pair lui aussi. Ainsi, \(2\) divise \(p\) et \(q\), ce qui contredit l’irréductibilité. Par conséquent, \(\sqrt{2}\) est irrationnel.
Ne confondez pas absurde et contraposition. Dans la contraposition, on suppose \(\neg Q\) et on démontre \(\neg P\), sans contradiction. Dans l’absurde, on suppose à la fois \(P\) et \(\neg Q\), puis on cherche une contradiction quelconque. La rédaction doit annoncer clairement le choix fait.
4. Raisonnement par analyse-synthèse
Ce raisonnement sert à déterminer tous les objets vérifiant une propriété, ou à prouver l’existence et l’unicité d’un objet. Il se déroule en deux temps bien séparés.
- Analyse : on suppose qu’un objet convient et on en déduit des conditions nécessaires, jusqu’à obtenir une forme explicite. Cette étape prouve l’unicité, ou restreint la liste des candidats.
- Synthèse : on vérifie que les candidats obtenus conviennent réellement. Cette étape prouve l’existence.
- Conclusion : on énonce l’ensemble exact des solutions.
Montrons que toute fonction \(f : \mathbb{R} \to \mathbb{R}\) s’écrit de façon unique \(f = g + h\), avec \(g\) paire et \(h\) impaire.
Analyse. Si \(f = g + h\) convient, alors pour tout \(x\), \(f(x) = g(x) + h(x)\) et \(f(-x) = g(x) – h(x)\). En ajoutant puis en retranchant, on obtient \[g(x) = \frac{f(x) + f(-x)}{2}, \qquad h(x) = \frac{f(x) – f(-x)}{2}.\] Ainsi, \(g\) et \(h\) sont imposées : il y a au plus une décomposition.
Synthèse. Définissons \(g\) et \(h\) par ces formules. D’abord, \(g(-x) = g(x)\) et \(h(-x) = -h(x)\). Ensuite, \(g(x) + h(x) = f(x)\). La décomposition existe donc, et elle est unique.
Pour choisir un type de raisonnement, observez la forme de l’énoncé.
- Énoncé universel « \(\forall x, P(x)\) » : on fixe \(x\) quelconque ; pour le réfuter, un contre-exemple suffit.
- Implication dont la conclusion est négative (« n’est pas », « est différent de ») : la contraposition ou l’absurde sont souvent efficaces.
- Énoncé d’impossibilité ou d’irrationalité : l’absurde est naturel.
- « Trouver tous les… » ou « existe un unique… » : l’analyse-synthèse.
V. Ensembles et opérations ensemblistes
La théorie des ensembles fournit le cadre de tous les objets mathématiques. On adopte ici un point de vue intuitif : un ensemble est une collection d’objets, appelés ses éléments.
1. Appartenance, inclusion, égalité
On note \(x \in E\) le fait que \(x\) est un élément de \(E\). L’ensemble vide \(\varnothing\) ne contient aucun élément. Un ensemble se décrit en extension, comme \(\{1, 2, 3\}\), ou en compréhension, comme \(\{x \in \mathbb{R} \mid x^2 \leq\, 4\}\). On dit que \(A\) est inclus dans \(B\), et on note \(A \subset B\), si \(\forall x,\ (x \in A \Rightarrow x \in B)\).
Deux ensembles sont égaux si et seulement si chacun est inclus dans l’autre : \[A = B \Leftrightarrow (A \subset B \text{ et } B \subset A).\] De plus, l’inclusion est transitive : si \(A \subset B\) et \(B \subset C\), alors \(A \subset C\).
2. Union, intersection, complémentaire
Dans toute la suite, \(A\) et \(B\) sont des parties d’un ensemble \(E\), appelé ensemble de référence.
- Réunion : \(A \cup B = \{x \in E \mid x \in A \text{ ou } x \in B\}\).
- Intersection : \(A \cap B = \{x \in E \mid x \in A \text{ et } x \in B\}\). Si \(A \cap B = \varnothing\), on dit que \(A\) et \(B\) sont disjoints.
- Complémentaire de \(A\) dans \(E\) : \(\overline{A} = \{x \in E \mid x \notin A\}\), aussi noté \(E \setminus A\) ou \(A^c\).
- Différence : \(A \setminus B = \{x \in A \mid x \notin B\} = A \cap \overline{B}\).
Les diagrammes de Venn représentent ces opérations par des régions du plan. Ils guident l’intuition, comme le montre la figure ci-dessous, mais ils ne remplacent pas une démonstration.
Chaque opération ensembliste traduit un connecteur logique : la réunion correspond à « ou », l’intersection à « et », le complémentaire à « non ». Par conséquent, les règles du paragraphe I se transportent aux ensembles.
Pour toutes parties \(A\), \(B\), \(C\) de \(E\) :
- \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\) et \(A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\) ;
- \(\overline{\overline{A}} = A\) ;
- lois de De Morgan : \(\overline{A \cup B} = \overline{A} \cap \overline{B}\) et \(\overline{A \cap B} = \overline{A} \cup \overline{B}\).
Prouvons la première loi de De Morgan. Soit \(x \in E\). On a les équivalences \[x \in \overline{A \cup B} \Leftrightarrow \neg(x \in A \vee x \in B) \Leftrightarrow (x \notin A) \wedge (x \notin B) \Leftrightarrow x \in \overline{A} \cap \overline{B}.\] La deuxième équivalence est la loi de De Morgan logique. Les deux ensembles ont donc les mêmes éléments. La seconde loi s’en déduit en appliquant la première à \(\overline{A}\) et \(\overline{B}\), puis en passant au complémentaire.
La figure suivante illustre la première loi : la zone hors de \(A\) et la zone hors de \(B\) ont pour partie commune exactement l’extérieur de \(A \cup B\).
Pour démontrer une égalité d’ensembles \(X = Y\), deux voies sont possibles.
- Double inclusion : on écrit « Soit \(x \in X\) » et on montre \(x \in Y\), puis on fait l’inverse.
- Chaîne d’équivalences : on montre \(x \in X \Leftrightarrow x \in Y\) pour tout \(x\), en justifiant chaque étape.
Pour une inclusion seule, on n’écrit que la première moitié. Pour réfuter une égalité, un contre-exemple explicite suffit.
Montrons que \(A \setminus (A \setminus B) = A \cap B\). Soit \(x \in E\). Alors \(x \in A \setminus (A \setminus B)\) équivaut à « \(x \in A\) et non(\(x \in A\) et \(x \notin B\)) ». Autrement dit, « \(x \in A\) et (\(x \notin A\) ou \(x \in B\)) ». Or le cas \(x \in A\) et \(x \notin A\) est impossible. Il reste « \(x \in A\) et \(x \in B\) », d’où l’égalité.
VI. Ensemble des parties et produit cartésien
Deux constructions fabriquent de nouveaux ensembles à partir d’anciens. Elles serviront pour les applications, les relations et les probabilités.
1. Ensemble des parties
L’ensemble des parties de \(E\), noté \(\mathcal{P}(E)\), est l’ensemble dont les éléments sont les parties de \(E\) : \[A \in \mathcal{P}(E) \Leftrightarrow A \subset E.\] En particulier, \(\varnothing \in \mathcal{P}(E)\) et \(E \in \mathcal{P}(E)\).
Pour \(E = \{a, b, c\}\), on obtient huit parties : \[\mathcal{P}(E) = \{\varnothing, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\}\}.\] Plus généralement, si \(E\) a \(n\) éléments, \(\mathcal{P}(E)\) en a \(2^n\) : pour construire une partie, on décide pour chaque élément s’il y figure ou non.
La figure ci-dessous range ces huit parties selon leur nombre d’éléments. Un trait relie deux parties quand la plus petite est incluse dans la plus grande avec un élément de moins.
Il faut distinguer \(a \in E\) et \(\{a\} \subset E\), ou encore \(\{a\} \in \mathcal{P}(E)\). De même, \(\varnothing\) n’a aucun élément, alors que \(\{\varnothing\}\) en a un. Par exemple, \(\mathcal{P}(\varnothing) = \{\varnothing\}\).
2. Produit cartésien
Le produit cartésien de \(A\) et \(B\) est l’ensemble des couples \[A \times B = \{(a, b) \mid a \in A,\ b \in B\}.\] Deux couples sont égaux si et seulement si \((a, b) = (a^{\prime}, b^{\prime}) \Leftrightarrow (a = a^{\prime} \text{ et } b = b^{\prime})\). On note \(A^2 = A \times A\), et plus généralement \(A^n\) l’ensemble des \(n\)-uplets.
Un couple est ordonné : \((1, 2) \neq (2, 1)\), alors que \(\{1, 2\} = \{2, 1\}\). Si \(A\) et \(B\) sont finis, \(A \times B\) a \(\operatorname{card}(A) \times \operatorname{card}(B)\) éléments. Comme le montre la figure ci-dessous, un produit fini se représente par une grille. De même, un produit d’intervalles se représente par un rectangle du plan \(\mathbb{R}^2\).
Pour toutes parties \(A, C\) de \(E\) et \(B, D\) de \(F\) : \[(A \times B) \cap (C \times D) = (A \cap C) \times (B \cap D).\] En revanche, \((A \times B) \cup (C \times D)\) est seulement inclus dans \((A \cup C) \times (B \cup D)\), en général strictement.
VII. Fonctions indicatrices
Les fonctions indicatrices transforment les calculs sur les ensembles en calculs sur des nombres. Elles donnent des preuves courtes et sûres.
Soit \(A\) une partie de \(E\). La fonction indicatrice de \(A\) est la fonction \(\mathbf{1}_A : E \to \{0, 1\}\) définie par \[\mathbf{1}_A(x) = \begin{cases} 1 \text{si } x \in A, \\ 0 \text{si } x \notin A. \end{cases}\]
Pour toutes parties \(A\), \(B\) de \(E\) :
- \(A = B \Leftrightarrow \mathbf{1}_A = \mathbf{1}_B\) et \(A \subset B \Leftrightarrow \mathbf{1}_A \leq\, \mathbf{1}_B\) ;
- \(\mathbf{1}_{A \cap B} = \mathbf{1}_A \mathbf{1}_B\) et \(\mathbf{1}_{\overline{A}} = 1 – \mathbf{1}_A\) ;
- \(\mathbf{1}_{A \cup B} = \mathbf{1}_A + \mathbf{1}_B – \mathbf{1}_A \mathbf{1}_B\) ;
- \(\mathbf{1}_A^2 = \mathbf{1}_A\), car \(0^2 = 0\) et \(1^2 = 1\).
Soit \(x \in E\). Le produit \(\mathbf{1}_A(x)\mathbf{1}_B(x)\) vaut \(1\) si et seulement si les deux facteurs valent \(1\), c’est-à-dire si \(x \in A \cap B\). Ensuite, \(1 – \mathbf{1}_A(x)\) vaut \(1\) exactement quand \(x \notin A\). Enfin, par De Morgan, \(\mathbf{1}_{A \cup B} = 1 – \mathbf{1}_{\overline{A} \cap \overline{B}} = 1 – (1 – \mathbf{1}_A)(1 – \mathbf{1}_B)\). En développant, on obtient la formule annoncée.
La figure ci-dessous montre, sur la droite réelle, les indicatrices de deux intervalles et de leur intersection. On y lit que le produit \(\mathbf{1}_A \mathbf{1}_B\) vaut \(1\) exactement sur \([2, 4]\).
Retrouvons la distributivité \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\). D’un côté, \(\mathbf{1}_{A \cap (B \cup C)} = \mathbf{1}_A(\mathbf{1}_B + \mathbf{1}_C – \mathbf{1}_B \mathbf{1}_C)\). De l’autre, \(\mathbf{1}_{(A \cap B) \cup (A \cap C)} = \mathbf{1}_A \mathbf{1}_B + \mathbf{1}_A \mathbf{1}_C – \mathbf{1}_A^2 \mathbf{1}_B \mathbf{1}_C\). Comme \(\mathbf{1}_A^2 = \mathbf{1}_A\), les deux fonctions coïncident. Les ensembles sont donc égaux.
Si \(E\) est fini, le cardinal d’une partie est la somme de son indicatrice : \(\operatorname{card}(A) = \sum_{x \in E} \mathbf{1}_A(x)\). En sommant la formule de la réunion, on obtient ainsi \(\operatorname{card}(A \cup B) = \operatorname{card}(A) + \operatorname{card}(B) – \operatorname{card}(A \cap B)\).
Ce qu’il faut retenir
- Une assertion est vraie ou fausse ; les connecteurs non, et, ou, \(\Rightarrow\), \(\Leftrightarrow\) se définissent par leur table de vérité.
- \(P \Rightarrow Q\) signifie \(\neg P \vee Q\) ; elle n’est fausse que si \(P\) est vraie et \(Q\) fausse.
- Une implication équivaut à sa contraposée, mais pas à sa réciproque.
- Pour nier une phrase quantifiée, on échange \(\forall\) et \(\exists\) sans changer leur ordre, puis on nie la propriété finale.
- L’ordre des quantificateurs compte : \(\exists y\, \forall x\) est plus fort que \(\forall x\, \exists y\).
- Raisonnements à maîtriser : direct, disjonction de cas, contraposition, absurde, contre-exemple, analyse-synthèse.
- Une égalité d’ensembles se prouve par double inclusion ou par chaîne d’équivalences ; une inclusion commence par « Soit \(x \in A\) ».
- Lois de De Morgan : \(\overline{A \cup B} = \overline{A} \cap \overline{B}\) et \(\overline{A \cap B} = \overline{A} \cup \overline{B}\).
- \(\mathcal{P}(E)\) a \(2^n\) éléments si \(E\) en a \(n\) ; \(A \times B\) est formé de couples ordonnés.
- Indicatrices : \(\mathbf{1}_{A \cap B} = \mathbf{1}_A \mathbf{1}_B\), \(\mathbf{1}_{\overline{A}} = 1 – \mathbf{1}_A\), \(\mathbf{1}_{A \cup B} = \mathbf{1}_A + \mathbf{1}_B – \mathbf{1}_A \mathbf{1}_B\).
Questions fréquentes sur logique et ensembles
Comment nier une phrase qui contient plusieurs quantificateurs ?
On remplace chaque « pour tout » par « il existe » et inversement, sans changer leur ordre ni les ensembles. Ensuite, on nie la propriété finale. Par exemple, la négation de \(\forall \varepsilon > 0,\ \exists N,\ \forall n \geq\, N,\ |u_n| \leq\, \varepsilon\) est \(\exists \varepsilon > 0,\ \forall N,\ \exists n \geq\, N,\ |u_n| > \varepsilon\).
Quelle différence entre raisonnement par l'absurde et par contraposition ?
Pour prouver \(P \Rightarrow Q\) par contraposition, on suppose \(\neg Q\) et on démontre directement \(\neg P\). Par l’absurde, on suppose à la fois \(P\) et \(\neg Q\), puis on cherche une contradiction quelconque. La contraposition est souvent plus claire quand la négation de la conclusion fournit une écriture exploitable.
Pourquoi l'analyse-synthèse a-t-elle besoin de deux étapes ?
L’analyse suppose qu’une solution existe et en déduit sa forme : elle donne des conditions nécessaires et prouve l’unicité. Elle ne garantit pas que le candidat obtenu convienne. C’est la synthèse qui vérifie qu’il est bien solution, et donc qu’il existe.
À quoi servent les fonctions indicatrices ?
Elles transforment les opérations ensemblistes en calculs sur des nombres égaux à 0 ou 1 : \(\mathbf{1}_{A \cap B} = \mathbf{1}_A \mathbf{1}_B\) et \(\mathbf{1}_{\overline{A}} = 1 – \mathbf{1}_A\). On prouve ainsi des égalités d’ensembles par un simple développement. Elles servent aussi à compter les éléments d’un ensemble fini et, plus tard, en probabilités.
Pour aller plus loin en L1
- Les énoncés : exercices de maths en L1 sur logique et ensembles
- Chapitre suivant : Applications et relations binaires
- Tester vos connaissances : QCM de maths en L1 par chapitre
- Le sommaire : tous les chapitres de maths de L1 et la licence de maths de L1 à L3
