Correction : Algèbre générale, Algèbre de Boole
3
pages
Français
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe en t'inscrivant gratuitement
Découvre YouScribe en t'inscrivant gratuitement
3
pages
Français
Ebook
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Publié par
Nombre de lectures
312
Licence :
Langue
Français
Publié par
Nombre de lectures
312
Licence :
Langue
Français
Algèbre de Boole
Dans l’intégralité de ce problème,désigne un ensemble.
On appelle algèbre de Boole sur l’ensemble, toute partiede℘() telle que :
(1)∅ ∈,
(2)∀∈,∈(oùdésigne le complémentaire dedans) et
(3)∀,∈,∪∈.
1. Propriétés élémentaires :
Dans cette questiondésigne une algèbre de Boole sur.
1.a Montrer que∈.
1.b Etablir :∀,∈,∩∈et\∈.
2. Quelques exemples :
2.a Donner un exemple simple d’algèbre de Boole sur.
2.b Soit (1,2,…, partition de) une.
On considère=∪⊂ {1, 2,…,}.
∈
Montrer queest une algèbre de Boole.
2.c Iciℝ.
=
On considèrel’ensemble formé par les réunions d’un nombre fini d’intervalles deℝ.
Montrer queest une algèbre de Boole surℝ.
On rappelle au passage que l’ensemble vide est considéré être un intervalle deℝ.
3. Endomorphisme d’algèbre de Boole
Soitune algèbre de Boole sur.
On appelle endomorphisme detoute application:→telle que :
(1)∀∈,()=() et
(2)∀,∈,(∪)=()∪() .
3.a
3.b
3.c
3.d
4.
4.a
4.b
4.c
4.c.i
4.c.ii
Justifier que()=et(∅)= ∅.
Montrer que∀,∈,(∩)=()∩() et(\)=() \() .
Etablir aussi∀,∈,⊂⇒()⊂() .
On note= {∈()= ∅}appelé noyau de.
Montrer queest injective si et seulement si= {∅}.
Description des algèbres de Boole finies.
Soitune algèbre de Boole sur.
On définit une relation binaire notéesurpar :⇔ ∀∈,∈⇔∈.
Montrer queest une relation d’équivalence sur.
Pour∈, nous noterons( classe d’équivalence de) lamodulo la relation, celle-ci est
appelée atome de l’algèbre de Booleengendré par l’élément.
Soit∈. On note= {∈∈}. Etablir que()=∩.
∈
On suppose queest constitué d’un nombre fini d’éléments.
Montrer quecontient chacun de ses atomes.
Montrer que chaque élément depeut s’écrire comme une réunion finie d’atomes.
Par suitese perçoit comme étant du type vu en 2.b.
1.a
1.b
2.a
2.b
2.c
3.a
3.b
3.c
3.d
4.a
4.b
∅ ∈et=
∅donc∈.
Correction
Soit,∈.,∈puis∪∈et donc∩=∪∈.
Soit,∈.∈et∈donc\=∩∈en vertu des propriétés qui précèdent.
= {∅,}et= ℘() sont des exemples simples.
(1) Pour= ∅,∪= ∅donc∅ ∈.
∈
(2) Soit∈. Il existe⊂ {1, 2,…,}tel que=∪.
∈
Considérons aussi=∪(oùdésigne le complémentaire dedans{1, 2,…,}).
∈
On a∪=∪=et∩= ∅car (1,2,…,) est partition de.
∈{1,2,…,}
Par suite=et puisque∈on a∈.
(3) Clair, mais une rédaction possible est :
Soit,∈. Il existe,⊂ {1, 2,…,}tels que=∪et=∪.
∈ ∈
On a∪=∪avec∪⊂ {1, 2,…,}donc∪∈.
∈∪
(1) ok, compte tenu du rappel
(3) clair, puisque la réunion de deux réunions finies d’intervalles deℝest elle-même réunion finie
d’intervalles deℝ.
(2) le complémentaire d’une réunion d’intervalles deℝ« se voit bien » comme une réunion d’intervalles
deℝ, mais cette argumentation n’est guère satisfaisante. En fait :
Il est clair, que le complémentaire d’un intervalle est soit un intervalle soit une réunion de deux
intervalles. D’autre part l’intersection de deux intervalles est un intervalle (éventuellement vide).
Par suite, le complémentaire d’une réunion d’intervalles étant l’intersection des complémentaire de ces
intervalles, « se voit », après développement, comme réunion d’intervalles. Cette fois-ci la justification
est satisfaisante sans pour autant être lourdement détaillée.
On a(∅)=()=() donc()=(∪ ∅)=()∪(∅)=()∪()=puis(∅)= ∅.
Soit,∈.(∩)=(∪)=(∪)=()∪()=()∪()=()∩() et
(\)=(∩)=()∩()=() \() .
Soit,∈. Supposons⊂. On a∪=donc()=(∪)=()∪() puis
()⊂() .
est l’ensemble des antécédents de∅par.
Supposonsest injective,∅a donc au plus un antécédent par. Or∅est antécédent, donc= {∅}.
Supposons= {∅}. Soit,∈. Si()=() alors(\)=() \()= ∅donc\∈
puis\= ∅et donc⊂. De même, par symétrie,⊂puis=. Par suiteinjective.
Soit∈. Pour tout∈, on a∈⇔∈donc. Par suiteest réflexive.
Soit,∈. Sialors, pour tout∈,∈⇔∈donc∈⇔∈. Ainsi.
Puisque⇒, on peut dire queest symétrique.
Soit,,∈. Sietalors pour tout∈on a∈⇔∈et∈⇔∈donc
∈⇔∈. Ainsi. Puisqueet⇒, on peut dire queest transitive.
Finalementest une relation d’équivalence.
Soit∈() . On adonc∀∈,∈⇔∈.
Pour tout∈ᙿ
