Logique et ensembles : cours de maths Licence L1

Rate this post

Cours de maths en Licence L1 : Logique et ensembles — Zyro, l’explorateur de Planète Maths

Avant de démontrer quoi que ce soit en analyse, en algèbre ou en probabilités, il faut s’accorder sur un langage : savoir écrire une phrase mathématique sans ambiguïté, la nier correctement, choisir la bonne forme de raisonnement et manipuler des collections d’objets appelées ensembles. Ce chapitre installe ces outils, que vous réutiliserez dans toute la licence : connecteurs et quantificateurs, contraposée, absurde et récurrence, puis ensembles, produits, relations d’équivalence et relations d’ordre.

Sommaire

1. Propositions et connecteurs

Proposition

Une proposition est un énoncé mathématique qui est soit vrai (V), soit faux (F), jamais les deux. Ainsi « \(17\) est un nombre premier » est une proposition vraie, « \(2^{10} = 1000\) » une proposition fausse, alors que « \(x + 1 = 5\) » n’est pas une proposition tant que \(x\) n’est pas précisé.

À partir de propositions \(P\) et \(Q\), on en fabrique d’autres grâce aux connecteurs : la négation \(\neg P\) (« non \(P\) »), la conjonction \(P \land Q\) (« \(P\) et \(Q\) »), la disjonction \(P \lor Q\) (« \(P\) ou \(Q\) »), l’implication \(P \Rightarrow Q\) et l’équivalence \(P \Leftrightarrow Q\). Leur sens est entièrement décrit par une table de vérité.

\(P\)	\(Q\)	\(\neg P\)	\(P \land Q\)	\(P \lor Q\)	\(P \Rightarrow Q\)	\(P \Leftrightarrow 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

Deux pièges du langage courant

Le « ou » mathématique est inclusif : \(P \lor Q\) est vraie si l’une des deux, ou les deux, sont vraies. Et l’implication \(P \Rightarrow Q\) n’est fausse que dans un seul cas : \(P\) vraie et \(Q\) fausse. Une hypothèse fausse ne contredit donc jamais une implication : « si \(1 = 2\) alors la Lune est en fromage » est une implication vraie.

Exemple : nier une implication

Montrons que \(\neg(P \Rightarrow Q)\) équivaut à \(P \land \neg Q\). On compare les deux colonnes ligne par ligne : pour \((P,Q) = (\text{V},\text{V})\), l’implication est vraie donc sa négation est fausse, et \(P \land \neg Q\) est fausse ; pour \((\text{V},\text{F})\), l’implication est fausse donc sa négation est vraie, et \(P \land \neg Q\) est vraie ; pour \((\text{F},\text{V})\) et \((\text{F},\text{F})\), l’implication est vraie, sa négation fausse, et \(P \land \neg Q\) est fausse car \(P\) l’est. Les deux propositions ont la même table de vérité : elles sont équivalentes.

2. Quantificateurs

Quantificateurs

Le quantificateur universel \(\forall\) (« pour tout ») et le quantificateur existentiel \(\exists\) (« il existe ») permettent de parler d’une propriété \(P(x)\) qui dépend d’un élément \(x\) d’un ensemble \(E\). On écrit \(\forall x \in E,\ P(x)\) et \(\exists x \in E,\ P(x)\). La notation \(\exists !\) signifie « il existe un unique ».

Négation des quantificateurs

\[ \neg\big(\forall x \in E,\ P(x)\big) \iff \exists x \in E,\ \neg P(x) \qquad\text{et}\qquad \neg\big(\exists x \in E,\ P(x)\big) \iff \forall x \in E,\ \neg P(x). \]

Pour nier une phrase quantifiée, on échange donc chaque \(\forall\) avec \(\exists\) et on nie la propriété finale.

L’ordre des quantificateurs compte. Dans \(\mathbb{N}\), la phrase \(\forall n,\ \exists m,\ m > n\) est vraie (prendre \(m = n+1\)), tandis que \(\exists m,\ \forall n,\ m > n\) est fausse : elle affirmerait qu’un entier est strictement plus grand que tous les entiers, lui-même compris.

Exemple : nier une phrase quantifiée

Soit \(P\) : « \(\forall n \in \mathbb{N},\ n^2 \geqslant 2n\) ». Sa négation est « \(\exists n \in \mathbb{N},\ n^2 < 2n\) ». Pour \(n = 1\) on a \(1 < 2\) : la négation est vraie, donc \(P\) est fausse. Un seul exemple suffit à réfuter un \(\forall\) : on parle de contre-exemple. En revanche, des centaines de vérifications ne démontrent jamais un \(\forall\).

3. Contraposée et raisonnement par l’absurde

Contraposée

L’implication \(P \Rightarrow Q\) est équivalente à sa contraposée \(\neg Q \Rightarrow \neg P\). Elle n’est pas équivalente à sa réciproque \(Q \Rightarrow P\).

Exemple : démonstration par contraposée

Montrons que, pour \(n \in \mathbb{N}\), si \(n^2\) est impair alors \(n\) est impair. La contraposée est : si \(n\) est pair, alors \(n^2\) est pair. Or si \(n = 2k\), alors \(n^2 = 4k^2 = 2 \times 2k^2\) est bien pair. La contraposée est démontrée, donc l’implication initiale aussi.

Raisonnement par l’absurde

On suppose que la proposition à démontrer est fausse, c’est-à-dire que sa négation est vraie.
On déroule des déductions correctes à partir de cette hypothèse.
On aboutit à une contradiction (un résultat faux ou en conflit avec une hypothèse).
On conclut que l’hypothèse de départ était impossible : la proposition est vraie.

Exemple : démonstration par l’absurde

Montrons que la somme d’un rationnel \(r\) et d’un irrationnel \(x\) est irrationnelle. Supposons \(r + x = s\) rationnel. Alors \(x = s - r\) serait une différence de deux rationnels, donc un rationnel : contradiction avec l’irrationalité de \(x\). Ainsi \(r + x\) est irrationnel.

4. Raisonnement par récurrence

Principe de récurrence

Soit \(P(n)\) une propriété portant sur l’entier \(n \geqslant n_0\). Si \(P(n_0)\) est vraie (initialisation) et si, pour tout \(n \geqslant n_0\), \(P(n) \Rightarrow P(n+1)\) (hérédité), alors \(P(n)\) est vraie pour tout \(n \geqslant n_0\).

L’image est celle d’une file de dominos : le premier tombe, et chaque domino qui tombe fait tomber le suivant. Pour la récurrence forte, l’hérédité suppose \(P(k)\) vraie pour tous les \(k\) compris entre \(n_0\) et \(n\) ; c’est indispensable pour les suites définies par une relation à deux pas.

Exemple : une somme classique

Montrons que, pour tout \(n \geqslant 1\), \(1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}\).

