6  Algèbre de Boole

• Définitions et propriétés
• Fonctions booléennes
• Fonctions caractéristiques

Les algèbres de Boole ont été introduites par le mathématicien anglais George Boole au milieu du 19ème siècle comme base pour le raisonnement logique.

6.1  Définitions et propriétés

Nous avons donné une caractérisation des algèbres de Boole comme des treillis distributifs complémentés. Dans ce chapitre nous allons plutôt regarder la définition algébrique.

On en déduit que les opérations ⊔ et ⊓ sont idempotentes, associatives, commutatives et distributives l’une par rapport à l’autre et qu’elle vérifient les lois d’absorption x ⊓ (x ⊔ y) = x = (y ⊓ x) ⊔ x ainsi que les propriétés des éléments minimum (⊥) et maximum (⊤) et du complément x.

6.1.1  Exemples

Soit E un ensemble non vide alors l’ensemble ℘(E) des parties de E est une algèbre de Boole. ⊥=∅, ⊤=E, a ⊓ b =a ∩ b, a ⊔ b =a ∪ b et ā=E∖ a.

L’ensemble B={0,1 } est une algèbre de Boole appelé ensemble des booléens avec ⊥=0, ⊤=1, a ⊓ b =min(a,b), a ⊔ b =max(a,b) et ā=1−a.

L’ensemble Bⁿ des n-uplets de booléens est une algèbre de Boole avec ⊥=0ⁿ (le n-uplet qui ne contient que des 0), ⊤=1ⁿ, a ⊓ b =(min(a_k,b_k))_k, a ⊔ b =(max(a_k,b_k))_k et ā=(1−a_k)_k.

Notations.

On utilise parfois des notations alternatives pour les algèbres de Boole. On note 0=⊥ et 1=⊤ et on note l’opération ⊔ comme une addition +^. et ⊓ comme un produit.

Ces opérations satisfont des propriétés analogues à l’addition et la multiplication sur les entiers : elles sont associatives, commutatives, distributives l’une par rapport à l’autre et ont respectivement 0 et 1 comme élément neutre. Par contre, il faut faire attention qu’elles ont également des propriétés différentes comme l’idempotence x+^. x = xx = x. L’addition ordinaire sur les entiers est reliée à l’addition booléenne par la relation :
x +^. y = x + y − xy.

6.1.2  Anneau de Boole

Une opération intéressante sur les algèbres de boole est la construction a ⊕ b  =^def  ab+āb.

Cette opération est associative et commutative, elle vérifie de plus :

• ∀ x, x ⊕ x = 0
• ∀ x, x ⊕ 0 = x
• ∀ x y z, (x ⊕ y)z = xz⊕ yz
• ∀ x, x ⊕ 1 = x
• ∀ x y, x +^. y = x⊕ y ⊕ xy

Dans le cas de l’algèbre des booléens B, cette opération correspond au ou-exclusif. Dans le cas des ensembles, cela correspond à la différence symétrique : X⊕ Y = X ∖ Y ∪ Y ∖ X.

Une présentation alternative d’une algèbre de Boole est de se donner uniquement un ensemble E et sur cet ensemble les opérations ⊕, le produit, 0 et 1. On parle alors d’anneau de Boole. On en déduit l’opération de complément et l’addition booléenne en utilisant les égalités ci-dessus.

6.2  Fonctions booléennes

Les fonctions booléennes apparaissent naturellement dans la modélisation de nombreux problèmes. Par exemple, si on se donne un circuit électronique avec un point d’entrée et un point de sortie et des interrupteurs, chaque interrupteur peut être associé à une variable booléenne qui vaut 1 si l’interrupteur est fermé (et donc laisse passer le courant) et 0 sinon. La fonction booléenne représentera alors le fait que le courant puisse ou non passer dans le circuit du point d’entrée au point de sortie.

On peut également interpréter une fonction booléenne comme un ensemble de n-uplets de booléens à savoir l’ensemble des n-uplets pour lesquels la fonction vaut 1. Les n-uplets de booléens peuvent eux-même servir à représenter des objets diverses : des entiers bornés en machine, des images …

L’ensemble des n-uplets de booléens contient 2ⁿ éléments. Si on choisit de les ordonner de manière canonique (par exemple dans l’ordre lexicographique) alors une fonction booléenne est uniquement déterminée par un 2ⁿ-uplet de booléens correspondant aux résultats de la fonction pour chaque entrée.

