Algèbre de Boole

En 1937, un étudiant du MIT de vingt et un ans rend un mémoire de maîtrise. Claude Shannon y remarque que l'algèbre publiée par George Boole en 1854 pour formaliser le raisonnement décrit exactement le comportement des circuits à relais des centraux téléphoniques : un relais ouvert ou fermé, une proposition fausse ou vraie, même algèbre. Le mémoire a été appelé le plus important du siècle, et il n'exagère qu'un peu — c'est lui qui autorise à calculer un circuit au lieu de le bricoler.

Ce chapitre est cette algèbre. Le chapitre 4 la câblera en portes ; ici, on apprend à poser une fonction logique, à la simplifier, et à savoir quand deux écritures différentes désignent le même circuit. La simplification n'est pas une coquetterie : chaque terme éliminé est une porte en moins, donc de la surface de silicium, de la consommation et du délai en moins.

Trois opérateurs, trois tables

Une variable booléenne ne prend que deux valeurs, 0 et 1. Trois opérateurs suffisent à tout décrire.

Les notations empruntent à l'arithmétique — produit pour le ET, somme pour le OU — et le parallèle tient tant qu'on ne l'étire pas : $1 + 1 = 1$ en logique, pas 2. Le OU booléen est inclusif : « l'un, l'autre, ou les deux ». Le « ou bien » exclusif du langage courant est un quatrième opérateur, le OU exclusif noté $a \oplus b$, vrai quand les entrées diffèrent. On le retrouvera partout au chapitre 4 : c'est la somme de l'additionneur, et le détecteur d'égalité du comparateur.

Une fonction booléenne de $n$ variables associe 0 ou 1 à chacune des $2^n$ combinaisons d'entrée. Sa table de vérité est donc de taille finie, ce qui a une conséquence forte : deux expressions sont équivalentes si et seulement si elles ont la même table, et cela se vérifie exhaustivement. Aucune autre branche des mathématiques n'offre un test d'égalité aussi brutal.

Les propriétés, et les deux qui surprennent

Beaucoup de règles sont celles de l'arithmétique : commutativité, associativité, distributivité du ET sur le OU, éléments neutres ($a \cdot 1 = a$, $a + 0 = a$) et absorbants ($a \cdot 0 = 0$, $a + 1 = 1$).

Trois s'en écartent, et ce sont celles qui font tout le travail.

L'idempotence : $a + a = a$ et $a \cdot a = a$. Un terme répété ne compte qu'une fois.

La distributivité du OU sur le ET : $a + (b \cdot c) = (a+b) \cdot (a+c)$. Elle n'a aucun équivalent arithmétique — $2 + (3 \times 4) \neq (2+3) \times (2+4)$ — et c'est elle qui rend l'algèbre de Boole duale : toute identité reste vraie en échangeant simultanément ET avec OU et 0 avec 1.

L'absorption : $a + (a \cdot b) = a$. Si $a$ suffit, préciser « $a$ et $b$ » n'apporte rien. C'est la règle qui élimine le plus de termes à la main.

Restent les théorèmes de De Morgan, les plus utiles du chapitre :

En français : la négation d'un ET est le OU des négations, et réciproquement. « Il est faux que la porte soit fermée et l'alarme active » équivaut à « la porte est ouverte ou l'alarme est inactive ». La faute classique consiste à distribuer la barre sans changer l'opérateur, et elle donne un circuit faux — pas seulement inélégant.

De Morgan a une conséquence pratique majeure, exploitée au chapitre 4 : le NON-ET (NAND) est universel. Toute fonction booléenne se construit avec des NAND seuls, et c'est pourquoi les technologies de fabrication en font leur brique de base.

Les formes canoniques

Toute fonction, si tordue soit son énoncé, s'écrit mécaniquement à partir de sa table de vérité. C'est ce qui permet de partir d'un cahier des charges en français et d'arriver à un circuit sans intuition.

La forme canonique disjonctive, dite somme de produits, se lit sur les lignes où la fonction vaut 1. Pour chacune, on écrit le produit de toutes les variables — barrées si elles valent 0 sur cette ligne — puis on fait le OU de ces produits. Chaque produit s'appelle un minterme.

Prenons la fonction « majorité » de trois variables, vraie dès que deux entrées au moins valent 1 — c'est le vote majoritaire des systèmes redondants, et la retenue sortante de l'additionneur du chapitre 4.

La forme conjonctive, ou produit de sommes, est la duale : elle se lit sur les lignes à 0, chaque ligne donnant une somme dont les variables sont barrées si elles valent 1. On la préfère quand la fonction est majoritairement vraie — il y a alors moins de lignes à écrire.

Ces formes ont une vertu et un défaut. La vertu : elles sont automatiques, donc jamais fausses. Le défaut : elles sont grosses. Quatre mintermes de trois variables, c'est quatre portes ET à trois entrées plus une porte OU à quatre entrées — là où la fonction majorité s'écrit en réalité $ab + ac + bc$, trois portes ET à deux entrées.

Simplifier par tableau de Karnaugh

