Logique et ensembles

Fiches de cours et sous-notions liées à ce chapitre.

Pas assez de questions pour un entraînement ciblé sur cette notion.

Ensembles

Non commencé

Définitions

Un ensemble $E$ est une collection d'objets appelés éléments. On note $x \in E$ si $x$ appartient à $E$ , et $x \notin E$ sinon. L'inclusion $A \subset B$ signifie que tout élément de $A$ est dans $B$ . Deux ensembles sont égaux si et seulement s'ils ont les mêmes éléments (double inclusion).

L'ensemble des parties $\mathcal{P}(E)$ est l'ensemble de tous les sous-ensembles de $E$ . En prépa, on manipule aussi les opérations ensemblistes : union $\cup$ , intersection $\cap$ , complémentaire et différence. Les lois de De Morgan et la distributivité sont des outils de démonstration quotidiens.

Pourquoi c’est central : cette notion structure les preuves et calculs du programme ; maîtriser définitions et hypothèses évite les applications hors cadre.

Formules

$A \subset B \Leftrightarrow (\forall x \in E,\ x \in A \Rightarrow x \in B)$
$A = B \Leftrightarrow A \subset B \text{ et } B \subset A$
$A \cap (B \cup C) = (A \cap B) \cup (A \cap C) \quad \text{(distributivité)}$
$\overline{A \cup B} = \overline{A} \cap \overline{B} \quad \text{(lois de De Morgan)}$
$|\mathcal{P}(E)| = 2^{|E|} \text{ si } E \text{ est fini}$

Exemples

Exemple 1

Montrer $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ par double inclusion.

Méthode

Si $x \in A \cap (B \cup C)$ , alors $x \in A$ et ( $x \in B$ ou $x \in C$ ), donc $x \in (A \cap B) \cup (A \cap C)$ . Réciproquement, si $x$ est dans le membre de droite, il est dans $A$ et dans $B$ ou $C$ .

Résultat

$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ .

Exemple 2

Calculer $|\mathcal{P}(\{1,2\})|$ .

Méthode

(1) Lire l'énoncé et repérer les hypothèses / la forme utile. (2) $\mathcal{P}(\{1,2\}) = \{\emptyset, \{1\}, \{2\}, \{1,2\}\}$ . Pour un ensemble fini à $n$ éléments, $|\mathcal{P}(E)| = 2^n$ . (3) Vérifier le résultat (ordre de grandeur, cas particulier, ou dérivation/substitution).

Résultat

$|\mathcal{P}(\{1,2\})| = 4 = 2^2$ .

À retenir

Quantificateurs

Non commencé

Définitions

Les quantificateurs permettent de formaliser des propriétés sur un ensemble. $\forall x \in E, P(x)$ signifie « pour tout $x$ de $E$ , la propriété $P(x)$ est vraie ». $\exists x \in E, P(x)$ signifie « il existe au moins un $x$ dans $E$ tel que $P(x)$ ».

On peut aussi écrire $\exists! x$ pour l'unicité. La négation d'une proposition quantifiée s'obtient en inversant le quantificateur et en niant la propriété. Attention : « pour tout » n'implique pas que tous les $x$ vérifient la même chose de manière identique — chacun doit seulement satisfaire $P$ .

Les quantificateurs formalisent les propriétés : $\forall x \in E, P(x)$ (« pour tout ») et $\exists x \in E, P(x)$ (« il existe »). On écrit aussi $\exists!$ pour l'unicité.

La négation d'une proposition quantifiée s'obtient en inversant le quantificateur et en niant la propriété. L'ordre des quantificateurs compte : $\forall x \exists y$ n'est pas équivalent à $\exists y \forall x$ .

Formules

$\neg(\forall x \in E, P(x)) \Leftrightarrow \exists x \in E, \neg P(x)$
$\neg(\exists x \in E, P(x)) \Leftrightarrow \forall x \in E, \neg P(x)$
$(\forall x, P(x) \Rightarrow Q(x)) \text{ se lit « si } P(x) \text{ alors } Q(x) \text{ pour tout } x \text{ »}$
$\exists x, P(x) \land Q(x) \Rightarrow \exists x, P(x) \text{ et } \exists x, Q(x)$

