Algèbre de Boole

Dans l’intégralité de ce problème, E désigne un ensemble.

On appelle algèbre de Boole sur l’ensemble E , toute partie A de ( )E℘ telle que :

(1) ∅∈A ,

(2) ,A A∀ ∈ ∈A A (où A désigne le complémentaire de A dans E ) et

(3) , ,A B A B∀ ∈ ∪ ∈A A .

1. Propriétés élémentaires : Dans cette question A désigne une algèbre de Boole sur E .

1.a Montrer que E ∈A .

1.b Etablir : , ,A B A B∀ ∈ ∩ ∈A A et \A B ∈A .

2. Quelques exemples :

2.a Donner un exemple simple d’algèbre de Boole sur E .

2.b Soit 1 2( , , , )nE E E… une partition de E .

On considère { }1,2, ,i

i I

E I n∈

= ⊂

A …∪ .

Montrer que A est une algèbre de Boole.

2.c Ici E =ℝ . On considère A l’ensemble formé par les réunions d’un nombre fini d’intervalles de ℝ . Montrer que A 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 A une algèbre de Boole sur E . On appelle endomorphisme de A toute application :f →A A telle que :

(1) , ( ) ( )A f A f A∀ ∈ =A et

(2) , , ( ) ( ) ( )A B f A B f A f B∀ ∈ ∪ = ∪A .

3.a Justifier que ( )f E E= et ( )f ∅ =∅ .

3.b Montrer que , , ( ) ( ) ( )A B f A B f A f B∀ ∈ ∩ = ∩A et ( \ ) ( ) \ ( )f A B f A f B= .

3.c Etablir aussi , , ( ) ( )A B A B f A f B∀ ∈ ⊂ ⇒ ⊂A .

3.d On note { }( )A f A= ∈ =∅K A appelé noyau de f .

Montrer que f est injective si et seulement si { }= ∅K .

4. Description des algèbres de Boole finies. Soit A une algèbre de Boole sur E .

4.a On définit une relation binaire notée R sur E par : ,x y A x A y A⇔ ∀ ∈ ∈ ⇔ ∈R A . Montrer que R est une relation d’équivalence sur E . Pour x E∈ , nous noterons ( )Cl x la classe d’équivalence de x modulo la relation R , celle-ci est

appelée atome de l’algèbre de Boole A engendré par l’élément x .

4.b Soit x E∈ . On note { }x X x X= ∈ ∈A A . Etablir que ( )xX

Cl x X∈

=A

∩ .

4.c On suppose que A est constitué d’un nombre fini d’éléments.

4.c.i Montrer que A contient chacun de ses atomes.

4.c.ii Montrer que chaque élément de A peut s’écrire comme une réunion finie d’atomes. Par suite A se perçoit comme étant du type vu en 2.b.

Devoirs Maison2017-2018

My Ismail Mamouni

http ://myismail.net.

Ensembles&ApplicationsLundi 13 Novembre 2017

Niveau III

1

Correction

1.a ∅∈A et E =∅ donc E ∈A .

1.b Soit ,A B ∈A . ,A B ∈A puis A B∪ ∈A et donc A B A B∩ = ∪ ∈A .

Soit ,A B ∈A . A∈A et B ∈A donc \A B A B= ∩ ∈A en vertu des propriétés qui précèdent.

2.a { },E= ∅A et ( )E=℘A sont des exemples simples.

2.b (1) Pour I =∅ , i

i I

E∈

=∅∪ donc ∅∈A .

(2) Soit A∈A . Il existe { }1,2, ,I n⊂ … tel que i

i I

A E∈

=∪ .

Considérons aussi i

i I

B E∈

=∪ (où I désigne le complémentaire de I dans { }1,2, ,n… ).

On a { }1,2, ,

i

i n

A B E E∈

∪ = =…

∪ et A B∩ =∅ car 1 2( , , , )nE E E… est partition de E .

Par suite B A= et puisque B ∈A on a A∈A . (3) Clair, mais une rédaction possible est : Soit ,A B ∈A . Il existe { }, 1,2, ,I J n⊂ … tels que i

i I

A E∈

=∪ et i

i J

B E∈

=∪ .

On a i

i I J

A B E∈ ∪

∪ = ∪ avec { }1,2, ,I J n∪ ⊂ … donc A B∪ ∈A .

