Calcul Booléen
\(\def\then{\Rightarrow}\def\lf{\leftarrow}\def\rg{\rightarrow}\def\iff{\Leftrightarrow}\def\rel#1{\,{\mathscr #1}\,}\def\N{{\mathbb N}}\def\Z{{\mathbb Z}}\def\Q{{\mathbb Q}}\def\R{{\mathbb R}}\def\B{{\mathscr B}}\)

Introduction

Nous avons vu au chapitre précédent comment l'on pouvait faire de la logique propositionnelle de ma­niè­re calculatoire sans se préoccuper de l'interprétation de ces calculs, à la manière du calcul en ari­thmé­ti­que. Il ne reste plus qu'un pas à franchir pour achever cette métamorphose en calcul al­gé­bri­que, et c'est le mathématicien britannique George Boole qui l'a réalisée à l'aube du 20-ème siècle. Boole a noté des si­mi­li­tu­des entre le calcul algébrique sur les nombres comme l'addition et la multiplication, et le calcul en logique pro­po­si­tion­nelle avec la disjonction et la conjonction de valeurs de vérité et a fait le pont entre ces deux visions. Il a en quelque sorte algébrisé la logique.

Les applications de l'al­gè­bre qui porte aujourd'hui son nom sont innombrables et centrales en in­for­ma­ti­que, en automatique et en électronique. Les circuits qui constituent un ordinateur s'appuient sur des circuits logiques qui font exclusivement du calcul booléen à partir de portes logiques. C'est le mathématicien Claude Shannon qui a été l'un des premiers à appliquer l'algèbre de Boole à la conception des circuits. Les calculs réalisés par les circuits logiques sont la matérialisation des calculs abstraits réalisés en algèbre de Boole.

Algèbre de Boole

En logique propositionnelle nous avons étudié plusieurs opérateurs logique dont la négation, la dis­jonc­tion et la conjonction, notés res­pec­ti­ve­ment \(\neg a\), \(a\vee b\) et \(a\wedge b\). La conjonction et la disjonction logiques sont des lois de compositions internes*(*) Nous étudierons les lois de composition au chapitre prochain. sur l'ensemble \(\{vrai,\,faux\}\), c'est-à-dire que le résultat d'une conjonction ou d'une disjonction est toujours un élément de l'ensemble \(\{vrai,\,faux\}\). Nous avions interprété les symboles \(\top\) et \(\perp\) en vrai et faux respectivement, cette fois nous allons coder la valeur logique vrai (resp. faux) par le nombre entier 1 (resp. 0) et transposer la disjonction et la conjonction en addition et en multiplication.

On munit alors l'ensemble \(\B:=\{0,1\}\) d'une structure algébrique particulière appelée algèbre de Boole. Les valeurs \(0\) et \(1\) sont qualifiées de bits, contraction des deux mots américains binary et digits, ou de logons en français. On traduit les tables de vérité des opérateurs logiques de disjonction et de conjonction res­pec­ti­ve­ment en tables d'addition et de multiplication :

+01
001
111
add. \((\vee)\)
×01
000
101
prod. \((\wedge)\)
Tables d'addition et de multiplication.

Pour simplifier l'écriture des expressions logiques, l'opérateur de négation \(\neg\) peut-être noté différemment lui aussi, et on écrit \(\overline{x}\) au lieu de \(\neg x\). Et on a

\(x\)01
\(\overline{x}\)10
nég. \((\neg)\)
Table de la négation.
Soit \(x\in\B\) une variable booléenne. On appelle littéral positif la variable \(x\) et littéral négatif sa négation \(\overline{x}\).

Ces trois opérateurs fonctionnent de manière analogue à ce que leur notation algébrique suggère en héritant essentiellement des mêmes propriétés que s'il s'agissait du calcul dans \(\Z\). La loi mul­ti­pli­ca­ti­ve est ainsi souvent notée \(\cdot\) et on omet parfois de l'écrire dans les ex­pres­sions al­gé­bri­ques quand il n'y aucune ambiguité, \(x(y+z)\) au lieu de \(x\cdot(y+z)\) ou \(x\times(y+z)\). On dispose d'autre part des nom­breu­ses propriétés suivantes :

  1. Associativité : \( (a+b)+c=a+(b+c)=a+b+c\quad\text{et}\quad (a b) c=a(b c)=a b c. \)
  2. Commutativité : \( a+b=b+a\quad\text{et}\quad ab=ba. \)
  3. Distributivité : \( a(b+c)=ab+ac\quad\text{et}\quad a+(bc)=(a+b)(a+c). \)
  4. Idempotence : \( a+a+\cdots+a=a\quad\text{et}\quad aa\cdots a = a. \)
  5. Élément neutre : \( a+0=0+a=a\quad\text{et}\quad a1=1a=a. \)
  6. Absorption : \( 0a=0\quad\text{et}\quad 1+a=1. \)
  7. Simplification : \( a+\overline{a}b=a+b\quad\text{et}\quad a(\overline{a}+b)=ab. \)
  8. Redondance : \( ab+\overline{a}c=ab+\overline{a}c+bc. \)
  9. De Morgan : \( \overline{a+b} = \overline{a}.\overline{b}\quad\text{et}\quad \overline{a.b} = \overline{a}+\overline{b}. \)
  10. Involution : \( \bar{\bar{a}}=a. \)
  11. Tiers-exclus : \( a+\overline{a}=1. \)
  12. Non-contradiction : \( a\overline{a}=0. \)

Le principe de dualité permet de déduire les propriétés de l'addition des propriétés de la mul­ti­pli­ca­tion et réciproquement, il suffit d'échan­ger le rôle des opérateurs \(+\) et \(\times\) et celui des valeurs \(0\) et \(1\). Par exemple \(a\cdot 1=1\cdot a=a\) est la propriété duale de \(a+0=0+a=a\). Les lois de De Morgan sont deux lois duales.

On retrouve les cinq autres opérateurs binaires, d'implication, d'équi­va­len­ce, de dis­jonc­tion ex­clu­si­ve, de non conjonction et de non disjonction construits à partir des trois opérateurs de base et à l'aide des équivalences logiques suivantes :

\begin{align} \label{equiv:then} a\Rightarrow b&\equiv \overline{a}+b,\\ \label{equiv:iff} a\Leftrightarrow b&\equiv (\overline{a}+b)\,(a+\overline{b}),\\ \label{equiv:oplus} a\oplus b&\equiv (a+b)\, \overline{(a\, b)},\\ \label{equiv:negand} a\uparrow b&\equiv \overline{ab},\\ \label{equiv:negor} a\downarrow b&\equiv \overline{a+b}. \end{align}

Et on en tire les tables de calcul (attention, ces opérateurs ne sont pas tous commutatifs, les valeurs sur la colonne à l'extrême gauche sont à gauche de chaque opérateur binaire, les valeurs sur la ligne supérieure sont à droite) :

01
011
101
imp. \(\Rightarrow\)
01
010
101
équiv. \(\Leftrightarrow\)
01
001
110
ou ex. \(\oplus\)
01
010
100
non et \(\uparrow\)
01
011
110
non ou \(\downarrow\)
Tables de calcul des autres opérateurs.

La lecture de ces tables est instructive sans même faire de calcul à proprement parler. La négation des valeurs dans la table de calcul de l'équivalence fournit manifestement la table de calcul du ou exclusif, soit

\begin{equation} \label{eq:oplusiff} \neg(a\iff b)\equiv a\oplus b. \end{equation}

Nous allons le démontrer \((\ref{eq:oplusiff})\) à l'aide du calcul booléen. D'après \((\ref{equiv:iff})\) et \((\ref{equiv:oplus})\) il faut donc démontrer que

\[ \overline{(\overline{a}+b)(a+\overline{b})}=(a+b)\overline{(ab)}. \]

Notons qu'il s'agit cette fois d'un égalité et plus d'une équivalence logique puisqu'on calcule dans l'en­sem­ble \(\{0,1\}\). Nous indiquons à droite la propriété qui est appliquée : \begin{align*} \overline{(\overline{a}+ b)} + \overline{(\overline{b}+ a)} &=(a\, \overline{b}) + (b\, \overline{a})&&\text{(De Morgan)}\\ &=\big((a\, \overline{b}) + b\big)\, \big((a\, \overline{b}) + \overline{a}\big)&&\text{(distributivité)}\\ &=\big((a+ b)\,({\color{#88F}\overline{b}+ b})\big)\, \big(({\color{#88F}a+\overline{a}}) \, (\overline{b}+\overline{a})\big)&&\text{(distributivité)}\\ &=\big((a+ b)\, {\color{#88F}1}\big)\, \big({\color{#88F}1}\, (\overline{b}+\overline{a})\big)&&\text{(tiers exclus)}\\ &=(a+b)\, (\overline{b}+\overline{a})&&\text{(élément neutre)}\\ &=(a+b)\, \overline{(ab)}&&\text{(De Morgan)}. \end{align*}

L'algèbre de Boole se contente des opérateurs de négation, de conjonction et de disjonction puisqu'ils suffisent à décrire tous les opérateurs binaires possibles. L'exercice ci-dessous a pour objectif de montrer que l'on peut décrire tous les opérateurs unaire et binaires avec un unique opérateur ce qui permet de construire des circuits électroniques complexes avec un seul type de circuit de base.

Démontrez que l'opérateur non et est un opérateur universel, c'est-à-dire que l'on peut définir les trois opérateurs non, ou et et par des combinaisons de cet opérateur. Indication : on a \(\overline{a}=a\uparrow a\). Montrez que l'opérateur non ou est lui aussi universel.
On le fait pour non et, charge au lecteur de s'en inspirer pour non ou. Il suffit de vérifier les égalités logiques suivantes : \begin{align*} \overline{a} &= \overline{a\,a}=a\uparrow a\\ a\,b &= \overline{\overline{a\,b}} = \overline{a\,b}\uparrow\overline{a\,b} = (a\uparrow b)\uparrow(a\uparrow b)\\ a+b &= \overline{\overline{a}\,\overline{b}} = (a\uparrow a)\uparrow(b\uparrow b) \end{align*}
Démontrez la propriété de redondance (et sa duale) i.e. \(\forall a,b,x\in B\), \[ax + \overline{a}y = ax + \overline{a}y + xy.\] Montrez la propriété de simplification, i.e. \(\forall a,b\in B\), \[a+\overline{a}\, b = a+b.\]
Pour conclure cette section, il faut remarquer les similitudes entre les propriétés des opérateurs de l'algèbre de Boole et les opérations ensemblistes. Soient \(A\) et \(B\) deux parties d'un ensemble \(X\). On utilise ici la notation \(\overline{A}\) pour désigner \(X\setminus A\), le complémentaire de \(A\) dans \(X\). Dans les propriétés des opérateurs logiques, si on remplace les variables booléennes \(a\) et \(b\) par les ensembles \(A\) et \(B\) respectivement, l'addition par la réunion et la multiplication par l'intersection, on obtient :
  1. Associativité : \( (A\cup B)\cup C=A\cup(B\cup C)\ \ \text{et}\ \ (A\cap B)\cap C=A\cap(B\cap C). \)
  2. Commutativité : \( A\cup B=B\cup A\ \ \text{et}\ \ A\cap B=B\cup A. \)
  3. Distributivité : \( A\cap(B\cup C)=(A\cap B)\cup(A\cap C)\ \ \text{et} \)
    \(A\cup(B\cap C)=(A\cup B)\cap (A\cup C).\)
  4. Idempotence : \( A\cup A\cup\cdots\cup A=A\ \ \text{et}\ \ A\cap A\cap\cdots\cap A = A. \)
  5. Élément neutre : \( A\cup\varnothing =\varnothing\cup A=A\ \ \text{et}\ \ A\cap X=X\cap A=A. \)
  6. Absorption : \( \varnothing\cap A=\varnothing\ \ \text{et}\ \ X\cup A=X. \)
  7. De Morgan : \( \overline{A\cup B} = \overline{A}.\overline{B}\ \ \text{et}\ \ \overline{A\cap B} = \overline{A}\cup \overline{B}. \)
  8. Involution : \( \bar{\bar{A}}=A. \)
  9. Tiers-exclus : \( A\cup\overline{A}=X. \)
  10. Non-contr. : \( A\cap\overline{A}=\varnothing. \)
Autrement dit, la logique propositionnelle, l'algèbre de Boole et les opérations en­sem­blis­tes sont différents formalismes pour décrire la même chose.

Fonctions booléennes

Définition

Les fonctions booléennes sont utilisées non seulement dans la modélisation des circuits logiques mais également en théorie de la complexité, en théorie de l'information et en particulier en codage et en cryp­to­gra­phie.

Soit \(n\in\N^*\) et \(\B:=\{0,1\}\). Toute application \(f:\B^n\rg \B\) est appelée fonction booléenne ou fonction logique.

Les fonctions logiques sont intimement liées aux interprétations des formules de la logique pro­po­si­tion­nel­le. Toute formule construite à partir de \(n\) variables pro­po­si­tion­nel­les se traduit par une fonc­tion logique \(f\) de \(n\) variables booléennes \((x_1,x_2,\ldots,x_n)\in\B^n\). À chaque interprétation des variables pro­po­si­tion­nel­le correspond une valeur de la fonction en le \(n\)-uplet correspondant. La table de vérité caractérise donc la fonction et réciproquement les différentes valeurs d'une fonction booléenne fournit la table de vérité de la formule cor­res­pon­dan­te de la lo­gi­que pro­po­si­tion­nel­le.

Considérons par exemple la formule \(P\wedge(Q\vee R)\). La fonction booléenne associée est définie par \begin{equation} \label{eq:foncbool} f(x_1,x_2,x_3):=x_1(x_2+x_3). \end{equation} en associant \(P\) (resp. \(Q\), \(R\)) à \(x_1\) (resp. \(x_2\), \(x_3\)). L'interprétation \(I(P)=V\), \(I(Q)=F\) et \(I(R)=F\) est associée au triplet \((1,0,0)\). L'évaluation de cette fonction en les \(2^3=8\) valeurs possibles des triplets \(x_1,x_2,x_3\) de \(B^3\) permet donc de construire la table de vérité de la formule \(P\wedge(Q\vee R)\).

La fonction logique associée à une tautologie (resp. antilogie) est la fonction constante égale à 1 (resp. 0)
Définissez les fonctions logiques correspondant à chaque opérateur logique.
Soit \(n\in\N^*\) et \(x_1,x_2,\ldots,x_n\) des variables booléennes. Démontrez les lois de De Morgan généralisées : \begin{align*} \overline{(x_1+x_2+\cdots+x_n)}&=\overline{x_1}\,\overline{x_2}\,\cdots\,\overline{x_n},\\ \overline{(x_1\,x_2\,\cdots\,x_n)}&=\overline{x_1}+\overline{x_2}+\cdots+\overline{x_n}. \end{align*}
Soit \(f:\B^n\rg\B\) une fonction booléenne de \(n\) variables. On appelle fonction duale la fonction notée \(f^*\) et définie par \begin{equation} f^*(x_1,x_2,\ldots,x_n):=\overline{f(\overline{x_1},\overline{x_2},\ldots,\overline{x_n})}. \end{equation}

C'est bien sûr une involution, \((f^*)^*=f\). La duale de la fonction constante égale à 1 est la fonction constante égale à 0. La duale de la fonction somme \(x+y\) est la fonction produit \(x\cdot y\) et la fonction duale du ou exclusif est l'équivalence logique. C'est une autre façon d'exprimer le principe de dualité.

Formes normales canoniques

Il est évident que l'on peut décrire une même fonction avec différentes expressions puisque n'importe quelle équivalence logique entre deux formules de la logique propositionnelle fournit deux ex­pres­sions de la même fonction.

Une formule propositionnelle (ou une fonction logique) est dite sous for­me nor­ma­le disjonctive (resp. forme nor­male con­jonc­ti­ve) si et seulement si elle est une disjonction (resp. conjonction) de conjonctions (resp. disjonction) de variables logiques ou leur négation (ou de littéraux pour les fonctions booléennes).

La formule \((P\vee\neg Q)\;{\color{#88F}\wedge}\;R\;{\color{#88F}\wedge}\;(\neg Q\vee\neg R\vee S)\) et la fonction \((p+\overline{q})\,{\color{#88F}\cdot}\,r\,{\color{#88F}\cdot}\,(\overline{q}+\overline{r}+s)\) sont sous forme nor­male disjonctive. La formule \((P\wedge\neg Q)\;{\color{#FF0}\vee}\;(\neg Q)\;{\color{#FF0}\vee}\;(R\wedge\neg S)\) et la fonction \((p\cdot\overline{q})\;{\color{#FF0}+}\;\overline{q}\;{\color{#FF0}+}\;(r\cdot\overline{s})\) sont sous forme nor­male conjonctive. Parmi toutes les expressions possibles sous forme normale d'une même fonction booléenne \(f\), nous allons nous intéresser à deux formes particulières, appelées formes normales canoniques de \(f\).

Considérons trois variables booléennes \(x\), \(y\) et \(z\) et les huit fonctions booléennes de \(\B^3\to\B\)

\begin{equation} \label{eq:min3} xyz,\ xy\overline{z},\ x\overline{y}z,\ x\overline{y}\overline{z},\ \overline{x}yz,\ \overline{x}y\overline{z},\ \overline{x}\overline{y}z,\ \overline{x}\overline{y}\overline{z}. \end{equation}

Pour chacune de ces 8 conjonctions, il n'existe qu'un seul triplet \((x,y,z)\) parmi les 8 triplets pos­si­bles dont l'image par la fonction vaut 1, les 7 autres valeurs sont nulles :

\(x\)\(y\)\(z\) \(x\;y\;z\)\(x\;y\;\overline{z}\)\(x\;\overline{y}\;z\) \(x\;\overline{y}\;\overline{z}\)\(\overline{x}\;y\;z\)\(\overline{x}\;y\;\overline{z}\) \(\overline{x}\;\overline{y}\;z\)\(\overline{x}\;\overline{y}\;\overline{z}\)
000 100 000 00
001 010 000 00
010 001 000 00
011 000 100 00
100 000 010 00
101 000 001 00
110 000 000 10
111 000 000 01

Par dualité, on étudie les 8 disjonctions obtenues par négation des 8 conjonctions de \((\ref{eq:min3})\) et cette fois l'image de la fonction n'est nulle qu'une seule fois sur les huit triplets possibles :

\(\overline{x}\)\(\overline{y}\)\(\overline{z}\) \(\overline{x}{\!\,{\small+}\,\!}\overline{y}{\!\,{\small+}\,\!}\overline{z}\)\(\overline{x}{\!\,{\small+}\,\!}\overline{y}{\!\,{\small+}\,\!}z\)\(\overline{x}{\!\,{\small+}\,\!}y{\!\,{\small+}\,\!}\overline{z}\) \(\overline{x}{\!\,{\small+}\,\!}y{\!\,{\small+}\,\!}z\)\(x{\!\,{\small+}\,\!}\overline{y}{\!\,{\small+}\,\!}\overline{z}\)\(x{\!\,{\small+}\,\!}\overline{y}{\!\,{\small+}\,\!}z\) \(x{\!\,{\small+}\,\!}y{\!\,{\small+}\,\!}\overline{z}\)\(x{\!\,{\small+}\,\!}y{\!\,{\small+}\,\!}z\)
111 011 111 11
110 101 111 11
101 110 111 11
100 111 011 11
011 111 101 11
010 111 110 11
001 111 111 01
000 111 111 10

Cet exemple motive la définition suivante :

On appelle minterme (resp. maxterme) d'ordre \(n\) toute fonction booléenne de \(n\) variables qui ne prend qu'une seule fois la valeur \(1\) (resp. \(0\)).
Soit \(n\in\N^*\). Une fonction booléenne \(f:\B^n\rg \B\) est un min­terme (resp. max­ter­me) si et seu­le­ment si \begin{align} f(x_1,x_2,\ldots,x_n)&=\widetilde{x}_1\,\widetilde{x}_2\,\ldots\,\widetilde{x}_n,\\ f(x_1,x_2,\ldots,x_n)&=\widetilde{x}_1+\widetilde{x}_2+\cdots+\widetilde{x}_n.\\ \end{align} où \(\widetilde{x}_i\) désigne le littéral \(x_i\) (resp. \(\overline{x_i}\)) ou le littéral \(\overline{x_i}\) (resp. \(x_i\)).
Montrons le pour le minterme, le résultat s'obtient par dualité pour le maxterme. C'est une condition suffisante puisque le seul cas où une conjonction de littéraux n'est pas nulle est celle où tous ses littéraux sont égaux à 1.

Mon­trons qu'elle est né­ces­sai­re. Par définition, si \(f\) est un minterme, alors il existe un unique \(n\)-uplet \(a:=(a_1,a_2,\ldots,a_n)\) tel que \(f(a)=1\). Si \(\widetilde{x}_i\) désigne le littéral \(x_i\) si \(a_i=1\) et \(\overline{x_i}\) si \(a_i=0\), alors la fonction définie par \((x_1,x_2,\ldots,x_n)\mapsto\widetilde{x}_1\widetilde{x}_2\ldots\widetilde{x}_n\) est égale à la fonction \(f\).

Soit \(n\in\N^*\). Il existe \(2^n\) mintermes et \(2^n\) maxtermes d'ordre \(n\).
Chaque minterme est le produit de \(n\) littéraux et chaque littéral est soit positif soit négatif, il y a donc \(2^n\) possibilités.
Toute fonction booléenne de \(n\) variables s'écrit de manière unique comme une somme (resp. produit) de mintermes (resp. maxtermes) à l'ordre près.
On ne le montre que pour les mintermes, on obtient le résultat pour les maxtermes par dualité. Soit \(f\) une fonction booléenne de \(n\) variables. Si \(\widetilde{x}_i\) désigne le littéral \(x_i\) si \(a_i=1\) et \(\overline{x_i}\) si \(a_i=0\), le produit des mintermes \(\widetilde{x}_1\widetilde{x}_2\ldots\widetilde{x}_n\) pour chacun des \(n\)-uplets \(a=(a_1,a_2,\ldots,a_n)\) tel que \(f(a)=1\) est égal à la fonction \(f\). L'unicité de l'écriture est obtenue en remarquant qu'il y a \(2^{2^n}\) produits de mintermes possibles et qu'il y a autant de fonctions booléennes.
L'écriture sous forme de somme (resp. produit) de mintermes (resp. max­ter­mes) d'une fonction booléenne \(f\) est appelée forme normale disjonctive ca­no­ni­que (resp. forme nor­male con­jonc­ti­ve ca­no­ni­que) de \(f\).
Quelles sont les formes normales canoniques conjonctives et disjonctives des fonctions :
  1. \(f(x,y)=\overline{x}+xy\) ?
  2. \(f(x,y,z)=\overline{x}+x(y+\overline{z})\) ?
  3. \(f(x,y)=x\) ?
  4. \(f(x)=1\) ?
Vous pourrez utiliser le programme plus bas pour vérifier vos calculs.

La preuve du deuxième corollaire fournit un algorithme pour trouver l'expression en mintermes ou en maxtermes d'une fonction booléenne, il suffit de collecter respectivement les \(n\)-uplets pour lesquels la fonction vaut 1 et 0 dans sa table de vérité.

Saisissez l'expression de votre fonction booléenne \(f\). Utilisez les lettres de \(a\) à \(z\) com­me variables. L'opérateur produit est omis, l'opérateur somme est codé + et l'opérateur de négation est codé \(!x\) : .

On calcule tout d'abord la table de vérité de la fonction \(f\) :

Table de vérité de la fonction booléenne \(f\).

Puis les deux formes normales canoniques de la fonction \(f\) :

L'algorithme naïf qui permet de déterminer les formes normales ca­no­ni­ques disjonctive et conjonctive d'une fonction booléenne est malheureusement fort peu efficace puisqu'il faut réa­li­ser un nombre exponentiel de calculs. Pour passer d'une forme canonique à une autre pour une fonction \(f\), on utilise le fait que la négation est involutive, i.e. \(\bar{\bar f}=f\) et

\begin{align} \label{eq:d2c}{\small\text{FND}}(f)&=\overline{{\small\text{FNC}}(f)}\\ \label{eq:c2d}{\small\text{FNC}}(f)&=\overline{{\small\text{FND}}(f)} \end{align}
Démontrez les deux propriétés \((\ref{eq:d2c})\) et \((\ref{eq:c2d})\).

Circuits logiques

Portes logiques

Il ne reste plus beaucoup de chemin à parcourir pour passer des écritures abstratires des formules propositionnelles ou des fonctions booléennes à la réalité concrète des circuits électroniques. Sché­ma­ti­que­ment, on peut voir une fonction booléenne \(f\) de \(n\) variables comme une boite avec \(n\) entrées binaires et une sortie binaire. On cherche à réaliser physiquement cette boite noire, à l'aide d'un circuit électronique. Les \(n\) entrées et la sortie de la boite sont cette fois \(n+1\) fils électriques sous tension ou non, la tension re­pré­sen­tant la valeur 1 et l'absence de tension 0.

Pour chaque opération logique, on peut fabriquer à l'aide de transistors un circuit électronique qui la réalise. Un tel circuit est appelé une porte logique. Nous n'en présentons ici que cinq, ce sont les opérateurs de négation de conjonction et de disjonction, de non conjonction et de non-disjonction. Les portes correspondantes sont très souvent symbolisées par

NON ET OU NON ET NON OU
Portes logiques associées à \(\neg\), \(\wedge\), \(\vee\), \(\uparrow\) et \(\downarrow\).

La ou les entrées sont à gauche et la sortie à droite de chaque circuit. On connecte les sorties aux en­trées des différents circuits pour réaliser une fontion booléenne. Considérons par exemple la fonction booléenne de trois variables

\[f(x,y,z)=\bar{x}\,(y+\bar z)+\overline{xz}.\]

Dans un schéma bi-dimensionnel représentant un circuit logique, il est inévitable que les fils se croisent alors qu'ils ne se croisent pas en réalité dans l'espace 3D. Ainsi, par convention deux fils qui se croisent ne sont pas con­nec­tés électriquement. Dans le cas contraire, on le signifie par un disque plein sur la connexion (par exemple juste à côté de \(x\) dans le schéma ci-dessous). Une telle connexion entre trois fils est parfois qualifiée de circuit duplicateur.

Circuit logique de \(f(x,y,z):=\bar{x}\,(y+\bar z)+\overline{xz}.\)
Dessinez les circuits logiques qui réalisent les fonctions booléennes suivantes :
  1. \(f(x,y)=(\bar x+\bar y)x+x\bar y\),
  2. \(f(x,y,z)=z(\bar x+\bar y)x+x\bar z y\),
  3. \(f(x,y,z)=(x+\bar y+z)\bar x\).

De nombreuses questions se posent aux électroniciens qui doivent concevoir ce type de circuit. Par exem­ple comment concevoir un circuit équivalent (au sens logique) qui utilise le moins possible de composants de base ? Comment dessiner un tel circuit afin d'éviter au maximum les croisements sur les pistes ? Peut-on déterminer facilement si un circuit est défectueux ? Comment tester les \(2^n\) entrées possibles d'un circuit à \(n\) entrées en ne changeant qu'une valeur booléenne à chaque fois ? Nous allons nous intéresser à la première et la dernière question.

Code de Gray

Commençons par la dernière. On peut se demander quel est l'intérêt de décrire les \(2^n\) valeurs lo­gi­ques possibles de \(n\) variables booléennes en ne changeant qu'un seul bit  ? Généralement quand on veut décrire l'ensemble des valeurs binaires possibles de \(n\) variables, on utilise la représentation binaire des entiers de \(0\) à \(2^n-1\) et on passe d'un entier à l'entier suivant en additionnant 1. Pour trois variables cela donne la sé­quen­ce :

\begin{align*} 0&=000\\ 1&=001\\ 2&=010\\ 3&=011\\ 4&=100\\ 5&=101\\ 6&=110\\ 7&=111 \end{align*}

Observons combien de fois chaque bit à été modifié. Le bit de poids faible (le chiffre le moins significatif à droite) a été modifié 4 fois, le bit suivant 2 fois et le bit de poids fort (le chiffre le plus significatif à gauche) 1 seule fois.

Soit \(n\in\N^*\). Après avoir étudié le chapitre Combinatoire, démontrez que le nombre de modifications du \(k\)-ème bit (où \(k=0\) désigne le bit de poids faible à droite) de la représentation binaire des \(2^n\) entiers naturels dans l'énumération croissante est égal à \(2^{k-1}\).

Ceci peut poser des problèmes physiques, par exemple dans l'utilisation de compteurs numériques. Quand un compteur doit passer d'une valeur à la suivante et que plusieurs bits sont modifiés, tout problème de synchronisation peut faire que ces bits ne basculent pas simultanément, créant ainsi des valeurs intermédiaires que l'on doit parfois éviter. D'autre part, un changement d'état sur le \(k\)-ème bit se fait électriquement et provoque une usure du circuit correspondant. On comprend bien qu'avec l'énumération classique des \(n\) valeurs logiques, l'usure des \(n\) circuits n'est pas du tout homogène. Com­ment corriger ça ?

\(k\) code binaire code de Gray
0 000 000
1 001 001
2 010 011
3 011 010
4 100 110
5 101 111
6 110 101
7 111 100
Code binaire et code de Gray pour \(n=3\).

Le code de Gray*(*) Frank Gray était un physicien américain qui travaillait aux Bell Labs. fournit une solution à ce problème. La table ci-dessus fournit les \(8\) codes de Gray des entiers de \(0\) à \(7\). On peut constater qu'il s'agit d'une permutation de leurs écritures binaires et que l'on passe du code d'un entier au code de l'entier suivant en ne changeant qu'un seul bit.

Soit \(x=x_{n-1}x_{n-2}\ldots x_2 x_1 x_0\) l'écriture binaire d'un entier naturel. On appelle co­de de Gray de \(x\) la séquence binaire \begin{equation} \begin{matrix} &\color{#88F}x_{n-1}&\color{#88F}x_{n-2}&\color{#88F}x_{n-3}&\cdots &\color{#88F}x_2 &\color{#88F} x_1 & x_0\\ \oplus & 0 &\color{#88F}x_{n-1}&\color{#88F}x_{n-2}&\cdots &\color{#88F}x_3 &\color{#88F} \color{#88F}x_2 &\color{#88F} x_1 \end{matrix} \end{equation} Soit \(n\in\N\). La suite des codes de Gray des entiers de l'intervalle \([0,2^n-1]\) est appelé code de Gray de dimension \(n\).

Par exemple le code de Gray de l'entier \(13\) dont la représentation est \(1101\) en base \(2\) s'obtient avec

\begin{align*} &\ {\color{#88F}1}\,{\color{#88F}1}\,{\color{#88F}0}\,1\\ \oplus&\ 0\,{\color{#88F}1}\,{\color{#88F}1}\,{\color{#88F}0}\\ =&\ 1\,0\,1\,1 \end{align*}
On appelle poids binaire d'un entier \(n\) le nombre de chiffres non-nuls de sa re­pré­sen­ta­tion binaire, on le note \(p_2(n)\).

À partir du code de Gray d'un entier, on obtient le code de Gray de l'entier suivant en appliquant la règle suivante : si le poids du code de Gray est pair alors on inverse le bit de poids faible, sinon on inverse le bit à gauche du 1 le plus à droite. Cette procédure permet de construire le code de Gray en dimension \(n\) en partant de 0 et en répétant \(2^n-1\) fois cette règle.

Soit \(n\in\N\) et \(k\in[0,2^n-1[\). Les codes de Gray des entiers \(k\) et \(k+1\) ne dif­fè­rent que d'un seul bit.
Il est facile de vérifier que deux séquences binaires \(x\) et \(y\) de même longueur diffèrent d'un seul bit si et seulement si \(p_2(x\oplus y)=1\). Il suffit donc de vérifier que \(p_2(g(k)\oplus g(k+1))=1\) si \(g(x)\) désigne le code de Gray de \(x\). Si l'on note \(s(x)\) le décalage d'une position à droite de la séquence binaire \(x\), alors on a \begin{align*} {\color{#88F}g(k)}\oplus{\color{#FF4}g(k+1)} &= \big({\color{#88F}k\oplus s(k)}\big)\oplus\big({\color{#FF4}(k+1)\oplus s(k+1)}\big)\\ &= \big({\color{#88F}k}\oplus({\color{#FF4}k+1})\big)\oplus \big({\color{#88F}s(k)}\oplus {\color{#FF4}s(k+1)}\big)\quad\text{car}\ \oplus\ \text{est associatif et commutatif.} \end{align*} Mais \(s(x)\oplus s(y)=s(x\oplus y)\), donc \begin{align*} g(k)\oplus g(k+1) &=\big(k\oplus (k+1)\big)\oplus\big(s(k\oplus (k+1))\big)\\ &=g(k\oplus (k+1)). \end{align*} Mais additionner \(1\) à une séquence binaire \(k\) inverse tous ses bits à partir du \(0\) le plus à droite inclus (par propagation de la retenue), les autres bits à gauche restes inchangés (pour fixer les idées : \(101{\color{#88F}011}+1=101{\color{#88F}100}\)). Autrement dit \(k\oplus(k+1)\) est une séquence de \(0\) suivie d'une séquence de \(1\) (\(101{\color{#88F}011}\oplus 101{\color{#88F}100}=000{\color{#88F}111}\)). Entre cette séquence et cette même sé­quen­ce décalée d'une position vers la droite, il n'y a donc qu'un seul bit qui diffère, donc \(p_2\big(g(k\oplus (k+1))\big)=1\).
Un disque est constitué de 4 anneaux concentriques. Ce disque est découpé à la manière d'une orange en \(16\) portions de \(4\) segments coloriés en noir et blanc selon la figure ci-dessous :
Schéma d'un encodeur rotatif optique.
Ce disque est en rotation autour de son axe et quatre cellules optiques fixes sont placées à intervalle régulier sur un quartier du disque de manière à mesurer la lumière réfléchie par chaque portion des 4 anneaux. Quand la portion est blanche, la lumière réfléchie crée un courant électrique qui est interprété comme 1. Quand la portion est noire, le courant induit est nul ou très faible et interprété comme 0. Ce dispositif permet donc de coder 16 directions différentes avec uniquement \(4\) cellules. Mais pourquoi un code de Gray de dimension 4 plutôt qu'un codage binaire ?

L'avantage d'un code de Gray par rapport au code binaire est déterminant. Il y a évidemment une tolérance sur l'alignement des cellules et le partitionnement du disque. Imaginons une légère oscillation du disque tel que les 4 cellules hésitent entre deux quartiers adjacents. Avec un code de Gray, une seule cellule peut changer de valeur, ces oscillations vont se traduire par le code de deux directions adjacentes et proches de la réalité, alors qu'avec un code binaire classique, il est tout à fait possible que certaines cellules soient au-dessus d'un quartier et les autres au-dessus d'un autre quartier indiquant alors deux directions qui, non seulement ne sont pas adjacentes, mais qui peuvent également être très différentes de la réalité.

Notons que si l'on veut plus de précision, il suffit d'augmenter la dimension du code de Gray. Pour obtenir une boussole avec une précision de l'ordre du degré, il suffit d'un jeu de 9 cellules. On peut évidemment réaliser un tel disque avec un mécanisme moins évolué que des cellules optiques, par exemple à l'aide de simples contacteurs en creusant une gorge sous les anneaux dans les portions noires (ou réciproquement selon le type de contacteurs).

Tables de Karnaugh

Nous allons nous intéresser à la première question. Afin d’utiliser un nombre minimum de portes logiques pour réaliser une fonction booléenne \(f\), il faut qu’elle comporte le moins de variables et le moins d’opérateurs possibles. Le travail se fait en amont du circuit en cherchant une décomposition de \(f\) la plus simple possible. Pour cela on utilise les tables de Karnaugh*(*) Maurice Karnaugh est un mathémati­cien amé­ricain qui a dé­ve­lop­pé cette tech­ni­que en 1954 aux Bell Labs.. Une table de Karnaugh est une autre façon de représenter la table de vérité, elle permet plus facilement de visualiser la forme d'une fonction mais n'est efficace que pour un nombre très restreint de variables (pas plus de quatre généralement).

Les tables de Karnaugh vont nous permettre :

  1. de trouver la forme normale conjonctive et la forme normale disjonctive d’une fonction booléenne,
  2. de trouver une expression simplifiée de la fonction booléenne avec le minimum de variables et d’opérateurs.

Les variables sont partitionnées en deux groupes de même taille. Si le nombre de variables est impair, un groupe en contient une de plus. Les différentes valeurs possibles des variables du premier groupe indexent les lignes de la table, celles du second groupe les colonnes de la table. Seule la valeur \(1\) de la fonction est notée dans la table. Considérons par exemples les trois fonctions boo­léen­nes de 2, 3 et 4 variables suivantes :

  1. \(\phantom{,z,t}f(x,y) := {\color{#FF0}x}\,(\bar{\color{#FF0}x}+y)+\bar{\color{#FF0} x}\),
  2. \(\phantom{,t}f(x,y,z) := {\color{#FF0}x}\,{\color{#88F}y}+\bar z\),
  3. \(f(x,y,z,t) := {\color{#FF0}x}\,{\color{#F44}y}+\bar {\color{#88F}z}(\bar {\color{#FF0}x}+{\color{#F44}y}+t)\).

Les tables de Karnaugh de ces trois fonctions booléennes sont :

\(y\)
\({\color{#FF0}x}\)
0 1
0 1 1
1 1
\({\color{#88F}y}\,z\)
\({\color{#FF0}x}\)
00 01 11 10
0 1 1
1 1 11
\({\color{#88F}z}\,t\)
\({\color{#FF0}x}\,{\color{#F44}y}\)
00 01 11 10
00 11
01 11
11 11 11
10 1
Tables de Karnaugh de fonctions de 2, 3 et 4 variables. À gauche la fonction

La méthode pour retrouver la forme normale disjonctive ou conjonctive canonique est la même que pour les tables de vérités, il suffit de lire les 1 ou les cases vides et de rajouter le minterme ou le maxterme correspondant. Ainsi pour la fonction de trois variables de l'exemple ci-dessus, on ob­tient la forme normale dis­jonc­ti­ve canonique :

\[ f(x,y,z)=\underbrace{\bar x\,\bar y\bar z+\bar x\,y\,\bar z}_{\text{première ligne}}+\underbrace{x\,\bar y \, \bar z+x\,y\,z+x\,y\bar z}_{\text{deuxième ligne}} \]

Ce n'est pas tant pour trouver les formes canoniques que l'on utilise les tables de Karnaugh, on ne gagne rien par rapport à la table de vérité usuelle, mais plutôt pour simplifier les expressions des fonctions booléennes. La base de la simplification repose sur l'iden­ti­té

\begin{equation} \label{eq:suminterms} x\,{\color{#F44}y}+x\,{\color{#F44}\bar y} =x. \end{equation}

Et cette identité est exploitée en rangeant les différentes valeurs possibles des variables logiques sui­vant un code de Gray. Ceci assure qu'entre deux cases adjacentes (y compris la dernière avec la pre­miè­re sur la même ligne ou la même colonne) il n'y a qu'une variable qui change de valeur boo­léen­ne. Ainsi, la somme des deux mintermes correspondants est de la forme \((\ref{eq:suminterms})\) ce qui permet de ne conserver que l'autre littéral dans l'expression. Reprenons la fonction \(f(x,y)=x\,(\bar x+y)+\bar x\). Sa table de Karnaugh et sa forme normale dis­jonc­ti­ve canonique sont

\(y\)
\({\color{#FF0}x}\)
0 1
0 1 1
1 1
\(f(x,y)=\underbrace{\bar x\,\bar y+\bar x\,y}_{\text{ligne 1}}+ \underbrace{x\,y}_{\text{ligne 2}}\)

On observe deux regroupements possibles dans cette table, les deux cases sur la première ligne ou les deux cases sur la dernière colonne :

\begin{align*} \boxed{\bar x\,\bar {\color{#F44}y}+\bar x\, {\color{#F44}y}} +x\,y\quad\text{ou}\quad\bar x\,\bar y+\boxed{\bar{\color{#F44}x}\, y +{\color{#F44}x}\,y} \end{align*}

Mais la propriété d'idempotence \({\color{#FF0}a}={\color{#FF0}a+a}\) nous permet d'exploiter les deux regroupements

\begin{align*} f(x,y)&= \bar x\,\bar y+{\color{#FF0}\bar x\, y} +x\,y\\ &=\underbrace{\bar x\,\bar y + {\color{#FF0}\bar x\, y}}_{\displaystyle \bar x}+ \underbrace{{\color{#FF0}\bar x\, y}+x\,y}_{\displaystyle y}\\ \end{align*}

Et on obtient finalement la simplification \(f(x,y)=\bar x+y\).

On considère la fonction boolénne \(f\) de 4 variables \(x,y,z\) et \(t\) dont la table de Karnaugh est la suivante :
\({\color{#88F}z}\,t\)
\({\color{#FF0}x}\,{\color{#F44}y}\)
00 01 11 10
00 11
11 11 1
11 1
10 1 1

Donnez la forme normale disjonctive canonique de la fonction \(f\) et simplifiez son expression. Dessinez le circuit logique correspondant.

On dispose d'un disque rotatif codant 8 directions, Nord, Nord-Ouest, Ouest, Sud-Ouest, Sud, Sud-Est, Est, Nord-Est à l'aide d'un code de Gray de dimension 3. Par convention on suppose que le triplet nul \((0,0,0)\) code le Nord. Soit \(f\) la fonction booléenne à trois variables \(x,y\) et \(z\) qui vaut \(1\) quand la direction est le Nord ou le Sud-Est. Construisez la table de Karnaugh de cette fonction et écrivez la forme normale disjonctive canonique de cette fonction. Simplifiez la fonction et élaborez un circuit logique pour la boussole qui allume une diode si la direction est le Nord ou le Sud-Est.