On peut simplifier à l'algèbre, mais c'est long et l'on ne sait jamais si l'on a fini. Le tableau de Karnaugh rend la simplification visuelle et permet de la mener jusqu'au bout.

Le tableau est une table de vérité repliée en deux dimensions, dont les en-têtes suivent un code de Gray : 00, 01, 11, 10. Ce n'est pas une coquetterie d'ordre — c'est le cœur de la méthode. Dans cet ordre, deux cases voisines ne diffèrent que par une seule variable, donc leur regroupement élimine cette variable : $ab + a\bar{b} = a(b + \bar{b}) = a$.

Voici la fonction majorité, avec $a$ en ligne et $bc$ en colonne :

La méthode tient en quatre règles.

1. On entoure des rectangles de 1 dont la taille est une puissance de 2 : 1, 2, 4, 8 cases. Jamais 3, jamais 6.
2. On les prend aussi grands que possible : un groupe de $2^k$ cases élimine $k$ variables.
3. Les groupes peuvent se chevaucher — l'idempotence l'autorise, $a + a = a$.
4. Le tableau est torique : les bords gauche et droit sont adjacents, de même que le haut et le bas. C'est l'oubli le plus fréquent, et il coûte systématiquement un terme.

Sur la majorité, trois groupes de deux cases suffisent : la colonne 11 donne $bc$, la paire (1,01)-(1,11) donne $ac$, la paire (1,11)-(1,10) donne $ab$. D'où :

On est passé de quatre termes de trois variables à trois termes de deux. Il faut couvrir tous les 1 et aucun 0 ; un groupe entièrement recouvert par les autres est inutile et se retire.

Deux remarques de terrain. Le Karnaugh reste lisible jusqu'à quatre variables, tolérable à cinq, inutilisable au-delà — les outils de synthèse emploient alors des algorithmes comme Quine-McCluskey. Et lorsque certaines combinaisons d'entrée ne peuvent pas se produire, on note leur sortie « indifférente » et on s'autorise à les compter comme des 1 quand cela agrandit un groupe, comme des 0 sinon : c'est gratuit, et cela simplifie beaucoup.

À vous

L'exercice construit la table de vérité d'une expression, puis compare deux écritures. C'est l'outil qui manque le plus en TD : il transforme « je crois que c'est équivalent » en preuve, puisque l'exhaustivité sur $2^n$ lignes est un test complet.

Vous vérifierez d'abord De Morgan, puis la simplification de la fonction majorité obtenue au Karnaugh — et enfin une simplification volontairement fausse, pour voir la table diverger.

// Une fonction booléenne de n variables est ici une fonction JS qui reçoit
// un tableau de 0/1. On énumère les 2^n entrées et on compare les sorties.

function table(f, n) {
  const lignes = [];
  for (let m = 0; m < (1 << n); m++) {
    // Bit de poids fort = première variable, pour lire comme au tableau.
    const e = [];
    for (let i = n - 1; i >= 0; i--) e.push((m >> i) & 1);
    lignes.push({ e, s: f(e) ? 1 : 0 });
  }
  return lignes;
}

function equivalentes(f, g, n, nom) {
  const tf = table(f, n), tg = table(g, n);
  const ecarts = tf.filter((l, i) => l.s !== tg[i].s);
  console.log(nom + " : " + (ecarts.length === 0 ? "équivalentes" : "DIFFÉRENTES"));
  for (const l of ecarts) {
    console.log("   contre-exemple " + l.e.join("") + " -> " +
                l.s + " contre " + tg[table(g, n).indexOf(l)]);
  }
  return ecarts.length === 0;
}

// ── De Morgan ─────────────────────────────────────────────────────────────
const gauche = ([a, b]) => !(a && b);
const droite = ([a, b]) => !a || !b;
equivalentes(gauche, droite, 2, "De Morgan  non(a.b) = na + nb");

// ── Majorité : forme canonique contre forme simplifiée ────────────────────
// Vraie dès que deux entrées au moins valent 1.
const canonique = ([a, b, c]) =>
  (!a && b && c) || (a && !b && c) || (a && b && !c) || (a && b && c);

const simplifiee = ([a, b, c]) => (a && b) || (a && c);   // ← il manque un terme

equivalentes(canonique, simplifiee, 3, "Majorité");

// ── À VOUS ────────────────────────────────────────────────────────────────
// 1. Le Karnaugh donnait ab + ac + bc. Corrigez simplifiee et relancez.
// 2. Écrivez le OU exclusif a XOR b de deux façons — (a et non b) ou
//    (non a et b), puis a différent de b — et vérifiez leur équivalence.

En travaux pratiques

Ce que la suite en fait

Chaque objet de ce chapitre a un équivalent matériel immédiat, et le chapitre 4 ne fera guère que traduire. Une expression devient un assemblage de portes ; une somme de produits devient deux étages de portes ; De Morgan devient la possibilité de tout construire en NAND ; et le nombre de termes après Karnaugh devient un nombre de transistors.

La fonction majorité étudiée ici n'a rien d'un exemple gratuit : c'est exactement la retenue sortante de l'additionneur complet. Vous l'avez déjà simplifiée, il ne restera qu'à la câbler.

À retenir