Algèbre de Boole Article, Signification, Explication

En mathématiques, une algèbre de Boole ou un treillis booléen est un type de structure algébrique.

Les algèbres de Boole les plus souvent utilisées sont celle des fonctions logiques comme la conjonction (et), la disjonction (ou) et la négation (notamment dans les disciplines utilisant la logique booléenne : mathématiques, informatique et électronique numérique) et celle de l'ensemble des parties d'un ensemble muni des opérations d'inclusion, d'intersection et de la complémentation.

Le nom provient de George Boole, un mathématicien britannique qui durant le milieu du XIXe siècle restructura complètement la logique en un système formel. Plus spécifiquement, l'algèbre booléenne permet d'utiliser des techniques algébriques pour traiter les expressions à deux valeurs de la logique des propositions. 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 permet de modéliser des raisonnements logiques, en exprimant un « état » en fonction de conditions. Par exemple :

Vert = Bleu ET Jaune

Vert est « VRAI » SI il ya du bleu ET du jaune (c'est une fonction logique dépendant des variables Bleu et Jaune)

Décrocher = ( Envie de répondre ET Sonnerie ) OU envie_d'appeler

Décrocher est « VRAI » SI on entend la sonnerie ET que l'on envie de répondre OU SI l'on a envie d'appeler

Table of contents

1 Point de vue algébriste 1.1 Définition mathématique d'une algèbre de Boole 1.2 Propriétés 1.3 Conclusion 2 Algèbre de Boole des fonctions logiques 3 Table de vérité 3.4 Cas dégénérés 3.5 Tables opérationnellement utiles 4 Opérateurs logiques 4.6 Somme logique OU 4.7 Multiplication logique ET 4.8 Inversion logique NON 5 Propriétés des opérateurs 5.9 Priorité 5.10 Associativité 5.11 Commutativité 5.12 Distributivité 5.13 Idempotence 5.14 Complémentarité 5.15 Théorème de De Morgan 6 Opérateurs composés 6.16 OU exclusif 6.17 Équivalence 6.18 Implication 6.19 Inhibition 7 Voir aussi :

Point de vue algébriste

Définition mathématique d'une algèbre de Boole

Bien que cet article traite principalement de l'algèbre de Boole des fonctions logiques, il est nécessaire pour obtenir une définition rigoureuse d'une algèbre de Boole de se la donner en des termes d'algèbre abstraite.

Une algèbre de Boole est un ensemble contenant deux éléments particuliers, et , muni de deux lois de composition internes, et , et qui vérifie les axiomes suivants () :

1. associativité : et
2. commutativité : et
3. absorption : et
4. distributivité d'une loi par rapport à l'autre : et
5. idempotence : et
6. bornes : et
7. complémentarité : a possède un complémentaire noté , tel que et

Les propriétés 1, 2, 3 et 5 définissent une structure de treillis. Ainsi, une algèbre de Boole est un treillis borné, distributif et complémentaire.

Propriétés

Ces propriétés se démontrent à partir des axiomes de la définition :

• .
• .
• .
• est l'élément neutre de la loi .
• est l'élément neutre de la loi .
• .
• (ces deux dernières formules sont les formules de De Morgan).

Conclusion

Dans la suite, nous nous restreindrons à l'étude de l'algèbre de Boole des fonctions logiques, que nous définirons dans la section qui suit. Rappelons-nous cependant qu'une algèbre de Boole n'est qu'une construction algébrique abstraite qui a priori n'est pas nécessairement un ensemble de fonctions logiques. L'ensemble des parties d'un ensemble, muni des opérations d'union, d'intersection et de complémentation forme un autre exemple, lui aussi très banal, bien que rarement qualifié d'algèbre de Boole.

Algèbre de Boole des fonctions logiques

• Les valeurs de vérité (ou booléens) sont les valeurs VRAI et FAUX, qui représenteront l'état d'une variable logique.

• Nous appelerons algèbre de Boole des valeurs de vérité l'ensemble {VRAI, FAUX} (ou encore {1, 0}), où 1 joue le rôle de et 0 celui de , muni des opérations logiques OU et ET (notées + et .) qui jouent les rôles des lois et et où la négation logique NON (notée ¯, c'est-à-dire une barre par dessus l'élément que l'on complémente) est l'opérateur de complémentation ().

• Nous nous donnons un ensemble V de symboles appelées variables logiques. Une valuation de V est une fonction qui à chaque variable logique associe une valeur de vérité. On supposera que V est un ensemble fini.

L'idée intuitive que l'on doit avoir d'une variable logique est celle d'une condition de la situation réelle observée, qui peut être satisfaite (état à VRAI), ou non (état à FAUX). Une valuation est la donnée de l'état de tout le système observé.

Exemple avec un état:

0 = lampe éteinte

1 = lampe allumée

