Correction : Algèbre générale, Algèbre de Boole

David Delaunay Http://Mpsiddl.Free.Fr

Description

Opération sur les ensembles. Relation d'équivalence (hors-programme).

Sujets

• Classe préparatoire aux grandes écoles
• Mathématiques, physique et sciences de l'ingénieur
• Public Readiness and Emergency Preparedness Act
• exercices

Informations

• Publié par: algebre-mpsi
• Nombre de lectures: 307
• Licence : En savoir +
  Paternité, pas d'utilisation commerciale, partage des conditions initiales à l'identique
• Langue: Français

Extrait

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 partiede℘() telle que :

(1)∅ ∈,
(2)∀∈,∈(oùdésigne le complémentaire dedans) et
(3)∀,∈,∪∈.
1. Propriétés élémentaires :
Dans cette questiondé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 queest une algèbre de Boole.
2.c Iciℝ.
=
On considèrel’ensemble formé par les réunions d’un nombre fini d’intervalles deℝ.
Montrer queest 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
Soitune algèbre de Boole sur.
On appelle endomorphisme detoute 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 queest injective si et seulement si= {∅}.
Description des algèbres de Boole finies.
Soitune algèbre de Boole sur.
On définit une relation binaire notéesurpar :⇔ ∀∈,∈⇔∈.
Montrer queest une relation d’équivalence sur.
Pour∈, nous noterons( classe d’équivalence de) lamodulo la relation, celle-ci est
appelée atome de l’algèbre de Booleengendré par l’élément.
Soit∈. On note= {∈∈}. Etablir que()=∩.
∈
On suppose queest constitué d’un nombre fini d’éléments.
Montrer quecontient chacun de ses atomes.
Montrer que chaque élément depeut s’écrire comme une réunion finie d’atomes.
Par suitese 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 dedans{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.
Supposonsest 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 suiteinjective.
Soit∈. Pour tout∈, on a∈⇔∈donc. Par suiteest réflexive.
Soit,∈. Sialors, pour tout∈,∈⇔∈donc∈⇔∈. Ainsi.
Puisque⇒, on peut dire queest symétrique.
Soit,,∈. Sietalors pour tout∈on a∈⇔∈et∈⇔∈donc
∈⇔∈. Ainsi. Puisqueet⇒, on peut dire queest transitive.
Finalementest une relation d’équivalence.
Soit∈() . On adonc∀∈,∈⇔∈.
Pour tout∈ᙿ