Algèbre de Boole

L'algèbre de Boole, ou calcul booléen, est la partie des mathématiques, de la logique et de l'électronique qui s'intéresse aux opérations ainsi qu'aux fonctions sur les variables logiques.



Catégories :

Algèbre - Fonction logique - Électronique numérique - Électronique

Recherche sur Google Images :


Source image : positron-libre.com
Cette image est un résultat de recherche de Google Image. Elle est peut-être réduite par rapport à l'originale et/ou protégée par des droits d'auteur.

Page(s) en rapport avec ce sujet :

  • La fonction OUI. Symbole logique. Schéma électrique. Table de vérité. Équation... L'algèbre de boole est l'algèbre de la logique binaire... (source : discip.crdp.ac-caen)

L'algèbre de Boole, ou calcul booléen, est la partie des mathématiques, de la logique et de l'électronique qui s'intéresse aux opérations ainsi qu'aux fonctions sur les variables logiques. Plus particulièrement, l'algèbre booléenne permet d'utiliser des techniques algébriques pour traiter les expressions à deux valeurs du calcul des propositions. Elle fut initiée par le mathématicien britannique du milieu du XIXe siècle George Boole.

Aujourd'hui, 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éphoniques par Claude Shannon.

L'algèbre de Boole des fonctions logiques sert à modéliser des raisonnements logiques, en exprimant un «état» selon conditions. Par exemple :

