Alors voilà...

"Une proposition peut être vraie OU fausse, mais ne peut pas être vraie ET fausse".

Non, non, et non, cette phrase n'est pas extraite des Mémoires du Seigneur de la PaliceMaréchal de France, moins connu sous le nom de Jacques de Chabannes [~1470-1525] qui, s'il avait su ce que l'Histoire ferait de son nom, ne se serait sûrement pas fendu la cuirasse à si vaillamment servir Charles VIII, Louis XII et François Ier !. Cette dépotante évidence est signée... Aristote [~384~322] !
Et oui ! Parfaitement, M'sieurs Dames ! De la Logique aristotélicienne ! De la Sagesse 100% grecque ! De la vraie Philosophie péripatéticienne et deux fois millénaire... Un minimum de respect, donc.

Comment ça, "vérité de comptoir" ? Douteriez-vous du très haut intérêt de ce genre de désarmante tautologie ? Et pourtant ! Avec sa jugeote pour seul diplôme, un certain George Boole a bâti sur ce truisme les axiomes d'une algèbre assez révolutionnaire dont les théories, lorsqu'elles se marieront aux technologies de l'électronique près d'un siècle plus tard, donneront naissance à une machine assez prometteuse appelée ordinateur.

Truisme, axiomes, tautologie... No panic ! L'algèbre de Boole, quand on sait laEt oui, "algèbre", comme tout ce qui est un peu mystérieux, est du genre féminin. prendre, est d'une logique déconcertante. Nul besoin, donc, à l'évocation de Boole, de flipperpfffff....

Arcana Percipio vous propose aujourd'hui un circuit touristique inédit, un voyage initiatique depuis les Mathématiques les plus abstraites jusqu'aux tripes électroniques de votre puce préférée.
Allez, roule Boole !

L'algèbre booléenne

Boole, qui est-cePardon ? ?

George Boole. Ici sans son cocker...George Boole nait en 1815 à Lincoln, Angleterre.
A ses débuts, le petit Boole verse plutôt dans le LatinAujourd'hui, le Latin a été remplacé par Super Mario contre les Lapins Crétins.
Le progrès, sans doute..., son premier amour, et c'est plus âgé qu'il se tourne vers les Mathématiques. Totalement autodidacte, son étude sur les équations différentielles lui vaut une chaire à l'université de Cork.

En 1854, sa publication "An investigation into the Laws of Thought, on Which are founded the Mathematical Theories of Logic and ProbabilitiesLe livre de Boole, in extenso." parvient à marier de manière éclatante les mathématiques à la logique, discipline qu'il arrache de fait aux philosophes de l'époque...qui, il faut bien le dire, n'en n'avait pas fait grand chose depuis Aristote...
Finalement, c'est peut-être ça le vrai progrès: offrir aux philosophes des occasions de se taire....

Honoré à Oxford, Boole devient membre de la "Royal Society" la même année, mais meurt précocement, en 1864, des suites des théories de Madame Boole..qui n'était pas d'origine brésilienne, non. Juste une sommité de la médecine alternative.
Normal, pour une nièce de Sir Everest... sur la meilleure manière de guérir une grippe.

Les lois de la pensée

Pour un non-cartésien comme l'auteur de cette page, le meilleur moyen d'approcher Boole, c'est encore de l'attaquer par derrière, l'air de rien, en faisant mine de s'amuser avec quelques dessins. Quels dessins ? Des dessins de partiesOui, tout cela est plutôt logique..., ou pour parler doctoralement, de sous-ensembles. Nous allons donc procéder de la sorte, entremêlant de façon parfaitement naïve algèbre de Boole et théorie des ensembles.
Normalement, ça ne fait pas malSi, néanmoins, un mathématicien devait se blesser en lisant ces lignes, il peut toujours (1) gentiment demander à l'auteur de cette page de cesser de martyriser ainsi les Saintes Mathématiques ou (2) charitablement lui indiquer comment adoucir les éventuelles aberrations de ce récit.
En tout cas, nous demanderons à ce maître en Boole de s'en abstenir, justement....

Les parties de Boole

A la source de l'inspiration de Boole, l'intime conviction que l'algèbre traditionnelle, celle qu'il baptise lui-même "l'algèbre d'école", n'est rien d'autre que l'application aux nombres de schémas de pensée plus fondamentaux par lesquels l'esprit humain manipule, combine et redéfinit ses concepts logiques (que Boole appelle classes) selon les lois immuables de la pensée ("the laws of thought").

De manière fort simple, nous pourrions définir une classe comme l'ensemble de tous les éléments partageant un même nom ou une même caractéristique, comme par exemple "les êtres humains", "les rivières"...exemples gracieusement apportés par Boole lui-même dans son ouvrage., "les cornets à piston", "les jours de grève à la SNCF"Ça, c'est un apport personnel de l'auteur de cette page à la compréhension globale du sujet., etc.

Ceci convenu, en imaginant deux classes A et B quelconques, Boole définit trois opérations fondamentales de l'esprit susceptible de s'exercer sur elles:

• Le produit logique (logical product), que nous noterions A x B (ou A . B, ou encore AB), définissant la classe des éléments obéissant simultanément aux définition des classes A et B;

