Voir la source de Algèbre de Boole (logique)

{{Sources à lier|date=février 2021}} 

{{Voir homonymes|Algèbre de Boole}}
L{{'}}'''algèbre de Boole''', ou calcul booléen, est la partie des [[mathématiques]] qui s'intéresse à une approche [[Algèbre|algébrique]] de la [[logique]], vue en termes de [[Variable (mathématiques)|variables]], d'[[Opérateur (mathématiques)|opérateurs]] et de [[Fonction (mathématiques)|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]] [[Britanniques|britannique]] [[George Boole]]. L'algèbre de Boole trouve de nombreuses applications en [[informatique]] et dans la [[Conception de circuits intégrés|conception]] des [[circuits électroniques]].

Elle fut utilisée la première fois pour les circuits de [[Commutateur téléphonique|commutation téléphonique]] par [[Claude Shannon]].

== Exemple introductif ==
L'algèbre de Boole des [[Fonction logique|fonctions logiques]] permet de modéliser des [[Logique|raisonnements logiques]], en exprimant un « état » en fonction de conditions. Par exemple, si nous étudions l'expression Communication et l'expression Décrocher :
* 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é
* <math>B=\{1,0\}</math>
* <math>B= \{\top , \perp \}</math>.
avec <math>\top</math> pour <math>1</math> et  <math>\perp</math> pour <math>0 </math>.

On privilégiera dans la suite la notation <math>B=\{1,0\}</math>.

Sur cet ensemble on peut définir deux [[loi de composition|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, <math>\{a, b, c\} \subset B</math>

=== Conjonction ===
{{Article connexe|Fonction ET|Conjonction logique}}

{|align="right" class="wikitable" cellspacing="0" border="1"
|- style = "background:#b3e2d1;text-align:center"
|colspan="3"|Table de la loi '''ET''' 
|- style="text-align:center" 
!scope=col width="50"|    a→<br/>b↓||width="50"|'''0'''||width="50"|'''1'''
|- style="text-align:center" 
!scope=row|0
|0||0
|- style="text-align:center"
!scope=row|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 :
*<math>\cdot \,</math> : [[Opérateur point]] ;
*<math>\wedge</math> ;
* « & » ou « && » : cette [[Mise en œuvre|implémentation]] fait partie de plusieurs [[Langage de programmation|langages de programmation]] tels que [[Perl (langage)|Perl]], [[C (langage)|C]], [[PHP]], [[Swift (langage d'Apple)|Swift]], [[Go (langage)|Golang]]. ; 
* « and » ou « ''AND'' » : la plupart des langages de programmation, par exemple [[Ada (langage)|Ada]], [[Pascal (langage)|Pascal]], Perl, [[Python (langage)|Python]], [[PHP]] proposent cette fonction ; 
* « ∧ » : utilisée dans plusieurs [[Notation algébrique|notations algébriques]] et en [[APL (langage)|APL]] ; 
* « * » ; le symbole d'une [[multiplication]] ordinaire est utilisée dans quelques langages ne disposant pas de fonction adaptée.

On privilégiera dans la suite la notation « <math>\cdot</math> ».

La table de cette loi (analogue à une [[table d'addition]] ou [[table de multiplication|de multiplication]]) n'est pas  une [[table de vérité]].

=== Disjonction ===

{|align="right" class="wikitable" cellspacing="0" border="1"
|- style = "background:#b3e2d1;text-align:center"
|colspan="3"|Table de la loi '''OU'''
|- style="text-align:center" 
!scope=col width="50"|    a→<br/>b↓||width="50"|'''0'''||width="50"|'''1'''
|- style="text-align:center" 
!scope=row|0
|0||1
|- style="text-align:center"
!scope=row|1
|1||1
|}
{{Article connexe|Fonction OU|Disjonction logique}}
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 :
*<math>+</math>
* « ∨ » (« <math>\vee</math> ») 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 <math>+</math> mais on prendra garde du fait que cette loi n'est pas l'addition usuelle dans [[Anneau ℤ/nℤ|'''Z'''/2'''Z''']]. C'est pourquoi, en mathématiques et en [[logique mathématique]], la notation <math>+</math> n'est pas utilisée pour désigner le « ou inclusif » : elle est réservée au « [[#Disjonction exclusive|ou exclusif]] », opération qui (jointe au « et ») fait de toute [[algèbre de Boole (structure)|algèbre de Boole]] un [[anneau de Boole]], en particulier une '''Z'''/2'''Z'''-[[algèbre sur un corps|algèbre]].

=== Négation ===
{{Article connexe|Fonction NON|Négation logique}}
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
*<math>\bar{a}</math>
*<math>a/</math>
*<math>\neg a</math>
* « ~a » dans quelques notations algébriques, en APL et dans quelques langages d'interrogation de [[base de données|bases de données]] ([[Structured Query Language|SQL]]…) ;
* « ! » dans quelques langages de programmation (C, [[C++]], [[Python (langage)|Python]] ..) ;
* « 1- » dans quelques langages ne disposant pas de fonctions adaptées ([[traitement par lots|Batch]]…) ''(puisque 1-0=1 et 1-1=0).''

On privilégiera dans la suite la notation <math>\bar{a}</math>.

On obtient alors <math>\bar{0}=1</math> et <math>\bar{1}=0</math>.

=== Propriétés ===
==== Propriétés des opérateurs ====
Les opérateurs sont concernés par plusieurs propriétés communes :

* [[associativité]] : <math>( a + b ) + c = a + (b + c) </math> , qui est parfois écrit pour cette raison : <math>a + b + c</math> et <math>( a \cdot b ) \cdot c = a \cdot (b \cdot c)</math>, qui est parfois écrit pour cette raison : <math>a \cdot b \cdot c</math> ;
* [[Loi commutative|commutativité]] : <math>a + b = b + a</math> et <math>a \cdot b = b \cdot a</math> ;
* [[distributivité]]<ref>Respectivement (E4.1) et (E4.2) dans {{Ouvrage|auteur=M. Jaume|et al.=oui|titre=Logique pour l'informatique|éditeur=[[Éditions Ellipses|Ellipses]]|date=2020|url={{Google Livres|nxlEEAAAQBAJ|page=76}}|page=76}}<!--ou exo 3.20 dans ce manuel de BTS https://books.google.fr/books?id=i21AEAAAQBAJ&pg=PA87 voir aussi ce manuel de Première mais avec d'autres notations : https://books.google.fr/books?id=shU5EAAAQBAJ&pg=PA15-->.</ref> : <math>a \cdot ( b + c ) = (a \cdot b) + (a \cdot c)</math> et  <math>a + (b \cdot c)  = (a + b)\cdot (a+c)</math> ;
* [[idempotence]] : <math>a + a = a</math> et <math>a\cdot a=a</math> .

Par ailleurs, chaque opérateur possède un [[élément neutre]] et un [[élément absorbant]] :
* <math>a+0=0+a=a</math> ;
* <math>a+1=1+a=1</math> ;
* <math>a \cdot 1=1 \cdot a=a</math> ;
* <math>a \cdot 0=0 \cdot a=0</math> ;
Des simplifications sont possibles comme :
* <math>a+a\cdot b=a</math> ;
* <math>a\cdot(a+b)=a</math> ;
* <math>a+\overline{a} \cdot b = a+b</math> ;
* <math>a \cdot (\overline{a}+b) = a \cdot b</math>.
le [[théorème du consensus]] s'applique aux opérateurs de l'algèbre de Boole :
* <math>a \cdot b + \overline{a} \cdot c = a \cdot b + \overline{a} \cdot c + b \cdot c </math>.
Enfin, ils suivent le [[principe de complémentarité]] :
* [[Involution (mathématiques)|involution]] : <math>a = \overline{\overline{a}}</math> ({{ex}} 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").
* [[Principe du tiers exclu|tiers exclu]] : <math>a + \overline{a} = 1</math> (la proposition "lumière allumée" OU "lumière non allumée" est toujours VRAI.).
* [[contradiction]] ou antilogie : <math>a \cdot \overline{a} = 0</math> (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 [[algèbre de Boole (structure)|structure d'algèbre de Boole]].

==== Priorité ====
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 :
:<math>1 + b\cdot 0 = 1 + 0 =1</math>
Il reste possible de placer des parenthèses dans les calculs pour changer l'ordre de priorité des opérations.

==== Lois de De Morgan ====
{|width="100%"
|-
|align="center"|
; Première loi de De Morgan (négation de la disjonction)
: s'exprime par l'égalité suivante <math>\overline{ a + b } = \overline{a} \cdot \overline{b}</math>

{|class="wikitable" width="150" cellspacing="0" border="1"
|+ style = "background:#b3e2d1"|Table de vérité/Table de fonctionnement
|- 
!scope=col|a 
!scope=col|b 
!scope=col|<math>a + b </math>
!scope=col|<math>\overline{ a + b } </math> 
!scope=col|<math>\overline{ a }</math>
!scope=col|<math>\overline{ b }</math>
!scope=col|<math>\overline{a} \cdot \overline{b}</math>
|- style="text-align:center"
!scope=row|0 
!scope = row|0
||0||1||1||1||1
|- style="text-align:center"
!scope=row|0 
!scope = row|1
|1||0||1||0||0
|- style="text-align:center"
!scope=row|1 
!scope = row|0
|1||0||0||1||0
|- style="text-align:center"
!scope=row|1 
!scope = row|1
|1||0||0||0||0
|}
Dans les deux cas, l'expression ne sera VRAIE<br />que si ''a'' et ''b'' sont ''fausses''.
|align="center"|
; Deuxième loi de De Morgan (négation de la conjonction)
:<math>\overline{ a \cdot b } = \overline{a} + \overline{b}</math>

{|class="wikitable" width="150" cellspacing="0" border="1"
|+ style = "background:#b3e2d1"|Table de vérité/Table de fonctionnement
|- 
!scope=col|a 
!scope=col|b 
!scope=col|<math>a \cdot b</math> 
!scope=col|<math>\overline{ a \cdot b }</math> 
!scope=col|<math>\overline{ a }</math> 
!scope=col|<math>\overline{ b }</math> 
!scope=col|<math>\overline{a} + \overline{b}</math> 
|- style="text-align:center"
!scope=row|0 
!scope = row|0
|0||1||1||1||1
|- style="text-align:center"
!scope=row|0 
!scope = row|1
|0||1||1||0||1
|- style="text-align:center"
!scope=row|1 
!scope = row|0
|0||1||0||1||1
|- style="text-align:center"
!scope=row|1 
!scope = row|1
|1||0||0||0||0
|}
Dans les deux cas, l'expression ne sera FAUSSE<br />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 ''B<sup>n</sup>'' dans ''B''.

En [[Électronique (technique)|électronique]], une fonction logique est une ''[[Boîte noire (système)|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 logique|disjonction]] (OU) ;
* [[Conjonction logique|conjonction]] (ET) ;
* [[Négation logique|négation]] (NON).

On démontre aussi qu'il existe exactement <math>2^{2^n}</math> fonctions logiques de <math>n</math> 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 <math>n</math> 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 ''B<sup>2</sup>'' 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'''||'''<math>\bar a</math>'''
|- style="text-align:center"
|0||1
|- style="text-align:center"
|1||0
|}
|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"
|'''a'''||'''b'''||'''a <math>+ \,</math> b'''
|- style="text-align:center"
|0||0||0
|- style="text-align:center"
|0||1||1
|- style="text-align:center"
|1||0||1
|- style="text-align:center"
|1||1||1
|}
|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"
|'''a'''||'''b'''||'''a <math>\cdot \,</math> b'''
|- style="text-align:center"
|0||0||0
|- style="text-align:center"
|0||1||0
|- style="text-align:center"
|1||0||0
|- style="text-align:center"
|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 ====