• L'algèbre de Boole des fonctions logiques est l'algèbre des fonctions qui à une valuation de V associent une valeur de vérité. Les opérations , et , toujours appelées OU, ET et NON se déduisent des opérations OU, ET et NON de l'algèbre des valeurs de vérité (par exemple : la négation d'une fonction logique f est la fonction logique NON(f) qui à une valuation v associe NON(f(v))).

Dans la pratique (dans le cadre de la logique propositonnelle), ces fonctions sont construites :

• soit à partir des valeurs de vérité 0 et 1 : ce sont les fonctions logiques constantes notées aussi 0 et 1 et qui valent toujours respectivement FAUX et VRAI quelle que soit la valuation des variables logiques
  soit à partir d'une variable logique p : c'est la fonction notée p (le même symbole que la variable) où p(v) vaut VRAI si et seulement si v(p) vaut VRAI
  soit à partir d'autres fonctions logiques, composées entre elles par les opérateurs logiques ET, OU et NON

Notons que selon la logique utilisée, il peut exister d'autres constructions (par exemple avec des quantificateurs, dans la logique du premier ordre). Dans le cas où V est fini (le cas qui nous intéresse), les constructions données plus haut permettent d'obtenir toutes les fonctions logiques.

Table de vérité

Une table de vérité est une table permettant de connaître les valeurs de sortie d'un opérateur logique en fonction des valeurs en entrée.

Cas dégénérés

Lorsqu'il y a deux entrées x et y et une sortie z, on peut en théorie définir 16 tables de vérité distinctes correspondant aux 16 quadruplets possibles de valeurs de la table. Dans la pratique, ne présentent pas d'intérêt celles pour lesquelles :