Une fonction booléenne f peuvent s’écrire sous forme normale disjonctive comme la somme de produits de litteraux (variables, ou complément de variable) ou bien sous forme normale conjonctive comme produit de sommes de litteraux.

6.3  Fonctions caractéristiques

On a vu que l’ensemble ℘(E) des parties d’un ensemble E est une algèbre de Boole.

Nous allons nous intéresser à une représentation alternative des ensembles comme des applications à valeur booléennes appelées fonctions caractéristiques.

Soit B^E l’ensemble des applications de E dans l’ensemble des booléens B.

On construit ensuite une application F de ℘(E) dans B^E qui à A∈ ℘(E) associe χ_A ∈ B^E.

Nous allons montrer que cette application est une bijection. Pour cela il suffit de construire l’application inverse G de B^E dans ℘(E) qui à une fonction f de B^E associe l’ensemble A={x ∈ A  | f(x)=1} et de montrer que ∀ A ⊆ E, G(F(A))=A et ∀ f∈ B^E,F(G(f))=f ce qui est trivial.

On peut alors s’intéresser à quelles opérations sur B^E correspondent les opérations de l’algèbre de Boole sur ℘(E).

Les opérations usuelles sur les booléens sont étendues point à point en des opérations sur les fonctions à valeurs booléennes. Par exemple l’addition sur les booléens permet de définir une addition entre fonctions booléennes. Si f et g sont des éléments de B^E, alors f+^. g est un élément de B^E qui est défini par (f+^. g)(x) =^def  f(x) +^. g(x).

Ordre

On regarde tout d’abord la notion d’ordre :

A ⊆ B ⇔ χA ≤ χB ⇔ ∀ x∈ E, χA(x)≤ χB(x)

Plus petit élément

Le plus petit élément de ℘(E) est l’ensemble vide qui correspond à la fonction parfois notée 0 qui vaut partout 0.

∀ x, χ∅(x)=0

Plus grand élément

Le plus grand élément de ℘(E) est l’ensemble E qui correspond à la fonction parfois notée 1 qui vaut partout 1.

∀ x, χE(x)=1

Borne inférieure

La borne inférieure des ensembles A et B est A ∩ B. La fonction caractéristique de A ∩ B correspond au produit des fonctions caractéristiques de A et B. On a :

χA⋂ B = χA χB         avec (χA χB)(x)

def =

χA(x)χB(x)

Borne supérieure

La borne supérieure des ensembles A et B est A ∪ B. La fonction caractéristique de A ∪ B correspond à la somme booléenne des fonctions caractéristiques de A et B.

χA⋃ B = χA

. +

χB= χA + χB−χAχB         avec (χA + χB)(x)

def =

χA(x) + χB(x)

Complément

Le complément de l’ensemble A est E ∖ A .

χE∖ A = 1−χA         avec (1−χA)(x)

def =

1−χA(x)

Les fonctions caractéristiques peuvent être utiles pour compter les éléments d’un ensemble A inclut dans un ensemble fini E. En effet si E est un ensemble fini, alors pour tout A inclus dans E, on a :

Cette égalité ainsi que les propriétés des fonctions caractéristiques nous permettent de déduire des formules pour calculer le cardinal de certains ensembles.

On a χ_Ā=1−χ_A donc |Ā|=|E|−|A|

On a χ_{A∪ B}=χ_A+χ_B−χ_{A∩ B} donc |A ∪ B|=|A|+|B|−|A∩ B|

Une autre exemple est de compter les nombres entre 1 et 12000 qui sont soit un multiple de 4, soit un multiple de 6. On va dénombrer les ensembles A₄ (resp. A₆, resp. A₁₂) des nombres entre 1 et 12000 qui sont multiples de 4 (resp. multiples de 6, resp. multiples de 4 et 6, c’est-à-dire multiples de 12).

A₄={4k|1≤ 4k ≤ 12000}={4k|1≤ k ≤ 3000} donc |A₄|=3000 de même A₆={6k|1≤ k ≤ 2000} A₁₂={12k|1≤ k ≤ 1000} donc |A₆|=2000 et |A₁₂|=1000 et finalement |A|=3000+2000−1000=4000.