L'algèbre booléenne

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:


Bêtes deux sommes
Attention ! Bien que leur nom et leur symbole nous y poussent, ne confondons pas la somme et le produit logiques avec la somme et le produit arithmétiques, tels que nous les connaissons. Les premiers s'exercent sur des classes, les seconds sur des nombres.

• 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.
  

Représentation graphique des opérateurs booléens de base (diagramme dit d'Euler-Venn).


Survolez les différentes classes ou expressions afin de visualiser leur équivalent graphique.
Comme
nous manipulons ici des ensembles plutôt que des classes, nous
prendrons la précaution préalable de définir E comme l'ensemble
référentiel, celui contenant tous les autres.




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 Morgan[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]Ci-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
  

La confiance règne...

Vérification

• Axiome des élément neutres: A + 0 = A (E) et A . 1 = A (E*)
  
• Axiome de la complémentation: A + A = 1 (E) et A . A = 0 (E*)
  
• Théorème de l'idempotence: A + A = A (E) et A . A = A (E*)
  
• Théorème des éléments absorbants: A + 1 = 1 (E) et A . 0 = 0 (E*)
  
• Théorème d'absorption: A + A . B = A (E) et A .(A + B) = A (E*)
  

Incroyable, ça marche !






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...:

<table width="95%"> <tr> <td colspan="3">Somme logique</td> </tr> <tr> <td width="30%">A</td> <td width="30%">B</td> <td width="40%">A+B</td> </tr> <tr> <td class="false">faux</td> <td class="false">faux</td> <td class="false">faux</td> </tr> <tr> <td class="false">faux</td> <td class="true">vrai</td> <td class="true">vrai</td> </tr> <tr> <td class="true">vrai</td> <td class="false">faux</td> <td class="true">vrai</td> </tr> <tr> <td class="true">vrai</td> <td class="true">vrai</td> <td class="true">vrai</td> </tr> </table>

<table width="95%"> <tr> <td colspan="3">Produit logique</td> </tr> <tr> <td width="30%">A</td> <td width="30%">B</td> <td width="40%">A.B</td> </tr> <tr> <td class="false">faux</td> <td class="false">faux</td> <td class="false">faux</td> </tr> <tr> <td class="false">faux</td> <td class="true">vrai</td> <td class="false">faux</td> </tr> <tr> <td class="true">vrai</td> <td class="false">faux</td> <td class="false">faux</td> </tr> <tr> <td class="true">vrai</td> <td class="true">vrai</td> <td class="true">vrai</td> </tr> </table>

<table width="95%"> <tr> <td colspan="2">Complémentation</td> </tr> <tr> <td width="50%">A</td> <td width="50%">A</td> </tr> <tr> <td class="false">faux</td> <td class="true">vrai</td> </tr> <tr> <td class="true">vrai</td> <td class="false">faux</td> </tr> </table>

Les trois opérateurs booléens appliqués aux éléments "vrai" et "faux".


Pas vraiment normande, notre nouvelle algèbre booléenne...



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...:


Quand et est ou
Méfions-nous quand même des subtilités de la langue; ainsi, par exemple, lorsque nous évoquons "les Hommes et
les Femmes", nous ne faisons généralement pas référence aux
hermaphrodites, mais bel et bien à toute personne, qu'elle soit homme ou femme. Bref, derrière nos "et" se cachent parfois de parfaits "ou".

• 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).


Boole, détecteur de mensonge

L'algèbre de la Vérité.


S'il
y a effectivement un domaine où la dualité des variable est évidente,
c'est celui de la logique. En logique, comme le disait si bien
Aristote, toute proposition est soit vraie, soit fausse, et ce qui
n'est pas vrai est alors nécessairement faux. Vous ne serez donc pas
surpris(e) d'apprendre que la logique est un parfait domaine
d'application de l'algèbre de Boole. Tout juste celle-ci change-t-elle
de nom pour s'appeler, de manière peut-être plus évocatrice, logique propositionnelle.
En logique propositionnelle, toute proposition "bien forméeEt il existe des règles strictes pour attester de cette "bonne formation"."
est soit vraie, soit fausse: c'est le principe du tiers exclu. Ainsi,
"Il pleut" est une proposition parfaitement bien formée, et ce, même
s'il fait grand soleil.
Plusieurs propositions peuvent être assemblées entre elles à l'aide de connecteurs,
c'est-à-dire, en langage normal, de petits mots très pratiques comme
"et", "ou", "alors"... pour former des propositions plus complexes.
Les connecteurs qui nous intéressent, à ce stade, sont:

• La conjonction, notée ∧, qui correspond à notre produit logique: "Il pleut et j'aime les frites"Oui, l'auteur de cette page confesse une légère origine nordiste... Très à la mode depuis peu....
  
• La disjonction, notée ∨, qui correspond à notre somme logique: "Il pleut ou j'aime les frites".
  
• La négation, notée ¬, qui correspond à notre complémentation: "Il ne pleut pas", "je n'aime pas les frites".
  

...Il en existe d'autres, telles l'implication (notée ⇒) ou l'équivalence logique (notée ⇔), et d'autres encore, moins facilement traduisibles en langage courant, que nous reverrons peut-être un peu plus tard.
Cette
formalisation de la logique permet de manipuler des propositions
complexes comme s'il s'agissait de données algébriques, et, ainsi,
évaluer leurs possibles valeurs, éventuellement démontrer qu'elles
seront toujours vraies (ce sont les tautologies) ou toujours fausses
(les antilogies).
Bref, un formalisme dément qui vous permet d'assurer mordicus que ((p⇒(q∧r∧s))∧¬s)⇒¬p...le genre de mystère que Boole dégomme... sera toujours vrai !
Des trucs à vous persuader que vous ne mangez des frites que quand il pleut...






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:






Application des opérateurs booléens OR et AND aux montages électriques de base.


Cliquez sur les différents interrupteurs du montage afin de voir la conséquence sur l'ampoule.



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:





Vérification de la validité des axiomes booléens dans le domaine des montages électriques de base.


Cliquez sur les différents interrupteurs du montage afin de vérifier la lumineuse pertinence des axiomes booléens.


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...




Binaire²
L'épithète
"binaire" doit être ici compris comme qualifiant une opération mettant
en jeu deux variables, tout comme notre opérateur NOT est un opérateur
unaire.
Tous ces opérateurs sont néanmoins des opérateurs de l'algèbre binaire
(dans le sens où toute variable ne peut prendre que deux valeurs), ce
qui n'arrange rien à la lisibilité de cette note...


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...

