1.
Dessinez le diagramme de treillis pour l’ensemble des parties de \(X = \{ a, b, c, d \}\) avec la relation d’inclusion d’ensembles, \(\subset\text{.}\)
Exercices 19.5 Exercices
2.
Dessinez le diagramme pour l’ensemble des entiers positifs qui sont diviseurs de \(30\text{.}\) Ce poset est-il une algèbre de Boole ?
Indication.
3.
Dessinez un diagramme du treillis des sous-groupes de \({\mathbb Z}_{12}\text{.}\)
4.
Soit \(B\) l’ensemble des entiers positifs qui sont diviseurs de \(210\text{.}\) Définissez un ordre sur \(B\) par \(a \preceq b\) si \(a \mid b\text{.}\) Prouvez que \(B\) est une algèbre de Boole. Trouvez un ensemble \(X\) tel que \(B\) soit isomorphe à \({\mathcal P}(X)\text{.}\)
5.
Prouvez ou réfutez : \({\mathbb Z}\) est un poset sous la relation \(a \preceq b\) si \(a \mid b\text{.}\)
6.
Dessinez le circuit à interrupteurs pour chacune des expressions booléennes suivantes.
-
\(\displaystyle (a \vee b \vee a') \wedge a\)
-
\(\displaystyle (a \vee b)' \wedge (a \vee b)\)
-
\(\displaystyle a \vee (a \wedge b)\)
-
\(\displaystyle (c \vee a \vee b) \wedge c' \wedge (a \vee b)'\)
7.
Dessinez un circuit qui sera fermé exactement lorsqu’un seul des trois interrupteurs \(a\text{,}\) \(b\) et \(c\) est fermé.
8.
Prouvez ou réfutez que les deux circuits représentés sont équivalents.
9.
Soit \(X\) un ensemble fini contenant \(n\) éléments. Prouvez que \(|{\cal P}(X)| = 2^n\text{.}\) Concluez que l’ordre de toute algèbre de Boole finie doit être \(2^n\) pour un certain \(n \in {\mathbb N}\text{.}\)
10.
Pour chacun des circuits suivants, écrivez une expression booléenne. Si le circuit peut être remplacé par un circuit avec moins d’interrupteurs, donnez l’expression booléenne et dessinez un diagramme pour le nouveau circuit.
11.
Prouvez ou réfutez : l’ensemble de tous les entiers non nuls est un treillis, où \(a \preceq b\) est défini par \(a \mid b\text{.}\)
12.
Soit \(L\) un ensemble non vide avec deux opérations binaires \(\vee\) et \(\wedge\) satisfaisant les lois commutatives, associatives, idempotentes et d’absorption. Nous pouvons définir un ordre partiel sur \(L\text{,}\) comme dans le Théorème 19.1.14, par \(a \preceq b\) si \(a \vee b = b\text{.}\) Prouvez que la borne inférieure de \(a\) et \(b\) est \(a \wedge b\text{.}\)
13.
Soit \(G\) un groupe et \(X\) l’ensemble des sous-groupes de \(G\) ordonné par l’inclusion ensembliste. Si \(H\) et \(K\) sont des sous-groupes de \(G\text{,}\) montrez que la borne supérieure de \(H\) et \(K\) est le sous-groupe engendré par \(H \cup K\text{.}\)
14.
Soit \(R\) un anneau et supposons que \(X\) est l’ensemble des idéaux de \(R\text{.}\) Montrez que \(X\) est un poset ordonné par l’inclusion ensembliste, \(\subset\text{.}\) Définissez l’intersection de deux idéaux \(I\) et \(J\) dans \(X\) par \(I \cap J\) et la réunion de \(I\) et \(J\) par \(I + J\text{.}\) Prouvez que l’ensemble des idéaux de \(R\) est un treillis sous ces opérations.
Indication.
Soient \(I, J\) des idéaux de \(R\text{.}\) Nous devons montrer que \(I + J = \{ r + s : r \in I \text{ et } s \in J \}\) est le plus petit idéal de \(R\) contenant à la fois \(I\) et \(J\text{.}\) Si \(r_1, r_2 \in I\) et \(s_1, s_2 \in J\text{,}\) alors \((r_1 + s_1) + (r_2 + s_2) = (r_1 + r_2) +(s_1 + s_2)\) est dans \(I + J\text{.}\) Pour \(a \in R\text{,}\) \(a(r_1 + s_1) = ar_1 + as_1 \in I + J\) ; donc \(I + J\) est un idéal de \(R\text{.}\)
15.
Soit \(B\) une algèbre de Boole. Prouvez chacune des identités suivantes.
16.
En dessinant les diagrammes appropriés, complétez la preuve du Théorème 19.3.7 pour montrer que les fonctions à interrupteurs forment une algèbre de Boole.
17.
Soit \(B\) une algèbre de Boole. Définissez des opérations binaires \(+\) et \(\cdot\) sur \(B\) par
\begin{align*}
a + b & = (a \wedge b') \vee (a' \wedge b)\\
a \cdot b & = a \wedge b\text{.}
\end{align*}
Prouvez que \(B\) est un anneau commutatif sous ces opérations satisfaisant \(a^2 = a\) pour tout \(a \in B\text{.}\)
18.
Soit \(X\) un poset tel que pour tout \(a\) et \(b\) dans \(X\text{,}\) soit \(a \preceq b\) soit \(b \preceq a\text{.}\) On dit alors que \(X\) est un ensemble totalement ordonné.
-
Prouvez que \({\mathbb N}\text{,}\) \({\mathbb Z}\text{,}\) \({\mathbb Q}\text{,}\) et \({\mathbb R}\) sont des ensembles totalement ordonnés sous l’ordre usuel \(\leq\text{.}\)
19.
Soient \(X\) et \(Y\) des posets. Une application \(\phi : X \rightarrow Y\) est préservant l’ordre si \(a \preceq b\) implique que \(\phi(a) \preceq \phi(b)\text{.}\) Soient \(L\) et \(M\) des treillis. Une application \(\psi: L \rightarrow M\) est un homomorphisme de treillis si \(\psi( a \vee b ) = \psi(a) \vee \psi(b)\) et \(\psi( a \wedge b ) = \psi(a) \wedge \psi(b)\text{.}\) Montrez que tout homomorphisme de treillis préserve l’ordre, mais qu’il n’est pas vrai que tout homomorphisme préservant l’ordre est un homomorphisme de treillis.
20.
Soit \(B\) une algèbre de Boole. Prouvez que \(a = b\) si et seulement si \((a \wedge b') \vee ( a' \wedge b) = O\) pour \(a,
b \in B\text{.}\)
Indication.
\(( \Rightarrow)\text{.}\) \(a = b \Rightarrow (a \wedge b') \vee (a' \wedge b) = (a \wedge a') \vee (a' \wedge a) = O \vee O = O\text{.}\) \(( \Leftarrow)\text{.}\) \(( a \wedge b') \vee (a' \wedge b) = O \Rightarrow a \vee b = (a \vee a) \vee b = a \vee (a \vee b) = a \vee [I \wedge (a \vee b)] = a \vee [(a \vee a') \wedge (a \vee b)] = [a \vee (a \wedge b')] \vee [a \vee (a' \wedge b)] = a \vee [(a \wedge b') \vee (a' \wedge b)] = a \vee 0 = a\text{.}\) Un argument symétrique montre que \(a \vee b = b\text{.}\)
21.
Soit \(B\) une algèbre de Boole. Prouvez que \(a = O\) si et seulement si \((a \wedge b') \vee ( a' \wedge b) = b\) pour tout \(b \in B\text{.}\)
22.
Soient \(L\) et \(M\) des treillis. Définissez une relation d’ordre sur \(L \times M\) par \(( a, b) \preceq (c, d)\) si \(a \preceq c\) et \(b \preceq d\text{.}\) Montrez que \(L \times M\) est un treillis sous cet ordre partiel.