Exemples

Exemple 1

Nier « $\forall x \in \mathbb{R}, x^2 \geq 0$ ».

Méthode

(1) Lire l'énoncé et repérer les hypothèses / la forme utile. (2) Négation : inverser $\forall$ en $\exists$ et nier le prédicat : $\exists x \in \mathbb{R}, x^2 < 0$ . (3) Vérifier le résultat (ordre de grandeur, cas particulier, ou dérivation/substitution).

Résultat

$\exists x \in \mathbb{R},\ x^2 < 0$ (proposition fausse, mais négation formellement correcte).

Exemple 2

Nier « $\exists n \in \mathbb{N}, n^2 = 2$ ».

Méthode

(1) Lire l'énoncé et repérer les hypothèses / la forme utile. (2) Inverser $\exists$ en $\forall$ : $\forall n \in \mathbb{N}, n^2 \neq 2$ . (3) Vérifier le résultat (ordre de grandeur, cas particulier, ou dérivation/substitution).

Résultat

$\forall n \in \mathbb{N},\ n^2 \neq 2$ .

À retenir

Raisonnements

Non commencé

Définitions

En prépa, on distingue plusieurs modes de raisonnement. L'implication $P \Rightarrow Q$ : on suppose $P$ vraie et on démontre $Q$ . La contraposée $\neg Q \Rightarrow \neg P$ est logiquement équivalente à $P \Rightarrow Q$ .

La réciproque $Q \Rightarrow P$ ne l'est en général pas. Le raisonnement par l'absurde : pour montrer $P$ , on suppose $\neg P$ et on aboutit à une contradiction. Le raisonnement par récurrence : on prouve $P(0)$ puis $\forall n, P(n) \Rightarrow P(n+1)$ pour conclure $\forall n, P(n)$ . Le raisonnement par disjonction de cas et par analyse-synthèse sont aussi courants.

Modes de raisonnement usuels en prépa : implication $P \Rightarrow Q$ (supposer $P$ , prouver $Q$ ), contraposée $\neg Q \Rightarrow \neg P$ (équivalente), réciproque $Q \Rightarrow P$ (non équivalente en général).

Absurde : pour montrer $P$ , on suppose $\neg P$ et on aboutit à une contradiction. Récurrence : $P(0)$ puis $\forall n, P(n) \Rightarrow P(n+1)$ . On utilise aussi disjonction de cas et analyse-synthèse.

Formules

$(P \Rightarrow Q) \Leftrightarrow (\neg Q \Rightarrow \neg P) \quad \text{(contraposée)}$
$\text{Absurde : } \neg P \Rightarrow \bot \Rightarrow P$
$\text{Récurrence : } P(0) \land (\forall n, P(n) \Rightarrow P(n+1)) \Rightarrow \forall n, P(n)$
$P \Leftrightarrow Q \text{ se montre par deux implications}$

Exemples

Exemple 1

Montrer « $n^2$ pair $\Rightarrow$ $n$ pair » par contraposée.

Méthode

(1) Lire l'énoncé et repérer les hypothèses / la forme utile. (2) Contraposée : si $n$ impair, $n=2k+1$ , alors $n^2=4k^2+4k+1$ impair. Donc si $n^2$ est pair, $n$ ne peut être impair. (3) Vérifier le résultat (ordre de grandeur, cas particulier, ou dérivation/substitution).

Résultat

$n^2$ pair $\Rightarrow$ $n$ pair.

Exemple 2

Montrer $1+\cdots+n = \frac{n(n+1)}{2}$ par récurrence.

Méthode

(1) Lire l'énoncé et repérer les hypothèses / la forme utile. (2) Init. $n=1$ : OK. Hérédité : si vrai en $n$ , alors $1+\cdots+(n+1) = \frac{n(n+1)}{2}+(n+1) = \frac{(n+1)(n+2)}{2}$ . (3) Vérifier le résultat (ordre de grandeur, cas particulier, ou dérivation/substitution).

Résultat

$\forall n \in \mathbb{N}^*,\ \sum_{k=1}^n k = \frac{n(n+1)}{2}$ .