La principale contribution de George Boole, mathématicien et logicien
anglais (1815--1864), a consisté en une mathématisation de la logique. Pour
cela, il a introduit le traitement algébrique de variables sans
signification numérique. L'algèbre de Boole, qu'il définit en
1854 dans son traité An investigation of the laws of thought, est une
base mathématique de la logique des circuits électroniques, notamment.
Une algèbre de Boole est un domaine muni des constantes 0, 1 et des
opérations inverse, somme et produit. Nous noterons l'inverse par une
barre au dessus de l'opérande inversé, la somme par Ú et le produit
par Ù. Ces opérations ont les propriétés suivantes :
la somme et le produit sont associatifs, commutatifs et idempotents ;
le produit est distributif sur la somme et la somme est distributive
sur le produit ;
0 est élément neutre de la somme, 1 est élément neutre du produit ;
0 est élément absorbant du produit, 1 est élément absorbant de la
somme ;
x Ú x = 1 (loi du tiers exclu), x Ù x = 0
(principe de contradiction), x = x ;
x Ù y = x Ú y, x Ú y
= x Ù y (lois de Morgan).
Dans la logique des circuits électroniques, on appelle habituellement le
produit "et" (and), la somme "ou"
(or) et l'inverse "non" (not),
et le domaine est réduit à 0, 1, qu'on appelle aussi faux,
vrai ou false, true1.
Les fonctions logiques suivantes sont souvent utilisées :
ou exclusif (xor) : x xor y = (x Ù
y) Ú (y Ù x)
implication : x Ţ y = x Ú y
équivalence : x Ű y = (x Ţ y) Ù (y
Ţ x)
"non ou" (nor) : x nor y =
x Ú y = x Ù y
"non et" (nand) : x nand y =
x Ù y = x Ú y
Pour tous ces opérateurs et fonctions, on recourt habituellement à une
table de vérité, qui permet d'énumérer toutes les solutions selon
les états des entrées.
J'en donne quelques-unes ci-dessous, à titre d'exemple :
Mais on notera que (E, È, Ç), par exemple, définit également une
algèbre de Boole (l'algèbre des parties d'un ensemble E), le produit étant
dans ce cas l'intersection, la somme l'union, l'inverse la partie
complémentaire, 1 est E et 0 est Ø.