Exercices
-
Ensembles et relations
Lois de Morgan Soient $A, B$ des ensembles, alors $$\overline{A \cap B} = \overline{A} \cup \overline{B}\\\ \overline{A \cup B} = \overline{A} \cap \overline{B}$$ Preuve : On commence par montrer $\overline{A \cap B} \subseteq \overline{A} \cup \overline{B}$, donc supposons $x \in \overline{A \cap B}$, i.
-
Fonctions et opérations
Exercice 3 Si $n<m$, il n’existe pas d’injection d’un ensemble à $m$ éléments dans un ensemble à $n$ éléments. Une formulation plus imagée de ce résultat est le principe des tiroirs (ou encore _pigeon-hole principle), à savoir: si ${n<m}$ et que l’on veut placer $m$ chemises dans $n$ tiroirs alors un tiroir au moins contiendra plusieurs chemises.
-
Relations d'ordre
Exercice 10 Soient $(A, \leq_1)$ et $(B, \leq_2)$ deux ordres bien fondés. Les ordres suivants sont-ils bien fondés ? Sur $A \times B$, l’ordre produit $(a, b) \leq (a', b')$ si et seulement si $a \leq_1 a'$ et $b \leq_2 b'$.
-
Induction sur $\mathbb{N}$
Exercice 7 Montrer que pour tout $n\in \mathbb{N}$, $(n+1)^2-(n+2)^2-(n+3)^2+(n+4)^2=4$. Indication : Developpez l’expresion :-) En déduire que tout entier $m$ peut s’écrire comme somme et différence des carrés $1^2, 2^2,\ldots , n^2$ pour un certain $n$, c’est-à-dire que pour tout $m$ :
-
Induction structurelle
Exercice 6 Soit $F_0 = \{a\}$ et $F_1 = \{s\}$ . On considère l’ensemble $\mathcal{T}$ des termes construits sur $F_0 \cup F_1$. Démontrer que $\mathcal{T} =\{s^n(a) \mid n \in \mathbb{N}\}$, où $s^n(a)$ est défini inductivement par : $s^0(a)=a$ et pour tout $n \in \mathbb{N}$, $s^{n+1}(a) = s(s^n(a))$.
-
Langages et automates
Exercice 2 Soit $A$ un alphabet contenant la lettre $b$. Soit $X=\{b\}$ et $Y=(A\setminus {b})\cdot \{b\}^*$. Décrire informellement les éléments de $X^*$, $Y$ et $Y^*$. Solution : $X^*$ est l’ensemble des mots (y compris le mot vide) formés uniquement de $b$.