Produit de première urgence

En absence de toute parenthèses explicites, le produit logique est prioritaire sur la somme logique.
Ainsi, (A.B)+C peut donc également s'écrire A.B+C.

• La somme logique (logical sum), que nous noterions A + B, définissant la classe des éléments obéissant à l'une ou l'autre des définitions des classes A et B;
• La complémentation (negation), que nous noterions A (ou B), définissant la classe des éléments n'obéissant pas à la définition de la classe A (ou B).

Mais ne nous emballons pas et appuyons-nous pour continuer sur l'exemple des deux classes suivantes:

• La classe A définie comme "les chasseurs",
• La classe B définie comme "les myopes".

Partant de ces deux simples définitions, nous pouvons très facilement, par le jeu de notre seule pensée, définir quatre autres classes:

• La classe A.B définie comme "les chasseurs myopes...des gars généralement très sympas.
  Au boulot.",
• La classe A+B définie comme "les chasseurs et les myopes".
• La classe A définie comme "les non-chasseurs",
• La classe B définie comme "les non-myopes".

Il existe un moyen très visuel de traduire ces concepts un peu abstraits: il consiste à considérer les classes de Boole comme des ensemblesL'idée n'est pas si niaise puisqu'un grand mathématicien anglais, John Venn [1834-1923] nous a d'ailleurs précédés.. Dès lors, les opérations fondamentales de Boole prennent des noms plus familiers à nos souvenirs scolaires:

• La somme logique de deux classes se traduit par l'union (∪) entre les deux ensembles correspondants,
• Le produit logique par l'intersection (∩),
• La complémententation par... le complément.
   

Les évidences booléennes

Avec un poil de curiosité mathématique, nous pourrions facilement constater que ces opérations fondamentales obéissent à quelques propriétés plus ou moins classiques mais si foncièrement évidentes qu'indémontrables.
Ce sont les axiomes de l'algèbre booléenne.

Ainsi, en reprenant nos deux classes exemples A ("les chasseurs") et B ("les myopes") et en y ajoutant pour l'occasion une troisième classe C définie comme "les buveurs excessifs", on ne peut nier que:

• A + B = B + ALa classe des chasseurs et des myopes est la même que la classe des myopes et des chasseurs. et A . B = B . ALa classe des chasseurs myopes est la même que la classe des myopes chasseurs., c'est la commutativité;
• (A + B) + C = A + (B + C)La classe des chasseurs et des myopes auxquels s'ajoutent les buveurs excessifs est la même que la classe des chasseurs auxquels s'ajoutent les myopes et les buveurs excessifs. et (A . B) . C = A . (B . C)La classe des chasseurs myopes également buveurs excessifs est la même que la classe des chasseurs également myopes buveurs excessifs. , c'est l'associativité;
• (A + B) . C = (A . C) + (B . C)La classe des chasseurs et des myopes, tous buveurs excessifs est la même que la classe des chasseurs buveurs excessifs et des myopes buveurs excessifs. mais aussi...et ce qui nous démontre combien la somme et le produit logiques ne sont absolument pas comparables avec la somme et le produit arithmétiques. (A . B) + C = (A + C) . (B + C)La classe des chasseurs myopes et des buveurs excessifs est la même que la classe des chasseurs et des buveurs excessifs parmi les chasseurs et les myopes., c'est la distributivité;

Avec un effort de curiosité supplémentaire, nous pourrions même sans trop de problème imaginer l'existence de deux classes "remarquables", notons les "0" et "1" qui, quelle que soit la classe A, vérifieraient toujours:

• A + 0 = A
  Dans l'esprit de Boole, cet élément 0 correspondait à une sorte de classe impossible, mais sur nos petits dessins à nous, on l'assimilera à l'élément vide {Ø}.
• A . 1 = A
  Pour Boole, cet élément 1 symbolisait la classe universelle, un espèce de grand Tout. Moins ambitieux, nous l'assimilerons sur nos dessins à E, la totalité du référentiel.

Un bon mathématicien dirait alors de 0 et 1 qu'ils sont éléments neutres: 0 à l'égard de la somme logique (+), et 1 à l'égard du produit logique (.).
Et le lascar en profiterait sans doute pour pour nous asséner un dernier axiome bien senti, tout aussi évident que les autres, qu'il appellerait axiome de la complémentation et qui dirait, de manière bien moins poétique qu'Aristote, que:

• A + A = 1La classe des chasseurs et des non-chasseurs donne tout., également appelé "loi du tiers exclu",
• A . A = 0La classe des chasseurs non-chasseurs est vide., également appelé "principe de contradiction".

Comme pour nous rassurer, ces cinq axiomes fondamentaux de l'algèbre de Boole sont tous confirmés par nos modestes petits dessins. Nous verrons par la suite pourquoi ceci (nos dessins) explique si bien cela (l'algèbre de Boole).

Bon ! Maintenant, quelques minutes d'intense phosphorage neuronal...
Ça risque de secouer un brin...

Les théorèmes de l'algèbre booléenne

A partir des lois booléennes fondamentales et évidentes que nous venons de détailler, il est tout à fait possible, à l'aide de raisonnements logiques appelés démonstrations, d'établir quelques autres propositions utiles que nous appellerons théorèmes de l'algèbre de Boole:

• Théorème de l'unicité du complément: pour toute classe A, il existe une et une seule classe A telle que:
  A + A = 1 et A . A = 0
Démonstration

Postulons qu'il existe une autre classe A' que A vérifiant à la fois A + A' = 1 et A . A' = 0.

Si A + A' = 1, on a aussi A .(A + A') = A . 1 (en faisant apparaître le terme A de part et d'autre de l'égalité)

1 étant élément neutre pour le produit logique, on a bien A . (A + A') = A . 1 = A

et, en distribuant: A . (A + A') = A . A + A . A' = A

Or, d'après l'axiome de la complémentation, on a A . A = 0

d'où, 0 étant élément neutre pour la somme logique: A . A' = A, qu'on garde bien au chaud (*)... 
 

D'autre part, l'axiome de la complémentation nous dit que A + A = 1.

En ajoutant le terme A' de part et d'autre de l' égalité, on obtient: (A + A) . A' = 1 . A'

1 étant élément neutre pour le produit logique, on a: (A + A) . A' = 1 . A' = A',

il vient, en distribuant: (A + A) . A' = A . A' + A . A' = A'

Comme, selon notre postulat, A . A' = 0

0 étant élément neutre pour la somme logique, on obtient A . A' = A'

d'où, en nous rappelant à point nommé l'égalité (*), il vient: A = A'
CQFD !

Boirais bien un truc, moi...

• Théorème de l'idempotence (idempotency): pour toute classe A, on a A + A = ALa classe des chasseurs et des chasseurs est la classe des chasseurs. et A . A = ALa classe des chasseurs chasseurs est la classe des chasseurs..
  Boole appelait "loi fondamentale de la pensée" cette déstabilisante égalité A² = A.
Démonstration

Vérifions d'abord que A + A = A.
Nous savons que A = 0 + A puisque 0 est élément neutre pour la somme logique.

Selon l'axiome de la complémentation A . A = 0, on a donc aussi A = A . A + A

En distribuant, on obtient: A = (A + A) . (A + A)

Or, selon l'axiome de la complémentation A + A = 1, il vient donc A = (A + A) . 1

Et comme 1 est élément neutre pour le produit logique, on trouve bien: A = A + A

Vérifions ensuite que A . A = A
1 étant élément neutre pour le produit logique, on a A = 1 . A

Or, selon l'axiome de la complémentation, 1 = A + A, et donc A = (A + A) . A

En distribuant, il vient: A = (A . A) + (A . A)

Or, d'après l'axiome de la complémentation, A . A = 0, d'où A = (A . A) + 0

Et 0 étant élément neutre pour la somme logique, on retrouve bien A = A . A

• Unicité des compléments des constantes 0 et 1: 0 = 1 et 1 = 0
• Théorèmes des éléments absorbants: A + 1 = 1La classe des chasseurs et de tout le reste est la classe de tout. et A . 0 = 0La classe des chasseurs parmi rien est rien.
Démonstration

Selon l'axiome de la complémentation, A + A = 1

En ajoutant le terme A de part et d'autre de l'égalité, on a donc A + (A + A) = 1 + A

Ce qui peut également s'écrire, selon l'axiome de l'associativité: (A + A) + A = 1 + A

Or, A + A = A nous dit le théorème de l'idempotence, on a donc A + A = 1 + A

Et puisque l'axiome de la complémentation nous dit que A + A = 1, on retrouve bien 1 + A = 1.

• Théorèmes de l'involution: A = ALa classe des non non-chasseurs est la classe des chasseurs.
• Théorèmes d'absorption: A + A . B = ALa classe des chasseurs et des chasseurs myopes est la classe des chasseurs. et A .(A + B) = ALa classe des chasseurs parmi les chasseurs et les myopes est la classe des chasseurs.
Démonstration

D'après l'axiome de l'élément neutre: A = A . 1
En faisant apparaître le terme A . B de part et d'autre de l'égalité, on trouve A + A . B = A . 1 + A . B
Ce que l'axiome de la distributivité nous permet d'écrire A + A . B = A . (1 + B)
Or, 1 est élément absorbant pour la somme logique, d'où 1 + B = 1, et élément neutre pour le produit logique, d'où A . 1 = A
On retrouve donc bien A + A . B = A

• Théorème de la redondance: A . B + A . C = A . B + A . C + B . CBon ! On va vous demander de nous croire sur ce coup là...
Démonstration

Sachant que X + X . Y = X (théorème d'absorption), en posant X = A . B et Y = C, on trouve A . B + A . B . C = A . B

et en posant X = A . C et Y = B, on trouve A . C + A . C . B = A . C

D'où, en ajoutant les deux égalités: A . B + A . C = (A . B + A . B . C) + (A . C + A . C . B)

Soit, conformément à l'axiome de la distributivité: A . B + A . C = A . B + A . C + (A + A) . B . C

Or, selon l'axiome de la complémentation: A + A = 1

1 étant élément neutre pour le produit logique, on retrouve bien A . B + A . C = A . B + A . C + B . C

Ajoutons à cette liste deux théorèmes importants, dits théorèmes de Morgan, fruits des travaux du mathématicien anglais Augustus de MorganCi-contre, l'auteur du désopilant Formal Logic (1847). [1806-1871], qui annoncent que:

• le complément d'une somme logique est égal au produit logique des compléments: A + B = A . BLa classe de tous ceux qui ne sont ni chasseurs ni myopes est la classe des non-chasseurs parmi les non-myopes.
• le complément d'un produit logique est égal à la somme logique des compléments: A . B = A + BLa classe de tous ceux qui ne sont pas chasseurs myopes est la classe des non-chasseurs auxquels s'ajoutent les non-myopes.

Attention ! Purs littéraires s'abstenir...

Démonstration

Si A . B est bien le complément de A + B, nous devrions retrouver nos axiomes de la complémentation: A + A = 1 et A . A = 0.

Commençons par démontrer que A + B + A . B = 1

Utilisons pour cela le théorème de redondance X . Y + X . Z = X . Y + X . Z + Y . Z

En posant X = A, Y = B et Z = 1, on retrouve A . B + A . 1 = A . B + A . 1 + B . 1

soit, puisque 1 est élément neutre pour le produit logique: A . B + A = A . B + A + B

Et en ajoutant le terme B à de part et d'autre de l'égalité: A . B + A + B = A . B + A + B + B

Sachant que B + B = 1, il vient: A . B + A + B = A . B + A + 1

Or, 1 étant élément absorbant pour la somme logique A on a: A . B + A + 1 = 1

et, donc, bien: A . B + A + B = 1

Et d'une !

Démontrons maintenant que A + B . (A . B) = 0

L'axiome de la distributivité nous permet d'écrire: (A + B) . A . B = A . B . A + A . B . B

Et celui de la commutativité: (A + B) . A . B = (A . A) . B + A . (B . B)

Or, on sait grâce à l'axiome de la complémentation que A . A = B . B = 0, on a donc (A + B) . A . B = 0 . B + 0 . A

Et, grâce au théorème des éléments absorbants, que 0 . A = 0

D'où (A + B) . A . B = 0 (et de deux !)

Pffff... Décidément, je ne suis vraiment pas fait pour ce genre de trucs...

Ces théorèmes de Morgan illustrent une particularité fascinante de l'algèbre booléenne: le principe de dualité (duality). Selon ce principe, pour toute égalité E vérifiée dans l'algèbre de Boole, il existe une égalité E*, appelée duale, qui se trouve également vérifiée. Celle-ci, qui plus est, se retrouve quasi immédiatement à partir de E puisqu'il suffit en effet:

• de permuter les opérateurs (+) et (.)
• de permuter les constantes 0 et 1

L'algèbre de Boole à facettes

Avouons-le bien volontiers: George Boole ne nous a pas légué "clef en main" cette théorie toute en formules simples et définitives. D'autres esprits illustres ont repris, approfondi et mis en ordre ces idées novatrices dont il eût néanmoins l'intuition géniale de jeter les premiers fondements. Citons, entre autres, l'anglais Augustus De Morgan [1806-1871], et les américains Charles Peirce [1839-1914] et Edward Huntington [1874-1952].

Aujourd'hui, en termes très mathématiques...et donc totalement abscons pour l'auteur de cette page..., on appelle algèbre de Boole (E, +, .,  , 0, 1) la donnée d'un ensemble E non vide, muni de deux lois de composition interne (+ et .) commutatives et associatives, d'une application unaire (  ) et de deux éléments privilégiés (0 et 1), toutes ces données vérifiant les différents axiomes vus plus haut.
Soupir...

Pour 99% de la population, cette très jolie phrase provoquera nausées, maux de tête voire un petit raffermissement du quadriceps. Les initiés y verront au contraire le formidable canevas à une foule d'applications plus ou moins évidentes: théorie des ensemblesEt voilà pourquoi nos ridicules petits dessins faisaient si bien merveille: la théorie des ensembles n'est en fait qu'une des applications de l'algèbre de Boole., logique des prédicats, calcul des aléas technologiques et, ce qui nous intéressera ici plus particulièrement, technologie des composants électroniques.

Partis très loin dans des sphères très abstraites, tentons de revenir à très petits pas vers notre pécé préféré...

L'algèbre du tout ou rien

De manière rassurante, entrevoir l'immense intérêt de l'algèbre de Boole pour nos petites machines réclamera un petit effort préalable de... simplification. Et imaginer pour cela un univers booléen minimaliste, c'est-à-dire réduit à ses deux seuls éléments remarquables: "0" et "1".

Et là, miracle ! Ce cas très particulier et plutôt minimaliste de l'algèbre de Boole ouvre grand les portes sur d'inattendus horizons: à savoir, tous les domaines où règne la loi du tout ou rien, tous ces univers où toute variable ne peut prendre que deux états différents et complémentaires. Bref, les univers chamarrés de l'algèbre binaire (binary algebra).

Si, pour vous aussi, la théorie est un tunnel, il semble bien que nous en voyons le bout...

Boole, au coeur de nos vies

Vrai / Faux

Dans cette algèbre booléenne que nous venons de décrire, avoir dénommé "0" et "1" nos deux éléments remarquables était pure convention d'écriture. D'ailleurs, appliqués à la théorie des ensemble, nous avons vu que ces derniers avaient pris des noms autrement plus explicites: ensemble vide (pour "0") et référentiel complet (pour "1").

Ramenés à un univers booléen minimaliste où ces deux valeurs, seules possibles, sont également complémentaires, pourquoi ne pas envisager de les rebaptiser "vrai" et "faux" ? Le "non-vrai" étant forcément "faux", et le "non-faux" obligatoirement "vrai", avouez que ces deux adjectifs colleraient plutôt bien à la "philosophie" booléenne.

Par ailleurs, l'algèbre binaire mettant en jeu des variable ne pouvant prendre que l'une ou l'autre de ces deux valeurs, il devient réalisable, pour chacun de nos trois opérateurs fondamentaux, de consigner en trois petits tableaux l'ensemble de tous les résultats possibles mettant en jeu deux variables...chose inconcevable en arithmétique "classique", toute variable pouvant prendre une infinité de valeurs...:
 

Dans ce nouveau contexte très manichéen, les résultats produits par chacun de nos opérateurs de base peuvent se résumer à trois phrases désarmantes de bon sens:

• Pour la somme logique: si A + B est "vrai", alors A est "vrai" OUET/OU serait en fait plus juste, puisque A + B sera également "vrai" dans le cas où A et B sont "vrai". Nous verrons plus tard qu'il s'agit ici d'un "ou inclusif"... B est "vrai",
• Pour le produit logique: si A . B est "vrai", alors A est "vrai" ET B est "vrai",
• Pour la complémentation: le NON "faux" est "vrai" et le NON "vrai" est "faux".

Avouez que nous avons trouvé là des noms beaucoup plus familiers pour nos trois opérateurs booléens fondamentaux. Nous les utiliserons donc dorénavant pour désigner ces derniers, mais plutôt dans leur version anglaiseOui... Autant vous le dire tout de suite: le Français n'a pas vraiment percé dans le domaine de l'informatique moderne...:

• Pour la somme logique: OR,
• Pour le produit logique: AND,
• Pour la complémentation: NOT.

Et maintenant, si je vous dis: "je sortirai s'il fait beau ou s'il pleut et que j'ai mon parapluie", et que j'appelle (A) la proposition "il fait beau" et (B) la proposition "j'ai mon parapluie", alors je peux très simplement exprimer mes chances de sortie par la délicieuse expression: A + A.B, digne des plus belles pages de la littérature française.
Tout cela pour vous montrer à quel point, nous, créatures pourtant si subtiles, ne cessons de jongler, sans nous en rendre compte...un truc à achever Monsieur Jourdain !, avec des concepts parfaitement booléens.

Sans surprise, nous appellerons variable booléenne (boolean variables), ou encore variable logique (logical variables), toute variable obéissant à cette algèbre binaire pour laquelle seules deux valeurs différentes et complémentaires sont possibles.
Celles-ci, comme nous l'avons vu, seront généralement notées "1" et "0", mais parfois aussi "vrai" (true) et "faux" (false).

On / Off

Bon, bon, bon... Nous en voyons que le précédent chapitre n'a pas du tout convaincus du très haut intérêt de l'algèbre de Boole. Pour ceux-là, nous allons donc sortir la très grosse artillerie, à savoir: une simple pile, quelques fils conducteurs et une ampoule en état de marche.
Tout va bientôt s'éclairer...

En un point donné de tout circuit électrique, deux situations très simples peuvent se produire: soit le courant "passe", soit il ne "passe pas": une simple ampouleEn fait, un simple doigt peut même suffire, mais une seule fois... nous l'apprendra brillamment.
Afin de symboliser ces deux états très différents, nous pourrions utiliser les termes très suggestifs de "lumière/obscurité", "on/off" ou, pourquoi pas, "1/0"Tiens, tiens.......

Etudions maintenant quelques montages électriques de niveau cours élémentaire:
 

Pense-bête: contacter Varta, Duracel et toute l'industrie de la pile pour leur proposer un espace d'affichage sur le générateur de cette spectaculaire animation.

Et là, divine suprise, nous remarquons ébahis que:

• Pour le montage en parallèle: l'ampoule brille si l'interrupteur A OU l'interrupteur B est en position fermée. Ce que pourrions exprimer par: Lumière = A + B,
• Pour le montage en série: l'ampoule brille si l'interrupteur A ET l'interrupteur B sont en position fermée, soit: Lumière = A . B.

Juste le temps de nous remettre de la vive émotion causée par cette révélation et profitons encore un instant du matériel grâcieusement prêté par le club des électriciens amateurs pour constater que nos axiomes booléens se vérifient parfaitement dans ce petit monde conducteur:

Vous voila rassuré(e): tout ce que nous avons appris sur l'algèbre booléenne n'est donc pas complètement vain puisqu'elle semble, en effet, trouver certaines applications très lumineuses et très concrètes.
Bon, il est vrai que le rapport est encore ténu entre ces montages pour grands débutants en génie électrique et le concentré de technologie que constitue une puce savante.
Le chemin est encore long, mais il est désormais un poil éclairé !

Heu, à ce propos... Nous allons entrer dans un nouveau tunnel de théorie... Mais promis, la lumière sera encore plus vive de l'autre côté.

Fonctions booléennes

Prenez un mathématicien normalement constitué, donnez lui pour s'amuser quelques variables usagées et attendez. Tôt ou tard, la créature toute excitée viendra vous embrumer l'esprit avec des fonctions !

Et oui. Tout comme en algèbre "classique", il est tout à fait envisageable de combiner entre elles plusieurs variables booléennes à l'aide de nos opérateurs fondamentaux (OR, AND, NOT) pour former des fonctions.
Sans surprise, une telle fonction sera baptisée fonction booléenne (boolean function), ou encore, fonction logique (logical function).

Fonctions logiques à deux variables:
OR, NOR, XOR et consorts...

A ce stade, nous avons déjà repéré deux opérateurs binaires fondamentaux: le "OR" et le "AND", de par le fait qu'ils correspondaient à des raisonnements logiques très familiers à notre esprit humain et, cadeau bonus, qu'ils décrivaient parfaitement les montages parallèle et série d'un circuit électrique.
Mais ce ne sont pas les seuls !

Pour nous en persuader, nous allons construire un petit tableau original - comme seule l'algèbre binaire peut nous permettre d'en concevoir - afin de lister toutes les fonctions possibles pouvant mettre en jeu deux variables booléennes.

Evidemment, ça va être pénible... mais on y a mis un peu de couleur...
 

Parfait ! Nous n'allons pas revenir sur la beauté parfaite de notre "OR" et de notre "AND", mais attardons-nous quelques instants sur certains de ces autres opérateurs aux noms étranges...

XOR (eXclusive OR)

Le XOR, alias "ou exclusif", qui correspond à la fonction booléenne F(A, B) = A.B + A.B est un peu un "ou" version "fromage ou dessert", dans le sens où A XOR B sera "vrai" si A est "vrai" ou B est "vrai", mais pas les deux ! Cela lui vaut ses noms, sans doute plus parlants, d'opérateur d'anticoïncidence, voire, également, de comparateur de différence.
Son symbole est ⊕ et ses caractéristiques principales sont:

• Commutativité: A ⊕ B = B ⊕ A,
• Associativité: (A ⊕ B) ⊕ C = A ⊕ (B ⊕ C),
• Comportement vis-à-vis des éléments neutres: A ⊕ 0 = A et A ⊕ 1 = A,
• A ⊕ A = 0 (pas d'idempotence) et A ⊕ A = 1.

NOR (Not OR)

Comme son nom l'indique assez bien, l'opérateur NOR, noté ↓, est le complément de l'opérateur OR, c'est-à-dire A + B.
Même si cet opérateur n'a pas d'équivalent simple dans le langage parlé, son intérêt en électronique est un tout petit peu essentiel...comme nous le verrons plus tard, si vous survivez à cette page... et nous allons donc expliciter quelques unes de ses propriétés:

• Commutativité: A ↓ B = B ↓ A,
• Pas d'associativité: (A ↓ B) ↓ C ≠ A ↓ (B ↓ C),
• Inversion: A ↓ 0 = A.

XNOR (eXclusive Not OR)

Booléennement parlant, XNOR est le complément de l'opérateur XOR que nous venons de voir. Vous ne serez donc pas étonné(e) d'apprendre que son petit nom soit opérateur de coïncidence, ou encore, comparateur d'identité puisque A XNOR B ne sera "vrai" que si A et B ont même valeur.
Ses principales propriétés sont:

• Commutativité: A XNOR B = B XNOR A,
• Associativité: (A XNOR B) XNOR C = A XNOR (B XNOR C),
• Comportement vis-à-vis des éléments neutres: A XNOR 0 = A et A XNOR 1 = A,
• A XNOR A = 1 (pas d'idempotence) et A XNOR A = 0.

NAND (Not AND)

L'opérateur NAND ("ET-NON"), noté ↑, est simple à assimiler puisqu'il agit comme le complément de l'opérateur AND. En clair, A ↑ B ne donnera "faux" que si A et B sont simultanément "vrai".
A l'image du NOR, le NAND n'a pas d'équivalent direct dans le langage parlé, mais son importance est tout aussi fondamentale en électronique et voici pourquoi nous allons nous intéresser à ses passionnantes propriétés:

• Commutativité: A ↑ B = B ↑ A,
• Pas d'associativité: (A ↑ B) ↑ C ≠ A ↑ (B ↑ C),
• Inversion: A ↑ 1 = A.

Fonctions booléennes à N variables

Nous venons d'étudier le cas très particulier et très simple des fonctions booléennes à deux variables. Bien évidemment, vous vous doutez qu'une fonction logique peut mettre en jeu un nombre quelconque de variables booléennes.
Ainsi, la fonction F(A, B, C) = A.B + A.C est un exemple pris tout à fait au hasard de fonction logique à trois variables.

Cartes sur table

Comme nous l'avons déjà mis en pratique, la grande particularité des fonctions booléennes est qu'elles peuvent être explorées de manière exhaustiveUn mathématicien dira plutôt "par induction", c'est-à-dire en considérant l'ensemble des cas possibles.. En effet, chaque variable de ces fonctions ne pouvant prendre que deux valeurs différentes, il devient tout à fait faisable...du moins tant que le nombre de variables mises en jeu par la fonction reste raisonnable... de récapituler tous les cas possibles dans un tableau que l'on appelle alors table de vérité (truth table).

Ainsi, si nous reprenons notre fonction booléenne définie par F(A, B, C) = A.B + A.C, nous pouvons sans trop de problème mettre au point sa table de vérité:
 

Canon Boole

Supposons un instant que nous ayons sous les yeux une table de vérité toute faite, sans aucune définition algébrique de la fonction associée:
 

Et bien cette table de vérité peut nous permettre de retrouver une définition polynômiale de la fonction F.
En effet, nous savons qu'en algèbre binaire, si nous avons une expression:
X + Y + Z + .... = 1, alors on peut dire que
X = 1 OU Y = 1 OU Z = 1...

Il est par conséquent tout à fait envisageable de définir notre fonction F comme la somme logique des différentes lignes pour lesquelles F = 1.

Conséquence toute naturelle de tout cela: deux fonctions logiques F et F' seront égales si et seulement si leur table de vérité sont identiques.

Ainsi, dans notre exemple, on peut écrire: F(A, B, C) = A.B.C...qui correspond à la deuxième ligne de notre table de vérité: A=0, B=0 et C=1. + A.B.C...qui correspond à la troisième ligne de notre table de vérité: A=0, B=1 et C=0. + A.B.C...qui correspond à la cinquième ligne de notre table de vérité: A=1, B=0 et C=0. + A.B.C...qui correspond à la sixième ligne de notre table de vérité: A=1, B=0 et C=1. + A.B.C...qui correspond à la septième ligne de notre table de vérité: A=1, B=1 et C=0.

En groscursussien, les différents monômes de la fonction (c'est-à-dire les produits logiques A.B.C, A.B.C, A.B.C, A.B.C et A.B.C) sont appelés des mintermes (minterms), et la fonction F, qui se trouve alors exprimée sous la forme d'une somme logique de mintermes est dite se trouver sous sa forme canonique disjonctive (disjunctive canonical form), ou également première forme canonique.

Par ailleurs, dans notre univers booléen, nous pouvons également définir le complément de F comme la somme des mintermes égaux à 0. Nous avons donc aussi:

     F(A, B, C) = A.B.C + A.B.C + A.B.C

Et puisque nous savons parfaitement que A = A et aussi que, grâce à ce qu'a fait MorganAh c'est Merlin ça..., A+B = A.B, nous pouvons donc également écrire F sous la forme:

Les termes A+B+C, A+B+C et A+B+C, sommes logiques de toutes les variables de F (ou de leur complément) sont appelés maxtermes (maxterms) de la fonction, et cette écriture de F sous la forme de produits de maxtermes est appelée forme canonique conjonctive (conjunctive canonical form), ou aussi parfois deuxième forme canonique.

Que vous ayez ou non compris cette histoire de canon, vous aurez de toute façon noté qu'une fonction logique peut être exprimée algébriquement de différentes façons.
Et ceci n'est pas une bonne nouvelle pour nos neurones...

L'art de faire simple

La plupart du temps, une fonction logique nous sera proposée sous une forme développée plus ou moins alambiquée qu'il sera très souvent possible de fortement simplifier.
Pour ce faire, trois pistes à explorer:

Méthode algébrique

Nous l'avons vu ensemble, l'algèbre booléenne dispose d'un véritable arsenal d'axiomes et théorèmes bien définitifs qui peuvent nous permettre de simplifier une fonction logique.
Bien souvent, la solution passe par de judicieux développements afin de faire apparaître des termes qui, par factorisations non moins habiles, vont s'annuler sur le principe que A + 1 = A ou A . 0 = 0.

Attention toutefois: la simplification algébrique demande un minimum de rigueur et de zénitude. Si vous êtes du genre à facilement oublier un A en route ou prêt(e) à tout abandonner quand retentit le jingle annonçant l'arrivée d'un pote sur MSN, envisagez peut-être directement le plan B...

Formes canoniques

L'annonce ne vous surprendra pas deux fois: la table de vérité d'une fonction logique à N variables comportera 2^N lignes.
Dès lors, trois scénarii possibles:

• Ou la table de vérité révèle un petit nombre de cas pour lesquels la fonction est égale à 1. Dans ce cas, il sera sensé d'exprimer la fonction dans sa forme canonique disjonctive;
• Ou la table de vérité révèle un petit nombre de cas pour lesquels la fonction est égale à 0, et il sera alors pertinent d'exprimer la fonction dans sa forme canonique conjonctive, en complémentant la somme des mintermes égaux à 0;
• Ou la table de vérité ne révèle aucune prépondérance nette de résultats égaux à 0 ou 1, et on devra se résoudre à faire appel à Maurice...

Diagramme de Karnaugh

Le diagramme de Karnaugh (Karnaugh map) est une méthode simple et ingénieuse afin de trouver à coup sûr la forme la plus simple d'une fonction logique donnée, à partir de sa table de vérité.

A vrai dire, le diagramme de KarnaughMaurice Karnaugh (né en 1952), est un mathématicien américain plutôt pas mauvais non plus en physique. Le genre de gars à donner son nom à des tableaux remplis de 1 et de 0...
Un génie, quoi. d'une fonction n'est ni plus ni moins que la table de vérité de celle-ci, mais mise en forme de telle manière que soient géographiquement proches les mintermes logiquement proches.

Comme le fait d'expliquer textuellement le principe de ce diagramme conduirait à une somme faramineuse de lignes totalement imbitables, nous allons plutôt illustrer nos dires par un exemple bien senti.

Soit l'anodine fonction logique F telle que F(A, B, C, D) = A + A.B + A.B.C + A.B.C.D.
Amusons-nous à développer sa table de vérité.
 

Voilà ! On s'est bien poilé et nous avons, conformément à nos attentes, obtenu une table de vérité à 16 lignes.

Nous allons maintenant transformer ce tableau à seize lignes en un tableau à seize cases. Pour ce faire, nous allons répartir tous les mintermes de nos variables groupées deux à deux, mais en prenant soin de scrupuleusement respecter cette règle: il faut impérativement que le passage d'une case à une case adjacente ne traduise le changement d'état que d'une seule variable.

Normalement, nous devrions obtenir quelque chose qui ressemble à ça:
 

 
A chaque case de notre nouveau tableau correspond un minterme de la table de vérité; il est donc normal de retrouver dans notre table de Karnaugh tous les résultats possibles pour la fonction F, et donc, le même nombre de "1" et de "0".

Nous allons dès lors pouvoir procéder aux simplifications.
Pour ce faire, nous allons localiser les cases adjacentes marquées à "1" en nombre égal à une puissance de deux, c'est-à-dire les groupes de 1, 2, 4, 8, 16.... cases "1" adjacentes, en recherchant bien sûr les regroupements les plus importants. On ne garde ensuite, parmi les mintermes concernés par le regroupement, que la ou les variable(s) logique(s) commune(s) à toutes les cases.
 

Premier regroupement: parmi les huit cases formées par les deux premières lignes, seule la variable B est commune aux mintermes.
Notez qu'on ne peut inclure la troisième ligne dans notre premier regroupement, car nous aurions alors douze cases, douze n'étant pas une puissance de deux.

Deuxième regroupement: parmi les huit cases formées par les deuxième et troisième lignes, seule la variable A est commune aux mintermes.
Comme vous le constatez pour notre deuxième ligne, une ou plusieurs case(s) peut(vent) tout à fait servir à plusieurs regroupementsA vrai dire, rien de surprenant à celà, puisque nous savons depuis notre découverte de l'idempotence qu'un même terme peut apparaître plusieurs fois dans une expression logique sans en modifier le sens..

Troisième regroupement: parmi les huit cases formées par la première et la dernière colonne, seule la variable C est commune aux mintermes.
Remarquez que les lignes / colonnes situées aux extrémités doivent être considérées comme adjacentes. Et cela est après tout fort logique, puisqu'une seule variable change d'état de l'une à l'autreEntre la première et la dernière lignes, seule la variable B change d'état - entre la première et la dernière colonne, seule la variable D change d'état..

Parfait ! Aucun autre regroupement n'étant possible, on recopie les mintermes n'ayant servi à aucun regroupement - ici, aucun - et on récupère les fruits de nos regroupements successifs, pour finalement obtenir:

F = B + A + C
...ce qui constitue quand même, vous êtes maintenant connaisseur(se), une fort belle simplification !

Bien évidemment, nous aurions pu parvenir au même résultat avec beaucoup moins d'efforts et un zeste de réflexion, en remarquant que la table de vérité ne recensait que deux cas où la fonction s'annulait, cas correspondant au monôme A.B.C.
Dès lors, on pouvait se remémorer le théorème de l'involution puis avoir une pensée pour Morgan pour noter que:

Evidemment, vous vous doutez que la méthode de Karnaugh devient franchement hostile dès lors que le nombre de variables logiques excède quatre, puisqu'il faut dès lors faire appel à une table en 3D...un cube quoi..., du moins si l'on veut continuer d'obéir à l'obligation de ne changer qu'une seule variable d'état lors du passage d'une case à une autre.
Inutile également de préciser qu'au delà de six variables logiques, la méthode de Karnaugh devient inapplicable sans très très haute faculté d'abstraction. Il faut alors se replier vers d'autres méthodes de simplification, telle la méthode de Quine-Mac Cluskey, que nous n'aborderons pas ici car nous ne voudrions pas abuser de votre gentille attention.

Enfin bref...

Oui, bon, d'accord, mais alors ?

On nous promettait du concret, du terre-à-terre, du pragmatisme à électrons, et nous voilà étourdis et repus, la tête toute boursouflée de pleines caisses de uns et de zéros mais tout amers de ne pas avoir vu l'ombre d'une puce, ni même d'une souris à roulette.

Friserait-on l'arnaque ? L'abus de confiance ? Le e-dol ?
Non mes ami(e)s ! Ce fut long, ce fut difficile, ce fut terriblement chiant, mais vous êtes prêt(e)s, maintenant, à entrer dans la Matrice.

Bienvenue à toi, Némo.
Et n'oublie pas les patins.