{|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"|'''a'''||width="40"|'''b'''||width="70"|'''a <math>\oplus</math> b'''
|- style="text-align:center"
|0||0||0
|- style="text-align:center"
|0||1||1
|- style="text-align:center"
|1||0||1
|- style="text-align:center"
|1||1||0
|}

{{Article connexe|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 [[Fonction OU exclusif|OU exclusif]] (ou XOR pour ' e'''X'''clusive '''OR'''') s'entend comme : « l'un ou l'autre, ''mais pas'' les deux ».

; a XOR b
:<math>a\ \operatorname{XOR}\ b = a \oplus b = (a+b) \cdot \overline{(a \cdot b)} = a\bar{b}+\bar{a}b</math>

On peut également le définir avec un [[modulo (informatique)|modulo]] sur une [[somme (arithmétique)|somme]] ordinaire :
:<math>a\ \operatorname{XOR}\ b = (a+b)\ \bmod\ 2</math>

Le « ou exclusif » est parfois noté par le signe arithmétique <math>\ne</math> (''différent de''). Fonctionnellement, on utilise aussi un + entouré :<math>a\oplus b</math>.

'''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 :{{Retrait|<math> \bar a = a\oplus\ 1 </math>, et <math>a + b = a \oplus\ b \oplus\ a\cdot b </math>}}

==== É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"|'''a'''||width="40"|'''b'''||width="70"|'''a <math>\Leftrightarrow</math> b'''
|- style="text-align:center"
|0||0||1
|- style="text-align:center"
|0||1||0
|- style="text-align:center"
|1||0||0
|- style="text-align:center"
|1||1||1
|}

L'[[Équivalence logique|é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 
:<math>a\ \operatorname{EQV}\ b = a \odot b = \overline{a \oplus b} = \overline{a \overline{b} + \overline{a} b} = (ab) + (\overline{a} \cdot \overline{b})</math>

L'équivalence est souvent notée par le signe <math>\Leftrightarrow</math>.
Elle peut aussi être notée « == » dans certains langages (C++, PHP…) et « ⊙ » en électronique.
{{Clr}}

==== 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"|'''a'''||width="40"|'''b'''||width="70"|'''a <math>\Rightarrow</math> b'''
|- style="text-align:center"
|0||0||1
|- style="text-align:center"
|0||1||1
|- style="text-align:center"
|1||0||0
|- style="text-align:center"
|1||1||1
|}

{{article détaillé|implication (logique)}}
;L'''implication'' (notée ''IMP'') s'écrit de la manière suivante 
:<math>a\ \operatorname{IMP}\ b = \overline{a}+b</math>

Cette opération n'est pas [[#Propriétés des opérateurs|commutative]]. a est une condition '''suffisante''' pour b, qui, elle, est une condition '''nécessaire''' pour a.

Mais

<math>a\ \operatorname{IMP}\ b = \overline{b}\ \operatorname{IMP}\ \overline{a}</math>

{{exemple|nom=Illustration|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.
}}

==== 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"|'''a'''||width="40"|'''b'''||width="70"|'''<math>a\cdot\overline{b}</math>'''
|- style="text-align:center"
|0||0||0
|- style="text-align:center"
|0||1||0
|- style="text-align:center"
|1||0||1
|- style="text-align:center"
|1||1||0
|}

;L{{'}}''inhibition'' (notée ''INH'') se compose comme suit :
:<math>a\ \operatorname{INH}\ b = a \cdot \overline{b}</math>

Si ''a'' est VRAI, l'expression vaut VRAI, SAUF si b est VRAI.

Cette opération n'est pas commutative.
{{Clr}}
=== 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"|'''a'''||width="35"|'''b'''||width="35"|'''c'''||width="70"|'''d'''
|- style="text-align:center"
|0||0||0||0
|- style="text-align:center"
|0||0||1||1
|- style="text-align:center"
|0||1||0||0
|- style="text-align:center"
|0||1||1||1
|- style="text-align:center"
|1||0||0||0
|- style="text-align:center;;color:red"
|1||0||1||1
|- style="text-align:center"
|1||1||0||1
|- style="text-align:center"
|1||1||1||1
|}

L'égalité
{{Retrait|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 :
* 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
{{retrait|<math>d {{=}} a \cdot b + c</math>}}

La table de vérité de cette fonction d est alors la suivante (à droite) :

{{Clr}}

{|align="right" class="wikitable" cellspacing="0" border="1"
|- style = "background:#b3e2d1;text-align:center"
|colspan="43"|Table de vérité de décrocher 2
|- style="text-align:center"
|width="35"|'''a'''||width="35"|'''b'''||width="35"|'''c'''||width="70"|'''d2'''
|- style="text-align:center"
|0||0||0||0
|- style="text-align:center"
|0||0||1||1
|- style="text-align:center"
|0||1||0||0
|- style="text-align:center"
|0||1||1||1
|- style="text-align:center"
|1||0||0||0
|- style="text-align:center;color:red"
|1||0||1||0
|- style="text-align:center"
|1||1||0||1
|- style="text-align:center"
|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 <math>d2 =\bar a \cdot c + a \cdot b</math>.

==== 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 :{{Retrait|Sortir {{=}}<math> a \cdot b \cdot ({\bar c}+d)</math>}}

=== Factorisation d'une expression ===
Une fonction logique peut être déterminée
* soit sous forme d'une expression faisant intervenir les 3 opérations (<math>+\,</math>, <math>\cdot\,</math>, <math>\bar{}\,</math>)
* 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 [[Forme normale conjonctive|somme de produits]].

Exemple : Dans l'exemple de "Décrocher 2", la lecture de la table montre que <math>d2</math> égale <math>1</math> quand <math>(a, b, c) = (0, 0, 1)</math> ou <math>(0, 1, 1)</math> ou <math>(1, 1, 0)</math> ou <math>(1, 1, 1)</math>.{{Retrait|Cela permet de définir d2 par <math>d2 =\bar a \cdot \bar b \cdot c + \bar a \cdot b \cdot c + a \cdot b \cdot \bar c + a \cdot b \cdot c</math>}}

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 [[table de Karnaugh|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 <math>\bar a \cdot c </math> et factorisation des deux derniers termes par <math> a \cdot b \,</math>{{Retrait|<math>d2 =\bar a \cdot c + a \cdot b</math>}}

== 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 <math>S(x, y, z) =</math> « si <math>x</math> alors <math>y</math> sinon <math>z</math> », qui ramène une question <math>x</math> à 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 <math>f = S(q, f(q=1), f(q=0))</math>, qui ramène à deux expressions indépendantes de <math>q</math>.

Soit <math>f = a \cdot b+a \cdot d \cdot f+c \cdot d+e \cdot f</math> ; on peut écrire <math>f= S(a, f(a=1), f(a=0))= S(a, b+c \cdot d+d \cdot f+e \cdot f, c \cdot d+e \cdot f)= S(a, S(b,1,d \cdot f+c \cdot d+e \cdot f), S(c,d+e \cdot f, e \cdot f))\dots</math> 

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 ==
{{Références}}

== Annexes ==
{{Autres projets
|wikibooks=Électronique numérique : logique
|wikibooks titre=Électronique numérique : logique
|wikiversity=Logique séquentielle
|wikiversity titre=Logique séquentielle
}}
=== Articles connexes ===
{{Loupe|Liste de sujets relatifs à l'algèbre de Boole}}
* [[Opération bit à bit]]
* [[Les lois de la pensée]]
=== Bibliographie ===
* {{Ouvrage|auteur1=J. Kuntzmann|titre=Algèbre de Boole|lieu=Paris|éditeur=[[Éditions Dunod|Dunod]]|année=1968}}
* {{Ouvrage|auteur1=N. Permingeat|titre=Algèbre de Boole : Théorie, méthodes de calcul, applications, avec exercices|lieu=Paris|éditeur=Dunod|année=1988}}
* {{Ouvrage|prénom1=Claude François|nom1=Picard|titre=Théorie des questionnaires|lieu=Paris|éditeur=[[Gauthier-Villars]]|année=1965}}

{{Palette
|Opérations binaires
|Connecteurs logiques
}}
{{Portail|informatique|électricité et électronique|logique|mathématiques}}

[[Catégorie:Algèbre de Boole|*]]