Today: Saturday 24 July 2021 , 11:26 am


advertisment
search




Algèbre de Boole (logique)

Dernière mise à jour 17 Jour , 18 heure 45 Vues

Advertisement
In this page talks about ( Algèbre de Boole (logique) ) It was sent to us on 06/07/2021 and was presented on 06/07/2021 and the last update on this page on 06/07/2021

Votre commentaire


Entrez le code
 
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. 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.

Exemple introductif


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 dans les expressions :
;Communication = Émetteur ET Récepteur
Communication serait « VRAI » si à la fois les variables Émetteur ET Récepteur étaient actifs (c'est une fonction logique dépendant des variables Émetteur et Récepteur)

;Décrocher = (Sonnerie ET Décision de répondre) OU Décision d'appeler
Décrocher serait « VRAI » soit si à la fois on entend la sonnerie ET l'on décide de répondre, soit (OU) si simplement l'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 appelle B l'ensemble constitué de deux éléments appelés valeurs de vérité {VRAI, FAUX. Cet ensemble est aussi noté
  • B=\{1,0\
  • B= \{\top , \perp \.
On a donc, \forall x \in B, \top \Leftrightarrow 1 , \perp \Leftrightarrow 0 .
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 appelée complémentaire, inversion ou contraire.
Pour l'ensemble des exemples et propriétés suivantes, \{a, b, c\ \subset B

Conjonction


{align="right" cellspacing="0" border="1"
- style = "background:#b3e2d1;text-align:center"
colspan="3"Table de la loi ET
- style="text-align:center"
width="50"b\awidth="50"0width="50"1
- style="text-align:center"
000
- style="text-align:center"
101
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 :
  • \cdot \,.
  • \wedge.
  • « & » ou « && » dans la plupart des langages de programmation (Perl, C, PHP, Swift…).
  • « AND » dans certains langages de programmation (Ada, Pascal, Perl, Python, PHP …).
  • « ∧ » dans quelques notations algébriques, ou en APL .
  • « * » (une multiplication ordinaire), pour quelques langages ne disposant pas de fonction adapté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) mais on ne la confondra pas avec une table de vérité.

Disjonction

{align="right" cellspacing="0" border="1"
- style = "background:#b3e2d1;text-align:center"
colspan="3"Table de la loi OU
- style="text-align:center"
width="50"b\awidth="50"0width="50"1
- style="text-align:center"
001
- style="text-align:center"
111
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 :
  • +.
  • « ∨ » (« \vee ») en mathématiques (et en logique mathématique) ou en APL.
  • «» ou «» dans certains langages de programmation.
  • En toutes lettres « or » ou « OR » en logique ou dans certains langages de programmation.
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.

Négation


La négation de a est VRAIE si et seulement si a est FAUX.
La négation de a est notée :
  • non-a, non a, not a.
  • \bar{a.
  • a/.
  • \neg a.
  • « ~a » dans quelques notations algébriques, en APL et dans quelques langages d'interrogation de bases de données (SQL…).
  • « ! » dans quelques langages de programmation (C, C++…)
  • « 1- » dans quelques langages ne disposant pas de fonctions adaptées (Batch…) (puisque 1-0=1 et 1-1=0).
On privilégiera dans la suite la notation \bar{a.
On obtient alors \bar{0=1 et \bar{1=0.

Propriétés

Propriétés des opérateurs

Les opérateurs sont concernés par plusieurs propriétés communes :
  • Associativité : Comme avec les opérations habituelles, certaines parenthèses sont inutiles. ( a + b ) + c = a + (b + c) = a + b + c .
  • Commutativité : L'ordre est sans importance. a . b = b . a .
  • Distributivité : a . ( b + c ) = a . b + a . c .
  • Idempotence : a + a + a + ... + a = a .
Par ailleurs, chaque opérateur possède un élément neutre et un élément absorbant :
  • a+0=a
  • a.1=a
  • 0 . a = 0
  • b.(b+a)=b+b.a=b
Ils peuvent être simplifiés :
  • a + \overline{a . b = a + b
  • a . ( \overline{a + b ) = a . b
Le Théorème du consensus s'applique aux opérations de l'algèbre de Boole
  • a . b + \overline{a . c = a . b + \overline{a . c + b . c
  • Enfin, ils suivent le principe de complémentarité :
    • Involution : a = \overline{\overline{a ( la proposition "La lumière est allumée" équivaut à "la lumière n'est pas non allumée" ou, dit autrement, "la lumière n'est pas éteinte").
    • Tiers exclus : a + \overline{a = 1 (la proposition "lumière allumée" OU "lumière non allumée" est toujours VRAI.).
    • Contradiction ou antilogie : a . \overline{a = 0 (la proposition "lumière allumée" ET "lumière non allumée" est toujours FAUX.).

    Structure

    On retrouve alors toutes les propriétés qui confèrent à B une structure d'algèbre de Boole.

    Priorité

    Pour faciliter leur compréhension, on a décidé que ces opérations seraient soumises aux mêmes 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 \cdot b + c = ???
    D'abord on calcule a \cdot b :
    a \cdot b = 0 \cdot b = 0 \cdot 1 = 0
    Puis, on calcule 0 + c = 0 + 1 = 1
    Le résultat final est donc:
    a \cdot b + c = ( a \cdot b )+ c = 1

    Théorème de De Morgan

    {width="100%"
    -
    align="center"
    ; Première loi de De Morgan (négation de la disjonction)
    s'exprime par l'égalité suivante \overline{ a + b = \overline{a . \overline{b
    {width="150" cellspacing="0" border="1"
    + style = "background:#b3e2d1"Table de vérité/Table de fonctionnement
    -
    !scope=cola
    !scope=colb
    !scope=cola + b
    !scope=col\overline{ a + b
    !scope=col\overline{ a
    !scope=col\overline{ b
    !scope=col\overline{a . \overline{b
    - style="text-align:center"
    !scope=row0
    !scope = row0
    01111
    - style="text-align:center"
    !scope=row0
    !scope = row1
    10100
    - style="text-align:center"
    !scope=row1
    !scope = row0
    10010
    - style="text-align:center"
    !scope=row1
    !scope = row1
    10000
    Dans les deux cas, l'expression ne sera VRAIE
    que si a et b sont fausses.
    align="center"
    ; Deuxième loi de De Morgan (négation de la conjonction)
    \overline{ a . b = \overline{a + \overline{b
    {class="wikitable" width="150" cellspacing="0" border="1"
    + style = "background:#b3e2d1"Table de vérité/Table de fonctionnement
    -
    !scope=cola
    !scope=colb
    !scope=cola . b
    !scope=col\overline{ a . b
    !scope=col\overline{ a
    !scope=col\overline{ b
    !scope=col\overline{a + \overline{b
    - style="text-align:center"
    !scope=row0
    !scope = row0
    01111
    - style="text-align:center"
    !scope=row0
    !scope = row1
    01101
    - style="text-align:center"
    !scope=row1
    !scope = row0
    01011
    - style="text-align:center"
    !scope=row1
    !scope = row1
    10000
    Dans les deux cas, l'expression ne sera FAUSSE
    que si a et b sont vraies.

    Fonctions logiques


    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 :
    • disjonction (OU)
    • conjonction (ET)
    • négation (NON)
    On démontre aussi qu'il existe exactement 2^{2^n fonctions logiques de n 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 n paramètres.

    Fonctions logiques fondamentales

    {cellspacing="5"
    - valign="top"
    Elles sont issues des trois opérations de base et définissent alors
    • une fonction de B dans B : le complémentaire ou inversion
    • deux fonctions de B2 dans B qui sont la somme (OU) et le produit (ET)
    align="center" width="12%"
    {class="wikitable" width="100" cellspacing="0" border="1"
    - style = "background:#b3e2d1;text-align:center"
    colspan="2"Table de vérité de l'inverse
    - style="text-align:center"
    a\bar a
    - style="text-align:center"
    01
    - style="text-align:center"
    10
    align="center" width="17%"
    {class="wikitable" width="150" cellspacing="0" border="1"
    - style = "background:#b3e2d1;text-align:center"
    colspan="3"Table de vérité de la somme
    - style="text-align:center"
    aba + \, b
    - style="text-align:center"
    000
    - style="text-align:center"
    011
    - style="text-align:center"
    101
    - style="text-align:center"
    111
    align="center" width="17%"
    {class="wikitable" width="150" cellspacing="0" border="1"
    - style = "background:#b3e2d1;text-align:center"
    colspan="3"Table de vérité du produit
    - style="text-align:center"
    aba \cdot \, b
    - style="text-align:center"
    000
    - style="text-align:center"
    010
    - style="text-align:center"
    100
    - style="text-align:center"
    111

    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

    {align="right" class="wikitable" width="150" cellspacing="0" border="1"
    - style = "background:#b3e2d1;text-align:center"
    colspan="3"Table de vérité de XOR
    - style="text-align:center"
    width="40"awidth="40"bwidth="70"a \oplus b
    - style="text-align:center"
    000
    - style="text-align:center"
    011
    - style="text-align:center"
    101
    - style="text-align:center"
    110
    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 ».
    ; a XOR b
    a\ \operatorname{XOR\ b = a \oplus b = (a+b).\overline{(a.b) = a\bar{b+\bar{ab
    On peut également le définir avec un modulo sur une somme ordinaire :
    a\ \operatorname{XOR\ b = (a+b)\ \bmod\ 2
    Le « ou exclusif » est parfois noté par le signe arithmétique \ne (différent de). Fonctionnellement, on utilise aussi un + entouré :a\oplus b.
    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 :

    Équivalence

    {align="right" class="wikitable" width="150" cellspacing="0" border="1"
    - style = "background:#b3e2d1;text-align:center"
    colspan="3"Table de vérité de EQV
    - style="text-align:center"
    width="40"awidth="40"bwidth="70"a \Leftrightarrow b
    - style="text-align:center"
    001
    - style="text-align:center"
    010
    - style="text-align:center"
    100
    - style="text-align:center"
    111
    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 peut s'écrire
    a\ \operatorname{EQV\ b = a \odot b = \overline{a \oplus b = \overline{a \overline{b + \overline{a b = (ab) + (\overline{a \cdot \overline{b)
    L'équivalence est souvent notée par le signe \Leftrightarrow.
    Elle peut aussi être notée « == » dans certains langages (C, C++, PHP…) et « ⊙ » en électronique.

    Implication

    {align="right" class="wikitable" width="150" cellspacing="0" border="1"
    - style = "background:#b3e2d1;text-align:center"
    colspan="3"Table de vérité de IMP
    - style="text-align:center"
    width="40"
    awidth="40"bwidth="70"a \Rightarrow b
    - style="text-align:center"
    001
    - style="text-align:center"
    011
    - style="text-align:center"
    100
    - style="text-align:center"
    111
    ;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

    Inhibition

    {align="right" class="wikitable" width="150" cellspacing="0" border="1"
    - style = "background:#b3e2d1;text-align:center"
    colspan="3"Table de vérité de INH
    - style="text-align:center"
    width="40"awidth="40"bwidth="70"a.\overline{b
    - style="text-align:center"
    000
    - style="text-align:center"
    010
    - style="text-align:center"
    101
    - style="text-align:center"
    110
    ;L inhibition (notée INH) se compose comme suit :
    a\ \operatorname{INH\ b = a.\overline{b
    Si a est VRAI, l'expression vaut VRAI, SAUF si b est VRAI.
    Cette opération n'est pas commutative.

    Exemple de fonctions logiques à trois ou quatre variables


    Fonction logique à trois variables

    {class="wikitable" align ="right"
    - style = "background:#b3e2d1;text-align:center"
    colspan="43"Table de vérité de décrocher
    - style="text-align:center"
    width="35"awidth="35"bwidth="35"cwidth="70"d
    - style="text-align:center"
    0000
    - style="text-align:center"
    0011
    - style="text-align:center"
    0100
    - style="text-align:center"
    0111
    - style="text-align:center"
    1000
    - style="text-align:center;;color:red"
    1011
    - style="text-align:center"
    1101
    - style="text-align:center"
    1111
    L'égalité
    {{RetraitDé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 :
    • a = "Sonnerie"
    • b = "Décision de répondre"
    • c = "Décision d'appeler"
    la variable d = "Décrocher" est fonction logique des 3 précédentes et peut s'écrire
    {{retraitd a.b + c
    La table de vérité de cette fonction d est alors la suivante (à droite) :
    {align="right" class="wikitable" cellspacing="0" border="1"
    - style = "background:#b3e2d1;text-align:center"
    colspan="43"Table de vérité de décrocher2
    - style="text-align:center"
    width="35"awidth="35"bwidth="35"cwidth="70"d2
    - style="text-align:center"
    0000
    - style="text-align:center"
    0011
    - style="text-align:center"
    0100
    - style="text-align:center"
    0111
    - style="text-align:center"
    1000
    - style="text-align:center;color:red"
    1010
    - style="text-align:center"
    1101
    - style="text-align:center"
    1111
    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 d2 =\bar a.c + a.b.

    Fonction logique à quatre variables

    Un bon élève s'interroge s'il est sage de sortir un soir. Il doit décider en fonction de quatre variables :
    • a = il a assez d'argent
    • b = il a fini ses devoirs
    • c = le transport en commun est en grève
    • d = l'automobile de son père est disponible
    Cet élève pourra sortir si :
    • il a assez d'argent, a = vrai
    • il a fini ses devoirs, donc b = vrai
    • le transport en commun n'est pas en grève, donc c = faux
    • ou si l'automobile de son père est disponible, donc d = vrai
    L'expression logique de sortir en fonction de l'état des variables a, b, c et d peut donc s'écrire ainsi :{{RetraitSortir a.b.({\bar c+d)

    Factorisation d'une expression

    Une fonction logique peut être déterminée
    • soit sous forme d'une expression faisant intervenir les 3 opérations (+\,, \cdot\,, \bar{\,)
    • soit sous forme de sa table de vérité. Dans ce cas il sera toujours possible d'effectuer un développement pour écrire cette fonction comme une somme de produits.
    Exemple: Dans l'exemple de "Décrocher2", la lecture de la table montre que d2 égale 1 quand (a, b, c) = (0, 0, 1) ou (0, 1, 1) ou (1, 1, 0) ou (1, 1, 1).
    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 \bar a.c et factorisation des deux derniers termes par a.b \,

    Arbre d'expression

    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 S(x, y, z) = « si x alors y sinon z », qui ramène une question x à 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 f = S(q, f(q=1), f(q=0)), qui ramène à deux expressions indépendantes de q.
    Soit f = a.b+a.d.f+c.d+e.f ; on peut écrire f= S(a, f(a=1), f(a=0))= S(a, b+c.d+d.f+e.f, c.d+e.f)= S(a, S(b,1,d.f+c.d+e.f), S(c,d+e.f, e.f))\dots
    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.

    Notes et références


    Annexes


    Bibliographie

    • .
    • .
    • .

    Articles connexes

    • Fonction logique
    • Table de Karnaugh
    • Calcul des propositions
    • Système de numération
    • Électronique numérique
    • Neurone formel
    • George Boole
    • Opération bit à bit
    • Théorème du consensus
    • Liste de sujets relatifs à l'algèbre de Boole
    • Table de vérité

    Boole (logique)
    Catégorie:Fonction logique
     
    commentaires

    Il n'y a pas encore de commentaires

    vu pour la dernière fois
    Most vists