Exercices

Exercice 1   Soient $A, B, C$ trois assertions. Pour chacune des assertions suivantes :

$$\begin{array}{cc} \Big(A\wedge(\neg B)\Big) & \Big(A\vee(\ne... ...) & \Big(A\vee(\neg B)\Longrightarrow (\neg C)\Big) \end{array}$$

1. Ecrire sa négation.
2. Traduire l'assertion et sa négation en langage courant, en remplaçant $A$ par «je mange», $B$ par «je bois»  et $C$ par «je fume».

Exercice 2   Soient $A$, $B$ et $C$ trois assertions. Démontrer que les équivalences suivantes sont toujours vraies, d'abord à l'aide des tables de vérité, ensuite en utilisant les opérations entre connecteurs logiques. Traduire chacune des assertions en langage courant, en remplaçant $A$ par «je mange», $B$ par «je bois»  et $C$ par «je fume».

1. $\Big( A\Longrightarrow (B\Longrightarrow C)\Big) \;\Longleftrightarrow\; \Big((A\wedge B)\Longrightarrow C\Big)$.
2. $\Big( (A\vee B)\Longrightarrow C\Big) \;\Longleftrightarrow\; \Big((A\Longrightarrow C)\wedge(B\Longrightarrow C)\Big)$.
3. $\Big( (A\wedge B)\Longrightarrow C\Big) \;\Longleftrightarrow\; \Big((A\Longrightarrow C)\vee (B\Longrightarrow C)\Big)$.
4. $\Big( A\Longrightarrow (B\wedge C)\Big) \;\Longleftrightarrow\; \Big((A\Longrightarrow B)\wedge (A \Longrightarrow C)\Big)$.
5. $\Big( A\Longrightarrow (B\vee C)\Big) \;\Longleftrightarrow\; \Big((A\Longrightarrow B)\vee (A \Longrightarrow C)\Big)$.

Exercice 3   On introduit un nouveau connecteur logique, dit barre de Scheffer, noté $\vert$, dont la table de vérité est la suivante :

$$\begin{array}{c\vert c\vert c} A&B&A\vert B \hline F&F&V\\ F&V&V\\ V&F&V\\ V&V&F\end{array}$$

1. Donner une expression de $A\vert B$ en utilisant les connecteurs usuels : $\neg$, $\vee$, $\wedge$.
2. Montrer que tous les connecteurs peuvent être remplacés par ce seul connecteur, en exprimant $\neg A$, $A\vee B$, $A\wedge B$ et $A\Longrightarrow B$ en utilisant seulement la barre de Scheffer et, si nécessaire, des parenthèses.

Exercice 4   On considère les quatre assertions suivantes :

$\bullet$

$F$ : je fume,

$\bullet$

$B$ : je bois,

$\bullet$

$J$ : je mange du jambon,

$\bullet$

$M$ : j'ai des moustaches.

Exprimer sous forme symbolique les phrases suivantes :

1. Je fume et je bois, mais je n'ai pas de moustache.
2. Quand je fume, je ne bois pas.
3. Chaque fois que je mange du jambon, je ne fume pas mais je bois.
4. Si je mange du jambon ou si je bois, alors je ne fume pas.
5. Il suffit que j'aie des moustaches pour que je mange du jambon.
6. Il faut que je mange du jambon et que je boive pour que je fume.
7. Une condition nécessaire pour que je boive et que je fume est que je mange du jambon.
8. Je fume et je bois, si et seulement si je mange du jambon ou j'ai des moustaches.
9. De deux choses l'une : soit je bois et je mange du jambon, soit si j'ai une moustache alors je ne fume pas.

En supposant que les valeurs de vérité respectives de $F,B,J,M$ sont $V, V, F, V$, trouver les valeurs de vérité des phrases précédentes.

Exercice 5   Exprimer sous forme symbolique les raisonnements suivants et vérifier qu'ils sont corrects.

1. Si je vais à Londres, j'irai aussi à Oxford. Soit je vais à Londres, soit je dépense mon argent à autre chose. Si je vais à Oxford, je verrai John. Si je dépense mon argent à autre chose, je verrai John. Donc je verrai John.
2. Si j'ai de l'argent ou si je bois du vin alors je chante en me rasant et je suis content. Donc je n'ai pas d'argent ou bien je chante en me rasant.
3. Soit je mange, soit je bois, et si je mange je ne fume pas. Comme je ne bois pas, je ne fume pas.
4. Si Pierre est marié, alors Jean est marié, et si Jean est marié, alors Louis l'est aussi. De plus, soit Jean est célibataire, soit il est marié et Louis est célibataire. Donc Pierre est célibataire.
5. Si on ne danse pas, je m'asseois. Si je m'asseois, je bois et je fume. Si on danse je m'amuse. Or je m'ennuie. Donc je fume.
6. Si je ne m'asseois pas, je bois. Si je bois, on danse et de plus je fume. Si je m'asseois, je m'amuse. Or je m'ennuie. Donc je fume.
7. Si je marche, je sue. Si je ne me fatigue pas, je ne sue pas. Or je ne me fatigue pas. Donc je ne marche pas.
8. Si $A$ dit la vérité, $B$ ment. Si $B$ ment, $C$ ment. Si $C$ ment, $D$ dit la vérité. $D$ ment ou bien $E$ ment. $A$ ne ment pas. Donc $E$ ment.

Exercice 6   Trois commerçants habitent dans 3 maisons situées aux numéros 21, 23 et 25 de la même rue. Le boucher habite dans la maison jaune, qui est à côté de la rouge mais qui n'est pas à côté de la verte. L'épicier, qui n'est pas suisse, habite à côté du Français. L'Italien habite au numéro 21 et sa maison n'est pas jaune. Quelle est la nationalité du pharmacien, quelle est la couleur de sa maison, et où habite-t-il ?

Exercice 7   Trois personnes, un policier un berger et un assassin, habitent dans 3 maisons situées aux numéros 19, 21 et 23 de la même rue. Le policier habite au numéro 23 et sa maison n'est pas rouge. La maison rouge est à côté de la maison bleue mais pas à côté de la maison jaune. L'Italien habite dans la maison rouge. Le Français, qui n'est pas berger, habite à côté de l'assassin. Quelle est la couleur de la maison de l'assassin et où habite-t-il ?

Exercice 8 (Pour les courageux)   .

$\bullet$

Alice dit que si Bernard est coupable, Charles l'est aussi.

$\bullet$

Bernard dit que Alice est coupable et que Charles ne l'est pas.

$\bullet$

Charles dit qu'il n'est pas coupable mais que au moins l'un des deux autres l'est.

Soit $A$ (respectivement $B$, $C$) l'assertion «Alice (respectivement : Bernard, Charles) est coupable».

1. Ecrire sous forme logique les affirmations de Alice, Bernard et Charles.
2. On sait que chacune des trois personnes ment si et seulement si elle est coupable. Déduire de la question précédente trois assertions vraies. Simplifier leur expression.
3. Contruire la table de vérité de chacune des trois assertions de la question précédente.
4. Déduire de ces tables de vérité que Alice est innocente, Bernard et Charles sont coupables.

Exercice 9   Définir les ensembles suivants en extension.

1. $\{ n\in\mathbb{N}\;;\quad (n>3)\wedge(n\leqslant 7) \}$.
2. $\{ n\in\mathbb{N}\;;\quad (2 \vert n)\wedge(n\leqslant 7) \}$.
3. $\{ n\in\mathbb{N}\;;\quad (n \vert 12)\vee(n\geqslant 7) \}$.
4. $\{ n\in\mathbb{N}\;;\quad (\neg(n \vert 12))\wedge(n\leqslant 7) \}$.
5. $\{ n\in\mathbb{N}\;;\quad (n>3)\wedge((n \vert 12)\vee(n\leqslant 7)) \}$.
6. $\{n \in \mathbb{N}; \quad(n\vert 15)\} \bigcup \{l \in \mathbb{N}; \quad(3 < l^2) \wedge (l^2 \leqslant 16)\}$.
7. $\{n \in \mathbb{N}; \quad((n+1)\vert 20) \vee ((n-1)\vert 8)\}$.

Exercice 10   Soient $A$, $B$ et $C$ trois sous-ensembles d'un ensemble $E$. Ecrire en fonction de $A, B, C$ les ensembles correspondant aux assertions suivantes.

1. $x$ appartient aux trois.
2. $x$ appartient au moins à l'un d'entre eux.
3. $x$ appartient à deux d'entre eux au plus.
4. $x$ appartient à l'un d'entre eux exactement.
5. $x$ appartient à deux d'entre eux au moins.
6. $x$ appartient à l'un d'entre eux au plus.

Exercice 11   Soit $E$ un ensemble. Soient $A$ et $B$ deux sous-ensembles de $E$. On appelle :

$\bullet$

différence de $B$ dans $A$ et on note $A\setminus B$ l'ensemble $A\cap {^c\!B}$,

$\bullet$

différence symétrique de $A$ et $B$ et on note $A\Delta B$ l'ensemble $(A\setminus B)\cup (B\setminus A)$.

1. Ecrire sous forme logique les propriétés « $x\in A\setminus B$»  et « $x\in A\Delta B$»  à l'aide des propriétés «$x\in A$»  et «$x\in B$». Démontrer les égalités ensemblistes suivantes.
2. $A\setminus\emptyset=A\Delta\emptyset=A$.
3. $A\setminus A=A\Delta A=\emptyset$.
4. $A\cap(B\Delta C) = (A\cap B)\Delta (A\cap C)$.
5. $(A\Delta B)\cup (A\Delta C)=(A\cup B\cup C)\setminus (A\cap B\cap C)$.
6. Donner une représentation sous forme de diagramme de Venn de tous les ensembles définis dans cet exercice.

Exercice 12   Soient $A$, $B$ et $C$ trois sous-ensembles d'un ensemble $E$.

1. Simplifier l'expression $(A\cap B\cap C) \cup ({^c\!A}\cap B\cap C) \cup {^c\!B} \cup {^c\!C}$.
2. Démontrer que $(A\cap {^c\!B})\cap {^c\!C} = A\cap{^c(B\cup C)} = (A\cap {^c\!C})\cap {^c\!B}$.
3. Démontrer que $(A\cup B \subset {^c\!C}) \wedge (A\cup C \subset B) \Longleftrightarrow (A\subset B) \wedge (C= \emptyset)$.

Exercice 13 (D'après Lewis Caroll)   . Parmi les combattants d'une grande bataille, au moins 70% ont perdu un il, au moins 75% une oreille, au moins 80% un bras, et au moins 85% une jambe. Quelle est la proportion minimale des combattants qui ont perdu les 4 ?

Exercice 14   Un centre de langue propose des cours d'Albanais, de Bantou et de Chinois. Sur 93 élèves, 54 étudient l'Albanais, 51 le Bantou ou le Chinois, 27 le Chinois mais pas le Bantou, 3 ni l'Albanais ni le Chinois, et 12 étudient les 3 langues.

1. Combien d'élèves étudient à la fois le Bantou et le Chinois ?
2. Combien d'élèves étudient l'Albanais ou le Bantou mais pas le Chinois ?
3. Combien d'élèves n'étudient ni le Bantou ni le Chinois ?
4. Combien d'élèves étudient une seule langue ?
5. Combien d'élèves étudient exactement deux langues ?

Exercice 15   Pour chacune des assertions suivantes :

$\bullet$

$\forall n\in \mathbb{N} ,\; \exists m\in \mathbb{N} \;;\quad (m \vert n)$,

$\bullet$

$\exists n\in \mathbb{N} \;;\quad \forall m\in \mathbb{N} ,\; (m \vert n)$,

$\bullet$

$\exists n\in \mathbb{N} \;;\quad \forall m\in \mathbb{N} ,\; (n \vert m)$,

$\bullet$

$\forall n\in \mathbb{N} ,\; \forall m\in \mathbb{N} ,\; \Big((m \vert n)\vee (n \vert m)\Big)$,

$\bullet$

$\forall n\in \mathbb{N} ,\; \forall m\in \mathbb{N} ,\; \Big(((m \vert n)\wedge (n \vert m))\Longrightarrow (m=n)\Big)$,

$\bullet$

$\forall n\in \mathbb{N} ,\; \forall m\in \mathbb{N} ,\; \exists k\in \mathbb{N} \;;\quad \Big((n \vert k)\wedge (m \vert k)\Big)$.

1. Lire à haute voix et comprendre.
2. Dire si l'assertion est vraie ou fausse et le démontrer.
3. Ecrire la négation, lire à haute voix et comprendre.

Exercice 16   On note $\mathbb{N}$ l'ensemble des entiers naturels, $A$ l'ensemble des nombres pairs, et $B$ l'ensemble des nombres premiers. Exprimer sous forme symbolique les phrases suivantes.

1. Tout nombre pair est divisible par 2.
2. Aucun nombre impair n'est divisible par 2.
3. Il n'existe pas de nombre premier pair distinct de 2.
4. Tout nombre premier distinct de 2 est impair.
5. Il existe un nombre pair qui divise tout nombre pair.
6. Tout nombre premier divise au moins un nombre pair

Exercice 17   On note $\mathbb{N}$ l'ensemble des entiers naturels, $A$ l'ensemble des nombres pairs, et $B$ l'ensemble des nombres premiers. Ecrire en langage courant et comprendre la signification des expressions logiques suivantes.

1. $\exists n\in A \;;\quad n\in B$.
2. $\forall n\in A ,\;\exists m\in B \;;\quad\; m \vert n$.
3. $\forall n\in\mathbb{N} ,\; n\in A\Longrightarrow \Big((n\notin B)\vee (n=2)\Big)$.
4. $\forall n\in A ,\;\Big( (n=2) \vee \big(\exists (m,p)\in A\times B \;;\quad\; n=mp\big) \Big)$.
5. $\exists n\in \mathbb{N} \;;\quad \forall (m,p)\in A\times B ,\; (n\neq m)\wedge (n\neq p)$.
6. $\forall n\in \mathbb{N} ,\; \Big( \exists m\in A \;;\quad m \vert n \Big) \;\Longrightarrow\; (n\in A)$.
7. $\forall n\in \mathbb{N} ,\;(n\in A)\vee \Big( \exists m\in A \;;\quad m+1=n \Big)$.

Exercice 18   Représenter sur un diagramme de Venn les ensembles suivants.

$\bullet$

Ensemble $Q$ des quadrilatères.

$\bullet$

Ensemble $T$ des trapèzes.

$\bullet$

Ensemble $P$ des parallélogrammes.

$\bullet$

Ensemble $R$ des rectangles.

$\bullet$

Ensemble $L$ des losanges.

$\bullet$

Ensemble $C$ des carrés.

Exprimer sous forme logique, puis ensembliste, les phrases suivantes.

1. Tout carré est un rectangle.
2. Tout rectangle qui est aussi un losange est un carré.
3. Il existe des parallélogrammes qui ne sont pas des rectangles.
4. Si un losange est un rectangle alors c'est un carré.
5. Une condition nécessaire pour qu'un trapèze soit un carré est que ce soit un rectangle.
6. Pour qu'un trapèze soit un rectangle il suffit que ce soit un carré.
7. Il existe des quadrilatères qui ne sont ni des rectangles, ni des losanges.
8. Il existe des parallélogrammes qui ne sont ni des rectangles, ni des losanges.

Exercice 19   Si $n$ est un entier, on note «$n$ modulo 5»  le reste de la division euclidienne de $n$ par $5$. Les applications suivantes sont définies sur $\{0,1,2,3,4\}$, à valeurs dans lui-même. Représentez-les sur un diagramme. Sont-elles injectives ? surjectives ? bijectives ? Représentez le diagramme de $f\circ f$.

1. $f : n\mapsto n+1$ modulo $5$.
2. $f : n\mapsto n+3$ modulo $5$.
3. $f : n\mapsto n+10$ modulo $5$.
4. $f : n\mapsto 2n$ modulo $5$.
5. $f : n\mapsto 3n$ modulo $5$.
6. $f : n\mapsto 10n$ modulo $5$.

Exercice 20   Si $n$ est un entier, on note «$n$ modulo 6»  le reste de la division euclidienne de $n$ par $6$. Les applications $f$ suivantes sont définies sur $\{0,1,2,3,4,5\}$, à valeurs dans lui-même. Représentez-les sur un diagramme. Sont-elles injectives ? surjectives ? bijectives ? Représentez le diagramme de $f\circ f$.

1. $f : n\mapsto n+1$ modulo $6$.
2. $f : n\mapsto n+3$ modulo $6$.
3. $f : n\mapsto n+10$ modulo $6$.
4. $f : n\mapsto 2n$ modulo $6$.
5. $f : n\mapsto 3n$ modulo $6$.
6. $f : n\mapsto 10n$ modulo $6$.

Exercice 21   On considère les applications suivantes, de $\mathbb{N}$ vers $\mathbb{N}$. Sont-elles injectives ? surjectives ? bijectives ?

1. $f : n\mapsto n+1$.
2. $f : n\mapsto 2n$.
3. $f : n\mapsto n^2$.
4. $$f : n\mapsto\left\{ \begin{array}{lcl} n+1&\mbox{si}&n\mbox{ est pair}\\ 2n&\mbox{si}&n\mbox{ est impair.} \end{array}\right.$$
5. $$f : n\mapsto\left\{ \begin{array}{lcl} 2n&\mbox{si}&n\mbox{ ... ...pair}\\ n-1&\mbox{si}&n\mbox{ est impair.} \end{array}\right.$$
6. $$f : n\mapsto\left\{ \begin{array}{lcl} n+1&\mbox{si}&n\mbox{... ...pair}\\ n-1&\mbox{si}&n\mbox{ est impair.} \end{array}\right.$$
7. $$f : n\mapsto\left\{ \begin{array}{lcl} n/2&\mbox{si}&n\mbox{... ...}\\ (n-1)/2&\mbox{si}&n\mbox{ est impair.} \end{array}\right.$$

Exercice 22   On considère les applications suivantes, de $\mathbb{R}$ vers $\mathbb{R}$. Sont-elles injectives ? surjectives ? bijectives ?

1. $f : x\mapsto x+1$.
2. $f : x\mapsto 2x$.
3. $f : x\mapsto x^2$.
4. $f : x\mapsto x^3$.
5. $f : x\mapsto \sqrt{\vert x\vert}$.
6. $f : x\mapsto \frac{x}{\sqrt{\vert x\vert}}$ si $x\neq 0 ,\;f(0)=0$.
7. $f : x\mapsto \mathrm{e}^{x}$.
8. $f : x\mapsto x^3-3x$.

Exercice 23   Soit $f$ l'application de $\mathbb{R}$ dans $\mathbb{R}$ définie par $$f (x) = \frac{2x}{1 + x^2}$$.

1. $f$ est-elle injective ? surjective ?
2. Montrez que $f (\mathbb{R}) = [-1, 1]$.
3. Montrez que la restriction
   $$g : \begin{cases}[ -1, 1]\to[-1, 1]&\\ x\to f (x)\end{cases}$$
   est une bijection.

Exercice 24   On considère l'application

$$f :\qquad \mathbb{R}^2 \to \mathbb{R}^2$$

$$(x,y) \mapsto (x+y,xy)$$

et l'ensemble $A=\{(x,y)\in\mathbb{R}^2 \vert x=0$ et $y>0\}$.

1. L'application $f$ est-elle injective ?
2. Déterminez $f^{-1}(A)$.
3. L'application $f$ est-elle surjective ?
4. On considère maintenant l'application définie sur $\mathbb{C}$,
   

   $$g :\qquad \mathbb{C}^2 \to \mathbb{C}^2$$

   $$(x,y) \mapsto (x+y,xy)$$

   
   Montrez que
   $$g(x,y)=(\alpha,\beta)\Leftrightarrow\left\{\begin{array}{rcl} y&=&\alpha-x x^2-\alpha x+\beta &=&0 \end{array}\right.$$
   Déduisez de cette équivalence la surjectivité de $g$.

Exercice 25   Les applications suivantes sont-elles injectives ? surjectives ? bijectives ?

1. $f :\begin{array}{rcl}\mathbb{R} &\longrightarrow& \mathbb{R}^2 \\ x &\longmapsto& (x,0)\end{array}$
2. $f :\begin{array}{rcl}\mathbb{R} &\longrightarrow& \mathbb{R}^2 \\ x &\longmap... ...2x^2&\mbox{si}&x<1\\ x+1&\mbox{si}&x\geqslant 1 \end{array}\right. \end{array}$
3. $f :\begin{array}{rcl}\mathbb{R}^2 &\longrightarrow& \mathbb{R}^2 \\ (x,y) &\longmapsto& (x+y,x-y)\end{array}$

Exercice 26   Soit $E$ un ensemble, $f$ et $g$ deux applications de $E$ dans $E$.

1. On suppose que $f\circ{}g = f\circ{}f\circ{}f$ et que $f$ est injective. Montrer que $\forall x \in E, g(x)=(f\circ{}f)(x)$.
2. On suppose que $g\circ{}f = f\circ{}f\circ{}f$ et que $f$ est surjective. Montrer que $\forall x \in E, g(x)=(f\circ{}f)(x)$.

On suppose maintenant que $f$ est bijective. Dans l'un quelconque des cas ci-dessus, montrer que $g$ est bijective et calculer son inverse.

Exercice 27   Soit $E$ un ensemble et $A$ un sous-ensemble de $E$. On appelle «fonction indicatrice de $A$»  et on note $\mathbb{I}_A$ l'application de $E$ vers $\{0,1\}$ qui à $x\in E$ associe $1$ si $x\in A$, 0 si $x\notin A$. Soient $A$ et $B$ deux sous-ensembles de $E$. Démontrer les assertions suivantes.

1. $\forall x\in E ,\; \mathbb{I}_{^c\!A}(x) = 1-\mathbb{I}_A(x)$.
2. $\forall x\in E ,\; \mathbb{I}_{A\cap B}(x) = \min\{\mathbb{I}_A(x),\mathbb{I}_B(x)\}=\mathbb{I}_A(x) \mathbb{I}_B(x)$.
3. $\forall x\in E ,\; \mathbb{I}_{A\cup B}(x) = \max\{\mathbb{I}_A(x),\mathbb{I}_B(x)\}=\mathbb{I}_A(x)+\mathbb{I}_B(x)-\mathbb{I}_A(x) \mathbb{I}_B(x)$.

Exercice 28   Soient $E$ et $F$ deux ensembles, $f$ une application de $E$ vers $F$. Soient $A$ et $A'$ deux sous-ensembles de $E$. Soient $B$ et $B'$ deux sous-ensembles de $F$. Démontrer les assertions suivantes.

1. $(A\subset A')\;\Longrightarrow\; (f(A)\subset f(A'))$.
2. $(B\subset B')\;\Longrightarrow\; (f^{-1}(B)\subset f^{-1}(B'))$.
3. $f(A\cup A')=(f(A)\cup f(A'))$.
4. $f^{-1}(B\cup B')=(f^{-1}(B)\cup f^{-1}(B'))$.
5. $f(A\cap A')\subset (f(A)\cap f(A'))$.
6. $f^{-1}(B\cap B')=(f^{-1}(B)\cap f^{-1}(B'))$.
7. $f^{-1}(f(A))\supset A$.
8. $f(f^{-1}(B))\subset B$.
9. $f(A\cap f^{-1}(B))=(f(A)\cap B)$.
10. $f(A\cup f^{-1}(B))\subset (f(A)\cup B)$.

Exercice 29   Ecrire chacune des assertions suivantes comme une implication.
Ecrire et démontrer sa contraposée.

1. Aucun nombre impair n'est la somme de deux nombres impairs.
2. Tout nombre premier strictement supérieur à 2 est impair.
3. Soient $m$ et $n$ deux entiers impairs tels que $m$ divise $2n$. Alors $m$ divise $n$.
4. Soient $m$ et $n$ deux entiers tels que $m$ divise $n$. Alors $m$ et $n+1$ sont premiers entre eux (ils n'ont aucun diviseur commun autre que $1$).
5. Si le produit de deux entiers strictement supérieurs à 1 est le carré d'un entier alors chacun des deux est le carré d'un entier ou bien ils ont un diviseur commun autre que $1$.

Exercice 30   Démontrer par récurrence les assertions suivantes.

1. $\forall n\in\mathbb{N}\;,\quad \displaystyle{ \sum_{k=0}^n (k+1) = (n+1)(n+2)/2 }$.
2. $\forall n\in\mathbb{N}\;,\quad \displaystyle{ \sum_{k=0}^n k^2 = n(n+1)(2n+1)/6 }$.
3. $\forall n\in\mathbb{N}\;,\quad \displaystyle{ \sum_{k=0}^n k^3 = n^2(n+1)^2/4 }$.
4. $\forall n\in\mathbb{N}\;,\quad 3\vert(n^3-n)$.
5. $\forall n\in\mathbb{N}\;,\quad \displaystyle{ \sum_{k=0}^n 2^k = 2^{n+1}-1 }$.
6. $\forall n\in\mathbb{N}\;,\quad \displaystyle{ \sum_{k=0}^n k2^k = (n-1)2^{n+1}+2 }$.
7. $\forall n\in\mathbb{N}, n\ge 3\;,\quad \displaystyle{ \prod_{k=3}^n\frac{k^2-4}{k} = \frac{(n+2)!}{12n(n-1)} }$.
8. $\forall n\in\mathbb{N}^*,\quad \displaystyle{ \prod_{k=1}^n(n+k)=2^n\prod_{k=1}^n(2k-1)}$.

Exercice 31   Soient $E$ un ensemble fini non vide et $x$ un élément fixé de $E$. On considère les relations ${\cal R}$ définies par les assertions suivantes.

$\bullet$

$\forall A,B\in {\cal P}(E)\;,\quad A{\cal R}B\;\Longleftrightarrow\; A=B$.

$\bullet$

$\forall A,B\in {\cal P}(E)\;,\quad A{\cal R}B\;\Longleftrightarrow\; \Big((A\cap B=\emptyset)\vee(A\cup B\neq \emptyset)\Big)$.

$\bullet$

$\forall A,B\in {\cal P}(E)\;,\quad A{\cal R}B\;\Longleftrightarrow\; \Big((x\in A\cap B)\vee (x\in {^c\!A}\cap {^c\!B})\Big)$.

Pour chacune de ces relations.

1. Montrer que ${\cal R}$ est une relation d'équivalence sur ${\cal P}(E)$.
2. Décrire l'ensemble quotient ${\cal P}(E)/{\cal R}$.

Exercice 32   Soit $E$ un ensemble non vide et $x$ un élément fixé de $E$. On définit la relation ${\cal R}$ sur l'ensemble ${\cal P}(E)$ des parties de $E$ par :

$$\forall A,B\in {\cal P}(E)\;,\quad A{\cal R}B\;\Longleftrightarrow\; \Big((x\in A\cap B)\vee (x\in {^c\!A}\cap {^c\!B})\Big)\;.$$

1. Montrer que ${\cal R}$ est une relation d'équivalence.
2. Montrer que la classe d'équivalence de $\emptyset$ est ${\cal P}(E\setminus\{x\})$ (ensemble des parties du complémentaire de $\{x\}$ dans $E$).
3. Montrer que l'ensemble quotient ${\cal P}(E)/{\cal R}$ a deux éléments :
   $${\cal P}(E)/{\cal R} = \{ \mathfrak{cl}_{{\cal R}}(\emptyset), \mathfrak{cl}_{{\cal R}}(\{x\}) \}\;.$$

4. On définit l'application $f_x$, de ${\cal P}(E)$ vers ${\cal P}(E)$, qui à un sous-ensemble $A$ associe $A\cup\{x\}$. L'application $f$ est-elle injective ? surjective ?
5. Vérifier que l'image par $f_x$ d'un élément de $\mathfrak{cl}_{{\cal R}}(\emptyset)$ appartient à $\mathfrak{cl}_{{\cal R}}(\{x\})$.
6. Montrer que tout élément de $\mathfrak{cl}_{{\cal R}}(\{x\})$ a un antécédent et un seul dans $\mathfrak{cl}_{{\cal R}}(\emptyset)$.
7. En déduire que :
   $$\mathrm{Card}(\mathfrak{cl}_{{\cal R}}(\emptyset)) = \mathrm{Card}(\mathfrak{cl}_{{\cal R}}(\{x\}))$$

8. Déduire des questions précédentes que :
   $$\mathrm{Card}({\cal P}(E)) = 2\mathrm{Card}({\cal P}(E\setminus\{x\}))\;.$$

9. Démontrer par récurrence que le cardinal de l'ensemble des parties d'un ensemble à $n$ éléments est $2^n$.