• la valeur de sortie ne dépend pas des valeurs d'entrée (z identique, soit 0, soit 1, quels que soient x et y)
• la valeur de sortie ne dépend que d'une seule des valeurs d'entrée (par exemple z = x ou non-x quel que soit y, ou bien y ou non-y quel que soit x.

Cela élimine l'intérêt pratique de 6 des tables.

Tables opérationnellement utiles

6 des 10 autres tables ont déjà des correspondances dans le domaine du quotidien, ce qui permet de les nommer sans difficulté :

• ET,
• OU,
• OU exclusif (autrement dit, pour du binaire, « différent de »),
• NI,
• x implique y
• y implique x.

Il s'agit bien entendu dans les deux derniers cas d'une implication au sens de variables logiques et non de causalité! La relation « A implique B » est vraie dans deux cas seulement :

• quand A est faux
• quand A et B sont tous deux vrais.

A n'en a pas pour autant vocation à être la cause de B. Ils sont simplement couplés d'une façon asymétrique.

a	b	valeur de a opérateur b
0	0	x1
0	1	x2
1	0	x3
1	1	x4

Opérateurs logiques

On écrit souvent sous forme symbolique trois des opérateurs logiques élémentaire, de façon hélas différente selon les contextes d'utilisation :

• ET
  • « . » (un point) en notation logique
  • « & » dans quelques langages de programmation (Perl, C...)
  • « ∧ » dans quelques notations algébriques, ou en APL
• OU :
  • « + » (un plus) en notation logique
  • « | » dans quelques langages de programmation
  • « ∨ » dans quelques notations algébriques ou en APL.
• NON :
  • « ¯ » (une barre placée au-dessus d'une variable ou d'un groupe de variables) en notation logique
  • « ! » dans quelques langages de programmation
  • « ~ » dans quelques notations algébriques ou en APL.

Exemples de lecture :

• a . b = S ⇔ « a ET b est égal à S ».
• a + b = S ⇔ « a OU b est égal à S ».
• ā se lit « a barre » et compte comme l'inverse de a. (0 si a=1, 1 si a=0)

Quelle que soit la notation symbolique utilisée :

• Le OU (opération +) est une loi de composition interne (="opération) dont 0 est l'élément neutre.
• Le ET (opération .) est une loi de composition interne distributive et associative par rapport au OU.
• Chacune de ces deux opérations est commutative (on peut sans changer sa valeur permuter ses deux arguments)
• L'ensemble des booléens muni de l'opération OU forme un groupe commutatif.
• L'ensemble des booléens munie de l'opération OU et de l'opération ET forme donc un anneau. Sa relation additive est le OU et sa relation multiplicative est le ET.
• Noter le OU par un +, et le symbole ET par un . permet donc de réutiliser facilement les réflexes de factorisation et d'autres transformations déjà connues dans le contexte de l'algèbre.

ATTENTION:

• Il ne faut pas confondre les opérateurs logiques avec les opérateurs d'addition de multiplication...
• Pour simplifier l'écriture informatique le symbole NON est parfois remplacé par le caractère | après la variable. ā devient en ce cas a|.

Somme logique OU

La somme logique OU est ici notée « + ».
Il suffit qu'un des termes soit « VRAI » (=1) pour que l'expression soit « VRAIE » (=1).

Règles:

• a + 0 = a

  Explication :

  Dans « a OU quelque_chose_d'impossible », seul « a » compte car l'impossible (le 0) n'arrive jammais et ne peut donc jamais rendre l'expression « VRAIE ». Comme il n'est pas indispensable, il ne la rend pas non plus fausse.

• a + 1 = 1

  Explication :

  "a OU quelque_chose_de_toujours_vrai" est toujours vrai. Car il suffit qu'une des deux conditions soit « VRAIE », et « 1 » l'est toujours.

Table de verité

a	b	a OU b
0	0	0
0	1	1
1	0	1
1	1	1

Multiplication logique ET

La multiplication logique ET est ici notée « . ».
Il faut que les deux termes soient « VRAIS » (=1) pour que l'expression soit « VRAIE » (=1).

Règles :

• a . 1 = a

  Explication :

  Comme « 1 » est toujours « VRAI » (=1), on ne se préoccupe pas de son état, mais seulement de celui de « a ».

• a . 0 = 0

  Explication :

  Comme « 0 » est toujours « FAUX » (=0), il est impossible que les deux termes soient vrais.

Table de verité

a	b	a ET b
0	0	0
0	1	0
1	0	0
1	1	1

Inversion logique NON

L'inversion logique NON est ici notée « ¯ » (signe placé au-dessus du terme inversé) ou « | » (signe placé après le terme inversé).
Elle est égale à l'inverse de ce à quoi elle s'applique.

Exemple :

a = 0 ↔ a| = 1

a ne peut avoir que deux états possibles 1 ou 0, si a = 0 alors a| = 1. La fonction NON remplace le 0 par 1 et le 1 par 0.

Table de verité

a	NON a
0	1
1	0

Propriétés des opérateurs

Il s'agit de règles permettant d'aboutir à autre manière de décrire la situation. Par exemple, il est plus facile de dire que « la lampe est allumée » que « la lampe n'est pas non allumée ».

Priorité

Pour faciliter leur compréhension, il a été décidé que ces opérations seraient soumises aux même règles que les opérations « de tous les jours », la fonction ET (multiplication logique) est ainsi prioritaire par rapport à 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 = ???

D'abord 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 = 1

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 possible de distribuer:
a . ( b + c ) = a . b + a . c
Attention: comportement différent par rapport aux opérateurs + et * habituels:
a + ( b . c ) = ( a + b ) . ( a + c )

Idempotence

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

Complémentarité

a = a||

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

a + a| = 1

(« VRAI » SI lumière_allumée OU SI lumière_non_allumée → toujours le cas → toujours VRAI)

a . a| = 0

(« VRAI » SI lumière_allumée ET SI lumière_non_allumée → impossible → toujours FAUX)

Théorème de De Morgan

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

Dans les deux cas, l'expression ne sera VRAIE que si a et b sont fausses.

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

Dans les deux cas, l'expression ne sera VRAIE que si a ou b sont fausses.

Opérateurs composés

À partir de ces opérateurs élémentaires, on peut en composer un certain nombre d'autres :

OU exclusif

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) s'entend comme : « l'un ou l'autre mais pas les deux ». Il se compose de la manière suivante :

a XOR b = (a+b).(a.b)|

Table de verité

a	b	a XOR b
0	0	0
0	1	1
1	0	1
1	1	0

Le « ou exclusif » est parfois noté par le signe arithmétique différent de, auquel il est équivalent fonctionnellement on utilise aussi un + entouré: a ⊕ b.

Équivalence

L'équivalence (notée EQV) est vrai si les deux entrées ont la même valeur et faux sinon. Elle se compose comme suit :

a EQV b = (a+b)|+(a.b) On peut aussi dire que : a EQV b = (a XOR b)|

Table de verité

a	b	a EQV b
0	0	1
0	1	0
1	0	0
1	1	1

Il arrive que l'équivalence soit notée par le signe « = », bien que ce choix ne soit pas recommandé compte-tenu des autres sens possibles attachés à ce signe.

Implication

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

a IMP b = a|+b

Cette opération n'est pas commutative.

Table de verité

a	b	a IMP b
0	0	1
0	1	1
1	0	0
1	1	1

Inhibition

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

a INH b = a.b|

Cette opération n'est pas commutative.

Table de verité

a	b	a INH b
0	0	0
0	1	0
1	0	1
1	1	0

Voir aussi :

Fonction logique ~ calcul des propositions ~ systèmes de numération ~ électronique numérique ~ neurone

Algèbre de Boole [1]

C'est un article concernant le Algèbre de Boole. La page contient la signification du Algèbre de Boole , Description et explication au sujet de Algèbre de Boole