Dans le monde d'aujourd'hui, Algèbre de Boole (logique), que ce soit comme sujet de débat, comme personnage pertinent ou comme date emblématique, a acquis une importance significative dans divers domaines. Que ce soit dans la politique, la culture, la science ou la vie quotidienne, Algèbre de Boole (logique) se positionne comme un élément clé qui donne le ton à nos actions et décisions. Dans cet article, nous analyserons l'impact et la pertinence de Algèbre de Boole (logique) dans différents contextes, ainsi que son influence sur notre société. Depuis son apparition, Algèbre de Boole (logique) a suscité un intérêt notable et sa présence continue aujourd’hui de susciter débats et réflexions.
L'algèbre de Boole, ou calcul booléen, est la partie des mathématiques qui s'intéresse à une approche algébrique de la logique, vue en termes de variables, d'opérateurs et de fonctions sur les variables logiques, ce qui permet d'utiliser des techniques algébriques pour traiter les expressions à deux valeurs du calcul des propositions. Elle fut lancée en 1854 par le mathématicien britannique George Boole. L'algèbre de Boole trouve de nombreuses applications en informatique et dans la conception des circuits électroniques.
Elle fut utilisée la première fois pour les circuits de commutation téléphonique par Claude Shannon.
L'algèbre de Boole des fonctions logiques permet de modéliser des raisonnements logiques, en exprimant un « état » en fonction de conditions. Par exemple, si nous étudions l'expression Communication et l'expression Décrocher :
L'algèbre de Boole étant un domaine commun à trois disciplines, on rencontre des notations différentes pour désigner un même objet. Dans le reste de l'article, on indiquera les diverses notations, mais on en privilégiera une pour conserver une certaine homogénéité.
On appelle B l'ensemble constitué de deux éléments appelés valeurs de vérité {VRAI, FAUX}. Cet ensemble est aussi noté
avec pour et pour .
On privilégiera dans la suite la notation .
Sur cet ensemble on peut définir deux lois (ou opérations) binaires, les lois ET et OU, et une opération unaire, la négation (ou le complémentaire).
Pour l'ensemble des exemples et propriétés suivantes,
Table de la loi ET | ||
b\a | 0 | 1 |
0 | 0 | 0 |
1 | 0 | 1 |
Elle est définie de la manière suivante : a ET b est VRAI si et seulement si a est VRAI et b est VRAI.
Cette loi est aussi notée :
On privilégiera dans la suite la notation « ».
La table de cette loi (analogue à une table d'addition ou de multiplication) n'est pas une table de vérité.
Table de la loi OU | ||
b\a | 0 | 1 |
0 | 0 | 1 |
1 | 1 | 1 |
Elle est définie de la manière suivante : a OU b est VRAI si et seulement si a est VRAI ou b est VRAI. (En particulier, si a est vrai et que b est vrai aussi, alors a OU b est vrai.)
Cette loi est aussi notée :
On privilégiera dans la suite la notation mais on prendra garde du fait que cette loi n'est pas l'addition usuelle dans Z/2Z. C'est pourquoi, en mathématiques et en logique mathématique, la notation n'est pas utilisée pour désigner le « ou inclusif » : elle est réservée au « ou exclusif », opération qui (jointe au « et ») fait de toute algèbre de Boole un anneau de Boole, en particulier une Z/2Z-algèbre.
La négation de a est VRAIE si et seulement si a est FAUX.
La négation de a est notée :
On privilégiera dans la suite la notation .
On obtient alors et .
Les opérateurs sont concernés par plusieurs propriétés communes :
Par ailleurs, chaque opérateur possède un élément neutre et un élément absorbant :
Des simplifications sont possibles comme :
le théorème du consensus s'applique aux opérateurs de l'algèbre de Boole :
Enfin, ils suivent le principe de complémentarité :
On retrouve alors toutes les propriétés qui confèrent à B une structure d'algèbre de Boole.
Pour alléger les écritures, il est d'usage que les opérations booléennes soient soumises aux mêmes règles de priorité que les opérations arithmétiques usuelles : la fonction ET (multiplication logique) est donc prioritaire par rapport à la fonction OU (somme logique). Ainsi :
Il reste possible de placer des parenthèses dans les calculs pour changer l'ordre de priorité des opérations.
Dans les deux cas, l'expression ne sera VRAIE |
Dans les deux cas, l'expression ne sera FAUSSE |
Mathématiquement, une fonction logique ou opérateur logique est une application de Bn dans B.
En électronique, une fonction logique est une boîte noire qui reçoit en entrée un certain nombre de variables logiques et qui rend en sortie une variable logique dépendant des variables d'entrée. L'article fonction logique précise comment construire les boîtes noires de quelques fonctions fondamentales.
Une table de vérité permet de préciser l'état de la sortie en fonction des états des entrées. Elle caractérise la fonction logique.
Toute table de vérité, et donc toute fonction logique, peut se décrire à l'aide des trois opérations de base :
On démontre aussi qu'il existe exactement fonctions logiques de paramètres. Il suffit en effet de considérer toutes les tables de vérités possibles, ou de considérer le développement d'une fonction de paramètres.
Elles sont issues des trois opérations de base et définissent alors
|
|
|
|
Ce sont les fonctions logiques à deux variables. Parmi celles-ci, on en dénombre certaines suffisamment intéressantes pour qu'on leur donne un nom.
Table de vérité de XOR | ||
a | b | a b |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
Le OU étudié jusqu'à présent doit se comprendre de la manière suivante : « l'un ou l'autre ou les deux ». Il est également appelé « OU inclusif ». Le OU exclusif (ou XOR pour ' eXclusive OR') s'entend comme : « l'un ou l'autre, mais pas les deux ».
On peut également le définir avec un modulo sur une somme ordinaire :
Le « ou exclusif » est parfois noté par le signe arithmétique (différent de). Fonctionnellement, on utilise aussi un + entouré :.
Propriété - Toute table de vérité, toute fonction logique, peut se décrire à l'aide de la constante 1 et des deux opérations : disjonction exclusive et conjonction, car :, et
Table de vérité de EQV | ||
a | b | a b |
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
L'équivalence (notée EQV ou XNOR) est vraie si les deux entrées ont la même valeur et fausse sinon. C'est la négation du « ou exclusif ».
L'équivalence est souvent notée par le signe . Elle peut aussi être notée « == » dans certains langages (C++, PHP…) et « ⊙ » en électronique.
Table de vérité de IMP | ||
a | b | a b |
0 | 0 | 1 |
0 | 1 | 1 |
1 | 0 | 0 |
1 | 1 | 1 |
Cette opération n'est pas commutative. a est une condition suffisante pour b, qui, elle, est une condition nécessaire pour a.
Mais
De l'affirmation « SI j'habite en Allemagne, ALORS j'habite en Europe. », on peut déduire « SI je n'habite pas en Europe, ALORS je n'habite pas en Allemagne. » mais pas « SI je n'habite pas en Allemagne, ALORS je n'habite pas en Europe. » car je peux habiter en Europe ailleurs qu'en Allemagne, sans contredire l'énoncé initial.
Table de vérité de INH | ||
a | b | |
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 1 |
1 | 1 | 0 |
Si a est VRAI, l'expression vaut VRAI, SAUF si b est VRAI.
Cette opération n'est pas commutative.
Table de vérité de décrocher | ||||||||||||||||||||||||||||||||||||||||||
a | b | c | d | |||||||||||||||||||||||||||||||||||||||
0 | 0 | 0 | 0 | |||||||||||||||||||||||||||||||||||||||
0 | 0 | 1 | 1 | |||||||||||||||||||||||||||||||||||||||
0 | 1 | 0 | 0 | |||||||||||||||||||||||||||||||||||||||
0 | 1 | 1 | 1 | |||||||||||||||||||||||||||||||||||||||
1 | 0 | 0 | 0 | |||||||||||||||||||||||||||||||||||||||
1 | 0 | 1 | 1 | |||||||||||||||||||||||||||||||||||||||
1 | 1 | 0 | 1 | |||||||||||||||||||||||||||||||||||||||
1 | 1 | 1 | 1 |
L'égalité Décrocher = (Sonnerie ET Décision de répondre) OU Décision d'appeler traduit la situation pratique suivante : On décroche un téléphone quand on décide d'appeler quelqu'un ou quand le téléphone sonne et qu'on décide de répondre.
Elle est constituée de trois variables :
la variable d = « Décrocher » est fonction logique des 3 précédentes et peut s'écrire
La table de vérité de cette fonction d est alors la suivante (à droite) :
Table de vérité de décrocher2 | ||||||||||||||||||||||||||||||||||||||||||
a | b | c | d2 | |||||||||||||||||||||||||||||||||||||||
0 | 0 | 0 | 0 | |||||||||||||||||||||||||||||||||||||||
0 | 0 | 1 | 1 | |||||||||||||||||||||||||||||||||||||||
0 | 1 | 0 | 0 | |||||||||||||||||||||||||||||||||||||||
0 | 1 | 1 | 1 | |||||||||||||||||||||||||||||||||||||||
1 | 0 | 0 | 0 | |||||||||||||||||||||||||||||||||||||||
1 | 0 | 1 | 0 | |||||||||||||||||||||||||||||||||||||||
1 | 1 | 0 | 1 | |||||||||||||||||||||||||||||||||||||||
1 | 1 | 1 | 1 |
La table indique une situation absurde : quand on décide d'appeler quelqu'un et que le téléphone sonne sans qu'on ait envie de répondre, on décrocherait quand même. Une modification de la table comme ci-contre corrigerait cette absurdité. Cette table correspond à une fonction logique Décrocher d2 ou d2 qu'il est possible de déterminer et simplifier en .
Un bon élève s'interroge s'il est sage de sortir un soir. Il doit décider en fonction de quatre variables :
Cet élève pourra sortir si :
L'expression logique de sortir en fonction de l'état des variables a, b, c et d peut donc s'écrire ainsi :Sortir =
Une fonction logique peut être déterminée
Exemple : Dans l'exemple de "Décrocher2", la lecture de la table montre que égale quand ou ou ou .Cela permet de définir d2 par
Il est possible de trouver une expression minimisant le nombre de termes et le nombre de lettres dans chaque terme. C'est l'objectif de certaines techniques comme la méthode de Quine-Mc Cluskey, les diagrammes de Karnaugh, la méthode des consensus, la double dualisation…
Exemple (suite) : la somme précédente peut être réduite par factorisation des deux premiers termes par et factorisation des deux derniers termes par
Les expressions logiques sont souvent représentées en informatique sous forme d'arborescence.
À un premier sommet (racine) sont rattachés différents sous-arbres (ou branches). Les sommets sans issue sont appelés feuilles.
Chaque sommet interne correspond à un sélecteur booléen « si alors sinon », qui ramène une question à deux sous-questions plus simples, éventuellement réduites à 1/vrai ou 0/faux.
L'évaluation d'une fonction f dépendant d'une variable q choisie pour la première question est alors , qui ramène à deux expressions indépendantes de .
Soit ; on peut écrire
Les arbres dépendant de l'expression et de l'ordre des questions, pour une même expression certains questionnaires seront plus simples que d'autres.