2.c (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.

3.a On a ( ) ( ) ( )f f E f E∅ = = donc ( ) ( ) ( ) ( ) ( ) ( )f E f E f E f f E f E E= ∪∅ = ∪ ∅ = ∪ = puis ( )f ∅ =∅ .

3.b Soit ,A B ∈A . ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )f A B f A B f A B f A f B f A f B f A f B∩ = ∪ = ∪ = ∪ = ∪ = ∩ et

( \ ) ( ) ( ) ( ) ( ) \ ( )f A B f A B f A f B f A f B= ∩ = ∩ = .

3.c Soit ,A B ∈A . Supposons A B⊂ . On a A B B∪ = donc ( ) ( ) ( ) ( )f B f A B f A f B= ∪ = ∪ puis

( ) ( )f A f B⊂ .

3.d K est l’ensemble des antécédents de ∅ par f .

Supposons f est injective, ∅ a donc au plus un antécédent par f . Or ∅ est antécédent, donc { }= ∅K .

Supposons { }= ∅K . Soit ,A B ∈A . Si ( ) ( )f A f B= alors ( \ ) ( ) \ ( )f A B f A f B= =∅ donc \A B ∈K

puis \A B =∅ et donc A B⊂ . De même, par symétrie, B A⊂ puis A B= . Par suite f injective.

4.a Soit x E∈ . Pour tout A∈A , on a x A x A∈ ⇔ ∈ donc x xR . Par suite R est réflexive. Soit ,x y E∈ . Si x yR alors, pour tout A∈A , x A y A∈ ⇔ ∈ donc y A x A∈ ⇔ ∈ . Ainsi y xR . Puisque x y y x⇒R R , on peut dire que R est symétrique.

Soit , ,x y z E∈ . Si x yR et y zR alors pour tout A∈A on a x A y A∈ ⇔ ∈ et y A z A∈ ⇔ ∈ donc

x A z A∈ ⇔ ∈ . Ainsi x zR . Puisque x yR et y z x z⇒R R , on peut dire que R est transitive. Finalement R est une relation d’équivalence.

4.b Soit ( )y Cl x∈ . On a x yR donc ,A x A y A∀ ∈ ∈ ⇔ ∈A .

Pour tout xX ∈A , on a x X∈ donc y X∈ . Par suite xX

y X∈

∈A

∩ .

Ainsi ( )xX

Cl x X∈

⊂A

∩ .

Devoirs Maison2017-2018

My Ismail Mamouni

http ://myismail.net.

2

Inversement : Soit

xX

y X∈

∈A

∩ .

Pour tout A∈A . Si xA∈A alors y A∈ et x A∈ .

Si xA∉A alors x A∉ donc x A∈ puis xA∈A . Par suite y A∈ et donc y A∉ .

Dans les deux cas, on a x A y A∈ ⇔ ∈ .

Ainsi x yR puis ( )y Cl x∈ et donc ( )xX

X Cl x∈

⊂A

∩

Par double inclusion : ( )xX

Cl x X∈

=A

∩ .

4.c.i Soit x E∈ . On reprend, les notations du 3.b et on étudie l’atome ( )xX

Cl x X∈

=A

∩

Puisque A est fini, xA est aussi fini et puisque l’intersection de deux éléments de A est encore élément

de A , on peut affirmer que ( )xX

Cl x X∈

=A

∩ est élément de A comme intersection d’un nombre fini

d’éléments de A .

4.c.ii Soit A∈A . Notons ( )x A

B Cl x∈

=∪ et montrons A B= .

x A∀ ∈ , on a ( )Cl x A⊂ compte tenu de la description de ( )Cl x obtenue en 3.b. Par suite B A⊂ .

D’autre part, , ( )x A x Cl x∀ ∈ ∈ donc x B∈ puis A B⊂ . Par double inclusion A B= .

Ainsi A se perçoit comme réunion d’atomes. Puisque, A est fini et que les atomes sont éléments de A , il n’existe qu’un nombre fini d’atomes

distincts. En éliminant, les atomes identiques dans la description ( )x A

A Cl x∈

=∪ , il ne reste alors plus

qu’un nombre fini d’atomes et finalement A se voit comme union d’un nombre fini d’atomes.

Devoirs Maison2017-2018

My Ismail Mamouni

http ://myismail.net.

3