Fonctions booléennes à deux variables
<table width="35%" align="left"> <tr><td width="30%">A</td><td width="30%">B</td> <td width="40%">F(A,B)</td> </tr> <tr><td class="false">0</td><td class="false">0</td><td class="false">0</td></tr> <tr><td class="false">0</td><td class="true">1</td><td class="false">0</td></tr> <tr><td class="true">1</td><td class="false">0</td> <td class="false">0</td></tr> <tr><td class="true">1</td><td class="true">1</td><td class="false">0</td></tr> </table> Quelles que soient les valeurs de A et B, cette fonction renvoie toujours la valeur 0. Il s'agit donc de la fonction constante: F(A, B) = 0 Intérêt discutable...		<table width="35%" align="left"> <tr><td width="30%">A</td><td width="30%">B</td> <td width="40%">F(A,B)</td> </tr> <tr><td class="false">0</td><td class="false">0</td><td class="false">0</td></tr> <tr><td class="false">0</td><td class="true">1</td><td class="false">0</td></tr> <tr><td class="true">1</td><td class="false">0</td> <td class="false">0</td></tr> <tr><td class="true">1</td><td class="true">1</td><td class="true">1</td></tr> </table> Cette fonction, qui ne renvoie 1 que si A et B sont égaux à 1, nous la connaissons fort bien: il s'agit de notre produit logique, alias AND: F(A, B) = A . B = A AND B
<table width="35%" align="left"> <tr><td width="30%">A</td><td width="30%">B</td> <td width="40%">F(A,B)</td> </tr> <tr><td class="false">0</td><td class="false">0</td><td class="false">0</td></tr> <tr><td class="false">0</td><td class="true">1</td><td class="false">0</td></tr> <tr><td class="true">1</td><td class="false">0</td><td class="true">1</td></tr> <tr><td class="true">1</td><td class="true">1</td><td class="false">0</td></tr> </table> Fonction sans grande correspondance dans le langage parlé, mais que les spécialistes appellent inhibition: F(A, B) = A . B		<table width="35%" align="left"> <tr><td width="30%">A</td><td width="30%">B</td> <td width="40%">F(A,B)</td> </tr> <tr><td class="false">0</td><td class="false">0</td><td class="false">0</td></tr> <tr><td class="false">0</td><td class="true">1</td><td class="false">0</td></tr> <tr><td class="true">1</td><td class="false">0</td><td class="true">1</td></tr> <tr><td class="true">1</td><td class="true">1</td><td class="true">1</td></tr> </table> Fonction pour laquelle la variable B ne sert pas à grand chose... Bref, la fonction unaire: F(A, B) = A
<table width="35%" align="left"> <tr><td width="30%">A</td><td width="30%">B</td> <td width="40%">F(A,B)</td> </tr> <tr><td class="false">0</td><td class="false">0</td><td class="false">0</td></tr> <tr><td class="false">0</td><td class="true">1</td><td class="true">1</td></tr> <tr><td class="true">1</td><td class="false">0</td> <td class="false">0</td></tr> <tr><td class="true">1</td><td class="true">1</td><td class="false">0</td></tr> </table> Fonction inhibition comparable à la fonction ci-dessus F(A, B) = A . B		<table width="35%" align="left"> <tr><td width="30%">A</td><td width="30%">B</td> <td width="40%">F(A,B)</td> </tr> <tr><td class="false">0</td><td class="false">0</td><td class="false">0</td></tr> <tr><td class="false">0</td><td class="true">1</td><td class="true">1</td></tr> <tr><td class="true">1</td><td class="false">0</td> <td class="false">0</td></tr> <tr><td class="true">1</td><td class="true">1</td><td class="true">1</td></tr> </table> Fonction qui ressemble fort à la fonction ci-dessus, A endossant cette fois le rôle de la variable croupion. F(A, B) = B
<table width="35%" align="left"> <tr><td width="30%">A</td><td width="30%">B</td> <td width="40%">F(A,B)</td> </tr> <tr><td class="false">0</td><td class="false">0</td><td class="false">0</td></tr> <tr><td class="false">0</td><td class="true">1</td><td class="true">1</td></tr> <tr><td class="true">1</td><td class="false">0</td><td class="true">1</td></tr> <tr><td class="true">1</td><td class="true">1</td><td class="false">0</td></tr> </table> Fonction très intéressante, qui ne donne 1 que si les variables A et B sont de valeur différente. Nous l'appellerons fonction d'anticoïncidence, ou XORRien à voir avec le gars dansant la tektonik déguisé en Albal dans les années 80.: F(A, B) = A . B + A . B = A XOR B		<table width="35%" align="left"> <tr><td width="30%">A</td><td width="30%">B</td> <td width="40%">F(A,B)</td> </tr> <tr><td class="false">0</td><td class="false">0</td><td class="false">0</td></tr> <tr><td class="false">0</td><td class="true">1</td><td class="true">1</td></tr> <tr><td class="true">1</td><td class="false">0</td><td class="true">1</td></tr> <tr><td class="true">1</td><td class="true">1</td><td class="true">1</td></tr> </table> Cette fonction là aussi, nous la connaissons déjà fort bien; c'est notre fonction OR, alias somme logique: F(A, B) = A + B = A OR B
<table width="35%" align="left"> <tr><td width="30%">A</td><td width="30%">B</td> <td width="40%">F(A,B)</td> </tr> <tr><td class="false">0</td><td class="false">0</td><td class="true">1</td></tr> <tr><td class="false">0</td><td class="true">1</td><td class="false">0</td></tr> <tr><td class="true">1</td><td class="false">0</td> <td class="false">0</td></tr> <tr><td class="true">1</td><td class="true">1</td><td class="false">0</td></tr> </table> Autre fonction intéressante, complémentaire de notre fonction OR... puisque quelles que soient les valeurs de A et B, on a: A NOR B = A OR B et que nous appellerons donc pour la peine fonction NOR (Not-OR): F(A, B) = A + B = A . BAuriez-vous déjà oublié notre cher Morgan et ses théorèmes ? = A NOR B		<table width="35%" align="left"> <tr><td width="30%">A</td><td width="30%">B</td> <td width="40%">F(A,B)</td> </tr> <tr><td class="false">0</td><td class="false">0</td><td class="true">1</td></tr> <tr><td class="false">0</td><td class="true">1</td><td class="false">0</td></tr> <tr><td class="true">1</td><td class="false">0</td> <td class="false">0</td></tr> <tr><td class="true">1</td><td class="true">1</td><td class="true">1</td></tr> </table> Fonction ô combien remarquable...y compris pour les logiciens, qui voient en elle la fonction "équivalence logique", que nous avons rapidement évoquée tout à l'heure..., qui ne prend la valeur 1 que si A et B sont de même valeur. Bref, une fonction de coïncidence, également appelée XNOR...et qui est elle-même la fonction complémentaire de la fonction NOR, que nous venons de voir !: F(A, B) = A . B + A . B = A XNOR B
<table width="35%" align="left"> <tr><td width="30%">A</td><td width="30%">B</td> <td width="40%">F(A,B)</td> </tr> <tr><td class="false">0</td><td class="false">0</td><td class="true">1</td></tr> <tr><td class="false">0</td><td class="true">1</td><td class="false">0</td></tr> <tr><td class="true">1</td><td class="false">0</td><td class="true">1</td></tr> <tr><td class="true">1</td><td class="true">1</td><td class="false">0</td></tr> </table> Fonction pour laquelle A ne sert pas à grand chose puisque ne renvoie de fait que le complément de B. Il s'agit donc de notre fonction NOT, appliquée à B: F(A, B) = B		<table width="35%" align="left"> <tr><td width="30%">A</td><td width="30%">B</td> <td width="40%">F(A,B)</td> </tr> <tr><td class="false">0</td><td class="false">0</td><td class="true">1</td></tr> <tr><td class="false">0</td><td class="true">1</td><td class="false">0</td></tr> <tr><td class="true">1</td><td class="false">0</td><td class="true">1</td></tr> <tr><td class="true">1</td><td class="true">1</td><td class="true">1</td></tr> </table> Fonction sans grand intérêt pour nous...mais plus importante en logique propositionnelle, ou elle prend le nom d'"implication inverse".: F(A, B) = A + B
<table width="35%" align="left"> <tr><td width="30%">A</td><td width="30%">B</td> <td width="40%">F(A,B)</td> </tr> <tr><td class="false">0</td><td class="false">0</td><td class="true">1</td></tr> <tr><td class="false">0</td><td class="true">1</td><td class="true">1</td></tr> <tr><td class="true">1</td><td class="false">0</td> <td class="false">0</td></tr> <tr><td class="true">1</td><td class="true">1</td><td class="false">0</td></tr> </table> Ici aussi, c'est notre fonction NOT qui se cache derrière une façade binaire, la variable B ne servant strictement à rien: F(A, B) = A		<table width="35%" align="left"> <tr><td width="30%">A</td><td width="30%">B</td> <td width="40%">F(A,B)</td> </tr> <tr><td class="false">0</td><td class="false">0</td><td class="true">1</td></tr> <tr><td class="false">0</td><td class="true">1</td><td class="true">1</td></tr> <tr><td class="true">1</td><td class="false">0</td> <td class="false">0</td></tr> <tr><td class="true">1</td><td class="true">1</td><td class="true">1</td></tr> </table> Autre fonction sans grand intérêt pour nous, mais beaucoup plus utile aux logiciens...pour lesquels elle prend le nom d'"implication".: F(A, B) = A + B
<table width="35%" align="left"> <tr><td width="30%">A</td><td width="30%">B</td> <td width="40%">F(A,B)</td> </tr> <tr><td class="false">0</td><td class="false">0</td><td class="true">1</td></tr> <tr><td class="false">0</td><td class="true">1</td><td class="true">1</td></tr> <tr><td class="true">1</td><td class="false">0</td><td class="true">1</td></tr> <tr><td class="true">1</td><td class="true">1</td><td class="false">0</td></tr> </table> Fonction complémentaire de notre opérateur AND, et qu'il serait donc logique d'appeler NAND: F(A, B) = A . B = A + B...de Morgan, toujours... = A NAND B		<table width="35%" align="left"> <tr><td width="30%">A</td><td width="30%">B</td> <td width="40%">F(A,B)</td> </tr> <tr><td class="false">0</td><td class="false">0</td><td class="true">1</td></tr> <tr><td class="false">0</td><td class="true">1</td><td class="true">1</td></tr> <tr><td class="true">1</td><td class="false">0</td><td class="true">1</td></tr> <tr><td class="true">1</td><td class="true">1</td><td class="true">1</td></tr> </table> Fonction somme toute optimiste, donnant 1 quels que soient les valeurs de A et B. Bref, la fonction constante: F(A, B) = 1

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...