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 appelle booléen toute variable définie sur un ensemble à deux éléments, i.e. qui ne peut prendre que deux valeurs distinctes.

On munit l'ensemble \(\B:=\{0,1\}\) d'une structure algébrique particulière appelée algèbre de Boole. Un élément de l'ensemble \(\B\) est donc un booléen. Les valeurs \(0\) et \(1\) sont souvent qualifiées de bits, contraction des deux mots américains binary et digits et parfois de logons#. (#) unité de logique ou d'information en France. 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é dif­fé­rem­ment 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.

Ces trois opérateurs fonctionnent de manière analogue à ce que leurs notations algébriques suggèrent en héritant essentiellement des mêmes propriétés que s'il s'agissait d'un 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 des identités suivantes :

\begin{align} \label{equiv:then} a\Rightarrow b&= \overline{a}+b,\\ \label{equiv:iff} a\Leftrightarrow b&= (\overline{a}+b)\,(a+\overline{b}),\\ \label{equiv:oplus} a\oplus b&= (a+b)\, \overline{(a\,b)},\\ \label{equiv:negand} a\uparrow b&= \overline{a\,b},\\ \label{equiv:negor} a\downarrow b&= \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
011
110
non et \(\uparrow\)
01
010
100
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)= a\oplus b, \end{equation}

ce que nous allons démontrer à 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)(a+\overline{b})}&= \overline{(\overline{a}+ b)} + \overline{(a+\overline{b})}&&\text{(De Morgan)}\\ &=(a\, \overline{b}) + (\overline{a}\,b)&&\text{(De Morgan)}\\ &=\big((a\, \overline{b}) + \overline{a}\big)\,\big((a\, \overline{b}) + b\big) &&\text{(distributivité)}\\ &=\big(({\color{#88F}a+\overline{a}}) \, (\overline{b}+\overline{a})\big)\,\big((a+ b)\,({\color{#88F}\overline{b}+ b})\big)&&\text{(distributivité)}\\ &=\big({\color{#88F}1}\, (\overline{b}+\overline{a})\big)\,\big((a+ b)\, {\color{#88F}1}\big)&&\text{(tiers exclus)}\\ &=(\overline{b}+\overline{a})\,(a+b)&&\text{(élément neutre)}\\ &=\overline{(ba)}\,(a+b)&&\text{(De Morgan)}\\ &=(a+b)\, \overline{(ab)}&&\text{(Commutativité)} \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 binaire non et, dit d'incompatibilité, noté \(\uparrow\) et défini par \[(A\uparrow B) := \neg (A.B)\] 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 {\mathscr B}\), \[ax + \overline{a}y = ax + \overline{a}y + xy.\] Montrez la propriété de simplification, i.e. \(\forall a,b\in {\mathscr 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. Soit \(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\) res­pec­ti­ve­ment, 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 \({\mathscr 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 conjonctive. 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 dis­jonctive. 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\phantom{{\!\,{\small+}\,\!}}y\phantom{{\!\,{\small+}\,\!}}z\)\(x\phantom{{\!\,{\small+}\,\!}}y\phantom{{\!\,{\small+}\,\!}}\overline{z}\)\(x\phantom{{\!\,{\small+}\,\!}}\overline{y}\phantom{{\!\,{\small+}\,\!}}z\) \(x\phantom{{\!\,{\small+}\,\!}}\overline{y}\phantom{{\!\,{\small+}\,\!}}\overline{z}\)\(\overline{x}\phantom{{\!\,{\small+}\,\!}}y\phantom{{\!\,{\small+}\,\!}}z\)\(\overline{x}\phantom{{\!\,{\small+}\,\!}}y\phantom{{\!\,{\small+}\,\!}}\overline{z}\) \(\overline{x}\phantom{{\!\,{\small+}\,\!}}\overline{y}\phantom{{\!\,{\small+}\,\!}}z\)\(\overline{x}\phantom{{\!\,{\small+}\,\!}}\overline{y}\phantom{{\!\,{\small+}\,\!}}\overline{z}\)
000 000 000 01
001 000 000 10
010 000 001 00
011 000 010 00
100 000 100 00
101 001 000 00
110 010 000 00
111 100 000 00

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 :

\(x\)\(y\)\(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\)
000 111 111 10
001 111 111 01
010 111 110 11
011 111 101 11
100 111 011 11
101 110 111 11
110 101 111 11
111 011 111 11
Il faut être attentif aux écritures, la notation de la négation à l'aide d'une barre au-dessus d'une variable booléenne peut être source d'erreurs quand on omet d'écrire comme souvent le symbole produit pour désigner la conjonction. En effet il est facile de confondre \(\overline{x}\overline{y}\) avec \(\overline{xy}\) alors que \(\overline{x}\overline{y}\not=\overline{xy}\).

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.\qquad\text{(resp.)}\\ \end{align*} où \(\widetilde{x}_i\) désigne le littéral \(x_i\) ou \(\overline{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.

Circuits logiques

Portes logiques

Il ne reste plus beaucoup de chemin à parcourir pour passer des écritures abstraites 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 réalisées à l'aide de \(n+1\) fils électriques sous tension ou non, la tension re­pré­sen­tant la valeur 1 et l'absence de tension 0 (grossièrement).

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.. Les tables de Karnaugh sont une autre façon de représenter une table de vérité, elles permettent plus facilement de visualiser la forme d'une fonction mais ne sont efficaces que pour un nombre très restreint de variables, pas plus de quatre généralement. Elles ne sont utilisées que pour résoudre des problèmes de conception de circuit à la main.

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é suivante :

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

En effet, \(xy+x\overline{y}=x(y+\overline{y})=x.1=x\). 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 booléenne qui change de valeur. 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éenne \(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
01 11
11 11 11
10 11

Donnez la forme normale disjonctive canonique de la fonction \(f\) et simplifiez son expression à l'aide de regroupements suggérés par cette table et la règle de simplification \(a+\overline{a}b=a+b\). Dessinez le circuit logique correspondant avec les trois portes usuelles.

On veut modéliser le fonctionnement d'une machine à café qui distribue du café, du thé ou du lait en appuyant sur le bouton correspondant après qu'une pièce de 1€ a été introduite. Il est possible d'obtenir un café au lait ou un thé au lait en appuyant simultanément sur les deux boutons correspondant. Si l'opérateur appuye simultanément sur café et thé, la pièce est restituée.

On considère les 4 variables booléennes \(t,c,l\) et \(p\) qui codent les propositions suivantes :

  1. \(c=1\) si et seulement si le bouton café est enfoncé.
  2. \(t=1\) si et seulement si le bouton thé est enfoncé.
  3. \(l=1\) si et seulement si le bouton lait est enfoncé.
  4. \(p=1\) si et seulement si une pièce de 1€ a été introduite.

(1) Trouvez les expressions des fonctions booléennes \(C\), \(T\), \(L\) et \(P\) de ces 4 variables et qui indiquent respectivement la distribution ou non d'un café, thé ou lait et la restitution ou non de la pièce de monnaie.

(2) Simplifiez les expressions de ces fonctions.

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.

Travaux pratiques

En séance

On veut réaliser un script Python qui calcule la table de vérité et les formes normales conjonctives et disjonctives d'une expression logique. Nous supposerons que cette expression ne peut contenir que les symboles suivants :

Ainsi la chaîne de caractères

!(p + q) * (!p + r) + (p * q)
code l'expression booléenne \[(\overline{p+q}).(\overline{p}+r)+p.q\]

où \(p\), \(q\) et \(r\) désignent trois variables booléennes. On décompose le travail en écrivant plusieurs fonc­tions.

Écrivez une fonction ListerVariables(expression) qui renvoie la liste des variables booléennes utilisées dans la chaîne expression. Vous trierez cette liste de caractères dans l'ordre alphabétique avec la fonction sorted du Python dans un premier temps, puis avec l'algorithme du tri à bulles étudié dans le cours d'algorithmique si vous avez traité les autres questions. Cette fonction doit donc renvoyer la liste ["p","q","r"] pour l'expression de l'exemple introductif.
Écrivez une fonction DicoVariables(liste) qui, à partir d'une liste de caractères triés dans l'ordre alphabétique, renvoie un dictionnaire dont les clés sont ces caractères et les valeurs sont leur ordre dans la liste. Ainsi pour la liste ["p","q","r"], le dictionnaire renvoyé est {"p":0,"q":1,"r":2}.
Écrivez une fonction Int2Bin(entier,n) qui renvoie la chaîne de caractères correspondant à l'écriture binaire de l'entier passé en paramètre sur \(n\) bits.

Indication : utilisez la fonction de conversion de type bin() du Python et rajoutez les 0 nécessaires. Par exemple Int2Bin(5,5) doit renvoyer la chaîne 00101 car \(\color{yellow}101\) est l'écriture binaire de l'entier \(5\).

Écrivez une fonction Bin2Bool(bits) qui renvoie un tuple de booléens correspondant à la chaîne de caractères binaire bits. L'appel Bin2Bool("00101") doit renvoyer le tuple
(False,False,True,False,True).

Indication : on rappelle qu'un tuple ne contenant qu'un seul élément \(x\) s'écrit (x,) pour changer l'interprétation des parenthèses.

Écrivez une fonction Math2Python(expression,vecteur,dicovar) qui convertit la chaîne de caractère expression codant une expression booléenne en une nouvelle chaîne en remplaçant : Ainsi, avec l'expression de l'exemple introductif et le tuple vecteur=(False,False,True), Math2Python doit renvoyer la chaîne
"not (False or False) and (not False or True) or False and False"
Indication : vous pouvez créer un autre dictionnaire dans votre fonction pour la conversion des trois opérateurs logiques.
Python peut évaluer une chaîne de caractères à l'aide de la fonction eval, ainsi eval("True or False") va renvoyer la valeur logique True. À l'aide des fonctions écrites précédemment écrivez une fonction TableVerite(expression,dicovar) qui renvoie la table de vérité de l'expression passée en paramètre sous forme d'une liste de valeurs binaires 0 ou 1. La décomposition binaire de l'indice de la liste fournit le tuple de booléens à intégrer dans l'expression. Avec l'expression de l'exemple introductif, si on note L la liste renvoyée par la fonction TableVerite, on a L[3] = 0.

Indication : il suffit d'évaluer la chaîne de ca­rac­tè­res obtenue à l'aide de la fonction Math2Python pour chacun des \(2^n\) tuples de booléens possibles.

Écrivez la ou les fonctions nécessaires pour afficher la table de vérité.
Écrivez les procédures FNC(TDV,listevar) et FND(TDV,listevar) qui affichent respectivement les formes normales conjonctives et disjonctives (sous forme de chaînes de caractères) de l'expression logique à l'aide de sa table de vérité passée en paramètre. le paramètre listevar est la liste des variables triées de la première question.

Indication : en concaténant la chaîne "\u0304" à un caractère à afficher avec la fonction print, celui-ci est surmonté d'une barre, ainsi print("a\u0304") affiche ā. Avec l'expression de l'exemple introductif, la procédure FND(TDV,listevar) doit afficher

p̄q̄r̄ + p̄q̄r + pqr̄ + pqr

Compléments hors séance

Écrivez une fonction Gray(n) qui renvoie le code de Gray de l'entier naturel \(n\) passé en paramètre.
Écrivez une fonction Python Karnaugh4(f) qui affiche la table de Karnaugh de la fonction à 4 variables passée en paramètre.
Écrivez une fonction Python Simplifier4(f) qui renvoie la fonction booléenne simplifiée (le cas échéant) de la fonction à 4 variables passée en paramètre.