Initialisation. Pour \(n = 1\), le membre de gauche vaut \(1\) et celui de droite \(\dfrac{1 \times 2}{2} = 1\).

Hérédité. Supposons la formule vraie au rang \(n\). Alors \(1 + \cdots + n + (n+1) = \dfrac{n(n+1)}{2} + (n+1) = \dfrac{(n+1)(n+2)}{2}\), c’est la formule au rang \(n+1\).

Conclusion. La formule est vraie pour tout \(n \geqslant 1\).

Oublier l’initialisation

Sans initialisation, l’hérédité ne prouve rien : la propriété « \(n = n+1\) » est héréditaire (si \(n = n+1\), alors \(n+1 = n+2\)) mais elle est fausse pour tout \(n\).

5. Ensembles et parties

Un ensemble est une collection d’objets appelés éléments. On écrit \(x \in E\) si \(x\) appartient à \(E\). L’ensemble \(A\) est inclus dans \(E\), noté \(A \subset E\), si tout élément de \(A\) est dans \(E\) : on dit que \(A\) est une partie de \(E\). L’ensemble de toutes les parties de \(E\) se note \(\mathcal{P}(E)\) ; il contient toujours \(\varnothing\) et \(E\).

Opérations

Pour \(A, B \subset E\) : l’intersection \(A \cap B = \{x \in E : x \in A \text{ et } x \in B\}\), la réunion \(A \cup B = \{x \in E : x \in A \text{ ou } x \in B\}\), la différence \(A \setminus B = \{x \in A : x \notin B\}\) et le complémentaire \(\overline{A} = E \setminus A\).

Lois de De Morgan et dénombrement

\[ \overline{A \cup B} = \overline{A} \cap \overline{B}, \qquad \overline{A \cap B} = \overline{A} \cup \overline{B}. \]

Si \(A\) et \(B\) sont finis : \(|A \cup B| = |A| + |B| - |A \cap B|\). Si \(E\) a \(n\) éléments, \(\mathcal{P}(E)\) en a \(2^n\).

Démontrer une égalité d’ensembles

Prendre un élément quelconque \(x\) du premier ensemble et montrer qu’il est dans le second : première inclusion.
Faire l’inverse : seconde inclusion.
Conclure à l’égalité, c’est la double inclusion.

Exemple : compter avec l’intersection

Dans \(E = \{1, 2, \ldots, 20\}\), soit \(A\) l’ensemble des multiples de \(3\) et \(B\) celui des multiples de \(4\). On a \(A = \{3, 6, 9, 12, 15, 18\}\), soit \(6\) éléments, et \(B = \{4, 8, 12, 16, 20\}\), soit \(5\) éléments. Leur intersection est \(\{12\}\) (multiples de \(12\)). Donc \(|A \cup B| = 6 + 5 - 1 = 10\), et \(|\overline{A \cup B}| = 20 - 10 = 10\) entiers ne sont multiples ni de \(3\) ni de \(4\).

6. Produit cartésien

Produit cartésien

Le produit cartésien de deux ensembles \(E\) et \(F\) est l’ensemble des couples \(E \times F = \{(x, y) : x \in E,\ y \in F\}\). Deux couples sont égaux si et seulement si leurs deux composantes sont égales, dans l’ordre : \((x, y) = (x', y') \iff x = x' \text{ et } y = y'\).

Pour \(E = \{1, 2, 3\}\) et \(F = \{a, b\}\), le produit \(E \times F\) comporte \(3 \times 2 = 6\) couples, visibles sur la grille ci-dessus. En général, \(|E \times F| = |E| \times |F|\). L’ordre compte : \((1, a) \in E \times F\) mais \((1, a) \notin F \times E\), donc \(E \times F \neq F \times E\) dès que les deux ensembles sont non vides et distincts. On note \(E^2 = E \times E\) ; le plan muni d’un repère est \(\mathbb{R}^2\).

7. Relations d’équivalence

Relation d’équivalence

Une relation \(\mathcal{R}\) sur un ensemble \(E\) est une relation d’équivalence si elle est : réflexive (\(x \,\mathcal{R}\, x\)), symétrique (\(x \,\mathcal{R}\, y \Rightarrow y \,\mathcal{R}\, x\)) et transitive (\(x \,\mathcal{R}\, y\) et \(y \,\mathcal{R}\, z\) \(\Rightarrow x \,\mathcal{R}\, z\)). La classe de \(x\) est \(\overline{x} = \{y \in E : y \,\mathcal{R}\, x\}\).

Partition en classes

Les classes d’équivalence sont non vides et deux classes sont soit égales, soit disjointes ; leur réunion est \(E\). Elles forment une partition de \(E\), et \(x \,\mathcal{R}\, y \iff \overline{x} = \overline{y}\).

Exemple : la congruence modulo 3

Sur \(\mathbb{Z}\), posons \(x \equiv y\) si \(3\) divise \(x - y\). Réflexivité : \(x - x = 0\) est divisible par \(3\). Symétrie : si \(3 \mid x - y\) alors \(3 \mid y - x\). Transitivité : si \(x - y = 3a\) et \(y - z = 3b\), alors \(x - z = 3(a+b)\). C’est une relation d’équivalence, qui possède exactement trois classes : \(\overline{0} = \{\ldots, -3, 0, 3, 6, \ldots\}\), \(\overline{1} = \{\ldots, -2, 1, 4, 7, \ldots\}\) et \(\overline{2} = \{\ldots, -4, -1, 2, 5, \ldots\}\), selon le reste dans la division par \(3\).

8. Relations d’ordre

Relation d’ordre

Une relation \(\preceq\) sur \(E\) est une relation d’ordre si elle est réflexive, antisymétrique (\(x \preceq y\) et \(y \preceq x\) \(\Rightarrow x = y\)) et transitive. Elle est totale si deux éléments quelconques sont toujours comparables, sinon l’ordre est partiel.

Dans \(E\) muni de \(\preceq\), un élément \(m\) est un plus petit élément s’il est inférieur à tous les autres, et un élément maximal si aucun élément distinct n’est au-dessus de lui. Un plus grand élément, s’il existe, est unique ; un élément maximal n’est pas forcément le plus grand.

Exemple : l’ordre de divisibilité

Sur \(\mathbb{N}^*\), la relation \(a \mid b\) (« \(a\) divise \(b\) ») est réflexive (\(a \mid a\)), antisymétrique (si \(a \mid b\) et \(b \mid a\) alors \(a \leqslant b\) et \(b \leqslant a\), donc \(a = b\)) et transitive. C’est un ordre partiel : \(4\) et \(6\) ne sont pas comparables car \(4 \nmid 6\) et \(6 \nmid 4\). Sur \(D = \{1, 2, 3, 4, 6, 12\}\), le plus petit élément est \(1\), le plus grand est \(12\).

Astuce de Zyro

Pour lire un diagramme de Hasse, montez de bas en haut : \(a \preceq b\) si l’on peut aller de \(a\) à \(b\) en suivant des segments qui montent. Deux éléments qu’aucun chemin montant ne relie sont incomparables !

À retenir

Une implication \(P \Rightarrow Q\) n’est fausse que si \(P\) est vraie et \(Q\) fausse ; elle équivaut à sa contraposée \(\neg Q \Rightarrow \neg P\), pas à sa réciproque.
Pour nier une phrase quantifiée, on échange \(\forall\) et \(\exists\) puis on nie la conclusion ; l’ordre des quantificateurs change le sens.
Un contre-exemple réfute un « pour tout » ; l’absurde suppose la négation et cherche une contradiction.
Une récurrence exige l’initialisation et l’hérédité.
Égalité d’ensembles : double inclusion. De Morgan : \(\overline{A \cup B} = \overline{A} \cap \overline{B}\). \(|\mathcal{P}(E)| = 2^{|E|}\), \(|E \times F| = |E||F|\).
Équivalence = réflexive, symétrique, transitive : ses classes partitionnent \(E\). Ordre = réflexive, antisymétrique, transitive ; total si tout couple est comparable.