Communication = Émetteur ET Récepteur
Communication est «VRAI» si Émetteur actif ET Récepteur actif (c'est une fonction logique dépendant des variables Émetteur et Récepteur)
Décrocher = (Décision de répondre ET Sonnerie) OU décision d'appeler
Décrocher est «VRAI» si on entend la sonnerie ET qu'on décide de répondre OU si on décide d'appeler.

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

Algèbre de Boole des valeurs de vérité

On nomme B la totalité constitué de deux éléments nommés valeurs de vérité {VRAI, FAUX}. Cet ensemble est aussi noté

On privilégiera dans la suite la notation B = {1, 0}.

Sur cet ensemble on peut définir deux lois (ou opérations ou foncteurs), les lois ET et OU et une transformation nommée complémentaire, inversion ou contraire.

Conjonction

Articles connexes : Fonction ET et Conjonction logique.

Elle est définie de la manière suivante : a ET b est VRAI si et uniquement si a est VRAI et b est VRAI. Cette loi est aussi notée

On privilégiera dans la suite la notation \cdot \,

On peut construire la table de cette loi (comme une table d'addition ou de multiplication de notre enfance) mais on ne la confondra pas avec une table de vérité.

Table de la loi ET
b\a 0 1
0 0 0
1 0 1

Disjonction

Articles connexes : Fonction OU et Disjonction logique.

Elle est définie de la manière suivante : a OU b est VRAI si et uniquement si a est VRAI ou b est VRAI. (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 que cette loi n'a pas de rapport avec l'addition qu'on connaît.

Cependant, en mathématiques et en logique mathématique, on n'utilise pas cette notation pour l'ou inclusif dans les algèbres de Boole, à cause de la confusion avec l'addition des anneaux de Boole, Z/2Z, pour ce qui est du présent article. Dans ce cas l'addition correspond au ou exclusif.

Table de la loi OU
b\a 0 1
0 0 1
1 1 1

Négation

Articles connexes : Fonction NON et Négation logique.

Le contraire de "a" est VRAI si et uniquement si a est FAUX. Le contraire d'a est noté

On privilégiera dans la suite la notation \bar{a}.

On obtient alors \bar{0}=1 et \bar{1}=0

Propriétés

Associativité

Comme avec les opérations habituelles, certaines parenthèses sont inutiles :
(a + b) + c = a + (b + c) = a + b + c
(a. b). c = a. (b. c) = a. b. c

Commutativité

L'ordre est sans importance :
a + b = b + a
a. b = b. a

Distributivité

Comme avec les opérations habituelles, il est envisageable de distribuer :
a. (b + c) = a. b + a. c
Attention : comportement différent comparé aux opérateurs + et * habituels :
a + (b. c) = (a + b). (a + c)

Idempotence

a + a + a + [... ] + a = a
a. a. a. [... ]. a = a

Élément neutre

a + 0 = a
a. 1 = a

Élément nullité

0. a = 0
1 + a = 1

Absorption

a + a. b = a
a. (a + b) = a

Simplification

a + \overline{a}  = a + b
a . ( \overline{a} + b ) = a

Redondance

a  + \overline{a}  = a  + \overline{a}  + b

Complémentarité

a = \overline{\overline{a}}

(«La lumière est allumée» = «la lumière n'est pas non allumée»)

a + \overline{a} = 1

(«VRAI» SI lumière_allumée OU SI lumière_non_allumée → c'est toujours le cas → vrai dans l'ensemble des cas → toujours VRAI, par conséquent =1)

a . \overline{a} = 0

(«VRAI» SI lumière_allumée ET SI lumière_non_allumée → impossible → faux dans l'ensemble des cas → toujours FAUX par conséquent =0)

Structure

On retrouve alors l'ensemble des propriétés qui confèrent à B une structure d'algèbre de Boole

Priorité

Pour favoriser leur compréhension, il a été décidé que ces opérations seraient soumises aux mêmes règles que les opérations «de l'ensemble des jours», la fonction ET (multiplication logique) est ainsi prioritaire comparé à la fonction OU (somme logique)  ; on peut, pour s'aider, placer des parenthèses dans les opérations.

Exemple :
a = 0;b = 1;c = 1
On cherche a. b + c = ???
Initialement on calcule a. b :
a. b = 0.1
0.1 = 0
Puis, on calcule 0 + c :
0 + c = c
c = 1
Le résultat final est donc :
a. b + c = (a. b) + c = 1

Théorème de De Morgan

Fonction Table de vérité/Table de fonctionnement
\overline{ a + b } = \overline{a} . \overline{b}
a b a+b \overline{ a + b } \overline{ a } \overline{ b } \overline{a} . \overline{b}
0 0 0 1 1 1 1
0 1 1 0 1 0 0
1 0 1 0 0 1 0
1 1 1 0 0 0 0
Dans les deux cas, l'expression ne sera VRAIE que si a et b sont fausses.
Fonction Table de vérité/Table de fonctionnement
\overline{ a  } = \overline{a} + \overline{b}
a b a. b \overline{ a  } \overline{ a } \overline{ b } \overline{a} + \overline{b}
0 0 0 1 1 1 1
0 1 0 1 1 0 1
1 0 0 1 0 1 1
1 1 1 0 0 0 0
Dans les deux cas, l'expression ne sera FAUSSE que si a et b sont vraies.

Fonctions logiques

Article détaillé : Fonction logique.

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

Une table de vérité sert à préciser l'état de la sortie suivant les états des entrées.

On démontre que toute fonction logique peut se décrire avec trois opérations de base.

Fonctions logiques principales

Elles sont issues des trois opérations de base et définissent alors

Table de vérité de l'inverse
a \bar a
0 1
1 0
Table de vérité de la somme
a b a + \, b
0 0 0
0 1 1
1 0 1
1 1 1
Table de vérité du produit
a b a \cdot \, b
0 0 0
0 1 0
1 0 0
1 1 1

Fonctions logiques composées

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.

Disjonction exclusive

Article connexe : OU exclusif.

Le OU étudié jusqu'désormais doit se comprendre de la manière suivante : «l'un ou l'autre ou les deux». Il est aussi nommé «OU inclusif». Le OU exclusif (ou XOR pour'eXclusive OR') s'entend comme : «l'un ou l'autre, mais pas les deux».

Il se compose de la manière suivante :

a\ \operatorname{XOR}\ b = (a+b).\overline{(a°} = a\bar{b}+\bar{a}b
Table de vérité de XOR
a b a \oplus b
0 0 0
0 1 1
1 0 1
1 1 0

Le «ou exclusif» est quelquefois noté par le signe arithmétique \ne (différent de), auquel il est équivalent. Fonctionnellement, on utilise aussi un + entouré : a\oplus b.

Équivalence

L'équivalence (notée EQV) est vraie si les deux entrées ont la même valeur et fausse sinon. Elle est nommée aussi «non-ou exclusif» (ou encore et exclusif). Elle se compose comme suit :

a\ \operatorname{EQV}\ b = \overline{(a+b)}+(a°

On peut aussi dire que :

a\ \operatorname{EQV}\ b = \overline{a\ \operatorname{XOR}\ b}
Table de vérité de EQV
a b a \Leftrightarrow b
0 0 1
0 1 0
1 0 0
1 1 1

Il arrive que l'équivalence soit notée par le signe \Leftrightarrow, quoique ce choix ne soit pas recommandé compte-tenu des autres sens envisageables attachés à ce signe.

Elle peut aussi être notée "==" dans certains langages (C, C++, PHP…).

Implication

L'implication (notée IMP) s'écrit de la manière suivante :

a\ \operatorname{IMP}\ b = \overline{a}+b

Cette opération n'est pas commutative. a est une condition suffisante pour b, qui, elle , est une condition nécessaire pour a.

Mais a\ \operatorname{IMP}\ b = \overline{b}\ \operatorname{IMP}\ \overline{a}

Illustration : de l'affirmation

"S'il fait beau, j'irai me promener. "

on peut conclure

"Si je ne vais pas me promener, il ne fait pas beau. "

mais on ne peut pas en déduire

"S'il ne fait pas beau, je ne vais pas me promener. "

car on ne sait pas si je n'aime pas me promener aussi sous la pluie.

Table de vérité de IMP
a b a \Rightarrow b
0 0 1
0 1 1
1 0 0
1 1 1

Inhibition

L'inhibition (notée INH) se compose comme suit :

a\ \operatorname{INH}\ b = a.\overline{b}

Cette opération n'est pas commutative.

Table de vérité de INH
a b a.\overline{b}
0 0 0
0 1 0
1 0 1
1 1 0

Exemple de fonctions logiques à trois ou quatre variables

Fonction logique à trois variables

Si on reprend l'exemple du téléphone, on se trouve en présence de 3 variables :

la variable d = "on décroche" est fonction logique des 3 précédentes. On écrira que

d = a. b + c

car on décroche lorsque ça sonne et qu'on a envie de répondre ou lorsque on a envie d'appeler quelqu'un.

La table de vérité de cette fonction d est alors la suivante :

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'observation de la table montre que notre analyse première comportait une situation absurde : le téléphone sonne, on a envie d'appeler quelqu'un, mais on n'a pas envie de répondre et on décroche quand même . Cela n'est sans doute pas le comportement souhaité, il est par conséquent préférable de modifier la fonction décrocher de manière à ce qu'on obtienne le tableau suivant :

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

En lisant le procédé de la simplification des expressions ci-dessous, vous verrez que la formule de décrocher2 correspond à d2 =\bar aÀ+ a.

Fonction logique à quatre variables

Un bon élève s'interroge s'il est sage de sortir un soir. Il doit décider selon quatre propositions :

Cet élève pourra sortir si :

Donc l'expression logique de sortir selon l'état des variables a, b, c et d ; et elle peut s'écrire ainsi :

Sortir =  a°({\bar c}+d)

Minimisation d'une expression

Une fonction logique peut être déterminée

Exemple : Dans l'exemple de "téléphoner2", on s'aperçoit que le résultat est à 1 lorsque (a, b, c) = (0, 0, 1) ou (0, 1, 1) ou (1, 1, 0) ou (1, 1, 1).

Cela sert à définir d2 par d2 =\bar aar bÀ+ \bar a°c + a°\bar c + a°c

Il est alors intéressant 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

Exemple (suite)  : la somme précédente peut être réduite en

d2 =\bar aÀ+ a

par factorisation des deux premiers termes par \bar aÀ et factorisation des deux derniers termes par  a°\,

Arbre d'expression

Les expressions logiques sont fréquemment représentées en informatique sous forme d'arborescence. Cette dernière comporte un sommet (la racine en fait) auquel sont rattachés différents sous-arbres (ou branches). Les bifurcations sont des sommets internes. Le nombre de sous-arbres reliés à un même sommet est nommé arité. Les sommets sans issue sont nommés feuilles. Chaque sommet interne est identifié par un opérateur booléen tandis que les feuilles représentent les variables qui subissent ces opérations.

Voir aussi


Recherche sur Amazone (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Alg%C3%A8bre_de_Boole_(logique).
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 07/04/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu